机器学习——决策树

• 决策树
• • 信息增益——ID3
  • 信息增益率——C4.5
  • 基尼指数——CART
  • 剪枝
  • • 预剪枝
    • 后剪枝
  • 连续值处理
  • 缺失值处理

决策树

参考博客，决策树的关键就是，如何选择最优化分属性。一般而言，随着划分过程的不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。

信息增益——ID3

“信息熵”是度量样本集合纯度最常用的一种指标。假定当前样本集合 D D D中第 k k k类样本所占的比例为 p k ( k = 1 , 2 , … , ∣ Y ∣ ) p_{k}(k=1,2, \ldots,|\mathcal{Y}|) pk​(k=1,2,…,∣Y∣)，则 D D D的信息熵定义为 Ent ⁡ ( D ) = − ∑ k = 1 ∣ Y ∣ p k log ⁡ 2 p k \operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_{k} \log _{2} p_{k} Ent(D)=−k=1∑∣Y∣​pk​log2​pk​Ent ( D ) (D) (D)的值越小，则 D D D的纯度越高。

假定离散属性 a a a有 V V V个可能的取值 { a 1 , a 2 , ⋅ ⋅ ⋅ , a V } \{a^1, a^2, ···, a^V \} {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。因此可以根据上面信息熵的公式计算出信息熵，再考虑到不同的分支结点所包含的样本数量不同，给分支节点赋予权重 ∣ D v ∣ ∣ D ∣ \frac{|D^v|}{|D|} ∣D∣∣Dv∣​，即样本数越多的分支节点的影响越大，因此能够计算出特征 a a a对样本集 D D D进行划分所获得的“信息增益”：

Gain ⁡ ( D , a ) = Ent ⁡ ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ Ent ⁡ ( D v ) \operatorname { Gain } ( D , a ) = \operatorname { Ent } ( D ) - \sum _ { v = 1 } ^ { V } \frac { \left| D ^ { v } \right| } { | D | } \operatorname { Ent } \left( D ^ { v } \right) Gain(D,a)=Ent(D)−v=1∑V​∣D∣∣Dv∣​Ent(Dv)

信息增益越大，则表示用特征 a a a对数据集划分所获得的“纯度”提升越大。所以信息增益可以用于决策树划分属性的选择，其实就是选择信息增益最大的属性。

但信息增益有个缺点就是对可取数值多的属性有偏好，这样对决策树不具有任何范化能力。

信息增益率——C4.5

为了改善泛化的缺点，使用信息增益率来构造决策树，

Gain ⁡ ratio ⁡ ( D , a ) = Gain ⁡ ( D , a ) IV ⁡ ( a ) \operatorname { Gain } _ { \operatorname { ratio } } ( D , a ) = \frac { \operatorname { Gain } ( D , a ) } { \operatorname { IV } ( a ) } Gainratio​(D,a)=IV(a)Gain(D,a)​ I V ( a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ log ⁡ 2 ∣ D v ∣ ∣ D ∣ \mathrm { IV } ( a ) = - \sum _ { v = 1 } ^ { V } \frac { \left| D ^ { v } \right| } { | D | } \log _ { 2 } \frac { \left| D ^ { v } \right| } { | D | } IV(a)=−v=1∑V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​

但信息增益率也存在缺点，就是对可取数值数目较少的属性有所偏好。因此在选择属性的时候，先从候选划分属性中找出信息增益高于平均水平的属性，在从中选择信息增益率最高的。

基尼指数——CART

基尼值可表示为：

Gini ⁡ ( D ) = ∑ k = 1 K ∑ k ′ ≠ k p k p k ′ = 1 − ∑ k = 1 K p k 2 \operatorname { Gini } ( D ) = \sum _ { k = 1 } ^ { K } \sum _ { k ^ { \prime } \neq k } p _ { k } p _ { k ^ { \prime } } = 1 - \sum _ { k = 1 } ^ { K } p _ { k } ^ { 2 } Gini(D)=k=1∑K​k′​=k∑​pk​pk′​=1−k=1∑K​pk2​

Gini ⁡ ( D ) \operatorname { Gini } ( D ) Gini(D)反应了从数据集 D D D中随机抽取两个样本，其类别标记不一致的概率，因此， Gini ⁡ ( D ) \operatorname { Gini } ( D ) Gini(D)越小，则数据集 D D D的纯度越高。则属性 a a a的基尼指数定义为

G i n i i n d e x ⁡ ( D ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ Gini ⁡ ( D v ) \operatorname { Gini_index } ( D ) = \sum _ { v = 1 } ^ { V } \frac { \left| D ^ { v } \right| } { | D | } \operatorname { Gini } \left( D ^ { v } \right) Ginii​ndex(D)=v=1∑V​∣D∣∣Dv∣​Gini(Dv)

剪枝

剪枝（pruning）的目的是为了避免决策树模型的过拟合。

预剪枝

预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛华性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。

后剪枝

后剪枝就是先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛华性能的提升，则把该子树替换为叶结点。

连续值处理

因为连续属性的可取值数目不再有限，因此不能像前面处理离散属性枚举离散属性取值来对结点进行划分。因此需要连续属性离散化，常用的离散化策略是二分法。

缺失值处理

我们可以在该属性上没有缺失的样本集来计算属性 a a a的信息增益或者其他指标。