统计机器学习07：决策树DecisionTree

基本概念

决策树(Decision Tree)实际上是通过树形的结构来进行分类或者回归，在分类问题中可以根据样本的不同特征属性的不同属性值来进行多次分类的决策最终确定输入样本的类别，也就相当于执行了一连串嵌套的if-else语句，也可以被认为是定义在特征空间和类空间上的条件概率分布。决策树的优点是模型具有较好的可读性，分类的速度比较快。

决策树中有一系列节点和有向边，节点又分为内部节点和也节点，内部节点表示一个特征或者属性，叶节点表示一种类别。

决策树模型的建立

决策树主要依靠训练数据，采取损失函数最小化的原则来建立决策树模型，分为特征选择、决策树的生成和剪枝三个步骤。建立决策树的过程用的特点主要有：

  • 采用递归的方法构建决策树

  • 当所有的样本都属于同一类或者在这一层已经对所有的特征都进行了分类，决策树的建立就停止

  • 在决策树的每一层选取一个最优的特征并用这个特征来进行分类，这也是决策树算法最关键的地方

  • 一般而言我们希望，随着划分过程的不断进行，决策树的分支节点所包含的样本尽可能属于同一类别，也就是节点的纯度越来越高

因为决策树考虑到了样本中的所有点，对所有的样本点都有正确的分类，因此决策树的bias实际上是0，因此评价一棵树的主要标准是variance，一般来说规模比较小的决策树的performance更好。

最优特征的选取

上面已经说到决策树构建的最重要的部分就是在每一层选择合适的特征来进行划分，常见的算法有熵、信息增益等等。

信息熵Entropy

熵可以用来表示随机变量的不确定性。如果X是一个取值个数为有限个值即，那么随机变量X的熵的定义就是： 而对于随机变量X和Y，如果，那么在X给定的情况下随机变量Y的条件熵代表了X给定条件下Y的条件概率分布的熵对于X的数学期望： 当用数据估计得到熵和条件熵的时候，他们又分别被称为经验熵和经验条件熵。

信息增益

信息增益(information gain)表示已经知道特征X的信息而使得类Y的信息的不确定度减少的程度。特征A对于数据集D的信息增益定义为D的经验熵和D在A给定条件下的经验条件熵的差值，即： 信息增益又叫做互信息(mutual information)，两个概念是等价的。基于信息增益的特征选择方法一般都是对于当前训练集D，计算其每个特征的信息增益，并比较大小，选择信息增益最大的特征来进行当前层的分类。

假设训练的数据集是，有K个不同的分类满足，其中特征A有n个不同的取值，根据特征的取值将划分成了n个不同的子集，而每个子集中表示属于类别的样本，那么数据集的经验熵可以表示为： 特征A对于数据集D的条件经验熵可以表示为：

信息增益比

以信息增益作为数据集划分依据的时候，容易偏向于选择取值更多的特征作为分类标准，但是使用信息增益比，可以校正这一偏差，信息增益比是当前数据集D关于特征A的信息增益和自身的熵的比值，即：

基尼指数

基尼指数是另一种决策树的评价标准，对于分类问题，假设样本集合中有K中不同的类别，每类出现的概率为那么基于概率分布的基尼指数可以定义成 而在样本集合D中，基尼指数可以定义为：

决策树的剪枝与生成

ID3算法

ID3算法的核心是在决策树的各个节点上用信息增益Information Gain来进行特征的选择，并且递归地建立决策树：

  • 从根结点开始，对于当前节点计算所有可能的特征值的信息增益，选择信息增益最大的特征作为划分的依据并建立子节点

  • 直到所有的特征的信息增益都很小或者没有子节点位置停止调用

C4.5算法

和ID3算法类似，但是采用信息增益比作为选择的特征，其他的好像区别不是很大，但实际上决策树的代码实现应该是一系列统计学习的算法中难度比较大的，因为决策树需要使用树的数据结构，相比于其他算法的一系列矩阵计算在coding的过程中可能会有更大的麻烦。

决策树的剪枝Pruning

我们要明白决策树实际上是一种基于大量统计样本的贪心算法(仅根据个人理解，不代表任何工人观点)，在选定了一个决策标准(信息熵，信息增益，信息增益比等等)之后，就需要根据训练集来构建一棵决策树，构建的策略就是在每一次作出决策的时候(对应到树中就是产生了一系列子节点)都会依照给定的标准，计算每种特征相对于给定标准的值，然后选择当前区分度最大，也就是最优的特征作为当前层的决策依据。

但是这样一来，生成的决策树的复杂度可能是非常高的，因此我们应该想办法对这个决策树进行一定的简化，也就是进行剪枝，决策树的剪枝往往通过极小化决策树整体的损失函数或者代价函数来实现。设决策树T的每个叶节点t有个样本点，其中属于类别k的有个，节点t的经验熵可以表示为： 那么决策树的损失函数可以定义为： 而其中是一个自己确定的参数值，比较大的可以使得损失函数偏向于更简单的模型，而比较小的则似的损失函数的优化偏向于比较复杂的模型，的时候完全无视了模型的复杂度，而只考虑模型和训练数据的匹配程度。其实这也就相当于给决策树的损失函数加一个正则项了，我们可以把过分精确的决策树看成是一种过拟合。

这里就不得不提一个冷知识：完整的决策树在训练的过程中分类的误差是0，也就是说不做任何剪枝处理的决策树对训练集的分类是一定准确的。

这也很好理解，因为决策树在构建的过程中并没有舍弃掉一些小概率的样本，而是对其如实进行了分类，虽然最后构建出来的决策树可能非常复杂但是在构建的时候因为我们的策略是贪心的，所以一定会把训练集上的样本分类到对应的叶节点上。

换句话说不剪枝的决策树的bias是0，而variance往往比较大，未剪枝的决策树在训练集上表现很好而在测试集上可能不尽人意，因此我们需要通过剪枝使得决策树可以更好地适应测试集，换句话说，剪枝可以降低决策树模型的variance

剪枝过程是一个从底部向上的递归过程，首先需要计算每个节点的经验熵，如果剪掉某一段子树之后损失函数比剪掉之前更小，就进行剪枝，将父节点作为新的叶节点，重复下去直到不能继续为止。

CART算法

CART的定义

CART算法是Classification And Regression Tree(分类与回归树)的简称，从字面意思就可以看出来这种决策树既可以用于分类，也可以用于回归。

  • CART树的一个基本假设就是决策树都是二叉树，决策的结果只有是与否两种，这等价于递归地二分每个特征， 将输入空间划分成优先个但愿，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布

  • CART算法由生成和剪枝两个部分组成，对于生成的决策树希望它尽可能要大，剪枝的时候使用验证数据集来选择最优子树，这时候用损失函数最小作为剪枝的标准

回归树的生成

回归树对应的是输入空间的一个划分和输出值的映射关系，假如说输入的空间被划分成了M个单元，每个分别对应了固定的输出值，那么回归树模型可以表示为一个函数： 如果输入空间的划分确定，就可以用平方误差来估计训练数据的预测误差，用平方误差最小的准则来求解每个单元上的最优输出值。对于每一个单元，这个单元对应的输出值就是其中若干个样本的label的平均值： 因此问题在于如何对输入空间进行合理的划分，《统计学习方法》这本书里采用了一种启发式的方法，选择选择特征空间中的第j个变量和它取的值s作为切分变量(splitting variable)和切分点。并定义两个区域： 然后我们可以遍历所有的特征j和特征j的取值s来找到使得平房误差最小的切分点，寻找的依据是： 对于一个固定的j而言，上面的表达式中的值是确定的，即按照上面所说的取这一范围内的平均值即可，而通过遍历所有的输入变量可以找到最优的切分变量j，然后就可以根据这样一个二元组将决策树划分成两个区域，然后在每个区域中重复上述操作，最后就可以生成一棵最小二乘回归树

分类树的生成

CART的分类树用基尼指数作为衡量集合不确定性的标准，因为CART默认采用的都是二分类，因此基尼指数可以定义成： 分类树的构建方法和普通的决策树一样，只不过选用基尼指数作为评价标准并且每次划分只能划分成两个子节点，递归建树的过程和普通决策树是完全一致的。