机器学习：决策树

• 机器学习：决策树
  • 相关定义
    • 信息
      • 信息量
      • 信息熵
      • 条件熵
    • 信息增益
      • 增益值
      • 增益率
      • Example
    • 基尼
      • 基尼值
      • 基尼指数
      • Eaxmple
  • 算法
    • ID3
    • C4.5
    • CART
  • 剪枝

相关定义

信息

• 非负性：不存在负信息量的事件。
• 单调性：单个事件概率越大，信息量越小。
• 累加性：各独立事件的信息量等于各事件信息量之和。

信息量

$\mathrm{Information}(x) = \log \dfrac{1}{p(x)} = -\log p(x)$

$p(x)$表示某一事件$X$其子情况$x$发生的概率。$p(x)$越大，信息量越小。

信息熵

$\mathrm{Entropy}(X) = -\sum_{x∈X} p(x) ⋅ \log p(x)$

$X$指某一事件，$x$遍历了其所有子情况，$p(x)$指某一子情况发生的概率。该值表达了事件$X$的不确定性，熵越大，不确定性越大。

信息熵亦是度量样本纯度地指标，该值越小，样本纯度越高，即样本中尽可能属于同一类别。

条件熵

$\mathrm{Entropy}(Y ⇐ X) = \mathrm{Entropy}(Y {\ \bold\vert\ } X) \begin{array}{l} \\ \\ = \sum\limits_{x∈X} p(x) ⋅ \mathrm{Entropy}(Y {\ \bold\vert\ } X=x) \\ = -\sum\limits_{x∈X} p(x) \sum\limits_{y∈Y} p(y {\ \bold\vert\ } x) ⋅ \log p(y {\ \bold\vert\ } x) \end{array}$

已知事件$X$的情况下求事件$Y$的不确定性。

信息增益

增益值

$\mathrm{Gain}(D, a) \begin{array}{l} \\ \\ = \mathrm{Entropy}(D) - \mathrm{Entropy}(D {\ \bold\vert\ } a) \\ = \mathrm{Entropy}(D) - \sum\limits_{v=1}^{a.V} \dfrac{|D^v|}{|D|} \mathrm{Entropy}(D^v) \end{array}$

• $D$：数据集
• $a$：某一离散属性
• $a.V$：属性可取的值数量
• $D^v$包含了$D$中所有属性$a$上取值为$a^v$的样本。

信息增益越大，即使用该属性进行划分时，对纯度的提升越大。信息增益准则对可取值数目较多的属性有所偏好。

增益率

$\mathrm{GainRatio}(D, a) = \dfrac{\mathrm{Gain}(D, a)}{\mathrm{IV}(a)}$

• $IV$：属性的固有值（Intrinsic Value）

$IV(a) = -\sum\limits_{v=1}^{a.V} \dfrac{|D^v|}{|D|} \log \dfrac{|D^v|}{|D|}$

增益率准则对可取值数目较少的属性有所偏好。

Example

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

好瓜	坏瓜
8	9

• $\mathrm{Entropy}(D) = -\left( \dfrac{8}{17}\log \dfrac{8}{17} + \dfrac{9}{17}\log \dfrac{9}{17} \right) = 0.998$

计算$\mathrm{Gain}(D, 色泽)$

色泽	数量	好瓜	坏瓜
青绿	6	3	3
乌黑	6	4	2
浅白	5	1	4

• $\mathrm{Entropy}(色泽=青绿) = -\left( \dfrac{3}{6}\log \dfrac{3}{6} + \dfrac{3}{6}\log \dfrac{3}{6} \right) = 1$
• $\mathrm{Entropy}(色泽=乌黑) = -\left( \dfrac{4}{6}\log \dfrac{4}{6} + \dfrac{2}{6}\log \dfrac{2}{6} \right) = 0.918$
• $\mathrm{Entropy}(色泽=浅白) = -\left( \dfrac{1}{5}\log \dfrac{1}{5} + \dfrac{4}{5}\log \dfrac{4}{5} \right) = 0.722$

$\begin{array}{l} \mathrm{Gain}(D, 色泽) \\\\ \\\\ \\\\ \end{array} \begin{array}{l} = \mathrm{Entropy}(D) - \sum\limits_{v=1}^{3} \dfrac{|D^v|}{|D|} \mathrm{Entropy}(D^v) \\\\ = 0.998 - \left( \dfrac{6}{17} × 1 + \dfrac{6}{17} × 0.918 \dfrac{5}{17} × 0.722 \right) \\\\ = 0.109 \end{array}$

基尼

基尼值

$\mathrm{Gini}(D) = \sum_{k=1}^{n} \sum_{k'≠k} p_kp_{k'} = 1 - \sum_{k=1}^{n} {p_k}^2$

• $n$：样本种类数

基尼值反映了从数据集中随机抽取两个样本，其类别标记不一致的概率（不纯性的度量）。基尼值越小，数据集纯度越高。

基尼指数

$\mathrm{GiniIndex}(D, a) = \sum_{v=1}^{a.V} \dfrac{|D^{v}|}{|D|} \mathrm{Gini}(D^v)$

选择基尼指数最小的属性作为最优划分属性。

Eaxmple

Day	Outlook	Temperature	Humidity	Wind	Decision
1	Sunny	Hot	High	Weak	No
2	Sunny	Hot	High	Strong	No
3	Overcast	Hot	High	Weak	Yes
4	Rain	Mild	High	Weak	Yes
5	Rain	Cool	Normal	Weak	Yes
6	Rain	Cool	Normal	Strong	No
7	Overcast	Cool	Normal	Strong	Yes
8	Sunny	Mild	High	Weak	No
9	Sunny	Cool	Normal	Weak	Yes
10	Rain	Mild	Normal	Weak	Yes
11	Sunny	Mild	Normal	Strong	Yes
12	Overcast	Mild	High	Strong	Yes
13	Overcast	Hot	Normal	Weak	Yes
14	Rain	Mild	High	Strong	No

计算$\mathrm{GiniIndex}(Outlook)$

Outlook	Number	Yes	No
Sunny	5	2	3
Overcast	4	4	0
Rain	5	3	2

• $\mathrm{Gini}(Outlook=Sunny) = 1 - (\dfrac{2}{5})^2 - (\dfrac{3}{5})^2 = 0.48$
• $\mathrm{Gini}(Outlook=OverCast) = 1 - (\dfrac{4}{4})^2 - (\dfrac{0}{4})^2 = 0$
• $\mathrm{Gini}(Outlook=Rain) = 1 - (\dfrac{3}{5})^2 - (\dfrac{2}{5})^2 = 0.48$

$\begin{array}{l} \mathrm{GiniIndex}(Outlook) = \\ \\\\ \\\\ \\\\ \\\\ \end{array} \begin{array}{l} \dfrac{5}{14}\mathrm{Gini}(Outlook=Sunny) + \\\\ \dfrac{4}{14}\mathrm{Gini}(Outlook=OverCast) + \\\\ \dfrac{5}{14}\mathrm{Gini}(Outlook=Rain) \\\\ = \dfrac{12}{35} ≈ 0.343 \end{array}$

算法

ID3

每次划分选取信息增益最高的属性为划分标准。

C4.5

先从候选属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

CART

优先选择基尼指数小的属性。

剪枝

避免过拟合的主要手段

• 预剪枝：减少训练测试时间，但有欠拟合风险。
• 后剪枝：泛化性能一般优于预剪枝，但训练开销大。