决策树 

什么是决策树？      决策树可以看成一系列if-then的规则，这个很好理解  也可以看成是条件概率分布，  X为特征，x1，x2  Y为分类，1，-1  那么对于每个叶节点，相当于对于每个经过的中间结点的条件概率  当x1=a,x2=b的时候为1分类的概率>0.5，则认为是1分类

决策树学习 

决策树学习的本质是从训练数据集上归纳出一组分类规则  但与训练集不相矛盾的决策树可能有多个，也可能一个都没有  我们的目标是找到一个和训练集矛盾较小，且具有很好的泛化能力的决策树（注意不要求没有矛盾，要防止overfit）  决策树学习的损失函数通常是正则化的极大似然函数，但是基于损失函数找到全局最优决策树是NP完全问题  所以实际使用的算法通常采用启发式的方法，即局部最优  具体做法就是，每次选择feature时，都挑选择当前条件下最优的那个feature作为划分规则，即局部最优的feature

决策树学习通常分为3个步骤：特征选择，决策树生成和决策树的修剪

特征选择 

前面已经说了，选择特征的标准是找出局部最优的特征  那么问题是如果判断一个特征对于当前数据集的分类效果？即以这个特征进行分类后，数据集是否更近有序（不同分类的数据被尽量分开），还是仍然很混乱？  这里要使用熵（entropy）和信息增益

参考

信息量 

信息量有这个事件发生的概率所决定，经常发生的事件是没有什么信息量的，比如你天天要吃饭，这个大家都知道。 

只有小概率事件才有信息量，比如马航失踪这种突发新闻，所以信息量的定义如下 

以2为底，单位是bit，以e为底，单位是nat，以10为底，单位是dit 

 

比如下面的例子，可以看出汉字的信息量要远远大于英文字母的（当然现实中，不可能所有字出现的概率一样，这里只是为了简单处理说明问题） 

这就意味着写同一篇文章，汉字会更加简短，当然学习门槛也会更高 

 

信息熵 

熵，就是信息量的期望 

 

熵起源于物理热力学系统，表示无序程度，同样在信息论中，熵表示对不确定性的测量 

如果有一枚理想的硬币，其出现正面和反面的机会相等，则抛硬币事件的熵等于其能够达到的最大值，这时候这个事件的熵为1bit，而当抛出正面的概率变大或变小时不确定性都会降低，极限情况一定为正或负时，没有任何不确定性，熵为0 

  

数据压缩也是基于熵理论，普通的编码方式每个字符都是8bit，很浪费，因为英文字母的熵在4.7bit左右，这个表示编码的最小平均长度，好的无损压缩算法应该可以接近这个编码长度

联合熵 

 

条件熵 

 

信息增益 

表示得知特征X的信息而使得类Y的信息的不确定性减少的程度  分类前，数据中可能出现各种类的情况，比较混乱，不确定性强，熵比较高  分类后，不同类的数据得到比较好的划分，那么在一个划分中大部分是同一类的数据，比较有序，不确定性降低，熵比较低  而信息增益用于描述这种熵的变化 

下面给出计算信息增益的具体的公式， 

H(D)，直接根据公司计算  而H(D|A)，D根据A分为n份D1…Dn，那么H(D|A)就是所有H(Di)的期望(平均值)

 

 

用书中的例子来解释一下，贷款申请训练集，想建决策树来辅助判断是否可以贷款 

   首先用哪个特征来划分了是”年龄”，还是”有工作”？

直接用上面的公式来计算信息增益来判断 

首先算下为分类时的经验熵，所谓经验熵就是根据训练数据算出的熵

这里分别以A1，A2表示”年龄””有工作”两个特性，这里为了说明问题只考虑两个特性 

关于年龄的信息增益计算，样本中青年，中年，老年各5个，然后每个划分中是否贷款比例分别为，2：3，3：2，4：1。可以直观的看出划分效果不明显，所以算出的信息增益也确实很小 

而对于有工作的，算出的信息增益要大很多，这也是符合直观的判断 

  所以如果要在这两个特征里面选择的话，应该选“有工作”

信息增益比 

单纯的信息增益只是个相对值，因为这依赖于H(D)的大小  所以定义信息增益比作为更加客观的度量 

 

决策树生成 

先介绍ID3生成算法，这是最基本的算法  而C4.5只是把其中的信息增益换成信息增益比  算法很简单，只是在每个节点上选出信息增益最大的那个特征进行划分  直到信息增益小于阙值时停止  因为信息增益是相对值，所以这里使用信息增益来比较阙值不合理  在C4.5中使用信息增益比来替代

  

 

决策树的剪枝（pruning） 

决策树生成算法对于训练集是很准确的，但是这样会过拟合，所以需要通过剪枝（简化过程）来提高泛化能力  剪枝的思路也很简单，就是在决策树对训练数据的预测误差和树复杂度之间找到一个balance  预测误差表示为，即所有叶节点的经验熵的和，其中Nt表示该叶节点的样本点个数，而Ht(T)表示该叶节点的经验熵   树复杂度，由叶节点个数来表示，|T|

所以决策树的学习损失函数定义为，剪枝的标准就是极小化该损失函数 

   是调节参数，越大表示选择更简单的树，而越小表示选择复杂的对训练集拟合度高的树

剪枝的算法 

很简单，从叶节点往上回溯，比较剪掉该叶节点前后的损失函数的值，如果剪掉后，损失函数更小就剪掉

 

 

CART算法 

这里只看分类树的相关算法，回归树即输出连续的case，参考原书

生成算法 

和ID3两点不同，  首先是二叉树，比如对于年龄不是分为青年，中年，老年，而是选一个子特性进行二分，比如青年，不是青年  再者，基于基尼指数，也是用于表示不确定性，和熵类似  

具体生成算法，还是看前面那个例子， 

   对于年龄的每个子特征的gini指数   A2和A3都只有一个切分点    最后是A4的    最后，发现最优的切分点是

剪枝算法 

CART的剪枝算法比较特别  首先树上任意一个节点t，如果以t为单节点树（即意味着把t的子树剪掉）的损失函数为   以t为根节点的子树Tt的损失函数是    如果，不考虑树复杂度，那么一定是 ，即不剪枝的情况下，损失函数更小  但是随着 不断增大，一定会出现 ，即剪不剪枝，损失函数相等，那么还不如剪了让树简单一点  此时，   当然如果过于大就没有意义了，因为我们需要balance对训练集的拟合度以及树的复杂度  所以算法是，     

具体的说，对整个树T0的每个节点计算g(t)， 

先将g(t)最小的节点进行剪枝，产生子树T1  然后再T1上再找到g(t)最小的节点进行剪枝。。。在这个过程中g(t)是不断变大的，最终剪到根节点Tn（单节点树）  最终， 

本文章摘自博客园，原文发布日期：2014-03-25