决策树构建与ID3算法解析：从原理到实战避坑指南

1次阅读

共计 1717 个字符，预计需要花费 5 分钟才能阅读完成。

决策树的构建过程（Construction）特指从数据集中递归生成树形结构的具体步骤，而训练过程（Training）是包含数据预处理、特征选择、树构建及后处理的完整流程。常见误区是将两者简单等同：

构建过程 ：核心是特征选择（如 ID3 的信息增益）和节点分裂，直到满足停止条件
训练过程 ：还包括数据清洗、缺失值处理、剪枝优化等环节

ID3 算法采用信息增益作为特征选择标准，公式为：

Gain(S,A) = Entropy(S) - Σ(|Sv|/|S|)*Entropy(Sv)
其中：Entropy(S) = -Σpᵢlog₂pᵢ  # 数据集 S 的经验熵
Sv 表示特征 A 取值为 v 的子集

仅支持离散特征
偏好取值多的特征（需用增益率改进）
无剪枝机制易过拟合

import numpy as np
from collections import Counter

class ID3DecisionTree:
    def __init__(self, max_depth=5):
        self.max_depth = max_depth

    def _entropy(self, y):
        """计算信息熵"""
        counts = np.bincount(y)
        probs = counts / len(y)
        return -np.sum([p * np.log2(p) for p in probs if p > 0])

    def _information_gain(self, X, y, feature_idx):
        """计算指定特征的信息增益"""
        parent_entropy = self._entropy(y)
        unique_values = np.unique(X[:, feature_idx])

        child_entropy = 0
        for val in unique_values:
            mask = X[:, feature_idx] == val
            child_entropy += np.sum(mask)/len(y) * self._entropy(y[mask])

        return parent_entropy - child_entropy

    def _best_feature(self, X, y, features):
        """选择信息增益最大的特征"""
        gains = [self._information_gain(X, y, f) for f in features]
        return features[np.argmax(gains)]

    def fit(self, X, y, depth=0):
        """递归构建决策树"""
        # 终止条件：纯度达到 100% 或超过最大深度
        if len(np.unique(y)) == 1 or depth >= self.max_depth:
            return Counter(y).most_common(1)[0][0]

        # 选择最佳分割特征
        features = list(range(X.shape[1]))
        best_feat = self._best_feature(X, y, features)

        # 递归构建子树
        tree = {best_feat: {}}
        for val in np.unique(X[:, best_feat]):
            mask = X[:, best_feat] == val
            subtree = self.fit(X[mask], y[mask], depth+1)
            tree[best_feat][val] = subtree

        return tree

时间复杂度分析：最坏情况下需遍历所有特征（d）和样本（n），构建完整树的复杂度为 O(d*n²)