ID3 C4.5 CART决策树原理及sklearn实现

* 问题描述 <https://blog.csdn.net/jingjishisi/article/details/79379847#问题描述>
* ID3 <https://blog.csdn.net/jingjishisi/article/details/79379847#id3>
* 信息增益 <https://blog.csdn.net/jingjishisi/article/details/79379847#信息增益>
* 决策树构建 <https://blog.csdn.net/jingjishisi/article/details/79379847#决策树构建>
* 剪枝 <https://blog.csdn.net/jingjishisi/article/details/79379847#剪枝>
* C4.5 <https://blog.csdn.net/jingjishisi/article/details/79379847#c45>
* 信息增益比 <https://blog.csdn.net/jingjishisi/article/details/79379847#信息增益比>
* 决策树构建 <https://blog.csdn.net/jingjishisi/article/details/79379847#决策树构建-1>
* 剪枝 <https://blog.csdn.net/jingjishisi/article/details/79379847#剪枝-1>
* CART <https://blog.csdn.net/jingjishisi/article/details/79379847#cart>
* 基尼指数 <https://blog.csdn.net/jingjishisi/article/details/79379847#基尼指数>
* 决策树构建 <https://blog.csdn.net/jingjishisi/article/details/79379847#决策树构建-2>
* 剪枝 <https://blog.csdn.net/jingjishisi/article/details/79379847#剪枝-2>
* sklearn之决策树算法的实现
<https://blog.csdn.net/jingjishisi/article/details/79379847#sklearn之决策树算法的实现>
* 参考文献 <https://blog.csdn.net/jingjishisi/article/details/79379847#参考文献>


问题描述

假设我们有一组训练数据D={(x1,y1),⋯,(xN,yN)}D={(x1,y1),⋯,(xN,yN)}，这组训练数据代表NN个样本，xi(i=1,⋯,N)
xi(i=1,⋯,N)是样本点ii的特征向量，yiyi是样本点ii的类别，样本共分为KK类的情况下，yiyi的取值来自于KK个类别值{C1,⋯,CK}{C1,⋯
,CK}，训练数据的特征集合为A=A1,⋯,AMA=A1,⋯,AM，样本在某个特征AmAm处可能取到的特征值有nn个，分别为{am1,⋯,amn}{a1m,⋯,
anm}。

决策树是一种由结点和有向边构成的树形结构，结点类型分为内部结点和叶结点，每个内部结点代表对象的一个特征，叶结点则代表对象的类别。下图是一个简单的决策树，它通过输入对象的特征自上而下进行判断，并输出对象的类别（通过对象是否常熬夜，是否常运动判断其分类是健康或亚健康）。在下图中，椭圆框代表内部结点，长方形框代表叶结点。


对于一个未知类别的输入对象，决策树自上而下的测试该对象在每个内部结点的特征取值，从而将其分配到相应的子结点或叶结点，当对象被分配到某个叶结点时，便可确定其类别。

ID3


ID3算法的基本流程为：如果某一个特征能比其他特征更好的将训练数据集进行区分，那么将这个特征放在初始结点，依此类推，初始特征确定之后，对于初始特征每个可能的取值建立一个子结点，选择每个子结点所对应的特征，若某个子结点包含的所有样本属于同一类或所有特征对其包含的训练数据的区分能力均小于给定阈值，则该子结点为一个叶结点，其类别与该叶结点的训练数据类别最多的一致。重复上述过程直到特征用完或者所有特征的区分能力均小于给定阈值。
如何衡量某个特征对训练数据集的区分能力呢，ID3算法通过信息增益来解决这个问题。

信息增益

一个离散型随机变量xx的概率分布为：P(x=xi)=pi,(i=1,⋯,n)P(x=xi)=pi,(i=1,⋯,n)，那么xx的熵定义如下：

H(x)=−∑i=1npilog2piH(x)=−∑i=1npilog2pi
熵的单位为比特(bit)，定义0log0=00log0=0。对于两个随机变量x,yx,y，他们有如下形式的联合概率分布：
P(x=xi,y=yj)=pij,(i=1,⋯,n;j=1,⋯,K)P(x=xi,y=yj)=pij,(i=1,⋯,n;j=1,⋯,K)
那么在xx确定的条件下yy的条件熵定义如下：
H(y|x)=∑i=1npiH(y|x=xi)H(y|x)=∑i=1npiH(y|x=xi)

数据集的熵表征着其类别的不确定程度，而数据集关于某个特征的条件熵则表征着给定某个特征后，其类别的不确定程度。可以想见，数据集的熵与其关于某个特征的条件熵之差表征着这个特征的确定使数据集不确定性减少的程度，数据集的熵与条件熵的差值叫做信息增益，很容易理解，某个特征的信息增益可以反映这个特征对数据集的分类能力，信息增益越大，证明该特征能更好的对数据集进行分类。


信息增益：数据集DD的熵为H(D)H(D)，其关于其某个特征AmAm的条件熵为H(D|Am)H(D|Am)，则信息增益为g(D,Am)g(D,Am)，g(D,
Am)=H(D)−H(D|Am)g(D,Am)=H(D)−H(D|Am)。

对于训练样本集来说，其概率是由数据估计得到的，因此其熵与条件熵分别称为经验熵和经验条件熵。经验熵和经验条件熵的计算方式如下：

H(D)=−∑k=1K|Ck||D|log2|Ck||D|g(D,Am)=H(D)−H(D|Am)=H(D)−∑i=1n|Di||D|H(Di)g(D,Am)
=−∑k=1K|Ck||D|log2|Ck||D|+∑i=1n|Di||D|∑k=1K|Dik||Di|log2|Dik||Di|H(D)=−∑k=1K|Ck|
|D|log2|Ck||D|g(D,Am)=H(D)−H(D|Am)=H(D)−∑i=1n|Di||D|H(Di)g(D,Am)=−∑k=1K|Ck||D|lo
g2|Ck||D|+∑i=1n|Di||D|∑k=1K|Dik||Di|log2|Dik||Di|
其中|D||D|表示数据集DD中的样本点个数，DiDi表示训练样本集中特征AA取值为aiai的样本点集合，DikDik表示训练样本集中特征AmAm取值为am
iaim且类别为CkCk的样本点集合。


决策树构建


ID3算法构建决策树的过程简单概括起来就是，自根结点开始，选择信息增益最大的特征作为根结点对应的特征，并依据该特征的可能取值将训练数据分配到不同的子结点，对子结点进行同样的操作，若子结点的所有样本属于同一类别或该子结点处所有特征的信息增益均小于给定阈值或无可供选择的特征，那么这个子结点是一个叶结点，将叶结点的样本数量最多的类别作为叶结点的类别。

* 输入：训练数据D={(x1,y1),⋯,(xN,yN)}D={(x1,y1),⋯,(xN,yN)}，特征集AA，信息增益阈值ϵϵ
* 输出：决策树TT
step1 若DD中样本特征为空，那么树TT为一棵单结点树，将样本数最大的类别作为树的类别，返回TT；否则，转到step2。
step2 计算训练集DD关于所有特征的信息增益，若信息增益均小于阈值ϵϵ，则TT是一棵单结点树，将样本数最大的类别作为树的类别，返回TT
；否则，转到step3。
step3 选择信息增益最大的特征AmaxAmax作为根结点特征，依据AmaxAmax
的所有可能值建立相应子结点，若子结点的样本全部属于同一类别，则子结点为叶结点，将叶结点类别标记为该结点所有样本所属的类别，若所有子结点均为叶结点，返回TT
；否则，返回TT并转到step4。
step4 对非叶子结点ii，以DiDi为训练数据集，A=A−{Amax}A=A−{Amax}为特征集，递归地调用step1-step3，返回子树TiTi。
剪枝


通过信息增益特征选择构造的决策树往往能够对训练数据进行很准确的分类，但是应用于测试数据的分类时，效果往往不够理想，造成这种情况的一个重要原因是对训练数据的过拟合，就是过分在意对训练数据分类的准确性，导致模型过于复杂，普适性低，将这样的模型用于测试数据的分类时，效果就大打折扣。解决这个问题的方法是简化模型，剪掉决策树的某些枝，使模型的普适性提高。剪枝的方式是剪掉某些子树或叶结点，并将其父结点做为新的叶结点。要剪掉哪些枝是通过损失函数来确定的，其定义如下。

损失函数
决策树TT的叶结点个数为|T||T|，t是它的一个叶结点，其包含的样本数为NtNt，其中类别为CkCk的样本数为NtkNtk，叶结点t的经验熵为Ht(T)=
−∑Kk=1NtkNtlog2NtkNtHt(T)=−∑k=1KNtkNtlog2NtkNt，损失函数定义为：

Cα(T)=∑t=1|T|NtHt(T)+α|T|α≥0Cα(T)=∑t=1|T|NtHt(T)+α|T|α≥0


将损失函数左端项记为C(T)C(T)，C(T)=∑|T|t=1NtHt(T)=−∑|T|t=1∑Kk=1Ntklog2NtkNtC(T)=∑t=1|T|NtH
t(T)=−∑t=1|T|∑k=1KNtklog2NtkNt，C(T)C(T)表示决策树对训练数据分类的误差，|T||T|表示模型的复杂度，αα
为平衡两者之间关系的参数，αα越大表示要求决策树越简单，αα越小表示要求决策树对训练数据的拟合程度越高。给定参数αα
后，利用损失函数最小化来对决策树进行剪枝，确定最终的决策树TαTα。

* 输入：决策树TT，参数αα
* 输出：剪枝后的决策树TαTα
step1 初始化TαTα，Tα=TTα=T，计算TαTα的损失函数Cα(Tα)Cα(Tα)。
step2 依次序选定TαTα的一个叶结点，将其缩回到父结点，叶结点缩回父结点后的决策树记为TβTβ，计算TβTβ的损失函数Cα(Tβ)Cα(Tβ)，若Cα(
Tβ)≤Cα(Tα)Cα(Tβ)≤Cα(Tα)，则令Tα=Tβ,Cα(Tα)=Cα(Tβ)Tα=Tβ,Cα(Tα)=Cα(Tβ)。
step3 若所有叶结点的损失函数都不再减小或决策树缩为一个根结点若干个叶结点的树，返回TαTα；否则，转到step2。

C4.5

C4.5算法的基本流程与ID3类似，但C4.5算法进行特征选择时不是通过计算信息增益完成的，而是通过信息增益比来进行特征选择。

信息增益比

信息增益比：训练数据DD关于特征AmAm的信息增益为g(D,Am)g(D,Am)，DD关于AmAm的熵为HAm(D)HAm(D)，HAm(D)=−∑ni=1|
Di||D|log2|Di||D|HAm(D)=−∑i=1n|Di||D|log2|Di||D|，则DD关于AmAm的信息增益比gr(D,Am)gr(D,Am)
为信息增益为g(D,Am)g(D,Am)与熵HAm(D)HAm(D)的比值：

gr(D,Am)=g(D,Am)HAm(D)gr(D,Am)=g(D,Am)HAm(D)


通过上面的定义，我们可以将信息增益比理解为信息增益的标准化，特征之间的信息增益比可比较性更强一些。同时我们要注意区分DD关于类别的熵H(D)H(D)，关于特征
AmAm的条件熵H(D|Am)H(D|Am)和关于特征AmAm的熵HAm(D)HAm(D)。

决策树构建

* 输入：训练数据D={(x1,y1),⋯,(xN,yN)}D={(x1,y1),⋯,(xN,yN)}，特征集AA，信息增益比阈值ϵϵ
* 输出：决策树TT
step1 若DD中样本特征为空，那么树TT为一棵单结点树，将样本数最大的类别作为树的类别，返回TT；否则，转到step2。
step2 计算训练集DD关于所有特征的信息增益比，若信息增益比均小于阈值ϵϵ，则TT是一棵单结点树，将样本数最大的类别作为树的类别，返回TT
；否则，转到step3。
step3 选择信息增益比最大的特征AmaxAmax作为根结点特征，依据AmaxAmax
的所有可能值建立相应子结点，若子结点的样本全部属于同一类别，则子结点为叶结点，将叶结点类别标记为该结点所有样本所属的类别，若所有子结点均为叶结点，返回TT
；否则，返回TT并转到step4。
step4 对非叶子结点ii，以DiDi为训练数据集，A=A−{Amax}A=A−{Amax}为特征集，递归地调用step1-step3，返回子树TiTi。
剪枝

通过信息增益比计算得到的决策树也需要进行剪枝，剪枝方法同ID3算法。

CART

CART算法构造的是二叉决策树，决策树构造出来后同样需要剪枝，才能更好的应用于未知数据的分类。CART算法在构造决策树时通过基尼系数来进行特征选择。

基尼指数

基尼指数：若某样本数据分为KK类，数据属于第k类的概率为pkpk，则样本数据的基尼指数定义为：

Gini(p)=∑k=1Kpk(1−pk)Gini(p)=∑k=1Kpk(1−pk)


对于训练样本集DD，其基尼指数如下：

Gini(D)=∑k=1K|Ck||D|(1−|Ck||D|)=1−∑k=1K(|Ck||D|)2Gini(D)=∑k=1K|Ck||D|(1−|Ck||D|
)=1−∑k=1K(|Ck||D|)2
如果样本集合DD根据特征AmAm的取值可以分为两部分D1D1和D2D2，那么在特征AmAm的条件下，DD的基尼指数如下：
Gini(D,Am)=|D1||D|Gini(D1)+|D2||D|Gini(D2)Gini(D,Am)=|D1||D|Gini(D1)+|D2||D|Gin
i(D2)
基尼指数Gini(D)Gini(D)表征着数据集DD的不确定性，而在特征AmAm的条件下，DD的基尼指数则表征着在特征AmAm确定的条件下DD
的不确定性，因此基尼指数之差和信息增益及信息增益比一样，可以表征特征AmAm对数据集DD的分类的能力。


决策树构建

下面给出CART算法。

* 输入： 训练数据集DD，特征集AA，结点样本数阈值δδ，基尼指数阈值ϵϵ
* 输出： CART二叉决策树TT
step1 若样本特征集为空，则TT是一棵单节点数，其类别为DD中样本数最多的类，返回TT；否则，转到step2。
step2 对数据集DD，计算特征集AA中所有特征所有可能切分点的基尼指数，若基尼指数的值均小于给定阈值ϵϵ，则TT是一棵单节点数，其类别为DD
中样本数最多的类，返回TT；否则，转到step3。
step3 选择基尼指数最小的特征AminAmin和相应切分点αα作为根节点的特征值和切分标准，根据DD中样本是否等于αα（或≤α≤α，或≥α≥α）将DD
分为两个子集D1D1和D2D2，将D1D1和D2D2分别分配到两个子结点中，若子结点样本数均小于给定阈值δδ
，则该子结点是一个叶结点，若两个子结点均为叶结点，返回T；否则，返回T并转到step4。
step4 对于非叶子结点，令DD等于该子结点所对应的数据集，特征集A=A−{Amin}A=A−{Amin}，递归的调用step1-step3，返回子树TT。
剪枝

CART算法生成的决策树同样需要剪枝，剪枝的方式是先进行剪枝形成一系列子树T0,T1,⋯,TLT0,T1,⋯,TL
，再用独立的验证数据集对这些子树进行验证，找到对于验证数据集基尼指数最小的树TαTα，将TαTα
作为最优决策树。在那些结点剪枝是通过损失函数计算的，损失函数形式如下：

Cα=C(T)+α|T|α≥0Cα=C(T)+α|T|α≥0
其中C(T)=∑|T|t=1NtGinit(T)=∑|T|t=1Nt(1−∑Kk=1(NtkNt)2)C(T)=∑t=1|T|NtGinit(T)=∑t=1
|T|Nt(1−∑k=1K(NtkNt)2)，它是决策树对训练数据的分类误差，|T||T|是决策树结点总数，αα是平衡两者的参数，αα
越大，优化后的决策树越简单（结点越少），αα越小，优化后的决策树对训练数据的分类误差越小。
对于整体二叉决策树TT的某个内部结点tt，以tt为单结点树的损失函数是Cα(t)=C(t)+αCα(t)=C(t)+α，以tt为根结点的子树TtTt
的损失函数是Cα(Tt)=C(Tt)+α|Tt|Cα(Tt)=C(Tt)+α|Tt|，当αα充分小时，有Cα(Tt)<Cα(t)Cα(Tt)<Cα(t)，当αα
增大到某个值时，有Cα(Tt)=Cα(t)Cα(Tt)=Cα(t)，当αα继续增大时，有Cα(Tt)>Cα(t)Cα(Tt)>Cα(t)。当Cα(Tt)=Cα(
t)Cα(Tt)=Cα(t)时，α=C(t)−C(Tt)|Tt|−1α=C(t)−C(Tt)|Tt|−1，此时，tt与TtTt有相同的损失函数，但tt
的结构更简单，因此剪掉子树TtTt，构建子树序列T0,T1,⋯,TLT0,T1,⋯,TL的方法就是基于这种思想的。
α0=0α0=0，对决策树T0T0，对于其所有内部结点tt，计算
g(t)=C(t)−C(Tt)|Tt|−1g(t)=C(t)−C(Tt)|Tt|−1
g(t)g(t)的最小值为α1α1，T0T0为区间[α0,α1)[α0,α1)上的最优子树，g(t)g(t)取最小值处的结点为t1t1，剪掉以t1t1
为根结点的子树Tt1Tt1即得到T1T1，T1T1为区间[α1,α2)[α1,α2)
上的最优子树。重复上述操作，直到得到的最优子树为一个根结点和两个叶结点构成的树，此时我们得到了一系列的αα值：0=α0<α1<⋯<αL0=α0<α1<⋯<αL
，和区间[α0,α1),[α1,α2),⋯,[αL,∞)[α0,α1),[α1,α2),⋯,[αL,∞)上的最优子树序列：T0,T1,⋯,TLT0,T1,⋯,T
L。
然后利用验证数据集对最优子树序列进行测试，选择对于验证数据集有最小基尼指数的最优子树作为最终的最优决策树。若最终TlTl为最优决策树，那么其所对应的αlαl
就是损失函数的参数αα。


* 输入： CART算法生成的决策树TT
* 输出： 最优决策树TαTα
step1 若TT为单结点树或由一个根结点和两个叶结点构成的树，返回TT；否则，k=0,α0=0,T0=Tk=0,α0=0,T0=T，转到step2。
step2 k=k+1k=k+1，计算Tk−1Tk−1所有内部结点tt的g(t)g(t)值，g(t)g(t)的最小值为αkαk，g(t)g(t)
取最小值处的结点为tktk，剪掉以tktk为根结点的子树TtkTtk，并以tktk处类别最多的样本作为新的叶结点tktk的类，得到[αk,αk+1)[αk,αk
+1)上的最优子树TkTk。
step3 若TkTk是由一个根结点和两个叶结点构成的树，转到step4；否则，转到step2。
step4 利用验证数据集对最优子树序列T0,T1,⋯,TLT0,T1,⋯,TL进行测试，选择对于验证数据集有最小基尼指数的最优子树作为最终的最优决策树TαT
α，返回TαTα。
sklearn之决策树算法的实现

用sklearn官方教程中的例子来说明如何用sklearn来构建决策树。
from sklearn import tree X = [[0, 0], [1, 1]] Y = [0, 1] clf =
tree.DecisionTreeClassifier() clf = clf.fit(X, Y)print (clf.predict([[2., 2.]]))
# [1]

DecisionTreeClassifier默认采用基尼指数作为特征选择标准。值得注意的是，DecisionTreeClassifier构建决策树没有剪枝的步骤，若决策树出现了过拟合现象，可以适当的减少训练数据，重新学习决策树。

参考文献

李航：《统计学习方法》
sklearn官方教程：http://scikit-learn.org/stable/ <http://scikit-learn.org/stable/>

• « 上一篇：Spring Cloud（Finchley.RELEASE版本）微服务学习实践：6.2全链路追踪监控-Zipkin
• » 下一篇：vue.js+mint-ui的Popup组件和Picker组件实现省市县三级联动功能