深入解析CART决策树的计算步骤：从理论到实现

1次阅读

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

决策树是机器学习中常用的算法之一，因其直观的解释性和广泛的应用场景而备受青睐。CART（Classification and Regression Trees）算法是一种经典的决策树算法，既可以用于分类问题，也可以用于回归问题。与 ID3 和 C4.5 算法相比，CART 采用二叉树结构，更适合处理连续特征和复杂数据集。

基尼系数是 CART 算法中用于衡量节点纯度的指标，其计算公式为：

Gini = 1 - Σ (p_i)^2

其中，p_i是节点中第 i 类样本所占的比例。基尼系数越小，说明节点的纯度越高。

虽然 CART 主要使用基尼系数，但在某些实现中也会用到信息增益。信息增益基于信息熵，用于衡量特征分裂前后的信息不确定性减少程度。

CART 算法通过遍历所有特征及其可能的切分点，选择基尼系数最小的特征和切分点作为当前节点的分裂标准。

一旦确定了最佳特征和切分点，算法将数据集分成两部分，分别进入左右子节点。这一过程递归进行，直到满足停止条件（如节点样本数小于阈值或基尼系数低于阈值）。

为了防止过拟合，CART 通常会进行剪枝操作。剪枝分为预剪枝和后剪枝，前者在树构建过程中提前停止分裂，后者在树构建完成后通过交叉验证选择最优子树。

以下是一个简化的 Python 实现，展示如何从零构建 CART 决策树：

import numpy as np

class Node:
    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):
    classes = np.unique(y)
    gini = 1
    for c in classes:
        p = np.sum(y == c) / len(y)
        gini -= p ** 2
    return gini

def 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
            right_indices = X[:, feature] > threshold

            if len(y[left_indices]) == 0 or len(y[right_indices]) == 0:
                continue

            current_gini = (len(y[left_indices]) * gini(y[left_indices]) + 
                            len(y[right_indices]) * gini(y[right_indices])) / len(y)

            if current_gini < best_gini:
                best_gini = current_gini
                best_feature = feature
                best_threshold = threshold

    return best_feature, best_threshold

def build_tree(X, y, max_depth=5, min_samples_split=2):
    if len(y) < min_samples_split or max_depth == 0:
        return Node(value=np.argmax(np.bincount(y)))

    feature, threshold = best_split(X, y)

    if feature is None:
        return Node(value=np.argmax(np.bincount(y)))

    left_indices = X[:, feature] <= threshold
    right_indices = X[:, feature] > threshold

    left = build_tree(X[left_indices], y[left_indices], max_depth-1, min_samples_split)
    right = build_tree(X[right_indices], y[right_indices], max_depth-1, min_samples_split)

    return Node(feature, threshold, left, right)