【数据挖掘】十大算法之ID3决策树生成算法和CART分类回归树算法

1 基本概念 1.1 CART 基本概念

CART (classification and regression tree,CART)分类回归树算法，是应用广泛的决策树学习方法，CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。

CART算法分为两步：

（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大。（注意：ID3算法是最简单的生成树算法，C4.5算法是在ID3基础上改进的算法，CART是以损失函数作为评价指标，又引入了剪枝过程的生成树算法）

（2）决策树剪枝：用验证数据集对已经生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

1.2 熵

熵(entropy)是表示随机变量不确定性的度量，设X是一个取有限个值的离散随机变量，其概率分布为 P ( X = x i ) = o i , i = 1 , 2 , . . , n P(X = x_i)=o_i,i=1,2,..,n P(X=xi​)=oi​,i=1,2,..,n 则随机变量X的熵定义为 H ( X ) = − ∑ i = 1 n p i l o g p i H(X) = -\sum_{i=1}^np_ilogp_i H(X)=−i=1∑n​pi​logpi​ 也可将X的熵记为 H ( p ) = − ∑ i = 1 n p i l o g p i H(p) = -\sum_{i=1}^np_ilogp_i H(p)=−i=1∑n​pi​logpi​ 熵越大，随机变量的不确定性就越大。

1.3 条件熵

设随机变量(X,Y)，其联合概率分布为 P ( X = x i , Y = y j ) = p i j , i = 1 , 2 , . . , n ; j = 1 , 2 , . . , m P(X= x_i,Y=y_j) = p_{ij},i=1,2,..,n;j=1,2,..,m P(X=xi​,Y=yj​)=pij​,i=1,2,..,n;j=1,2,..,m

条件熵 H ( Y ∣ X ) H(Y|X) H(Y∣X)表示已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵 H ( Y ∣ X ) H(Y|X) H(Y∣X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望 H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) H(Y|X) = \sum_{i=1}^np_iH(Y|X = x_i) H(Y∣X)=i=1∑n​pi​H(Y∣X=xi​) 其中 p i = P ( X = x i ) , i = 1 , 2 , . . , n p_i = P(X =x_i),i=1,2,..,n pi​=P(X=xi​),i=1,2,..,n

1.4 信息增益

当熵和条件熵中个概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别为经验熵和经验条件熵。此时如果有0概率，令0log0 =0。信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

（1）定义

定义是特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵D(D|A)之差。 g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A) = H(D) -H(D|A) g(D,A)=H(D)−H(D∣A) 一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息。信息增益大的特征具有更强的分类能力。

（2）算法

设训练数据集为D，|D|表示样本容量，即样本个数。设有K个类别 C k ， k = 1 , 2 , . . . , K C_k，k=1,2,...,K Ck​，k=1,2,...,K， ∣ C k ∣ |C_k| ∣Ck​∣为属于类 C k C_k Ck​的样本个数， ∑ k = 1 K ∣ C k ∣ = ∣ D ∣ \sum_{k=1}^K|C_k| =|D| ∑k=1K​∣Ck​∣=∣D∣。设特征A有n个不同的取值 { a 1 , a 2 , . . . , a n } \{a_1,a_2,...,a_n\} {a1​,a2​,...,an​}，根据特征A的取值将D划分为n个子集 D 1 , D 2 , . . . , D n D_1,D_2,...,D_n D1​,D2​,...,Dn​。 ∣ D i ∣ |D_i| ∣Di​∣为 D i D_i Di​的样本个数， ∑ i = 1 n ∣ D i ∣ = ∣ D ∣ \sum_{i=1}^n|D_i| = |D| ∑i=1n​∣Di​∣=∣D∣。记子集 D i D_i Di​中属于类别 C k C_k Ck​的样本集合为 D i k D_{ik} Dik​，即 D i k = D i ⋂ C k D_{ik} = D_i \bigcap C_k Dik​=Di​⋂Ck​， ∣ D i k ∣ |D_{ik}| ∣Dik​∣为 D i k D_{ik} Dik​的样本个数。

第一步：是计算数据集D的经验熵H(D) H ( D ) = − ∑ k = 1 K ∣ C k ∣ ∣ D ∣ l o g 2 ∣ C k ∣ ∣ D ∣ H(D) = -\sum_{k=1}^K\frac{|C_k|}{|D|}log_2 \frac{|C_k|}{|D|} H(D)=−k=1∑K​∣D∣∣Ck​∣​log2​∣D∣∣Ck​∣​ 第二步 ：计算特征A对数据集D的经验条件熵H(D|A) H ( D ∣ A ) = ∑ i = 1 n ∣ D i ∣ ∣ D ∣ H ( D i ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ ∑ k = 1 K ∣ D i k ∣ ∣ D i ∣ l o g 2 ∣ D i k ∣ ∣ D i ∣ 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_2\frac{|D_{ik}|}{|D_i|} H(D∣A)=i=1∑n​∣D∣∣Di​∣​H(Di​)=−i=1∑n​∣D∣∣Di​∣​k=1∑K​∣Di​∣∣Dik​∣​log2​∣Di​∣∣Dik​∣​ 第三步：计算信息增益 g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A) = H(D)-H(D|A) g(D,A)=H(D)−H(D∣A)

1.3 信息增益比

（1）简介

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的的问题。

使用信息增益比可以对这一问题进行校正。这是特征选择的另一准则。

（2）定义

特征A训练数据集D的信息增益比 g R ( D , A ) g_R(D,A) gR​(D,A)定义为其信息增益 g ( D , A ) g(D,A) g(D,A)与训练数据集D关于特征A的值的熵 H A ( D ) H_A(D) HA​(D)之比，及 g R ( D , A ) = g ( D , A ) H A ( D ) g_R(D,A) = \frac{g(D,A)}{H_A(D)} gR​(D,A)=HA​(D)g(D,A)​ 其中， H A ( D ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ l o g 2 ∣ D i ∣ ∣ D ∣ H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}log_2 \frac{|D_i|}{|D|} HA​(D)=−∑i=1n​∣D∣∣Di​∣​log2​∣D∣∣Di​∣​，n是特征A取值的个数。

2 ID3算法

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

ID3相当于用极大似然法进行概率模型的选择。

3 C4.5算法

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

4 CART 算法

CART算法可以用于建立回归树和分类树。对于回归树的建立，采用平方根误差最小化准则进行特征选择，分类树采用基尼指数最小化准则进行特征选择。

4.1 CART 生成 4.1.1 回归树的生成（最小二乘回归树生成算法）

输入：训练数据集D

输出：回归树f(x)

在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域的输出值，构建二叉决策树。

假设X与Y的分别为输入和输出变量，并且Y是连续变量，给定训练书籍及 D = { ( x 1 , y 1 ) , ( x 1 , y 1 ) , . . . , ( x N , y N ) , } D = \{(x_1,y_1),(x_1,y_1),...,(x_N,y_N),\} D={(x1​,y1​),(x1​,y1​),...,(xN​,yN​),}

（1）选择最优切分变量j与切分点s，求解 m i n j , s [ m i n c 1 ∑ x i ∈ R 1 ( j , x ) ( y i − c 1 ) 2 + m i n c 2 ∑ x i ∈ R 2 ( j , x ) ( y i − c 2 ) 2 ] min_{j,s}[min_{c_1}\sum_{x_i \in R_1(j,x)}(y_i-c_1)^2 +min_{c_2}\sum_{x_i \in R_2(j,x)}(y_i-c_2)^2] minj,s​[minc1​​xi​∈R1​(j,x)∑​(yi​−c1​)2+minc2​​xi​∈R2​(j,x)∑​(yi​−c2​)2] 遍历变量j，对固定的切分变量j扫描切分点s，使得以上式子达到最小值。输出此时的(j,s)。

对空间划分，采用的是启发式的方法，选择第j个变量 x ( j ) x^{(j)} x(j)和它取的值s。作为切分变量和切分点。

（2）用选择得到的(j,s)划分区域并决定相应的输出值： R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } R 2 ( j , s ) = { x ∣ x ( j ) > s } c m ^ = 1 N m ∑ x i ∈ R m ( j , s ) y i , x ∈ R m , m = 1 , 2 R_1(j,s)= \{ x|x^{(j)} \leq s\} \\ R_2(j,s)= \{ x|x^{(j)} > s\} \\ \hat{c_m} = \frac{1}{N_m}\sum_{x_i \in R_m(j,s)}y_i,x \in R_m , m = 1,2 R1​(j,s)={x∣x(j)≤s}R2​(j,s)={x∣x(j)>s}cm​^​=Nm​1​xi​∈Rm​(j,s)∑​yi​,x∈Rm​,m=1,2

（3）继续对两个子区域调用步骤（1）（2），直到满足停止条件。

（4）将输入空间划分为M个区域 R 1 , R 2 , . . . , R M R_1,R_2,...,R_M R1​,R2​,...,RM​，生成决策树。 f ( x ) = ∑ m = 1 M c m ^ I ( x ∈ R m ) f(x) = \sum_{m=1}^M \hat{c_m}I(x \in R_m) f(x)=m=1∑M​cm​^​I(x∈Rm​)

4.1.2 分类树的生成

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

（1）基尼指数

分类问题中，假设有K个类，样本带你属于第k类的概率为 p k p_k pk​，则概率分布的基尼指数定义为 G i n i ( p ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 k p k 2 Gini(p) = \sum_{k=1}^Kp_k(1-p_k) = 1-\sum_{k=1}^kp^2_k Gini(p)=k=1∑K​pk​(1−pk​)=1−k=1∑k​pk2​ 对于二分类问题，若样本点属于第1个类的概率是p，则概率分布的基尼指数为 G i n i ( p ) = 2 p ( 1 − p ) Gini(p) = 2p(1-p) Gini(p)=2p(1−p) 对于给定的样本集合D，则基尼指数为 G i n i ( D ) = 1 − ∑ k = 1 K ( ∣ C k ∣ ∣ D ∣ ) 2 Gini(D)=1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2 Gini(D)=1−k=1∑K​(∣D∣∣Ck​∣​)2

这里 C k C_k Ck​是属于第k个类的样本子集，K是类的个数。

如果样本集合D根据特征A是否取某一个可能只a被分割为 D 1 D_1 D1​和$D_2两部分。则在特征A的条件下，集合D的基尼指数定义为 G i n i ( D , A ) = ∣ D 1 ∣ ∣ D ∣ G i n i ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ G i n i ( D 2 ) Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2) Gini(D,A)=∣D∣∣D1​∣​Gini(D1​)+∣D∣∣D2​∣​Gini(D2​)

基尼指数Gini(D)表示集合D的不确定性，基尼指数Gini(D,A)表示A= a分割后集合D的不确定性。基尼指数值越大，样本集合的不确定性也就越大，这一点与熵类似。

（2）算法过程

第一步：设结点的训练数据集为D，计算现有特征对数据集的基尼指数。此时，在样本集中，对每一个特征A，计算A是否等于a，划分为 D 1 D_1 D1​和 D 2 D_2 D2​两个部分。计算A=a时的基尼指数。

第二步：选择基尼字数最小的特征及其对应的切分点作为最优特征与最优切分点。

第三步：递归子节点调用第一步和第二步，直到满足停止条件。停止条件有三种类别

• 结点中的样本个数小于预定阈值
• 样本集的基尼指数小于预定阈值
• 没有更多特征

第四步：生成CART决策树。

4.2 CART剪枝 4.2.1 简介

CART剪枝算法是从完全生长的决策树的低端剪去一些子树，使得决策树变小（模型变得简单），从而能够对未知数据有更准确的预测。采用递归的方法。

CART剪枝算法分为两步：

第一步：从生成算法产生的决策树 T 0 T_0 T0​低端不断开始剪枝，知道 T 0 T_0 T0​的根结点，形成一个子树序列 { T 0 , T 1 , . . . , T n } \{T_0,T_1,...,T_n\} {T0​,T1​,...,Tn​}

第二步：通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。

在剪枝过程中，计算子树的损失函数表示为 C α ( T ) = C ( T ) + α ∣ T ∣ C_{\alpha}(T) = C(T)+ \alpha|T| Cα​(T)=C(T)+α∣T∣ 其中，T为任意子树。C(T)为对训练数据的预测误差（如基尼指数），|T|为子树的叶节点个数。 α ≥ 0 \alpha \geq 0 α≥0 为参数， C α ( T ) C_{\alpha}(T) Cα​(T)为参数 a l p h a alpha alpha时的子树T的整体损失。参数 α \alpha α权衡训练数据的拟合程度与模型的复杂度。

4.2.2 算法过程

输入：CART算法生成的决策树 T 0 T_0 T0​

输出：最优决策树 T α T_\alpha Tα​

（1）设k=0, T = T 0 T = T_0 T=T0​

（2）设 α = + ∞ \alpha = +\infty α=+∞

（3）自上而下对各内部节点t计算 C ( T t ) C(T_t) C(Tt​)， ∣ T t ∣ |T_t| ∣Tt​∣以及 g ( t ) = C ( t ) − C ( T t ) ∣ T t ∣ − 1 α = m i n ( α , g ( t ) ) g(t) = \frac{C(t)-C(T_t)}{|T_t|-1}\\ \alpha = min(\alpha,g(t)) g(t)=∣Tt​∣−1C(t)−C(Tt​)​α=min(α,g(t))

式中， T t T_t Tt​表示以t为根结点的子树， C ( T t ) C(T_t) C(Tt​)是对训练数据的预测误差， ∣ T t ∣ |T_t| ∣Tt​∣是 T t T_t Tt​的叶结点个数

（4）对 g ( t ) = α g(t) = \alpha g(t)=α的内部结点t进行剪枝，并对叶结点t以多数表决法决定其类，得到树T。

（5）设k = k+1， α k = α , T k = T \alpha_k = \alpha,T_k =T αk​=α,Tk​=T

（6）如果 T k T_k Tk​不是由根结点以及两个叶结点构成的树，则会到步骤（2）；否则令 T k = T n T_k = T_n Tk​=Tn​

（7）采用交叉验证法在子树序列 T 0 , T 1 , . . . , T n T_0,T_1,...,T_n T0​,T1​,...,Tn​中选取最优子树 T α T_{\alpha} Tα​。测试各棵子树的平方误差或基尼指数，误差最小或基尼指数最小被认为最优的决策树。