简介

  决策树是一种解决分类和回归的的模型。决策树由节点和有向边组成。节点分为两种，内部节点和叶节点。每个叶节点都代表一个特征，根据每个输入的该特征的值的不同，该输入会被分向不同的有向边，指向下一级节点，直到叶节点为止，每一个叶节点都是一个输出。回归问题中每一个叶节点都是一个值，分类问题中每一个叶节点都是一个类。
  决策树在学习的时候每次会选择当下最好的特征将训练数据集分割成几个子集，一直到每个子集具有良好的值或者分类。训练完后的数据可能会过拟合，所以这里在训练结束后还需要对决策树进行剪枝，有的文献说决策树剪枝比训练还重要。

特征选择

  不同的决策树的特征选择方法各有不同，用于分类的树可以采用信息增益，信息增益比，基尼系数等，用于回归的树可以采用损失函数最小等等方法。

信息增益

熵

  熵的大小是代表一个随机变量的不确定性大小，如果一个随机变量的概率分布如下：

  那么这个变量的熵为：

  对于一个binary变量(0,1),熵随其中某一值概率变化的曲线如下：

条件熵

  条件熵指的是当某变量已知的情况下随机变量的不确定性，如下：

  上式中pi=P(X=xi),i=1,2,…,n。

信息增益

  一个特征对于训练数据的信息增益指的是训练集合的经验熵与该特征给定的情况下的经验条件熵的差。如果一个熵是通过数据估计得到的，那么这个熵就是经验熵。

  一般的这个差也被称之为互信息。在数的特征选择中会选择信息增益大的特征作为节点进行分类。

信息增益比

  由于采用信息增益作为特征选择的标准时，树会偏向于选择一些取值比较多的特征。为了解决这个问题可以采用信息增益比。
  信息增益比是该特征的信息增益与训练数据的关于该特征的熵的比值，如下:

  上式中HA(D)=−∑ni=1|Di|Dlog2|Di|D，n为特征A取值个数。

基尼指数

  基尼指数用在分类树中，这种树是二叉树，类似于信息增益用于描述集合的不确定性。

  上式中K为类的个数，pk为属于每个类的概率。
  由于这种树是二叉树，所以某一特征条件给定的时候样本集合会被分割成两个部分，那么在该特征A的条件下，集合D的基尼指数为：

  在分类树的训练过程中会采用基尼指数最小的特征条件来作为节点。

经验风险最小

  经验风险最小这种思路运用在回归树中，回归树也是一种二叉树，选择特征时需要遍历所有特征对应所有取值的经验风险大小，选择其中最小的一种作为节点，如下：

  这里cm的取值一般为ave(yi|xi∈Rm),上式中遍历j，以及s找出经验风险最小的点作为分割点，其中j对应的是特征的选取,s对应的是特征分割点值的选取。

决策树的生成

ID3

  ID3算法每次依据信息增益选取特征产生新的节点，一直到信息增益小于给定阈值时停止作为叶节点，每次选取的特征如果有k种取值，那么会产生k个有向边。

C4.5

  C4.5对于ID3做了一些改进，将特征选取的依据从信息增益改成了信息增益比。

CART

  CART全称classification and regression tree,该模型分为分类树和回归树，也都叫做决策树。CART树是一种二叉树，也就是说每一个内部节点只会衍生出两条有向边。

回归树

  回归树每次采用经验风险最小作为选择节点条件的依据，不停的将样本集合分割成两个区域，直到满足停止条件为止。

分类树

  分类树每次采用基尼指数作为选择节点条件的依据，不停的将样本集合分割成两个区域，直到满足停止条件为止。

决策树的剪枝

  剪枝是通过去掉决策树上的一些子树或者叶节点，并将根节点或者其父节点作为新的叶节点，从而降低模型的复杂度，减少过拟合的出现。

ID3与C4.5算法的剪枝

  这里按照书上介绍一种简单的剪枝方法。首先将整个决策树的损失函数定义如下：

  上式中|T|代表树T的叶节点数,t为树的叶节点，这个叶节点有Nt个样本点，这些样本点中属于k类的样本有Ntk个,Ht(T)为叶节点t上面的经验熵，α≥0为参数。
  这里设C(T)=∑|T|t=1NtHt(T)=−∑|T|t−1∑Kk=1NtklogNtkNt,这样的话这个式子可以变形为:

  进行剪枝的时候每次计算每个节点的经验熵以及去掉这个节点前后整体数的损失函数，如果去掉后损失函数减小，则进行剪枝。

CART算法的剪枝

  CART算法的损失函数与上面的类似:

  这里的C(T)对于回归树来说是训练数据的经验风险，对于分类树来说是基尼指数。
  对于初始的整体数T0的任意内部节点t,以t为单节点树的损失函数为:

  这里以t为根节点的子树的损失函数为:

  这里当α=C(t)−C(Tt)|Tt|−1时，两个损失函数相等，两个损失函数相同的时候，保留节点少的树，也就是执行剪枝。这样的话我们对于每一个节点都可以计算这样一个α。
  实际剪枝的过程中通过不断增大α（值都为前面计算出来的），来得到一系列剪枝完的树。最后拿出一组独立的测试集来测试哪一个树的误差最小，最后就采用哪一颗树作为输出。