从零实现CART决策树代码：机器学习入门实战指南

1次阅读

没有评论

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

作为机器学习初学者，直接调用 sklearn.tree.DecisionTreeClassifier 确实方便，但可能会遇到这些困惑：

黑箱操作导致对分裂过程缺乏直观理解
遇到数据异常时不知道如何调整参数
面试被问到原理时只能回答 ” 调过 API”

自己动手实现一次，你会真正掌握：

如何用基尼系数衡量数据不纯度
递归构建树形结构的编程技巧
避免过拟合的核心方法

决策树分裂的目标是让子节点比父节点更 ” 纯 ”，CART 算法使用基尼系数 (Gini Index) 作为衡量标准：

$$ Gini(D) = 1 – \sum_{k=1}^{K} (\frac{|C_k|}{|D|})^2 $$

其中：
– $D$ 表示当前节点数据集
– $K$ 是类别总数
– $|C_k|$ 是第 $k$ 类样本的数量

当所有样本属于同一类时，基尼系数为 0（最理想情况）。

对于每个候选特征，我们需要：

计算分裂前的基尼系数
尝试所有可能的分裂点（对连续特征需要排序后取中点）
选择使基尼系数下降最多的分裂方案

数学表达式：

$$ \Delta Gini = Gini(D) – \frac{|D_左 |}{|D|}Gini(D_左) – \frac{|D_右 |}{|D|}Gini(D_右) $$

from dataclasses import dataclass
from typing import Any, Optional

@dataclass
class TreeNode:
    feature_idx: Optional[int] = None  # 分裂特征索引
    threshold: Optional[float] = None  # 分裂阈值
    left: Optional['TreeNode'] = None  # 左子树
    right: Optional['TreeNode'] = None # 右子树
    value: Optional[Any] = None       # 叶节点存储的类别

def gini_impurity(y: np.ndarray) -> float:
    """计算基尼不纯度"""
    if len(y) == 0:
        return 0

    probs = np.bincount(y) / len(y)
    return 1 - np.sum(probs ** 2)

def build_tree(X, y, max_depth=5, min_samples_split=2):
    # 终止条件检查
    if len(y) < min_samples_split or max_depth <= 0:
        return TreeNode(value=np.argmax(np.bincount(y)))

    best_gini = float('inf')
    best_feature, best_thresh = None, None

    # 遍历所有特征
    for feature_idx in range(X.shape[1]):
        # 对连续值特征排序并尝试分裂点
        thresholds = np.unique(X[:, feature_idx])
        for thresh in thresholds:
            left_mask = X[:, feature_idx] <= thresh
            gini = weighted_gini(y, left_mask)

            if gini < best_gini:
                best_gini = gini
                best_feature = feature_idx
                best_thresh = thresh

    # 分裂后递归调用
    left_mask = X[:, best_feature] <= best_thresh
    left = build_tree(X[left_mask], y[left_mask], max_depth-1, min_samples_split)
    right = build_tree(X[~left_mask], y[~left_mask], max_depth-1, min_samples_split)

    return TreeNode(feature_idx=best_feature, 
                    threshold=best_thresh,
                    left=left,
                    right=right)

特征预筛选：先用卡方检验选择 Top- K 特征
增量训练：对超大数据集使用在线学习方式
并行化：对不同特征的分裂评估可以并行计算

import matplotlib.pyplot as plt
from sklearn.tree import plot_tree

# 将自实现的树转换为 sklearn 格式（仅用于可视化）def tree_to_sklearn_format(node):
    # 转换逻辑省略...
    pass

plt.figure(figsize=(12,8))
plot_tree(tree_to_sklearn_format(root), filled=True)
plt.show()

问题现象	可能原因	解决方案
基尼系数为负数	样本计数时整数溢出	检查 `np.bincount` 输入数据类型
树深度爆炸	缺少终止条件	添加 `max_depth` 和`min_samples_split`限制
预测准确率低	连续特征未离散化	对连续特征排序后取中点作为候选分裂点