决策树作为一种解释性好, 训练效率高, 理解简单的机器学习算法, 在特征选择等领域用的非常广泛.
算法释义
决策树通过递归地进行特征选择, 将训练集数据 D 进行分类最终生成一颗由节点和有向边组成的树结构. 其中结点分为两种类型: 内部节点和叶节点, 内部结点表示一个特征, 叶结点表示一个类别.
算法步骤
输入: 训练集 D, 特征集 A
输出: 决策树 T
(1) 生成叶节点:
a. 若 D 中所有实例属于同一类 C, 则 T 为单结点树, 并将 C 作为该节点的类标记, 返回 T
b. 若特征集 A 为空, 则 T 为单结点树, 并将 D 中实例最多的类 C 作为该节点的类标记, 返回 T
c. 其他终止条件下, 则 T 为单结点树, 并将 D 中实例最多的类 C 作为该节点的类标记, 返回 T
(2) 特征选择: 根据某种标准, 在特征集 A 中选择一个特征 a 和划分, 然后将训练集划分为 n 份, 其对应的特征集 A = {A - a}
(3) 递归生成: 对 (2) 中划分之后的的训练集分别调用该算法.
特征选择
特征选择在于选取对训练数据具有分类能力的特征, 如果特征选择的结果和随机分类的结果错误率没有什么差别的话, 就认为这样的特征选择是失败的, 相反, 如果特征选择使得决策树的叶节点内部基本都属于同一个类别, 显然这样的特征选择错误率是很低的, 也就是说决策树的叶节点的 "纯度" 要越高越好, 那么数学上怎么去衡量这样的 "纯度" 呢? 下面引入熵的概念.
熵和条件熵
在信息论和概率统计中, 熵是表示随机变量不确定性的度量, 假设随机变量 Y 是一个取有限个值得离散随机变量, 其概率分布有:
那么随机变量 Y 的熵的定义是:
不难看出, 如果随机变量的纯度越高, 那么其熵越小, 相反如果随机变量的不确定越大, 则其熵也越大.
条件熵 H(Y|X) 表示在已知随机变量 X 的条件下随机变量 Y 的不确定性:
信息增益
信息增益 g 借助熵和条件熵, 用来形象的表示特征选择对分类 "纯度" 的提升:
在决策树的特征选择中:
决策树算法 ID3 就是采用信息增益来做特征选择的.
信息增益比
用信息增益作为判别标准时, 会存在偏向于选择取值较多的特征的问题, 为了避免这个问题, 可以在信息增益的基础上除以一个惩罚参数, 惩罚参数是训练数据集 D 关于特征 A 的值的熵:
决策树算法 C4.5 就是基于信息增益比来做特征选择的, 但它并不是直接选择信息增益比最大的特征作为划分属性的, 因为信息增益比会对可取数值较少的属性有偏好, 因此它采用的是一种启发式: 先从候选划分属性中选择信息增益高于平均水平的属性, 再从中选择信息增益比最高的划分属性.
基尼系数
除了熵之外, 还可以用基尼系数来描述数据集的 "纯度":
显然, 基尼系数越小, 数据集的 "纯度" 越高, 对于给定的数据集, 其基尼系数为:
在对特征 A 做二类属性划分是, 其划分后的基尼系数可表示为:
CART 分类决策树就是采用基尼系数做特征选择, 每一轮都会选择使基尼系数最小的划分属性.
剪枝
在决策树学习中, 为了尽可能正确的分类训练样本, 很容易造成决策树分支过多, 从而把训练集自身的一些特点当作数据具有的一般性质, 从而导致过拟合, 因此为了对付过拟合, 可以使用剪枝来减少决策树的复杂度, 从而降低过拟合的风险. 按照剪枝与决策树生成的关系, 可以分为预剪枝和后剪枝.
预剪枝
预剪枝是在决策树的生成过程中, 对每个节点在划分前先进行估计, 如果当前结点不能带来泛化性能的提升, 则停止划分并将该结点标记为叶结点.
判断泛化性能可以采用留出法, 训练前先留出一部分数据用作测试集, 然后用决策树在测试集上的性能表示其泛化性能.
预剪枝不仅能降低过拟合的风向, 而且还减少了决策树的训练时间, 但是它也存在欠拟合的风险, 因为预剪枝属于一种 "贪心" 本质的算法, 有些分支划分可能暂时降低了泛化性能, 但是其子结点的划分却有可能带来泛化性能的提升, 而这时预剪枝无法预知的.
后剪枝
后剪枝是在完整的决策树生成之后, 自底向上地对内部结点进行考察, 若把该结点替换成叶结点能带来泛化性能的提升, 则把该结点替换成叶结点.
相对于预剪枝, 后剪枝算法可以降低欠拟合的风险, 但是它需要在生成整颗决策树之后对所有内部结点进行逐一考察, 因此其训练时间比预剪枝大的多.
连续与缺失值
连续值处理
采用连续值离散化技术, 把连续值通过一个阈值作为划分点进行划分.
缺失值处理
C4.5 算法在应对缺失值时, 首先计算信息增益时, 用无缺失值的训练子集计算信息增益, 然后乘以无缺失值的密度, 当成属性划分的依据; 然后在做划分时, 根据各个类别所占的比例, 将有缺失值数据按照比例划分到子结点.
CART
pass
参考文献
统计学习方法, 李航
机器学习, 周志华
来源: http://www.jianshu.com/p/6283054403af