决策树+Python3实现ID3

1. 什么是决策树

决策树（decision tree）是一种基本的分类与回归方法。决策树的生成算法主要有ID3，C4.5，CART等。决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。

这里通过一个简单的例子说明决策树的构成思路：

给出如下的一组数据，一共有十五个样本，每个样本有年龄，有工作，有自己的房子，信贷情况四个属性，最后判断是否给申请人批准贷款。

然后利用这一组附带分类结果的样本可以训练出多种多样的决策树，这里为了简化过程，我们假设决策树为二叉树，且类似于下图：

首先选择A₂(是否有工作)作为特征进行划分，它将训练数据集 D 划分为两个子集D₁(A₂取值为“是”)和D₂(A₂取值为“否”)。由于 D₁ 只有同一类的样本点，所以它成为一个叶节点。

对D₂我这里选择A3(是否有自己的房子)作为节点特征进行划分。A3有两种情况，一种对应的是“有房子”，其划分只有同一类节点，所以该节点为叶节点；另一种对应的是“没有房子”，其划分也只有同一类节点，所以该节点为叶节点。

所以决策树的生成只有分以下两步，这两步通常通过学习已经知道分类结果的样本来实现。

1.节点的分裂：一般当一个节点所代表的属性无法给出判断时，则选择这一节点分成2个子节点（前提是二叉树）。

2.阈值的确定：选择适当的阈值使得分类错误率最小（Trainiing error）

2. 特征的选择问题

特征的选择一般选择对训练数据能够起到良好的分类左作用的特征，如上表中“是否有工作”特征，这样可以提高决策树学习的效率。如果一个特征进行分类结果与随机分类结果没有很大的差别，则称这个特征没有分类能力。通常特征选择的准则时信息增益或信息增益比。

2.1 信息增益

为了便于说明，先给出熵与条件熵的定义。

在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设 X 是一个取有限个值的离散随机变量，其概率分布为

​ P(X = x_i) = p_i，i = 1 , 2, … , n

则随机变量 X 的熵定义为

​ H( X ) = -$\sum_{i=1}^n $p_i log p_i

若 p_i = 0, 则定义0 log 0 = 0。通常，上式中的对数以 2 为底或以 e 为底（自然对数），这时熵的单位分别称作比特（bit）或纳特( nat )。由定义可知，熵只依赖于 X 的分布，而与 X 的取值无关，所以也可将 X 的熵记作 H§ ,即

​ H( p ) = - $\sum_{i=1}^n$∑i=1n​ p_i log p_i

熵越大，随机变量的不确定性就越大。从定义可验证

​ 0 <= H( p ) <= log n

条件熵 H( Y|X ) 表示在已知随机变量 X 的条件下随机变量 Y 的不确定性。随机变量 X 给定的条件下随机变量 Y 的条件熵（conditional entropy）H( Y | X)，定义为 X 给定条件下 Y 的概率分布的熵对 X 的数学期望

​ H( Y|X) = $\sum_{i=1}^n$∑i=1n​ p_i H( Y | X = x_i)

这里，p_i = P( X = x_i), i = 1,2 …, n。

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵 （empirical conditional entropy）。

此时，如果有 0 概率，令 0 log 0 = 0 。

信息增益（information gain）表示得知特征 X 的信息而使得类 Y 的信息的不确定性减少程度。

信息增益：特征 A 对训练数据集 D 的信息增益 g(D, A)，定义为集合 D 的经验熵 H（D）与特征 A 给定条件下 D 的经验条件熵 H( D | A )之差，即

​ g( D, A ) = H(D) - H(D|A)

一般地，熵 H( Y ) 与条件熵 H( Y|X )之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

决策树学习应用信息增益准则选择特征 。给定训练数据集D 和特征 A，经验熵H(D) 示对数据集 D 进行分类的不确定性。而经验条件熵 H(D｜A) 表示在特征 A 给定的条件下对数据集 D 进行分类的不确定性。那么它们的差，即信息增益，就表示由于特征 A 而使得对数据集 D的分类的不确定性减少的程度。显然，对于数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。

根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

设训练数据集为D，|D|表示其样本容量，即样本个数。设有 K 个类C_k，k = 1,2，… ，K，|C_k|为属于类 C_k 的样本个数，$\sum_{k=1}^K$∑k=1K​|C_k| = |D|。设特征 A 有 n 个不同的取值{ a₁,a₂,…,a_n}，根据特征 A 的取值将 D 划分为 n 个子集D₁,D₂,…,D_n,|D_i|为 D_i 的样本个数，$\sum_{i=1}^n$∑i=1n​|D_i| = |D|。记子集 D_i 中属于类 C_k的样本集合为 D_ik，即D_ik = D_i$\bigcap$⋂ C_k,|D_ik| 为D_ik 的样本个数。于是信息增益的算法如下。

信息增益的算法

2.2 信息增益比

以信息增益划分训练数据集的特征，存在于偏向于选择值较多的特征的问题。使用信息增益比（information gain ratio）可以对这一问题进行校正。这是特征选择的另一准则。

特征 A 对训练数据集 D 的信息增益比 g_R(D,A)定义为其信息增益g(D, A)与训练数据集 D 关于特征 A 的值的熵 H_A(D)之比，即

3.决策树的生成

3.1 ID3 算法

ID3 算法的核心是在决策树各个节点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根节点（root node）开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；再对子节点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一棵决策树。ID3 相当于用极大似然法进行概率模型的选择。

算法流程：

输入：训练数据集 D ，特征集 A 阈值 $\varepsilon$ε；

输出：决策树 T。

(1) 若 D 中所有实例属于同一类 C_k，则 T 为单节点树，并将类 C_k 作为该节点的类标记，返回T；

(2) 若 A = $\emptyset$∅，则 T 为单节点树，并将 D 中实例数最大的类 C_k 作为该节点的类标记，返回T；

(3) 否则，计算 A 中各特征对 D 的信息增益，选择信息增益最大的特征 A_g;

(4) 如果 A_g 的信息增益小于阈值$\varepsilon$ε，则置 T 为单节点树，并将 D 中实例数最大的类 C_k 作为该节点的类标记，返回T；

(5) 否则，对A_g 的每一可能值 a_i，依 A_g = a_i 将 D 分割为若干非空子集 D_i，将D_i中实例数最大的类作为标记，构建子节点，由节点及其子节点构成树 T，返回 T；

(6) 对第 i 个子节点，以 D_i为训练集，以A-{A_g} 为特征集，递归地调用步骤1-5，得到子树 T_i，返回T_i。

3.2 C4.5 的生成算法

C4.5 算法与 ID3 算法相似，C4.5 算法对 ID3算法进行了改进。C4.5 在生成的过程中，用信息增益比来选择特征。

输入：训练数据集 D ，特征集 A 阈值 $\varepsilon$ε；

输出：决策树 T。

(1) 若 D 中所有实例属于同一类 C_k，则 T 为单节点树，并将类 C_k 作为该节点的类标记，返回T；

(2) 若 A = $\emptyset$∅，则 T 为单节点树，并将 D 中实例数最大的类 C_k 作为该节点的类标记，返回T；

(3) 否则，计算 A 中各特征对 D 的信息增益比，选择信息增益比最大的特征 A_g;

(4) 如果 A_g 的信息增益比小于阈值$\varepsilon$ε，则置 T 为单节点树，并将 D 中实例数最大的类 C_k 作为该节点的类标记，返回T；

(5) 否则，对A_g 的每一可能值 a_i，依 A_g = a_i 将 D 分割为若干非空子集 D_i，将D_i中实例数最大的类作为标记，构建子节点，由节点及其子节点构成树 T，返回 T；

(6) 对第 i 个子节点，以 D_i为训练集，以A-{A_g} 为特征集，递归地调用步骤1-5，得到子树 T_i，返回T_i。

4. ID3算法的实现

4.1 Python3实现

import numpy as np
import pandas as pd
from math import log


# 定义节点类 二叉树
class Node:
    def __init__(self, root=True, label=None, feature_name=None, feature=None):
        self.root = root
        self.label = label
        self.feature_name = feature_name
        self.feature = feature
        self.tree = {}
        self.result = {
            'label': self.label,
            'feature': self.feature,
            'tree': self.tree,
        }

    #  __repr__()方法：显示属性
    def __repr__(self):
        return '{}'.format(self.result)

    # 添加子节点
    def add_node(self, val, node):
        self.tree[val] = node

    # 使用决策树进行预测
    def predict(self, features):
        if self.root is True:
            return self.label
        return self.tree[features[self.feature]].predict(features)


class DTree:
    # 定义阈值以及空树
    def __init__(self, epsilon=0.1):
        self.epsilon = epsilon
        self._tree = {}

    # 熵
    @staticmethod
    def calc_ent(datasets):
        data_length = len(datasets)
        # 统计类别，即Ck类别个数
        label_count = {}
        for i in range(data_length):
            label = datasets[i][-1]
            if label not in label_count:
                label_count[label] = 0
            label_count[label] += 1
        # 根据信息熵公式计算
        ent = -sum([(p / data_length) * log(p / data_length, 2) for p in label_count.values()])
        return ent

    # 经验条件熵
    def cond_ent(self, datasets, axis=0):
        data_length = len(datasets)
        feature_sets = {}
        for i in range(data_length):
            # 根据axis传入的值，选择对应特征计算条件熵
            feature = datasets[i][axis]
            if feature not in feature_sets:
                feature_sets[feature] = []
            feature_sets[feature].append(datasets[i])
        cond_ent = sum([(len(p) / data_length) * self.calc_ent(p) for p in feature_sets.values()])
        return cond_ent

    # 信息增益
    @staticmethod
    def info_gain(ent, cond_ent):
        return ent - cond_ent

    # 返回最大信息增益的特征，以及信息增益，以元组的形式
    def info_gain_train(self, datasets):
        count = len(datasets[0]) - 1
        ent = self.calc_ent(datasets)
        best_feature = []
        for c in range(count):
            c_info_gain = self.info_gain(ent, self.cond_ent(datasets, axis=c))
            best_feature.append((c, c_info_gain))
        best_ = max(best_feature, key=lambda x: x[-1])

        return best_

    def train(self, train_data):
        """

        :param train_data:数据集D(DataFrame格式)，特征集A，阀值eta
        :return: 决策树T
        """
        _, y_train, features = train_data.iloc[:, :-1], train_data.iloc[:, -1], train_data.columns[:-1]

        # 1.若D中实例属于同一类ck, 则T为单节点树，并将类ck作为结点的类标记，返回T
        # value_counts()是一种查看表格某列中有多少个不同值的快捷方法，并计算每个不同值有在该列中有多少重复值。
        if len(y_train.value_counts()) == 1:
            return Node(root=True, label=y_train.iloc[0])

        # 2,若A为空，则T为单节点树，将D中实例树最大的类CK作为该节点的类标记，返回T
        if len(features) == 0:
            return Node(root=True, label=y_train.value_counts.sort_values(ascending=False).index[0])

        # 3,计算最大信息增益，Ag为信息增益最大的特征
        max_feature, max_info_gain = self.info_gain_train(np.array(train_data))
        # 获取最大信息增益特征的名称
        max_feature_name = features[max_feature]

        # 4,Ag的信息增益小于阈值eta,则置T为单节点树，并将D中是实例数最大的类ck作为该节点的类标记，返回T
        if max_info_gain < self.epsilon:
            return Node(root=True, label=y_train.value_counts().sort_values(ascending=False.index[0]))

        # 5,构建Ag子集
        node_tree = Node(root=False, feature_name=max_feature_name, feature=max_feature)
        # print(train_data[max_feature_name].value_counts())
        feature_list = train_data[max_feature_name].value_counts().index
        for f in feature_list:
            sub_train_df = train_data.loc[train_data[max_feature_name] ==
                                          f].drop([max_feature_name], axis=1)

            # 6, 递归生成树
            sub_tree = self.train(sub_train_df)
            node_tree.add_node(f, sub_tree)

        return node_tree
    # 调用train构造决策树
    def fit(self, train_data):
        self._tree = self.train(train_data)
        return self._tree
    
    # 利用已经生成的决策树进行预测
    def predict(self, x_test):
        return self._tree.predict(x_test)


if __name__ == '__main__':
    def create_data():
        datasets = [['青年', '否', '否', '一般', '否'],
                    ['青年', '否', '否', '好', '否'],
                    ['青年', '是', '否', '好', '是'],
                    ['青年', '是', '是', '一般', '是'],
                    ['青年', '否', '否', '一般', '否'],
                    ['中年', '否', '否', '一般', '否'],
                    ['中年', '否', '否', '好', '否'],
                    ['中年', '是', '是', '好', '是'],
                    ['中年', '否', '是', '非常好', '是'],
                    ['中年', '否', '是', '非常好', '是'],
                    ['老年', '否', '是', '非常好', '是'],
                    ['老年', '否', '是', '好', '是'],
                    ['老年', '是', '否', '好', '是'],
                    ['老年', '是', '否', '非常好', '是'],
                    ['老年', '否', '否', '一般', '否'],
                    ]
        labels = [u'年龄', u'有工作', u'有自己的房子', u'信贷情况', u'类别']
        # 返回数据集和每个维度的名称
        return datasets, labels
    datasets, labels = create_data()
    train_data = pd.DataFrame(datasets, columns=labels)
    datasets, labels = create_data()
    data_df = pd.DataFrame(datasets, columns=labels)
    dt = DTree()
    tree = dt.fit(data_df)
    print(tree)
    res = dt.predict(['老年', '否', '否', '一般'])
    print(res)

4.2 scikit-learn实例

import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from collections import Counter
from math import log
from sklearn.tree import DecisionTreeClassifier


# data
def create_data():
    iris = load_iris()
    df = pd.DataFrame(iris.data, columns=iris.feature_names)
    df['label'] = iris.target
    df.columns = [
        'sepal length', 'sepal width', 'petal length', 'petal width', 'label'
    ]
    data = np.array(df.iloc[:100, [0, 1, -1]])
    # print(data)
    return data[:, :2], data[:, -1]


X, y = create_data()
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)
clf = DecisionTreeClassifier()
clf.fit(X_train, y_train, )
clf.score(X_test, y_test)
res = clf.predict([[5.5, 4]])
print(res)


“”“
class sklearn.tree.DecisionTreeClassifier(criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)

 树模型参数:

-  1.criterion： gini  or  entropy

-  2.splitter： best or random 前者是在所有特征中找最好的切分点 后者是在部分特征中（数据量大的时候）

-  3.max_features： None（所有），log2，sqrt，N  特征小于50的时候一般使用所有的

-  4.max_depth： 数据少或者特征少的时候可以不管这个值，如果模型样本量多，特征也多的情况下，可以尝试限制下（预剪枝）

-  5.min_samples_split： 如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。（预剪枝）

-  6.min_samples_leaf： 这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝，如果样本量不大，不需要管这个值，大些如10W可是尝试下5（预剪枝）

-  7.min_weight_fraction_leaf：这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝默认是0，就是不考虑权重问题。一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了。

-  8.max_leaf_nodes 通过限制最大叶子节点数，可以防止过拟合，默认是"None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制具体的值可以通过交叉验证得到。（预剪枝）

-  9.class_weight：指定样本各类别的的权重，主要是为了防止训练集某些类别的样本过多导致训练的决策树过于偏向这些类别。这里可以自己指定各个样本的权重如果使用“balanced”，则算法会自己计算权重，样本量少的类别所对应的样本权重会高。

- 10.min_impurity_split：这个值限制了决策树的增长，如果某节点的不纯度(基尼系数，信息增益，均方差，绝对差)小于这个阈值则该节点不再生成子节点。即为叶子节点 。（预剪枝）
- n_estimators:要建立树的个数
”“”

4.总结

首先我们看看决策树算法的优点：

​ 1）简单直观，生成的决策树很直观。

2）基本不需要预处理，不需要提前归一化，处理缺失值。

3）使用决策树预测的代价是O(log2m)。 m为样本数。

4）既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。

5）可以处理多维度输出的分类问题。

6）相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释

7）可以交叉验证的剪枝来选择模型，从而提高泛化能力。

8） 对于异常点的容错能力好，健壮性高。

我们再看看决策树算法的***缺点***:：

1）决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。

2）决策树会因为样本发生一点点的改动（特别是在节点的末梢），导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。

3）寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。

4）有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。

5）如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善

参考资料：

《统计学习方法》第二版
scikit-learn的英文文档

如果你觉得这篇文章有收获就给我点个赞吧!

下期预告：CART