决策树 ID3 算法实战：从熵与信息增益到 Python 代码实现

决策树是机器学习中最直观且强大的算法之一，而 ID3 算法作为其经典实现，通过信息论原理构建分类模型。本文将深入解析熵与信息增益的数学本质，并逐步实现完整的 Python 决策树构建流程，最终通过可视化展示决策逻辑。

1. 决策树与 ID3 算法基础

决策树模仿人类决策过程，通过一系列规则对数据进行分类。ID3（Iterative Dichotomiser 3）算法由 Ross Quinlan 在 1986 年提出，它使用信息增益作为特征选择标准，递归构建树结构。

核心概念对比 ：

术语	数学表达	直观解释
熵	H(S)=-∑pᵢlog₂pᵢ	系统混乱程度度量
信息增益	Gain(D,A)=H(D)-∑(	Dᵥ

在 Python 中计算熵的函数实现：

import math

def entropy(class_probabilities):
    return sum(-p * math.log2(p) for p in class_probabilities if p > 0)

def class_probabilities(labels):
    total_count = len(labels)
    return [count/total_count for count in Counter(labels).values()]

2. 关键数学原理实现

2.1 信息增益计算

信息增益衡量特征对分类效果的提升，计算步骤如下：

1. 计算数据集原始熵
2. 按特征划分后计算各子集熵
3. 求加权平均子集熵
4. 原始熵与子集熵的差即为增益

from collections import Counter

def information_gain(attributes, labels, feature_index):
    # 计算原始熵
    total_entropy = entropy(class_probabilities(labels))
    
    # 按特征值分组
    feature_values = [attr[feature_index] for attr in attributes]
    partitions = defaultdict(list)
    for attr, label in zip(attributes, labels):
        partitions[attr[feature_index]].append(label)
    
    # 计算加权熵
    weighted_entropy = 0.0
    for value, subset_labels in partitions.items():
        prob = len(subset_labels) / len(labels)
        weighted_entropy += prob * entropy(class_probabilities(subset_labels))
    
    return total_entropy - weighted_entropy

2.2 特征选择策略

ID3 采用贪心算法，每次选择信息增益最大的特征作为节点：

def best_feature_to_split(attributes, labels):
    num_features = len(attributes[0])
    gains = [information_gain(attributes, labels, i) 
             for i in range(num_features)]
    return max(range(num_features), key=lambda i: gains[i])

3. 完整决策树构建

3.1 树节点结构设计

决策树采用递归结构，节点包含：

• 特征索引（非叶节点）
• 特征值到子节点的映射
• 类别标签（叶节点）

class DecisionNode:
    def __init__(self, feature_index=None, branches=None, label=None):
        self.feature_index = feature_index  # 非叶节点的分裂特征
        self.branches = branches or {}      # 子节点字典 {特征值: 节点}
        self.label = label                  # 叶节点的类别标签

3.2 递归构建算法

构建过程遵循以下递归逻辑：

1. 如果所有样本属于同一类，返回叶节点
2. 如果没有剩余特征，返回多数类叶节点
3. 选择最佳分裂特征
4. 对每个特征值递归构建子树

def build_tree(attributes, labels, feature_names):
    # 终止条件1：所有样本同类别
    if len(set(labels)) == 1:
        return DecisionNode(label=labels[0])
    
    # 终止条件2：无剩余特征
    if not feature_names:
        majority_label = Counter(labels).most_common(1)[0][0]
        return DecisionNode(label=majority_label)
    
    best_index = best_feature_to_split(attributes, labels)
    best_name = feature_names[best_index]
    
    # 构建子树
    partitions = defaultdict(list)
    partitioned_labels = defaultdict(list)
    for attr, label in zip(attributes, labels):
        key = attr[best_index]
        partitions[key].append(attr[:best_index] + attr[best_index+1:])
        partitioned_labels[key].append(label)
    
    branches = {
        value: build_tree(sub_attrs, partitioned_labels[value], 
                         feature_names[:best_index] + feature_names[best_index+1:])
        for value, sub_attrs in partitions.items()
    }
    
    return DecisionNode(feature_index=best_index, branches=branches)

4. 案例实战：餐厅吸引力预测

我们使用经典数据集预测餐厅是否具有吸引力：

温度	口味	份量	吸引力
热	甜	大	否
热	酸	大	否
热	甜	小	是
冷	咸	小	否
冷	甜	大	否
冷	酸	大	是
冷	甜	小	是

数据预处理 ：

features = ['温度', '口味', '份量']
data = [
    ['热', '甜', '大'],
    ['热', '酸', '大'],
    ['热', '甜', '小'],
    ['冷', '咸', '小'],
    ['冷', '甜', '大'],
    ['冷', '酸', '大'],
    ['冷', '甜', '小']
]
labels = ['否', '否', '是', '否', '否', '是', '是']

构建决策树 ：

restaurant_tree = build_tree(data, labels, features)

5. 决策树可视化

使用 Graphviz 实现决策树可视化：

from graphviz import Digraph

def visualize_tree(tree, feature_names, dot=None, parent_node=None, edge_label=None):
    if dot is None:
        dot = Digraph(comment='Decision Tree')
        dot.attr('node', shape='box')
    
    node_id = str(id(tree))
    label = (feature_names[tree.feature_index] if tree.feature_index is not None 
             else f"分类: {tree.label}")
    dot.node(node_id, label=label)
    
    if parent_node:
        dot.edge(parent_node, node_id, label=edge_label or '')
    
    if tree.branches:
        for value, child in tree.branches.items():
            visualize_tree(child, feature_names, dot, node_id, str(value))
    
    return dot

# 生成可视化图形
graph = visualize_tree(restaurant_tree, features)
graph.render('restaurant_decision_tree', view=True)

可视化结果将显示决策路径：

1. 首先按"口味"分裂
2. "酸"分支直接分类为"是"
3. "甜"分支继续按"份量"分裂
4. "咸"分支分类为"否"

6. 模型预测与评估

实现预测函数对新样本进行分类：

def predict(tree, sample, feature_names):
    if tree.label is not None:
        return tree.label
    
    feature_value = sample[tree.feature_index]
    if feature_value not in tree.branches:
        return None  # 处理未见特征值
    
    remaining_sample = sample[:tree.feature_index] + sample[tree.feature_index+1:]
    remaining_features = feature_names[:tree.feature_index] + feature_names[tree.feature_index+1:]
    return predict(tree.branches[feature_value], remaining_sample, remaining_features)

# 测试样本预测
test_sample = ['冷', '甜', '小']
print(predict(restaurant_tree, test_sample, features))  # 输出: 是

评估指标实现 ：

def evaluate(tree, test_data, test_labels, feature_names):
    correct = 0
    for sample, label in zip(test_data, test_labels):
        prediction = predict(tree, sample, feature_names)
        if prediction == label:
            correct += 1
    return correct / len(test_labels)

7. 算法优化与扩展

7.1 处理连续特征

ID3 原生支持离散特征，扩展连续特征处理：

def find_best_split(continuous_values, labels):
    unique_values = sorted(set(continuous_values))
    thresholds = [(unique_values[i] + unique_values[i+1])/2 
                 for i in range(len(unique_values)-1)]
    
    best_threshold = None
    best_gain = -1
    
    for threshold in thresholds:
        left_labels = [label for value, label in zip(continuous_values, labels) 
                      if value <= threshold]
        right_labels = [label for value, label in zip(continuous_values, labels) 
                       if value > threshold]
        
        current_gain = information_gain(labels, left_labels + right_labels)
        if current_gain > best_gain:
            best_gain = current_gain
            best_threshold = threshold
    
    return best_threshold, best_gain

7.2 预剪枝策略

防止过拟合的预剪枝方法：

def build_tree_with_pruning(attributes, labels, feature_names, max_depth=3, min_samples=2):
    if len(set(labels)) == 1:
        return DecisionNode(label=labels[0])
    
    if not feature_names or len(labels) < min_samples or max_depth == 0:
        majority_label = Counter(labels).most_common(1)[0][0]
        return DecisionNode(label=majority_label)
    
    best_index = best_feature_to_split(attributes, labels)
    best_name = feature_names[best_index]
    
    partitions = defaultdict(list)
    partitioned_labels = defaultdict(list)
    for attr, label in zip(attributes, labels):
        key = attr[best_index]
        partitions[key].append(attr[:best_index] + attr[best_index+1:])
        partitioned_labels[key].append(label)
    
    branches = {
        value: build_tree_with_pruning(
            sub_attrs, partitioned_labels[value], 
            feature_names[:best_index] + feature_names[best_index+1:],
            max_depth-1, min_samples)
        for value, sub_attrs in partitions.items()
    }
    
    return DecisionNode(feature_index=best_index, branches=branches)

决策树 ID3 算法虽然简单，但包含了机器学习模型构建的核心思想。通过本实现，我们不仅掌握了算法原理，还构建了可扩展的代码框架。在实际项目中，可以进一步扩展为 C4.5 或 CART 算法，加入增益率或基尼系数等改进指标。