决策树.png
1.基本流程
性质：决策树是基于树形结构来进行决策的，一颗决策树包含一个根结点、若干个内部结点和若干个叶节点。叶结点对应决策结果、其他结点对应属性测试
目的：产生一棵泛化能力强，即处理未见示例能力强的决策树
基本流程：遵循简单且直观的“分而治之”策略
2.划分选择
结点的纯度：决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度越来越高,划分指标：信息增益、增益率、基尼指数.
（1）信息增益
信息熵：度量样本集合纯度最常用的一种指标。Ent(D)的值越小，则D的纯度越高
熵代表一个系统中蕴含多少信息量，信息量越大表明一个系统不确定性就越大，就存在越多的可能性。当样本中某类样本均匀分布时，这时信息熵最大，纯度最小；假设样本中只有一类样本，此时信息熵最小，纯度最大。
image.png
信息增益：即样本数越多的分支结点的影响越大。信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。我们可用信息增益来进行决策树的划分属性选择
image.png
偏好：对可取值数目较多的属性有所偏好
算法例子：ID3决策树
eg：利用信息增益画出决策树
image.png
该数据集包含17个训练样例，其中正例占8份，反例占9份，可计算出根结点的信息熵：
image.png
再按属性色泽来进行划分，求出三个根结点不同颜色的信息熵：
image.png
然后根据公式计算色泽的信息增益：
image.png
按以上步骤计算出其他属性的信息增益，选择数值最大的作为划分属性，生成的决策树如下：
image.png
（2）增益率
基于信息增益的缺点，C4.5 算法不直接使用信息增益，而是使用一种叫增益率的方法来选择最优特征进行划分。从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的
image.png
IV(a)称为属性a的固有值，是特征 a 的熵，属性a的可能取值数目越多（即V越大），则IV(a)的值通常会越大
image.png
偏好：对可取值数目较少的属性有所偏好
算法例子：C4.5决策树
（3）基尼系数
假定当前样本集合 D 中第 k 类样本所占的比例为 pk，数据集D的纯度可用基尼值来度量。Gini(D)越小，则数据集D的纯度越高
image.png
属性a的基尼指数定义为：
image.png
偏好：在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性
算法例子：CART决策树
3.剪枝处理
目的：剪枝是决策树学习算法对付“过拟合”的主要手段，通过主动去掉一些分支来降低过拟合的风险
基本策略：
(1).预剪枝--对每个结点在划分前先进行估计，若当前结点不能提升泛化性能，则停止划分
优点：a.降低过拟合风险；b.显著减少决策树的训练时间开销和测试时间开销
决策树桩：一棵仅有一层划分的决策树
(2).后剪枝--在训练集生成的决策树中自底向上对非叶结点进行考察，若该结点对应的子树替换叶结点能提升泛化性能，则用该子树代替叶结点。
优点：a.欠拟合风险小；b.泛化性能往往优于预剪枝决策树
缺点：训练时间开销比未剪枝决策树和预剪枝决策树都要多
4.连续值与缺失值
(1)连续值处理：
采用二分法对连续属性进行处理，二分法是C4.5决策树算法中采用的机制，其中Gain(D,a,t)是样本D基于划分点t二分后的信息增益。我们可选择使Gain(D,a,t)最大化的划分点
注意：与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性
(2)缺失值处理
问题：
1.如何在属性值缺失的情况下进行划分属性选择？
2.给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分
对于问题1的解决方案：我们可根据样本在属性a上没有缺失值的样本子集来判断属性a的优劣
对于问题2的解决方案：若样本x在划分属性a上的取值已知，则将x划入与其取值对应的子结点，且样本权值在于结点中保持为wx。否则，让同一个样本以不同的概率划入到不同的结点中去
5.多变量决策树
特点：轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。使得学习结果有较好的可解释性
缺点：要进行大量的属性测试，预测时间开销会很大
决策树对复杂分类边界的分段近似，使用斜的划分边界则决策树模型将大大简化
多变量决策树--斜决策树：把轴平行的划分边界改为斜划分
网友评论