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

1次阅读

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

决策树是机器学习中最直观的算法之一，广泛应用于分类和回归任务。CART（Classification and Regression Trees）算法是一种经典的决策树算法，由 Breiman 等人于 1984 年提出。它的核心思想是通过递归地将数据集划分为更纯的子集，从而构建一棵树状模型。CART 算法不仅能处理分类问题（通过基尼系数），还能处理回归问题（通过平方误差）。

基尼系数是 CART 算法中用于分类问题的纯度度量标准。它表示从数据集中随机抽取两个样本，其类别标签不一致的概率。基尼系数越小，数据集的纯度越高。计算公式如下：

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

其中，p_i是数据集中第 i 类样本的比例。

信息增益是另一种常见的纯度度量标准，常用于 ID3 和 C4.5 算法。虽然 CART 主要使用基尼系数，但了解信息增益有助于对比不同算法的特点。信息增益基于信息熵，计算公式为：

Entropy(D) = -Σ p_i * log2(p_i)

信息增益是父节点的熵与子节点熵的加权平均之差。

特征选择：遍历所有特征及其可能的分割点，计算基尼系数（分类）或平方误差（回归），选择使不纯度下降最多的特征和分割点。
节点分裂：根据选定的特征和分割点，将数据集划分为左右子节点。
递归构建：对每个子节点重复上述过程，直到满足停止条件（如节点样本数小于阈值、基尼系数低于阈值或树达到最大深度）。
剪枝：为了防止过拟合，可以对生成的树进行剪枝。剪枝分为预剪枝（在构建过程中提前停止）和后剪枝（构建完成后剪去部分子树）。

以下是一个简化的 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  # 叶节点的预测值

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

    def _gini(self, y):
        classes = np.unique(y)
        gini = 1.0
        for c in classes:
            p = np.sum(y == c) / len(y)
            gini -= p ** 2
        return gini

    def _best_split(self, 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
                gini_left = self._gini(y[left_indices])
                gini_right = self._gini(y[right_indices])
                gini = (len(y[left_indices]) * gini_left + len(y[right_indices]) * gini_right) / len(y)
                if gini < best_gini:
                    best_gini = gini
                    best_feature = feature
                    best_threshold = threshold
        return best_feature, best_threshold

    def _build_tree(self, X, y, depth=0):
        if depth == self.max_depth or len(np.unique(y)) == 1:
            return Node(value=np.argmax(np.bincount(y)))

        feature, threshold = self._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 = self._build_tree(X[left_indices], y[left_indices], depth + 1)
        right = self._build_tree(X[right_indices], y[right_indices], depth + 1)
        return Node(feature, threshold, left, right)

    def fit(self, X, y):
        self.root = self._build_tree(X, y)

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

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

CART 决策树的时间复杂度主要取决于树的深度和特征数量。假设树的最大深度为d，特征数量为m，样本数量为n，则时间复杂度约为O(m * n * d)。空间复杂度则取决于树的节点数量，约为O(2^d)。

对于大规模数据集，可以采用以下优化策略：