《统计学习方法》笔记之－－－决策树

申明：本文的公式均来自《统计学习方法》电子版截图（太懒没手敲。。。）

1.首先选择特征以开展（生成）决策树

特征选择有三个算法：ID3 C4.5 CART 分别使用的是：最大信息增益 最大信息增益比 最小Gini系数（分类）或 平方误差最小化（回归） 准则

［（CART）算法可分别对回归和分类问题构建二叉决策树，分别是应用误差最小化准则 和 最小Gini系数准则  ］其实Gini系数的计算及含义与信息熵很相似。

2.三大算法的公式：

ID3:信息增益

经验熵（对“纯度”的度量），越小越纯。决策树分到后面，是希望叶结点越来越纯的。

k为总的类别个数，Ck为类别k的样本个数。

Di的i，指特征A的可取值情况。即在A特征下，Di 是 A的不同取值情况下包含的样本数量。Dik表示，特征A取i值，且对应样本中属于k类别的样本个数。

信息增益比较倾向分支很多的特征（即该特征的可取值很多），故又提出了信息增益比的概念。

C4.5: 信息增益比：（信息增益比比较偏好特征分支少的特征，所以，C4.5算法先找到信息增益高于平均增益值的特征们，再选择其中增益比最大的那个特征，作为最优分类特征。）（来自西瓜书的补充。）

CART算法，（只介绍分类问题的Gini系数）

选择好最佳特征后，就开始利用训练数据迭代的往下生成决策树，直到数据被分类完全。

3.决策树剪枝

因为在生成决策树的时候，利用训练数据严格的一步步生成输的分枝，使得数会过于复杂或者说对训练数据过拟合了，所以为了使输对待测数据也有较好的分类效果，需要在树的数据拟合程度和树的复杂度之间做好平衡，对树进行剪枝。

这句话要好好理解下。

t是树的叶结点，Nt为该点下样本的个数。

ITI为树含有的总 叶结点 个数。

以下要介绍的剪枝算法是：不断的迭代一个个值，得到该值下的最佳树，然后就得到最佳树集合（序列）。再利用独立的验证数据，通过交叉验证，得到序列中的最佳，也即最终的修剪后的决策树。

 CART 剪枝：（后剪枝，西瓜书有介绍预剪枝，但是那样容易欠拟合）

公式（5.29）我是这样理解的：

当afa趋于无穷，根结点组成的单结点树最优，则小于 ，所以相反，当afa趋于0，（5.29）成立。

这里是关键，不断修改afa的区间，一个区间内得到一个最佳树，这样就产生最佳树序列。

算法流程：

在验证集上进行交叉验证，注意是验证集！！！

西瓜书里的后剪枝和这里不太一致，他是从下往上依次对“小树分枝”进行是否剪枝的判断，判断准则就是修剪前后是否能在验证集上提高分类准确率。

把一个“小树分枝”剪掉的话，它得到的那个叶结点的类别是：原先这个“小树分枝”对应的训练集的类别，举个栗子：

具体见西瓜书P82。

以上就是决策树的内容，主要是特征选择的三大算法，然后迭代往下生成决策树，然后为了减轻过拟合问题对树进行算法修剪。

写得很粗糙，有了新理解会再来补充，欢迎大家指正！