决策树、随机森林

决策树

决策树是一个预测模型，它代表的是对象属性与对象值之间的一种映射关系。

树中每个节点表示某个对象，而每个分叉路径则代表某个可能的属性值，而每个叶节点则对应从根节点到该叶节点所经历的路径所表示的对象的值。

决策树视图

决策树是一树状结构，它的每一个叶节点对应着一个分类，非叶节点对应着在某个属性上的划分，根据样本在该属性上的不同取值将其划分成若干个子集。对于非纯的叶节点，多数类的标号给出到达这个节点的样本所属的类。构造决策树的核心问题是在每一步如何选择适当的属性对样本做拆分。对一个分类问题，从已知类标记的训练样本中学习并构造出决策树是一个自上而下，分而治之的过程。

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

属性选择

信息熵

信息熵是用来衡量信息量或不确定性的一个度量。在信息理论中，熵被用来表示随机变量不确定性的程度，也就是说，它衡量了信息的"混乱度"。

对于一个离散随机变量XX，其信息熵H(D)H(D)定义为:

H(D)=−∑i=1nP(xi)logbP(xi)H(D)=-\sum_{i=1}^{n}P_{(x_i)}log_bP_{(x_i)}

其中P(xi)P_{(x_i)}是随机变量取特定值xix_i的概率，nn是可能的结果数量，而logblog_b是以bb为底的对数（一般是2）
实际应用中，会将概率用频率替代

H(D)=−∑k=1K∣Ck∣∣D∣log2∣Ck∣∣D∣H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}

信息熵越高，表示随机变量的不确定性越大，即其可能的结果越难以预测。一个不太可能发生的事件（低概率）提供的信息量更大，相应地会增加熵值。

条件熵

条件熵的定义是：定义为X给定条件下，Y的条件概率分布的熵对X的数学期望
解释为：
条件熵H（Y|X）表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵H(Y|X)

H(Y∣X)=∑x∈Xp(x)H(Y∣X=x)=−∑x∈Xp(x)∑y∈Ylog(p(y∣x))=−∑x∈X∑y∈Yp(x,y)log(p(y∣x))H(Y|X)=\sum_{x\in X}p(x)H(Y|X=x)\\ =-\sum_{x\in X}p(x)\sum_{y\in Y}log(p(y|x))\\ =-\sum_{x\in X}\sum_{y\in Y}p(x,y)log(p(y|x))

这个条件熵，是指在给定某个数（某个变量为某个值）的情况下，另一个变量的熵是多少，变量的不确定性是多少

想要深究可以看这篇文章：通俗理解条件熵 - 知乎 (zhihu.com)

信息增益(ID3算法)

信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。举个例子，比如你要出去玩，然后会考虑三个特征：天气，有没有漂亮女孩子。当我告知你天气，你觉得热的话可以玩桌游，凉快的话可以打篮球，可见天气对你做决策的影响不大，也就是天气这个特征的信息增益小。而告知你有漂亮女孩子时，你打电话告诉我你九成要去，那说明有没有漂亮女孩子这个特征对你来说很重要，信息增益很高。

具体一点说就是：对于已知的事件𝐴来说，事件𝐷的信息增益就是𝑫的信息熵与𝑨事件下𝑫的条件熵之差。𝑨对𝑫的影响越大，条件熵𝑯(𝑫∣𝑨)𝑯(𝑫|𝑨)就会越小（在事件𝑨的影响下，事件𝑫被划分得越“纯净”），体现在信息增益上就是差值越大，进而说明事件𝑫的信息熵下降得越多。

GainA(D)=H(D)−H(D∣A)Gain_A(D)=H(D)-H(D|A)

所以，在根节点或中间节点的变量选择过程中，就是挑选出各自变量下因变量的信息增益最大的。

image-20240101230139178

image-20240101230131750

信息增益率(C4.5算法)

以信息增益作为划分训练数据集的特征，存在信息增益会偏向于取值较多的字段的问题。使用信息增益比可以对这一问题进行校正

比如，当我选择房贷那个表格中的ID作为特征时，那么ID将会成为最优特征。因为ID给定就相当于知道了类别，ID的信息增益很高。但实际上我们直到ID对于我们划分类别并没有什么卵用。使用增益比就是为了解决这种问题。也可以这样理解，如果经验熵是100，条件熵是10，那么信息增益为90.如果经验熵是10，条件熵是5，那么信息增益为5.如果按照信息增益的观点，那么我们倾向于选择经验熵为10 的特征。但是从另外一种角度思考的话，第一种只是降低了10%的不确定性，而第二种降低了50%，我们应该选择第二种。

房贷信息

信息增益比的定义为

Gain−RatioA(D)=GainA(D)HAGain-Ratio_A(D)=\frac{Gain_A(D)}{H_A}

HAH_A为：

HA(D)=−∑i=1n∣Di∣∣D∣log2∣Di∣∣D∣H_A(D)=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}

其中，HAH_A为事件𝐴的信息熵。事件𝐴的取值越多，GainA(D)Gain_A(D)可能越大，但同时HAH_A也会越大，这样以商的形式就实现了GainA(D)Gain_A(D)的惩罚。

image-20240101235302113

CART（Gini）

C4.5算法使用信息增益率和ID3信息增益算法实现根节点或中间节点的字段选择，但都只能针对离散型因变量进行分类，但不能处理连续型因变量，所以发展出了CART算法，当特征选择的时候使用的是基尼指数，那么可以用作分类，如果使用的均方差那么可以用作回归。下方介绍用作分类的CART

GINI系数

首先是CART（GINI）模型的特点：

  1. 与ID3或C4.5等生成多叉树的算法不同，CART总是生成二叉树。每个节点分裂成两个子节点，使得树的结构更加简洁和平衡。
  2. CART模型包含剪枝过程，可以通过代价复杂度剪枝（Cost-Complexity Pruning）来防止过拟合。

CART模型训练过程

跟普通的决策树模型一样，CART模型也会进行属性选择、递归分裂和决策树剪枝

属性选择：

  1. 计算分裂指标：CART模型使用不同的指标来选择最佳的分裂属性。对于分类问题，它使用基尼不纯度（Gini Impurity）；对于回归问题，则使用最小化均方误差。
  2. 评估每个属性：对于数据集中的每个属性（特征），CART算法会计算如果按照这个属性进行分裂，会产生多大的纯度提升（对于分类问题）或误差减少（对于回归问题）。
  3. 选择最佳属性：算法会比较各个属性的分裂指标，选择能够最大化纯度提升或最小化误差的属性作为分裂属性。

递归分裂：

  1. 分裂节点：按照属性选择的结果，将当前节点的数据集分裂成两个或多个子集。在CART模型中，这通常是一个二元分裂，即每次分裂创建两个子节点。
  2. 递归应用：对每个生成的子节点，再次应用属性选择和递归分裂的过程。每个子节点都会考虑作为下一个分裂的候选节点。
  3. 停止条件：这个递归过程会持续进行，直到满足某些停止条件，比如树达到最大深度、节点包含的数据量小于最小分裂阈值、节点的纯度达到一定水平等。
  4. 生成决策树：最终，当所有节点都满足停止条件时，递归过程结束，生成完整的决策树。

GINI系数指数

基尼指数定义

Gini(p1,p2,…,pk)=∑k=1Kpk(1−pk)=∑k=1K(pk−pk)2=1−∑k=1Kpk2Gini(D)=1−∑k=1K(∣Ck∣∣D∣)2Gini(p_1,p_2,\dots,p_k)=\sum_{k=1}^{K}p_k(1-p_k)=\sum_{k=1}^{K}(p_k-p_k)^2=1-\sum_{k=1}^{K}p_k^2\\ Gini(D)=1-\sum_{k=1}^{K}(\frac{|C_k|}{|D|})^2

基尼指数的值介于0和1之间，其中0表示数据集完全纯净（所有实例都属于同一个类别），1表示数据集完全混杂（每个类别的实例均匀分布）Gini(D)越小，则数据集D的纯度越高

因为要选属性特征，所以需要计算条件基尼指数

Gini(D∣A)=∣D1∣∣D∣Gini(D1)+∣D2∣∣D∣Gini(D2)Gini(D|A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)

选小的就行了

GINI系数增益

先计算当前节点的基尼指数

Gini(D)=1−∑i=1mpi2Gini(D)=1-\sum_{i=1}^{m}p_{i}^2

然后计算分裂后子节点的基尼指数

Gini(D1)=1−∑i=1mp1i2Gini(D2)=1−∑i=1mp2i2Gini(D_1)=1-\sum_{i=1}^{m}p_{1i}^2\\ Gini(D_2)=1-\sum_{i=1}^{m}p_{2i}^2

基尼指数增益就为：

ΔGini(F)=Gini(D)−(∣D1∣∣D∣Gini(D1)+∣D2∣∣D∣Gini(D2))\Delta Gini(F)=Gini(D)-(\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2))

也就是

ΔGini(D)=Gini(D)−Gini(D∣A)\Delta Gini(D)=Gini(D)-Gini(D|A)

这里附上老师给出的练习题
image.png

如果使用基尼系数作为计算依据，那么CART决策树应该选择用哪个属性作为根节点？

  • 基于收入（income）分裂的基尼系数增益是 0.16875。
  • 基于信用评级（credit rating）分裂的基尼系数增益是 0.28125。

因为我们在选择分裂属性时希望基尼系数增益最大化，所以CART决策树应该选择**信用评级（credit rating）**作为根节点的分裂属性

计算过程如下：
c9901f55d066c4e64050f71def90b8b9

CART（MSE）

上面的介绍的是CART分类树，面对的还是离散数据，使用的是Gini系数选择属性，如果要对连续数据进行训练，则是使用均方差来选择属性

确定分割点 (PPT上这段话的开头是有误的)对于任意划分特征A，对应的任意划分点s两边划分成的数据集D1D_1和D2D_2，求出使D1D_1和D2D_2各自集合的均方差最小，同时D1D_1和D2D_2的均方差之和最小所对应的特征和特征值划分点，表达式为

mina,s[minc1∑xi∈D1(yi−c1)2+minc2∑xi∈D2(yi−c2)2]min_{a,s}[min_{c_1}\sum_{x_i\in D_1}(y_i-c_1)^2+min_{c_2}\sum_{x_i\in D_2}(y_i-c_2)^2]

其中为c1c_1为D1D_1数据集的样本输出均值，c2c_2为D2D_2数据集的样本输出均值。

**选择最佳分割点 ** 算法会评估所有候选分割点，并选择那个使得分割后的总不纯度（通常是两个子节点不纯度的加权平均）最小的点。对于回归树，这意味着选择一个分割点，使得两个子节点内部的均方误差最小化

分割数据并构建树的下一层 一旦选择了最佳分割点，数据集就会根据这个点被分割成两个子集。每个子集接着被用来构建决策树的下一层，对每个子集重复上述过程，直到满足停止准则（例如，达到最大深度、节点内数据点的数量小于某个阈值等）。

最后是基于代价复杂度的剪枝，后面介绍。

image-20240102184253251

剪枝

注意ID3模型是没有剪枝的，C4.5和CART模型才有剪枝

预剪枝

预剪枝是在决策树完全生成之前进行的。它通过提前停止树的构建来防止过拟合。预剪枝的方法包括：

  • 设置最大深度：限制树的生长深度。
  • 最小样本分裂：设置一个节点在继续分裂前必须拥有的最小样本数。
  • 最小样本叶节点：设置一个叶节点必须拥有的最小样本数。
  • 最小增益阈值：只有当分裂带来的纯度提升超过某个阈值时，才允许分裂发生。

预剪枝的主要优点是能够减少决策树的构建时间和复杂度，但它也可能导致树的生长过早停止，从而造成欠拟合。

后剪枝

后剪枝是在决策树完全生成后进行的。它首先构造一个复杂的完全树，然后从底部开始，尝试删除一些分支。后剪枝的方法包括：

  • 成本复杂度剪枝（Cost Complexity Pruning）：又称为弱化剪枝（Weakening Pruning），它考虑了剪枝后树的性能和复杂度之间的权衡。
  • 误差降低剪枝（Error Reduction Pruning）：只有当剪枝后能减少测试错误时，才执行剪枝操作。
  • 最小错误剪枝（Minimum Error Pruning）：在剪枝过程中使用一个独立的验证数据集来评估剪枝操作是否减少了预测错误。

后剪枝通常比预剪枝更能提高决策树的泛化能力，因为它基于完全成长的树进行优化，但这也意味着需要更多的计算资源和时间。

image-20240102181408528

误差降低剪枝

image-20240102212515563

该方法属于一种自底向上的后剪枝方法，需要结合测试数据集对决策树进行验证，如果某个节点的子孙节点都被剪去后，新的决策树在测试集上的误差反而降低了，则表明剪枝过程是正确的，否则就不能对其剪枝。

具体过程

  1. 将决策树的某个非叶子节点作为剪枝的候选对象（如图中的x3x_3处节点），如果将其子孙节点删除（对应的两个叶节点），则x3x_3处的节点就变成了叶节点

  2. 利用投票原则，将此处叶节点中频数最高的类别用作分类标准（如图中剪枝后该叶节点属于类 A ）。

  3. 利用剪枝后的新树在测试数据集上进行预测，然后对比新树与老树在测试集上的误判样本量，如果新树的误判样本量低于老树的误判样本量，则将x3x_3处的中间节点替换为叶节点，否则不进行剪枝。、

  4. 重复上面步骤，直到当没有更多节点可以被有效剪枝时，剪枝过程结束。

悲观剪枝法

image-20240102213142427

误差降低剪枝法虽然简单，但由于需要结合测试数据集才能够实现剪枝，所以有可能导致剪枝过度的情况。避免使用测试数据集，便产生了悲观剪枝法。它是自顶向下的剪枝过程，剪枝前后叶节点的误判率可以表示为：
这里有点问题，我是觉得悲观剪枝法自底向上更加合理，在根节点处，各种误差都累积到一块了，剪枝的效率并不是很高啊

{e′(T)=(E(T)+0.5)/Ne′(Tt)=(∑i=1L(E(ti)+0.5))/(∑i=1LNi)\begin{cases} e'(T)=(E(T)+0.5)/N \\ e'(T_t)=(\sum_{i=1}^{L}(E(t_i)+0.5))/(\sum_{i=1}^{L}N_i) \end{cases}

其中，e′(T)e'(T)表示剪枝后中间节点TT被换成叶节点的误判率，e′(Tt)e'(T_t)表示中间节点TT剪枝前其对应的所有叶节点的误判率；E(T)E(T)为中间节点TT处的误判个数，E(ti)E(t_i)为节点TT下的所有叶节点误判个数，LL表示中间节点TT对应的所有叶节点个数；NN表示中间节点TT的样本个数 ；NiN_i表示各叶节点中的样本个数，其实∑iLNi=1=N\sum_{i}^{L}N_{i=1}=N

image-20240102214528772

代价复杂度剪枝法

从字面理解该剪枝方涉及涉及两则信息，一则是代价是指将中间节点替换为叶节点后误判率会上升，另一则是复杂度是指剪枝后叶节点的个数减少，进而使模型的复杂度下降。为了平衡上升的误判率与下降的复杂度，需要加入一个系数α\alpha，故可以将代价复杂度剪枝法的目标函数写成：

Ca(T)=C(T)+α⋅∣Nleaf∣C_a(T)=C(T)+\alpha·|N_{leaf}|

其中，C(T)=∑i=1LNi×H(i)C(T)=\sum_{i=1}^{L}N_i\times H(i)，ii表示节点TT下第ii个叶节点；NiN_i为第ii个叶节点的样本量；H(i)H(i)为第ii个叶节点的信息熵；∣Nleaf∣|N_{leaf}|为节点TT对应的所有的叶节点个数；α\alpha就是调节参数

α\alpha的计算方法为：

image-20240102215130308

image-20240102214838515

结束

随机森林

抽样方式

利用 Bootstrap 抽样法（有放回的均匀抽样），从原始数据集中生成 k 个数据集，并且每个数据集都含有 N 个观测和 P 个自变量。 在构建每棵树的决策点时，不是考虑所有的特征，而是从所有可用特征中随机选择一个子集。这个过程增加了模型的多样性。

数据集

  1. 基于bootstrap样本生成决策树。
    1. 不放回的随机选择dd个特征
    2. 根据目标函数的要求，例如信息增益最大化，使用选定的最佳特征来分裂节点
  2. 重复抽样和生成决策树kk次

结果汇集

聚合每棵树的预测结果，并以多数票机制确定标签的分类

多票数机制

在一个集成学习框架中，构建多个分类器。每个分类器都独立地对同一数据点做出预测。

  1. 汇总预测结果：对于每个观测值，就是统计所有分类器的预测结果
  2. 计算最多票数的标签：对于每个观测值，统计每个可能标签的票数（即被预测为该标签的次数）
  3. 选择多数票标签：最终的预测标签是获得最多票数的标签。如果存在票数相同的情况，则可能需要一个额外的规则来决定最终的预测（例如，随机选择一个或使用分类器权重等）。

评估模型

使用未被Bootstrap抽样选择的数据（袋外数据，Out-of-Bag，OOB）来评估模型性能。这相当于对模型进行交叉验证。

结束