4.1基本流程

决策树是基于树结构来进行决策的，例如在西瓜问题中，对新样本的分类可看作对“当前样本属于正类吗”这个问题的“决策”过程，图4.1是西瓜问题的一棵决策树

决策树学习基本算法如图4.2所示

在决策树基本算法中，有三种情形导致递归返回：1、当前结点包含的样本全属于同一类别，无需划分 2、当前属性集为空，或是所有样本在所有属性上取值相同，无法划分 3、当前结点包含的样本集合为空，不能划分。在第2种情形下，把当前结点标记为叶结点，但类别设定为该结点所含样本最多的类别。在第3种情形下，把当前结点标记为叶节点，但类别设定为其父结点所含样本最多的类别。它们的不同点是 ，第2种是利用当前结点的后验分布，第3种则是把父结点的样本分布作为当前结点的先验分布

一个例子搞清楚（先验分布/后验分布/似然估计）转载 - 简书

4.2划分选择

图4.2中，决策树学习的关键是第8行：如何选择最优划分属性。一般希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高

4.2.1信息增益

“信息熵”是度量样本集合纯度常用的指标，样本集D的信息熵Ent(D)的值越小，D的纯度越高。定义为

利用属性a对样本集D进行划分可以得到“信息增益”，信息增益越大，使用属性a来划分获得的“纯度提升”越大。定义为

下面举一个例子来了解这两个概念：

属性“色泽”的信息增益为

4.2.2增益率

由于信息增益准则对可取值数目较多的属性有所偏好，C4.5决策树算法使用“增益率”来选择最优划分属性，定义为

IV(a)是属性a的固有值，属性a的可能取值越多(即V越大)，IV(a)的值越大，例如，在表4.1中，IV(触感)=0.874(V=2)，IV(色泽)=1.580(V=3)，IV(编号)=4.088(V=17)

由于增益率准则对可取值数目较少的属性有所偏好，C4.5算法采用先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的方法来选择最优划分属性

4.2.3基尼指数

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

在候选属性集合A中，选择使划分后基尼指数最小的属性作为最优划分属性，即

4.3剪枝处理

剪枝是决策树算法处理“过拟合”的手段。剪枝的基本策略有“预剪枝”和“后剪枝”。

预剪枝是对每个结点在划分前先进行估计，若当前结点的划分不能使决策树泛化性能提升，则停止划分并将当前结点标记为叶节点。后剪枝是先从训练集生成一棵完整的决策树，然后自底向上对非叶结点考察，若将该结点的子树替换成叶结点能使决策树性能提升，则将该子树替换成叶结点。

决策树的预剪枝与后剪枝 - zfan520的博客 - CSDN博客

4.4连续与缺失值

在决策树中使用连续属性，采用二分法对连续属性进行处理。

假设样本集D和连续属性a，a在D上有n个不同的取值，从小到大排序为{a1,a2...}。对于属性a，考察包含n-1个元素的候选划分点集合：

Gain(D,a,t)是样本集D基于划分点t二分后的信息增益，选择使Gain(D,a,t)最大化的划分点。

下面举一个例子：

4.4.2缺失值处理

对于某些属性值缺失的样本：1、属性选择：通过样本集D在属性a上没有缺失值的样本子集来判断属性a的优劣 2、样本划分：若样本x在划分属性a上的取值已知，则将x划入对应的子结点，反之则将x同时划入所有子结点，调整子结点的样本权值，相当于让同一个样本以不同概率划入不同的子结点

信息增益计算式推广为

下面举一个例子：

4.5多变量决策树

d个属性对应d维空间的一个数据点，对样本分类表示在坐标空间中找到不同样本之间的分类边界。

分类边界由若干个与坐标轴平行的分段组成，例子如下：

“多变量决策树”能实现斜的划分边界，使决策树模型简化。在多变量决策树的学习过程中，不是为非叶结点寻找最优划分属性，而是试图建立合适的线性分类器。例子如下：