决策树节点的划分

小象实战讲义 · 机器学习算法精讲

上一节我们用信息熵与信息增益搭起了 ID3。但真实数据比 Play-Tennis 复杂得多：特征有名义型、有序型、连续型之分，决策树要能”对症下刀”。本节讲清楚三件事：不同类型的特征怎么分叉（连续特征必须先离散化）、信息熵之外还有哪些划分度量（基尼指数、误分类误差，以及”没有免费午餐”），以及树该长到什么时候停——为下一章的集成学习埋下伏笔。

💡 核心导读

• 特征三类型：名义型（nominal）直接多路分叉；有序型（ordinal）分叉时要尊重顺序；连续型（continuous）必须先离散化。
• 离散化三法：等宽分箱、等频（按分布）分箱、基于信息增益/基尼的动态找切点——第三种是决策树的正牌做法。
• 基尼指数与基尼分裂：CART 决策树的度量，不用算 log、手算即可；与信息增益方向相反——基尼分裂越小越好。
• 三种度量怎么选：熵、基尼、误分类误差形状相似、目标一致，但没有免费午餐——不同数据各有胜场。
• 树何时停：训练误差随树的长大一直降，测试误差却先降后升——停早了欠学、停晚了过拟合。

特征的三种类型

决策树的核心是”按特征值分叉”，但特征本身形态各异，直接决定这一刀怎么砍。

1. 名义型（nominal / discrete）：完全离散且无序。比如婚姻状况（未婚、已婚、离异）、是否退税（Yes/No）。有多少个取值就分多少叉，最省事。
2. 有序型（ordinal）：离散但内部有顺序。比如年龄（baby → kid → young → middle age → old）、尺寸（small/medium/large）。既可以多路分叉，也可以把相邻取值合并成组做二分——但合并要尊重顺序（后面细说）。
3. 连续型（continuous / numerical）：取值为实数，比如身高、体重、应税年收入。取值无穷多，没法一个值一叉，必须先离散化。

一个小技巧：当离散取值特别多时，可以先把若干标签聚成大类再分——比如把 baby、kid、young 先并成”年轻”一档，与”中年""老年”三分；若第一刀分得不够好，再往下细拆。先粗后细，省计算。

连续特征离散化：三种砍刀法

离散化（discretization）就是把连续量变成离散区间，是决策树处理连续特征的必经之路。讲师画了张二维图：在 $x_1$ 轴上取一个值 $\alpha$ 把平面切成左右两半，再在 $x_2$ 轴上取 $\beta_1$、$\beta_2$ 继续切——两次切割就把平面分成了四个矩形区域，每块区域对应树的一片叶子。方法上有三种：

1. 等宽分箱：把整个值域三等分（或 k 等分），完全不关心数据怎么分布。简单，但可能有的箱挤满数据、有的箱空着。
2. 等频分箱（按分布）：让每个区间里落进去的数据个数一样多。数据密的区间窄、数据疏的区间宽——比如从 60 千美元到 220 千美元的收入数据，低段密集、高段稀疏，等频切出来的边界会明显偏向低段。
3. 动态找切点：遍历相邻数据点之间的候选切点，选信息增益最大（或加权基尼最小）的那一个——这是决策树构建时的正牌做法。

用课件里的 10 个应税年收入（千美元）演示前两种：

# 讲师课件中的 10 个应税年收入（千美元）
incomes = [60, 70, 75, 85, 90, 95, 100, 120, 125, 220]

def equal_width_binning(data, k):
    """等宽分箱：把值域均分 k 段，返回 k-1 个边界"""
    lo, hi = min(data), max(data)
    width = (hi - lo) / k
    return [round(lo + i * width, 2) for i in range(1, k)]

def equal_frequency_binning(data, k):
    """等频分箱：让每段落入大致相同数量的数据，返回边界"""
    s = sorted(data)
    n = len(data)
    boundaries = []
    for i in range(1, k):
        idx = -(-i * n // k) - 1          # 即 ceil(i*n/k)-1
        if idx + 1 < n:
            boundaries.append(round((s[idx] + s[idx + 1]) / 2, 2))
    return boundaries

print("收入数据:", incomes)
print("等宽分箱(k=3)边界:", equal_width_binning(incomes, 3))
print("等频分箱(k=3)边界:", equal_frequency_binning(incomes, 3))

收入数据: [60, 70, 75, 85, 90, 95, 100, 120, 125, 220]
等宽分箱(k=3)边界: [113.33, 166.67]
等频分箱(k=3)边界: [87.5, 110.0]

可以看到：等宽的边界 113.33/166.67 只是把 60~220 的值域机械三等分；等频的边界 87.5/110.0 则把三段切成大约 4/3/3 个数据——密集的低收入段切得更细。

顺带回答一个课堂问题：候选切点为什么总取”正中间”？比如 75 和 85 之间，为什么切 80 而不是 81？原则上两者之间任意一点效果都一样（都没有数据落在切点附近），我们只是取两个相邻数据点的中点作为代表，既均匀又不遗漏。

基尼指数：不用算 log 的不纯度度量

最早的决策树算法之一 CART（Classification and Regression Trees）用的度量叫基尼指数。名字来源于经济学里衡量收入不均等的基尼指数——两者不是一回事，但都在某种层面上刻画概率分布的”混杂”程度。

对一个节点 $t$，基尼指数定义为：

$$\text{Gini}(t) = 1 - \sum_{j=1}^{J} [p(j|t)]^2$$

其中 $p(j|t)$ 是节点 $t$ 中类别 $j$ 的相对频率。讲师用三个口算例子讲透它：

• 节点里 6 个样本全是一类（如全红叉）：$p_1=1, p_2=0$，$1 - (1^2 + 0^2) = 0$——最纯；
• 3 叉 3 圈对半混合：$1 - (\frac{1}{2})^2 - (\frac{1}{2})^2 = 0.5$——二分类时最混，基尼取最大值 0.5；
• 5 比 1（如 5 叉 1 圈）：$1 - (\frac{5}{6})^2 - (\frac{1}{6})^2 \approx 0.278$。由对称性，1 比 5 的结果完全一样。

和熵一样，基尼也是”纯则 0、混则大”，最大值在各类均分时取到。最大的好处是不用算 log——手算平方和即可，工程上计算也更省。

基尼分裂与最佳切点

有了节点的不纯度，怎么评价一次切分的好坏？仿照信息增益的结构，定义基尼分裂（Gini Split）：父节点切成 $K$ 个子节点后，各子节点基尼的加权和：

$$\text{Gini}_{\text{split}} = \sum_{i=1}^{K} \frac{n_i}{n}\, \text{Gini}(i)$$

其中 $n_i$ 是落进第 $i$ 个子节点的数据量，$n$ 是总量。它与信息增益”同出一炉”，但方向相反：信息增益挑最大，基尼分裂挑最小。

用课件的逃税（Cheat）例子走一遍完整流程。10 个人的应税年收入与是否逃税——逃税（Yes）的恰好是 85K、90K、95K 三个人：

把 10 个收入排序后取相邻中点作为候选切点，逐一算加权基尼：

def gini_index(class_counts):
    """基尼指数：Gini = 1 - Σ (p_j)^2，输入为各类别计数"""
    total = sum(class_counts)
    if total == 0:
        return 0.0
    return 1 - sum((c / total) ** 2 for c in class_counts)

def split_weighted_gini(data, cut):
    """以 cut 切分后，左右子节点基尼的加权和"""
    left = [lab for inc, lab in data if inc <= cut]
    right = [lab for inc, lab in data if inc > cut]
    n = len(data)
    w_l, w_r = len(left) / n, len(right) / n
    return (w_l * gini_index([left.count('No'), left.count('Yes')])
          + w_r * gini_index([right.count('No'), right.count('Yes')]))

# 课件 Cheat 表：收入（千美元）与是否逃税
data = [(60, 'No'), (70, 'No'), (75, 'No'), (85, 'Yes'), (90, 'Yes'),
        (95, 'Yes'), (100, 'No'), (120, 'No'), (125, 'No'), (220, 'No')]

vals = sorted(set(v for v, _ in data))
candidates = [(vals[i] + vals[i+1]) / 2 for i in range(len(vals) - 1)]

print("候选切点与加权基尼指数：")
best_cut, best_gini = None, 1.0
for cut in candidates:
    g = split_weighted_gini(data, cut)
    print(f"  切点 {cut:>6}: 加权基尼 = {g:.3f}")
    if g < best_gini:
        best_cut, best_gini = cut, g
print(f"最优切点: {best_cut}，加权基尼 = {best_gini:.3f}")

候选切点与加权基尼指数：
  切点   65.0: 加权基尼 = 0.400
  切点   72.5: 加权基尼 = 0.375
  切点   80.0: 加权基尼 = 0.343
  切点   87.5: 加权基尼 = 0.417
  切点   92.5: 加权基尼 = 0.400
  切点   97.5: 加权基尼 = 0.300
  切点  110.0: 加权基尼 = 0.343
  切点  122.5: 加权基尼 = 0.375
  切点  172.5: 加权基尼 = 0.400
最优切点: 97.5，加权基尼 = 0.300

对照讲师在课上的现场口算：他先试了在 80 处切（75 与 85 的正中）——左边 3 个数据全是 No（基尼 0），权重 3/10；右边 7 个（3 Yes 4 No）基尼约 0.49——加权后约 0.343；又试了 87.5，得到约 0.417；把候选切点都算完后，最小的是 0.3——与代码扫出的 97.5 处 0.300 完全一致。在 97.5 切一刀，右边剩下 100/120/125/220 四个纯 No，左边把三个逃税者与其他人隔到一起继续细分。

误分类误差与三种度量的选择

最直观的第三种度量是误分类误差（misclassification error）：按多数类预测时的错误率。

$$\text{Error}(t) = 1 - \max_j p(j|t)$$

• 全一类（0 与 1）：$\max = 1$，误差 0；
• 3 叉 3 圈：$\max = 1/2$，误差 1/2。

三种度量（熵、基尼、误分类误差）画在同一个坐标系里形状神似：纯时为 0，对半混合时最大，且左右对称。讲师的评价很干脆：误分类误差最好算；熵理论最完整；基尼介于两者之间，不用 log、手算即可。

那到底哪个更好？——没有免费午餐（No Free Lunch）。机器学习里不存在一个处处最优的度量：有的数据用熵好，有的数据基尼好，误分类误差也可能在某个问题上表现不错。三种度量在多数问题上差别其实不大，选哪个要看数据和情况，不能迷信某一种。ID3 用熵，CART 用基尼——它们都长成了经典。

树该长到什么时候停？

最后是决策树绕不开的问题：什么时候停止分叉？

• 停得太早：树没学好数据的规律，欠学；
• 停得太晚：树长得过大、分支过多，过拟合。

把”节点数”看作模型复杂度：随着树不断长大，训练误差一路下降——极端情况是每个叶子只剩一个样本，训练误差归零；但测试误差先降后升——降到某个节点数时达到最低，继续长大反而掉头向上，这就是过拟合在曲线上的样子。

那测试误差与训练误差之间的这种背离，背后的原理是什么？讲师留了个大钩子：误差其实可以分解成不同类型——偏差（bias）与方差（variance），而且对付它的一个大杀器是把很多树集成在一起做判断（ensemble）。这正是下一章集成学习（CART/Bagging/Boosting）要展开的主线。

📝 动手练一练

1. 概念辨析：有序特征（尺寸 small/medium/large）强制二分时，为什么”small 与 large 一组、medium 单独一组”通常不是首选？什么情况下它反而可能成立？

2. 代码实践：主示例里 split_weighted_gini 的类别计数写死了 ‘No’/‘Yes’ 两个标签。若数据有 3 个类别（如 ‘No’/‘Yes’/‘Under-review’），函数还能用吗？改写为支持任意类别数的版本。

from collections import defaultdict

def gini_index_counts(counts):
    """基尼指数：Gini = 1 - Σ (p_j)^2"""
    total = sum(counts)
    if total == 0:
        return 0.0
    return 1 - sum((c / total) ** 2 for c in counts)

def split_weighted_gini_multiclass(data, cut):
    """支持任意类别数的加权基尼"""
    left = defaultdict(int)
    right = defaultdict(int)
    for value, lab in data:
        if value <= cut:
            left[lab] += 1
        else:
            right[lab] += 1
    n = len(data)
    return (sum(left.values()) / n * gini_index_counts(left.values())
          + sum(right.values()) / n * gini_index_counts(right.values()))

demo = [(60, 'No'), (70, 'No'), (75, 'Under-review'),
        (85, 'Yes'), (90, 'Yes'), (95, 'Yes'),
        (100, 'No'), (120, 'No'), (125, 'No'), (220, 'No')]
print(f"切点 80.0 的加权基尼 = {split_weighted_gini_multiclass(demo, 80.0):.3f}")

切点 80.0 的加权基尼 = 0.476

本章小结

• 特征分三类：名义型直接分叉、有序型按顺序组合二分（两端并组要谨慎，除非真有”尿布”式的共性）、连续型先离散化。
• 离散化三法：等宽、等频、按信息增益/基尼动态找切点；候选切点取相邻数据点的中点。
• 基尼指数 $1-\sum p_j^2$：纯则 0、混则大，免 log、好手算；基尼分裂（加权和）越小越好，与信息增益方向相反——课件逃税例的最优切点是 97.5，加权基尼 0.300。
• 误分类误差最简单，熵理论最完整，基尼居中；没有免费午餐——度量之间没有绝对赢家。
• 树的停止时机是一门平衡艺术：训练误差随树长大一路降，测试误差先降后升。误差可以分解为偏差与方差，多条树可以集成——这是下一章的主角。

📋 行动清单

• 用手头的连续数据分别做等宽、等频、基尼动态三种离散化，对比切出的边界差异
• 把主示例代码里的度量从基尼换成信息熵（去掉 log 的地方换成 $-\sum p\log_2 p$），重扫一遍切点，看最优切点是否还是 97.5
• 思考：为什么”训练误差归零”几乎从来不是好消息？（带着这个问题进入下一章：偏差、方差与集成学习）

—— 小象教研组