决策树
什么是决策树？
决策树可以看成一系列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的损失函数是
如果
，不考虑树复杂度，那么一定是
，即不剪枝的情况下，损失函数更小
但是随着
不断增大，一定会出现
，即剪不剪枝，损失函数相等，那么还不如剪了让树简单一点
此时，
当然如果过于大就没有意义了，因为我们需要balance对训练集的拟合度以及树的复杂度
所以算法是，
具体的说，对整个树T0的每个节点计算g(t)，
先将g(t)最小的节点进行剪枝，产生子树T1
然后再T1上再找到g(t)最小的节点进行剪枝。。。在这个过程中g(t)是不断变大的，最终剪到根节点Tn（单节点树）
最终，
本文章摘自博客园，原文发布日期：2014-03-25
