**两个关键概念**： #第一性原理 - 信息熵: 想象你有一个装满不同颜色小球的罐子。如果所有球都是一个颜色,那么闭着眼睛拿球时你很容易猜对颜色,这种情况的"信息熵"很低。但如果每种颜色的球数量相等,你就很难猜对,这种情况的"信息熵"就高。 - **都穿校服**：大家衣服都一样，分类很纯粹，没有什么不确定性，所以熵比较小。 - **夜店各种服装**：服饰类型五花八门、混杂度高，不确定性大，所以熵值更高。 - 信息增益: 继续用猜动物的例子。问"这个动物会飞吗?"比问"这个动物喜欢吃胡萝卜吗?"可能更有助于你猜对。前一个问题带来的信息增益更大。 - 问"纹身吗"比问"喜欢吃馒头吗"更可能有助于判断是不是一个好女孩，前一个问题带来的信息增益更大。 - 所以决策树的可解释性会更好 **核心思想**是一个**贪心构建过程**： - 从根节点开始，选一个在当前数据子集上"最能区分样本"的特征及分裂点。比如使用特征 Age 分裂后，**数据整体的熵减少了多少**。减少得越多，说明分裂越有效，让子节点变得更"纯"(不确定性更低)，因此信息增益就越大。 - 将数据子集分裂为若干个子集后，再对子集递归地做同样的分裂选择。 - 一直分裂，直到满足终止条件(如达到最大深度、节点纯度足够高、样本数不足等)。 典型的分裂指标： 1. **信息增益**(基于熵) $\text{InfoGain} = H(\text{parent}) - \sum_{k} \frac{N_k}{N} H(\text{child}_k)$, - 其中 $H(\cdot)$ 是熵，$\frac{N_k}{N}$ 表示子节点占父节点数据量的比例。 - 直观理解就是"分裂前后的熵之差"，越大说明"分裂后越纯"，效果越好。 2. **Gini指数**(CART 决策树) $Gini(D) = \sum_{i=1}^{C} p_i (1 - p_i)$, - 其中 $p_i$ 是某类在数据集 $D$ 中的比例。 - 分裂时，会计算分裂前、后的加权 Gini，**Gini 越小越纯**。 停止分裂 & 剪枝 - 如果过度分裂，树会过拟合(非常深的树可能把训练数据划分到每叶节点只有1个样本)，导致泛化能力差。 - 因此需要设置**最大深度**、**最小叶子样本数**、**最小信息增益阈值**等超参数来阻止过度生长；或者先让树长到较深，再使用**剪枝**(pruning)技术，如"代价复杂度剪枝(CCP)"等，把贡献不大的分支剪掉。 - 这对应神经网络里的**正则化**(如 L2、L1、Dropout)——决策树也需要**限制模型复杂度**，以减少过拟合风险。 ## 数据集 假设我们想预测某人 "是否会购买 X 产品(Buys?)"，数据如下： | **Age** | **Student?** | **Income** | | **Buys?** | |:-----: |:----------: |:--------: | --- |:-------: | | Young | Yes | Low | - | Yes | | Young | No | High | - | No | | Mid | Yes | High | - | Yes | - **Age**: 取值有 "Young" 或 "Mid"(在更大数据里可能还有 "Old" 等，这里只出现了两种) - **Student?**: 是否是学生 (Yes/No) - **Income**: 这里只出现 "Low" 或 "High" - **Buys?**: 最终分类标签 (Yes/No) 我们要构建一棵**分类决策树**，用特征 (Age, Student?, Income) 来预测标签 (Buys?)。 --- ## 第 1 步：计算数据集的整体熵 在 ID3 算法里，需要先计算**当前数据集的熵**(Entropy)。熵衡量"混杂度"或"不确定性"，分类越混乱，熵越高。 ### 1.1 统计各类样本数 - "Yes" 样本数: 2 条(第 1 行、第 3 行) - "No" 样本数: 1 条(第 2 行) 总样本数 N=3N = 3。 ### 1.2 计算熵 $H(S) \;=\; - \sum_{c \in \{\text{Yes},\text{No}\}} p(c)\,\log_2\,p(c)$ 这里 - $p(\text{Yes}) = \tfrac{2}{3}$ - $p(\text{No}) = \tfrac{1}{3}$ 因此 $H(S) = - \Bigl(\frac{2}{3}\log_2 \frac{2}{3} + \frac{1}{3}\log_2 \frac{1}{3}\Bigr)$. 可以用大约数值估计（只要看个相对大小就行）： - $\log_2 \tfrac{2}{3}\approx -0.585$ - $\log_2 \tfrac{1}{3}\approx -1.585$ 所以 $H(S) \approx -\Bigl(\frac{2}{3}\times(-0.585) + \frac{1}{3}\times(-1.585)\Bigr) = -\Bigl(-\,0.39 + -\,0.53\Bigr) = 0.92 \;\;(\text{约值})$ 这里结果不必特别精确，你只要知道它介于 0 和 1.58(=$\log_2(3)$)之间即可。**熵越大表示"越混杂"**。 ## 第 2 步：分别尝试用各特征分裂，看哪个信息增益最大 ID3 算法会**遍历所有特征**(Age, Student?, Income)，看看以该特征做"根节点分裂"后，数据集的熵降低了多少(也就是**信息增益**)。信息增益越大，说明这个特征"分裂"效果越好，更能把数据切分得纯净。 ### 2.1 以特征 Age 分裂 - **Age = Young**: 含第 1、2 行，共 2 条 - 其中标签 "Yes" 1 条，"No" 1 条 ⇒ 这个子集还是混杂；熵可计算。 - **Age = Mid**: 含第 3 行，共 1 条 - 其中标签 "Yes" 1 条 ⇒ 这是纯集，熵=0 #### 2.1.1 计算子集熵 1. 子集 "Age=Young" 有 2 个样本: (Yes=1, No=1) $H(\text{Young}) = - \bigl(\tfrac{1}{2}\log_2 \tfrac{1}{2} + \tfrac{1}{2}\log_2 \tfrac{1}{2}\bigr) = 1.$ 1. 子集 "Age=Mid" 有 1 个样本: (Yes=1, No=0)，这是纯集 $H(\text{Mid}) = 0.$ #### 2.1.2 加权求和(分裂后的熵) 分裂后数据被分成 2 个子集(Young, Mid)，它们的大小分别是 2、1，总共 3 个样本： $H_{\text{Age}} = \frac{2}{3} \times 1 + \frac{1}{3} \times 0 = \frac{2}{3}.$ #### 2.1.3 信息增益 $\text{InfoGain}(\text{Age}) = H(S) - H_{\text{Age}} \approx 0.92 - \frac{2}{3} = 0.92 - 0.67 = 0.25.$ (大约值) --- ### 2.2 以特征 Student? 分裂 - **Student = Yes**: 第 1、3 行，共 2 条 - 标签情况: (Yes=2, No=0) 纯集 - **Student = No**: 第 2 行，共 1 条 - 标签情况: (Yes=0, No=1) 纯集 #### 2.2.1 子集熵 1. 子集 "Student=Yes": 2 个样本，都是 Yes ⇒ 纯集，熵 = 0 2. 子集 "Student=No": 1 个样本，都是 No ⇒ 纯集，熵 = 0 #### 2.2.2 加权求和(分裂后的熵) $H_{\text{Student}} = \frac{2}{3} \times 0 + \frac{1}{3} \times 0 = 0.$ #### 2.2.3 信息增益 $\text{InfoGain}(\text{Student}) = H(S) - H_{\text{Student}} = 0.92 - 0 = 0.92.$ 这很高，说明 Student? 非常能区分数据。 --- ### 2.3 以特征 Income 分裂 - **Income = Low**: 第 1 行，共 1 条 => (Yes=1) - **Income = High**: 第 2、3 行，共 2 条 => (Yes=1, No=1) #### 2.3.1 子集熵 1. "Income=Low" => 1 条 Yes => 纯集，熵 = 0 2. "Income=High" => 2 条(Yes=1, No=1)，熵 = 1 #### 2.3.2 加权求和 $H_{\text{Income}} = \frac{1}{3}\times 0 + \frac{2}{3}\times 1 = \frac{2}{3}.$ #### 2.3.3 信息增益 $\text{InfoGain}(\text{Income}) = H(S) - H_{\text{Income}} = 0.92 - 0.67 = 0.25.$ ## 第 3 步：选信息增益最大的特征做根节点 比较三者： - $\text{InfoGain}(Age) \approx 0.25$ - $\text{InfoGain}(Student) = 0.92$ - $\text{InfoGain}(Income) \approx 0.25$ 可见 **Student?** 的信息增益最高，所以 **ID3** 会选择 **Student?** 作为**根节点**来分裂。 --- ## 第 4 步：根据 Student? 分裂数据 - **Student = Yes** => 子集 { (Young, Yes, Low, Yes), (Mid, Yes, High, Yes) } - 这两个样本标签全是 "Yes"，是**纯集**；无需继续分裂 - **Student = No** => 子集 { (Young, No, High, No) } - 这 1 个样本标签是 "No"，也是纯集；无需继续分裂 因为在根节点分裂之后，左右子集都已经纯净，没有混杂，所以**决策树构建完成**。 --- ## 第 5 步：得到最终的决策树 画成一棵非常简单的树： ```Java ┌─── Student? ───┐ │ │ (Yes) │ │ (No) ▼ ▼ 全部 Yes 全部 No ``` - 如果样本 "Student = Yes"，则直接预测标签 "Yes" - 如果样本 "Student = No"，则直接预测标签 "No" 这么简单的树，就能完美地分类这 3 条数据。 --- ## 验证或预测新样本 假设来一个新样本 (Age=Young,Student=Yes,Income=High)(Age=Young, Student=Yes, Income=High)，我们只需看它的 **Student** 值： - 它是 "Yes"，因此决策树输出 "Yes"。 在这个小数据上非常直接。真实应用中会有更多特征和更多层分裂，但过程类似：**递归地贪心选择分裂特征**，直到子集纯或达到停止条件(如最大深度、最少样本数等)。 --- ## 总结 1. **熵与信息增益**：ID3 算法用信息增益来选择分裂特征。谁能最大幅度降低数据的熵，就选谁做节点。 2. **一步步分裂**：在本例中，最初数据的熵约 0.92，用特征 "Student?" 分裂后直接降为 0，这说明它能很好地区分所有样本。 3. **生成树**：最后得到一颗只有一个分裂节点(根节点)的非常小的树： - "Student=Yes" => 叶子输出 "Yes" - "Student=No" => 叶子输出 "No" 4. **对新数据的预测**：从根节点判断特征，走向对应叶子，输出标签。 这就是一个**极小的决策树构造示例**，通过这个过程你就能看到——和多层感知机用"梯度下降"优化权重不同，**决策树是用"特征分裂"+"信息增益"**的方式递归构建出来的。本质上都在最小化混杂度/误差，只是实现机制不同。 ## 决策树 决策树(Decision Tree)是一种**基于树结构**的模型，用于处理分类或回归问题。它通过对特征进行一系列条件判断(如"特征 A ≤ 某个值？"、"某个类别特征是否等于 X？"等)，将样本逐步分到不同子节点，直到到达叶子节点并给出预测结果。 和多层感知机(MLP)中神经元加权求和 + 激活函数不同，**决策树是"离散式"地划分特征空间**： - 每个节点对应一个**条件判断** - 若满足条件就往左(或右)子树走，不满足就往另一个子树走 - 最终在叶子节点输出一个预测值(类别/回归值) 下面分步骤介绍决策树的"前向(预测)过程"和"训练(构造树)过程"，以及在实际应用中需要注意的要点。 --- ## 1. 前向传播(预测)类比 在神经网络(MLP)中，**前向传播**指的是： - 把输入 xx 乘以权重矩阵、加偏置，再经过激活函数，层层传播，得到输出。 在决策树中，**预测过程**可以类比为一次"**从根节点到叶子节点的传递**"： 1. **从根节点开始** - 根节点上存放了一个"分裂规则"(比如：$\text{Age} \le 30$？$\text{Income} \le 5000$？某特征是否等于某值？等等)，拿输入样本在这里判断。 2. **根据特征值，走向左右子树** - 如果满足节点的分裂条件，就走左子树；否则走右子树(或者根据类比，可能还有多叉分裂的情况)。 3. **重复判断** - 每到一个子节点，又会有新的分裂条件，继续判断、分支。 4. **到达叶子节点** - 叶子节点对应一个输出值(对于分类是一个类别标签或类别概率；对于回归是一个实数值)。 - 这就是决策树的最终预测结果。 这一串操作"从根到叶"就好比神经网络里"从输入层到输出层"，只是**决策树的计算是基于"判断条件"来走分支**，没有连续可微的"加权求和"操作。 --- ## 2. 决策树训练(构造树) ### 2.1 类比"反向传播"？ 在[[多层感知机 MLP]]中，"反向传播"通过计算梯度来更新每个权重，最终最小化损失函数。而在决策树里**没有权重矩阵和激活函数**，它的"训练"是**构建出一个合适的分裂结构**(哪个特征先分裂？阈值多少？分裂到什么深度？)。 --- ## 3. 损失函数与决策树 在神经网络中，我们显式地设定损失函数(比如 MSE、交叉熵)，然后通过反向传播去更新权重。而决策树中，**分类树**常用的信息增益、Gini 指数等"纯度指标"来指导分裂，这些指标本身就充当了"局部的损失函数"。**回归树**则可以显式使用 MSE、MAE 等指标来选择最优分裂点。 也可以把决策树看成是在**局部**(每次分裂)最小化损失——比起神经网络的全局梯度下降，决策树的贪心策略没有**端到端**的"反向传播"，但也是一个**以损失(或纯度)为优化目标**的过程。 --- ## 4. 举个小例子 来个简化版本，帮助你直观感受决策树的构建： 1. **数据集** - 如下表，每行有特征 (年龄, 是否有房, 信用等级...)，以及标签 (是否违约)。 - 我们要构造一棵分类树来预测"是否违约"。 2. **根节点选择分裂特征** - 先尝试用"年龄"来分，看看分裂前后的信息增益；再尝试用"是否有房"来分；再尝试用"信用等级"等。 - 计算哪一个分裂带来的信息增益(或 Gini 降低)最大，就选它作为第一步。 3. **生成左右子节点** - 将数据根据所选特征的分裂规则(如"年龄 ≤ 30 岁" vs "> 30 岁")划分为两部分。 - 然后在每个子节点重复类似操作：继续选分裂特征、划分子节点……直到满足停止条件。 4. **叶子节点** - 最终可能出现： - 叶子 A：绝大多数样本是"违约"，模型就输出"违约" - 叶子 B：绝大多数样本是"非违约"，模型就输出"非违约" - 这样就完成了一棵可用于预测的新树。 --- ## 5. 使用决策树的实践要点 1. **选择合适的分裂准则** - **分类**：常见用 Gini 或信息增益。 - **回归**：常见用 MSE、MAE 等。 2. **预剪枝/后剪枝** - 通过超参数(如 `max_depth`, `min_samples_split`, `min_samples_leaf`, `min_impurity_decrease`)限制树的增长，避免过拟合。 3. **特征类型** - 对于离散分类特征或连续数值特征，要采用对应的最优分裂策略。 4. **可解释性** - 决策树可以可视化，直观显示"每一步怎么分裂、为什么这样分裂"，这是它的优势。 5. **易受训练数据影响** - 树对小规模数据或高维数据可能过拟合，或对噪声特征过度分裂；要注意数据清洗、特征选择等。 --- ## 6. 类比多层感知机的"训练-预测"流程 可以把决策树的流程也画成一个类似的"训练-预测"图表： **预测阶段**(相当于 MLP 的"前向传播")： 1. 对新样本从根节点开始，顺着特征条件判断，落到对应叶子。 2. 叶子里的结果(多数投票或均值等)就是预测值。 --- ## 7. 小结 - **决策树**是一种"**基于条件分裂**"的模型，和神经网络里的"连续可微计算图"不同。 - 它通过在训练阶段"**贪心地选择分裂特征**，逐层划分"，最终得到一棵可对样本进行预测的树结构。 - 训练中使用**信息增益/Gini/MSE**等分裂准则来衡量"分裂效果"并决定如何分裂。 - 过深的树容易过拟合，需要通过**剪枝**或限制深度等方式进行正则化。 - 预测时只需做一串**条件判断**(从根到叶)，可视化也比较容易，这使得决策树往往很**易解释**。 --- ## 结语 至此，你可以把**决策树**和**多层感知机(MLP)**做一个整体对比： |指标|多层感知机 (MLP)|决策树 (Decision Tree)| |:--|:--|:--| |**模型结构**|多层感知(全连接层 + 激活函数)，通过权重和偏置进行线性变换与非线性激活|树形结构，每个节点基于特征做离散分裂，叶子节点最终给出分类/回归值| |**前向传播**|矩阵乘法 + 激活函数|条件判断，从根节点按特征值分支到叶子| |**训练方式**|梯度下降+反向传播更新权重|递归选择分裂特征点(贪心)，根据信息增益/Gini/MSE 等指标做最优切分| |**正则化**|权重衰减(L2/L1)、Dropout、BatchNorm 等|剪枝、限制深度、最小样本数、最小增益阈值等| |**优点**|能拟合复杂函数(深度网络)，表达能力强|结构直观，可解释性好，适合很多表格型特征；训练/预测都较快| |**缺点**|训练需要大量数据，容易过拟合(需要大量正则化技巧)|易受样本噪声影响(不稳定)，容易过拟合(需要剪枝等措施)，单棵树泛化性能相对有限| |**延伸**|CNN、RNN、Transformer 等深度网络|随机森林(RF)、梯度提升树(GBDT)、XGBoost、LightGBM 等，都是基于决策树的集成算法| 如果你之后想学习**集成方法**(如随机森林、XGBoost)，你就会看到，它们都是在"决策树"的基础上做了**很多改进**或**集成策略**(比如对多棵树取平均、加权等)。 这正如深度学习里，从最简单的 MLP 不断扩展到 CNN、RNN、Transformers 一样，都在核心思想之上演变而来。 --- 希望这个分步骤的介绍能让你**像理解 MLP 一样**，快速理解决策树模型的本质。 祝学习顺利!