深入解析CART决策树算法原理：从数学基础到Python实现

1次阅读

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

决策树是机器学习中最基础也最常用的算法之一，而 CART（Classification and Regression Trees）算法则是决策树家族中的重要成员。今天我们就来深入探讨 CART 算法的原理和实现，特别是针对机器学习初学者常见的困惑点进行详细讲解。

CART 算法由 Breiman 等人在 1984 年提出，它可以同时处理分类和回归问题。与 ID3 和 C4.5 算法不同，CART 生成的是二叉树，每个非叶节点都有两个分支。

决策树的核心是选择最佳分裂特征，CART 使用基尼系数 (Gini Index) 作为分裂标准。基尼系数计算公式如下：

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

其中 $D$ 是数据集，$C_k$ 是第 k 类的样本子集。

对比 ID3 和 C4.5 使用的信息增益(基于熵)：

$$ Entropy(D) = -\sum_{k=1}^{K} \frac{|C_k|}{|D|} log_2 \frac{|C_k|}{|D|} $$

主要区别：
– 基尼系数计算更快(不需要对数运算)
– 两者在实际应用中效果通常很接近

特征选择的伪代码如下：

对于每个特征：对于该特征的每个可能分割点：计算分割后的基尼系数
选择使基尼系数最小的特征和分割点

CART 处理连续特征采用二分法：
1. 将特征值排序
2. 计算相邻值的中间点作为候选分割点
3. 选择最佳分割点

例如，特征值[1,2,3,5]，候选分割点为 1.5,2.5,4

import numpy as np

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

def gini(y):
    _, counts = np.unique(y, return_counts=True)
    probabilities = counts / counts.sum()
    return 1 - np.sum(probabilities ** 2)

def find_best_split(X, y):
    best_gini = float('inf')
    best_feature, best_threshold = None, None

    for feature in range(X.shape[1]):
        thresholds = np.unique(X[:, feature])
        for threshold in thresholds:
            left_indices = X[:, feature] <= threshold
            g = (gini(y[left_indices]) * left_indices.sum() + 
                 gini(y[~left_indices]) * (~left_indices).sum()) / len(y)
            if g < best_gini:
                best_gini = g
                best_feature = feature
                best_threshold = threshold

    return best_feature, best_threshold

def build_tree(X, y, max_depth=5, min_samples_split=2, depth=0):
    # 终止条件
    if (depth >= max_depth or len(y) < min_samples_split or 
        len(np.unique(y)) == 1):
        return TreeNode(value=np.argmax(np.bincount(y)))

    # 寻找最佳分裂
    feature, threshold = find_best_split(X, y)
    if feature is None:
        return TreeNode(value=np.argmax(np.bincount(y)))

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

    return TreeNode(feature=feature, threshold=threshold, left=left, right=right)

剪枝是防止过拟合的关键技术，分为预剪枝和后剪枝：