决策树系列算法（Decision Tree）
什么是决策树？
决策树是一类常见的机器学习算法，以二分类任务为力，我们希望从给定的训练数据集中学得一个模型用以对新示例进行分类，这个把样本分类的任务，可以看作对“当前样本属于正类吗？”这个问题的“决策”或者“判定”过程。决策树是基于树形结构来进行决策的，这恰是人类面临决策问题时一种很自然的处理机制。例如，我们要对“这是个好瓜吗？”这个问题进行决策，通常会进行一系列判断或“子决策”：我们先看“它是什么颜色？”，如果是“青绿色”，则我们再看“它的根蒂是什么形态？”……最终我们得出决策，这是个好瓜。——周志华《机器学习》（西瓜书）
这里观看图形示例会更加直观的明白决策树。
决策树可以举出很多例子，和人类的思维方式非常像，简单来说就是对每个特征加以区分，例如公司筛选简历，非985毕业直接不要，985毕业，再看项目，项目不错再看颜值……
决策树算法
输入：训练集 $D={(x_1, y_1), (x_2, y_2),… (x_m, y_m)}$ 属性集 $A = {a_1, a_2,… a_d}$ 过程：函数TreeGenerate(D, A)
- 生成节点node；
- if D 中样本全属于同一类别C then
- 将node 标记为C类叶节点； return
- end if
- if A = null OR D 中样本在A上取值相同 then
- 将node 标记为叶节点，其类别标记为D 中样本数量最多的类；return
- end if
- 从A中选择最优划分属性 $a_*$ ;
- for $a_*$ 的每一个值 $a_*^v$ do
- 为node生成一个分支；令$D_v$ 表示$D$中在$a_*$上取值为$a_*^v$ 的样本子集；
- if $D_v$为空 then
- 将分支节点标记为叶节点，其类别标记为$D$中样本最多的类；return
- else
- 以TreeGenerate($D_v, A$ \ $A{ a_*}$)为分支结点
- end if
- end for
输出：以node为跟节点的一棵决策树
不看算法，从图片上看，决策树非常的直观和简单，但是这里却有一个复杂而简单的问题：我们首先采用什么特征来区分样本集？即我们如何选择算法里的最优划分属性$a_*$，为什么我们看西瓜先看颜色，再看根蒂形态？通常人类的直觉是，哪个特征能更好的区分样本，我们首先就看哪个特征，这就是一种划分选择。
ID3算法
ID3算法（Iterative Dichotomiser 3 迭代二叉树3代）是一个由Ross Quinlan发明的用于决策树的算法。是一个启发式算法，这个算法遵循一个理念：越是小型的决策树越优于大的决策树（be simple）。
信息增益
“信息熵”（information entropy）是度量样本集合纯度最常用的一种指标。信息熵越大，说明样本集越混乱；越小，纯度越高。类似于人类的划分选择，信息熵使决策树能够使用让划分后的子样本集纯度更高的特征来划分样本集。
| 特征1 | 特征2 | 类别 |
|---|---|---|
| x | a | 1 |
| y | a | 1 |
| x | b | 2 |
显然，对于以上表格数据，我们更倾向于使用特征2来划分样本集，因为特征2可以很好的区分样本的类别，特征2的值为a时，类别都为1；特征2为b时，类别都为2。而特征1相对来说就要混乱一些。“如无必要，勿增实体” ，这和“奥卡姆剃刀”的概念是一样的。
“切勿浪费较多东西去做，用较少的东西，同样可以做好的事情。” ——《箴言书注》
事实上了解这一简单概念也有助于我们日常生活中的决策，帮助我们理清自己的头绪，做出正确的决策。
信息熵实质是信息论中的一个数学定义，假定当前样本集合D中第k类样本所占比例为$ p_k$ (k = 1, 2, 3 …, n) 则D的信息熵定义为：$\text{Ent}(D) = -\sum{_{k=1}^{n}p_klog_2p_k}$
假定当前样本集合的信息熵为$E_1$，使用某个特征划分后的信息熵为$E_2$，则信息增益为$Gain = E_1 - E_2$
例，
| Race | Incom | Child | Insurance |
|---|---|---|---|
| black | high | no | yes |
| white | high | yes | yes |
| white | low | yes | yes |
| white | low | yes | yes |
| black | low | no | no |
| black | low | no | no |
| black | low | no | no |
| white | low | no | no |
这样的一个数据集D，包含三个特征，两个类别。
则未划分之前信息熵为：$Ent(D) = -\frac{1}{2}log_2\frac{1}{2} - \frac{1}{2}log_2\frac{1}{2} = 1$
使用特征Race划分数据集的信息增益计算如下：
$Ent(T_{black}) = -\frac{3}{4}log_2\frac{3}{4} - \frac{1}{4}log_2\frac{1}{4} = 0.8113 …… (1)$
$Ent(T_{white}) = -\frac{3}{4}log_2\frac{3}{4} - \frac{1}{4}log_2\frac{1}{4} = 0.8113……(2)$
注意：（1）（2）两式不是采用race特征划分后各自的信息熵，我们定义此时对于数据集D划分后的信息熵等于（1）（2）两式加权求和。即
$Ent(T_{Race}) = \frac{1}{2}Ent(T_{black}) - \frac{1}{2}Ent(T_{white})$
原本信息熵与划分后的信息熵相减得：
$Gain(Race) = Ent(D) - Ent(T_{Race}) = 0.1887$
可以看出，信息增益实际上是原信息熵与划分后信息熵的差值，划分后的信息熵越小，划分后的数据集越纯，信息增益越大。因此我们依次对每个特征计算信息增益，选择信息增益最大的特征进行划分。如果我们将原样本集划分为两个子样本集，对子样本集采用同样的算法继续划分，如此我们就可以得到一颗决策树。
ID3的思想便是：
- 自顶向下的贪婪搜索遍历可能的决策树空间构造决策树(此方法是ID3算法和C4.5算法的基础)；
- 从“哪一个属性将在树的根节点被测试”开始；
- 使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性作为树的根结点测试(如何定义或者评判一个属性是分类能力最好的呢？这便是下文将要介绍的信息增益，or 信息增益率)。
- 然后为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是说，样例的该属性值对应的分支）之下。
- 重复这个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。
这形成了对合格决策树的贪婪搜索，也就是算法从不回溯重新考虑以前的选择。
ID3算法完成了决策树构建的雏形，然而问题依然存在，也就是说ID3版本的决策树仍然存在很多缺陷。例如无法处理连续值属性；信息增益对取值多的属性具有偏好，因而容易将树分裂的很宽，导致最终可能每个叶子上都是“纯的”，有时候这并不见得就是好事，会降低泛化能力。
C4.5算法
C4.5总体上与ID3的策略相同，是ID3算法的一个改进，相比来说要复杂许多，可以说是一套算法。我们具体来看一下C4.5相对于ID3的改进之处。
- 用信息增益率代替信息增益，通过选择信息增益率最大的属性，来选择最优划分属性。
- 在树的构造过程中进行剪枝。
- 增加了对非离散值的处理，也就是回归模型
- 增加了对确实值的处理。
下面，我们针对这四点逐一详细解释。
信息增益率
对于信息增益来说，我们在自己构建决策树实例的时候，会发现信息增益准则对可取值数目较多的属性有所偏好，为了减少这种偏好可能带来的不利影响，C4.5采用了信息增益率。
$GainRatio(D, a) = \frac{Gain(D, a)}{IV(a)}$ ， 其中$IV(a) = -\sum_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{D^v}{D}$ 称为属性$a$的“固有值”。
我们用相同的例子来说明信息增益率的计算。
| Race | Incom | Child | Insurance |
|---|---|---|---|
| black | high | no | yes |
| white | high | yes | yes |
| white | low | yes | yes |
| white | low | yes | yes |
| black | low | no | no |
| black | low | no | no |
| black | low | no | no |
| white | low | no | no |
未划分之前信息熵为：$Ent(D) = -\frac{1}{2}log_2\frac{1}{2} - \frac{1}{2}log_2\frac{1}{2} = 1$
使用特征Race划分数据集的信息增益计算如下：
$Ent(T_{black}) = -\frac{3}{4}log_2\frac{3}{4} - \frac{1}{4}log_2\frac{1}{4} = 0.8113 …… (1)$
$Ent(T_{white}) = -\frac{3}{4}log_2\frac{3}{4} - \frac{1}{4}log_2\frac{1}{4} = 0.8113……(2)$
$Ent(T_{Race}) = \frac{1}{2}Ent(T_{black}) + \frac{1}{2}Ent(T_{white}) = 0.8113$
原本信息熵与划分后的信息熵相减得：
$Gain(Race) = Ent(D) - Ent(T_{Race}) = 0.1887$
此时，我们需要多计算一个Race本身信息熵的固有值
$IV(Race) = -\frac{1}{2}log_2\frac{1}{2} - \frac{1}{2}log_2\frac{1}{2} =1$
最后我们来计算信息增益率
$GainRatio(Race) = \frac{Gain()}{IV(Race)} = (1-0.8113)/1 = 0.1887$
然而需要注意的是，信息增益率与信息增益相反，可能对取值数目较少的属性有所偏好，即$IV(Race)$接近于0的情况下，信息增益率会变得非常大。因此实际上C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式方法：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益率最高的。
剪枝
剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段，在决策树学习中，为了尽可能正确分类样本，结点划分过程将不断重复，有时候会造成决策树分支过多，这时就可能因训练样本训练的“太好”了，以至于把训练集自身的一些特点当作所有数据都具有的一般性质而降低泛化能力（如ID3介绍时末位提到的）。因此，可以通过主动去掉一些分支来降低过拟合的风险。
泛化能力的评估
通常我们将数据集分为训练集和测试集，但是很多时候，这并不能很好的评估我们训练的模型的泛化能力。例如，通常我们通过评估我们的模型在测试集上的表现来反应模型的性能，并在此基础上改进模型，听起来这并没有什么问题，但是仔细想想看，我们优化模型针对的是测试集上的表现，也就是我们为了模型能在测试集上有好的表现而改进模型，实际上在改进过程中，模型正逐步学习测试集上的特性，当我们的模型在测试集上有好的表现的时候，并不意味着这个模型对它从来没讲过的数据也能有好的表现。
明白了这一点，要针对模型性能进行模型优化，我们可以再从原始数据集中分出一个验证集，使用验证集来优化我们的模型。对于决策树来说，验证集的作用可以很好的评估决策树的泛化能力并对决策树进行改进，这样做，测试集对这棵决策树仍然是从没见过的数据，可以客观反应模型的性能。在有了验证集之后，我们就能够知道剪枝是否对泛化能力带来了提升。
预剪枝
预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶子结点。
以西瓜树上的西瓜数据集为例：
对生成的决策树进行剪枝：
可以看到，在这个数据集上，通过验证集对模型的评估，我们可以计算剪枝前后模型在验证集上的准确度，基于“贪心”的策略，只要验证集上泛化能力提升，就进行剪枝，这样的剪枝一方面避免了模型过拟合，一方面节省了生成决策树时的计算开销。然而，需要注意的是，很多分支都没有展开，虽然当前泛化能力提升了，但是也不能排除有些分支在划分后的后续划分有可能会提高模型性能，因此预剪枝显然也带来了欠拟合的风险。
后剪枝
后剪枝是先从训练集生成一棵完整的决策树，然后自底向上对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
后剪枝决策树通常比预剪枝决策树保留了更多分支，一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但是后剪枝决策树是在生成了整颗决策树后进行的，并且自底向上对决策树中所有非叶结点逐一考察，因此训练时间上的开销要比预剪枝大得多。
以上表4.2，图4.6，图4.7 来自《机器学习》——周志华
对连续值的处理
ID3是一种分类算法，在构建决策树的过程中要求属性值是离散的，而C4.5中加入了对连续值的处理。处理如下：
- 对该连续值属性$a$的取值进行升序排序，记为{$a_1, a_2, a_3, … a_n$}；
- 计算分类属性发生改变的那些值的信息增益（见下图红线处）。基于划分点$t$可将$D$分为子集$D_t^+$和$D_t^-$，其中$D_t^-$包含那些在属性$a$上取值不大于t的样本，而$D_t^+$则包含那些在属性a上取值大于t的样本。显然，对相邻的$a^i$与$a^{i+1}$来说，t的取值在[$a^i, a^{i+1}$)中取任意值所产生的划分都是一样的，因此通常我们取相邻值的中点作为划分点。
- 接下来，我们选择信息增益率最大的那个属性值，将数据集根据这个值划分成2部分。注意，此处需对最佳分裂点的信息增益进行修正：减去log2(N-1)/|D|（N是连续特征的可能的分裂点个数，D是训练数据数目，此修正的原因在于：当离散属性和连续属性并存时，C4.5算法倾向于选择连续特征做最佳树分裂点）
以上例子可以看到，对Temperature排序，计算类别发生改变处的信息增益。注意，对于连续值在决定分界点时，还是采用增益这个指标，而选择属性的时候才使用增益率这个指标。这个改进能够很好得抑制连续值属性的倾向。
缺失值处理
- 采用抛弃缺失值
抛弃极少量的缺失值的样本对决策树的创建影响不是太大。但是如果属性缺失值较多或是关键属性值缺失,创建的决策树将是不完全的,同时可能给用户造成知识上的大量错误信息,所以抛弃缺失值一般不采用。只有在数据库具有极少量的缺失值同时缺失值不是关键的属性值时,且为了加快创建决策树的速度,才采用抛弃属性缺失值的方式创建决策树。
- 补充缺失值
缺失值较少时按照我们上面的补充规则是可行的。但如果数据库的数据较大,缺失值较多(当然,这样获取的数据库在现实中使用的意义已不大,同时在信息获取方面基本不会出现这样的数据库),这样根据填充后的数据库创建的决策树可能和根据正确值创建的决策树有很大变化。
- 概率化缺失值
对缺失值的样本赋予该属性所有属性值的概率分布,即将缺失值按照其所在属性已知值的相对概率分布来创建决策树。用系数F进行合理的修正计算的信息量,F=数据库中缺失值所在的属性值样本数量去掉缺失值样本数量/数据库中样本数量的总和,即F表示所给属性具有已知值样本的概率。
- 缺失值单独分支
CART算法（Classification and Reggression Tree）
CART决策树使用“基尼系数”来选择最优划分属性，数据集D的纯度可以用基尼系数值来度量：$Gini(D) = \sum_{k=1}^np_kp_k` = 1- \sum_{k=1}^np_k^2$ ，直观来说，Gini(D)反应了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini(D)越小，则数据集D的纯度越高。
对于属性$a$而言，其基尼系数为$Gini(D, a) = \sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$ ，于是我们在候选属性中选择那个划分后基尼系数最小的属性作为我们最优划分属性。
例，
| Race | Incom | Child | Insurance |
|---|---|---|---|
| black | high | no | yes |
| white | high | yes | yes |
| white | low | yes | yes |
| white | low | yes | yes |
| black | low | no | no |
| black | low | no | no |
| black | low | no | no |
| white | low | no | no |
$Gini(D) = 1 - (\frac{1}{2})^2 - (\frac{1}{2})^2 = \frac{1}{2}$
对于属性Race，
$Gini(T_{Black}) = 1 - (\frac{3}{4})^2 - (\frac{1}{4})^2 = 0.375$
$Gini(T_White) = 1 - (\frac{3}{4})^2 - (\frac{1}{4})^2 = 0.375$
$Gini(D, Race) = \frac{1}{2} * Gini(T_{Black}) + \frac{1}{2} * Gini(T_{White}) = 0.375$
$Gain(Race) = Gini(D) - Gini(D, Race) = 0.125$
CART具备之前C4.5算法引入的一系列优点，如剪枝避免过拟合、处理连续值、处理缺失值。并且因为使用了基尼系数，因此避免了C4.5中大量的对数运算，提高了生成树的效率。另外CART采用了二分割的方式，每次将样本分成两份，构成了一棵更为简洁的二叉决策树。
总结
- 决策树是包含根节点、内部节点和叶子节点的属性结构，通过判断不同属性的值来解决分类问题；
- 决策树的学习过程包括特征选择、决策树生成、决策树剪枝三个步骤；
- 决策树生成的基础是特征选择，特征选择的指标包括信息增益、信息增益率和基尼系数；
- 决策树的剪枝包括预剪枝和后剪枝。