“机器学习”系列之决策树

本文介绍决策树的ID3、C4.5和CART三种生成算法。ID3以信息增益划分，有过拟合等缺点；C4.5用信息增益率，改进了缺失值处理等；CART为二叉树，用基尼系数，可分类回归，有独特剪枝和平衡策略。还附ID3实现及sklearn中CART的使用代码。

“机器学习”系列之决策树

0 前言

决策树是一种机器学习的方法。决策树的生成算法有ID3, C4.5和CART等。决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。算法主要是公式的讲解，如果初学建议先去看一下这方面的图例说明，再回来看此项目。

1 ID3

1.1 思想

从信息论的知识中我们知道：信息熵越大，从而样本纯度越低，。ID3 算法的核心思想就是以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间（C4.5 也是贪婪搜索）。 其大致步骤为：（1）初始化特征集合和数据集合；（2）计算数据集合信息熵和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点；（3）更新数据集合和特征集合（删除上一步使用的特征，并按照特征值来划分不同分支的数据集合）；（4）重复 2，3 两步，若子集值包含单一特征，则为分支叶子节点。

1.2 划分标准

ID3 使用的分类标准是信息增益，它表示得知特征 A 的信息而使得样本集合不确定性减少的程度。数据集的信息熵公式如下：

其中 $C_k$Ck 表示集合 D 中属于第 k 类样本的样本子集。针对某个特征 A，对于数据集 D 的条件熵  $H(D\mathrm{\mid }A)$H(D∣A) 为：

其中 $D_i$Di 表示 D 中特征 A 取第 i 个值的样本子集， $D_{i}k$Dik 表示 $D_i$Di 中属于第 k 类的样本子集。信息增益 = 信息熵 - 条件熵：

信息增益越大表示使用特征 A 来划分所获得的“纯度提升越大”

1.3 缺点

ID3 没有剪枝策略，容易过拟合；信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；只能用于处理离散分布的特征；没有考虑缺失值。

2 C4.5

C4.5 算法最大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准。

2.1 思想

C4.5 相对于 ID3 的缺点对应有以下改进方式：（1）引入悲观剪枝策略进行后剪枝；（2）引入信息增益率作为划分标准；（3）将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择- - （4）信息增益最大的点作为该连续特征的二元离散分类点；

2.2 对于缺失值的处理可以分为两个子问题

（1）问题一：在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）（2）问题二：选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）（3）针对问题一，C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；（4）针对问题二，C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

2.3 划分标准

利用信息增益率可以克服信息增益的缺点，其公式如下

$H_A(D)$HA(D)称为特征 A 的固有值。这里需要注意，信息增益率对可取值较少的特征有所偏好（分母越小，整体越大），因此 C4.5 并不是直接用增益率最大的特征进行划分，而是使用一个启发式方法：先从候选划分特征中找到信息增益高于平均值的特征，再从中选择增益率最高的。

2.4 剪枝策略

为什么要剪枝：过拟合的树在泛化能力的表现非常差。

2.4.1 预剪枝

在节点划分前来确定是否继续增长，及早停止增长的主要方法有：（1）节点内数据样本低于某一阈值；（2）所有节点特征都已分裂；（3）节点划分前准确率比划分后准确率高。（4）预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。

2.4.2 后剪枝

在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。C4.5 采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但同时其训练时间会大的多。

2.5 缺点

剪枝策略可以再优化；C4.5 用的是多叉树，用二叉树效率更高；C4.5 只能用于分类；C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

3 CART

ID3 和 C4.5 虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但是其生成的决策树分支、规模都比较大，CART 算法的二分法可以简化决策树的规模，提高生成决策树的效率。

3.1 思想

CART 包含的基本过程有分裂，剪枝和树选择。分裂：分裂过程是一个二叉递归划分过程，其输入和预测特征既可以是连续型的也可以是离散型的，CART 没有停止准则，会一直生长下去；剪枝：采用代价复杂度剪枝，从最大树开始，每次选择训练数据熵对整体性能贡献最小的那个分裂节点作为下一个剪枝对象，直到只剩下根节点。CART 会产生一系列嵌套的剪枝树，需要从中选出一颗最优的决策树；树选择：用单独的测试集评估每棵剪枝树的预测性能（也可以用交叉验证）。

3.2 CART 在 C4.5 的基础上进行了很多提升。

C4.5 为多叉树，运算速度慢，CART 为二叉树，运算速度快；C4.5 只能分类，CART 既可以分类也可以回归；CART 使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算；CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中；CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法。

3.3 划分标准

熵模型拥有大量耗时的对数运算，基尼指数在简化模型的同时还保留了熵模型的优点。基尼指数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（率）正好相反。

其中k代表类别基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。因此基尼指数越小，则数据集纯度越高。基尼指数偏向于特征值较多的特征，类似信息增益。基尼指数可以用来度量任何不均匀分布，是介于 0~1 之间的数，0 是完全相等，1 是完全不相等，当 CART 为二分类，其表达式为：

在平方运算和二分类的情况下，其运算更加简单。当然其性能也与熵模型非常接近。那么问题来了：基尼指数与熵模型性能接近，但到底与熵模型的差距有多大呢？我们知道$ln(x)=-1+x+o(x)$ln(x)=−1+x+o(x)，所以

基尼指数可以理解为熵模型的一阶泰勒展开

3.4 缺失值处理

模型对于缺失值的处理会分为两个子问题：（1）如何在特征值缺失的情况下进行划分特征的选择？（2）选定该划分特征，模型对于缺失该特征值的样本该进行怎样处理？对于问题 1，CART 一开始严格要求分裂特征评估时只能使用在该特征上没有缺失值的那部分数据，在后续版本中，CART 算法使用了一种惩罚机制来抑制提升值，从而反映出缺失值的影响（例如，如果一个特征在节点的 20% 的记录是缺失的，那么这个特征就会减少 20% 或者其他数值）。对于问题 2，CART 算法的机制是为树的每个节点都找到代理分裂器，无论在训练数据上得到的树是否有缺失值都会这样做。在代理分裂器中，特征的分值必须超过默认规则的性能才有资格作为代理（即代理就是代替缺失值特征作为划分特征的特征），当 CART 树中遇到缺失值时，这个实例划分到左边还是右边是决定于其排名最高的代理，如果这个代理的值也缺失了，那么就使用排名第二的代理，以此类推，如果所有代理值都缺失，那么默认规则就是把样本划分到较大的那个子节点。代理分裂器可以确保无缺失训练数据上得到的树可以用来处理包含确实值的新数据。

3.5 剪枝策略

采用一种“基于代价复杂度的剪枝”方法进行后剪枝，这种方法会生成一系列树，每个树都是通过将前面的树的某个或某些子树替换成一个叶节点而得到的，这一系列树中的最后一棵树仅含一个用来预测类别的叶节点。然后用一种成本复杂度的度量准则来判断哪棵子树应该被一个预测类别值的叶节点所代替。这种方法需要使用一个单独的测试数据集来评估所有的树，根据它们在测试数据集熵的分类性能选出最佳的树。首先我们将最大树称为$T_0$T0 ，我们希望减少树的大小来防止过拟合，但又担心去掉节点后预测误差会增大，所以我们定义了一个损失函数来达到这两个变量之间的平衡。损失函数定义如下：

$T$T 为任意子树，$C(T)$C(T) 为预测误差， $\mathrm{\mid }T\mathrm{\mid }$∣T∣ 为子树 $T$T 的叶子节点个数， $a$a 是参数， $C(T)$C(T) 衡量训练数据的拟合程度， $\mathrm{\mid }T\mathrm{\mid }$∣T∣ 衡量树的复杂度， $a$a 权衡拟合程度与树的复杂度。那么如何找到合适的 $a$a 来使得复杂度和拟合度达到最好的平衡点呢，最好的办法就是另 $a$a 从 0 取到正无穷，对于每一个固定的 $a$a ，我们都可以找到使得 $C_a(T)$Ca(T) 最小的最优子树 $T(a)$T(a) 。当 $a$a 很小的时候， $T_0$T0 是最优子树；当 $a$a 最大时，单独的根节点是这样的最优子树。随着 $a$a 增大，我们可以得到一个这样的子树序列： $T_i+1$Ti+1 ，这里的子树 $T_0{T}_1{T}_2\mathrm{.}\mathrm{.}\mathrm{.}{T}_n$T0T1T2...Tn 生成是根据前一个子树 $T_i$Ti 剪掉某一个内部节点生成的。Breiman 证明：将 $a$a 从小增大，0=a0[ai,ai+1)[ai,ai+1) 中，子树 $T_i$Ti 是这个区间里最优的。这是代价复杂度剪枝的核心思想。每次剪枝都是针对某个非叶节点，其他节点不变，所以我们只需要计算该节点剪枝前和剪枝后的损失函数即可。对于任意内部节点 t，剪枝前的状态，有 $\mathrm{\mid }{T}_i\mathrm{\mid }$∣Ti∣ 个叶子节点，预测误差是 $C(T_i)$C(Ti) ；剪枝后的状态：只有本身一个叶子节点，预测误差是 $C(t)$C(t) 。因此剪枝前以 t 节点为根节点的子树的损失函数是：

剪枝后的损失函数是

通过 Breiman 证明我们知道一定存在一个 $a$a 使得 $C_a(T)=C_a(t)$Ca(T)=Ca(t) ，使得这个值为：

$a$a 的意义在于， $[a_i,a_i+1)$[ai,ai+1) 中，子树 $T_i$Ti 是这个区间里最优的。当 $a$a 大于这个值是，一定有 $C_a(T)>C_a(t)$Ca(T)>Ca(t) ，也就是剪掉这个节点后都比不剪掉要更优。所以每个最优子树对应的是一个区间，在这个区间内都是最优的。然后我们对 $T_i$Ti 中的每个内部节点 t 都计算：

$g(t)$g(t) 表示阈值，故我们每次都会减去最小的 $T_i$Ti 。

3.6 类别不平衡

CART 的一大优势在于：无论训练数据集有多失衡，它都可以将其子冻消除不需要建模人员采取其他操作。CART 使用了一种先验机制，其作用相当于对类别进行加权。这种先验机制嵌入于 CART 算法判断分裂优劣的运算里，在 CART 默认的分类模式中，总是要计算每个节点关于根节点的类别频率的比值，这就相当于对数据自动重加权，对类别进行均衡。对于一个二分类问题，节点 node 被分成类别 1 当且仅当：

比如二分类，根节点属于 1 类和 0 类的分别有 20 和 80 个。在子节点上有 30 个样本，其中属于 1 类和 0 类的分别是 10 和 20 个。如果 10/20>20/80，该节点就属于 1 类。通过这种计算方式就无需管理数据真实的类别分布。假设有 K 个目标类别，就可以确保根节点中每个类别的概率都是 1/K。这种默认的模式被称为“先验相等”。先验设置和加权不同之处在于先验不影响每个节点中的各类别样本的数量或者份额。先验影响的是每个节点的类别赋值和树生长过程中分裂的选择。

3.7 回归树

CART（Classification and Regression Tree，分类回归树），从名字就可以看出其不仅可以用于分类，也可以应用于回归。其回归树的建立算法上与分类树部分相似，这里简单介绍下不同之处。

3.7.1 连续值处理

对于连续值的处理，CART 分类树采用基尼系数的大小来度量特征的各个划分点。在回归模型中，我们使用常见的和方差度量方式，对于任意划分特征 A，对应的任意划分点 s 两边划分成的数据集 $D_1$D1 和 $D_2$D2 ，求出使 $D_1$D1 和 $D_2$D2 各自集合的均方差最小，同时 $D_1$D1 和 $D_2$D2 的均方差之和最小所对应的特征和特征值划分点。表达式为：

其中， $c_1$c1 为 $D_1$D1 数据集的样本输出均值， $c_2$c2 为 $D_2$D2 数据集的样本输出均值。

3.7.2 预测方式

对于决策树建立后做预测的方式，上面讲到了 CART 分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

4 代码实现

4.1 导入相关包

In [1]

import numpy as npimport pandas as pdimport matplotlib.pyplot as plt%matplotlib inlinefrom sklearn.datasets import load_irisfrom sklearn.model_selection import train_test_splitfrom collections import Counterimport mathfrom math import logimport pprint

登录后复制

4.2 数据定义

In [2]

def create_data():    datasets = [['青年', '否', '否', '一般', '否'],               ['青年', '否', '否', '好', '否'],               ['青年', '是', '否', '好', '是'],               ['青年', '是', '是', '一般', '是'],               ['青年', '否', '否', '一般', '否'],               ['中年', '否', '否', '一般', '否'],               ['中年', '否', '否', '好', '否'],               ['中年', '是', '是', '好', '是'],               ['中年', '否', '是', '非常好', '是'],               ['中年', '否', '是', '非常好', '是'],               ['老年', '否', '是', '非常好', '是'],               ['老年', '否', '是', '好', '是'],               ['老年', '是', '否', '好', '是'],               ['老年', '是', '否', '非常好', '是'],               ['老年', '否', '否', '一般', '否'],               ]    labels = [u'年龄', u'有工作', u'有自己的房子', u'信贷情况', u'类别']    # 返回数据集和每个维度的名称    return datasets, labels

登录后复制In [3]

datasets, labels = create_data()

登录后复制In [4]

train_data = pd.DataFrame(datasets, columns=labels)

登录后复制In [5]

train_data

登录后复制

    年龄 有工作 有自己的房子 信贷情况 类别0   青年   否      否   一般  否1   青年   否      否    好  否2   青年   是      否    好  是3   青年   是      是   一般  是4   青年   否      否   一般  否5   中年   否      否   一般  否6   中年   否      否    好  否7   中年   是      是    好  是8   中年   否      是  非常好  是9   中年   否      是  非常好  是10  老年   否      是  非常好  是11  老年   否      是    好  是12  老年   是      否    好  是13  老年   是      否  非常好  是14  老年   否      否   一般  否

登录后复制

4.3 定义计算熵函数

In [6]

# 熵def calc_ent(datasets):    data_length = len(datasets)    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(datasets, axis=0):    data_length = len(datasets)    feature_sets = {}    for i in range(data_length):        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)*calc_ent(p) for p in feature_sets.values()])    return cond_ent# 信息增益def info_gain(ent, cond_ent):    return ent - cond_entdef info_gain_train(datasets):    count = len(datasets[0]) - 1    ent = calc_ent(datasets)    best_feature = []    for c in range(count):        c_info_gain = info_gain(ent, cond_ent(datasets, axis=c))        best_feature.append((c, c_info_gain))        print('特征({}) - info_gain - {:.3f}'.format(labels[c], c_info_gain))    # 比较大小    best_ = max(best_feature, key=lambda x: x[-1])    return '特征({})的信息增益最大，选择为根节点特征'.format(labels[best_[0]])

登录后复制In [7]

info_gain_train(np.array(datasets))

登录后复制

特征(年龄) - info_gain - 0.083特征(有工作) - info_gain - 0.324特征(有自己的房子) - info_gain - 0.420特征(信贷情况) - info_gain - 0.363

登录后复制

'特征(有自己的房子)的信息增益最大，选择为根节点特征'

登录后复制

4.4 利用ID3算法生成决策树

In [8]

# 定义节点类 二叉树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}    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)        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):            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):        """        input:数据集D(DataFrame格式)，特征集A，阈值eta        output:决策树T        """        _, y_train, features = train_data.iloc[:, :-1], train_data.iloc[:, -1], train_data.columns[:-1]        # 1,若D中实例属于同一类Ck，则T为单节点树，并将类Ck作为结点的类标记，返回T        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,计算最大信息增益 同5.1,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)        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)        # pprint.pprint(node_tree.tree)        return node_tree    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)

登录后复制In [9]

datasets, labels = create_data()data_df = pd.DataFrame(datasets, columns=labels)dt = DTree()tree = dt.fit(data_df)

登录后复制In [10]

tree

登录后复制

{'label:': None, 'feature': 2, 'tree': {'否': {'label:': None, 'feature': 1, 'tree': {'否': {'label:': '否', 'feature': None, 'tree': {}}, '是': {'label:': '是', 'feature': None, 'tree': {}}}}, '是': {'label:': '是', 'feature': None, 'tree': {}}}}

登录后复制In [11]

dt.predict(['老年', '否', '否', '一般'])

登录后复制

'否'

登录后复制

4.4 利用 sklearn.tree.DecisionTreeClassifier函数用于构建决策树,默认使用CART算法

In [12]

# datadef 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)

登录后复制In [13]

from sklearn.tree import DecisionTreeClassifierfrom sklearn.tree import export_graphvizimport graphviz

登录后复制In [14]

clf = DecisionTreeClassifier()clf.fit(X_train, y_train,)

登录后复制In [15]

clf.score(X_test, y_test)

登录后复制

0.9

登录后复制In [16]

tree_pic = export_graphviz(clf, out_file="mytree.pdf")with open('mytree.pdf') as f:    dot_graph = f.read()

登录后复制In [17]

# 决策树可视化graphviz.Source(dot_graph)

登录后复制