2、决策树原理（一）：ID3算法详解、决策树的构建过程、特征选择策略

好，咱们正式开始啃决策树这块硬骨头。

说实话，我刚开始学机器学习的时候，第一个真正让我觉得「哇，原来算法可以这么直观」的就是决策树。它不像SVM那样上来就是核函数，也不像神经网络那样像个黑盒子。决策树说白了，就是一堆if-else规则的集合。你想想看，我们平时做决定不也是这样吗？

2.1 决策树长什么样？

先看个最简单的例子。假设你要判断今天要不要去打球。

• 如果「天气=晴」且「湿度=低」，那就去
• 如果「天气=晴」且「湿度=高」，那就不去
• 如果「天气=雨」，那就不去

把这些规则画成树状结构，就是一棵决策树。根节点是「天气」，内部节点是「湿度」，叶子节点是「去」或「不去」。嗯，就是这么简单。

我在项目中遇到过不少新人，一上来就调参调包，连树长什么样都没看过。我建议你，先用手画一棵树，哪怕只有两层，也比直接调RandomForest强。

2.2 ID3算法的核心思想

ID3算法是决策树的鼻祖之一，由Quinlan在1986年提出。它的核心就一句话：每次分裂，选那个能让数据「纯度」提升最快的特征。

什么叫纯度？说白了就是：分裂之后，子节点里的样本尽量属于同一类别。比如一个节点里全是「去打球」，那纯度就是100%。如果一半去一半不去，那纯度就很低。

ID3用「信息增益」来衡量纯度提升。信息增益越大，说明这个特征越适合做分裂。

2.3 熵：混乱程度的度量

熵这个概念来自信息论，是香农老爷子提出来的。公式长这样：

Entropy(S) = - Σ p_i * log₂(p_i)

其中p_i是第i类样本的比例。举个例子：

• 如果样本全是同一类，比如10个样本全是「去」，那p=1，log₂(1)=0，熵=0。完美纯净。
• 如果5个去、5个不去，p=0.5，熵 = -0.5*log₂(0.5) - 0.5*log₂(0.5) = 1。混乱至极。

我刚开始学的时候，总觉得这个公式很抽象。后来我给自己编了个口诀：熵越小，越整齐；熵越大，越乱套。你记住这个就行。

2.4 信息增益的计算过程

咱们用一个经典例子来走一遍流程。这个例子来自《机器学习实战》，我稍微改了一下。

假设我们有14个样本，判断是否适合打球。特征有两个：天气（晴、阴、雨）和湿度（高、正常）。

天气	湿度	是否打球
晴	高	否
晴	高	否
晴	正常	是
晴	正常	是
阴	高	是
阴	正常	是
阴	正常	是
雨	高	否
雨	高	否
雨	正常	否
雨	正常	是
雨	正常	是
晴	高	否
阴	高	是

第一步：计算根节点的熵

14个样本中，打球=「是」的有8个，打球=「否」的有6个。

Entropy(根) = - (8/14)*log₂(8/14) - (6/14)*log₂(6/14)
            ≈ -0.5714*(-0.8074) - 0.4286*(-1.2224)
            ≈ 0.4614 + 0.5239
            ≈ 0.9853

第二步：按「天气」特征分裂

天气有三个取值：晴、阴、雨。

• 天气=晴：5个样本，打球=「是」有2个，打球=「否」有3个。熵 = -2/5*log₂(2/5) - 3/5*log₂(3/5) ≈ 0.9710
• 天气=阴：4个样本，全是「是」。熵 = 0
• 天气=雨：5个样本，打球=「是」有2个，打球=「否」有3个。熵 ≈ 0.9710

加权平均熵 = (5/14)*0.9710 + (4/14)*0 + (5/14)*0.9710 ≈ 0.6936

信息增益 = 0.9853 - 0.6936 = 0.2917

第三步：按「湿度」特征分裂

湿度有两个取值：高、正常。

• 湿度=高：7个样本，打球=「是」有2个，打球=「否」有5个。熵 ≈ 0.8631
• 湿度=正常：7个样本，打球=「是」有6个，打球=「否」有1个。熵 ≈ 0.5917

加权平均熵 = (7/14)*0.8631 + (7/14)*0.5917 ≈ 0.7274

信息增益 = 0.9853 - 0.7274 = 0.2579

第四步：比较

天气的信息增益0.2917 > 湿度的信息增益0.2579。所以根节点选「天气」作为分裂特征。

2.5 决策树的构建过程

构建过程其实就是一个递归。我习惯用伪代码来描述：

函数 BuildTree(数据集, 特征列表):
    如果 数据集中所有样本属于同一类别:
        返回该类别作为叶子节点
    
    如果 特征列表为空:
        返回数据集中出现次数最多的类别作为叶子节点
    
    选择 信息增益最大的特征 best_feature
    
    创建 以 best_feature 为分裂标准的内部节点
    
    对于 best_feature 的每个取值 value:
        子数据集 = 数据集中 best_feature == value 的样本
        如果 子数据集为空:
            子节点 = 数据集中出现次数最多的类别
        否则:
            子节点 = BuildTree(子数据集, 特征列表 - {best_feature})
    
    返回 当前节点

这里有个细节要注意：每次递归时，要把用过的特征从特征列表里移除。不然同一个特征会被反复使用，那就出问题了。

2.6 特征选择策略的深层理解

ID3用的信息增益，说白了就是「这个特征能帮我们消除多少不确定性」。你想想看，如果某个特征取值很多，比如「编号」这种唯一标识，它的信息增益会非常大——因为每个取值只对应一个样本，分裂后每个子节点纯度都是100%。

但这显然不合理。这就是ID3的一个大问题：倾向于选择取值多的特征。

我记得有一次做用户画像分类，特征里有「用户ID」，ID3直接把它选成了根节点。结果树长成了这样：每个叶子节点只有一个用户。泛化能力？不存在的。

所以后来才有了C4.5算法，用信息增益比来替代信息增益。这个咱们下一章再细聊。

2.7 代码实现：手写一个ID3

光说不练假把式。我写了一个极简版的ID3，帮你理解核心逻辑。

import numpy as np
from collections import Counter

def entropy(y):
    """计算熵"""
    counter = Counter(y)
    total = len(y)
    ent = 0.0
    for count in counter.values():
        p = count / total
        ent -= p * np.log2(p) if p > 0 else 0
    return ent

def information_gain(X, y, feature_idx):
    """计算某个特征的信息增益"""
    total_entropy = entropy(y)
    values = set(X[:, feature_idx])
    weighted_entropy = 0.0
    for v in values:
        mask = X[:, feature_idx] == v
        sub_y = y[mask]
        weighted_entropy += (len(sub_y) / len(y)) * entropy(sub_y)
    return total_entropy - weighted_entropy

def id3_fit(X, y, features):
    """极简版ID3训练"""
    # 如果所有样本类别相同
    if len(set(y)) == 1:
        return {'type': 'leaf', 'class': y[0]}
    
    # 如果没有特征可用
    if len(features) == 0:
        return {'type': 'leaf', 'class': Counter(y).most_common(1)[0][0]}
    
    # 选择信息增益最大的特征
    gains = [information_gain(X, y, f) for f in features]
    best_idx = features[np.argmax(gains)]
    
    tree = {'type': 'node', 'feature': best_idx, 'children': {}}
    
    # 递归构建子树
    values = set(X[:, best_idx])
    for v in values:
        mask = X[:, best_idx] == v
        sub_X = X[mask]
        sub_y = y[mask]
        remaining_features = [f for f in features if f != best_idx]
        tree['children'][v] = id3_fit(sub_X, sub_y, remaining_features)
    
    return tree

这段代码去掉了很多边界检查和优化，但核心逻辑是完整的。你可以在小数据集上跑跑看，感受一下。

2.8 本章小结

咱们这一章讲了ID3算法的三个核心点：

• 熵：衡量数据混乱程度的指标，越小越纯
• 信息增益：分裂前后熵的差值，越大说明特征越好
• 递归构建：每次选最优特征，然后对每个取值递归建树

ID3虽然简单，但它是理解后续所有树模型的基础。你把这个搞透了，C4.5、CART、随机森林，学起来都会轻松很多。

下一章咱们聊C4.5算法，看看它是怎么解决ID3「偏爱取值多的特征」这个毛病的。到时候我会分享一个我在金融风控项目里踩过的坑，跟这个特性有关。

先消化这一章的内容，有问题随时交流。