Skip to content

决策树

交叉熵

Ent(D)=k=1Ypklog2pk\displaystyle{ \operatorname{ Ent } \left( D \right) = - \sum _{ k = 1 } ^{ \left|\mathcal{ Y }\right| } p _{ k } \log _{ 2 } p _{ k } }
  • 最好时某一个类的概率为 1
  • 最坏时为均匀分布
Ent(D)={0p1=1log2Yp1==pY=1Y\displaystyle{ \operatorname{ Ent } \left( D \right) = \left\lbrace \begin{array}{ll} 0 & p _{ 1 } = 1 \\ \log _{ 2 } \left|\mathcal{ Y }\right| & p _{ 1 } = \ldots = p _{ \left|\mathcal{ Y }\right| } = \frac{ 1 }{ \left|\mathcal{ Y }\right| } \end{array} \right. }

Ent(D)\displaystyle{ \operatorname{ Ent } \left( D \right) } 越小,划分的越清晰,纯度越高

信息增益

相当于 Δ\displaystyle{ \Delta },描述了划分和不划分之间的变化

划分之前,信息熵为 Ent(D)\displaystyle{ \operatorname{ Ent } \left( D \right) },划分后,信息熵为 v=1VDvDEnt(Dv)\displaystyle{ \sum _{ v = 1 } ^{ V } \frac{ \left|D ^{ v }\right| }{ \left|D\right| } \operatorname{ Ent } \left( D ^{ v } \right) }

信息增益越大,纯度提升越大

每个分类占了 Dv\displaystyle{ D ^{ v } } 的权重,因此要对每个交叉熵乘一个 DvD\displaystyle{ \frac{ \left|D ^{ v }\right| }{ \left|D\right| } }

graph TB D((D))-->D1((D1)) D-->D2((D2)) D-->Dv((Dv))
%%{init: {'theme':'dark'}}%% graph TB D((D))-->D1((D1)) D-->D2((D2)) D-->Dv((Dv))
Gain(A,a)=Ent(D)v=1VDvDEnt(Dv)\displaystyle{ \operatorname{ Gain } \left( A , a \right) = \operatorname{ Ent } \left( D \right) - \sum _{ v = 1 } ^{ V } \frac{ \left|D ^{ v }\right| }{ \left|D\right| } \operatorname{ Ent } \left( D ^{ v } \right) }

信息增益越大越好

Ent(D)=k=1Ypklog2pk=(817log2817+917log2917)=0.998\displaystyle{ \begin{aligned}\operatorname{ Ent } \left( D \right) & = - \sum _{ k = 1 } ^{ \left|\mathcal{ Y }\right| } p _{ k } \log _{ 2 } p _{ k } \\ & = - \left( \frac{ 8 }{ 17 } \log _{ 2 } \frac{ 8 }{ 17 } + \frac{ 9 }{ 17 } \log _{ 2 } \frac{ 9 }{ 17 } \right) = 0.998\end{aligned} } Ent(D)=617(36log236+36log236)617(46log246+26log226)517(15log215+45log245)\displaystyle{ \begin{aligned}\operatorname{ Ent } ^{\prime} \left( D \right) & = - \frac{ 6 }{ 17 } \left( \frac{ 3 }{ 6 } \log _{ 2 } \frac{ 3 }{ 6 } + \frac{ 3 }{ 6 } \log _{ 2 } \frac{ 3 }{ 6 } \right) \\ & - \frac{ 6 }{ 17 } \left( \frac{ 4 }{ 6 } \log _{ 2 } \frac{ 4 }{ 6 } + \frac{ 2 }{ 6 } \log _{ 2 } \frac{ 2 }{ 6 } \right) \\ & - \frac{ 5 }{ 17 } \left( \frac{ 1 }{ 5 } \log _{ 2 } \frac{ 1 }{ 5 } + \frac{ 4 }{ 5 } \log _{ 2 } \frac{ 4 }{ 5 } \right)\end{aligned} }

增益率

剪枝处理

  • 预剪枝(生成过程中评估和剪枝)
  • 后剪枝(用所有数据生成,尽管可能过拟合,之后再剪枝)

凹陷 (1, 2, 3), 14 稍凹 (6, 7), 15, 17 平坦 10, 16

连续值在决策树中的处理

  • 按门限值划分 - 将连续值转化为分类问题
  1. 离散化 - 门限 - 利用 max 找到门限
  2. 找哪个使得 Gain 最大

连续属性可以不断划分,离散值重复划分是无效的

缺失值处理

  • 无缺失值 a\displaystyle{ a } 属性样本子集 D~D\displaystyle{ \tilde{ D } \subseteq D }
  • 属性值为 av\displaystyle{ a ^{ v } } 样本子集 D~v\displaystyle{ \tilde{ D } ^{ v } }
  • 标签为 k\displaystyle{ k } 的样本子集 D~k\displaystyle{ \tilde{ D } ^{ k } }