《机器学习》周志华-CH4（决策树）
4.1基本流程
决策树是一类常见的机器学习方法，又称“判别树”，决策过程最终结论对应了我们所希望的判定结果。
一棵决策树 { 一个根结点 包含样本全集 若干个内部结点 对应属性测试，每个结点包含的样本集合根据属性测试结果划分到子结点中 若干个叶结点 对应决策结果 一棵决策树 \begin{cases} 一个根结点 &包含样本全集 \\ 若干个内部结点 & 对应属性测试，每个结点包含的样本集合根据属性测试结果划分到子结点中 \\ 若干个叶结点 & 对应决策结果 \\ \end{cases} 一棵决策树⎩ ⎨ ⎧一个根结点若干个内部结点若干个叶结点包含样本全集对应属性测试，每个结点包含的样本集合根据属性测试结果划分到子结点中对应决策结果
决策树的生成是一个递归过程
有三种情况会递归返回
4.2划分选择
关键在于如何选择最优划分属性
我们希望决策树分支结点所包含的样本尽可能属同一类别，即“纯度”（purity）越来越高
4.2.1信息增益
“信息熵”（information entropy）是度量样本纯度的一种指标
学习一棵能预测是不是好瓜的决策树。 ∣ y ∣ = 2 |y|=2 ∣y∣=2
数据集一共17个西瓜，正例8个，反例9个。则 P 1 = 8 17 P_{1}=\frac{8}{17} P1=178, P 2 = 9 17 P_{2}=\frac{9}{17} P2=179
计算当前属性集合{色泽，根蒂，瞧声，纹理，脐部，触感}每个属性信息增益。
同理其他信息增益
{
G
a
i
n
(
D
,
根蒂
)
=
0.143
G
a
i
n
(
D
,
敲声
)
=
0.141
G
a
i
n
(
D
,
纹理
)
=
0.381
最大，选为划分属性
G
a
i
n
(
D
,
脐部
)
=
0.289
G
a
i
n
(
D
,
触感
)
=
0.006
同理其他信息增益 \begin{cases} Gain(D,根蒂)=0.143 &\\ Gain(D,敲声)=0.141 & \\ Gain(D,纹理)=0.381 & 最大，选为划分属性 \\ Gain(D,脐部)=0.289 & \\ Gain(D,触感)=0.006 & \\ \end{cases}
同理其他信息增益⎩
⎨
⎧Gain(D,根蒂)=0.143Gain(D,敲声)=0.141Gain(D,纹理)=0.381Gain(D,脐部)=0.289Gain(D,触感)=0.006最大，选为划分属性
4.2.2增益率
信息增益准则对可取值数目较多的属性有所偏好
C 4.5 C_{4.5} C4.5决策树算法不直接使用信息增益，而是使用“增益率”（gain ratio）
增益率准则对可取值数目较少的属性有所偏好。
C 4.5 C_{4.5} C4.5并不是直接使用增益率：先找信息增益高于平均水平的，再选择增益率最高。
4.2.3基尼参数
CART决策树使用“基尼指数”选择划分属性
4.3剪枝处理
剪枝(pruning)是用来解决“过拟合”，比如分支过多，把训练集自身的一些特点当作所有数据的一般性质。
4.3.1预剪枝
4.4连续与缺失值
4.4.1连续值处理
由于连续属性的可取值数目不再有限，连续属性离散化技术可派上用场。比如二分法(bipartition-)对连续属性进行处理( C 4.5 C_{4.5} C4.5决策树机制)
给定样本集 D D D，连续属性 a a a
假定
a
a
a在
D
D
D上出现了
n
n
n个不同值，从小到大排序
4.4.2缺失值处理
比如一些缺失属性值进行训练样例
(1)如何在属性缺失的情况下进行划分属性选择？
(2)给定划分属性，若该属性上的值缺失，如何对样本进行划分？
举例，数据集看之前
C
4.5
算法策略如上页一样的解决方案
C_{4.5}算法策略如上页一样的解决方案
C4.5算法策略如上页一样的解决方案
D D D一共有17个样例{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17},各样例权值均为1
以属性“色泽”为例，属性上无缺失值的样例子集
4.5多变量决策树
若我们把每个属性视为坐标空间中的一个坐标轴，则
d
d
d个属性描述的样本就对应了
d
d
d维空间中的一个数据点寻找，寻找不同样本的分类边界。
决策树形成的分类边界特点：轴平行(axis-parallel),分类边界由若干个与坐标轴平行的分段组成
