精华内容
下载资源
问答
  • 决策树(Decision Tree)是一种基本的分类与回归方法。本文会讨论决策树中的分类树与回归树,后续文章会继续讨论决策树的Boosting和Bagging的相关方法。决策树由结点和有向边组成。结点有两种类型:内部结点和叶结点...

    分类目录:《深入理解机器学习》总目录
    相关文章:
    基于决策树的模型(一)分类树和回归树
    基于树的模型(二):集成学习之Bagging和Random Forest
    基于树的模型(三):集成学习之GBDT和XGBoost
    基于树的模型(四):随机森林的延伸——深度森林(gcForest)
    基于树的模型(五):从零开始用Python实现ID3决策树
    基于树的模型(六):Python实现CART决策树并利用Tkinter构建GUI对决策树进行调优
    基于树的模型(七):RF/XGBoost等算法实践与决策树Scala实践等(材料准备中)


    决策树(Decision Tree)是一种基本的分类与回归方法,当决策树用于分类时称为分类树,用于回归时称为回归树。本文主要讨论决策树中的分类树与回归树的一些基本理论,后续文章会继续讨论决策树的BoostingBagging相关方法。

    决策树由结点和有向边组成。结点有两种类型:内部结点和叶结点,其中内部结点表示一个特征或属性,叶结点表示一个类。一般的,一棵决策树包含一个根结点、若干个内部结点和若干个叶结点。叶结点对应于决策结果,其他每个结点则对应于一个属性测试。每个结点包含的样本集合根据属性测试的结果被划分到子结点中,根结点包含样本全集,从根结点到每个叶结点的路径对应了一个判定测试序列。在下图中,圆和方框分别表示内部结点和叶结点。决策树学习的目的是为了产生一棵泛化能力强,即处理未见示例能力强的决策树。
    j决策树图示

    分类树

    分类树是一种描述对实例进行分类的树形结构。在使用分类树进行分类时,从根结点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子结点。这时,每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配,直至达到叶结点。最后将实例分到叶结点的类中。

    假设给定训练数据集:
    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)\} D={(x1,y1),(x2,y2),...,(xN,yN)}其中, x i = ( x i ( 1 ) , x i ( 2 ) , . . . , x i ( n ) ) T , x_i=(x_i^{(1)}, x_i^{(2)}, ..., x_i^{(n)})^T, xi=(xi(1),xi(2),...,xi(n))T,为输入实例,即特征向量, n n n为特征个数, i = 1 , 2 … , N i=1,2…,N i=12N N N N为样本容量, y i ∈ { 1 , 2 , . . . , K } y_i \in \{ 1, 2, ..., K\} yi{1,2,...,K}为类标。分类树学习的目标是根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类。

    决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个,也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树,同时具有很好的泛化能力。从另一个角度看,决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个,我们选择的条件概率模型应该不仅对训练数据有很好的拟合,而且对未知数据有很好的预测。

    决策树学习用损失函数表示这一目标,其损失函数通常是正则化的极大似然函数,决策树学习的策略是以损失函数为目标函数的最小化。当损失函数确定以后,学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题,所以现实中决策树学习算法通常采用启发式方法,近似求解这一最优化问题。这样得到的决策树是次最优的。

    决策树分类算法
    输入:
    \qquad 训练集: D = ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) D = {(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)} D=(x1,y1),(x2,y2),,(xN,yN)
    \qquad 属性集: A = a 1 , a 2 , ⋯   , a n A = {a_1, a_2, \cdots, a_n} A=a1,a2,,an
    过程:
    \qquad 函数 T r e e G e n e r a t e ( D , A ) TreeGenerate(D, A) TreeGenerate(D,A)
    输出:
    \qquad 以node为根节点的决策树
    算法:
    ( 1 ) 生成结点根node
    ( 2 ) if D D D中样本全属于同一类别 C k C_k Ck then
    ( 3 ) \quad 将node标记为 C k C_k Ck类叶结点
    ( 4 ) \quad return
    ( 5 ) end if
    ( 6 ) if A = ∅ A = \varnothing A= OR D D D中样本在 A A A上取值相同 then
    ( 7 ) \quad 将node标记为叶结点,其类别标记为 D D D中样本数最多的类
    ( 8 ) \quad return
    ( 9 )end if
    (10)从 A A A中选择最优划分属性 a ∗ a_* a
    (11)for a ∗ a_* a 的每一个值 a ∗ v a_*^v av do
    (12) \quad 为node生成一个分支:令 D v D_v Dv表示 D D D中在 a ∗ a_* a上取值为 a ∗ v a_*^v av的样本子集
    (13) \quad if D v D_v Dv为空 then
    (14) \qquad 将分支结点标记为叶结点,其类别标记为 D D D中样本最多的类
    (15) \qquad return
    (16) \quad else
    (17) \qquad T r e e G e n e r a t e ( D v , A − { a ∗ } ) TreeGenerate(D_v, A - \{a_*\}) TreeGenerate(Dv,A{a})为分支结点
    (18) \quad end if
    (19)end for

    决策树学习的算法通常是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分,也对应着决策树的构建。开始,构建根结点,将所有训练数据都放在根结点。选择一个最优特征,按照这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类,那么构建叶结点,并将这些子集分到所对应的叶结点中去,如果还有子集不能被基本正确分类,那么就对这些子集选择新的最优特征,继续对其进行分割,构建相应的结点。如此递归地进行下去,直至所有训练数据子集被基本正确分类,或者没有合适的特征为止。最后每个子集都被分到叶结点上,即都有了明确的类。这就生成了一棵决策树。

    从上述过程中就可以看出,决策树的生成是一个递归过程。在决策树基本算法中,有三种情形会导致递归返回

    1. 当前结点包含的样本全属于同一类别,无需划分
    2. 当前属性集为空,或是所有样本在所有属性上取值相同,无法划分
    3. 当前结点包含的样本集合为空,不能划分

    在第二种情形下,我们把当前结点标记为叶结点,并将其类别设定为该结点所含样本最多的类别。在第三种情形下,同样把当前结点标记为叶结点,但将其类别设定为其父结点所含样本最多的类别。这两种情形的处理实质不同:第二种情况是在利用当前结点的后验分布,而第三种情况则是把父结点的样本分布作为当前结点的先验分布

    以上方法生成的决策树可能对训练数据有很好的分类能力,但对未知的测试数据却未必有很好的分类能力,即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝,将树变得更简单,从而使它具有更好的泛化能力。具体地,就是去掉过于细分的叶结点,使其回退到父结点,甚至更高的结点,然后将父结点或更高的结点改为新的叶结点。如果特征数量很多,也可以在决策树学习开始的时候,对特征进行选择,只留下对训练数据有足够分类能力的特征。

    可以看出,决策树学习算法包含特征选择决策树的生成决策树的剪枝过程。由于决策树表示一个条件概率分布,所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择,决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优,相对地,决策树的剪枝则考虑全局最优。

    决策树模型呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。分类树具有良好的可读性与分类速度快的优点。分类树在学习时,利用训练数据,根据损失函数最小化的原则建立分类树模型,在预测时,对新的数据,利用分类树模型进行分类。决策树学习通常包括3个步骤:特征选择、决策树的生成和决策树的修剪。

    决策树与if-then规则

    可以将决策树看成一个if-then规则的集合:由决策树的根结点到叶结点的每一条路径构建一条规则,路径上内部结点的特征对应着规则的条件,而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质——互斥并且完备。这就是说,每一个实例都被一条路径或一条规则所覆盖,而且只被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

    决策树与条件概率分布

    决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域,并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设 X X X为表示特征的随机变量, Y Y Y为表示类的随机变量,那么这个条件概率分布可以表示为 P ( Y ∣ X ) P(Y|X) PYX X X X取值于给定划分下单元的集合, Y Y Y取值于类的集合。各叶结点(单元)上的条件概率往往偏向某一个类,即属于某一类的概率较大。决策树分类时将该结点的实例强行分到条件概率大的那一类去。

    决策树的优缺点
    • 计算复杂度不高
    • 对中间缺失值不敏感
    • 解释性强,在解释性方面甚至比线性回归更强
    • 与传统的回归和分类方法相比,决策树更接近人的决策模式
    • 可以用图形表示,非专业人士也可以轻松理解
    • 可以直接处理定性的预测变量而不需创建哑变量
    • 决策树的预测准确性一般比回归和分类方法弱,但可以通过用集成学习方法组合大量决策树,显著提升树的预测效果

    特征选择

    特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。比如,我们希望构建一棵决策树来根据不同人的各种属性来预测每个人性别,那么对于属性“头发的长度”可能就要比属性“头发的颜色”所能包含的信息更多。因为一般来说,男生的头发要比女生的头发短,所以我们希望“头发的长度”这个属性处于决策树的上部。随着划分过程不断进行,我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的“纯度”(purity)越来越高。

    信息增益

    为了便于说明信息增益,先给出熵与条件熵的定义。在信息论与概率统计中,熵(entropy)是表示随机变量不确定性的度量。设 X X X是一个取有限个值的离散随机变量,其概率分布为:
    P ( X = x i ) = p i , i = 1 , 2 , ⋯   , n P(X = x_i) = p_i, i = 1, 2, \cdots, n P(X=xi)=pi,i=1,2,,n
    则随机变量 X X X的熵定义为:
    H ( X ) = − ∑ i = 1 n p i log ⁡ p i H(X) = -\sum_{i = 1}^n p_i \log p_i H(X)=i=1npilogpi
    在上式中,若 p i = 0 p_i = 0 pi=0,则定义 p i log ⁡ p i = 0 p_i \log p_i = 0 pilogpi=0。通常,上式中的对数以 2 2 2为底或以 e e e为底(自然对数),这时熵的单位分别称作比特(bit)或纳特(nat).由定义可知,熵只依赖于 X X X的分布,而与 X X X的取值无关,所以也可将 X X X的熵记作 H ( p ) H(p) H(p),即:
    H ( p ) = − ∑ i = 1 n p i log ⁡ p i H(p) = -\sum_{i = 1}^n p_i \log p_i H(p)=i=1npilogpi
    由此可见,熵越大,随机变量的不确定性就越大。从熵的定义可验证
    0 ≤ H ( p ) ≤ log ⁡ n 0 \leq H(p) \leq \log n 0H(p)logn
    当随机变量只取两个值,例如1,0时,即 X X X的分布为:
    P ( X = 1 ) = p , P ( X = 0 ) = 1 − p , 0 ≤ p ≤ 1 P(X = 1) = p,\quad P(X = 0) = 1-p, \quad 0≤p≤1 P(X=1)=p,P(X=0)=1p,0p1
    其熵为:
    H ( p ) = − p log ⁡ 2 p − ( 1 − p ) log ⁡ 2 ( 1 − p ) H(p) = -p \log_2 p - (1 - p)\log_2 (1 - p) H(p)=plog2p(1p)log2(1p)
    这时,熵 H ( p ) H(p) H(p)随概率 p p p变化的曲线如下图所示(单位为比特):
    熵的变化曲线
    p = 0 p = 0 p=0 p = 1 p = 1 p=1 H ( p ) = 0 H(p) = 0 H(p)=0,随机变量完全没有不确定,当 p = 0.5 p = 0.5 p=0.5时, H ( p ) = 1 H(p) = 1 H(p)=1,熵取值最大,随机变量不确定性最大。

    设有随机变量 ( X , Y ) (X, Y) (X,Y),其联合概率分布为:

    P ( X = x i , Y = y i ) = p i j { i = 1 , 2 , ⋯   , n j = 1 , 2 , ⋯   , m P(X = x_i, Y = y_i) = p_{ij} \quad \begin{cases} i = 1, 2, \cdots, n \\ j = 1, 2, \cdots, m \end{cases} P(X=xi,Y=yi)=pij{i=1,2,,nj=1,2,,m

    条件熵 H ( Y ∣ X ) H(Y|X) H(YX)表示在已知随机变量 X X X的条件下随机变量 Y Y Y的不确定性。随机变量 X X X给定的条件下随机变量 Y Y Y的条件熵(conditional entropy) H ( Y ∣ X ) H(Y|X) H(YX),定义为 X X X给定条件下 Y Y Y的条件概率分布的熵对 X X X的数学期望:
    H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) H(Y|X) = \sum_{i = 1}^n p_iH(Y|X = x_i) H(YX)=i=1npiH(YX=xi)

    其中, p i = P ( X = x i ) , i = 1 , 2 , ⋯   , n p_i = P(X = x_i), i = 1, 2, \cdots, n pi=P(X=xi),i=1,2,,n

    当熵和条件熵中的概率由数据估计(如极大似然估计)得到时,所对应的熵与条件熵分别称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)。此时,如果有0概率,令 0 log ⁡ 0 = 0 0\log0 = 0 0log0=0

    信息增益(information gain)表示得知特征 X X X的信息而使得类 Y Y Y的信息的不确定性减少的程度。特征 a ∗ a_* a对训练数据集 D D D的信息增益 g ( D , a ∗ ) g(D, a_*) g(D,a),定义为集合 D D D的经验熵 H ( D ) H(D) H(D)与特征 a ∗ a_* a给定条件下 D D D的经验条件熵 H ( D ∣ a ∗ ) H(D|a_*) H(Da)之差,即:
    g ( D , a ∗ ) = H ( D ) − H ( D ∣ a ∗ ) g(D, a_*) = H(D) - H(D|a_*) g(D,a)=H(D)H(Da)
    一般地,熵 H ( Y ) H(Y) H(Y)与条件熵 H ( Y ∣ X ) H(Y|X) H(YX)之差称为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

    决策树学习应用信息增益准则选择特征。给定训练数据集 D D D和特征 a ∗ a_* a,经验熵 H ( D ) H(D) H(D)表示对数据集 D D D进行分类的不确定性。而经验条件熵 H ( D ∣ a ∗ ) H(D|a_*) H(Da)表示在特征 a ∗ a_* a给定的条件下对数据集 D D D进行分类的不确定性。那么它们的差,即信息增益,就表示由于特征 a ∗ a_* a而使得对数据集 D D D的分类的不确定性减少的程度。显然,对于数据集 D D D而言,信息增益依赖于特征,不同的特征往往具有不同的信息增益,信息增益大的特征具有更强的分类能力。

    根据信息增益准则的特征选择方法:对训练数据集(或子集) D D D,计算其每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征。

    设训练数据集为 D D D ∣ D ∣ |D| D表示其样本容量,即样本个数。设有 K K K个类 C k C_k Ck k = 1 , 2 , ⋯   , K k=1, 2, \cdots, K 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=1KCk=D。设特征 a ∗ a_* a V V V个不同的取值 { a ∗ 1 , a ∗ 2 , ⋯   , a ∗ V } \{ a_*^1, a_*^2, \cdots, a_*^V\} {a1,a2,,aV},根据特征 a ∗ a_* a的取值将 D D D划分为 V V V个子集 D 1 , D 2 , ⋯   , D V D_1, D_2, \cdots, D_V D1,D2,,DV ∣ D t ∣ |D_t| Dt D t D_t Dt的样本个数, ∑ i = 1 n ∣ D t ∣ = ∣ D ∣ \sum_{i=1}^n|D_t|=|D| i=1nDt=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 \cap C_k Dik=DiCk ∣ D i k ∣ |D_{ik}| Dik D i k D_{ik} Dik的样本个数。于是计算信息增益的方法如下:

    信息增益
    输入:训练数据集 D D D和特征 a ∗ a_* a
    输出:特征 a ∗ a_* a对训练数据集 D D D的信息增益 g ( D , a ∗ ) g(D, a_*) g(D,a)
    1.计算数据集 D D D的经验熵 H ( D ) H(D) H(D) H ( D ) = − ∑ k = 1 K C k D log ⁡ 2 C k D H(D) = -\sum_{k=1}^K \frac{C_k}{D}\log_2\frac{C_k}{D} H(D)=k=1KDCklog2DCk
    2.计算特征 A A A对数据集 D D D的经验条件熵 H ( D ∣ A ) H(D|A) H(DA) 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 log ⁡ 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(DA)=i=1nDDiH(Di)=i=1nDDik=1KDiDiklog2DiDik
    3.计算信息增益: g ( D , a ∗ ) = H ( D ) − H ( D ∣ a ∗ ) g(D, a_*) = H(D) - H(D|a_*) g(D,a)=H(D)H(Da)

    一般而言,信息增益越大,则意味着使用特征 a ∗ a_* a来进行划分所获得的“纯度提升”越大。因此,我们可用信息增益来进行决策树的划分属性选择,即在上述决策树分类算法第10行使用 a ∗ = arg  max ⁡ a ∈ A g ( D , a ) a_* = \text{arg}\ \max_{a \in A}g(D, a) a=arg maxaAg(D,a)选择最优划分属性。著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性。

    ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征,递归地构建决策树。具体方法是:从根结点开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立子结点。之后,再对子结点递归地调用以上方法,构建决策树,直到所有特征的信息增益均很小或没有特征可以选择为止,最终得到一个决策树。ID3相当于用极大似然法进行概率模型的选择

    ID3算法
    输入:训练数据集 D D D,特征集 A A A,阈值 ϵ \epsilon ϵ
    输出:决策树 T T T
    1.若 D D D中所有实例属于同一类 C k C_k Ck,则 T T T为单结点树,并将类 C k C_k Ck作为该结点的类标记,返回决策树 T T T
    2.若 A = ∅ A = \varnothing A=,则 T T T为单结点树,并将 D D D中实例数最大的类 C k C_k Ck,作为该结点的类标记,返回决策树 T T T
    3.否则,计算 A A A中各特征对 D D D的信息增益,选择信息增益最大的特征 a ∗ a_* a
    4.如果 a ∗ a_* a的信息增益小于阈值 ϵ \epsilon ϵ,则置 T T T为单结点树,并将 D D D中实例数最大的类 C k C_k Ck作为该结点的类标记,返回决策树 T T T
    5.否则,对 a ∗ a_* a的每一可能值 a ∗ v a_*^v av,依 a ∗ = a ∗ v a_* = a_*^v a=av D D D分割为若干非空子集 D v D_v Dv,将 D v D_v Dv中实例数最大的类作为标记,构建子结点,由结点及其子结点构成决策树 T T T,返回决策树 T T T
    6.对第 v v v个子结点,以 D v D_v Dv为训练集,以 A − { a ∗ } A - \{a_*\} A{a}为特征集,递归地调用第(1)步~第(5)步,得到子树 T v T_v Tv,并返回子树 T v T_v Tv

    信息增益率

    信息增益值的大小是相对于训练数据集而言的,并没有绝对意义。在训练数据集的经验熵大的时候,信息增益值会偏大。反之,信息增益值会偏小。使用信息增益率(information gain ratio)可以对这一问题进行校正。这是特征选择的另一准则。特征 a ∗ a_* a对训练数据集 D D D的信息增益率 g g ( D , a ∗ ) g_g(D, a_*) gg(D,a)定义为其信息增益 g ( D , a ∗ ) g(D, a_*) g(D,a)与训练数据集 D D D的经验熵 H ( D ) H(D) H(D)之比:
    g g ( D , a ∗ ) = g ( D , a ∗ ) H ( D ) g_g(D, a_*) = \frac{g(D, a_*)}{H(D)} gg(D,a)=H(D)g(D,a)

    如前文所说,信息增益准则对可取值数目较多的属性有所偏好,为减少这种偏好可能带来的不利影响,著名的C4.5决策树算法不直接使用信息增益来选择划分属性,而是使用信息增益率来选择最优划分属性。

    C4.5算法
    输入:训练数据集 D D D,特征集 A A A,信息增益率阈值 ϵ \epsilon ϵ,信息增益阈值 α \alpha α
    输出:决策树 T T T
    1.若 D D D中所有实例属于同一类 C k C_k Ck,则 T T T为单结点树,并将类 C k C_k Ck作为该结点的类标记,返回决策树 T T T
    2.若 A = ∅ A = \varnothing A=,则 T T T为单结点树,并将 D D D中实例数最大的类 C k C_k Ck,作为该结点的类标记,返回决策树 T T T
    3.否则,计算 A A A中各特征对 D D D的信息增益和信息增益率,在信息增益大于 α \alpha α的特征中选择信息增益率最大的特征 a ∗ a_* a
    4.如果 a ∗ a_* a的信息增益率小于阈值 ϵ \epsilon ϵ,则置 T T T为单结点树,并将 D D D中实例数最大的类 C k C_k Ck作为该结点的类标记,返回决策树 T T T
    5.否则,对 a ∗ a_* a的每一可能值 a ∗ v a_*^v av,依 a ∗ = a ∗ v a_* = a_*^v a=av D D D分割为若干非空子集 D v D_v Dv,将 D v D_v Dv中实例数最大的类作为标记,构建子结点,由结点及其子结点构成决策树 T T T,返回决策树 T T T
    6.对第 v v v个子结点,以 D v D_v Dv为训练集,以 A − { a ∗ } A - \{a_*\} A{a}为特征集,递归地调用第(1)步~第(5)步,得到子树 T v T_v Tv,并返回子树 T v T_v Tv

    需注意的是,信息增益率准则对可取值数目较少的属性有所偏好,因此,C4.5算法并不是直接选择增益率最大的候选划分属性,而是使用了一个启发式的方法选择最优划分属性:先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的.。

    连续值处理

    实际的任务中常会遇到连续属性,对于全部为连续属性的样本来说,我们一般使用回归决策树来处理。C4.5算法则采用了二分法对连续属性进行处理。由于连续属性的可取值数目不再有限,因此,不能直接根据连续属性的可取值来对结点进行划分。此时,连续属性离散化技术可派上用场。最简单的策略是采用二分法对连续属性进行处理。

    给定样本集 D D D和连续属性 a a a,假定 a a a D D D上出现了 n n n个不同的取值,将这些值从小到大进行排序,记为 { a 1 , a 2 , a 3 , ⋯   , a n } \{a_1, a_2, a_3, \cdots, a_n\} {a1,a2,a3,,an}。基于划分点 t t t可将 D D D分为子集 D t + D_t^+ Dt+ D t − D_t^- Dt,其中 D t + D_t^+ Dt+包含那些在属性 a a a上取值大于 t t t的样本,而 D t − D_t^- Dt则包含那些在属性 a a a上取值不大于 t t t的样本。显然,对相邻的属性取值 a i a^i ai a i + 1 a^{i + 1} ai+1来说, t t t在区间 [ a i , a i + 1 ) [a^i, a^{i + 1}) [ai,ai+1)中取任意值所产生的划分结果相同.因此,对连续属性 a a a,我们可考察包含 n − 1 n-1 n1个元素的候选划分点集合:
    T a = { a i + a i + 1 2   ∣   1 ≤ i ≤ n − 1 } T_a = \{\frac{a^i + a^{i + 1}}{2} \ | \ 1 \leq i \leq n - 1\} Ta={2ai+ai+1  1in1}

    即把区间 [ a i , a i + 1 ) [a^i, a^{i + 1}) [ai,ai+1)的中位点 a i + a i + 1 2 \frac{a^i + a^{i + 1}}{2} 2ai+ai+1作为候选划分点。然后,我们就可像离散属性值一样来考察这些划分点,选取最优的划分点进行样本集合的划分:
    G a i n ( D , a ) = max ⁡ t ∈ T a G a i n ( D , a , t ) = max ⁡ t ∈ T a E n t ( D ) − ∑ λ ∈ { − , + } D t λ D E n t ( D t λ ) \begin{aligned} Gain(D, a) &= \max_{t \in T_a} Gain(D, a, t)\\ & = \max_{t \in T_a} Ent(D) - \sum_{\lambda \in \{-, +\}} \frac{D^\lambda _t}{D}Ent(D^\lambda _t) \end{aligned} Gain(D,a)=tTamaxGain(D,a,t)=tTamaxEnt(D)λ{,+}DDtλEnt(Dtλ)

    其中 G a i n ( D , a , t ) Gain(D, a, t) Gain(D,a,t)是样本集 D D D基于划分点 t t t二分后的信息增益。于是,我们就可选择使 G a i n ( D , a , t ) Gain(D, a, t) Gain(D,a,t)最大化的划分点。

    缺失值处理

    现实任务中常会遇到不完整样本,即样本的某些属性值缺失。且在属性数目较多的情况下,有时会有大量样本出现缺失值。如果简单地放弃不完整样本,仅使用无缺失值的样本来进行学习,显然是对数据信息极大的浪费。显然,有必要考虑利用有缺失属性值的训练样例来进行学习。

    划分属性的选择

    给定训练集 D D D和属性 a a a,令 D ~ \tilde{D} D~表示 D D D中在属性 a a a上没有缺失值的样本子集。显然,我们仅可根据 D ~ \tilde{D} D~来判断属性 a a a的优劣。假定属性 a a a V V V个可取值 { a 1 , a 2 , a 3 , ⋯   , a V } \{a^1, a^2, a^3, \cdots, a^V\} {a1,a2,a3,,aV},令 D ~ v \tilde{D}^v D~v表示 D ~ \tilde{D} D~中在属性 a a a上取值为 a v a^v av的样本子集, D ~ k \tilde{D}_k D~k表示 D ~ \tilde{D} D~中属于第 k k k ( k = 1 , 2 , 3 , ⋯   , K ) (k = 1, 2, 3, \cdots, K) (k=1,2,3,,K)的样本子集,则显然有 D ~ = ⋃ k = 1 K D ~ k \tilde{D} = \bigcup^K_{k = 1}\tilde{D}_k D~=k=1KD~k D ~ = ⋃ v = 1 V D ~ v \tilde{D} = \bigcup^V_{v = 1}\tilde{D}^v D~=v=1VD~v。假定我们为每个样本 x x x赋予一个权重 ω x \omega_x ωx,并定义:
    ρ = ∑ x ∈ D ~ ω x ∑ x ∈ D ω x p ~ k = ∑ x ∈ D ~ k ω x ∑ x ∈ D ~ ω x r ~ v = ∑ x ∈ D ~ v ω x ∑ x ∈ D ~ ω x \begin{aligned} \rho & = \frac{\sum_{x \in \tilde{D}}\omega_x}{\sum_{x \in D}\omega_x}\\ \tilde{p}_k & = \frac{\sum_{x \in \tilde{D}_k}\omega_x}{\sum_{x \in \tilde{D}}\omega_x}\\ \tilde{r}_v & = \frac{\sum_{x \in \tilde{D}^v}\omega_x}{\sum_{x \in \tilde{D}}\omega_x} \end{aligned} ρp~kr~v=xDωxxD~ωx=xD~ωxxD~kωx=xD~ωxxD~vωx

    直观地看,对于属性 a a a ρ \rho ρ表示无缺失值样本所占的比例, p ~ k \tilde{p}_k p~k表示无缺失值样本中第 k k k类所占的比例, r ~ v \tilde{r}_v r~v则表示无缺失值样本中在属性 a a a上取值 a v a^v av的样本所占的比例。基于上述定义,我们可将信息增益的计算式推广为:
    G a i n ( D , a ) = ρ × G a i n ( D ~ , a ) = ρ × ( E n t ( D ~ ) − ∑ x = 1 V r ~ v E n t ( D ~ v ) ) \begin{aligned} Gain(D, a) &= \rho \times Gain(\tilde{D}, a)\\ & = \rho \times (Ent(\tilde{D}) - \sum_{x = 1}^V \tilde{r}_v Ent(\tilde{D}^v)) \end{aligned} Gain(D,a)=ρ×Gain(D~,a)=ρ×(Ent(D~)x=1Vr~vEnt(D~v))

    对样本进行划分

    根据上面的定义,若样本 x x x在划分属性 a a a上的取值已知,则将 x x x划入与其取值对应的子结点,且样本权值在子结点中保持为 ω x \omega_x ωx。若样本 x x x在划分属性 a a a上的取值未知,则将 x x x同时划入所有子结点,且样本权值在与属性值 a v a^v av对应的子结点中调整为 r ~ v × ω x \tilde{r}_v \times \omega_x r~v×ωx。直观地看,这就是让同一个样本以不同的概率划入到不同的子结点中去。

    基尼指数

    数据集 D D D的纯度还可用基尼值来度量:
    G i n i ( D ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 Gini(D) = \sum^K_{k=1}p_k(1 - p_k) = 1 - \sum^K_{k=1}p_k^2 Gini(D)=k=1Kpk(1pk)=1k=1Kpk2

    其中, K K K为类别数, p k p_k pk为样本点属于第 k k k类的概率。对于二类分类问题,若样本点属于第1个类的概率是 p p p,则概率分布的基尼指数为:
    G i n i ( D ) = 2 p ( 1 − p ) Gini(D) = 2p(1 - p) Gini(D)=2p(1p)

    直观来说, G i n i ( D ) Gini(D) Gini(D)反映了从数据集 D D D中随机抽取两个样本,其类别标记不一致的概率。因此, G i n i ( D ) Gini(D) Gini(D)越小,则数据集 D D D的纯度越高。对于属性 a a a的基尼指数定义为:
    G i n i _ i n d e x ( D , a ) = ∑ v = 1 V D v D G i n i ( D v ) Gini\_index(D, a) = \sum^V_{v = 1}\frac{D^v}{D}Gini(D^v) Gini_index(D,a)=v=1VDDvGini(Dv)

    CART算法中,我们在候选属性集合 A A A中,选择那个使得划分后基尼指数最小的属性作为最优划分属性,即: a ∗ = arg min ⁡ a ∈ A G i n i _ i n d e x ( D , a ) a_* = \text{arg}\min_{a \in A}Gini\_index(D, a) a=argminaAGini_index(D,a)

    在二类分类问题中,基尼指数 G i n i ( D ) Gini(D) Gini(D)、熵 H ( p ) H(p) H(p)的一半,和分类误差率的关系:
    特征选择方法对比
    其中,横坐标表示概率 p p p,纵坐标表示损失。可以看出基尼指数和熵的一半的曲线很接近,都可以近似地代表分类误差率。

    分类树的剪枝

    剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段。在决策树学习中,为了尽可能正确分类训练样本,结点划分过程将不断重复,有时会造成决策树分支过多,这时就可能因为对训练样本学习得“太好”了,以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此,可通过主动去掉一些分支来降低过拟合的风险。决策树剪枝的基本策略有预剪枝后剪枝

    预剪枝

    预剪枝是指在决策树生成过程中,对每个结点在划分前先进行估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点。停止决策树生长常用方法:

    1. 定义一个高度,当决策树达到该高度时就停止决策树的生长
    2. 达到某个节点的实例具有相同的特征向量,即使这些实例不属于同一类,也可以停止决策树的生长。这个方法对于处理数据的数据冲突问题比较有效。
    3. 定义一个阈值,当达到某个节点的实例个数小于阈值时就可以停止决策树的生长
    4. 定义一个阈值,通过计算每次扩张对系统性能的增益,并比较增益值与该阈值大小来决定是否停止决策树的生长。

    后剪枝

    后剪枝则是先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升,则将该子树替换为叶结点。相比于预剪枝,后剪枝更常用,因为在预剪枝中精确地估计何时停止树增长很困难。

    错误率降低剪枝(REP,Reduced-Error Pruning)

    错误率降低剪枝方法是一种比较简单的后剪枝的方法。在该方法中,可用的数据被分成两个样例集合:首先是训练集,它被用来形成学习到的决策树,另一个是与训练集分离的验证集,它被用来评估这个决策树在后续数据上的精度,确切地说是用来评估修剪这个决策树的影响。学习器可能会被训练集中的随机错误和巧合规律所误导,但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验。

    错误率降低剪枝方法考将树上的每个节点作为修剪的候选对象,再决定是对该节点进行剪枝:

    1. 删除以此结点为根的子树
    2. 使其成为叶子结点
    3. 当修剪后的树对于验证集合的性能不比修剪前的树的性能差时,则确认删除该结点,否则恢复该节点

    因为训练集合的过拟合,使得验证集合数据能够对其进行修正,反复进行上面的操作,从底向上的处理结点,删除那些能够提高验证集合的精度的结点,直到进一步修剪会降低验证集合的精度为止。

    错误率降低剪枝方法是最简单的后剪枝方法之一,不过由于使用独立的测试集,原始决策树相比,修改后的决策树可能偏向于过度修剪。这是因为一些不会再次在测试集中出现的很稀少的训练集实例所对应的分枝在剪枝过程中往往会被剪枝。尽管错误率降低剪枝方法有这个缺点,不过错误率降低剪枝方法仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学习方法的优点和缺点提供了一个很好的学习思路。由于验证集合没有参与决策树的构建,所以用错误率降低剪枝方法剪枝后的决策树对于测试样例的偏差要好很多,能够解决一定程度的过拟合问题。

    悲观错误剪枝(PEP,Pesimistic-Error Pruning)

    悲观错误剪枝方法是根据剪枝前后的错误率来判定子树的修剪。它不需要像错误率降低修剪方法那样,需要使用部分样本作为测试数据,而是完全使用训练数据来生成决策树,并进行剪枝,即决策树生成和剪枝都使用训练集

    该方法引入了统计学中连续修正的概念弥补错误率降低剪枝方法中的缺陷,在评价子树的训练错误公式中添加了一个常数,即假定每个叶子结点都自动对实例的某个部分进行错误的分类。

    把一颗具有多个叶子节点的子树的分类用一个叶子节点来替代的话,在训练集上的误判率肯定是上升的,但是在新数据上不一定。于是我们把子树的误判计算加上一个经验性的惩罚因子来做是否剪枝的考量指标。对于一个叶子节点,它覆盖了 N N N个样本,其中有 E E E个错误,那么该叶子节点的错误率为 E + 0.5 N \frac{E + 0.5}{N} NE+0.5。这个 0.5 0.5 0.5就是惩罚因子,那么一颗子树,它有 L L L个叶子节点,那么该子树的误判率估计为:
    ∑ E i + 0.5 ∗ L ∑ N i \frac{\sum E_i +0.5 * L}{\sum N_i} NiEi+0.5L

    这样的话,我们可以看到一棵子树虽然具有多个子节点,但由于加上了惩罚因子,所以子树的误判率计算未必占到便宜。剪枝后内部节点变成了叶子节点,其误判个数 E E E也需要加上一个惩罚因子,变成 E + 0.5 E+0.5 E+0.5,那么子树是否可以被剪枝就取决于剪枝后的错误 E + 0.5 E+0.5 E+0.5在的标准误差内。对于样本的误差率 e e e,我们可以根据经验把它估计成各种各样的分布模型,比如二项式分布、正态分布等。如果 E + 0.5 < E i + S E ( E i ) E+0.5 < E_i + SE(E_i) E+0.5<Ei+SE(Ei)则对 i i i进行剪枝。

    代价复杂度剪枝(CCP,Cost-Complexity Pruning)

    代价复杂度剪枝算法为子树 T t T_t Tt定义了代价和复杂度,以及一个可由用户设置的衡量代价与复杂度之间关系的参数 α α α。其中,代价指在剪枝过程中因子树 T t T_t Tt被叶节点替代而增加的错分样本,复杂度表示剪枝后子树 T t T_t Tt减少的叶结点数, α α α则表示剪枝后树的复杂度降低程度与代价间的关系,定义为:
    α = R ( t ) − R ( T t ) ∣ N t ∣ − 1 \alpha = \frac{R(t) - R(T_t)}{|N_t| - 1} α=Nt1R(t)R(Tt)

    其中, ∣ N t ∣ |N_t| Nt是子树 T t T_t Tt中的叶节点数, R ( t ) = r ( t ) ∗ p ( t ) R(t) = r(t) * p(t) R(t)=r(t)p(t)为结点 t t t的错误代价, r ( t ) r(t) r(t)为结点 t t t的错分样本率, p ( t ) p(t) p(t)为落入结点 t t t的样本占所有样本的比例, R ( T t ) = ∑ R ( i ) R(T_t) = \sum R(i) R(Tt)=R(i)是子树 T t T_t Tt错误代价, i i i为子树 T t T_t Tt的叶节点。

    1. 对于完全决策树 T T T的每个非叶结点计算 α α α值,循环剪掉具有最小 α α α值的子树,直到剩下根节点,得到一系列的剪枝树 { T 0 , T ‘ 1 , T 2 , ⋯   , T m } \{ T_0, T_`1, T_2, \cdots, T_m \} {T0,T1,T2,,Tm},其中 T 0 T_0 T0为原有的完全决策树, T m T_m Tm为根结点, T i + 1 T_{i +1} Ti+1为对 T i T_i Ti进行剪枝的结果
    2. 从子树序列中,根据真实的误差估计选择最佳决策树
    REPPEPCCP
    剪枝方式自底向上自顶向下自底向上
    计算复杂度 O ( n ) O(n) O(n) O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2)
    误差估计测试集上误差估计使用连续纠正标准误差

    回归树

    建立回归树的过程大致可以分为两步:

    1. 将预测变量空间( X 1 , X 2 , X 3 , ⋯   , X p X_1, X_2, X_3, \cdots, X_p X1,X2,X3,,Xp)的可能取值构成的集合分割成 J J J个互不重叠的区域 { R 1 , R 2 , R 3 , ⋯   , R J } \{ R_1, R_2, R_3, \cdots, R_J\} {R1,R2,R3,,RJ}
    2. 对落入区域 R j R_j Rj的每个观测值作同样的预测,预测值等于 R j R_j Rj上训练集的各个样本取值的算术平均数。

    比如,在第一步中得到两个区域 R 1 R_1 R1 R 2 R_2 R2 R 1 R_1 R1中训练集的各个样本取值的算术平均数为10, R 2 R_2 R2中训练集的各个样本取值的算术平均数为20。则对给定的观测值 X = x X = x X=x,若 x ∈ R 1 x \in R_1 xR1,给出的预测值为10,若 x ∈ R 2 x \in R_2 xR2,则预测值为20。

    所以,类似于上述决策树分类算法的第(10)步,关键在于如何构建区域划分 { R 1 , R 2 , R 3 , ⋯   , R J } \{ R_1, R_2, R_3, \cdots, R_J\} {R1,R2,R3,,RJ}。事实上,区域的形状是可以为任意形状的,但出于模型简化和增强可解释性的考虑,这里将预测变量空间划分成高维矩形,我们称这些区域为称盒子。划分区域的目标是找到使模型的残差平方和 R S S RSS RSS最小的矩形区域 { R 1 , R 2 , R 3 , ⋯   , R J } \{ R_1, R_2, R_3, \cdots, R_J\} {R1,R2,R3,,RJ} R S S RSS RSS的定义为:
    R S S = ∑ j = 1 J ∑ i ∈ R j ( y i − y ^ R j ) 2 RSS = \sum^J_{j=1} \sum_{i \in R_j}(y_i - \hat{y}_{R_j})^2 RSS=j=1JiRj(yiy^Rj)2

    其中, y ^ R j \hat{y}_{R_j} y^Rj是第 j j j个矩形区域中训练集中各个样本取值的算术平均数。但是,要想考虑将特征空间划分为 J J J个矩形区域的所有可能性,在计算上是不可行的。因此一般采用一种自上而下的贪婪法:递归二又分裂。“自上而下”指的是它从树顶端开始依次分裂预测变量空间,每个分裂点都产生两个新的分支。“贪婪”意指在建立树的每一步中,最优分裂确定仅限于某一步进程,而不是针对全局去选择那些能够在未来进程中构建出更好的树的分裂点。

    在执行递归二又分裂时,先选择预测变量 X j X_j Xj和分割点 s s s,将预测变量空间分为两个区域 { X ∣ X j < s } \{ X|X_j <s \} {XXj<s} { X ∣ X j ≥ s } \{ X|X_j \geq s \} {XXjs},使 R S S RSS RSS尽可能地减小。也就是说,考虑所有预测变量 X 1 , X 2 , X 3 , ⋯   , X p X_1, X_2, X_3, \cdots, X_p X1,X2,X3,,Xp和与每个预测变量对应的 s s s的取值,然后选择预测变量和分割点,使构造出的树具有最小的 R S S RSS RSS。更详细地,对 j j j s s s,定义一对半平面:
    R 1 ( j , s ) = { X ∣ X j < s } 和 R 2 ( j , s ) = { X ∣ X j ≥ s } R_1(j, s) = \{ X|X_j <s \} \quad \text{和} \quad R_2(j, s) = \{ X|X_j \geq s \} R1(j,s)={XXj<s}R2(j,s)={XXjs}

    寻找 j j j s s s,使得下式最小:
    ∑ x i ∈ R 1 ( j , s ) ( y i − y ^ R 1 ) 2 + ∑ x i ∈ R 2 ( j , s ) ( y i − y ^ R 2 ) 2 \sum_{x_i \in R_1(j, s)}(y_i - \hat{y}_{R_1})^2 + \sum_{x_i \in R_2(j, s)}(y_i - \hat{y}_{R_2})^2 xiR1(j,s)(yiy^R1)2+xiR2(j,s)(yiy^R2)2

    重复上述步骤,寻找继续分割数据集的最优预测变量和最优分割点,使随之产生的区域中的 R S S RSS RSS达到最小。此时被分割的不再是整个预测变量空间,而是之前确定的两个区域之一。如此一来就能得到3个区域。接着进一步分割3个区域之一以最小化 R S S RSS RSS。这一过程不断持续,直到符合某个停止准则,如我们在分类决策树中讨论到的前剪枝中的停止准则。

    区域 { R 1 , R 2 , R 3 , ⋯   , R J } \{ R_1, R_2, R_3, \cdots, R_J\} {R1,R2,R3,,RJ}产生后,就可以确定某一给定的测试数据所属的区域,并用这一区域训练集的各个样本取值的算术平均数作为与测试进行预测。

    f回归树实例

    回归树的剪枝

    上述方法生成的回归树会在训练集中取得良好的预测效果,却很有可能造成数据的过拟合,导致在测试集上效果不佳。原因在于这种方法产生的树可能过于复杂。一棵分裂点更少、规模更小(区域 { R 1 , R 2 , R 3 , ⋯   , R J } \{ R_1, R_2, R_3, \cdots, R_J\} {R1,R2,R3,,RJ}的个数更少)的树会有更小的方差和更好的可解释性(以增加微小偏差为代价)。针对上述问题,一种可能的解决办法是:仅当分裂使残差平方和 R S S RSS RSS的减小量超过某阈值时,才分裂树结点。这种策略能生成较小的树,但可能产生过于短视的问题,一些起初看来不值得的分裂却可能之后产生非常好的分裂。也就是说在下一步中, R S S RSS RSS会大幅减小。

    因此,更好的策略是生成一棵很大的树 T 0 T_0 T0,然后通过后剪枝得到子树。直观上看,剪枝的目的是选出使测试集预测误差最小的子树。子树的测试误差可以通过交叉验证或验证集来估计。但由于可能的子树数量极其庞大,对每一棵子树都用交叉验证来估计误差太过复杂。因此需要从所有可能的子树中选出一小部分再进行考虑。在回归树中,我们一般使用代价复杂度剪枝(CCP,Cost-Complexity Pruning),也称最弱联系剪枝(Weakest Link Pruning)。这种方法不是考虑每一棵可能的子树,而是考虑以非负调整参数 α \alpha α标记的一系列子树。每一个 α \alpha α的取值对应一棵子树 T ∈ T 0 T \in T_0 TT0,当 α \alpha α一定时,其对应的子树使下式最小:
    ∑ m = 1 ∣ T ∣ ∑ x i ∈ R m ( y i − y ^ R m ) 2 + α ∣ T ∣ \sum_{m=1}^{|T|} \sum_{x_i \in R_m}(y_i - \hat{y}_{R_m})^2 + \alpha |T| m=1TxiRm(yiy^Rm)2+αT

    这里的 ∣ T ∣ |T| T表示树 T T T的结点数, R m R_m Rm是第 m m m个终端结点对应的矩形(预测向量空间的一个子集), y ^ R m \hat{y}_{R_m} y^Rm是与 R m R_m Rm对应的预测值,也就是 R m R_m Rm中训练集的平均值。调整系数 α \alpha α在子树的复杂性和与训练数据的契合度之间控制权衡。当 α = 0 \alpha = 0 α=0时,子树 T T T等于原树 T 0 T_0 T0,因为此时上式只衡量了训练误差。而当 α \alpha α增大时,终端结点数多的树将为它的复杂付出代价,所以使上式取到最小值的子树会变得更小。

    α \alpha α从0开始逐渐增加时,树枝以一种嵌套的、可预测的模式被修剪,因此获得与 α \alpha α对应的所有子树序列是很容易的。可以用交又验证或验证集确定 α \alpha α,然后在整个数据集中找到与之对应的子树:

    回归决策树算法
    1.利用递归二叉分裂在训练集中生成一额大树,只有当终端结点包含的观测值个数低于某个最小值时才停止。
    2.对大树进行代价复杂性剪枝,得到一系列最优子树,子树是 α \alpha α的函数。
    3.利用 K K K折交叉验诞选择 α \alpha α。具体做法是将训练集分为 K K K折。对所有 k = 1 , 2 , 3 , ⋯   , K k=1, 2, 3, \cdots, K k=1,2,3,,K,对训练集上所有不属于第 k k k折的数据重复第(1)步~第(2)步得到与 α \alpha α对应的子树,并求出上述子树在第 k k k折上的均方预测误差。
    4.每个 α \alpha α会有相应的 K K K个均方预测误差,对这 K K K个值求平均,选出使平均误差最小的 α \alpha α
    5.找出选定的 α \alpha α在第(2)步中对应的子树。

    决策树的基础即是上文所述的分类决策树与回归决策树,其预测准确性一般比回归和分类方法弱,但可以通过用集成学习方法组合大量决策树,显著提升树的预测效果,这些方法我将会在接下来的文章中继续阐述,欢迎关注学习讨论!

    展开全文
  • 决策树与随机森林(从入门到精通)

    万次阅读 多人点赞 2020-07-06 22:54:44
    决策树(decision tree)是一种基本的分类与回归方法,本文主要讨论用于分类的决策树决策树学习通常包括三个步骤:特征选择,决策树的生成和决策树的修剪。而随机森林则是由多个决策树所构成的一种分类器,更准确...

      决策树(decision tree)是一种基本的分类与回归方法,本文主要讨论用于分类的决策树。决策树学习通常包括三个步骤:特征选择,决策树的生成和决策树的修剪。而随机森林则是由多个决策树所构成的一种分类器,更准确的说,随机森林是由多个弱分类器组合形成的强分类器。

    一、信息论知识

    1.信息熵的概念

      设离散型随机变量X的取值有 x 1 , x 2 , x 3 , . . . , x n x_{1},x_{2},x_{3},...,x_{n} x1,x2,x3,...,xn,其发生概率分别为 p 1 , p 2 , p 3 , . . . , p n p_{1},p_{2},p_{3},...,p_{n} p1,p2,p3,...,pn,那么就可以定义信息熵为:
    在这里插入图片描述
      一般对数的底数是2,当然也可以换成e,当对数底数为2时,信息熵的单位为比特,信息熵也称香农熵。当对数不为2而是其他大于2的整数r时,我们称信息熵为r-进制熵,记为 H r ( X ) H_{r}(X) Hr(X),它与信息熵转换公式为:
    在这里插入图片描述
      信息熵用以描述信源的不确定度, 概率越大,可能性越大,但是信息量越小,不确定性越小,熵越小。

    2.条件熵

      设随机变量(X,Y)具有联合概率分布:
    在这里插入图片描述
      条件熵 H ( Y ∣ X ) H(Y|X) H(YX)表示 在已知随机变量X的条件下随机变量Y的不确定性。
       可以这样理解:
       (X,Y)发生所包含的熵,减去X单独发生的熵,就是在X发生的前提下,Y发生新带来的熵。
       所以条件熵有如下公式成立:
    在这里插入图片描述
       推导如下:
    在这里插入图片描述

    3.相对熵

       相对熵,又称互熵,交叉熵,鉴别信息,Kullback熵,Kullback-Leible散度等。定义如下:
    设p(x),q(x)是随机变量X中取值的两个概率分布,则p对q的相对熵为:
    在这里插入图片描述
      在信息理论中,相对熵等价于两个分布的信息熵(Shannon entropy)的差值。 即:
    在这里插入图片描述

    4.互信息

      两个随机变量X和Y的互信息,定义为X,Y的联合分布和独立分布乘积的相对熵。即:
    在这里插入图片描述
      所以根据KL散度也就是相对熵的定义,可以推出互信息的表达式如下:
    在这里插入图片描述
      继续推导如下:
    在这里插入图片描述
      所以最后有:
    在这里插入图片描述

    5.几个量之间的关系

      结合上述条件熵的两个表达式,可以进一步推出:
    在这里插入图片描述
      当然我们也可以根据熵的定义来直接推出上面这个互信息的公式:
    在这里插入图片描述
      同时我们也可以得到两个不等式:
    在这里插入图片描述
      上面这个不等式告诉我们,对于一个与X相关的随机变量Y,只要我们得知了一点关于Y的信息,那么X的不确定度就会减小。
      最后,借助强大的韦恩图来记住这些关系:
    在这里插入图片描述

    二、决策树

    1.引入

      决策树,顾名思义,就是帮我们做出决策的树。现实生活中我们往往会遇到各种各样的抉择,把我们的决策过程整理一下,就可以发现,该过程实际上就是一个树的模型。比如相亲的时候:
    在这里插入图片描述
      我们可以认为年龄,长相,收入是一个人的三个特征,每次我们做出抉择都是基于这三个特征来把一个节点分成好几个新的节点。
      一颗完整的决策树包含以下三个部分:

    1. 根节点:就是树最顶端的节点,比如上面图中的“年龄”。
    2. 叶子节点:树最底部的那些节点,也就是决策结果,见还是不见。
    3. 内部节点,除了叶子结点,都是内部节点。

       树中每个内部节点表示在一个属性特征上的测试,每个分支代表一个测试输出,每个叶节点表示一种类别。
    给定一个决策树的实例:
    在这里插入图片描述
       构造决策树如下:
    在这里插入图片描述

    1.第一层根节点
    被分成14份,9是/5否,总体的信息熵为:
    H0= -[(5/14)log5/14+(9/14)log9/14]=0.9403.

    2.第二层
    晴:被分为5份,2是/3否,它的信息熵为:
    H1=-[(2/5)log2/5+(3/5)log3/5]=0.9710.
    阴:被分为4份,4是/0否,它的信息熵为:
    H2= -[log1]=0.
    雨:被分为5份,3是/2否,它的信息熵为:
    H3=-[(2/5)log2/5+(3/5)log3/5]=0.9710.
       我们规定,假设我们选取天气为分类依据,把它作为根节点,那么第二层的加权信息熵,也就是 H ′ = 5 / 14 H 1 + 4 / 14 H 2 + 5 / 14 H 3 H^{'}=5/14H1+4/14H2+5/14H3 H=5/14H1+4/14H2+5/14H3要比H0小,也就是随着决策的进行,其不确定度要减小才行,要不然我们还决策干什么。。。决策肯定是一个由不确定到确定状态的转变。 算出 H ′ = 0.6936 < 0.9403 H^{'}=0.6936<0.9403 H=0.6936<0.9403,符合要求。
       事实上,随着分类的进行,越来越多的信息被知道,那么总体的熵肯定实惠下降的。
      同样,对于晴这个节点,他的两个叶子结点的熵都是0,到了叶子结点之后,熵就变为0了,就得到了决策结果。
       因此,决策树采用的是自顶向下的递归方法,其基本思想是以信息熵为度量构造一棵熵值下降最快的树,到叶子节点处的熵值为0,此时每个叶子节点中的实例都属于同一类。 至于怎么定义下降最快,下面接着讲。

    2.决策树的生成算法

      首先我们要选择一个根节点,那么选谁当做根节点呢?比如上面的例子,有天气,湿度以及风级三个属性,所以我们要在三个当中选择一个。三个属性f1,f2,f3,以三个属性分别为根节点可以生成三棵树(从第一层到第二才层),而究竟选择谁来当根节点的准则,有以下三种。

    1.信息增益与ID3

      决策树中信息增益定义如下:
      给定一个样本集D,划分前样本集合D的熵是一定的 ,用H0表示; 使用某个特征A划分数据集D,计算划分后的数据子集的熵,用H1表示,则:
      信息增益=H0-H1,也可以表示为:
    在这里插入图片描述
      比如上面实例中我选择天气作为根节点,将根节点一分为三,设f1表示天气,则有:
    g ( D , f 1 ) = H 0 − H ′ = 0.9403 − 0.6936 = 0.2467. g(D,f1)=H0-H^{'}=0.9403-0.6936=0.2467. g(D,f1)=H0H=0.94030.6936=0.2467.
      意思是,没有选择特征f1前,是否去打球的信息熵为0.9403,在我选择了天气这一特征之后,信息熵下降为0.6936,信息熵下降了0.2467,也就是信息增益为0.2467.

      信息增益的局限:信息增益偏向取值较多的特征。
      原因:当特征的取值较多时,根据此特征划分更容易得到纯度更高的子集,因此划分之后的熵更低,由于划分前的熵是一定的,因此信息增益更大,因此信息增益比较偏向取值较多的特征。
    比如说有一个特征可以把训练集的每一个样本都当成一个分支,也就说有n个样本,该特征就把树分成了n叉树,那么划分后的熵变为0,因此信息增益当然是下降最大的。 也就是如果我们在生成决策树的时候以信息增益作为判断准则,那么分类较多的特征会被优先选择。
      利用信息增益作为选择指标来生成决策树的算法称为ID3算法。

    2.信息增益率与C4.5

      为了解决信息增益的局限,引入了信息增益率的概念。分支过多容易导致过拟合,造成不理想的后果。假设原来的熵为0.9,选择f1特征划分后整体熵变成了0.1,也就是信息增益为0.8,而选择f2划分后,熵变为0.3,也就是信息增益为0.6。我们不想选择f1,因为它让决策树分支太多了,那么就可以定义决策指标=信息增益/特征本身的熵。f1划分后分支更多,也就是特征f1本身的熵比f2更大,大的数除以一个大的数,刚好可以中和一下。
      即:
    在这里插入图片描述
      还是以这张图为例子算一下:
    在这里插入图片描述
    现在我们要选择谁做根节点。未划分前:(前面都算过一遍了)
    H0= 0.9403.
    选择天气作为根节点,则有:
    晴:被分为5份,2是/3否,它的信息熵为:
    H1=0.9710.
    阴:被分为4份,4是/0否,它的信息熵为:
    H2= -[log1]=0.
    雨:被分为5份,3是/2否,它的信息熵为:
    H3=0.9710.
    划分后总体的信息熵为:
    H ′ = 5 / 14 H 1 + 4 / 14 H 2 + 5 / 14 H 3 = 0.6936 H^{'}=5/14H1+4/14H2+5/14H3=0.6936 H=5/14H1+4/14H2+5/14H3=0.6936 。一定要注意,这个算的是总体的信息熵, 那么信息增益为:0.2467.
    这个时候我们考虑天气本身的熵,这里算的是天气本身的熵,而不是样本X,也就是是否外出打球的熵,这里一定要将二者区分开。天气本身有三种可能,每种概率都已知,则天气的熵为:
    H 0 = − [ ( 5 / 14 ) l o g 5 / 14 + ( 4 / 14 ) l o g 4 / 14 + ( 5 / 14 ) l o g 5 / 14 ] = 0.9403 = 1.5774 H0= -[(5/14)log5/14+(4/14)log4/14+(5/14)log5/14]=0.9403=1.5774 H0=[(5/14)log5/14+(4/14)log4/14+(5/14)log5/14]=0.9403=1.5774.
    那么选择天气作为分类依据时,评价指标=0.2467/1.5774=0.1566.

      这里还是想要强调一下,很多人在算信息增益率的时候总是出错,是因为搞混了总体的熵与特征的熵!!! 我在算信息增益的时候,两个相减的熵都是算的总体的熵,也就是依据是否外出来划分的,而我计算特征本身的熵的时候,是依据这个特征本身来算的,比我算天气的熵,那么就看天气分为了哪几类,比如晴天,阴天,雨天之类的,每一类又有自己的概率,然后再根据信息熵的定义来计算,二者相除即是信息增益率。
      利用信息增益率作为选择指标来生成决策树的算法称为C4.5算法。

    3.Gini系数与CART

      定义:基尼指数(基尼不纯度):表示在样本集合中一个随机选中的样本被分错的概率。
      定义式:
    在这里插入图片描述
    一些参数的说明:

    1. pk表示选中的样本属于k类别的概率,则这个样本被分错的概率是(1-pk)。
    2. 样本集合中有K个类别,一个随机选中的样本可以属于这k个类别中的任意一个。
    3. 易知,当样本属于每一个类别的概率都相等即均为1/K时,基尼系数最大,也就是说此时不确定度最小。

      关于基尼系数的理解,网上有一种说法比较通俗易懂。现解释如下:
      我们知道信息熵的定义式为:
    在这里插入图片描述
      那么基尼系数实际上就是用 1 − p i 1-p_{i} 1pi来代替了 − l o g ( p i ) -log(p_{i}) log(pi),画出二者图像:
    在这里插入图片描述
      因为概率是属于0到1之间,所以我们只看01区间上的图像:基尼系数对于信息熵而言,就是在01区间内近似的用切线来代替了对数函数。因此,既然信息熵可以表述不确定度,那么基尼系数自然也可以,只不过存在一些误差。

      CART决策树又称分类回归树,当数据集的因变量为连续性数值时,该树算法就是一个回归树,可以用叶节点观察的均值作为预测值;当数据集的因变量为离散型数值时,该树算法就是一个分类树,可以很好的解决分类问题。
      当CART是分类树时,采用GINI值作为结点分裂的依据;当CART是回归树时,采用MSE(均方误差)作为结点分裂的依据。我们这里只讨论分类。

    3.决策树的评价

      假定样本总类别为K,而对于决策树的某叶节点,假定该叶子节点包含的样本数目为n,其中第k类的样本数目为 n k n_{k} nk,k=1,2,…,K。
    若某类样本的 n j n_{j} nj=n,其他类别个数全为0,也就是说该叶结点中所有样本完全属于同一个类,则称该结点为纯结点,其熵为0.
      若某一叶子结点中包含了所有类别的样本且各类数目相同,则称该结点为均结点。 其熵为 l o g K logK logK
      那么我们对所有叶子结点的熵求和,该值越小说明越精确。 而又由于各个叶子结点包含的样本数目不同,所以我们采用加权熵和。
      评价函数定义如下:
    在这里插入图片描述
      其中 N t N_{t} Nt表示叶子结点的样本数目,评价函数越小说明决策树越好。

    4.决策树的过拟合

      当决策树深度过大时,在训练集上表现特别好,往往就会出现过拟合现象,我们需要一些解决办法:

    1.剪枝

       剪枝总体思路:
       由完全树T0开始,剪枝部分结点得到树T1,然后再剪枝部分结点得到树T2,…,直到仅剩树根的Tk。在验证数据集上对这K个树分别评价,选择损失函数最小的树 T α T_{α} Tα
       三种决策树的生成算法过程相同,只是对于当前树的评价标准不同。

    三、随机森林

      随机森林也是为了解决决策树的过拟合问题。

    1.Bootstrap

      假设有一个大小为N的样本,我们希望从中得到m个大小为N的样本用来训练。bootstrap的思想是:首先,在N个样本里随机抽出一个样本x1,然后记下来,放回去,再抽出一个x2,… ,这样重复N次,即可得到N个新样本,这个新样本里可能有重复的。重复m次,就得到了m个这样的样本。实际上就是一个有放回的随机抽样问题。每一个样本在每一次抽的时候有同样的概率(1/N)被抽中。

    2.bagging策略

      bagging的名称来源于: Bootstrap Aggregating,意为自助抽样集成。既然出现了Bootstrap那么肯定就会使用到Bootstrap方法,其基本策略是:

    1. 利用Bootstrap得到m个样本大小为N的样本集。
    2. 在所有属性上,对每一个样本集建立分类器。
    3. 将数据放在这m个分类器上,最后根据m个分类器的投票结果,决定数据最终属于哪一类。如果是回归问题,就采用均值。

      什么时候用bagging?当模型过于复杂容易产生过拟合时,才使用bagging,决策树就容易产生过拟合。

    3.out of bag estimate(包外估计)

      在使用bootstrap来生成样本集时,由于我们是有放回抽样,那么可能有些样本会被抽到多次,而有的样本一次也抽不到。我们来做个计算:假设有N个样本,每个样本被抽中的概率都是1/N,没被选中的概率就是1-1/N,重复N次都没被选中的概率就是 ( 1 − 1 / N ) N (1-1/N)^N (11/N)N,当N趋于无穷时,这个概率就是1/e,大概为36.8%。也就是说样本足够多的时候,一个样本没被选上的概率有36.8%,那么这些没被选中的数据可以留作验证集。每一次利用Bootstrap生成样本集时,其验证集都是不同的。
      以这些没被选中的样本作为验证集的方法称为包外估计。

    4.样本随机与特征随机

      在我们使用Bootstrap生成m个样本集时,每一个样本集的样本数目不一定要等于原始样本集的样本数目,比如我们可以生成一个含有0.75N个样本的样本集,此处0.75就称为采样率。
      同样,我们在利用0.75N个样本生成决策树时,假设我们采用ID3算法,生成结点时以信息增益作为判断依据。我们的具体做法是把每一个特征都拿来试一试,最终信息增益最大的特征就是我们要选的特征。但是,我们在选择特征的过程中,也可以只选择一部分特征,比如20个里面我只选择16个特征。
      那可能有的人就要问了,假设你没选的4个特征里面刚好有一个是最好的呢?这种情况是完全可能出现的,但是我们在下一次的分叉过程中,该特征是有可能被重新捡回来的,另外别的决策树当中也可能会出现那些在另一颗决策树中没有用到的特征。
      随机森林的定义就出来了,利用bagging策略生成一群决策树的过程中,如果我们又满足了样本随机和特征随机,那么构建好的这一批决策树,我们就称为随机森林(Random Forest)。
      实际上,我们也可以使用SVM,逻辑回归等作为分类器,这些分类器组成的总分类器,我们习惯上依旧称为随机森林

    展开全文
  • 决策树决策树生成与剪枝

    万次阅读 多人点赞 2018-07-24 16:37:01
    1. 决策树学习 2. 最优划分属性的选择 2.1 信息增益 - ID3 2.1.1 什么是信息增益 2.1.2 ID3 树中最优划分属性计算举例 2.2 信息增益率 - C4.5 2.3 基尼指数 - CART 3. 决策树剪枝 3.1 决策树的损失...

    (转自个人博客)

    决策树 (Decision tree) 是一种基本的分类与回归方法。它是一个树形结构,对于指定特征空间上的数据点来说,总能顺着决策树的根节点一步步分配到子节点最终到达叶节点,而叶节点表示了该数据点所属的分类。在每一次分配到子节点的过程中可以看作是对数据点中特有的特征属性值进行的 if-then 判断。

    决策树可以认为是 if-then 规则的集合,也可以认为时定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性,分类速度快。如何得到该决策树叫做决策树学习,决策树学习时,利用训练数据,根据损失函数最小化的原则建立决策树模型。预测试,对新的数据,利用决策树模型进行分类。

    接下来按照周志华老师的《机器学习》第 4 章[1] 来梳理一下对决策树的学习:

    1. 决策树学习

    决策树学习的目的是为了生成一颗泛化能力强,即处理未见示例能力强的决策树,其基本流程遵循简单而直观的 分而治之 (Divide and Conquer) 策略,如下图所示:

    Decision_tree_Learning

    决策树的生成是一个自根结点一直到叶结点的递归生成过程。

    在递归生成的伪代码表述中,可以看到,有三个地方导致递归返回:

    1. (行 3) 当前结点包含的样本全部属于同一个类别,无需划分;
    2. (行 6) 当前属性集为空,或是所有样本在所有属性上取值相同,无法划分。在这种情况下,把当前结点标记为叶结点,并且将其类别设定为该结点所含样本最多的类别;
    3. (行 12) 当前结点包含的样本集和为空,不能划分,把当前结点标记为叶结点,但是将其类别设定为其父结点所含样本最多的类别,周志华老师的《机器学习》中在该条件下执行了 return,但是按照我的理解由于这里处于 for 循环中,虽然属性中的一个取值样本集合为空,但是其它取值情况下还有有可能有样本集合的,如果这里执行了 return,那么就跳过了其它取值判断的可能。

    另外,其中第 14 行 A \ { a ∗ } A \backslash \lbrace a_\ast \rbrace A\{a} 表示从 A A A 中去除 a ∗ a_\ast a 属性。

    2. 最优划分属性的选择

    从递归生成伪代码图示中可以看出,(行 8)选择最优划分属性 a ∗ a_\ast a 是最关键的一步。如何选择决定了决策树的效率与准确率。一般而言我们希望选择一个属性 a ∗ a_\ast a 之后,其分支节点所包含的样本尽可能属于同一类别,即结点的 纯度 (Purity) 越来越高。

    根据最优属性 a ∗ a_\ast a 选择方法的不同,决策树大致分为了 ID3 [Quinlan, 1986]、C4.5 [Quinlan, 1993]、CART [Breiman et al., 1984]。

    接下来分别介绍三种方法,在之前,先给出周志华老师《机器学习》中表 4.1 4.1 4.1 中的西瓜数据如下:

    编号色泽根蒂敲声纹理脐部触感好瓜
    1青绿蜷缩浊响清晰凹陷硬滑
    2乌黑蜷缩沉闷清晰凹陷硬滑
    3乌黑蜷缩浊响清晰凹陷硬滑
    4青绿蜷缩沉闷清晰凹陷硬滑
    5浅白蜷缩浊响清晰凹陷硬滑
    6青绿稍蜷浊响清晰稍凹软粘
    7乌黑稍蜷浊响稍糊稍凹软粘
    8乌黑稍蜷浊响清晰稍凹硬滑
    9乌黑稍蜷沉闷稍糊稍凹硬滑
    10青绿硬挺清脆清晰平坦软粘
    11浅白硬挺清脆模糊平坦硬滑
    12浅白蜷缩浊响模糊平坦软粘
    13青绿稍蜷浊响稍糊凹陷硬滑
    14浅白稍蜷沉闷稍糊凹陷硬滑
    15乌黑稍蜷浊响清晰稍凹软粘
    16浅白蜷缩浊响模糊平坦硬滑
    17青绿蜷缩沉闷稍糊稍凹硬滑

    2.1 信息增益 - ID3

    2.1.1 什么是信息增益

    按照周志华老师《机器学习》中第 4.2.1 4.2.1 4.2.1 小节中所述,假定离散属性 a a a V V V 个可能的取值 { a 1 , a 2 , . . . , a V } \lbrace a_1,a_2,...,a_V \rbrace {a1,a2,...,aV},若使用 a a a 来对样本集 D D D 进行划分,会产生 V V V 个分支结点,其中第 v v v 个分支结点包含了 D D D 中所有在属性 a a a 上取值为 a v a_v av 的样本,记为 D v D_v Dv,其对应的信息熵为:

    H ( D v ) = − ∑ k ∈ Y p ( k ∣ v ) log ⁡ p ( k ∣ v ) = − ∑ k ∈ Y ∣ D v k ∣ ∣ D v ∣ log ⁡ ∣ D v k ∣ ∣ D v ∣ H(D_v)=-\sum_{k \in \mathcal{Y}}p(k\mid v)\log p(k \mid v)=-\sum_{k \in \mathcal{Y}}\frac{|D_{vk}|}{|D_v|}\log \frac{|D_{vk}|}{|D_v|} H(Dv)=kYp(kv)logp(kv)=kYDvDvklogDvDvk

    其中 D v k D_{vk} Dvk 表示 D v D_v Dv 中分类为 k k k 的样本。再考虑到不同的分支 v v v 结点所包含的样本数不同,给分支结点赋予权重 ∣ D v ∣ / ∣ D ∣ |D_v|/|D| Dv/D,于是可以计算出属性 a a a 对样本集 D D D 进行划分所获得的 信息增益 (Information gain)

    Gain ( D , a ) = H ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ H ( ∣ D v ∣ ) = H ( D ) − H ( D , a ) = I ( D , a ) \textrm{Gain}(D,a)=H(D)-\sum_{v=1}^V \frac{|D_v|}{|D|}H(|D_v|)=H(D)-H(D,a)=I(D,a) Gain(D,a)=H(D)v=1VDDvH(Dv)=H(D)H(D,a)=I(D,a)

    其实,信息增益就是训练数据集 D D D 中的类别与某一属性之间(或者两个属性之间的,因为最终决策树的目的是要进行分类,所以在决策树的每一个分支判断时都用类别与对应的属性进行信息增益比较)的互信息。我们知道,互信息表示了两事件发生所代表的信息之间的重复部分,当两事件信息重复的部分越大,那么采用一种事件为标准来划分另一种事件所能确定的部分也就越大,也就是说采用属性 a a a 来进行划分所获得的“纯度提升”越大。考虑极端情况,当属性 a a a 与类别完全没有关系时,其互信息为 0 0 0,这时候采用 a a a 属性作为划分标准对于数据集的类别确认完全没有帮助;当属性 a a a 的各属性分别与数据集的类别一一对应时,也就是其概率分布完全相同,那么根据互信息的计算公式,其互信息等于各自的熵,也就是说,如果我们采用 a a a 进行数据的划分,那么数据可以完全干净的划分出来,也就不再含有额外的不可知信息了。

    当决策树中选择最优划分属性(行 8)按照信息增益最大来进行时,决策树属于 ID3 决策树

    2.1.2 ID3 树中最优划分属性计算举例

    根据上节给出的西瓜数据集,我们学习一个对瓜好坏判断的决策树。在这个例子中分类个数为 2 2 2 (是好瓜、不是好瓜),即 Y = 2 \mathcal{Y}=2 Y=2。在决策树学习开始时,根结点包含 D D D 中所有样例,正例占 p 1 = 8 17 p_1=\frac{8}{17} p1=178,反例占 p 2 = 9 17 p_2=\frac{9}{17} p2=179。根结点的信息熵(下面我们都以比特为单位计算)为:

    H ( D ) = − ∑ k = 1 2 p ( k ) log ⁡ 2 p ( k ) = − ( 7 17 log ⁡ 2 7 17 + 9 17 log ⁡ 2 9 17 ) = 0.998 H(D)=-\sum_{k=1}^2p(k)\log_2 p(k)=-\left(\frac{7}{17}\log_2\frac{7}{17}+\frac{9}{17}\log_2\frac{9}{17}\right)=0.998 H(D)=k=12p(k)log2p(k)=(177log2177+179log2179)=0.998

    然后我们要计算出与当前属性集合 {色泽、根蒂、敲声、纹理、脐部、触感}中每个属性的信息增益,也就是对应的互信息。以属性“色泽”为例,它有 3 3 3 个可能取值:{青绿、乌黑、浅白}。以该属性对数据集进行划分,可以得到 3 3 3 个子集,分别为: D 1 D_1 D1(色泽=青绿)、 D 2 D_2 D2(色泽=乌黑)、 D 3 D_3 D3(色泽=浅白)。

    对子集 D 1 D_1 D1 来说,包含了编号为 { 1 , 4 , 6 , 10 , 13 , 17 } \lbrace1,4,6,10,13,17\rbrace {1,4,6,10,13,17} 6 6 6 个样例,其中正例为 { 1 , 4 , 6 } \lbrace1,4,6\rbrace {1,4,6},占 p 1 = 3 6 p_1=\frac{3}{6} p1=63 ;反例为 { 10 , 13 , 17 } \lbrace10,13,17\rbrace {10,13,17},占 p 1 = 3 6 p_1=\frac{3}{6} p1=63。计算其熵为:

    H ( D 1 ) = − ( 3 6 log ⁡ 2 3 6 + 3 6 log ⁡ 2 3 6 ) = 1.000 H(D_1)=-\left(\frac{3}{6}\log_2\frac{3}{6}+\frac{3}{6}\log_2\frac{3}{6}\right)=1.000 H(D1)=(63log263+63log263)=1.000

    依次可以计算另外两个子集的信息熵为:

    H ( D 2 ) = 0.918 H ( D 3 ) = 0.722 \begin{aligned} H(D_2)&=0.918 \\ H(D_3)&=0.722 \end{aligned} H(D2)H(D3)=0.918=0.722

    最终可以计算数据集 D D D 的类别信息在属性“色泽”熵的信息增益(也可以理解为类别与“色泽”属性之间的互信息)为:

    Gain ( D , 色 泽 ) = H ( D ) − ∑ v = 1 3 p ( v ) H ( D v ) = 0.998 − ( 6 17 × 1.000 + 6 17 × 0.918 + 5 17 × 0.722 ) = 0.109 \begin{aligned} \textrm{Gain}(D,色泽) &=H(D)-\sum_{v=1}^3p(v)H(D_v) \\ &=0.998-\left(\frac{6}{17}\times1.000+\frac{6}{17}\times0.918+\frac{5}{17}\times0.722\right) \\ &=0.109 \end{aligned} Gain(D,)=H(D)v=13p(v)H(Dv)=0.998(176×1.000+176×0.918+175×0.722)=0.109

    重复上述的计算步骤,我们可以计算出其他属性的信息增益:

    Gain ( D , 根 蒂 ) = 0.143 ; Gain ( D , 敲 声 ) = 0.141 ; Gain ( D , 纹 理 ) = 0.381 ; Gain ( D , 脐 部 ) = 0.289 ; Gain ( D , 触 感 ) = 0.006. \begin{aligned} \textrm{Gain}(D,根蒂) &=0.143; \\ \textrm{Gain}(D,敲声) &=0.141; \\ \textrm{Gain}(D,纹理) &=0.381; \\ \textrm{Gain}(D,脐部) &=0.289; \\ \textrm{Gain}(D,触感) &=0.006. \\ \end{aligned} Gain(D,)Gain(D,)Gain(D,)Gain(D,)Gain(D,)=0.143;=0.141;=0.381;=0.289;=0.006.

    经过比较,发现采用“纹理”进行划分得到的信息增益最大,于是它被选为划分属性。下图给出了根据“纹理”属性划分之后的数据子集:

    Root_node_decision

    对每一个数据子集按照上边的步骤继续划分下去就能得到最终的决策树(需要注意的是每次样例子集中的属性不包含父结点中划分所依赖的属性),如下图所示:

    Decision-tree

    2.2 信息增益率 - C4.5

    采用信息增益来进行划分属性的决策有一个潜在的问题,当某一个属性的取值种类非常多时,对应每一个属性取值的样本子集,其分类的信息熵可能会变得很小。为了说明,采用一种极端情况,假设我们对上一节中要分类的西瓜数据进行决策树生成时,把“编号”也当作一种可以作为划分依据的属性。则在这种情况下,每一个编号属性对应一个实例,且其分类是确定的,那么对于每一个“编号”属性取值来说,其分类信息熵为 0 0 0,计算“编号”分类所带来的信息增益为:

    Gain ( D , a ) = H ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ H ( ∣ D v ∣ ) = − 8 17 log ⁡ 2 8 17 − 8 17 log ⁡ 2 8 17 − ∑ v = 1 17 1 17 × 0 = 0.9975 \begin{aligned} \textrm{Gain}(D,a)&=H(D)-\sum_{v=1}^V \frac{|D_v|}{|D|}H(|D_v|) \\ &=-\frac{8}{17}\log_2\frac{8}{17}-\frac{8}{17}\log_2\frac{8}{17}-\sum_{v=1}^{17}\frac{1}{17}\times0 \\ &=0.9975 \end{aligned} Gain(D,a)=H(D)v=1VDDvH(Dv)=178log2178178log2178v=117171×0=0.9975

    最后计算出来的信息增益很大。但是显然,用“编号”属性来作为结点的划分是没有意义的。思考其中的问题在于,对数函数并不是线性的,信息量的减少速度大于类别数量的增加速度。信息增益准则对取值数目较多的属性有所偏好,为了减小这种偏好,C4.5 决策树 采用 信息增益率 (gain ratio) 来选择最优划分属性。其定义如下:

    Gain ratio ( D , a ) = G a i n ( D , a ) I V ( a ) {\textrm{Gain}}_\textrm{ratio}(D,a)=\frac{\rm{Gain}(D,a)}{\rm{IV}(a)} Gainratio(D,a)=IV(a)Gain(D,a)

    其中,

    IV ( a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ log ⁡ ∣ D v ∣ ∣ D ∣ = H ( a ) \textrm{IV}(a)=-\sum_{v=1}^V \frac{|D_v|}{|D|}\log \frac{|D_v|}{|D|}=H(a) IV(a)=v=1VDDvlogDDv=H(a)

    到这里,我们就可以发现,信息增益率是用属性分类的信息熵对由属性分类引起的互信息熵进行了归一。属性的种类越多其信息熵通常也会越大。对西瓜数据,有: H ( 触 感 ) = 0.874   ( V = 2 ) H(触感)=0.874\ (V=2) H()=0.874 (V=2) H ( 色 泽 ) = 1.580   ( V = 3 ) H(色泽)=1.580\ (V=3) H()=1.580 (V=3) H ( 编 号 ) = 4.088   ( V = 17 ) H(编号)=4.088\ (V=17) H()=4.088 (V=17)

    最后一点需要注意的是,增益率准则虽然减少了对取值数目较多的属性依赖,但是增加了对取值数目较少的属性偏好。因此, C4.5 并没有直接选择增益率最大的候选划分属性,而是使用了一个启发式:先从候选划分属性中找出 信息增益 高于 平均水平 的属性,再从中选择 增益率 最高的。

    2.3 基尼指数 - CART

    最后介绍一种选择划分属性的依据是使用 基尼指数 (Gini index)。数据集合 D D D 的纯度可用基尼指数来度量:

    Gini ( D ) = ∑ k = 1 ∣ Y ∣ ∑ k ′ ≠ k p k p k ′ = 1 − ∑ k = 1 Y p k 2 \textrm{Gini}(D) = \sum_{k=1}^{|\mathcal{Y}|}\sum_{k^\prime\neq k}p_kp_{k^\prime}=1-\sum_{k=1}^{\mathcal{Y}}p_k^2 Gini(D)=k=1Yk=kpkpk=1k=1Ypk2

    直观来看, Gini ( D ) \textrm{Gini}(D) Gini(D) 反映了从数据集 D D D 中随机抽取两个样本,其类别标记不一致的概率。因此, Gini ( D ) \textrm{Gini}(D) Gini(D) 越小,则数据集 D D D 的纯度越高。

    对特定属性 a a a 的基尼指数定义如下:

    Gain index ( D , a ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ Gini ( D v ) {\textrm{Gain}}_\textrm{index}(D,a) = \sum_{v=1}^{V}\frac{|D_v|}{|D|}\textrm{Gini}(D_v) Gainindex(D,a)=v=1VDDvGini(Dv)

    我们在候选属性集合 A A A 中,选择那个使得划分后基尼指数最小的属性作为最优划分属性,即:

    a ∗ = arg ⁡ min ⁡ a ∈ A Gain index ( D , a ) a_\ast=\arg \min \limits_{a \in A}{{\textrm{Gain}}_\textrm{index}(D,a)} a=argaAminGainindex(D,a)

    采用基尼指数作为划分属性的判据的决策树是一种 CART 决策树。

    3. 决策树剪枝

    3.1 决策树的损失函数

    刚开始我提到,决策树可以看作是一系列 if-then 规则的集合。这个规则集合有一个重要的性质:互斥并且完备。意思就是说,拿来任意一个实例,顺着规则的起点(根结点)出发,最终都有且只有一条路径到达某一个具体的叶结点(具体的分类),并且不会出现实例无法分类的情况。

    如果不考虑泛化能力,在训练集上生成的所有不同规则集合对应的决策树中,挑选出最优的决策树,可以根据所有叶结点中的预测误差来衡量,即模型与训练数据的拟合程度。设树 T T T 的叶结点个数为 ∣ T ∣ |T| T t t t 是树 T T T 的一个叶结点,该叶结点有 N t N_t Nt 个样本点,其中 k k k 类的样本点有 N t k N_{tk} Ntk 个, k = 1 , 2 , . . . , K k=1,2,...,K k=1,2,...,K K K K 为样本空间中的所属分类数量。叶结点 t t t 上的经验熵 H t ( T ) H_t(T) Ht(T)

    H t ( T ) = − ∑ k N t k N t log ⁡ N t k N t H_t(T)=-\sum_k\frac{N_{tk}}{Nt}\log\frac{N_{tk}}{N_t} Ht(T)=kNtNtklogNtNtk

    代表了该叶结点的分类还有多少信息量不知道(混乱程度),可以这么考虑一个理想的极端情况,当该叶结点中只有一个分类 k n k_n kn 时,那么 N t k n = N t N_{tk_n}=N_t Ntkn=Nt,其它的 N k 1 , . . . , N k n − 1 , N k n + 1 , . . . , N k K N_{k_1},...,N_{k_{n-1}},N_{k_{n+1}},...,N_{k_K} Nk1,...,Nkn1,Nkn+1,...,NkK 全部为 0 0 0,最终 H t ( T ) = 0 H_t(T)=0 Ht(T)=0,这个结论与分类已经完全的结果是相吻合的。那么我们可以说,经验熵 H t ( T ) H_t(T) Ht(T) 就代表了连接该叶结点的整个路径对数据分类的彻底性。

    考虑到所有的叶结点每个叶结点中的样例个数不同,我们采用

    C ( T ) = ∑ t = 1 ∣ T ∣ N t H t ( T ) = − ∑ t = 1 ∣ T ∣ ∑ k = 1 K N t k log ⁡ N t k N t C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^K N_{tk}\log\frac{N_{tk}}{N_t} C(T)=t=1TNtHt(T)=t=1Tk=1KNtklogNtNtk

    来衡量模型对训练数据的整体测量误差。

    但是如果仅仅用 C ( T ) C(T) C(T) 来作为优化目标函数,就会导致模型走向过拟合的结果。因为我们可以尽可能的对每一个分支划分到最细结来使得每一个叶结点的 H t ( T ) = 0 H_t(T)=0 Ht(T)=0,最终使得 C ( T ) = 0 C(T)=0 C(T)=0 最小。

    为了避免过拟合,我们需要给优化目标函数增加一个正则项,正则项应该包含模型的复杂度信息。对于决策树来说,其叶结点的数量 ∣ T ∣ |T| T 越多就越复杂,我们用添加正则项的

    C α ( T ) = C ( T ) + α ∣ T ∣ C_\alpha(T)=C(T)+\alpha|T| Cα(T)=C(T)+αT

    来作为优化的目标函数,也就是树的损失函数。参数 α \alpha α 控制了两者之间的影响程度。较大的 α \alpha α 促使选择较简单的模型(树),较小的 α \alpha α 促使选择较复杂的模型(树)。

    决策树的生成过程并不是一个准确的求解树的损失函数的最优化方法。三种决策树学习方法都是一种启发式的求解步骤,在每一步扩大树的规模的时候都是找当前步能使分类结果提升最明显的选择。

    如果以文章最开始标示的三个递归学习返回条件进行树的学习,那么最后学习的树是一个以 C ( T ) C(T) C(T) 为损失函数的最优化过程。最后学习到的决策树对训练数据集能达到令人满意的结果,但是对于未知的测试集来说却未必有很好的分类能力。即数据集的泛化能力不能保证。

    为了提高决策树的泛化能力,需要对树进行 剪枝 (Pruning),把过于细分的叶结点(通常是数据量过少导致噪声数据的影响增加)去掉而回退到其父结点或更高的结点,使其父结点或更高的结点变为叶结点。

    3.2 如何进行决策树剪枝

    决策树的剪枝基本策略有 预剪枝 (Pre-Pruning)后剪枝 (Post-Pruning) [Quinlan, 1933]。根据周志华老师《机器学习》一书中所描述是先对数据集划分成训练集和验证集,训练集用来决定树生成过程中每个结点划分所选择的属性;验证集在预剪枝中用于决定该结点是否有必要依据该属性进行展开,在后剪枝中用于判断该结点是否需要进行剪枝。

    3.2.1 预剪枝

    仿照第 1 小节中的决策树生成流程图,加入预剪枝后的决策树生成流程图如下,

    Decision_tree_Learning_add_Pruning

    其中红色部分是我参考周志华老师《机器学习》第 4.3.1 小节中给出的实例总结的算法流程。其中的核心思想就是,在每一次实际对结点进行进一步划分之前,先采用验证集的数据来验证如果划分是否能提高划分的准确性。如果不能,就把结点标记为叶结点并退出进一步划分;如果可以就继续递归生成节点。

    3.2.2 后剪枝

    对于后剪枝,周志华老师《机器学习》中述说如下:

    后剪枝则是先从训练集生成一颗完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来泛化性能提升,则将该子树替换为叶结点。

    对于后剪枝,书中采用了具体的西瓜分类决策树作为剪枝操作讲解,跟着流程走下来感觉挺顺畅,无非就是对想要进行剪枝的结点进行验证集数据的准确性比较,如果剪枝能带来准确性的提高,那么就剪枝,否则保留。然后去判断其它需要考虑剪枝的结点。

    在进行剪枝判断的操作中,只对底端结点进行判断。一步一步收缩至每一个底端结点对验证集数据都有更好的分类准确率为止。

    更具体地,李航老师《统计学习方法》中第 5.5.2 小节具体介绍了 CART 剪枝算法的步骤流程。刚开始看这部分内容的时候,不容易看懂,后来结合网上的解释回过头来发现其实很简单。下边是参考书中以及网上的解释总结的一套算法流程:

    Decision_tree_Post-Pruning

    针对流程图中的第 8 步计算,按照书中的描述逻辑,对 T 0 T_0 T0 中的任意内部结点 t t t,以 t t t 为单结点树(结点即为叶,没有分支)的损失函数是

    C α ( t ) = C ( t ) + α C_\alpha(t)=C(t)+\alpha Cα(t)=C(t)+α

    t t t 为根结点的子树 T t T_t Tt 的损失函数是

    C α ( T t ) = C ( T t ) + α ∣ T t ∣ C_\alpha(T_t)=C(T_t)+\alpha|T_t| Cα(Tt)=C(Tt)+αTt

    α = 0 \alpha=0 α=0或充分小时,有不等式

    C α ( T t ) < C α ( t ) C_\alpha(T_t)<C_\alpha(t) Cα(Tt)<Cα(t)

    α \alpha α 增大到某一个值时,有

    C α ( T t ) = C α ( t ) C_\alpha(T_t)=C_\alpha(t) Cα(Tt)=Cα(t)

    α \alpha α 再继续增大时,不等式反向,所以只要 α = C ( t ) − C ( T t ) ∣ T t ∣ − 1 \alpha=\frac{C(t)-C(T_t)}{|T_t|-1} α=Tt1C(t)C(Tt) T t T_t Tt t t t 有相同的损失函数值,而 t t t 的结点更少,因此 t t t T t T_t Tt 更可取,对 T t T_t Tt 进行剪枝。

    这个位置容易让人疑惑,逻辑上让人不是很容易想明白,需要多看几遍。其实它的逻辑是这样的:

    剪枝的目的不是为了最小化损失函数,剪枝的目的是为了达到一个更好的泛化能力。而对于决策树来说,叶结点的数量越多,反应了决策树对训练数据的细节反应的越多,继而弱化了泛化能力。要想提高泛化能力就需要进行剪枝,而在 3.1 节中给出的损失函数中, α \alpha α 值衡量了损失函数中叶结点数量的权重, α \alpha α 值越大,在最小化损失函数时,需要更多的考虑叶结点数量的影响。 α \alpha α 可以看作一个系数,不同的 α \alpha α 对应于不同的损失函数。而对于所有的这些损失函数来说,在训练集上进行决策树生成时候的步骤都一样,差别只是在判断某些结点是否进行展开的区别。

    这个有点类似于对一个函数的泰勒级数展开,而 α \alpha α 值控制着展开的次数项,越小的值展开的次数项越多(往回收缩的高次项越少)。因为决策树的结点个数是有限的,对应到 α \alpha α 的值来说也是有限的。上述求 α \alpha α 过程就是得到具体收缩每一个分支对应的值。

    CART 剪枝算法的前半部分递归寻找 α \alpha α 的过程就相当于对一个已经展开到极值的泰勒展开式依次进行收缩,并且找到其对应的系数。最终哪一级的展开泛化能力更好,还是要靠验证集数据来进行验证。展开的太多对训练集符合度好而对验证集不好,展开的太小了偏差又变大了,对训练集和验证集数据符合都不好。所以算法中直到最后才用到了验证集数据,最开始的剪枝判断递归过程都是基于训练数据进行的。

    这里有一个疑惑就是,按照这样的逻辑来获得的 α list \alpha_\textrm{list} αlist 真的满足递增顺序吗?

    借鉴周志华老师《机器学习》中的图 4.5 来对 CART 剪枝算法进行梳理如下。

    Decision_tree_Pruning

    该图展示的是表 4.2 中的西瓜数据集对应的决策树。

    编号色泽根蒂敲声纹理脐部触感好瓜
    1青绿蜷缩浊响清晰凹陷硬滑
    2乌黑蜷缩沉闷清晰凹陷硬滑
    3乌黑蜷缩浊响清晰凹陷硬滑
    6青绿稍蜷浊响清晰稍凹软粘
    7乌黑稍蜷浊响稍糊稍凹软粘
    10青绿硬挺清脆清晰平坦软粘
    14浅白稍蜷沉闷稍糊凹陷硬滑
    15乌黑稍蜷浊响清晰稍凹软粘
    16浅白蜷缩浊响模糊平坦硬滑
    17青绿蜷缩沉闷稍糊稍凹硬滑
    4青绿蜷缩沉闷清晰凹陷硬滑
    5浅白蜷缩浊响清晰凹陷硬滑
    8乌黑稍蜷浊响清晰稍凹硬滑
    9乌黑稍蜷沉闷稍糊稍凹硬滑
    11浅白硬挺清脆模糊平坦硬滑
    12浅白蜷缩浊响模糊平坦软粘
    13青绿稍蜷浊响稍糊凹陷硬滑

    下面按照给出的算法流程来对该决策树进行剪枝操作。我们采用 3.1 小节中关于 C ( T ) C(T) C(T) C α ( T ) C_\alpha(T) Cα(T) 的定义。

    1. 第一层递归: T 0 = { 1 , 2 , 3 , 4 , 5 } T_0=\lbrace 1,2,3,4,5\rbrace T0={1,2,3,4,5},其在训练集数据上的执行情况见下图:
    Decision_tree_Execute
    对其每一个内部结点计算其剪枝后的整体树的损失函数减少程度 g ( t ) g(t) g(t)
    以结点 5 5 5 为例,一例好一例坏,
    C ( 5 ) = − ∑ t = 1 1 ∑ k ∈ ( 好 、 坏 ) N t k log ⁡ 2 N t k N t = − 1 × log ⁡ 2 ( 1 / 2 ) − 1 × log ⁡ 2 ( 1 / 2 ) ) = 2 ; C ( T 5 ) = − ∑ t = 1 3 ∑ k ∈ ( 好 、 坏 ) N t k log ⁡ 2 N t k N t = − ( 1 × log ⁡ 2 ( 1 / 1 ) + 0 × log ⁡ 2 ( 0 / 1 ) ) − ( 0 × log ⁡ 2 ( 0 / 1 ) + 1 × log ⁡ 2 ( 1 / 1 ) ) − 0 = 0 ; ∣ T 5 ∣ = 3 ; g ( 5 ) = C ( 5 ) − C ( T 5 ) ∣ T 5 ∣ − 1 = 2 − 0 3 − 1 = 1. \begin{aligned} C(5)&=-\sum_{t=1}^1\sum_{k \in (好、坏)}N_{tk}\log_2\frac{N_{tk}}{N_t} \\ &=-1\times\log_2(1/2)-1\times\log_2(1/2)) \\ &=2; \\ C(T_5)&=-\sum_{t=1}^3\sum_{k \in (好、坏)}N_{tk}\log_2\frac{N_{tk}}{N_t} \\ &=-\left(1\times\log_2(1/1)+0\times\log_2(0/1)\right)-\left(0\times\log_2(0/1)+1\times\log_2(1/1)\right)-0 \\ &=0; \\ |T_5|&=3; \\ g(5)&=\frac{C(5)-C(T_5)}{|T_5|-1}=\frac{2-0}{3-1}=1. \end{aligned} C(5)C(T5)T5g(5)=t=11k()Ntklog2NtNtk=1×log2(1/2)1×log2(1/2))=2;=t=13k()Ntklog2NtNtk=(1×log2(1/1)+0×log2(0/1))(0×log2(0/1)+1×log2(1/1))0=0;=3;=T51C(5)C(T5)=3120=1.
    同理,可以计算出:
    g ( 4 ) = C ( 4 ) − C ( T 4 ) ∣ T 4 ∣ − 1 = 2.7549 − 0 5 − 1 = 0.6887 g ( 3 ) = C ( 3 ) − C ( T 3 ) ∣ T 3 ∣ − 1 = 4 − 0 7 − 1 = 0.5714 g ( 2 ) = C ( 2 ) − C ( T 2 ) ∣ T 2 ∣ − 1 = 3.2451 − 0 3 − 1 = 1.6226 g ( 1 ) = C ( 1 ) − C ( T 1 ) ∣ T 1 ∣ − 1 = 10 − 0 11 − 1 = 1 \begin{aligned} g(4)&=\frac{C(4)-C(T_4)}{|T_4|-1}=\frac{2.7549-0}{5-1}=0.6887 \\ g(3)&=\frac{C(3)-C(T_3)}{|T_3|-1}=\frac{4-0}{7-1}=0.5714 \\ g(2)&=\frac{C(2)-C(T_2)}{|T_2|-1}=\frac{3.2451-0}{3-1}=1.6226 \\ g(1)&=\frac{C(1)-C(T_1)}{|T_1|-1}=\frac{10-0}{11-1}=1 \end{aligned} g(4)g(3)g(2)g(1)=T41C(4)C(T4)=512.75490=0.6887=T31C(3)C(T3)=7140=0.5714=T21C(2)C(T2)=313.24510=1.6226=T11C(1)C(T1)=111100=1
    比较之后发现,最小的是 g ( 3 ) g(3) g(3),对应的结点是 t ( 3 ) t(3) t(3),对其进行剪枝后得到新的树 T 1 T_1 T1 在训练集数据上的执行情况见下图:
    Decision_tree_Learning_Pruned_1

    2. 第二层递归: 以树 T 1 = { 1 , 2 } T_1=\lbrace 1,2\rbrace T1={1,2} 为新的输入,重复第一层递归中的计算步骤:
    g ( 2 ) = C ( 2 ) − C ( T 2 ) ∣ T 2 ∣ − 1 = 3.2451 − 0 3 − 1 = 1.6226 g ( 1 ) = C ( 1 ) − C ( T 1 ) ∣ T 1 ∣ − 1 = 10 − 0 5 − 1 = 2.5 \begin{aligned} g(2)&=\frac{C(2)-C(T_2)}{|T_2|-1}=\frac{3.2451-0}{3-1}=1.6226 \\ g(1)&=\frac{C(1)-C(T_1)}{|T_1|-1}=\frac{10-0}{5-1}=2.5 \end{aligned} g(2)g(1)=T21C(2)C(T2)=313.24510=1.6226=T11C(1)C(T1)=51100=2.5
    比较之后发现,最小的是 g ( 2 ) g(2) g(2),对应的结点是 t ( 2 ) t(2) t(2),对其进行剪枝后得到新的树 T 2 T_2 T2 在训练集数据上的执行情见下图:
    Decision_tree_Learning_Pruned_2

    3. 第三层递归: 以树 T 2 = { 1 } T_2=\lbrace 1\rbrace T2={1} 为新的输入,重复第一层递归中的计算步骤:
    g ( 1 ) = C ( 1 ) − C ( T 1 ) ∣ T 1 ∣ − 1 = 10 − 0 3 − 1 = 5 g(1)=\frac{C(1)-C(T_1)}{|T_1|-1}=\frac{10-0}{3-1}=5 g(1)=T11C(1)C(T1)=31100=5