当前位置：首页 > news >正文

决策树学习

news 2025/7/9 2:47:19

1. 背景

DT决策树是一种基本的分类与回归方法，其学习时，利用训练数据，根据损失函数最小化原则建立DT模型。
分类DT主要优点：模型具有可读性，分类速度快。

由DT树的根结点到叶结点的每一条路径构建一条规则，即组合特征，路径上内部结点
的特征对应着规则的条件，而叶结点的类对应着规则的结论。这些路径互斥且完备。
DT学习通常包括3个步骤：特征选择、DT的生成与DT的修剪。DT的生成只考虑局部最优，而DT的剪枝则考虑全局最优。

DT学习是由训练数据集估计条件概率模型，其损失函数通常是正则化的极大似然函数，其策略是损失函数为目标函数的最小化。

2. 特征选择

特征选择在于选取对训练数据具有分类能力的特征，这样可以提高DT学习的效率。通常特征选择的准则是信息增益或信息增益比。

2.1 熵

随机变量X的熵定义为 $H(p)=-\sum_{1}^{n}p_{i}logp_{i}$ (对数以2为底时，熵的单位叫bit；以e为底时，熵的单位叫nat)。

其中 $P(X=x_{i})=p_{i}$ ，i=1,2,...,n

熵只依赖于X的分布，与X的取值无关，且 $0\leq H(p)\leq logn$ 。

2.2 条件熵

H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。
即X给定条件下Y的条件概率分布的熵对X的数学期望

$H(Y|X)=\sum_{i=1}^{n}p_{i}H(Y|X=x_{i})$

其中令0log0=0

信息增益表示，得知特征X的信息而使得类Y的信息的不确定性减少的程度。

2.3 信息增益及其计算

特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差(亦叫类与特征的互信息)。

（1）计算数据集D的经验熵H(D)

$H(D)=-\sum_{k=1}^{K}\frac{|C_{k}|}{|D|}log_{2}\frac{|C_{k}|}{|D|}$

表示对数据集D进行分类的不确定性。

（2）计算特征A对数据集D的经验条件熵H(D|A)

$H(D|A)=\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}H(D_{i}) =-\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_{i}|}log_{2}\frac{|D_{ik}|}{|D_{i}|}$

表示在特征A给定的条件下对数据集D进行分类的不确定性。

（3）计算信息增益

$g(D,A)=H(D)-H(D|A)$

表示由于特征A而使得对数据集D的分类的不确定性减少的程度。

2.4 信息增益比

信息增益存在偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题
进行校正。
定义：信息增益g(D,A)与训练集D关于特征A的值的熵 $H_{A}(D)$ 之比。

即 $g_{R}(D,A)=\frac{g(D,A)}{H_{A}(D)}$

其中 $H_{A}(D)=-\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}log_{2}\frac{|D_{i}|}{|D|}$ ，n为特征A取值的个数。

3. DT的生成

3.1 ID3算法

ID3算法的核心是在DT各个结点上应用信息增益准则选择特征，递归地构建DT。具体方法如下：

从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建DT；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个DT。

ID3相当于用极大似然法进行概率模型的选择，但其只有树的生成，所以该算法生成的树
容易产生过拟合。

3.2 C4.5算法

C4.5算法对ID3算法进行了改进，在生成过程中，用信息增益比来选择特征。

4. DT的剪枝

剪枝(pruning)是将已生成的树进行简化的过程，即从已生成的树上裁掉一些子树或叶结点，
并将其根结点或父结点作为新的叶结点，从而简化分类树模型。DT的剪枝往往通过极小化DT整体的损失函数来实现。

DT学习的损失函数可以定义为： $C_{\alpha }(T)=C(T)+{\alpha }|T|$ （ $\alpha \geq 0$ ）

其中

$C(T)=\sum_{t=1}^{|T|}N_{t}H_{t}(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}log\frac{N_{tk}}{N_{t}}$ 表示模型对训练数据的预测误差；

$H_{t}(T)=\sum_{k}\frac{N_{tk}}{N_{t}}log\frac{N_{tk}}{N_{t}}$ 为叶结点t上的经验熵。

|T|为树T的叶结点个数(即模型复杂度)，t是树T的叶结点，该叶结点有 $^{N_{t}}$ 个样本点，其中k类样本点有 $N_{tk}$ 个。

参数 $\alpha \geq 0$ 控制着预测误差与模型复杂度之间的影响，较小的 $\alpha$ 促使选择较复杂的模型。

剪枝就是当 $\alpha$ 确定时，选择损失函数最小的模型(子树)。

DT生成学习局部的模型(只考虑了通过提高信息增益对训练数据进行更好的拟合)，DT剪枝学习整体的模型(通过优化损失函数还考虑了减小模型复杂度)。

利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。

5. CART算法

分类与回归树CART(classification and regression tree)模型既可以用于分类也可以用于回归(其假设DT是二叉树)。

5.1 CART生成

基于训练数据集生成DT，生成的DT要尽量大；

DT的生成就是递归地构建二叉DT的过程，对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。

5.1.1 回归树的生成

可以用平方误差来表示回归树对于训练数据的预测误差。

5.1.2 分类树的生成

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点（选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点）。

样本集合D的基尼指数 $Gini(D)=1-\sum_{k=1}^{K}\left ( \frac{|C_{k}|}{|D|} \right )^{2}$

特征A条件下集合D的基尼指数 $Gini(D,A)=\frac{|D_{i}|}{|D|}Gini(D_{1})+\frac{|D_{2}|}{|D|}Gini(D_{2})$

基尼指数Gini(D)表示集合D的不确定性，基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性。基尼指数与熵相似，其值越大，样本集合的不确定性也就越大。

5.2 CART剪枝

用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。CART剪枝算法从“完全生长”的DT的底端剪去一些子树，使DT变得简单，从而能够对未知数据有更准确的预测。

step.1 剪枝，形成一个子树序列；
step.2 在剪枝得到子树序列中通过交叉验证选取最优子树。