决策树是一种基本的分类与回归算法
构成：节点有两种类型：内部节点表示一个特征，叶节点表示一个类
- 叶节点（终端节点）：
- Left Node Mean = 6：这个节点表示样本 1、2、3 的均值，属于叶节点。
- Left Subtree Mean = 10：这个节点表示样本 4 的均值，属于叶节点。
- Right Subtree Mean = 12：这个节点表示样本 5 的均值，属于叶节点。
- 内部节点：
- Root x1 <= 3.5：这是根节点，表示对\(x_1\)的第一次切分，属于内部节点。
- Right Node x1 <= 4.5：这是右子树的内部节点，表示对\(x_1\)的第二次切分，属于内部节点。
学习过程
步骤：特征选择，决策树的生成，决策树的剪枝
特征选择有信息增益(ID3)，信息增益比(C4.5)，基尼指数(CART分类树)，平方误差最小准则(CART回归树)
决策树的生成算法(学习算法)有3种：ID3，C4.5和CART
ID3、C4.5 和 CART 之间的主要区别：
| 特性 | ID3 | C4.5 | CART |
|---|---|---|---|
| 选择划分特征的标准 | 信息增益 | 信息增益比 | 基尼指数（分类）/ 均方误差（回归） |
| 处理连续特征 | 不支持（需要离散化） | 支持，选择最优切分点 | 支持，选择最优切分点 |
| 处理缺失值 | 不支持 | 支持，采用概率分配法处理缺失值 | 支持，采用概率分配法处理缺失值 |
| 树的形状 | 树形可分为多个分支 | 树形可分为多个分支 | 生成二叉树 |
| 适用问题类型 | 分类问题 | 分类问题（回归通过扩展） | 分类问题（回归问题也支持） |
| 剪枝 | 不支持 | 支持后剪枝 | 支持代价复杂度剪枝 |
三种停止条件：
(1) 当前结点包含的样本全属于同一类别，无需划分；
(2) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；
(3) 当前结点包含的样本集合为空，不能划分。
特征选择-信息增益和信息增益比
信息量
\(H(x_i)=\log\frac{1}{p_i}\)
熵(经验熵)
熵：\(H(X)=\sum_{i = 1}^{n}p_i\log\frac{1}{p_i}=H(p)\)
熵和条件熵依赖于真实的概率分布 P(x)。而用频率估计计算得到的则为经验熵和经验条件熵
经验熵：\(H(D)=-\sum_{k = 1}^{K}\frac{|C_{k}|}{|D|}\log_{2}\frac{|C_{k}|}{|D|}\)
- D：数据集，包含所有的样本。
- K：数据集中的类别数，即目标变量的不同类别数。
- \(C_k\)：数据集D中属于第k类的样本集合。class的缩写
- \(|C_k|\)：类别k中样本的数量。
- \(|D|\)：数据集D中样本的总数量。data的缩写
条件熵(经验条件熵)
条件熵：\(H(Y|X)=\sum_{i = 1}^{n}p_iH(Y|X = x_i)\)
经验条件熵：\(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进行划分。特征A将数据集划分为多个子集\(D_1, D_2, \ldots, D_n\)
- n：特征A的不同取值个数。
- \(D_i\)：特征A取值为i时的数据子集
- \(|D_i|\)：子集\(D_i\)中样本的数量。
信息增益（互信息）
信息增益\(g(D, A)\)是基于某特征A对数据集D进行划分前后，熵的减少量。
\(g(D,A)=H(D)-H(D|A)\)，其中
- \(H(D)\)：是数据集D的熵，对数据集D进行分类的不确定性
- \(H(D|A)\)：是在特征A条件下，数据集D的条件熵，对数据集D进行分类的不确定性（特征A给定）
熵是用来衡量一个系统不确定性的指标，对于分类问题的熵公式如下： \(H(D)=-\sum_{i = 1}^{k}p_{i}\log_{2}p_{i}\) 其中\(p_{i}\)是类别i出现的概率，k是类别数。
条件熵是表示在已知特征A的条件下，数据集D的熵： \(H(D|A)=\sum_{v\in A}\frac{|D_{v}|}{|D|}H(D_{v})\) 其中A是特征，\(D_{v}\)是特征A取值为v的子集，\(|D_{v}|\)是子集大小，\(H(D_{v})\)是子集\(D_{v}\)的熵。
信息增益的含义： 信息增益衡量的是使用特征A进行划分，数据的不确定性（熵）减少的程度。信息增益越大，特征对目标变量的预测能力越强。
由于在机器学习中，我们通常没有完整的概率分布，而是通过样本数据来估计熵，因此会用经验熵和经验条件熵来代替真实的熵和条件熵。
信息增益比
信息增益比\((D, A)=\frac{IG(D, A)}{H(A)}\)
- \(H(A)\)是特征A的熵（即A上可能取值的熵），计算公式为： \(H(A)=-\sum_{v\in A}\frac{|D_{v}|}{|D|}\log_{2}\frac{|D_{v}|}{|D|}\)
含义
- 信息增益比通过对信息增益进行标准化，解决了信息增益偏向选择取值较多的特征的问题。信息增益比较大的特征通常是那些能够将数据有效划分且本身取值不太多的特征。
- 在决策树构建中，如果信息增益比大，表示这个特征在区分数据方面的效果较好。
总结
- 信息增益：衡量通过某特征划分数据后的不确定性减少量，越大越好。
- 信息增益比：通过标准化信息增益，避免特征取值多的特征被过度选择，选择更合适的特征用于划分。
例题
| 样本编号 | 特征 A | 目标变量 |
|---|---|---|
| 1 | A1 | Yes |
| 2 | A1 | No |
| 3 | A2 | Yes |
| 4 | A2 | No |
| 5 | A3 | Yes |
| 6 | A3 | No |
计算熵\(H(D)\)-只看结果
- 总样本数\(|D| = 6\)。
- 样本中 “Yes” 有 3 个，“No” 有 3 个，所以： \(p_{Yes}=\frac{3}{6}=0.5, \ p_{No}=\frac{3}{6}=0.5\)
- 所以总体的熵\(H(D)\)为： \(H(D)=-(0.5\log_{2}0.5 + 0.5\log_{2}0.5)=1\)
计算条件熵： 对于每个特征\(A_i\)，我们计算对应的子集熵\(H(D_i)\)并加权求和。
- 对于\(A_1\)（取值为\(A_1\)的样本为样本 1 和样本 2）：
- 样本 1 的目标变量为 “Yes”，样本 2 的目标变量为 “No”。
- 目标变量在此子集中的熵为： \(H(D_1)=-\left(\frac{1}{2}\log_{2}\frac{1}{2}+\frac{1}{2}\log_{2}\frac{1}{2}\right)=1\)
- \(|D_1| = 2\)。
- 对于\(A_2\)（取值为\(A_2\)的样本为样本 3 和样本 4）：
- 样本 3 的目标变量为 “Yes”，样本 4 的目标变量为 “No”。
- 目标变量在此子集中的熵同样是 1： \(H(D_2)=1\)
- \(|D_2| = 2\)。
- 对于\(A_3\)（取值为\(A_3\)的样本为样本 5 和样本 6）：
- 样本 5 的目标变量为 “Yes”，样本 6 的目标变量为 “No”。
- 目标变量在此子集中的熵也是 1： \(H(D_3)=1\)
- \(|D_3| = 2\)。
现在我们可以计算条件熵\(H(D|A)\)，根据各个子集的大小和熵的加权和： \(H(D|A)=\frac{|D_1|}{|D|}H(D_1)+\frac{|D_2|}{|D|}H(D_2)+\frac{|D_3|}{|D|}H(D_3)\) 代入数值： \(H(D|A)=\frac{2}{6}\cdot1+\frac{2}{6}\cdot1+\frac{2}{6}\cdot1 = 1\)
结果：总体熵\(H(D)=1\)。条件熵\(H(D|A)=1\)。
这个结果表明，在特征A的条件下，目标变量的熵没有得到减少，因此特征A对目标变量的分类效果并不理想。
学习时的依据：最小化损失函数
ID3算法与C4.5算法(不考过程，知道什么为选择特征即可)
ID3算法：
- 所有样本都属于同一类：那就没必要再分了，直接把这个结点当成叶子结点，标上这类的类别就完事了
- 比如你当前这个结点包含 5 个样本，它们全都是“猫”，那就不用再选特征、再分了，直接把这个结点标成“猫”
- 已经没有特征可以用了（A = ∅）：所有特征都已经用光了，但这个结点里的样本还不是同一类，那怎么办？就选出现次数最多的类别作为这个叶结点的类别，强行归类
- 比如当前这个结点有 5 个样本，其中：3个是“狗”2个是“猫”但所有特征都已经用完了，无法再切分。那就选“狗”作为最终类别（因为出现最多），这个结点就是“狗”
C4.5算法：
决策树各个节点应用信息增益作为选择特征
C4.5只是更换了特征选择的标准，从信息增益到信息增益比
CART算法 Classification and Regression tree
回顾：输出变量是离散的-分类问题，输出变量是连续的-回归问题
之前的决策树可以是多叉树，但CART树假设树是二叉树。多叉树可以转化为二叉树
基尼指数
同样需要一个选择特征的标准-分类树
样本集的基尼指数：
上面的定义为理想状态下的定义，因为假设直到属于每个类的概率，但实际我们需要通过数数去估计，样本点属于Dk个类的概率Pk。用属于Dk类的样本数/总样本数
特征的基尼指数：
甜度和硬度相比，甜度的基尼指数更小。这表明甜度这个特征更有利于分类，即分的更彻底（可以想象完全分类一个0和1，此时为0，所以基尼指数肯定是越小越好）
树的生成
分类树
回归树
回归是连续的输出值，怎么将其对应到一个一个节点呢，将输入分段
对于一个特征（变量），我们遍历所有可能的切分点 s，将样本分为 x≤s 和 x>s 两个区域
- \(R_1(j, s)=\{x | x^{(j)}\leq s\}\)：表示特征j小于等于s的样本集合。
- \(R_2(j, s)=\{x | x^{(j)}> s\}\)：表示特征j大于s的样本集合。
- \(c_1\)、\(c_2\)是左右区域的预测值，分别取对应区域内y的平均值。
总结流程：
例题：
| 样本编号 | x1 | x2 | y |
|---|---|---|---|
| 1 | 1 | 5 | 5 |
| 2 | 2 | 4 | 6 |
| 3 | 3 | 3 | 7 |
| 4 | 4 | 2 | 10 |
| 5 | 5 | 1 | 12 |
我们尝试分别用\(x_1\)和\(x_2\)做分裂，寻找哪个变量在哪个切分点能使平方误差最小：
对变量\(x_1\)： 可能切分点（中点）：\(1.5, 2.5, 3.5, 4.5\)
假设我们尝试\(x_1\leq3.5\)：
- 左：样本\(1\sim3\)，\(y = 5, 6, 7\)，均值\(c_1 = 6\)，平方误差： \((5 – 6)^2+(6 – 6)^2+(7 – 6)^2 = 1 + 0 + 1 = 2\)
- 右：样本\(4\sim5\)，\(y = 10, 12\)，均值\(c_2 = 11\)，平方误差： \((10 – 11)^2+(12 – 11)^2 = 1 + 1 = 2\) 总误差 = 4
对变量\(x_2\)： 可能切分点：\(1.5, 2.5, 3.5, 4.5\) 假设我们尝试\(x_2 \leq 3.5\)：
- 左：样本\(3\sim5\)，\(y = 7, 10, 12\)，均值\(c_1 = 9.67\)，误差： \((7 – 9.67)^2 + (10 – 9.67)^2 + (12 – 9.67)^2 \approx 7.11\)
- 右：样本\(1\sim2\)，\(y = 5, 6\)，均值\(c_2 = 5.5\)，误差： \((5 – 5.5)^2 + (6 – 5.5)^2 = 0.25 + 0.25 = 0.5\) 总误差 = \(7.11 + 0.5 = 7.61\)
✅ 结论
- \(x_1 \leq 3.5\)的分裂误差更小（4），所以选择变量\(x_1\)，切分点\(s = 3.5\)。
这样我们就完成了第一步划分，再对左右子集递归做同样的操作，就能构建整棵 CART 回归树了。
我们在根节点（第一个切分）时，选择了\(x_1\leq3.5\)作为切分变量。此时，数据被分成了两部分：
- 左子树（\(x_1\leq3.5\)）：样本 1、2、3，均值为 6
- 右子树（\(x_1 > 3.5\)）：样本 4、5，待进一步切分
现在我们需要对右子树（样本 4 和样本 5）继续进行切分。此时，我们将选择\(x_1\)还是\(x_2\)来作为切分变量。我们将再次遍历所有切分点，并计算平方误差，选择最优的切分点。
选择特征\(x_1\)作为切分变量：
- 样本 4 和样本 5 的\(x_1\)分别为 4 和 5。
- 所以，\(x_1\)的中间切分点为\(s = 4.5\)。
切分点\(x_1\leq4.5\)：
- 左子集（\(x_1\leq4.5\)）：样本 4，\(y = 10\)，均值为 10，误差为：\((10 – 10)^2 = 0\)
- 右子集（\(x_1 > 4.5\)）：样本 5，\(y = 12\)，均值为 12，误差为：\((12 – 12)^2 = 0\)
总误差：0
因此，使用\(x_1\leq4.5\)作为切分点时，误差为零，划分非常有效。
选择特征\(x_2\)作为切分变量： 现在我们考虑是否使用\(x_2\)作为切分变量。
- 样本 4 的\(x_2 = 2\)，样本 5 的\(x_2 = 1\)，因此\(x_2\)的中间切分点为\(s = 1.5\)。
切分点\(x_2\leq1.5\)：
- 左子集（\(x_2\leq1.5\)）：样本 5，\(y = 12\)，均值为 12，误差为：\((12 – 12)^2 = 0\)
- 右子集（\(x_2 > 1.5\)）：样本 4，\(y = 10\)，均值为 10，误差为：\((10 – 10)^2 = 0\)
总误差：0
同样，使用\(x_2\leq1.5\)作为切分点时，误差也为零。这里的划分同样有效。
在右子树的划分过程中，无论是选择\(x_1\)还是\(x_2\)进行切分，两者都能有效地将数据分开并实现零误差。然而，由于我们在根节点已经使用了\(x_1\)，为了保持一致性，我们会继续使用\(x_1\leq4.5\)进行切分。
最终回归树：
根节点：\(x_1\leq3.5\)
- 左子树：样本 1、2、3，均值为 6
- 右子树（继续使用\(x_1\)切分）：
- 左子树（\(x_1\leq4.5\)）：样本 4，均值为 10
- 右子树（\(x_1 > 4.5\)）：样本 5，均值为 12
决策树的剪枝
以最小化损失函数为学习策略递归的选择最优的特征可能对训练数据有很好的分类能力，但对未知数据却未必有很好的分类能力，这种现象被称为过拟合现象。
因此我们需要自下而上的进行剪枝，去掉过于细分的叶节点使其父节点改为新的叶节点，让树变得更简单，从而使其具有更好的泛化能力
剪枝主要有两种方式：
- 预剪枝（Pre-Pruning）：在决策树生成的过程中，通过设置一些提前的限制条件（如最大深度、最小样本数等），避免树生成得过于复杂。
- 后剪枝（Post-Pruning）：在决策树生成完成后，通过从叶子节点开始回溯，删除一些冗余的子树和分支，来优化决策树。
在大多数情况下，后剪枝是更常见且更有效的方式。
1.计算每个叶节点的经验熵
经验熵用于衡量数据集的纯度（或不确定性）。经验熵越高，表示该叶节点的数据越混乱，类别不确定性较高。
2.计算损失函数 损失函数用来衡量树的复杂度和每个叶节点的熵。一个常见的损失函数公式为： \(C_{\alpha}(T)=\sum_{t = 1}^{|T|}N_tH_t(T)+\alpha|T|\) 其中：
- \(|T|\)：树T的节点数。
- \(\alpha\)：控制剪枝强度的参数，\(\alpha\)越大，意味着剪枝力度越大，即偏向较小的树。
- \(N_t\)：叶节点t的样本数量。
- \(H_t(T)\)：叶节点t的经验熵。
3.剪枝的决策 剪枝的基本决策是：当一个子树的剪枝后损失函数小于或等于剪枝前的损失函数时，我们就保留剪枝后的树。 公式： \(C_{\alpha}(T_A)\leq C_{\alpha}(T_B)\) 其中：
- \(T_A\)是剪枝后的树。
- \(T_B\)是剪枝前的树。
- \(C_{\alpha}(T_A)\)和\(C_{\alpha}(T_B)\)分别是剪枝后和剪枝前的损失函数。
4.重复剪枝过程
剪枝过程从树的叶节点开始进行，不断回溯并执行剪枝，直到没有进一步剪枝的空间为止。在每一步中，计算每个节点的损失函数并决定是否剪枝。
