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

1次阅读

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

决策树是机器学习中最基础且直观的算法之一，而 CART（Classification and Regression Trees）算法则是其中最经典的实现方式。它不仅能处理分类问题（通过基尼系数），还能解决回归问题（通过方差最小化）。与 ID3、C4.5 等算法相比，CART 的特点是：

严格生成二叉树结构
同时支持分类和回归任务
默认使用基尼不纯度作为分类标准

基尼系数衡量数据的不纯度，值越小表示纯度越高。计算公式为：

Gini = 1 - Σ(p_i)^2

其中 p_i 是第 i 类样本在节点中的比例。计算示例：

假设一个节点有 10 个样本，类别 A 有 6 个，类别 B 有 4 个
Gini = 1 – (6/10)^2 – (4/10)^2 = 0.48

CART 采用贪婪算法选择最佳分割特征和分割点：

遍历所有特征
对每个特征，遍历所有可能的分割点
计算分割后的加权基尼系数
选择使基尼系数下降最多的特征和分割点

分裂过程递归进行，直到满足停止条件：

当前节点样本数小于阈值
基尼系数低于阈值
达到最大树深度

以下是完整的 CART 决策树实现：

import numpy as np

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

class CARTDecisionTree:
    def __init__(self, max_depth=None, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.root = None

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

    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_indices = X[:, feature_idx] <= thresh
                right_indices = ~left_indices

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

                gini_left = self._gini(y[left_indices])
                gini_right = self._gini(y[right_indices])
                weighted_gini = (len(y[left_indices]) * gini_left + 
                                len(y[right_indices]) * gini_right) / len(y)

                if weighted_gini < best_gini:
                    best_gini = weighted_gini
                    best_feature = feature_idx
                    best_thresh = thresh

        return best_feature, best_thresh

    def _build_tree(self, X, y, depth=0):
        if (self.max_depth is not None and depth >= self.max_depth) or \
           len(y) < self.min_samples_split or len(np.unique(y)) == 1:
            return TreeNode(value=np.argmax(np.bincount(y)))

        feature_idx, threshold = self._best_split(X, y)
        if feature_idx is None:
            return TreeNode(value=np.argmax(np.bincount(y)))

        left_indices = X[:, feature_idx] <= threshold
        right_indices = ~left_indices

        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 TreeNode(feature_idx, threshold, left=left, right=right)

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

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

    def _predict_tree(self, x, node):
        if node.value is not None:
            return node.value

        if x[node.feature_idx] <= node.threshold:
            return self._predict_tree(x, node.left)
        else:
            return self._predict_tree(x, node.right)

在树构建过程中提前停止生长：