统计学习方法笔记 -- 决策树
决策树
什么是决策树？ 
决策树可以看成一系列if-then的规则，这个很好理解
也可以看成是条件概率分布，
X为特征，x1，x2
Y为分类，1，-1
那么对于每个叶节点，相当于对于每个经过的中间结点的条件概率
当x1=a,x2=b的时候为1分类的概率>0.5，则认为是1分类
决策树学习
决策树学习的本质是从训练数据集上归纳出一组分类规则
但与训练集不相矛盾的决策树可能有多个，也可能一个都没有
我们的目标是找到一个和训练集矛盾较小，且具有很好的泛化能力的决策树（注意不要求没有矛盾，要防止overfit）
决策树学习的损失函数通常是正则化的极大似然函数，但是基于损失函数找到全局最优决策树是NP完全问题
所以实际使用的算法通常采用启发式的方法，即局部最优
具体做法就是，每次选择feature时，都挑选择当前条件下最优的那个feature作为划分规则，即局部最优的feature
决策树学习通常分为3个步骤：特征选择，决策树生成和决策树的修剪
特征选择
前面已经说了，选择特征的标准是找出局部最优的特征
那么问题是如果判断一个特征对于当前数据集的分类效果？即以这个特征进行分类后，数据集是否更近有序（不同分类的数据被尽量分开），还是仍然很混乱？
这里要使用熵（entropy）和信息增益
参考http://zh.wikipedia.org/wiki/%E7%86%B5_%28%E4%BF%A1%E6%81%AF%E8%AE%BA%29
信息量
信息量有这个事件发生的概率所决定，经常发生的事件是没有什么信息量的，比如你天天要吃饭，这个大家都知道。
只有小概率事件才有信息量，比如马航失踪这种突发新闻，所以信息量的定义如下
以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的损失函数是 
如果
但是随着
此时， 
当然如果
所以算法是， 
具体的说，对整个树T0的每个节点计算g(t)，
先将g(t)最小的节点进行剪枝，产生子树T1
然后再T1上再找到g(t)最小的节点进行剪枝。。。在这个过程中g(t)是不断变大的，最终剪到根节点Tn（单节点树）
最终，
本文章摘自博客园，原文发布日期：2014-03-25