CART决策树简单实现：从原理到生产环境避坑指南

1次阅读

没有评论

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

虽然 Scikit-learn 等库提供了现成的决策树实现，但在实际工程中常遇到三个问题：

计算冗余：传统递归实现会重复计算同一节点的基尼系数
内存泄漏风险：深度优先遍历时未及时释放临时变量
接口僵化：难以自定义分裂评估函数（如改用信息增益比）

决策树的核心是找到最佳分裂点，基尼系数计算公式如下：

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

伪代码实现逻辑：

统计当前节点中各类别的样本数
计算每个类别占比的平方和
用 1 减去该和值

对于连续特征，通常需要排序后遍历可能的分裂点：

对特征值进行排序
计算相邻值的中间点作为候选分裂点
选择使基尼系数下降最大的分裂点

from typing import List, Dict, Optional
import numpy as np

class CartNode:
    def __init__(self, feature_idx: int = -1, threshold: float = 0.0,
                 left: Optional['CartNode'] = None, right: Optional['CartNode'] = None):
        self.feature_idx = feature_idx  # 分裂特征索引
        self.threshold = threshold      # 分裂阈值
        self.left = left                # 左子树
        self.right = right              # 右子树

class DecisionTreeClassifier:
    def __init__(self, max_depth: int = 3):
        self.max_depth = max_depth
        self.root: Optional[CartNode] = None

    def _gini(self, y: np.ndarray) -> float:
        """计算基尼系数"""
        _, counts = np.unique(y, return_counts=True)
        proportions = counts / len(y)
        return 1 - np.sum(proportions ** 2)

    def fit(self, X: np.ndarray, y: np.ndarray) -> None:
        """训练入口方法"""
        self.root = self._build_tree(X, y, depth=0)

    # 其余方法实现...

传统实现中容易出现的性能瓶颈：