第四章 决策树算法
一、基本流程
一般决策树包含一个根节点,若干个内部节点和若干个叶节点;叶节点对应于决策结果,其他每个节点则对应于一个人属性;每个节点包含的样本集合根据属性测试的结果被划分到子结点中;根节点包含样本全集,
目的:为了产生一颗泛化能力强,即处理未见示例能力强的决策树,其基本流程遵循简单且直观的“分而治之”策略;
西瓜问题的决策树:
决策树算法:
二、划分选择
算法关键:如何选择最优划分属性
1、信息增益
信息熵:度量样本集合纯度的一种指标
假定当前样本集合
中第 类样本所占的比例为 Pk (k = 1, 2,. . . , IYI) ,则的信息熵定义为
算法:
Ent(D)的值越小,则D的纯度越高。
信息增益 (对数目骄较多的属性有所偏好)
算法:
增益率:对数目较少的属性有所偏好
Ⅳ(α)称为α的“固有值”属性α的可能取值数目越多(即 α越大),则 IV(α) 的值通常会越大.
基尼指数:
基尼值:从数据集D中随机抽取两个样本,起类别标记不一致的概率。
直观来说Gini(D)反映了从数据集D中随机抽取两个样本,其类别标记不一致的概率,Gini(D)越小,则数据集D的纯度越高。
基尼指数:一般,选择使划分后基尼系数最小的属性作为最优化分属性
三、剪枝处理
剪枝是决策树学习算法对付“过拟合”的主要手段,目的 通过主动去掉一些分支来降低过拟合的风险。
预剪枝:在决策树生成过程中,对每个节点在分裂前进行估计,若当前节点的划分不能带来决策树泛化性能提升,则停止分裂,并将当前节点标记为叶节点并返回。下图是针对西瓜数据集的预剪枝处理,可以发现比原决策树精简了很多。
后剪枝:先通过算法生成一棵完整的决策树,然后自底向上的对非叶节点进行考察,若将该节点对应的子树替换为叶节点能带来决策树泛化能力的提升,则将该子树替换为叶节点。下图是针对西瓜数据集的后剪枝处理
四、连续值于缺失值
连续值处理方法:
特征属性如果是连续值的话,可取值数目是无限的,不能按照离散值那样通过可取值数目来进行节点划分,最常用的办法是二分法。
数据集D和连续值属性a,假设a在D中出现了n个不同的取值,先把这些值从小到大排序,可以考察包含n-1个候选划分点集合:
即把每两个取值点的中位点作为候选划分点,然后计算每个划分点之后的信息增益,选取信息增益最大的划分点进行分裂,也就是需找使Gain(D,a,t)最大的划分点。
缺失值处理:需要解决的两个问题
(1) 如何在属性值缺失的情况下进行划分属性选择
(2) 给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分
假设有训练集D和属性a,D表示D中在属性a上没有缺失值的样本集合(有效样本集合),属性a有V个取值{a1,a2,…..av},每个取值的样本数为Dv, Dk表示D中第k类样本子集,为每个样本x赋予一个权重wx(初始化为1), 因此有
p(rho)表示无缺失值样本所占的比例,pk表示无缺失值样本中第k类样本所占的比例,rv表示无缺失值样本中在属性a上取值av的样本所占的比例
所以针对问题一解决方案:
针对问题二解决方案:
如果样本x在属性a上取值已知,则把x划分到与其取值对应的子结点,并且样本权值在子结点中保持为wx; 如果样本x在属性a上取值未知,则将x同时划分到所有子结点,并且样本权值在与属性值av对应的子结点中调整为rv~乘以wx,也就是说让同一个样本以不同的概率划入到不同的子结点中去。
五、多变量决策树
也叫‘斜决策树’,非叶子结点不再是针对单个属性,而是对属性的线性组合进行测试,也就是说每个非叶子结点都是一个形如的线性分类器,wi和t可以在该结点所含的样本集和属性集上学得。
决策树形成的分类边界有一个明显的特点:轴平行,即它的分类边界由若干个与坐标轴平行的分段组成,如下图所示:
以上的分类边界使得分类结果有较好的解释性,但是在学习任务的真是分类边界比较复杂时,必须划分很多段才可以较好的近似,此时的决策树回很复杂,由于要进行大量的属性测试,预测时间的开销会变得非常大,如下图所示:
若能够使用上述红色边界,那么决策模型将会大大简化。“多决策变量树”即可实现这样的划分。
在此类决策树当中,非叶结点不再是仅针对某一个属性,而是对多个属性的线性组合进行测试。
换句话说,每个非叶结点是一个形如
的线性分类器。
d个属性描述的样本对应d为空间的一个数据点,a代表各个属性,wi 和 t 都是结合该样本集和属性集上学习到的。
与“传统单变量决策树”不同,在多变量决策树的学习过程中,不是为每个非叶结点寻找一个最优划分属性,而是试图建立一个合适的线性分类器,如下图所示: