第5章 决策树

　　决策树是一种基本的分类与回归方法。这章主要讨论用于分类的决策树，也就是基于特征对实例进行分类的决策树。决策树通常包括3个步骤：特征选择、决策树的生成、决策树的修剪。

5.1 决策树模型

　　分类决策树模型是一种描述对实例进行分类的树形结构，内部节点表示一个特征或属性，叶子节点表示一个类。它可以认为是if-then规则的集合，也可以是定义在特征空间与类空间上的条件概率。

　　

　　决策树的本质上是从训练数据集中归纳出一组分类规则。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛华能力。决策树学习用损失函数表示这一目标。其损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。

　　如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。

5.2 特征选择

　　直观上，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，是的各个子集在当前条件下有最好的分类，则就更应该选择这个特征。信息增益就能够很好地表示这一直观的准则。　　

　　特征选择的准则是信息增益或信息增益比。

　　5.2.1 信息增益

　　　　在这里，要先给出熵和条件熵的定义，熵表示随机变量不确定性的度量。设X是一个取有限个值得离散随机变量，其概率分布为：，

　　则随机变量X的熵定义为：，若Pi=0，则H(X)=0，由定义可知，熵只依赖于X的分布，而与X的取值无关，所以也可将X的熵记作H（p）：；熵越大，随机变量的不确定性就越大。

　　　当随机变量只有两个值时，例如1， 0时，即X的分布为：

　　　 熵为：，当p=0或p=1时，H(p)=0，表示随机变量完全没有不确定性。

　　　设有随机变量（X,Y），其联合概率分布为：

　　　 条件熵H（Y|X）表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X数学期望

　　　 信息增益表示得知特征X 的信息而使得类Y的信息的不确定性减少的程度。

　　　　

　　   显然，对于数据集D而言，信息增益依赖于特征，不同特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。。

　　　根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征。

　　　信息增益的算法：　　　　

　　　　

　　　　　

　　　　给出例子便于理解：

　　　

 

 　　　

 　　　

　　5.2.2 信息增益比

　　　　以信息增益作为划分训练数据集 的特征，存在偏向于选择值较多的特征的问题。使用信息增益比可以对这一问题进行校正。

5.3 决策树的生成

　　从根节点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。而C4.5算法是对ID3算法进行了改进。在C4.5的生成树过程中，是用信息增益比来选择特征的。

　　这里在介绍一下CART算法，CART假设决策树是二叉树，内部结点特征取值为“是”或者“否”的行为分支，比如对于年龄不是分为老、中、青年，而是选择其中一个子特性进行二分，比如“是青年”和“不是青年”，再者，也是基于基尼指数，基尼指数数值越大，样本集合的不确定性也就越大，和熵类似。分类树用基尼指数选择最优特征，同时决定该特征的最优二指切分点。

　　

　　

　　有了基尼指数，下面给出CART的生成算法：

　　

　　

　　依然给出之前的例子便于理解，这次使用CART算法：

　　

 

 　　决策树的剪枝，这里参考http://www.cnblogs.com/fxjwind/p/3623294.html的分析笔记：