从零实现决策树：机器学习算法手写实践指南

一位机器学习学习者在 Reddit 上分享了自己从零手写决策树算法的经历。这是他「从零构建机器学习算法」系列挑战的第 13 天。虽然分享内容简短且带着学习者的真实困惑，但背后折射出的学习方法与技术要点，对同样想入门机器学习底层原理的人颇具参考价值。

为什么要「从零手写」决策树

很多初学者习惯直接调用 scikit-learn 里的 DecisionTreeClassifier，几行代码就能跑出结果。但真正理解算法内部机制的最好方式，是自己动手把它实现一遍。

这位作者提到，他第一天尝试时「完全搞砸了」，第二天一早重新开始编码才最终完成。这种反复试错正是深入理解算法的必经之路。决策树的核心难点在于如何递归地划分数据集——在每个节点根据某个特征和阈值把数据一分为二，然后对子集重复这一过程，直到满足停止条件。

作者坦言自己借助了 GPT 来理解「树是如何生成的」。这其实是当下学习者一种务实的做法：当卡在某个概念上时，用 AI 工具把抽象逻辑讲清楚，再自己动手实现，比单纯抄代码收获更大。他形容看到输出结果时「震撼到了」，并感慨「没想到递归竟然这么有用」。

递归：决策树的灵魂

作者的顿悟点在于递归。决策树的构建本质上就是一个递归过程：

决策树构建的基本逻辑

• 选择最优划分特征：通过信息增益、基尼系数等指标，找到能最好区分数据的特征和分裂点。
• 划分数据集：按选定条件把数据分成左右两个子集。
• 递归建树：对每个子集重复上述过程，生成子节点。
• 设置停止条件：当节点纯度足够高、样本数太少或达到最大深度时停止分裂，形成叶节点。

理解了这个递归结构，决策树看似复杂的树形结构就变得清晰了。这也是为什么作者会对递归的威力感到惊讶——短短几十行递归代码就能构建出完整的分类树。

信息增益衡量的是按某特征分裂后，数据集「混乱程度」的减少量，底层依赖香农熵（Shannon Entropy）计算：熵越低说明数据越纯净。基尼系数（Gini Impurity）是另一种常见纯度指标，计算代价比熵更低，是 scikit-learn 默认的分裂准则。两者在实践中效果相近，选择哪种通常对最终模型影响不大。手写实现时，最耗时的部分往往是「暴力搜索最优分裂点」：对每个特征、每个可能的阈值都计算一遍信息增益，取最大值——这一步的时间复杂度为 O(n·m·log n)，其中 n 为样本数、m 为特征数，也是决策树训练速度的主要瓶颈。

蘑菇数据集与过拟合的真实教训

作者用经典的 Mushroom Dataset（蘑菇数据集）来测试自己的实现。这个数据集包含蘑菇的各种特征，用于判断是否有毒，是决策树教学中的常用案例，因为它的特征都是类别型的，非常适合树模型。

值得关注的是，作者敏锐地意识到自己的模型「过拟合了，所以不能依赖它的准确率」。这是一个很成熟的判断。手写的基础决策树如果不加限制（比如最大深度、最小样本数、剪枝），很容易把训练数据完全记住，在训练集上准确率极高，但泛化能力差。

认识到过拟合的存在，比盲目为高准确率兴奋要重要得多。这说明作者不只是在「跑通代码」，而是在真正思考模型的局限性。

过拟合（Overfitting）本质上是模型把训练数据中的噪声也「学进去」了，导致在新数据上表现大幅下滑。判断过拟合最直接的方法是比较训练集准确率与验证集/测试集准确率之间的差距：若训练集近乎 100% 而测试集明显偏低，则过拟合几乎可以确定。对于未加任何约束的决策树，极端情况下每片叶节点只包含一个训练样本，树会把所有训练样本全部「记住」，这在统计上等同于零偏差但极高方差。常用的约束手段包括：限制最大树深（max_depth）、要求分裂前节点至少含 N 个样本（min_samples_split）、以及后剪枝（Post-Pruning）——先长出完整的树，再自底向上裁剪对验证集无益的分支。

下一步：从单棵树到集成学习

作者预告接下来要挑战 Bagging（Bootstrap Aggregating，自助聚合）。这是一个自然的进阶方向。

单棵决策树最大的问题就是方差高、容易过拟合——正是作者刚刚遇到的困境。而 Bagging 通过对训练数据进行有放回采样，训练多棵决策树并综合它们的预测结果，能有效降低方差、提升稳定性。随机森林（Random Forest）就是 Bagging 思想的经典应用。

从单棵树到集成方法，这条学习路径设计得相当合理：先理解基础模型的原理和缺陷，再学习如何用集成手段弥补这些缺陷。

Bagging 的核心思想来自统计学中的Bootstrap 重采样：从含 n 个样本的训练集中有放回地抽取 n 次，构造出一个新的「Bootstrap 样本集」，约有 63.2% 的原始样本会被选中，剩余约 36.8% 的样本（称为 Out-of-Bag，OOB 样本）天然可用作验证集，无需额外划分。重复此过程训练出多棵树后，分类任务取多数投票，回归任务取平均值。随机森林在 Bagging 基础上再加一层随机性：每次分裂时不考虑全部特征，而是随机抽取 √m 个特征作为候选，使各棵树之间的相关性更低，集成效果更好。这种「高偏差换低方差」的权衡是集成学习的核心逻辑。

坚持每日实践的价值

「从零构建机器学习算法」已经进行到第 13 天，这种持续的每日实践是掌握底层原理的有效方式。作者在帖子结尾还调侃自己本想早点写完代码去看动漫或 YouTube，结果还得赶作业。这种真实的学习状态反而让人共鸣——学习从来不是一帆风顺的。

对于想走类似路线的学习者，这里有几点可借鉴：

• 动手实现胜过被动阅读：亲手写一遍算法，才能真正理解每个步骤。
• 善用 AI 辅助理解：卡壳时用 GPT 等工具讲解概念，但务必自己动手编码。
• 保持批判性思维：像作者一样质疑高准确率背后的过拟合问题。
• 循序渐进：从基础算法逐步过渡到集成方法，构建完整知识体系。

手写机器学习算法或许不会成为工程实践的日常，但它带来的底层理解，是任何调包侠都难以获得的宝贵财富。