决策树（decesion tree）算法与其他机器学习算法最大的优势就是有很好的解释性，并可将分类结果进行可视化展示。但是决策树算法选择特征的方法众多，如何选择合适的方法是一个难点。

一、决策树一些概念

• 决策树是一种树形结构，叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根节点包含样本全集。基本划分流程遵循简单而直观的“分而治之”（divide-and-conquer）策略
• 决策树算法式基于启发式思想比如贪婪方法，逐步构建决策树，在每个节点采用局部最优策略。这种算法不能保证返回全局最优的决策树，但是在实践中效果也不错
• 决策树学习是以实例为基础的归纳学习，在本质上是从训练数据集中归纳出一组分类规则，其学习的策略是以损失函数（损失函数通常是正则化的极大似然函数）为目标函数的极小化
• 决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶子节点中的实例都属于一类
  注:正则化，知乎上看到一个很好的解释。英文为regularizer，顾名思义，规则化就是...向你的模型加入某些规则，加入先验，缩小解空间，减小求出错误解的可能性。你要把你的知识数学化告诉这个模型，对代价函数来说，就是加入对模型“长相”的惩罚。

二、划分选择

划分不断进行，我们希望树的分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”（purity）越来越高。说白了，就是划分数据的原则就是是使无序的数据变得有序

1.信息增益

什么叫信息增益？
划分数据集之前之后信息发生的变化称为信息增益，计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。
怎么计算？
首先，需要知道的是，信息肯定是由度量的，这个度量确实也有，就是香农提出来的“信息熵”（information entropy）。看一下字典对entropy的解释：(in data transmission and information theory) a measure of the loss of information in a transmitted signal or message.信息量的度量就等于不确定性的多少，而熵就是衡量这种不确定性（混杂度）的数学指标，被定义为信息的期望值。那么信息是什么？$x_{i}$的信息可定义为:$L(x_{i})=-log(p(x_{i}))$，其中$p(x_{i})$是选择该分类的概率。
假定当前样本集合$D$中的$k$类样本所占的比例为$p_{k}(k=1,2,....,|\gamma|)$,则$D$的信息熵被定义为

$$ Ent(D)=-\sum_{k=1}^{|\gamma|}p_{k}log_{2}p_{k}. $$

其中，$|\gamma|$表示分类的个数。$Ent(D)$的值越小，则$D$的纯度越高。
根据之前的解释，信息增益（information gain）表示得知属性（特征）$X$的信息而使得类$Y$的信息的不确定性减少的程度。
假定离散属性$a$有$V$个可能的取值$\left\{a^{1},a^{2},...,a^{V}\right\}$，若使用$a$来对样本集$D$进行划分，则会产生$V$个分支节点，其中第$v$个分支节点包含了$D$中所有在属性$a$上取值为$a^{v}$的结点，记为$D^{v}$。我们可以由上式计算出$D^{v}$信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重$\frac{|D^{v}|}{|D|}$，即样本数越多的分支结点的影响越大，于是可计算出用属性$a$对样本集$D$进行划分所获得的“信息增益”

$$ Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}Ent(D^{v}). $$

一般而言，信息增益越大，则意味着使用属性$a$来进行划分所获得的“纯度提升”越大。因此，我们可以用信息增益来进行决策树的划分属性选择。
ID3算法的核心是在决策树各个结点上应用信息增益准则来选择特征，递归地构建决策树。

2.增益率

信息增益准则对取值数目较多的属性有所偏好，举个例子，如果把样本的编号也作为一个属性来划分，那么显然将产生n个分支，每个分支结点仅包含一个样本，这些分支结点的纯度已达最大，然而这样的决策树不具备泛化能力，无法对新样本进行有效预测。所以在C4.5决策树算法中不直接使用信息增益，而是使用“增益率”（gain ratio）来选择最优划分属性：

$$ Gain-ratio(D,a)=\frac{Gain(D,a)}{IV(a)}, $$

其中

$$ IV(a)=-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}log_{2}\frac{|D^{v}|}{|D|} $$

称为a的“固有值”（intrinsic value）.属性$a$的可能取值数目越多（即$V$越大），则$IV(a)$的值通常会越大.
需要注意的是，增益率准则对取值数目较少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

3.基尼指数

CART（Classification and Regression Tree）决策树使用“基尼指数”（Gini index）来选择划分属性。数据集$D$的纯度可用基尼值来度量：

$$ Gini(D)=\sum_{k=1}^{|\gamma|}\sum_{k'\neq k}p_{k}p_{k'} $$

$$ =1-\sum_{k=1}^{|\gamma|}p_{k}^{2}. $$

直观来说，$Gini(D)$反映了从数据集$D$中随机抽取两个样本，其类别标记不一致的概率。因此，$Gini(D)$越小，则数据集$D$的纯度越高。属性$a$的基尼指数定义为

$$ Gini_index(D,a)=\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}Gini(D^{v}). $$

好了，总之不同的划分对应不同的决策树类型。

    ID3算法：信息增益
    C4.5算法：增益率
    CART算法：Gini指数

三、剪枝（pruning）

通过上述方法生成的决策树包含许多不必要的分支，这些分支可能是由于训练集合的噪音和异常值产生的。这导致了决策树算法可能过拟合，根据奥卡姆剃刀准则，为了防止结点划分过程不断重复，造成决策树分支过多，以至于因训练样本学的“太好”了把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合，应该考虑对决策树进行适当简化。这就是剪枝了。
剪枝的策略有两种：预剪枝（prepruning）和后剪枝（postpruning）.

预剪枝

在树完全构造出来之前提前停止树的构造。即在指决策树生成过程中，对每个结点在划分前后进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。

后剪枝

对已生成的树进行剪枝，这种策略效果好于预剪枝，打破了决策树生成时的不回溯限制。即对于从训练集中生成的一颗完整的决策树，自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

决策树就先搞到这里，虽然只是浅尝辄止，以后还会补充(～￣▽￣)～下一站——>支持向量机

参考：周志华《机器学习》