从零构建ID3决策树：用Python实现信息熵驱动的分类器

决策树算法是机器学习中最直观也最强大的工具之一。想象一下，你正在教一个孩子区分水果——你会先问"它是红色的吗？"，如果是，再问"它表面光滑吗？"，通过一系列这样的问题最终确定答案。这正是决策树的工作方式，而ID3算法则是构建这种"问题序列"的经典方法。

不同于直接调用scikit-learn的黑箱操作，本文将带你从数学基础到完整实现，一步步构建自己的ID3决策树。你会真正理解信息熵如何量化不确定性，信息增益如何指导特征选择，以及递归如何构建出高效的分类路径。我们将用纯Python实现所有核心组件，包括：

• 信息熵的数学计算与Python表达
• 条件熵与信息增益的代码实现
• 递归构建决策树的工程技巧
• 分类预测的树遍历逻辑

1. 信息熵：不确定性的数学度量

信息熵是ID3算法的基石概念，由香农在1948年提出，用来量化系统的不确定性。在决策树中，熵帮助我们衡量标签的混乱程度——熵越高，分类越不确定；熵为零则表示所有样本都属于同一类别。

1.1 熵的数学定义

对于离散随机变量X，其熵H(X)定义为：

H(X) = -Σ p(x)log₂p(x)

其中p(x)是x出现的概率。在Python中实现这个公式时，我们需要：

1. 统计每个标签出现的次数
2. 计算各标签的概率
3. 对概率应用对数运算并求和

import numpy as np

def entropy(labels):
    """计算标签的信息熵"""
    _, counts = np.unique(labels, return_counts=True)
    probabilities = counts / len(labels)
    return -np.sum(probabilities * np.log2(probabilities))

1.2 熵的实际意义

考虑一个二分类问题：

案例	标签分布	熵值
完全纯净	[10, 0]	0.0
均匀混合	[5, 5]	1.0
轻微倾斜	[7, 3]	0.881

注意：当所有样本属于同一类别时，熵达到最小值0；当类别均匀分布时，熵达到最大值1（对二分类）

2. 条件熵与信息增益：特征选择的指南针

有了熵的概念，我们就能定义条件熵——在已知某个特征条件下，标签的不确定性。信息增益则是熵与条件熵的差值，表示通过知道该特征能减少多少不确定性。

2.1 条件熵的计算

条件熵H(Y|X)表示在已知特征X的条件下Y的不确定性：

H(Y|X) = Σ p(x)H(Y|X=x)

Python实现需要：

1. 找出特征的所有唯一值
2. 对每个值计算子集的熵
3. 按比例加权求和

def conditional_entropy(features, labels, feature_idx):
    """计算指定特征的条件熵"""
    feature_values = np.unique(features[:, feature_idx])
    total_entropy = 0.0
    
    for value in feature_values:
        subset_mask = features[:, feature_idx] == value
        subset_labels = labels[subset_mask]
        prob = len(subset_labels) / len(labels)
        total_entropy += prob * entropy(subset_labels)
    
    return total_entropy

2.2 信息增益的计算

信息增益IG(Y,X)就是熵减去条件熵：

IG(Y,X) = H(Y) - H(Y|X)

在代码中只需组合前面的函数：

def information_gain(features, labels, feature_idx):
    """计算指定特征的信息增益"""
    return entropy(labels) - conditional_entropy(features, labels, feature_idx)

3. 递归构建决策树

有了信息增益这个工具，我们就可以实现ID3算法的核心——递归地选择信息增益最大的特征进行分裂，直到满足停止条件。

3.1 选择最佳特征

遍历所有特征，计算它们的信息增益，选择增益最大的：

def choose_best_feature(features, labels):
    """选择信息增益最大的特征"""
    best_gain = -1
    best_feature = None
    
    for feature_idx in range(features.shape[1]):
        gain = information_gain(features, labels, feature_idx)
        if gain > best_gain:
            best_gain = gain
            best_feature = feature_idx
            
    return best_feature

3.2 递归构建树结构

决策树的构建遵循以下递归过程：

1. 如果所有标签相同，返回该标签
2. 如果没有特征可分，返回最常见的标签
3. 否则：
   • 选择最佳特征
   • 为每个特征值创建分支
   • 对每个分支递归建树

def build_tree(features, labels, feature_names=None):
    """递归构建决策树"""
    
    # 基本情况1：所有标签相同
    if len(np.unique(labels)) == 1:
        return labels[0]
    
    # 基本情况2：没有特征可分
    if features.shape[1] == 0:
        return np.bincount(labels).argmax()
    
    best_feature = choose_best_feature(features, labels)
    tree = {best_feature: {}}
    
    # 获取该特征的所有唯一值
    feature_values = np.unique(features[:, best_feature])
    
    for value in feature_values:
        # 创建子集
        subset_mask = features[:, best_feature] == value
        subset_features = np.delete(features[subset_mask], best_feature, axis=1)
        subset_labels = labels[subset_mask]
        
        # 递归构建子树
        subtree = build_tree(subset_features, subset_labels)
        tree[best_feature][value] = subtree
    
    return tree

4. 预测与树遍历

构建好决策树后，我们需要实现预测功能——根据特征值遍历树结构，直到到达叶节点。

4.1 树的遍历预测

预测过程是从根节点开始，根据特征值选择分支，直到到达叶节点：

def predict(tree, sample):
    """使用决策树预测单个样本"""
    if not isinstance(tree, dict):
        return tree  # 到达叶节点
    
    feature_idx = next(iter(tree))
    feature_value = sample[feature_idx]
    
    if feature_value in tree[feature_idx]:
        subtree = tree[feature_idx][feature_value]
        return predict(subtree, sample)
    else:
        # 处理未见过的特征值
        return None

4.2 批量预测

对多个样本进行预测：

def predict_batch(tree, features):
    """批量预测"""
    return np.array([predict(tree, sample) for sample in features])

5. 实战：鸢尾花分类

让我们用经典的鸢尾花数据集测试我们的实现。这个数据集包含150个样本，每个样本有4个特征（花萼长度、花萼宽度、花瓣长度、花瓣宽度）和3个类别标签。

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

# 加载数据
iris = load_iris()
X, y = iris.data, iris.target

# 划分训练测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 构建决策树
tree = build_tree(X_train, y_train)

# 预测并评估
predictions = predict_batch(tree, X_test)
accuracy = np.mean(predictions == y_test)
print(f"测试准确率: {accuracy:.2f}")

提示：实际应用中，我们需要处理连续特征（通过离散化）、缺失值、过拟合等问题。这些是完整决策树实现需要考虑的进阶话题。

6. 决策树的局限与改进

虽然我们的实现已经可以工作，但ID3算法有一些固有局限：

1. 倾向于选择取值多的特征 ：信息增益对可取值数目较多的特征有所偏好
2. 无法处理连续特征 ：需要先离散化处理
3. 容易过拟合 ：没有剪枝机制

这些局限催生了后来的C4.5算法（引入信息增益率）和CART算法（使用基尼系数）。在实际项目中，你可能会发现：

• 对于取值分布不均匀的特征，信息增益可能不是最佳选择标准
• 递归深度需要控制以防止过拟合
• 添加提前停止条件（如最大深度、最小样本数）能提升模型泛化能力

def build_tree_improved(features, labels, max_depth=5, min_samples_split=2, depth=0):
    """改进版决策树，添加深度控制和最小样本限制"""
    
    if (depth >= max_depth) or (len(labels) < min_samples_split):
        return np.bincount(labels).argmax()
    
    if len(np.unique(labels)) == 1:
        return labels[0]
    
    best_feature = choose_best_feature(features, labels)
    tree = {best_feature: {}}
    
    feature_values = np.unique(features[:, best_feature])
    
    for value in feature_values:
        subset_mask = features[:, best_feature] == value
        subset_features = np.delete(features[subset_mask], best_feature, axis=1)
        subset_labels = labels[subset_mask]
        
        if len(subset_labels) == 0:
            tree[best_feature][value] = np.bincount(labels).argmax()
        else:
            subtree = build_tree_improved(
                subset_features, subset_labels, 
                max_depth, min_samples_split, depth+1
            )
            tree[best_feature][value] = subtree
    
    return tree

7. 可视化决策过程

理解决策树最好的方式之一是可视化它的决策路径。虽然我们不会深入可视化代码，但了解树的表示方式很重要：

{'特征索引': {
    '值1': '类别' 或 {子决策树},
    '值2': '类别' 或 {子决策树},
    ...
}}

例如，一个简单的决策树可能看起来像：

{
    2: {  # 花瓣长度
        0: 0,  # <=0.8cm的是setosa
        1: {
            3: {  # 花瓣宽度
                0: 1,  # <=1.65cm的是versicolor
                1: 2   # >1.65cm的是virginica
            }
        }
    }
}

这种结构清晰地展示了决策路径：先检查花瓣长度，如果大于0.8cm再检查花瓣宽度，最终确定类别。