机器学习（五）~决策树算法
机器学习（五）~决策树算法
机器学习（五）~决策树算法
1. 决策树模型
关键步骤： 特征选择、决策树的生成、决策树的修剪
损失函数： 正则化的极大似然函数
概率模型： 由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型
- 决策树的生成考虑局部最优，决策树的剪枝考虑全局最优
常用算法： ID3、C4.5和CART
2.特征选择策略
2.1 信息增益
熵： 表示随机变量不确定性的度量；只依赖于数据分布，与取值无关；熵越大，混乱程度越大越难分类
- p=0/1时H( p )最小, p=0.5时H( p )最大
条件熵： H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，即随机变量X给定条件下随机变量Y的条件熵
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时，所对应的熵和条件熵分别称为经验熵和经验条件熵
信息增益： 表示得知特征X的信息而使得类Y的信息不确定性减少的程度
特征A对训练数据集D的信息增益 g(D,A), 定义为集合 D 的经验熵 H(D) 和特征 A 给定条件下 D 的经验条件熵 H(D|A) 之差也称互信息即
信息增益依赖于特征，信息增益大的特征具有更强的分类能力
应用： ID3的生成算法
缺点： 存在偏向于选择取值较多的特征的问题
解决办法： 信息增益率
2.2 信息增益率
(相当于除以各属性占比的熵值)
应用： C4.5的生成算法
2.3 基尼系数
Gini(D)表示集合D的不确定性；Gini(D,A)表示经A=a分割后集合D的不确定性
3.决策树算法
3.1 决策树生成
利用信息增益或其他准则进行特征选择，划分数据集，生成分类树或回归树
3.2 决策树剪枝
决策树学习的损失函数为
其中经验熵为
则损失函数可以写作：
C(T)表示模型对训练数据的预测误差(即模型的拟合程度)，|T|表示模型的复杂度
设一组叶节点回缩到其父节点之前与之后的整体树分别为TB和TA，对应损失函数C(TB)和C(TA),若C(TA)≤C(TB),则进行剪枝，将其父节点变为新的叶节点
- 剪枝，就是当α确定时，选择损失函数最小的模型，即损失函数最小的子树
- 决策树生成学习局部模型，决策树剪枝学习整体模型
- 利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择
3.3 CART算法
CART全称分类与回归树，既可用于回归也可分类
步骤：
1)决策树生成： 基于训练数据集生成决策树，生成的决策树要尽量大
2)决策树剪枝： 用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝标准
对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树
注意：一个子树对应一个α，当最优子树确定时，α也确定