从零开始理解CART决策树算法：原理与Python实战

1次阅读

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

决策树是机器学习中最直观的算法之一，它模仿人类做决策的过程，通过一系列判断条件对数据进行分类或回归。CART（Classification and Regression Trees）是其中最经典的算法，由 Breiman 等人于 1984 年提出。与其他决策树算法（如 ID3、C4.5）相比，CART 有两大特点：

二元分裂 ：每个节点只生成两个子节点，形成二叉树结构
多功能性 ：既能处理分类任务（使用基尼系数），也能处理回归任务（使用平方误差）

基尼系数衡量数据的不纯度，计算公式为：

$$ Gini(p) = 1 – \sum_{k=1}^K p_k^2 $$

其中 $p_k$ 是第 k 类样本的比例。分裂时选择使基尼系数下降最多的特征：

$$ \Delta Gini = Gini(D) – \sum_{v=1}^V \frac{|D_v|}{|D|}Gini(D_v) $$

对于回归树，分裂标准是最小化平方误差：

$$ \min_{j,s} \left[\min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i – c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i – c_2)^2 \right] $$

其中 $R_1,R_2$ 是分裂后的两个区域，$c_1,c_2$ 是各自区域的输出值（通常取均值）。

class Node:
    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              # 叶节点值

import numpy as np

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

    def _gini(self, y):
        classes = np.unique(y)
        return 1 - sum([(np.sum(y == c) / len(y))**2 for c in classes])

    def _best_split(self, X, 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_idx = X[:, feature_idx] <= thresh
                gini = (left_idx.sum() * self._gini(y[left_idx]) + 
                       (~left_idx).sum() * self._gini(y[~left_idx])) / len(y)
                if gini < best_gini:
                    best_gini = gini
                    best_feature = feature_idx
                    best_thresh = thresh
        return best_feature, best_thresh

max_depth：控制树的最大深度，防止过拟合
min_samples_split：节点分裂所需最小样本数
min_samples_leaf：叶节点最少样本数

from sklearn.tree import DecisionTreeClassifier

clf = DecisionTreeClassifier(
    criterion='gini', 
    max_depth=5,
    min_samples_split=10
)
clf.fit(X_train, y_train)

决策树容易过拟合训练数据，表现为：