【西瓜书】决策树

决策树

决策树（decision tree）是一种常见的机器学习方法，也叫“判定树”。
- 根据上下文，决策树有时候是指学习方法，有时候是指学得的树。
决策树是根据树形结构来进行决策的，这与人类在面临决策问题时的处理机制非常一致。在进行决策时，通常会进行一系列的判断或者决策，最后得出最终决策。
决策过程的最终结论，就是期望的判定结果。
决策过程中提出的每个判定问题，都是对某个属性的测试。
每个测试的结果，或是导出最终结论，或是导出进一步的判定问题。其考虑范围是在上次决策结果的限定范围之内。
一般来说，一颗决策树包含一个根节点，若干个内部节点和若干个叶节点。
- 叶节点对应于决策结果。
- 其他每个节点则对应于一个属性测试。
- 每个节点包含的样本集合根据属性测试的结果被划分到子节点中。
- 根节点包含样本全集。
- 从根节点到每个叶节点的路径对应一个判定测试序列。
决策树学习的目的是为了产生一棵泛化能力强——处理未见适应能力强的决策树。
决策树的基本流程遵循简单且直观的“分而制之”（divide and conquer）策略。
决策树的生成是一个递归过程。有三种情况会导致递归返回：
1. 当前节点包含的样本全是同一类别，无需划分。
2. 当前属性集为空，或者所有样本在所有属性上取值相同，无法划分。
3. 当前节点包含的样本集合为空，不能划分。
4. 注意：第2种、第3种情况，都把当前节点标记为叶节点。
5. 第2种情况，将当前节点的类别设定为该节点所含样本最多的类别。利用当前节点的后验分布。
6. 第3种情况，将当前节点的类别设定为其父节点所含样本最多的类别。把父节点的样本分布作为当前节点的先验分布。
决策树的关键是如何选择最优划分属性，这就是划分选择。
一般而言，随着划分过程不断进行，希望决策树的分支节点所包含的样本尽可能属于同一类别，即为节点的“纯度”（purity）越来越高。

划分选择

ID3与信息增益

“信息熵”（Information entropy）是度量样本集合纯度最常用的指标。
假设当前样本集合D中第k类样本所占的比例为pk，则D的信息商定义为 $Ent(D) = -\sum_{k=1}^{|y|}p_klog_2p_k$ Ent(D)的值越小，则D的纯度越高。其中 $p_k$ 表示集合D中第k类样本所占的比例。
一般而言，“信息增益”（information gain）越大，则意味着使用属性a来进行划分所获得的纯度提升越大。因此可以用信息增益来进行决策树的划分属性选择。信息增益的定义如下： $Gain(D,a) = Ent(D)-\sum_{v=1}^V\frac{|D^{v}|}{D}Ent(D^{v})$
其中，D^v表示第v个分支节点包含了D中所有在属性a上取值为a^v的样本。
著名的 ID3 决策树学习算法是以信息增益为准则来划分属性。 ID3 中的 ID 是 Iterative Dichotomiser（迭代二分器）的简称。
信息增益对可取值数目较多的属性有所偏好。

C4.5与增益率

为减少这种信息增益的偏好可能带来的不利影响，著名的 C4.5 决策树算法不直接使用信息增益而使用“增益率”（gain ratio）来选择最优划分属性。定义如下： $Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$
其中 $IV(a) = -\sum\limits_{v=1}^V\frac{D^v}{D}log_2\frac{D^v}{D}$ ，称为属性a的“固有值”（intrinsic value）。
增益率准则对可取值数目较少的属性有所偏好。
C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

CART与基尼指数

CART（Classification and regression tree) 决策树使用“基尼指数”（Gini index）来选择划分属性。 CART是一种著名的决策树学习算法，分类和回归任务都可用。
基尼值得定义如下： $Gini(D)=1-\sum\limits_{k=1}^{|y|}{p_k}^2$
基尼指数的定义如下： $Gini\_index(D,a)=\sum\limits_{v=1}^V\frac{D^v}{D}Gini(D^v)$
观来说，Gini(D) 反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此 Gini(D) 越小，则数据集D的纯度越高。
选择使得划分后基尼指数最小的属性作为最优划分属性。