CART决策树算法原理与实现：从数学推导到Python实战

1次阅读

没有评论

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

在机器学习的世界里，我们常常需要在模型性能和可解释性之间做取舍。深度学习模型虽然强大，但它们的决策过程往往像个黑盒子。而决策树则以直观的树形结构，清晰地展示出从特征到结论的推理路径，这种特性在以下场景中尤为宝贵：

金融风控需要向客户解释拒绝贷款的原因
医疗诊断希望理解决策依据
商业分析需要直观的规则提取

CART(Classification And Regression Trees) 是决策树家族中的重要成员，与 ID3 和 C4.5 算法相比有几个关键区别：

二叉树结构 ：每个节点只做二元分裂，简化决策路径
基尼系数 ：使用基尼不纯度代替信息增益
回归能力 ：既可处理分类问题也能解决回归任务
高效的剪枝 ：采用代价复杂度剪枝避免过拟合

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

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

其中 $p_k$ 是第 k 类样本在数据集中的比例。当所有样本都属于同一类别时，基尼系数为 0，表示完全纯净。

计算示例 ：

假设我们要根据天气预测是否打网球，有以下数据：

 天气 | 打球
-----|-----
晴   | 是
晴   | 否
阴   | 是
雨   | 是

根节点的基尼系数：1 – (3/4)^2 – (1/4)^2 = 0.375
按 ” 天气 = 晴 ” 分裂后：
左节点 (晴)：1 – (1/2)^2 – (1/2)^2 = 0.5
右节点 (非晴)：1 – (2/2)^2 – (0/2)^2 = 0
加权基尼：(2/4)0.5 + (2/4)0 = 0.25

分裂后的基尼系数下降，说明这个分裂是有益的。

class TreeNode:
    """ 决策树节点类

    Attributes:
        feature_index: int, 分裂特征索引
        threshold: float, 分裂阈值
        left: TreeNode, 左子树
        right: TreeNode, 右子树
        value: Any, 叶节点的预测值
        is_leaf: bool, 是否为叶节点
    """
    def __init__(self, feature_index=None, threshold=None, 
                 left=None, right=None, value=None, is_leaf=False):
        self.feature_index = feature_index
        self.threshold = threshold
        self.left = left
        self.right = right
        self.value = value
        self.is_leaf = is_leaf

def build_tree(X, y, depth=0, max_depth=None, min_samples_split=2):
    """ 递归构建决策树

    实现要点：1. 检查停止条件
    2. 寻找最佳分裂
    3. 递归构建子树
    """
    n_samples, n_features = X.shape
    n_classes = len(np.unique(y))

    # 停止条件
    if (n_classes == 1 or 
        (max_depth is not None and depth >= max_depth) or 
        n_samples < min_samples_split):
        return TreeNode(value=np.argmax(np.bincount(y)),
            is_leaf=True
        )

    # 寻找最佳分裂
    best_gini = float('inf')
    best_feature, best_threshold = None, None

    for feature_idx in range(n_features):
        thresholds = np.unique(X[:, feature_idx])
        for threshold in thresholds:
            left_indices = X[:, feature_idx] <= threshold
            right_indices = ~left_indices

            if np.sum(left_indices) == 0 or np.sum(right_indices) == 0:
                continue

            gini = calculate_weighted_gini(y[left_indices], y[right_indices])

            if gini < best_gini:
                best_gini = gini
                best_feature = feature_idx
                best_threshold = threshold

    # 如果没有找到合适的分裂，返回叶节点
    if best_gini == float('inf'):
        return TreeNode(value=np.argmax(np.bincount(y)), is_leaf=True)

    # 递归构建子树
    left_indices = X[:, best_feature] <= best_threshold
    left = build_tree(X[left_indices], y[left_indices], depth+1, max_depth, min_samples_split)
    right = build_tree(X[~left_indices], y[~left_indices], depth+1, max_depth, min_samples_split)

    return TreeNode(
        feature_index=best_feature,
        threshold=best_threshold,
        left=left,
        right=right
    )

def calculate_gini(y):
    """计算单个节点的基尼系数"""
    _, counts = np.unique(y, return_counts=True)
    probs = counts / len(y)
    return 1 - np.sum(probs ** 2)

def calculate_weighted_gini(y_left, y_right):
    """计算分裂后的加权基尼系数"""
    n_left, n_right = len(y_left), len(y_right)
    n_total = n_left + n_right

    gini_left = calculate_gini(y_left)
    gini_right = calculate_gini(y_right)

    return (n_left/n_total)*gini_left + (n_right/n_total)*gini_right

我们使用经典的鸢尾花数据集进行测试：

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split

# 加载数据
iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 我们的实现
our_tree = build_tree(X_train, y_train, max_depth=3)
our_pred = predict(our_tree, X_test)
our_acc = np.mean(our_pred == y_test)

# sklearn 实现
sklearn_tree = DecisionTreeClassifier(max_depth=3, random_state=42)
sklearn_tree.fit(X_train, y_train)
sklearn_acc = sklearn_tree.score(X_test, y_test)

print(f"我们的准确率: {our_acc:.2f}")
print(f"sklearn 准确率: {sklearn_acc:.2f}")