4.1-基本流程

1-基本概念

决策树decision tree：基于树的结构来进行的决策。
算法原理：在分类问题上，从逻辑角度，表示基于特征对实例进行分类的过程，可以认为是if-then的集合。从几何角度可以认为是定义在特征空间与类空间上的条件概率分布。
决策树结构：下图所示的西瓜分类决策树（我感觉更像树的根，可以称为决策根），一个完整的决策树由三部分组成：
1，根节点：树的最顶端的节点，如色泽。
2，叶子节点：树最底部的那些节点，也就是决策结果，好瓜或者坏瓜。
3，内部节点：除了叶子节点的，都是内部节点，如根蒂，表示属性特征。

2-基本算法流程

决策树的目标是在给定的训练数据集的基础上，建立一个泛化能力强的决策树模型，样本越分越纯。
基本流程：遵循简单直观的分而治之策略。
决策树的三个步骤：特征选择、决策树生成、决策树修剪。

如上图所示，对于决策树学习的基本算法，决策树的生成是一个递归的过程。在决策树算法中，以下三种情况会导致递归返回：
1，当前节点包含的样本全属于同一类别，无需划分；
2，当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；
3，当前结点包含的样本集合为空，不能划分。
情形2，把当前结点标记为叶结点，井将其类别设定为该结点所含样本最多的类别，利用当前结点的后验分布。
情形3，把当前结点标记为叶结点，且将其类别设定为其父结点所含样本最多的类别，把父结点的样本分布作为当前结点的先验分布。

4.2-划分选择

1-补充知识

– 参考香农的信息论
信息熵 information entropy:假设离散随机变量x的取值有,其发生的概率为,那么信息熵为：
信息熵用于描述源的不确定性。概率越大，可能性越大，但信息量越小，不确定性越小，熵越小。
举个例子：假如说天气预报说明天下雨的概率是,那明天下雨的可能性就很大，也就意味着不确定性很小；假如说明天下雨的概率是100%，那就没有不确定性。
条件熵：条件熵表示在已知随机变量X的条件下随机变量Y的不确定性。即：(X,Y)发生的熵，减去X单独发生的熵，就是在X发生的前提下，Y发生新带来的熵，有点类似于贝叶斯公式。
它们的关系公式如下：

相对熵：又称互熵，交叉熵，鉴别信息，Kullback熵，Kullback-Leible散度。设p(x)，q(x)是随机变量X中取值的两个概率分布，则p对q的相对熵为：

互信息：两个随机变量X和Y的互信息，定义为X，Y的联合分布和独立分布乘积的相对熵。

几个参数之间的关系如下图所示： 后面的坑填充具体推导。

将信息论中的内容引入到决策树中，便产生以下算法，不得不说，香农真NB！
信息增益 ==> 信息熵，互信息

2-ID3算法与信息增益

在决策树中，信息熵是用来衡量样本集纯度的指标。

的值越小，则D的纯度越高。
信息增益：指互信息的概念。
信息增益公式：

特征a对训练数据集D的信息增益g(D,a)，定义为集合D的经验熵H(D)与特征a给定条件下D的经验条件熵H(D|a)之差：

熵H(D)与条件熵H(D|a)之差成为互信息,决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
信息增益是互信息：它表示在一个随机变量的信息已知后，另一个随机变量的不确定性降低的程度。一般来说，信息增益越大，一个随机变量降低另一个随机变量不确定性的程度就越大，这意味着样本的纯度越高。
ID3决策树算法就是以信息增益为准则来选择划分特征。

3-C4.5算法与增益率

由于信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，引入了C4.5决策树优化算法，并引入了信息增益率。

IV(a)称为属性α 的”固有值”，属性α 的可能取值数目越多(即V 越大)，则IV(α) 的值通常会越大。
C4.5算法：由于信息增益偏向于属性多，增益率对可取值数目较少的属性有所偏好。为了更准确，采用先选出信息增益高平均水平的属性，再选择信息增益率最高的。

4-CART算法与基尼指数

CART 决策树使用Gini指数来选择划分属性，基尼指数表示了在样本集合中，一个随机选中的样本被分错的概率。公式如下：


Gini(D) 反映了从数据集D 中随机抽取两个样本，其类别标记不一致的概率.因此，Gini(D) 越小，则数据集D 的纯度越高。
关于基尼系数的理解，我在写笔记的时候看到了一种通俗易懂的方法，如参考3：
我们都知道信息熵的定义是：

那么基尼系数其实就是把换成，画出两者的图像：

基尼系数对于信息熵而言，就是在01区间内近似的用切线来代替了对数函数。因此，既然信息熵可以表述不确定度，那么基尼系数自然也可以，只不过存在一些误差。

4.3-剪枝处理

剪枝(pruning)：是决策树学习算法对付”过拟合”的主要手段。

1-预剪枝

预剪枝（prepruning）：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
特征：
1，预剪枝使得决策树的很多分支都没有”展开，降低过拟合风险，显著减少了时间开销。
2，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高
3，预剪枝基于”贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

2-后剪枝

后剪枝（post-pruning）：先生成一棵决策树，然后自底向上地对非叶结点进行验证，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
特征：
1，通常比预剪枝决策树保留了更多的分支. 一般情形下后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树.
2，但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

参考：

1,统计学习方法
2,信息论
3,决策树与随机森林（从入门到精通）