表示得知特征X的信息而使得类Y的信息的不确定性减少的程度
大致步骤:
给定训练数据集D和特征A,经验熵H(D)表示对数据集D进行分类的不确定性。而经验条件熵H(D|A)表示在特征A给定的条件下对数据集D进行分类的不确定性。那么它们的差,即信息增益,就表示由于特征A而使得对数据集D的分类的不确定性减少的程度。显然,对于数据集D而言,信息增益依赖于特征,不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。
决策树 |
决策树
是什么?
描述对实例进行分类的树形结构
本质是:从训练数据集种归纳出一组分类规则,与训练数据集不想矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个,也可能一个也没有。
决策树的生成只考虑局部最优,剪枝考虑全局最优
损失函数:通常是正则化的极大似然函数。
学习步骤
特征选择
选择的准则是:信息增益或信息增益比
信息增益
表示得知特征X的信息而使得类Y的信息的不确定性减少的程度
大致步骤:
给定训练数据集D和特征A,经验熵H(D)表示对数据集D进行分类的不确定性。而经验条件熵H(D|A)表示在特征A给定的条件下对数据集D进行分类的不确定性。那么它们的差,即信息增益,就表示由于特征A而使得对数据集D的分类的不确定性减少的程度。显然,对于数据集D而言,信息增益依赖于特征,不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。
熵
条件熵
经验熵和经验条件熵
互信息
熵:表示随机变量不确定性的度量
条件熵:在已知随机变量X的条件下随机变量Y的不确定性
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵与条件熵分别称为经验熵和经验条件熵
熵与条件熵之差称为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息
信息增益比
利用信息增益作准则存在偏向于“偏向于选择取值较多的特征”问题
定义
信息增益g(D,A)与训练数据集D关于特征A的值的熵Ha(D)之比
HA(D)为训练集D关于特征A的值的熵,n是特征A的取值个数。
决策树的生成
ID3:ID3的核心是在各个结点上应用“信息增益”准则选择特征。
从根结点出发,选择信息增益最大的特征作为结点特征,由该特征的不同取值建立子结点,对子结点递归调用以上方法。直到所有特征的信息增益均很小(设一个阈值ε)或没有特征可选为止。
C4.5:对ID3算法进行了改进,生成过程中用信息增益比来选择特征。
ID3:信息增益
C4.5:信息增益比
决策树的剪枝
剪枝
学习时过多地考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树(过拟合)。
解决办法是考虑决策树的复杂度,对已生成的树进行简化,这一过程称为剪枝(pruning)。
具体地,从树上裁掉一些子树或叶结点,并将其根结点或父结点作为新的叶结点,从而简化分类树模型。
决策树的损失函数
“决策树生成”只考虑了通过提高信息增益(或信息增益比)对训练数据进行更好的拟合。而“决策树剪枝”通过优化损失函数,还考虑了减小模型复杂度。“决策树生成”学习局部的模型,而“决策树剪枝”学习整体的模型。
CART
CART假设决策树是二叉树,内部结点特征的取值为“是”和“否”,左分支是取值为“是”的分支,右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征,将输入空间即特征空间划分为有限个单元,并在这些单元上确定预测的概率分布。CART算法分为两步:
(1)决策树生成:基于训练数据集生成决策树,生成的决策树要尽量大。
(2)决策树剪枝:用验证数据集对已生成的树进行剪枝并选择最优子树,这时用损失函数最小作为剪枝的标准。
生成树
回归树:平方误差最小化,分类树:基尼指数
Gini值越大,样本集合的不确定性也越大(与熵类似)
剪枝
形成一个子树序列
通过交叉验证法在独立的验证数据集上对子树序列进行测试,从中选择最优子树。