引言

上一篇学习了机器学习中常用的线性模型。首先学习了对于回归问题采用最小二乘法等数学方法对一般线性模型和广义线性模型进行推导。接着讨论了对于分类问题，采用对数几率回归的方法进行求解。又介绍了线性判别分析（LDA）这个经典的线性学习方法。最后对于多分类问题和类别不平衡问题给出了解决办法。
本篇继续学习一个非常重要的学习方法：决策树。

1.基本概念及流程

决策树顾名思义，就是以树结构来进行决策，它包含有一个根结点、若干个分支结点和若干个叶结点（对应决策结果）。
决策树的生成是一个递归过程，在决策树算法中，有三种情况会导致递归返回：
（1）当前结点包含的样本全属于同一类别，无需划分;
（2）当前属性集为空，或是所有样本在所有属性上取值相同，无法划分;
（3）当前结点包含的样本集合为空，不能划分。
其算法的流程如下：

2.划分选择

决策树的关键在于如何对属性进行划分选择。我们通常希望决策树的分支结点包含的样本尽量属于同一类别，即“纯度”高。衡量这个“纯度”有一下几种指标。

2.1.信息增益（ID3决策树）

信息熵的概念：信息熵是度量样本集纯度的一种指标，假定pk为样本集中第k类样品所占得比例，样品集的信息熵表达式如下：

考虑到不同分类子集Dv的样本数目不一样，按样本数量给每个结点赋予权重，引入信息增益的概念：

可以依据信息增益来划分属性，信息增益越大，以为着改属性纯度越大，可以作为优先划分。

2.2.信息增益率（C4.5决策树）

在上面的算法中，以信息增益作为划分依据，有个缺陷是该种划分方式对可取值数目较多的属性有所偏好，可能带来不利影响（如将样本编号视为，则样本编号为纯度最高，显然该属性划分意义不大）。C4.5决策树算法对此进行了改进，引入了信息增益率的概念：

其中

信息增益率可能对于样本数目较少的属性有所偏好。
我们通常选择优先属性的原则是：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

2.3.基尼系数（CART决策树）

CART 决策树使用基尼系数来判断属性纯度：

基尼系数的概念即为从样本集中任选两个样本，其属性不一样的概率。因此，基尼系数越高，数据集纯度越高。同样，引入样本数量权值后，该表达式可以修正为：

3.剪枝处理

剪枝是对付“过拟合”的主要手段。基本策略有“预剪枝”和“后剪枝”两种：预剪枝是指在决策树生成过程中，对每个结点划分前进行与估计，若划分无法带来泛化能力提升，则停止划分，将该节点视为也结点；后剪枝是指完整的决策树生成好后，自底向上进行考察，删除不能带来泛化能力提升的子结点。

4.连续与缺失值

4.1.连续值处理

连续属性可取的数目无限，不可太过属性的取值来划分，需要用到连续属性离散化的技术。最简单的方法是C4.5决策树算法中的“二分法”：假定连续属性a在样本集D中有n个取值，从小到大进行排序{a1,a2,…an}，在这些样本中选取一个划分点，即可将样本划分为两部分，划分见可以简单得取为相邻两个取值的中位点：

n个取值则有n-1个待选的划分点，在根据前面讲到的纯度选择原则，计算其信息增益可以选择合适的划分点。

4.2.缺失值处理

在现实任务中，可能会遇到样品的某些属性缺失，若将这些样品剔除，会造成样品的浪费。可以通过在信息增益中给不同属性赋予权值的方法来实现。为每个样本 x贼予一个权重w（初始化为1）并定义

可将信息增益的计算式推广为

其中

5.多变量决策树

决策树所形成的分类边界有一个明显的特点：轴平行。多变量决策树目标是寻找一个合适的线性分类器对边界进行近似简化。