决策树与随机森林:用流图表做预测

决策树与随机森林:用流图表做预测

本节摘要:决策树(Decision Tree)就是一张流程图,但一棵森林却是机器学习里最强大的工具之一。对于表格数据(行是样本、列是特征),树模型——决策树、随机森林、梯度提升树——始终碾压深度学习,Kaggle 的结构化数据竞赛被 XGBoost 和 LightGBM 统治,不是 Transformer。原因在于:树天然处理混合特征类型、无需特征工程就能拟合非线性关系、可解释(你能直接看到为何做出某个预测),而随机森林通过平均许多棵树,对中等规模数据集高度抗过拟合。本节将从零实现基尼不纯度(Gini)、熵(Entropy)、信息增益(Information Gain),手写一棵带预剪枝控制的决策树,再用自助采样(Bootstrap)和特征随机化搭出随机森林,理解「弱学习器集成变强」的数学原理。

学习目标

阅读完本节,你应当能够:

1. 实现基尼不纯度、熵、信息增益的计算,找出最优决策树切分点。
2. 从零构建带预剪枝控制(最大深度、最小样本数)的决策树分类器。
3. 用自助采样和特征随机化构造随机森林,解释它为何降低方差。
4. 对比 MDI 特征重要性与置换重要性,识别 MDI 在何时会有偏。

一、问题与直觉

你手上有表格数据,行是样本、列是特征,还有一个想预测的目标列。你可以扔个神经网络上去,但对表格数据,树模型(决策树、随机森林、梯度提升树)始终碾压深度学习。Kaggle 的结构化数据竞赛由 XGBoost 和 LightGBM 统治,不是 Transformer。

为什么?树无需预处理就能处理混合特征类型(数值与类别)。无需特征工程就能处理非线性关系。它们可解释:你能看着树,准确知道某个预测为何被做出。而随机森林,通过平均许多棵树,在中型数据集上高度抗过拟合。

本节用递归切分从零搭建决策树,再在其上搭随机森林。你将实现切分准则背后的数学(基尼不纯度、熵、信息增益),并理解为什么一群弱学习器会变成强学习器。

决策树在做什么

决策树通过一连串是非问题,把特征空间切成矩形区域。

每个内部节点拿一个特征和一个阈值做比较,每个叶子节点给出一个预测。要分类一个新数据点,你从根开始,顺着分支走,直到到达叶子。

树是自顶向下构建的:在每个节点选最能分离数据的(特征, 阈值)对。「最能」由切分准则定义。

切分准则:度量不纯度

在每个节点上,我们有一组样本,想把它们切分得让子节点尽量「纯」,即每个子节点主要含一个类。

基尼不纯度(Gini Impurity) 度量:若按该节点的类分布给一个随机样本标号,它被错分的概率。

Gini(S) = 1 - sum(p_k^2)

其中 p_k 是集合 S 中类 k 的占比。
​

对纯节点(全一类),Gini = 0。对 50/50 两类切分,Gini = 0.5。越低越好。

例:6 只猫, 4 只狗

Gini = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 0.48
​

熵(Entropy) 度量节点中的信息含量(无序度)。详见第 1 章第 09 节。

Entropy(S) = -sum(p_k * log2(p_k))
​

对纯节点,熵 = 0。对 50/50 两类,熵 = 1.0。越低越好。

例:6 只猫, 4 只狗

Entropy = -(0.6 * log2(0.6) + 0.4 * log2(0.4))
        = -(0.6 * -0.737 + 0.4 * -1.322)
        = 0.442 + 0.529
        = 0.971 比特
​

信息增益(Information Gain) 是切分后不纯度(熵或基尼)的下降量。

IG(S, feature, threshold) = Impurity(S) - weighted_avg(Impurity(S_left), Impurity(S_right))

其中权重是每个子节点中样本的占比。
​

每个节点的贪心算法:试每个特征、每个可能的阈值,选使信息增益最大的(特征, 阈值)对。

切分如何运作

对当前节点 n 个特征、m 个样本的数据集:

1. 对每个特征 j(j = 1 到 n):
   • 按特征 j 排序样本
   • 试相邻不同值之间的每个中点作为阈值
   • 计算每个阈值的信息增益
2. 选信息增益最高的(特征, 阈值)
3. 把数据切成左(特征 <= 阈值)和右(特征 > 阈值)
4. 对每个子节点递归

这个贪心做法不保证全局最优树。找最优树是 NP 难的。但贪心切分在实践中表现良好。

停止条件

没有停止条件,树会一直长到每个叶子都纯(每叶一个样本)。这会完美背下训练数据,泛化极差。

预剪枝(Pre-pruning) 在树完全长成前停:

• 最大深度:树达到设定深度就停止切分
• 叶子最小样本数:节点少于 k 个样本就停
• 最小信息增益:最佳切分对不纯度的改进不足某个阈值就停
• 最大叶子数:限制总叶子数

后剪枝(Post-pruning) 先长成全树,再往回修剪:

• 代价复杂度剪枝(scikit-learn 用):按叶子数加一个惩罚,增大惩罚得到更小的树
• 减少误差剪枝:若移除子树不增加验证误差,就移除

预剪枝更简单更快。后剪枝常产生更好的树,因为它不会过早停掉那些本可继续做出有用切分的分支。

决策树用于回归

回归时,叶子预测是该叶子目标值的均值。切分准则也变了:

方差减少(Variance Reduction) 取代信息增益:

VR(S, feature, threshold) = Var(S) - weighted_avg(Var(S_left), Var(S_right))
​

选方差减少最多的切分。树把输入空间切成区域,在每个区域预测一个常数(均值)。

随机森林:集成的力量

单棵决策树方差高。数据的微小变化会产生完全不同的树。随机森林通过平均许多棵树来修正这点。

两个随机性来源让树有多样性:

Bagging(Bootstrap Aggregating,自助聚合):每棵树在自助样本上训练——从训练数据有放回地随机抽样。约 63% 的原始样本出现在每个自助样本里(其余是袋外样本 OOB,可用于验证)。

特征随机化:每次切分时只考虑特征的随机子集。分类默认是 sqrt(n_features),回归是 n_features/3。这避免所有树都在同一个主导特征上切分。

关键洞见:平均许多去相关的树能降低方差而不增偏差。每棵树单独看可能平庸,集成起来却很强。

特征重要性

随机森林天然给出特征重要性分数。最常用的方法:

平均不纯度减少(Mean Decrease in Impurity, MDI):对每个特征,把所有树、所有用该特征的节点上的不纯度总减少量加起来。能在更早切分处产生更大不纯度减少的特征更重要。

importance(feature_j) = 对所有使用 feature_j 的节点求和:
    (n_samples_at_node / n_total_samples) * impurity_decrease
​

它快(训练时就算好),但对高基数特征和有很多切分点的特征有偏。

置换重要性(Permutation Importance) 是替代:打乱某特征的取值,看模型准确率掉多少。更可靠但更慢。

树何时打败神经网络

树和森林在表格数据上碾压神经网络。原因:

当数据有空间或序列结构(图像、文本、音频)时神经网络胜出。对于扁平的特征表,树是默认选择。

二、从零实现

第 1 步:基尼不纯度与熵

从零实现两种切分准则,验证它们对哪些切分好达成一致。

import math

def gini_impurity(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return 1.0 - sum((c / n) ** 2 for c in counts.values())

def entropy(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return -sum(
        (c / n) * math.log2(c / n) for c in counts.values() if c > 0
    )
​

第 2 步:找最佳切分

试每个特征、每个阈值,返回信息增益最高的那个。

def information_gain(parent_labels, left_labels, right_labels, criterion="gini"):
    measure = gini_impurity if criterion == "gini" else entropy
    n = len(parent_labels)
    n_left = len(left_labels)
    n_right = len(right_labels)
    if n_left == 0 or n_right == 0:
        return 0.0
    parent_impurity = measure(parent_labels)
    child_impurity = (
        (n_left / n) * measure(left_labels) +
        (n_right / n) * measure(right_labels)
    )
    return parent_impurity - child_impurity
​

第 3 步:构建 DecisionTree 类

递归切分、预测、特征重要性跟踪。_build 是树的心脏:当节点纯或触及预剪枝限制时停,否则取最佳切分并对两个子节点递归。

import random

class DecisionTree:
    def __init__(self, max_depth=None, min_samples_split=2,
                 min_samples_leaf=1, criterion="gini",
                 max_features=None):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.min_samples_leaf = min_samples_leaf
        self.criterion = criterion
        self.max_features = max_features
        self.tree = None
        self.feature_importances_ = None

    def fit(self, X, y):
        self.n_features = len(X[0])
        self.feature_importances_ = [0.0] * self.n_features
        self.n_samples = len(X)
        self.tree = self._build(X, y, depth=0)
        total = sum(self.feature_importances_)
        if total > 0:
            self.feature_importances_ = [
                fi / total for fi in self.feature_importances_
            ]

    def predict(self, X):
        return [self._predict_one(x, self.tree) for x in X]

    def _build(self, X, y, depth):
        if len(set(y)) == 1:
            return {"leaf": True, "value": y[0]}

        if self.max_depth is not None and depth >= self.max_depth:
            return self._make_leaf(y)

        if len(y) < self.min_samples_split:
            return self._make_leaf(y)

        best_feature, best_threshold, best_gain = self._best_split(X, y)

        if best_feature is None or best_gain <= 0:
            return self._make_leaf(y)

        left_X, left_y, right_X, right_y = self._split_data(
            X, y, best_feature, best_threshold
        )

        if len(left_y) < self.min_samples_leaf or len(right_y) < self.min_samples_leaf:
            return self._make_leaf(y)

        weight = len(y) / self.n_samples
        self.feature_importances_[best_feature] += weight * best_gain

        return {
            "leaf": False,
            "feature": best_feature,
            "threshold": best_threshold,
            "left": self._build(left_X, left_y, depth + 1),
            "right": self._build(right_X, right_y, depth + 1),
        }

    def _make_leaf(self, y):
        counts = {}
        for label in y:
            counts[label] = counts.get(label, 0) + 1
        return {"leaf": True, "value": max(counts, key=counts.get)}

    def _best_split(self, X, y):
        best_feature = None
        best_threshold = None
        best_gain = -1.0

        if self.max_features == "sqrt":
            k = max(1, int(math.sqrt(self.n_features)))
            feature_indices = random.sample(range(self.n_features), k)
        elif isinstance(self.max_features, int):
            if self.max_features < 1:
                raise ValueError("max_features must be at least 1 when given as an integer")
            k = min(self.max_features, self.n_features)
            feature_indices = random.sample(range(self.n_features), k)
        else:
            feature_indices = list(range(self.n_features))

        for feature_idx in feature_indices:
            values = sorted(set(X[i][feature_idx] for i in range(len(X))))
            if len(values) <= 1:
                continue

            for i in range(len(values) - 1):
                threshold = (values[i] + values[i + 1]) / 2.0
                left_y = [y[j] for j in range(len(X)) if X[j][feature_idx] <= threshold]
                right_y = [y[j] for j in range(len(X)) if X[j][feature_idx] > threshold]

                if len(left_y) < self.min_samples_leaf or len(right_y) < self.min_samples_leaf:
                    continue

                gain = information_gain(y, left_y, right_y, self.criterion)
                if gain > best_gain:
                    best_gain = gain
                    best_feature = feature_idx
                    best_threshold = threshold

        return best_feature, best_threshold, best_gain

    def _split_data(self, X, y, feature, threshold):
        left_X, left_y, right_X, right_y = [], [], [], []
        for i in range(len(X)):
            if X[i][feature] <= threshold:
                left_X.append(X[i])
                left_y.append(y[i])
            else:
                right_X.append(X[i])
                right_y.append(y[i])
        return left_X, left_y, right_X, right_y

    def _predict_one(self, x, node):
        if node["leaf"]:
            return node["value"]
        if x[node["feature"]] <= node["threshold"]:
            return self._predict_one(x, node["left"])
        return self._predict_one(x, node["right"])
​

第 4 步:构建 RandomForest 类

自助采样、特征随机化、多数投票。

class RandomForest:
    def __init__(self, n_trees=100, max_depth=None,
                 min_samples_split=2, max_features="sqrt",
                 criterion="gini"):
        self.n_trees = n_trees
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.max_features = max_features
        self.criterion = criterion
        self.trees = []

    def fit(self, X, y):
        n = len(X)
        for _ in range(self.n_trees):
            indices = [random.randint(0, n - 1) for _ in range(n)]
            X_boot = [X[i] for i in indices]
            y_boot = [y[i] for i in indices]
            tree = DecisionTree(
                max_depth=self.max_depth,
                min_samples_split=self.min_samples_split,
                max_features=self.max_features,
                criterion=self.criterion,
            )
            tree.fit(X_boot, y_boot)
            self.trees.append(tree)

    def predict(self, X):
        all_preds = [tree.predict(X) for tree in self.trees]
        predictions = []
        for i in range(len(X)):
            votes = {}
            for preds in all_preds:
                v = preds[i]
                votes[v] = votes.get(v, 0) + 1
            predictions.append(max(votes, key=votes.get))
        return predictions
​

完整实现(含全部辅助方法)见 code/trees.py。

三、框架对比

用 scikit-learn,训练随机森林只需三行:

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)

rf = RandomForestClassifier(n_estimators=100, random_state=42)
rf.fit(X_train, y_train)
print(f"Accuracy: {rf.score(X_test, y_test):.4f}")
print(f"Feature importances: {rf.feature_importances_}")
​

四、可复用产物

本节产出 outputs/prompt-tree-interpreter.md——一个为业务干系人解读决策树切分的提示词。喂给它一棵训练好的树的结构(深度、特征、切分阈值、准确率),它把模型翻译成大白话规则、给特征重要性排名、标记过拟合或泄漏、并建议下一步。任何时候你需要向不懂代码的人解释树模型,都用得上。

五、练习

1. 在一个三类二维数据集上训练单棵决策树,手动追踪切分点,画出矩形决策边界,对比 max_depth=2 和 max_depth=10 时的边界。
2. 实现回归树的方差减少切分。生成 y = sin(x) + 噪声(200 个点),拟合回归树,把树的分段常数预测和真实曲线画在一起。
3. 用 1、5、10、50、200 棵树建随机森林,画训练准确率和测试准确率随树数变化的曲线。观察测试准确率会平台化但不下降(森林抗过拟合)。
4. 在 5 个不同数据集上对比基尼与熵作为切分准则,测准确率和树深度。大多数情况下结果几乎相同,解释为什么。
5. 实现置换重要性,在一个某特征是随机噪声但高基数的数据集上与 MDI 对比。MDI 会给噪声特征高排名,置换重要性不会。

本节要点回顾

1. 树用是非问题切特征空间:递归地把数据切成更纯的矩形区域,叶子给预测,全程可解释。
2. 两种不纯度度量:基尼(错分概率,00.5)和熵(信息含量,01.0),纯节点都是 0,越低越好。
3. 信息增益 = 父不纯度 − 加权子不纯度:贪心选增益最大的(特征, 阈值),虽非全局最优但实用(找最优是 NP 难)。
4. 预剪枝 vs 后剪枝:前者设最大深度/最小样本数提前停,简单快;后者长成全树再修剪,常更准。
5. 回归树用方差减少:叶子预测区域均值,本质是把空间分段、每段预测常数。
6. 随机森林 = Bagging + 特征随机化:有放回自助采样 + 每次切分只用特征子集,让树去相关。
7. 平均去相关树降方差不增偏差:单棵树平庸,集成强;约 63% 样本进自助,其余袋外可验证。
8. MDI 快但有偏:对高基数、多切分点特征高估;置换重要性更可靠但更慢。
9. 表格数据首选树:混合类型、小数据、特征交互、可解释、训练快、低超参敏感度全面胜神经网络;图像文本音频才让位给深度学习。

下一节,我们走向支持向量机——用最大间隔和核技巧,把线性不可分的数据投到高维空间硬切开。