模型
决策树的学习目标是根据给定的训练数据集,建立一个决策树,能够对实例进行正确分类。决策树算法通常是递归选择最优特征,使得这个特征能够最好的对数据进行分割。
一个决策树从根节点开始构建,选择最优特征,将数据分为K组,对每一个子组,再次从其他特征总选择最优的,直至达到退出条件,或数据基本不可再分。
生成的决策树可能出现过拟合现象,则需要剪枝。剪枝的基本原理是去除不必要的叶子节点,使得决策树从繁至简。
特征选择
如何评价一个特征是最优特征呢?
熵和条件熵
每一个特征对应一定的混乱程度,称为变量的熵,记作H(X)
H(x)=-∑Pi·log(Pi)
其中Pi是随机变量X可取的第i个值,熵值H(P)大于零小于等于log(N)
条件熵H(Y|X)定义为X给定条件下Y的条件概率分布的熵对X的数学期望;
如果说X的熵H(X)表示随机变量X的变化程度,H(Y|X)则表示,已知X时Y的变化程度,也就是在X的限定条件下Y的混乱程度。
信息增益
信息增益g(D,A) = H(D)-H(D|A)
这句话很好理解:特征值D有原始混乱程度,在引入新的信息A之后,D的混乱程度有所减小,信息增益表示特征A使得数据集D混乱程度减小的程度。信息增益值越大,则表示这一特征A越是具有分类能力,越是重要。
信息增益有时会由于取值问题产生偏差,故引入了信息增益比这一概念,
信息增益比是对信息增益的优化。
算法
生成决策树的最终结果应该是特征值和该特征值取值的
ID3
此算法即根据信息增益迭代计算在每个节点上,每个特征值的信息增益,从而选择出最佳特征,作为此节点的类别。
- 若数据集中所有实例属于同一类,则T为单节点树,返回T
- 若特征为空,将数据集T记为D中最大的类,返回该类
- 计算A中各个特征的信息增益,选择信息增益最大的特征Ag
- 若Ag的值小于阈值,回到2
- 对A的每一个可能值将D划分为非空子集,取其中最大的类作为标记
- 对第i个子节点,以Di为训练集,以A-{Ai}为特征集,递归调用1~5
C4.5
C4.5是用信息增益比代替了ID3中第三条的信息增益,其他都一样。
以上的算法用于生成分类决策树,对于每个可取的特征值,存在固定的类别,决策树还可以生成回归模型,对于取值在连续空间上的特征进行分类,选取最优分割点,将数据分成2类,CART算法生成的决策树树为二叉决策树。
CART
CART的特征节点满足对指定变量,取值为是或者否。一般地,左子树为是的分支,右子树为否的分支。
回归决策树的表达式
f(x) = ∑Cm·I(x∈Rm)
表达着这样的意义:回归树首先生成一个个特征,在特定的特种中选取一个最优分割点;模型表示在输入数据属于该单元时,返回该单元的值。
由于对于某一个固定的变量,其最优分割点是所有输入实例Xi对应的输出Yi 的算数平均值。选取最优特征和该特征的最优分割点在于求最小化值:
min[min∑(Yi-C1)^2 + min∑(Yi-C2)^2]
剪枝
对于CART树,剪枝的核心是从当前回归树的所有子树种选取【整体损失函数最小,也就是预测能力最强的】最优决策树。
网友评论