统计学习方法 决策树

这篇具有很好参考价值的文章主要介绍了统计学习方法 决策树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

统计学习方法 决策树

阅读李航的《统计学习方法》时,关于决策树的笔记。

决策树模型与学习

决策树:树状的模型,其中内部节点表示一个特征或属性,叶子节点表示一个类。使用决策树分类时:

  • 从根结点出发,对实例的某一特征进行测试,根据测试结果分配到某一叶节点中;
  • 重复,直到到达叶子节点;

决策树可以看成是 if-then 规则的集合,也可以看成是对特征空间进行划分的条件概率分布:

统计学习方法 决策树,# ML,决策树,算法,机器学习,人工智能

决策树的学习:给定训练集:
D = {   ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋅ , ( x N , y N )   } D=\set{(x_1,y_1),(x_2,y_2),\cdot,(x_N,y_N)} D={(x1,y1),(x2,y2),,(xN,yN)}
其中 x i = ( x i ( 1 ) , x i ( 2 ) , ⋯   , x i ( n ) ) x_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)}) xi=(xi(1),xi(2),,xi(n)) 为输入实例(特征向量), y i ∈ {   1 , 2 , ⋯   , K   } y_i\in\set{1,2,\cdots,K} yi{1,2,,K} 为类标记。

决策树的学习是从训练数据集中归纳出一组分类规则。但与数据集不相矛盾的决策树往往有很多,在定义好损失函数的情况下,从所有可能的决策树中选取最优的决策树是 NP 完全问题。所以决策树的学习算法通常采用启发式方法,学习到次最优的决策树。

决策树的学习算法通常是对当前训练集,递归地选择某个/些最优特征,并根据特征对训练数据集进行分割。特征选择好和树的深度较深的情况下,在训练集上表现较好,但不一定具有很好的泛化能力,即可能发生过拟合现象。此时我们需要对已生成的树进行从下而上的剪枝。

因此,决策树的学习算法包括:特征选择、决策树的生成和决策树的剪枝过程。

特征选择

我们每一步选择特征,是为了能够将不同类别的实例尽可能分开。特征选择的准则是信息增益和信息增益比。

熵(entropy):表示随机变量不确定性的度量,设 X X X 是一个有限取值个数的离散型随机变量,其概率分布为:
P ( X = x i ) = p i , i = 1 , 2 , ⋯   , n P(X=x_i)=p_i,\quad 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\limits_{i=1}^n p_i\log p_i H(X)=i=1npilogpi

  • 定义 0 log ⁡ 0 = 0 0\log 0=0 0log0=0

  • 对数取 2 2 2 e \text{e} e 为底,此时熵的单位分别成为比特(bit)或纳特(nat);

可以看出熵与 X X X 的取值无关,只与概率分布有关,因此关于 X X X 的熵也可以记作 H ( p ) H(p) H(p)

熵越大,随机变量的不确定性就越大,可以得到:
0 ≤ H ( p ) ≤ log ⁡ n 0\leq H(p) \leq \log n 0H(p)logn
条件熵:两个随机变量 X X X Y Y Y ,条件熵 H ( Y ∣ X ) H(Y|X) H(YX) 表示已知随机变量 X X X 的条件下随机变量 Y Y Y 的不确定性,定义为:
H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) H(Y|X)=\sum\limits_{i=1}^n p_iH(Y|X=x_i) H(YX)=i=1npiH(YX=xi)
当熵和条件熵由数据估计(特别是极大似然估计)得到时,分别被称为经验熵(empirical entropy)和经验条件熵。就是说,我们往往不知道数据的概率分布,而只能从训练集中估计出概率分布(比如以类别所占比例作为该类别出现的概率,即极大似然估计法),所以我们算的熵往往都是经验熵。

信息增益:表示得知特征 X X X 的信息而使得类 Y Y Y 的信息的不确定性减少的程度。定义为:特征 A A A 对训练集 D D D 的信息增益 g ( D , A ) g(D,A) g(D,A) 为:
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) 之差也称为互信息。决策树中信息增益等价于训练数据集中类与特征的互信息。

信息增益的算法:设训练集为 D D D ,样本容量为 ∣ D ∣ |D| D ;假设有 K K K 个类 C k C_k Ck ∣ C k ∣ |C_k| Ck 为属于类 C k C_k Ck 的样本个数。假设特征 A A A n n n 个不同的取值 {   a 1 , a 2 , ⋯   , a n   } \set{a_1,a_2,\cdots,a_n} {a1,a2,,an},将训练集分为 {   D 1 , D 2 , ⋯   , D n   } \set{D_1,D_2,\cdots,D_n} {D1,D2,,Dn} 。记子集 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 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\limits_{k=1}^{K}\frac{|C_k|}{|D|}\log_2{\frac{|C_k|}{|D|}} H(D)=k=1KDCklog2DCk

  1. 计算特征 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 ⁡ ∣ D i k ∣ ∣ D i ∣ H(D|A)=\sum\limits_{i=1}^{n}\frac{|D_i|}{|D|}H(D_i)=-\sum\limits_{i=1}^{n}\frac{|D_i|}{|D|}\sum\limits_{k=1}^{K}\frac{|D_{ik}|}{|D_{i}|}\log{\frac{|D_{ik}|}{|D_{i}|}} H(DA)=i=1nDDiH(Di)=i=1nDDik=1KDiDiklogDiDik

  1. 计算信息增益:

g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A)=H(D)-H(D|A) g(D,A)=H(D)H(DA)

信息增益比:定义为信息增益 g ( D , A ) g(D,A) g(D,A) 与训练数据集 D D D 关于特征 A A 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 ∣ log ⁡ 2 ∣ D i ∣ ∣ D ∣ H_A(D)=-\sum\limits_{i=1}^{n}\frac{|D_i|}{|D|}\log_2{\frac{|D_i|}{|D|}} HA(D)=i=1nDDilog2DDi
以信息增益作为划分训练集的特征,会存在一个问题:偏向于选择取值较多的特征,因为这样算出来的 H ( D ∣ A ) H(D|A) H(DA) 往往更小。所以可以使用信息增益比进行矫正。

决策树的生成

ID3 算法

输入:训练集 D D D ,特征集 A A A 和阈值 ε \varepsilon ε

输出:决策树 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 g A_g Ag
    1. g ( D , A g ) < ε g(D,A_g)\lt \varepsilon g(D,Ag)<ε ,则不再分支,将 T T T 置为单节点树,并将 D D D 中实例数最多的类 C k C_k Ck 作为该节点的类标记,返回 T T T
    2. 否则,依据 A g A_g Ag 的各个取值,将 D D D 分割为若干子集 D i D_i Di (丢弃非空子集),递归地以 A − {   A g   } A-\set{A_g} A{Ag} 为特征集构建子节点;

C4.5 的生成算法

与 ID3 基本类似,但是使用信息增益比来选择 A g A_g Ag

决策树的剪枝

为了提高模型的泛化能力,我们需要对生成的决策树进行剪枝。剪枝往往通过极小化决策树整体的损失函数来实现,这里介绍一个简单的剪枝算法。

损失函数:设 T T T 的叶子节点个数为 ∣ T ∣ |T| T,第 t t t 个叶子节点的样本数为 N t N_{t} Nt ,该叶子节点中属于类别 C k C_k Ck 的样本数为 N t k N_{tk} Ntk H t ( T ) H_t(T) Ht(T) 为节点 t t t 上的经验熵, α ≥ 0 \alpha \geq 0 α0 为参数。则决策树学习的损失函数可以定义为:
C α ( T ) = ∑ t = 1 ∣ T ∣ N t H t ( T ) + α ∣ T ∣ C_{\alpha}(T)=\sum\limits_{t=1}^{|T|}N_tH_t(T)+\alpha|T| Cα(T)=t=1TNtHt(T)+αT

其中经验熵为:
H t ( T ) = − ∑ k ∣ N t k ∣ ∣ N t ∣ log ⁡ ∣ N t k ∣ ∣ N t ∣ H_t(T)=-\sum\limits_{k}\frac{|N_{tk}|}{|N_{t}|}\log \frac{|N_{tk}|}{|N_{t}|} Ht(T)=kNtNtklogNtNtk
则右边第一项展开为:
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\limits_{t=1}^{|T|}N_tH_t(T)=-\sum\limits_{t=1}^{|T|}\sum\limits_{k=1}^{K}N_{tk}\log \frac{N_{tk}}{N_{t}} C(T)=t=1TNtHt(T)=t=1Tk=1KNtklogNtNtk
此时:
C α ( T ) = C ( T ) + α ∣ T ∣ C_{\alpha}(T)=C(T)+\alpha|T| Cα(T)=C(T)+αT
α \alpha α 类似于正则化系数。

树的剪枝算法:目标为最小化损失函数

  • 输入:生成算法产生的整个树 T T T ,参数 α \alpha α
  • 输出:修建后的子树 T α T_\alpha Tα
  1. 计算每个节点的经验熵;(对于内部节点,则以它所有后续节点的所有样本实例来计算经验熵)
  2. 递归地从树的叶节点向上回缩:设对于某一个叶子节点的父节点,将其子节点回缩;回缩之前与之整体树分别为 T B T_B TB T A T_A TA ,若:

C α ( T A ) ≤ C α ( T B ) C_\alpha(T_A)\leq C_\alpha(T_B) Cα(TA)Cα(TB)

则进行剪枝;

  1. 重复,直到无法继续减少损失函数为止;

统计学习方法 决策树,# ML,决策树,算法,机器学习,人工智能

注意

  • 由于损失函数使用的是叶子节点的个数 ∣ T ∣ |T| T ,因此损失函数的计算可以在局部进行;
  • 对于二叉决策树而言,每剪枝一次,叶子节点就减少一个(因为原来的父节点变成了叶子节点),此时 α \alpha α 就代表判断是否剪枝的阈值。若增加的经验熵大于 α \alpha α ,则不进行剪枝。 α \alpha α 越大,则树越小; α \alpha α 越小,则树越大;

CART 算法

CART 全称为分类与回归树(classification and regression tree),由特征选择、树的生成及剪枝组成。CART 假设决策树为二叉树,内部节点的特征取值为 ”是“ 或 ”否“。

CART 回归树的生成

回归树的生成思路:此时输出变量 Y Y Y 是连续变量,而输入变量 X X X 的各个维度往往也是连续变量。可以把回归树想象成对输入空间(特征空间)不断划分,假设已经划分为 M M M 个单元 R 1 ,   R 2 ,   ⋯   ,   R M R_1,\,R_2,\,\cdots,\,R_M R1,R2,,RM (其实就是对应 M M M 个叶子节点) ,并且每一个划分单元 R m R_m Rm 上有一个固定的输出值 c m c_m cm 。则对于某一实例 x x x ,其所属的划分单元的输出值就是回归树的预测值,表示为:
f ( x ) = ∑ m = 1 M c m I ( x ∈ R m ) f(x)=\sum\limits_{m=1}^{M}c_mI(x\in R_m) f(x)=m=1McmI(xRm)
在某一个划分单元内,我们使用平方误差 L ( R m ) = ∑ x i ∈ R m ( y i − f ( x i ) ) 2 L(R_m)=\sum\limits_{x_i\in R_m}(y_i-f(x_i))^2 L(Rm)=xiRm(yif(xi))2 作为损失函数,已知此时输出值 c m c_m cm 的最优值为划分单元内每个实例对应输出值的平均值:
c ^ m = 1 ∣ R m ∣ ∑ x i ∈ R m y i \hat c_m=\frac{1}{|R_m|}\sum\limits_{x_i\in R_m}y_i c^m=Rm1xiRmyi
对于如何划分,采用启发式的方法。选择第 j j j 个变量 x ( j ) x^{(j)} x(j) (即第 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)=\set{x|x^{(j)}\leq s} \quad\text{和}\quad R_2(j,\,s)=\set{x|x^{(j)}\gt s} R1(j,s)={xx(j)s}R2(j,s)={xx(j)>s}
我们的目标是选择最优切分变量 j j j 和最优切分点 s s s ,即求解:
min ⁡ j , s [ min ⁡ c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + min ⁡ c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] \min_{j,s}\left[ \min_{c_1} \sum\limits_{x_i\in R_1(j,s)}(y_i-c_1)^2 + \min_{c_2} \sum\limits_{x_i\in R_2(j,s)}(y_i-c_2)^2 \right] j,smin c1minxiR1(j,s)(yic1)2+c2minxiR2(j,s)(yic2)2
显然 c 1 c_1 c1 c 2 c_2 c2 的选择也是区域内的平均值;我们遍历每个 j j j ,找到最优切分点 s j s_j sj ,选出所有切分变量中平方误差最小的一个 ( j ,   s j ) (j,\,s_j) (j,sj) 。这样的回归树通常称为 最小二乘回归树

最小二乘回归树生成算法

  • 输入:训练集 D D D ,停止计算的条件;
  • 输出:回归树 f ( x ) f(x) f(x)
  1. 选择最优切分变量 j j j 与切分点 s s s ,求解:

min ⁡ j , s [ min ⁡ c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + min ⁡ c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] \min_{j,s}\left[ \min_{c_1} \sum\limits_{x_i\in R_1(j,s)}(y_i-c_1)^2 + \min_{c_2} \sum\limits_{x_i\in R_2(j,s)}(y_i-c_2)^2 \right] j,smin c1minxiR1(j,s)(yic1)2+c2minxiR2(j,s)(yic2)2

  1. 用选定的对 ( j , s ) (j,s) (j,s) 划分区域并决定相应的输出值:

R 1 ( j ,   s ) = {   x ∣ x ( j ) ≤ s   } , R 2 ( j ,   s ) = {   x ∣ x ( j ) > s   } c ^ m = 1 ∣ R m ∣ ∑ x i ∈ R m ( j , s ) y i , x ∈ R m , m = 1 , 2 \begin{aligned} R_1(j,\,s)=\set{x|x^{(j)}\leq s},\quad R_2(j,\,s)=\set{x|x^{(j)}\gt s} \\ \hat c_m=\frac{1}{|R_m|}\sum\limits_{x_i\in R_m(j,s)}y_i,\quad x\in R_m,\quad m=1,2 \end{aligned} R1(j,s)={xx(j)s},R2(j,s)={xx(j)>s}c^m=Rm1xiRm(j,s)yi,xRm,m=1,2

  1. 递归对两个子区域生成决策树,直到满足停止条件:达到最小样本数、最大深度、最小损失减少、没有特征等;
  2. 将输入空间划分为 M M M 个单元 R 1 ,   R 2 ,   ⋯   ,   R M R_1,\,R_2,\,\cdots,\,R_M R1,R2,,RM ,得到决策树:

f ( x ) = ∑ m = 1 M c m I ( x ∈ R m ) f(x)=\sum\limits_{m=1}^{M}c_mI(x\in R_m) f(x)=m=1McmI(xRm)

CART 分类树的生成

基尼指数:也成为基尼不纯度,分类问题中,假设有 K K K 个类,样本属于第 k k k 类的概率为 p k p_k pk ,则概率分布的基尼指数定义为:
Gini ( p ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 \text{Gini}(p)=\sum\limits_{k=1}^{K}p_k(1-p_k)=1-\sum\limits_{k=1}^{K}p_k^2 Gini(p)=k=1Kpk(1pk)=1k=1Kpk2
基尼指数可以理解为,从样本集中随机选取两个样本,其不属于同一类的概率。

给定样本集合 D D D ,其基尼指数(应该叫经验基尼指数?)为:
Gini ( D ) = 1 − ∑ k = 1 K ( ∣ C k ∣ ∣ D ∣ ) 2 \text{Gini}(D)=1-\sum\limits_{k=1}^{K}\left( \frac{|C_k|}{|D|} \right)^2 Gini(D)=1k=1K(DCk)2
在特征 A A A 和其某一划分条件的条件下,集合 D D D 的基尼指数(应该叫经验条件基尼指数?)为:
Gini ( D ,   A ) = ∣ D 1 ∣ ∣ D ∣ Gini ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ Gini ( D 2 ) \text{Gini}(D,\,A)=\frac{|D_1|}{|D|}\text{Gini}(D_1)+\frac{|D_2|}{|D|}\text{Gini}(D_2) Gini(D,A)=DD1Gini(D1)+DD2Gini(D2)
在二分类问题中,基尼指数、熵(以 2 为底)的一半 H ( p ) 2 \frac{H(p)}{2} 2H(p) 和分类误差率的关系为:

统计学习方法 决策树,# ML,决策树,算法,机器学习,人工智能

CART 分类树使用基尼指数选择最优特征:

  • 基尼指数计算更快,不涉及对数计算;
  • 熵对于不平衡程度更敏感,分布相对平衡的数据集使用熵会更合适;

CART分类树生成算法

  • 输入:训练集 D D D ,停止计算的条件;
  • 输出:决策树 f ( x ) f(x) f(x)
  1. 遍历每个特征 A A A 和可能的取值 a a a ,以 A = a A=a A=a 作为划分条件计算划分后的基尼指数。选择得到最小的基尼指数的 ( A ,   a ) (A,\,a) (A,a) 作为最优特征和最优切分点;
  2. 依据 ( A ,   a ) (A,\,a) (A,a) D D D 划分为两个子集,并对两个子集递归划分,直到满足停止条件;
  3. 叶子节点中,使用多数表决法决定其类,生成 CART 决策树;

注意:CART 树生成过程中,一般来说某个特征被某个节点使用过后,该节点的后续节点的划分将不再使用该特征,这个特性有助于确保决策树的多样性和不过度拟合。但并不是说一个特征只能使用一次,而是一条从上到下的路径只能出现一次。但是该做法可能导致某些情况下的不充分利用特征。

CART 剪枝

CART 剪枝算法包含两个步骤:

  • 从”完全生长“的决策树 T 0 T_0 T0 的底端开始不断剪枝,直到根节点,一次得到一个子树序列 {   T 0 , T 1 , ⋯   , T n   } \set{T_0,T_1,\cdots,T_n} {T0,T1,,Tn}
  • 在独立的验证集上交叉验证子树序列,从中选择最优子树;

剪枝过程:定义损失函数为( C ( T ) C(T) C(T) 可以是基尼指数):
C α ( T ) = C ( T ) + α ∣ T ∣ C_\alpha(T)=C(T)+\alpha|T| Cα(T)=C(T)+αT
前面说过, α \alpha α 类似于一个阈值,控制着决策树的剪枝程度。我们可以采用递归的方法对树进行剪枝,将 α \alpha α 逐渐增大,得到一系列子树 {   T 0 , T 1 , ⋯   , T n   } \set{T_0,T_1,\cdots,T_n} {T0,T1,,Tn}

对于 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
α \alpha α 大时,选择 t t t 较好(损失更小); α \alpha α 小时,选择保留 T t T_t Tt 较好;阈值为:
α = C ( t ) − C ( T t ) ∣ T t ∣ − 1 \alpha=\frac{C(t)-C(T_t)}{|T_t|-1} α=Tt1C(t)C(Tt)
CART 剪枝算法

  • 输入:CART 算法生成的决策树 T 0 T_0 T0
  • 输出:最优决策树 T α T_\alpha Tα
  1. 初始化 k = 0 k=0 k=0 ,当前树为 T = T 0 T=T_0 T=T0

  2. α = + ∞ \alpha=+\infty α=+

  3. 自下而上地对各个内部节点 t t t 计算:

g ( t ) = C ( t ) − C ( T t ) ∣ T t ∣ − 1 , α = min ⁡ ( α , g ( t ) ) g(t)=\frac{C(t)-C(T_t)}{|T_t|-1},\quad \alpha=\min(\alpha,g(t)) g(t)=Tt1C(t)C(Tt),α=min(α,g(t))

  1. 对于 g ( t ) = α g(t)=\alpha g(t)=α 的内部节点 t t t 进行剪枝,得到新的树 T T T

  2. 更新 k = k + 1 k=k+1 k=k+1 ,记录 T k = T T_k=T Tk=T α k = α \alpha_k=\alpha αk=α ;(注意这里更新完 k k k 以后才记录)

  3. T k T_{k} Tk 不是根节点或者只有两个子节点,则回到步骤 2,否则停止算法;

  4. 采用交叉验证法从 {   T 0 , T 1 , ⋯   , T n   } \set{T_0,T_1,\cdots,T_n} {T0,T1,,Tn} 中选取最优子树 T α T_\alpha Tα

注意:每次都选择最小的 α \alpha α ,相当于尽可能保留树的节点,所以 {   T 0 , T 1 , ⋯   , T n   } \set{T_0,T_1,\cdots,T_n} {T0,T1,,Tn} 集合中树是逐渐变小的, α k \alpha_k αk 是逐渐变大的;

我有一个问题,某个内部节点的 α \alpha α 有没有可能比其后续节点的 α \alpha α 要小?就是有没有可能出现先剪了父节点,后剪了子节点的情况?

我们考虑某一个内部节点 t t t,其对应的数据集为 D D D ;它的两个子节点 t 1 t_1 t1 t 2 t_2 t2 将数据集分为 D 1 D_1 D1 D 2 D_2 D2 两部分,则:
g ( t ) =   C ( t ) − C ( T t ) ∣ T t ∣ − 1 =   ( 1 − ∑ k = 1 K ( C k D ) 2 ) − D 1 D ( 1 − ∑ k = 1 K ( C k 1 D 1 ) 2 ) − D 2 D ( 1 − ∑ k = 1 K ( C k 2 D 2 ) 2 ) ∣ T t ∣ − 1 =   D 1 D ∑ k = 1 K ( C k 1 D 1 ) 2 + D 2 D ∑ k = 1 K ( C k 2 D 2 ) 2 − ∑ k = 1 K ( C k D ) 2 ∣ T t ∣ − 1 \begin{aligned} g(t) =&\, \frac{C(t)-C(T_t)}{|T_t|-1} \\ =&\, \frac{\left(1-\sum\limits_{k=1}^{K}\left(\frac{C_k}{D}\right)^2\right) -\frac{D_1}{D}\left(1-\sum\limits_{k=1}^{K}\left(\frac{C_{k1}}{D_1}\right)^2\right) -\frac{D_2}{D}\left(1-\sum\limits_{k=1}^{K}\left(\frac{C_{k2}}{D_2}\right)^2\right) }{|T_t|-1} \\ =&\ \frac{ \frac{D_1}{D}\sum\limits_{k=1}^{K}\left(\frac{C_{k1}}{D_1}\right)^2 +\frac{D_2}{D}\sum\limits_{k=1}^{K}\left(\frac{C_{k2}}{D_2}\right)^2 -\sum\limits_{k=1}^{K}\left(\frac{C_{k}}{D}\right)^2 }{|T_t|-1} \end{aligned} g(t)===Tt1C(t)C(Tt)Tt1(1k=1K(DCk)2)DD1(1k=1K(D1Ck1)2)DD2(1k=1K(D2Ck2)2) Tt1DD1k=1K(D1Ck1)2+DD2k=1K(D2Ck2)2k=1K(DCk)2
这个值跟好多因素有关。。。感觉没法确定;但我认为父节点的 α \alpha α 应当是更大的。文章来源地址https://www.toymoban.com/news/detail-734658.html

到了这里,关于统计学习方法 决策树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包