一图胜千言
一个女孩找相亲对象的决策逻辑
EricZhang 的博客这便是决策树的核心思想:基于训练数据学习出一个含有决策逻辑的树
然后用这个决策树进行分类预测
其中常见的学习算法有 ID3、C4.5、CART
下面内容需要一定的概率与数理统计基础
信息论
设定X是一个取有限个值的随机变量
则随机变量X的熵定义为
熵越大,随机变量的不确定性就越大。事件的确定性越高,熵就越小,比如必然事件的熵为0。
条件熵表示已知X的条件下Y的不确定性
定义为X给定条件下Y的条件概率分布的熵对X的数学期望
当对X的概率密度是由极大似然估计(基于频率估计)得到时,熵被成为经验熵。
设训练数据集D,特征A
信息增益定义为经验熵与经验条件熵之差
信息增益比定义为信息增益和的经验熵的比值
ID3 & C4.5
ID3的核心思想为选择信息增益最大的特征进行递归分类
输入训练数据集D,特征集A,阈值 ε
输出决策树T
(1) 若 D 中所有实例属于同一类C(k),则返回单节点树,并标记类别为C(k)
(2) 若A为空集,则返回单节点树,并将D中实例数最多的类别C(k)作为分类标记
(3) 否则,使用极大似然估计计算特征集A的信息增益,选择增益最大的特征A*
(4) 如果信息增益 g(A*, D) < ε ,则返回单节点树,并将D中实例数最多的类别C(k)作为分类标记
(5) 否则,对A*的每一种取值将D划分为若干个子集D(i),并将D(i)中实例数最多的类别C(k)作为分类标记,构建子节点。
(6) 对于第i个子节点,以D(i)为训练集,A - {A*}特征集,递归调用(1) ~ (5),得到子树T(i)
为什么选择信息增益大的特征作为划分?
对于待划分的数据集D,其 H(D) 是一定的,但是划分之后的熵 H(D|A) 是不定的,H(D|A) 越小说明使用此特征划分得到的子集的不确定性越小(也就是纯度越高),因此 H(D)-H(D|A) 差异越大,说明使用当前特征划分数据集D的话,其纯度上升的更快。
C4.5
C4.5和ID3的区别为——使用信息增益比而不是信息增益选择特征
这是因为ID3算法存在一个问题,就是偏向于多值属性。例如,如果存在唯一标识属性ID,则ID3会选择它作为分裂属性,这样虽然使得划分充分纯净,但这种划分对分类几乎毫无用处。C4.5使用信息增益比试图克服这个偏倚。
信息增益比的本质: 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时,惩罚参数较小;特征个数较少时,惩罚参数较大。
惩罚参数:数据集D以特征A作为随机变量的熵的倒数,即将特征A取值相同的样本划分到同一个子集中(而同通常所说数据集的熵是依据类别进行划分的)
惩罚参数C4.5 剪枝
C4.5决策树生成算法递归的产生决策树,直到不能继续下去。这样产生的决策树往往对训练数据的分类很准确,却容易出现过拟合现象,所以有时候我们需要简化决策树,减少模型的拟合程度。通常方法是减去一些不必要的枝叶。
此处不介绍具体算法
CART(分类与回归树)
分类和回归树的意思是CART分为回归树算法和分类树算法
首先我们要知道的是CART假设决策树视为一颗二叉树(C4.5 是多叉树)
其次CART算法分为两个组成部分:
(1) 基于训练数据集生成决策树,要尽可能大
(2) 使用CART剪枝算法简化决策树
CART分类树
和C4.5不同的是,CART分类树使用基尼指数作为划分特征选择的标准
基尼指数定义基尼指数越大表示不确定性越大,这点和熵是类似的。
因为CART假设决策树唯一一颗二叉树,所以生成算法和C4.5也有些不同
主要区别是对于每一个特征计算A,对其每个可能取值a,用“是”、“否” A = a 划分为两个子集计算基尼指数(C4.5是计算特征A的条件熵)
CART剪枝 —— CCP方法
CCP方法选择节点误差率增益值最小的非叶子节点,删除该非叶子节点的左右子节点。
子树的损失函数
误差率增益值
α 就是误差率增益值,因为 α 越大意味着剪枝前后预测误差 C(T)变化越大!
步骤
注意:若有多个非叶子节点的表面误差率增益值相同小,则选择非叶子节点中子节点数最多的非叶子节点进行剪枝。
CART回归树
回归树把输入空间划分为多个单元,并且给出对应的输出值。与之类似的算法是线性回归
举个例子
给出一个人的健康指标X。先做多次二分类,最后每个叶结点对应的不再是类别,而是该结点下所有样本的健康系数均值,作为对这些样本健康系数的预测y。
推导
给定训练数据集
假设回归树将输入空间划分为M个单元[R1,R2...Rm],每个单元对应的输出值为Cm,于是回归树模型可表示为
Cm的取值
对于单元Rm,设其预测误差为
使 Cm* = Rm单元中所有样本的 y 值的平均值,即可使这个误差最小化
选择划分特征
和C4.5算法一样,CART回归树也需要选择一个特征进行子树划分
CART回归树生成算法
参考
《统计学习方法》
http://www.cnblogs.com/muzixi/p/6566803.html
http://www.cnblogs.com/fionacai/p/5894142.html
http://www.jianshu.com/p/b90a9ce05b28
网友评论