CART决策树算法深度解析：从数学原理到工程实践

1次阅读

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

决策树是机器学习中最直观的算法之一，它通过一系列规则对数据进行分类或回归。CART（Classification and Regression Trees）是其中最具代表性的算法，由 Breiman 等人于 1984 年提出。与 ID3 和 C4.5 不同，CART 可以同时处理分类和回归任务，且始终采用二叉树结构。

ID3 算法 ：使用信息增益作为分裂标准，倾向于选择取值多的特征，且只能处理离散特征
C4.5 算法 ：改进为信息增益比，缓解了 ID3 的偏置问题，但仍限于分类任务
CART 算法 ：
分类任务：采用基尼系数（Gini Index）
回归任务：使用最小平方误差

基尼系数计算公式：

Gini(D) = 1 - Σ(p_i)^2

其中 p_i 是第 i 类样本在数据集 D 中的比例。基尼系数越小，数据纯度越高。

以下是 CART 分类树的完整实现，包含三个核心部分：

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

class CARTClassifier:
    def __init__(self, max_depth=None, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split

    def _gini(self, y):
        # 计算基尼系数
        classes = np.unique(y)
        gini = 1.0
        for cls in classes:
            p = np.sum(y == cls) / len(y)
            gini -= p**2
        return gini

    def _best_split(self, X, y):
        # 寻找最优分裂特征和阈值
        best_gini = float('inf')
        best_idx, best_thresh = None, None

        for idx in range(X.shape[1]):
            thresholds = np.unique(X[:, idx])
            for thresh in thresholds:
                left_mask = X[:, idx] <= thresh
                gini = (left_mask.sum() * self._gini(y[left_mask]) + 
                        (~left_mask).sum() * self._gini(y[~left_mask])) / len(y)
                if gini < best_gini:
                    best_gini = gini
                    best_idx, best_thresh = idx, thresh
        return best_idx, best_thresh

    def predict(self, X):
        return np.array([self._predict(x) for x in X])

    def _predict(self, x, node=None):
        if node is None:
            node = self.root
        if node.value is not None:
            return node.value
        if x[node.feature_idx] <= node.threshold:
            return self._predict(x, node.left)
        else:
            return self._predict(x, node.right)