机器学习笔记5-决策树

小编 2026-06-05 阅读:864 评论:0

机器学习笔记5-决策树决策树是一种基本的分类与回归方法。决策树学习通常包括三个步骤：特征选择、决策树的生成和决策树的剪枝。一般一个决策树包含一个根结点，若干个内部结点和若干个叶结点。叶结点对...

机器学习笔记5-决策树

决策树是一种基本的分类与回归方法。决策树学习通常包括三个步骤：特征选择、决策树的生成和决策树的剪枝。一般一个决策树包含一个根结点，若干个内部结点和若干个叶结点。叶结点对应于决策结果，其它的每个结点则对应于一个属性测试。每个结点包含的样本集合根据属性测试的结果被分到子结点中。根结点包含样本全集。

特征选择。特征选择会选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率。通常特征选择的准则是信息增益或信息增益比。
(1)信息增益
在信息论与概率统计中，熵(entropy)表示随机变量不确定性的度量，它由变量的分布决定，与变量的取值无关。假设X是一个取有限个值的离散随机变量，其概率分布为
$P(X = {x_i}) = {p_i},i = 1,2, \\cdots ,n$
则其熵定义为
$H(X) = - \\sum\\limits_{i = 1}^n {{p_i}\\log {p_i}}$
熵越大，随机变量的不确定性就越大。设有随机变量 $(X,Y)$ ，其联合概率分布为
$P(X = {x_i},Y = {y_i}) = {p_{ij}},i = 1,2, \\cdots ,n{\\rm{; }}j = 1,2, \\cdots ,n$
条件熵 $H(Y|X)$ 表示在已知随机变量X的条件下随机变量 $Y$ 的不确定性，定义为X给定条件下Y的条件概率分布的熵对X的数学期望
$H(Y|X) = \\sum\\limits_{i = 1}^n {{p_i}} H(Y|X = {x_i})$
${p_i} = P(X = {x_i}),i = 1,2, \\cdots ,n$
信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。特征A对训练数据集D的信息增益 $g(D,A)$ ，定义为集合D的熵 $H(D)$ 与特征A给定条件下D的条件熵 $H(D|A)$ 之差，即
$g(D,A)=H(D)-H(D|A)$
(2)信息增益比
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题进行校正。特征A对训练数据集D的信息增益比 $g_R(D,A)$ 定义为信心增益 $g(D,A)$ 与训练数据集D关于特征A的值的熵 $H_A(D)$ 之比，即 ${g_R}(D,A) = \\frac{{g(D,A)}}{{{H_A}(D)}}$
决策树生成
(1)ID3算法。利用信息增益选择特征，递归地构建决策树。具体地，从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同值建立子结点；再对子结点递归地调用以上方法，构建决策树。直到所有特征的信息增益均很小或没有特征可以选择为止。其中，建立子结点，计算新的信息增益是以子结点所包含的数据集为基础来计算的。
(2)C4.5算法。该算法与ID3算法类似，但采用了信息增益比来选择特征。
决策树的剪枝
决策树学习时会过多考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，造成过拟合。这时候就需要剪枝，在已生成的树上裁掉一些子树或叶结点，从而提高泛化能力。决策树的剪枝可以通过引入正则化来实现，如定义决策树的损失函数为：
${C_\\alpha }(T) = \\sum\\limits_{t = 1}^{|T|} {{N_t}{H_t}(T) + \\alpha |T|}$ （可理解为叶结点的熵加正则化）
其中叶节点的个数为 $|T|$ ，每个叶结点有 $N_t$ 个样本点，其中k类的样本点有 $N_{tk}$ 个， ${H_t}(T) = - \\sum\\limits_k {\\frac{{{N_{tk}}}}{{{N_t}}}\\log \\frac{{{N_{tk}}}}{{{N_t}}}}$ ，令 $C(T) = \\sum\\limits_{t = 1}^{|T|} {N_t}{H_t}(T)$ ，这时 $C_\\alpha(T)=C(T)+\\alpha|T|$ 。 $C(T)$ 表示模型对训练数据的预测误差， $|T|$ 表示模型复杂度。损失函数完成了两者的平衡。
树的剪枝算法：（1）计算每个结点的熵；（2）递归地从树的结点回缩，计算回缩前后的损失函数，如果变小则进行剪枝，即将父结点变为新的叶结点；（3）返回（2）直到不能继续，得最小的子树。

补充
CART算法
CART（分类与回归树）模型也是基于以上三个步骤，既可以用于分类，也可用于回归。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”。这样决策树递归地二分每个特征。

CART生成
CART在特征选择时，对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则。
(1)回归树的生成
回归树对应着输入空间（即特征空间）的一个划分以及在划分单元上的输出值。当输入空间划分确定时，可以用平方误差 $\\sum\\limits_{{x_i} \\in {R_m}} {{{({y_i} - f({x_i}))}^2}}$