决策树实战：从零解析CART算法构造流程与实现细节

1次阅读

没有评论

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

CART（Classification and Regression Trees）是决策树家族中最常用的算法之一。与 ID3 和 C4.5 不同，CART 算法可以同时处理分类和回归问题，这使其在实际应用中非常灵活。

分类树 ：使用基尼系数（Gini Index）作为分裂标准
基尼系数公式：$Gini(D) = 1 – \sum_{k=1}^K (p_k)^2$
其中 $p_k$ 是样本属于第 k 类的概率
回归树 ：使用平方误差最小化作为分裂标准
目标是最小化：$\sum_{i \in R_1}(y_i – c_1)^2 + \sum_{i \in R_2}(y_i – c_2)^2$
其中 $c_1$ 和 $c_2$ 是两个子区域的输出均值

对于分类问题 ：
计算每个特征的基尼指数
选择使基尼指数减少最多的特征
对于回归问题 ：
遍历所有可能的切分点
选择使平方误差最小的切分

连续值处理 ：
对特征值排序
取相邻值的中点作为候选切分点
离散值处理 ：
对于 m 个取值，考虑 $2^{m-1}-1$ 种划分方式
实践中常使用二分法简化计算

节点中的样本数少于预定阈值
所有特征的分裂增益小于预定阈值
树达到最大深度

import numpy as np
from sklearn.datasets import load_iris

class TreeNode:
    """决策树节点类"""
    def __init__(self, feature_idx=None, threshold=None, value=None, left=None, right=None):
        self.feature_idx = feature_idx  # 分裂特征索引
        self.threshold = threshold      # 分裂阈值
        self.value = value              # 叶节点值
        self.left = left                # 左子树
        self.right = right              # 右子树

class CART:
    """CART 决策树实现"""
    def __init__(self, max_depth=None, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split

    def fit(self, X, y):
        self.n_classes = len(np.unique(y))
        self.n_features = X.shape[1]
        self.tree = self._grow_tree(X, y)

    def _gini(self, y):
        """计算基尼系数"""
        m = y.size
        return 1.0 - sum((np.sum(y == c) / m) ** 2 for c in range(self.n_classes))

    def _best_split(self, X, y):
        """寻找最佳分裂特征和阈值"""
        # 实现细节省略...

    def _grow_tree(self, X, y, depth=0):
        """递归构建决策树"""
        # 停止条件检查
        if (self.max_depth is not None and depth >= self.max_depth) or \
           len(y) < self.min_samples_split or len(np.unique(y)) == 1:
            return TreeNode(value=self._leaf_value(y))

        # 寻找最佳分裂
        idx, thr = self._best_split(X, y)

        # 递归构建子树
        left_idx = X[:, idx] <= thr
        right_idx = X[:, idx] > thr
        left = self._grow_tree(X[left_idx], y[left_idx], depth+1)
        right = self._grow_tree(X[right_idx], y[right_idx], depth+1)

        return TreeNode(feature_idx=idx, threshold=thr, left=left, right=right)