《统计学习方法》：第五章：决策树

该章结构

一、决策树模型与学习：
二、特征选择：
- 1、信息增益：
- 2、信息增益比：
三、决策树的生成：
- 1、
  
  ID3
  
  算法：
- 2、
  
  C4.5
  
  算法：
四、决策树的剪枝：
五、

CART

算法：
- 1、
  
  CART
  
  生成：
- 2、
  
  CART
  
  剪枝：

一、决策树模型与学习：

1、决策树模型：

决策树

：决策树由

节点

和

有向边

组成，节点有两种类型：一种是

内部节点

，其表示一个特征或属性，一种是

叶节点

表示一个类别。

2、决策树与条件概率分布：

决策树可以表示为

：给定特征条件下

类的条件概率分布

；这一条件概率分布定义在特征空间的一个划分上；这个划分将特征空间划分为互不相交的单元，并且在每个单元上定义一个

类的概率分布

；

这个类的概率分布其实质就是在这个单元中的样本属于某一类的概率，可以理解为一个长度为类个数的列表，列表中的元素就是该单元中的样本属于某一类的概率，这个概率一般是通过统计训练样本得到；

每个单元的

类的概率分布

就构成了决策树所表示的

条件概率分布
决策树中的每条

路径

对应于划分中的一个

单元

。即决策树的每个

叶节点

对应于一个

单元

。
假设
各叶结点(单元)往往偏向某一个类，即属于概率较大的某一类。决策树分类时将该叶结点(单元)的实例强行分到条件概率大的那一类中去。
上面的描述可能有点抽象小面用一个列子来解释一下：

图1是一个划分，图2是一个概率分布，图3是决策树，他们的对应关系我用红色数字标出来了；从图2我们可以看出：单元1全是+1的样本，单元2全是-1的样本，单元3全是-1的样本数多于+1的样本数，单元4全是+1的样本数多于-1的样本数。

3、决策树的学习：

假设训练集为：
$D=\{(x_1,y_1 ),(x_2,y_2 ),…,(x_N,y_N )\} D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x N , y N ) } 其中 x i = ( x i 1 , x i 2 , … , x i n ) , y = { 1 , 2 , … , K } x_i=(x_i^1,x_i^2,…,x_i^n ),y=\{1,2,…,K\} x i = ( x i 1 , x i 2 , … , x i n ) , y = { 1 , 2 , … , K }$
决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练集不相矛盾的决策树可能有多个，我们需要的是一个于训练集

矛盾较小

同时又

有很好的泛化能力

的决策树。
总统思路：
- 决策树学习的算法通常是一个
  
  递归地选择最优特征的过程
  
  ，并根据该最优特征对训练数据进行分割，使得分割得到的子集数据集有一个最好的分类。这一过程对应着对特征空间的划分，也对应着决策树的构建。
过程：
- 开始，构建根结点，将所有训练数据都放在
  
  根结点
  
  。选择一个
  
  最优特征
  
  ，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。
- 然后递归向下处理子集：
  - 如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去；
  - 如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。
- 最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树
剪枝：
- 以上方法生成的决策树可能会发生
  
  过拟合
  
  的现象。
- 这时我们需要对已生成的树自下而上进行
  
  剪枝
  
  ，将树变得更简单，从而使它具有更好的泛化能力。
- 具体说就是：去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。
决策树学习算法主要包含：

特征选择

、

决策树的生成

与

决策树的剪枝

。
决策树学习常用的算法有：ID3、C45与CART

二、特征选择：

在上面决策树的学习过程中需要

选择一个最优的特征

；那么什么是最优特征？怎样选择最优特征？
最优特征

指的是对训练数据

具有分类能力的特征

。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。
通常

选择最优特征的准则

是

信息增益

或

信息增益比

1、信息增益：

熵(entropy)：
- 在信息论与概率统计中，
  
  熵
  
  是表示随机变量
  
  不确定性的度量
  
  .
- 设
  $P(X=x_i )=p_i; i=1，2，，n P ( X = x i ) = p i ; i = 1 ， 2 ，， n 则随机变量 X X X 的熵定义为: H ( X ) = − ∑ i n p i l o g ⁡ p i H(X)=-∑_i^np_i log⁡p_i H ( X ) = − i ∑ n p i l o g ⁡ p i 其中规定 0 l o g 0 = 0 0log0=0 0 l o g 0 = 0 ， l o g log l o g 的底可以是 2 2 2 或 e e e 对应的熵的单位是比特(bit) 或纳特(nat)$
- 熵越大随机变量的不确定性就越大。
- 当随机变量只取两个值：1，0时，即
  $H(p)=-plog_2 p-(1-p) log_2⁡(1-p) H ( p ) = − p l o g 2 p − ( 1 − p ) l o g 2 ⁡ ( 1 − p ) 变化图如下：$
- 当
条件熵(conditional entropy)：
- 设有随机变量
  $P(X=x_i,Y=y_j )=P_{ij}，i=1,2,…,n；j=1,2,…,m P ( X = x i , Y = y j ) = P i j ， i = 1 , 2 , … , n ； j = 1 , 2 , … , m$
- 条件熵
  $H(Y│X)=∑_{i=1}^np_i H(Y│X=x_i ) H ( Y │ X ) = i = 1 ∑ n p i H ( Y │ X = x i ) 这里: p i = P ( X = x i ) ， i = 1 , 2 , … , n p_i=P(X=x_i )，i=1,2,…,n p i = P ( X = x i ) ， i = 1 , 2 , … , n .$
当熵和条件熵公式中的

概率由数据估计(特别是极大似然估计)得到时

，所对应的熵与条件熵分别称为

经验熵和经验条件熵
信息增益(information gain)：
- 信息增益
  
  ：表示得知特征
- 特征
- 熵
信息增益算法：
- 设训练数据集为
  $C_k，k=1,2,…,K C k ， k = 1 , 2 , … , K ； ∣ C k ∣ |C_k| ∣ C k ∣ 表示属于 C k C_k C k 的样本个数.设特征 A A A 有 n n n 个不同的取值 a 1 , a 2 , … , a n {a_1,a_2,…,a_n} a 1 , a 2 , … , a n ，根据特征 A A A 的取值将 D D D 划分为 n n n 个子集 D 1 , D 2 , … , D n D_1,D_2,…,D_n D 1 , D 2 , … , D n 。记子集 D i D_i D i ，中属于类 C k C_k C k ，的样本的集合为 D i k D_{ik} D i k $
- 输入：训练数据集
- 输出：特征
- 第一步：计算数据集
  $H(D)=-∑_{k=1}^K\frac{|C_k |}{|D|} log_2⁡\frac{|C_k |}{|D|} H ( D ) = − k = 1 ∑ K ∣ D ∣ ∣ C k ∣ l o g 2 ⁡ ∣ D ∣ ∣ C k ∣ $
- 第二步：计算特征
  $H(D|A)=∑_{i=1}^n\frac{|D_i |}{|D|} H(D_i)=-∑_{i=1}^n\frac{|D_i |}{|D|} ∑_{k=1}^K\frac{|C_{ik} |}{|D_i |} log_2\frac{⁡|C_{ik} |}{|D_i |} H ( D ∣ A ) = i = 1 ∑ n ∣ D ∣ ∣ D i ∣ H ( D i ) = − i = 1 ∑ n ∣ D ∣ ∣ D i ∣ k = 1 ∑ K ∣ D i ∣ ∣ C i k ∣ l o g 2 ∣ D i ∣ ⁡ ∣ C i k ∣ $
- 第三步：计算信息增益：

2、信息增益比：

信息增益值的大小是相对于训练数据集而言的，并没有绝对意义.在分类问题困难时，也就是说在训练数据集的

经验熵大

的时候，

信息增益值

会偏大.反之，信息增益值会偏小
使用

信息增益比

可以对上面这一问题进行修复.这是特征选择的另一准则.
信息增益比：
- 特征A对训练数据集
  $g_R (D,A) g R ( D , A ) 定义为:其信息增益 g ( D , A ) g(D,A) g ( D , A ) 与训练数据集 D D D 的经验熵 H ( D ) H(D) H ( D ) 之比： g R ( D , A ) = g ( D , A ) H ( D ) g_R (D,A)=\frac{g(D,A)}{H(D)} g R ( D , A ) = H ( D ) g ( D , A ) $

三、决策树的生成：

1、

ID3

算法：

ID3算法的核心是

：在决策树各个结点上

应用信息增益准则选择特征

，递归地构建决策树.
具体方法是

：
- 从根结点开始，每个结点计算所有可能的特征的信息增益，
  
  选择信息增益最大的特征作为当前结点的特征
  
  ，由该特征的不同取值对该节点的样本进行划分，并建立子结点；
- 再对子结点递归地调用以上方法，构建决策树；
- 直到所有特征的信息增益均很小或没有特征可以选择为止.
ID3算法：
- 输入：训练数据集
- 输出：决策树
- 第一步：若
  $C_k C k ，则 T T T 为单结点树，并将类 C k C_k C k 作为该结点的类标记，返回 T T T ；$
- 第二步：若
  $C_k C k ，作为该结点的类标记，返回 T T T ；$
- 第三部：计算
  $A_g A g $
- 第四部：如果
  $A_g A g 的信息增益小于阈值 ε ε ε ，则置 T T T 为单结点树，并将 D D D 中实例数最多的类 C k C_k C k ，作为该结点的类标记，返回 T T T ；$
- 第五部：如果
  $A_g A g 的信息增益大于阈值 ε ε ε ，对 A g A_g A g 的每一可能取值 a i a_i a i ，依 A g = a i A_g=a_i A g = a i 将 D D D 分割为若干非空子集 D i D_i D i ，将 D i D_i D i 中实例数最大的类作为标记，构建子结点，由该结点及其子结点构成树 T T T ，返回 T T T ；$
- 第六部：对第
  $D_i D i 为训练集，以 A − A g A-A_g A − A g 为特征集，递归地调用步(1)~步(5)，得到子树 T T T ，返回 T T T .$

2、

C4.5

算法：

C4.5算法对ID3算法进行了改进.C4.5在生成的过程中，

用信息增益比来选择特征

.
C4.5算法:
- 输入：训练数据集
- 输出：决策树
- 第一步：若
  $C_k C k ，则 T T T 为单结点树，并将类 C k C_k C k 作为该结点的类标记，返回 T T T ；$
- 第二步：若
  $C_k C k ，作为该结点的类标记，返回 T T T ；$
- 第三部：计算
  $A_g A g $
- 第四部：如果
  $A_g A g 的信息增益比小于阈值 ε ε ε ，则置 T T T 为单结点树，并将 D D D 中实例数最多的类 C k C_k C k ，作为该结点的类标记，返回 T T T ；$
- 第五部：如果
  $A_g A g 的信息增益比大于阈值 ε ε ε ，对 A g A_g A g 的每一可能取值 a i a_i a i ，依 A g = a i A_g=a_i A g = a i 将 D D D 分割为若干非空子集 D i D_i D i ，将 D i D_i D i 中实例数最大的类作为标记，构建子结点，由该结点及其子结点构成树 T T T ，返回 T T T ；$
- 第六部：对第
  $D_i D i 为训练集，以 A − A g A-A_g A − A g 为特征集，递归地调用步(1)~步(5)，得到子树 T T T ，返回 T T T .$

四、决策树的剪枝：

设树
$N_t N t 个样本点，其中 k k k 类的样本点有 N t k N_{tk} N t k 个， k = 1 , 2 , … , K k=1,2,…,K k = 1 , 2 , … , K ， H t ( T ) H_t (T) H t ( T ) 为叶结点 t t t 上的经验熵， α ≥ 0 α≥0 α ≥ 0 为参数，则决策树学习的损失函数可以定义为： C α ( T ) = ∑ t = 1 T N t H t ( T ) + α ∣ T ∣ C_α (T)=∑_{t=1}^TN_t H_t (T) +α|T| C α ( T ) = t = 1 ∑ T N t H t ( T ) + α ∣ T ∣ 其中经验熵为: H t ( T ) = − ∑ k K N t k N t l o g N t k N t H_t (T)=-∑_k^K\frac{N_{tk}}{N_t} log \frac{N_{tk}}{N_t} H t ( T ) = − k ∑ K N t N t k l o g N t N t k 在损失函数中，令： C ( T ) = ∑ t = 1 T N t H t ( T ) = − ∑ t = 1 T ∑ k K N t N t k N t l o g N t k N t = − ∑ t = 1 T ∑ k K N t k l o g N t k N t C(T)=∑_{t=1}^TN_t H_t (T) =-∑_{t=1}^T∑_k^KN_t \frac{N_{tk}}{N_t} log \frac{N_{tk}}{N_t} =-∑_{t=1}^T∑_k^KN_{tk} log \frac{N_{tk}}{N_t } C ( T ) = t = 1 ∑ T N t H t ( T ) = − t = 1 ∑ T k ∑ K N t N t N t k l o g N t N t k = − t = 1 ∑ T k ∑ K N t k l o g N t N t k 则有： C α ( T ) = C ( T ) + α ∣ T ∣ C_α (T)=C(T)+α|T| C α ( T ) = C ( T ) + α ∣ T ∣ C ( T ) C(T) C ( T ) 表示模型对训练数据的预测误差，即模型与训练数据的拟合程度， ∣ T ∣ |T| ∣ T ∣ 表示模型复杂度，参数 α ≥ 0 α≥0 α ≥ 0 控制两者之间的影响.较大的 α α α 促使选择较简单的模型，较小的 α α α 促使选择较复杂的模型(树). α = 0 α=0 α = 0 意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度.$
这样

剪枝

就是当
经过上面分析我们可以这样理解：
- 决策树生成阶段：使用生成算法生成决策树，这时使用的损失函数是
  
  C(T)
  
  $C (T)$
  
  ，这样生成一颗很大和复杂的决策
- 剪枝阶段：我们可以将这一阶段理解为，我们将上一阶段的生成的决策树进行随机的剪枝，生成很多上一阶段生成的决策树的子树。然后使用
  
  C_α (T)
  
  $C_{α} (T)$
  
  作为损失函数来选择一颗该损失函数最小的子树作为最后的决策树
C4.5算法:
- 输入：生成算法产生的整个树
- 输出：修剪后的子树
  $T_α T α ，.$
- 第一步：计算每个结点的经验熵.
- 第二步：递归地从树的叶结点向上回缩.
  - 当回溯到某个节点将其下面的子树剪掉，将没剪之前的树和剪了之后的树分别记为：
    $T_B T B 和 T A T_A T A 。如果 C α ( T A ) ≤ C α ( T B ) C_α (T_A )≤C_α (T_B ) C α ( T A ) ≤ C α ( T B ) ,就直接剪掉，反之将还原到原来的树。$
- 第三步：重复第二步直到回溯到根节点，得到损失函数最小的子树
  $T_α T α .$

五、

CART

算法：

CART树又叫

分类与回归树

。
CART算法假设决策树是

二叉树

，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支.这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定

预测的概率分布

，也就是在

输入给定的条件下输出的条件概率分布

.
CART算法由以下两步组成

：
- 决策树生成
  
  ：基于训练数据集生成决策树，生成的决策树要尽量大；
- 决策树剪枝
  
  ：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准.

1、

CART

生成：

特征选择

：
- 对
  
  回归树
  
  用
  
  平方误差最小化准则
  
  ，对
  
  分类树
  
  用
  
  基尼指数最小化准则
  
  ，进行特征选择，生成二叉树.
回归树的生成

：
- 假设
  $D=\{(x_1,y_j ),(x_2，y_2 ),…,(x_N，y_N )\} D = { ( x 1 , y j ) , ( x 2 ， y 2 ) , … , ( x N ， y N ) } 其中 x i = ( x i 1 , x i 2 , … , x i n ) x_i=(x_i^1,x_i^2,…,x_i^n ) x i = ( x i 1 , x i 2 , … , x i n )$
- 一个回归树对应着输入空间(即特征空间)的一个划分以及在划分的单元上的输出值.假设将输入空间划分为
  $R_1,R_2,…,R_M R 1 , R 2 , … , R M ，并且在每个单元 R m R_m R m 上有一个固定的输出值 c m c_m c m ，于是回归树模型可表示为: f ( x ) = ∑ m = 1 M c m I ( x ∈ R m ) f(x)=∑_{m=1}^Mc_m I(x∈R_m) f ( x ) = m = 1 ∑ M c m I ( x ∈ R m )$
- 损失函数：均方误差
  $∑_{x∈R_m}(y_i-f(x_i ))^2 x ∈ R m ∑ ( y i − f ( x i ) ) 2$
- 输入空间划分方法：
  - 采用启发式的方法，选择第j个属性变量
    $x^{(j)} x ( j ) 和它取的值 s s s ，作为切分变量和切分点，将数据切分为两个区域： R 1 ( j , s ) = ( x │ x ( j ) ≤ s ) R_1 (j,s)=(x│x^{(j) }≤s) R 1 ( j , s ) = ( x │ x ( j ) ≤ s ) R 2 ( j , s ) = ( x ∣ x ( j ) > s ) R_2 (j,s)=(x|x^{(j)}>s) R 2 ( j , s ) = ( x ∣ x ( j ) > s )$
  - 然后寻找最优切分变量
    $\min_{j,s} [\min_{c_1 }⁡∑_{x∈R_1(j,s)}(y_i-c_1 )^2 +\min_{c_2 }⁡∑_{x∈R_2(j,s)}(y_i-c_2 )^2 ] j , s min [ c 1 min ⁡ x ∈ R 1 ( j , s ) ∑ ( y i − c 1 ) 2 + c 2 min ⁡ x ∈ R 2 ( j , s ) ∑ ( y i − c 2 ) 2 ]$
  - 若确切分变量
    $c_1 c 1 和 c 2 c_2 c 2 为： c 1 ^ = a v e ( y i ∣ x i ∈ R 1 ( j , s ) ) \hat{c_1 }=ave(y_i |x_i∈R_1 (j,s)) c 1 ^ = a v e ( y i ∣ x i ∈ R 1 ( j , s ) ) c 2 ^ = a v e ( y i ∣ x i ∈ R 2 ( j , s ) ) \hat{c_2 }=ave(y_i |x_i∈R_2 (j,s)) c 2 ^ = a v e ( y i ∣ x i ∈ R 2 ( j , s ) ) 遍历所有切分变量，找到最优的切分变量 j j j 和划分点 s s s .再将输入空间划分为两个区域。两个区域的输出为： c 1 ^ \hat{c_1 } c 1 ^ ， c 2 ^ \hat{c_2} c 2 ^ 。接着对每个区域重复上述划分过程，直到满足停止条件为止。$
  - 这样就生成一棵回归树;通常称为
    
    最小二乘回归树
- 最小二乘回归树生成算法:
  - 输入：训练数据集
  - 输出：回归树
  - 第一步：选择最优切分变量
    $\min_{j,s} [\min_{c_1 }⁡∑_{x∈R_1(j,s)}(y_i-c_1 )^2 +\min_{c_2 }⁡∑_{x∈R_2(j,s)}(y_i-c_2 )^2 ] j , s min [ c 1 min ⁡ x ∈ R 1 ( j , s ) ∑ ( y i − c 1 ) 2 + c 2 min ⁡ x ∈ R 2 ( j , s ) ∑ ( y i − c 2 ) 2 ] 遍历所有属性变量 j j j ，对固定的切分变量 j j j 扫描切分点 s s s ，选择使式上述达到最小值的对 ( j , s ) (j,s) ( j , s ) .$
  - 第二步：用选定的对
    $R_1 (j,s)=(x│x^{(j) }≤s) R 1 ( j , s ) = ( x │ x ( j ) ≤ s ) R 2 ( j , s ) = ( x ∣ x ( j ) > s ) R_2 (j,s)=(x|x^{(j)}>s) R 2 ( j , s ) = ( x ∣ x ( j ) > s ) 对应输出为： c 1 ^ = a v e ( y i ∣ x i ∈ R 1 ( j , s ) ) \hat{c_1 }=ave(y_i |x_i∈R_1 (j,s)) c 1 ^ = a v e ( y i ∣ x i ∈ R 1 ( j , s ) ) c 2 ^ = a v e ( y i ∣ x i ∈ R 2 ( j , s ) ) \hat{c_2 }=ave(y_i |x_i∈R_2 (j,s)) c 2 ^ = a v e ( y i ∣ x i ∈ R 2 ( j , s ) )$
  - 第三步：继续对两个子区域调用步骤一和二，直至满足停止条件.
  - 第四步：将输入空间划分为
    $R_1,R_2,…,R_M R 1 , R 2 , … , R M ，生成决策树： f ( x ) = ∑ m = 1 M c m I ( x ∈ R m ) f(x)=∑_{m=1}^Mc_m I(x∈R_m) f ( x ) = m = 1 ∑ M c m I ( x ∈ R m )$
分类树的生成：

：
- 分类树用
  
  基尼指数
  
  选择最优特征，同时决定该特征的
  
  最优二值切分点
  
  .
- 基尼指数：
  - 在分类问题中，假设有
    $p_k p k ，则概率分布的基尼指数定义为: G i n i ( P ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 Gini(P)=∑_{k=1}^Kp_k (1-p_k)=1-∑_{k=1}^Kp_k^2 G i n i ( P ) = k = 1 ∑ K p k ( 1 − p k ) = 1 − k = 1 ∑ K p k 2 $
  - 对于给定的样本集合
    $Gini(D)=1-∑_{k=1}^K(\frac{|C_k |}{|D|} )^2 G i n i ( D ) = 1 − k = 1 ∑ K ( ∣ D ∣ ∣ C k ∣ ) 2 这里， C k C_k C k 是 D D D 中属于第 k k k 类的样本子集， K K K 是类的个数.$
  - 如果样本集合
    $D_1 D 1 和 D 2 D_2 D 2 两部分，即: D 1 = { ( x , y ) ∈ D ∣ A ( x ) = a } D_1=\{(x,y)∈D|A(x)=a\} D 1 = { ( x , y ) ∈ D ∣ A ( x ) = a } D 2 = D − D 1 D_2=D-D_1 D 2 = D − D 1 则在特征 A A A 的条件下，集合 D D 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 ) G i n i ( D , A ) = ∣ D ∣ ∣ D 1 ∣ G i n i ( D 1 ) + ∣ D ∣ ∣ D 2 ∣ G i n i ( D 2 )$
  - 基尼指数
  - 基尼指数值越大，样本集合的不确定性也就越大，这一点与熵相似.
  - 下图是二类分类问题中基尼指数、熵(单位比特) 之半一
- CART生成算法：
  - 输入：训练数据集
  - 输出：CART决策树.
  - 停止计算的条件
    
    ：一般是节点的样本数小于某个阈值，或基尼指数小于某各阈值。
  - 第一步：假设当前结点的训练数据集为
    $Gini(D,A)=\frac{|D_1 |}{|D|} Gini(D_1 )+\frac{|D_2 |}{|D|} Gini(D_2 ) G i n i ( D , A ) = ∣ D ∣ ∣ D 1 ∣ G i n i ( D 1 ) + ∣ D ∣ ∣ D 2 ∣ G i n i ( D 2 )$
  - 第二步：在所有可能的特征
    $D_1={(x,y)∈D|A(x)=a} D 1 = ( x , y ) ∈ D ∣ A ( x ) = a D 2 = D − D 1 D_2=D-D_1 D 2 = D − D 1 $
  - 第三部：对两个子节点递归的调用第一步和第二步，直到满足停止条件。

2、

CART

剪枝：

CART剪枝算法由两步组成：
- 首先从生成算法产生的决策树
  $T_0 T 0 底端开始不断剪枝，直到 T 0 T_0 T 0 的根结点，形成一个子树序列 T 0 , T 1 , T 2 , … , T n {T_0,T_1,T_2,…,T_n} T 0 , T 1 , T 2 , … , T n ；$
- 然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树.
剪枝形成一个子树序列:：

：
- 在剪枝过程中，计算子树的损失函数：
  $C_α (T)=C(T)+α|T| C α ( T ) = C ( T ) + α ∣ T ∣ 其中， T T T 为任意子树， C ( T ) C(T) C ( T ) 为对训练数据的预测误差(如基尼指数)， ∣ T ∣ |T| ∣ T ∣ 为子树的叶结点个数， α ≥ 0 α≥0 α ≥ 0 为参数， C α ( T ) C_α (T) C α ( T ) 为参数是 α α α 时的子树 T T T 的整体损失.参数 α α α 权衡训练数据的拟合程度与模型的复杂度.$
- 对固定的α，一定存在使损失函数
  $C_α (T) C α ( T ) 最小的子树，将其表示为 T α T_α T α 。 T α T_α T α 在损失函数 C α ( T ) C_α (T) C α ( T ) 最小的意义下是最优的.容易验证这样的最优子树是唯一的.当 α α α 大的时候，最优子树 T α T_α T α 偏小；当 α α α 小的时候，最优子树 T α T_α T α 偏大。极端情况，当 α = 0 α=0 α = 0 时，整体树是最优的(整体树是指生成算法生成的决策树 T 0 T_0 T 0 ).当 α = ∞ α=∞ α = ∞ 时，根结点组成的单结点树是最优的.$
- 我们将
  $0<α_0<α_1<⋯<α_n<∞ 0 < α 0 < α 1 < ⋯ < α n < ∞ ,其中每个区间 [ α i , α i + 1 ) [α_i,α_{i+1}) [ α i , α i + 1 ) 中的 α α α 剪枝得到的子树是一样的，并产生一个最优子树序列 { T 0 , T 1 , T 2 , … , T n } \{T_0,T_1,T_2,…,T_n\} { T 0 , T 1 , T 2 , … , T n }$
- 具体做法：
  - 从整体树
    $T_0 T 0 开始剪枝。对 T 0 T_0 T 0 的任意内部结点 t t t ，以 t t t 为单结点树的损失函数是： C α ( t ) = C ( t ) + α C_α (t)=C(t)+α C α ( t ) = C ( t ) + α 以 t t t 为根结点的子树 T t T_t T t 的损失函数是： C α ( T t ) = C ( T t ) + α ∣ T t ∣ C_α (T_t )=C(T_t )+α|T_t | C α ( T t ) = C ( T t ) + α ∣ T t ∣ 当 α = 0 α=0 α = 0 及 α α α 充分小时，有不等式： C α ( t ) > C α ( T t ) C_α (t)>C_α (T_t ) C α ( t ) > C α ( T t ) 当 α α α 增大时，在某一 α ′ α' α ′ 有: C α ( t ) = C α ( T t ) C_α (t)=C_α (T_t ) C α ( t ) = C α ( T t ) 可以得到: α ′ = C α ( t ) − C α ( T t ) ∣ T t ∣ − 1 α'=\frac{C_α (t)-C_α (T_t )}{|T_t |-1} α ′ = ∣ T t ∣ − 1 C α ( t ) − C α ( T t ) 当 α α α 再增大时，有不等式： C α ( t ) < C α ( T t ) C_α (t)<C_α (T_t ) C α ( t ) < C α ( T t ) 这样可以得到：当 α ≥ α ′ α≥α' α ≥ α ′ 时， t t t 比 T t T_t T t 更可取，可以对 T t T_t T t 进行剪枝$
  - 然后，对
    $T_0 T 0 中每一内部结点 t t t ，计算： g ( t ) = C α ( t ) − C α ( T t ) ∣ T t ∣ − 1 g(t)=\frac{C_α (t)-C_α (T_t )}{|T_t |-1} g ( t ) = ∣ T t ∣ − 1 C α ( t ) − C α ( T t ) $
  - 在
    $T_0 T 0 中剪去 g ( t g(t g ( t )最小的 T t T_t T t ，将得到的子树作为 T 1 T_1 T 1 ，同时将最小的 g ( t ) g(t) g ( t ) 设为 α 1 α_1 α 1 , T 1 T_1 T 1 为区间 [ α 1 ， α 2 ) [α_1，α_2) [ α 1 ， α 2 ) 的最优子树.按照这个方法依次确定： α 2 , T 2 , … , α n , T n α_2, T_2,…, α_n, T_n α 2 , T 2 , … , α n , T n ;其中 T n T_n T n 是是只有根节点的决策树$
- 交叉验证选取最优子树
  T
  
  α
  
  T_α
  
  $T_{α}$
  
  .
  
  利用独立的验证数据集，测试子树序列
  $T_0,T_1,T_2,…,T_n T 0 , T 1 , T 2 , … , T n 中各棵子树的平方误差或基尼指数.平方误差或基尼指数最小的决策树被认为是最优的决策树.$
CART剪枝算法：

：
- 输入：CART算法生成的决策树
  $T_0 T 0 ；$
- 输出：最优决策树
  $T_α T α $
- 第一步：设
  $k=0，T=T_0 k = 0 ， T = T 0 。·$
- 第二步：设
- 第三步：自下而上地对各内部结点t计算
  $C(T_t )，|T_t | C ( T t ) ， ∣ T t ∣ 以及 g ( t ) = C α ( t ) − C α ( T t ) ∣ T t ∣ − 1 g(t)=\frac{C_α (t)-C_α (T_t )}{|T_t |-1} g ( t ) = ∣ T t ∣ − 1 C α ( t ) − C α ( T t ) α = m i n ( α , g ( t ) ) α=min(α,g(t)) α = m i n ( α , g ( t ) )$
- 第四步：自上而下地访问内部结点t，如果有
- 第五步：设
  $k=k+1，α_k=α，T_k=T k = k + 1 ， α k = α ， T k = T .$
- 第六步：如果T不是由根结点单独构成的树，则回到第四步.
- 第七步：采用交叉验证法在子树序列
  $T_0,T_1,T_2,…,T_n T 0 , T 1 , T 2 , … , T n 中选取最优子树 T α T_α T α .$

原文链接：https://blog.csdn.net/ACM_hades/article/details/90043691

该章结构

一、决策树模型与学习：

1、决策树模型：

2、决策树与条件概率分布：

3、决策树的学习：

二、特征选择：

1、信息增益：

2、信息增益比：

三、决策树的生成：

1、 ID3 算法：

2、 C4.5 算法：

四、决策树的剪枝：

五、 CART 算法：

1、 CART 生成：

2、 CART 剪枝：

你可能也喜欢

1、

ID3

算法：

2、

C4.5

算法：

五、

CART

算法：

1、

CART

生成：

2、

CART

剪枝：