决策树

交叉熵

$$\displaystyle{ \operatorname{ Ent } \left( D \right) = - \sum _{ k = 1 } ^{ \left|\mathcal{ Y }\right| } p _{ k } \log _{ 2 } p _{ k } }$$

• 最好时某一个类的概率为 1
• 最坏时为均匀分布

$$\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. }$$

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

信息增益

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

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

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

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

graph TB D((D))-->D1((D¹)) D-->D2((D²)) D-->Dv((D^v))

%%{init: {'theme':'dark'}}%% graph TB D((D))-->D1((D¹)) D-->D2((D²)) D-->Dv((D^v))

$$\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) }$$

信息增益越大越好

例

$$\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} }$$ $$\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 最大

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

缺失值处理

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