机器学习 | 决策树模型（一）理论

决策树（Decision tree）是一种基本的分类与回归方法，是一种非参数的有监督学习方法。

决策树是一种树状结构，它的每一个叶子结点对应着一个分类，非叶子结点对应着在某个属性上的划分，根据样本在该属性上的不同取值降气划分成若干个子集。其基本原理是通过递归切割的方法来寻找最佳分类标准，进而最终形成规则。CATA树是对回归树用平方误差最小化准则，分类树用基尼系数最小化准则，进行特征选择，生成二叉树。

树模型算法容易理解，因为它是站在人的思维角度去解决问题，它是基于特征对实例进行分类的过程。它能够从一些列具有众多特征和标签的数据中总结出决策规则，并用树状图的结构呈现这些规则。众多集成算法的基模型均采用决策树模型，其在各个行业和领域都有广泛的应用。

决策树的学习

决策树学习是利用训练数据，根据损失函数最小化的原则建立决策树模型。决策树学习通常包括三个步骤：特征选择、决策树的生成和决策树的剪枝。

节点 根节点： 没有进边，有出边。包含最初的，针对特征的提问。 中间节点： 既有进边也有出边，进边只有一条，出边可以有很多条。都是针对特征的提问。 叶子节点： 有进边，没有出边，每个叶子节点都是一个类别标签。 子节点和父节点：在两个相连的节点中，更接近根节点的是父节点，另一个是子节点

决策树学习用损失函数来完成决策树模型的学习，即寻找一棵不仅对训练数据具有很好的拟合，且对未知数据具有很好的预测的树模型。损失函数通常是正则化的极大似然函数，决策树的学习策略是以损失函数为目标函数的最小化。

特征选择

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。但这样构建的决策树很有可能会发生过拟合现象，此时需要对树模型进行剪枝，使它变得更简单，从而具有更好的泛化能力。若开始时特征数量就很多，也可以在决策树学习开始时进行特征选择，只留下对训练数据有足够分类能力的特征。

不纯度

特征选择在于选择对训练数据具有分类能力的特征。决策树需要找出最佳节点和最佳的分枝方法，即特征选择是决定用哪个特征来划分特征空间。而衡量这个"最佳"的指标叫做"不纯度"。

不纯度 决策树的每个叶子节点中都会包含一组数据，在这组数据中，如果有某一类标签占有较大的比例，我们就说叶子节点"纯"，分枝分得好。某一类标签占的比例越大，叶子就越纯，不纯度就越低，分枝就越好。如果没有哪一类标签的比例很大，各类标签都相对平均，则说叶子节点"不纯"，分枝不好，不纯度高。

通常来说，不纯度越低，决策树对训练集的拟合越好。现在使用的决策树算法在分枝方法上的核心大多是围绕在对某个不纯度相关指标的最优化上。

计算不纯度的方法是由误差率衍生而来的，其计算公式为

error(t) = 1-max_{i=1}[p(i|t)]

其中

为决策树的某个节点，

D_t

是

节点所对应的数据集，

p(i|t)

是给定节点

中属于类别的样本所占有的比例，这个比例越高，则代表叶子越纯。

信息增益

由不纯度衍生了两个准则用于特征选择，分别是经验熵、基尼指数。而由经验熵、基尼指数可以计算出信息增益或信息增益率。

决策树学习通过信息增益准则选择特征。因为信息增益大的具有更强的分类能力。具体方法：对于训练数据集，计算每个特征的信息增益，比较大小，选择信息增益大的那个特征。

信息增益（information gain）表示由于特征

的信息而使得类

的信息的不确定性的减少程度。决策树中信息增益等价于训练集中类与特征的互信息。

信息增益定义集合

的经验熵

H(D)

与特征

给定条件下

的经验条熵

H(D|X)

之差。

G(D,X)=H(D)-H(D|X)

这里需要先理解熵和条件熵的概念。

熵

在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设

是一个取有限个值的离散随机变量，其概率分布为

P(X=x_i)=p_i,,,,,,i=1,2,3,cdots,n

则随机变量

的熵定义为

H(X)=-sum_{i=1}^np_ilog p_i

其中若

p_i

=0，则定义

0log 0=0

，通常对数

log

是以

为底或以

为低，熵只依赖于

的分布，与

的取值无关。

熵越大，随机变量的不确定性就越大。则

0leq H(p)leq log n

条件熵

设有随机变量

(X,Y)

，其联合概率分布为

P(X=x_i,Y=y_i)=p_{ij},,,,, i=1,2,3,cdots,n;,,,j=1,2,3,cdots,m

条件熵

H(Y|X)

表示在已知随机变量

的条件下随机变量

的不确定性。其定义为

给定条件下

的条件概率分布的熵对

的数学期望

H(Y|X)=sum_{i=1}^{n}P(X=x_i)H(Y|X=x_i)

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

信息增益的算法

输入：训练数据集

和特征

；

输出：特征

对训练数据集

的信息增益

g(D,A)

。

1）计算经验熵

H(D)

H(D) = -sum_{k=1}^K frac{|C_k|}{|D|}log_2frac{|C_k|}{|D|}

2）计算经验条件熵

H(D|A)

H(D,A)=sum_{i=1}^n frac{|D_i|}{|D|}H(D_i)=-sum_{i=1}^n frac{|D_i|}{|D|}sum_{k=1}^K frac{|D_{ik}|}{|D_i|}log_2frac{|D_{ik}|}{|D_i|}

3）计算信息增益

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

其中

|D|

表示样本个数，

|C_k|

为

个类

C_k

的样本个数。根据特征

的取值将

划分为

个子集，

|D_i|

为其中

D_i

子集的样本个数。

D_{ik}

为子集

D_i

中属于类

C_k

的样本的集合（

D_{ik}=D_ibigcap C_k

），

|D_{ik}|

为集

D_i

的样本个数。

以上计算信息增益即不纯度的下降是利用经验熵减去条件熵得到的，此外，在回归树中将会运用基尼指数代替经验熵或条件熵来计算信息增益或不纯度的下降。

基尼指数

基尼指数

Gini (D)

：对于给定集合

，基尼指数为

Gini(D)=1-sum_{k=1}^Kleft(frac{|C_k|}{|D|}right)^2

是类的个数，

C_k

是

中属于第

类的样本子集

基尼指数

Gini (D,A)

：集合

根据特征

是否取某一可能值

被切割成

D_1

和

D_2

，则特征

的条件下，集合

的基尼指数为：

Gini(D,A)=frac{|D_1|}{|D|}Gini(D_1) frac{|D_2|}{|D|}Gini(D_2)

运用基尼指数计算信息增益或不纯度下降数可类比经验熵。基尼指数

Gini(D)

，表示集合

的不确定性，基尼指数

Gini(D,A

表示经

A=a

分割后集合

的不确定性。基尼指数数值越大，样本集合的不确定性也就越大。。

为什么有了信息熵还要考虑采用基尼系数作为选择的方式？ 在ID3算法使用信息增益来选择特征，信息增益大的优先选择。在C4.5算法采用信息增益比来选择特征，以减少信息增益容易选择特征值多的特征的问题（避免高度分枝属性）。 ID3和C4.5，都是基于信息论的熵模型的，会涉及大量的对数运算。简化模型同时也不至于完全丢失熵模型的优点。CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益（率）是相反的。

以上分别介绍了三种方法，分类误差、经验熵、基尼指数，其本质上都相同，在类分布均衡时（即当

p=0.5

时）达到最大值，而当所有记录都属于同一个类时（

p=1

或

p=0

）达到最小值。换而言之，在纯度较高时三个指数均较低，而当纯度较低时，三个指数都比较大，且可以计算得出，熵在

[0-1]

区间内分布，而

Gini

指数和分类误差均在

[0-0.5]

区间内分布，三个指数随某变量占比增加而变化的曲线如下所示：

将以上较难理解的信息增益，简单的讲：一个父节点下可能有多个子节点，而每个子节点又有自己的信息熵，所以父节点信息熵和子节点信息熵之差，应该是父节点的经验熵减去所有子节点经验熵的加权平均（即条件熵）。其中，权重是使用单个叶子节点上所占的样本量比上父节点上的总样本量来确定的一个权重。

I(child)=sum_{j=1}^{k}frac{N(v_j)}{N}

而父节点和子节点的不纯度下降数可由下述公式进行计算：

Delta = I(parent)-I(child)

I(.)

是给定结点的不纯性度量（即基尼系数或经验熵），

是父结点上的样本数，

是这一层上子节点的个数，

N(vj)

是与子结点

相关联的样本个数。决策树算法通常选择最大化增益。最大化增益等价于最小化子结点的不纯性衡量的加权平均。

决策树的生成

学习决策树，总会先学习三种决策树模型，分别为Quinalan在1956年提出的ID3算法及1993年提出的C4.5算法，以及由Breiman等人在1984年提出的CART算法。

决策树算法	算法描述
ID3算法	其核心是在决策树的各级节点上，使用信息增益方法的选择标准，来帮助确定生产每个节点时所对应采用的合适属性，不能自动分箱，不能剪枝。
C4.5算法	相对于ID3改进是使用信息增益率来选择节点属性。克服ID3点不足： ID3只适用于离散的描述属性；C4.5可以处理连续和离散属性；可以剪枝。
CART算法	通过构建树、修剪树、评估树来构建一个二叉树。通过控制树的结构来控制模型：当终节点是连续变量是——回归树；当终节点是分类变量是——分类树。

以下将详细介绍三种经典决策树算法。

ID3算法

ID3算法原型见于J.R Quinlan的博士论文，是基础理论较为完善，使用较为广泛的决策树模型，在此基础上J.RQuinlan进行优化后，陆续推出了C4.5和C5.0决策树算法，后二者现已成为当前最流行的决策树算法。

ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征，递归地构建决策树。具体做法：从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点特征，由该特征的不同取值建立子节点；再对节点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。

ID3决策树生长

`ID3`决策树是以`信息增益`作为树生长的条件。下面以一个简单的例子来体会ID3算法的精髓。

现在有如下数据集，是一个消费者个人属性和信用评分数据，标签是"是否会发生购买电脑行为"，仍然是个而分类问题，在此数据集之上我们使用ID3构建决策树模型，并提取有效的分类规则。

第一步计算经验熵：

H(D) = -sum_{k=1}^K frac{|C_k|}{|D|}log_2frac{|C_k|}{|D|} = -frac{9}{14}log_2frac{9}{14}-frac{5}{14}log_2frac{5}{14}=0.940

第二步计算条件熵：

依次选取各特征来尝试进行切分，并计算切分完成后的子节点的条件熵。首先选取Age列进行切分，Age是三分类的离散变量，则用Age对根节点进行切分得到三个分支，分别对应一个Age的取值，分支所指向的子节点为对应的切分后的数据集：

条件熵

H(D,A)=sum_{i=1}^n frac{|D_i|}{|D|}H(D_i)=-sum_{i=1}^n frac{|D_i|}{|D|}sum_{k=1}^K frac{|D_{ik}|}{|D|}log_2frac{|D_{ik}|}{|D|}

=frac{5}{14} times (-frac{2}{5}log_2frac{2}{5}-frac{3}{5}log_2frac{3}{5}) frac{4}{14} times (-frac{4}{4}log_2frac{4}{4}-frac{0}{4}log_2frac{0}{4}) frac{5}{14} times (-frac{3}{5}log_2frac{3}{5}-frac{2}{5}log_2frac{2}{5})

H(14,Age)=0.694

第三步计算信息增益：

Gain(D,Age)=H(D)-H(D|Age)=0.940-0.694=0.246

依此类推计算其他几个特征的信息增益：

Gain(D,Income)=H(D)-H(D|Income)=0.029 \ Gain(D,Student)=H(D)-H(D|Student)=0.15 \ Gain(D,Credit_{rating})=H(D)-H(D|Credit_{rating})=0.029

然后比较哪个信息增益大，就选用哪个特征进行分支。即先按年龄进行分支。因Age:30--40分类指标所指向的数据集不纯度为0，则不需要再进行切分。而其余均需要继续切分。再次按照上面的方法进行切分，直至所有叶子节点的不纯度为0而停止切分。此例切分结构即ID3 决策树模型如下图所示。

总的来说，决策树模型是一个典型的贪心模型，总目标是一个全局最优解，即一整套合理的分类规则使得最终叶节点的纯度最高，但全局最优解在随特征增加而呈现指数级增加的搜索空间内很难高效获取，因此我们退而求其次考虑采用局部最优来一步步推导结果——只要保证信息增益最大，我们就能得到次最优的模型。当然，局部最优不一定等于全局最优，接下来我们就ID3可能存在的一些问题及改进方向进行一些讨论。

ID3算法的局限性

ID3局限主要源于局部最优化条件，即信息增益的计算方法，其局限性主要有以下几点：

分支度越高（分类水平越多）的离散变量往往子节点的总信息熵会更小，ID3是按照某一列进行切分，有一些列的分类可能不会对我需要的结果有足够好的指示。极限情况下取ID作为切分字段，每个分类的纯度都是100%，因此这样的分类方式是没有效益的。也就说ID3算法本身对取值很多的分类特征有所偏好。
不能直接处理连续型变量，若要使用ID3，则首先需要对连续变量进行离散化。
对缺失值较为敏感，使用ID3之前需要提前对缺失值进行处理。
没有剪枝的设置，容易导致过拟合，即在训练集上表现很好，测试集上表现很差。
通过计算信息增益、信息增益比、基尼系数作为特征选择准则，从根节点开始，递归地产生决策树。这相当于利用不纯度不断选取局部最优特征，或将训练集分割为能够基本分类正确的子集。

C4.5算法

1、修改局部最优条件

C4.5与ID3相似，是对ID3算法进行了改进。ID3是基于信息增益来选择特征，而C4.5是以信息增益率来选择特征。

信息增益率是用信息增益除以一个信息值IV（Information Value）

IV = -sum_{i=1}^n frac{|D_i|}{|D|}log_2frac{|D_i|}{|D|}

这里注意与经验熵比较，经验熵的分子

|C_k|

为

个类

C_k

的样本个数，

frac{|C_k|}{|D|}

即某个类别样本占总样本的比例。IV值分子

|D_i|

为

D_i

子集的样本个数，

frac{|D_i|}{|D|}

即某子节点的样本总数占父节点总样本数的比例。这其实就是我们加权求和时的"权重"。这样的一个指标，让我们在切分的时候自动避免那些分类水平太多，经验熵减小过快的特征。

很明显，IV可作为惩罚项带入子节点的经验熵计算中。可以简单计算得出，当取ID特征作为切分字段时，IV值为

log_2(14)

(ID特征一共有14个取值) 。所以IV值会随着分类的数量增多而增大，从而解决ID3算法偏好于分类取值更多的那种特征带来的问题。比如这里我们重新计算Age这个特征的信息增益率

IV(Age) = -frac{5}{14}log_2frac{5}{14}-frac{4}{14}log_2frac{4}{14} -frac{5}{14}log_2frac{5}{14} = 1.577

则信息增益率为

Gain_ratio = frac{Gain(Age)}{IV(Age)}=frac{0.246}{1.577}=0.156

然后同ID3算法，进一步计算其他各字段的Gain_ratio值，并选取Gain_ratio值最大的特征进行分支。

2、连续变量处理手段

ID3不能处理连续型变量，在C4.5中，同样还增加了针对连续变量的处理手段。

算法首先会对这一列数进行从小到大的排序。
选取相邻的两个数的中间数作为切分数据集的备选点，若一个连续变量有

个值，则在C4.5的处理过程中将产生

N-1

个备选切分点，并且每个切分点都代表着一种二叉树的切分方案。

这里需要注意的是，此时针对连续变量的处理并非是将其转化为一个拥有

N-1

取值的分类变量，而是将其转化成了

N-1

个二分方案，而在进行下一次的切分过程中，这

N-1

个方案都要单独带入考虑，哪个切分方案所获得的信息增益率最高，就按此进行二分。

CART算法

分类与回归CART树模型是由Breiman等人在1984年提出。CART树本质其实和C4.5区别不大，只不过CART是递归地构建二叉树，即树所有的层都是二叉树，也就是每层只有两个分枝。

CATA回归树的生成

在训练数据集所在的空间中，递归地将每个空间区域划分为两个子区域，并决定每个子区域上的输出值，生产二叉树。对回归树用平方误差最小化准则

选择最优切分变量

和最优切分点

，求解

min_{j,s}left[ min_{c_1}sum_{x_i in R_1(j,s)}(y_i-c_1)^2 min_{c_2}sum_{x_i in R_2(j,s)}(y_i-c_2)^2 right]

遍历

，对固定的切分变量

扫描切分点

，使得上式达到最小值的对

(j,s)

，依此对输入空间划分为两个区域。不断循环直至满足条件停止。

CATA分类树的生成

用基尼系数选择最优特征，同时决定该特征的最优二值切分点。

计算每个特征对数据集的基尼指数。对于每个特征

，对其可能取的每个值

，将数据集切分成两部分，并计算基尼指数。选择基尼系数最小的特征以及其切分点作为最优特征和最优切分点。不断循环直至满足条件停止。

算法停止条件是节点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值，或者没有更多特征。

决策树的剪枝

决策树生成算法递归地生成决策树，直到不能继续下去为止。这样生成的决策树对训练数据的分类很准确，但对未知的测试数据的分类不那么准确。即发生过拟合现象。

过拟合 模型在训练集上表现很好，在测试集上表现很糟糕，其原因在于学习时过多地考虑如何提高对训练数据的正确学习，学习能力很强但是学得太过精细了。 欠拟合 模型在训练集和测试集上都表现糟糕，学习能力不足。

决策树的简化过程称为剪枝（pruning）。决策树的剪枝一般通过极小化决策树整体的损失函数或代价函数来实现。用的是正则化极大似然估计进行模型选择。损失函数定义为模型拟合程度和模型复杂度求和。

C_alpha(T)=C(T) alpha|T|

其中

C(T)

为

C(T) = -sum_{t=1}^{|T|}sum_{k=1}^K D_{tk}log_2frac{|D_{tk}|}{|D_t|}

树

的叶子节点个数为

|T|

，

是树

|T|

的叶节点，该节点有

D_t

个样本，其中

类的样本有

N_{tk}

个。

C(T)

表示模型对训练数据的预测误差，

|T|

表示模型的复杂度，参数

alpha

控制这两者之间的影响。

剪枝时，当

alpha

确定时，选择损失函数最小的模型。模型的子树越大，模型的复杂度越高，模型与训练数据的拟合越好。相反，模型的子树越小，模型的复杂度越低，模型与训练数据的拟合越不好。损失函数表示了对两者的平衡。

剪枝策略

预剪枝

决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化能力的提升，则停止划分并将该结点标记为叶子结点。

优缺点：降低过拟合风险，减少训练和测试时间开销。但“贪心”本质带来欠拟合风险。

后剪枝

先从训练集生产一颗完整的决策树，自底向上地对非叶子结点进行考察，若该结点对应的子树替换为叶子结点能够带来决策树泛化能力的提升，则将该子树替换为叶结点。

优缺点：欠拟合风险小，泛化能力优于预剪枝。但训练时间比未剪枝和预剪枝的时间开销大得多。

CATA树的剪枝

第一步：从生成的决策树

T_0

底部进行剪枝，直到根节点，形成一个子树序列

{T_0,T_1,...,T_n}

。

第二步：利用交叉验证在验证集上对子树序列进行测试，选择最优子树。

决策树处理缺失值

如何在属性值缺失的情况下进行划分属性选择？

基本思想是计算没有出现属性缺失的样本子集的信息增益，然后根据这部分样本在总体样本中的比例打个折，作为总体样本在该属性的信息增益。具体如下：

假设训练集为

，对于某个属

，如果

存在缺失值，令

tilde D

为属性

上没有缺失值的样本子集。初始时，赋给每个样本

以权重

w_x

，值为1。假设

有

个取

{a^1,a^2,...,a^v}

，令

tilde{D}^v

表示

tilde{D}

中在属性

上取值为

a^v

的样本子集。

令

rho=frac{sum_{xin{tilde D}}w_x}{sum_{xin{D}}w_x}

，表示没有缺失值的样本中第

类所占的比例。

令

tilde r_v=frac{sum_{xin{tilde D}^v}w_x}{sum_{xin{tilde D}}w_x}

，用来评估取值为

a^v

的子集在

tilde{D}^v

中的概率。

tilde r_v

表示无缺失值样本中属性

上取值

a^v

的样本所占的比例。

信息增益可用下式表达：

begin{aligned} Gain(D,a)&=rho times Gain(tilde{D},a) \ &=rho times left( Ent(tilde{D},a)-sum^V_{v=1}tilde r_vEnt(tilde{D}^v) right) end{aligned}

其中， Ent(tilde{D})=-sum^{|Y|}_{k=1}tilde{p}_klog_2tilde{p}_k

给定一个属性，若样本在该属性上的值缺失，如何划分该样本？

对于一个样本

，如果它在属性

上的取值已知，则将

划入到与其值对应的子节点，且样本的权值保持为

w_x

。

如果它在

上的属性未知（缺失值），那么将

同时将其划归到所有的子节点，且将其在属性值

a^v

对应的子节点上的权重更新为

tilde r_v cdot w_x

，其实质就是将一个样本以不同的概率划入到不同的子节点。

决策树可视化

代码语言：javascript复制

>>> from sklearn.datasets import load_iris
>>> from sklearn import tree
>>> from sklearn.tree import DecisionTreeClassifier
>>> iris = load_iris()
>>> clf = tree.DecisionTreeClassifier()
>>> clf = clf.fit(iris.data, iris.target)
>>> #  pip install python-graphviz
>>> import graphviz
>>> dot_data = tree.export_graphviz(clf, out_file=None,
...                      feature_names=iris.feature_names,  
...                      class_names=iris.target_names,  
...                      filled=True, rounded=True,  
...                      special_characters=True)  
>>> graph = graphviz.Source(dot_data)  
>>> graph

以上方法在jupyter notebook中显示，往往不能完全显示，需要截图或保存为完整树时显得力不从心，下面介绍一种保存成完整决策树的方法：

代码语言：javascript复制

>>> with open("iris.dot", 'w') as f:
... f = tree.export_graphviz(clf, out_file=f,
...                       feature_names=iris.feature_names,  
...                       class_names=iris.target_names,  
...                       filled=True, rounded=True,  
...                       special_characters=True)
>>> cd # 到存储"iris.dot"的目录下
>>> dot -Tpdf iris.dot -o output.pdf # 转化为pdf格式

更加简洁的方法

代码语言：javascript复制

>>> dot_data = tree.export_graphviz(clf, out_file=None)
>>> graph = graphviz.Source(dot_data)
>>> graph.render("iris") #保存为pdf格式

输出结果

本文主要参考李航老师的《统计学习方法》。有兴趣的读者可联系笔者，或后台回复"统计学习方法"获取下载链接，免费获得电子书。

决策树机器学习神经网络深度学习人工智能

0 人点赞

机器学习 | 决策树模型（一）理论

决策树的学习

特征选择

不纯度

信息增益

熵

条件熵

信息增益的算法

基尼指数

决策树的生成

ID3算法

ID3决策树生长

ID3决策树是以信息增益作为树生长的条件。下面以一个简单的例子来体会ID3算法的精髓。

ID3算法的局限性

C4.5算法

1、修改局部最优条件

2、连续变量处理手段

CART算法

CATA回归树的生成

CATA分类树的生成

决策树的剪枝

剪枝策略

预剪枝

后剪枝

CATA树的剪枝

决策树处理缺失值

如何在属性值缺失的情况下进行划分属性选择？

给定一个属性，若样本在该属性上的值缺失，如何划分该样本？

决策树可视化

输出结果

`ID3`决策树是以`信息增益`作为树生长的条件。下面以一个简单的例子来体会ID3算法的精髓。