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

1次阅读

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

决策树是机器学习中最基础且直观的算法之一，它通过树状结构对数据进行分类或回归。CART（Classification and Regression Trees）算法由 Breiman 等人于 1984 年提出，是目前最常用的决策树算法之一，广泛应用于数据挖掘和机器学习领域。

CART 算法的特点包括：

可以处理分类和回归问题
使用基尼系数（Gini Index）作为特征选择的指标
生成二叉树结构
支持剪枝操作防止过拟合

基尼系数是 CART 算法用于分类问题的纯度衡量标准。对于一个包含 K 个类别的数据集 D，基尼系数计算公式为：

Gini(D) = 1 - Σ(p_k)^2，其中 p_k 是第 k 个类别在 D 中出现的概率。

CART 算法通过计算每个特征的基尼指数增益来选择最佳分裂特征。对于特征 A，将数据集 D 划分为 D1 和 D2 后的基尼指数增益为：

ΔGini(A) = Gini(D) - (|D1|/|D|)*Gini(D1) - (|D2|/|D|)*Gini(D2)

算法会选择使 ΔGini 最大的特征作为当前节点的分裂特征。

对于选定的特征，算法会寻找最佳分裂点将数据划分为两个子集。对于连续特征，通常通过排序后尝试所有可能的分割点；对于离散特征，则尝试所有可能的二分组合。

下面我们使用面向对象的方式实现 CART 决策树算法。完整代码包含以下主要部分：

import numpy as np
from collections import Counter

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  # 叶节点值

class CARTDecisionTree:
    """CART 决策树实现"""
    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 fit(self, X, y):
        """训练决策树"""
        self.root = self._build_tree(X, y)

    def _build_tree(self, X, y, depth=0):
        """递归构建决策树"""
        n_samples, n_features = X.shape
        n_classes = len(np.unique(y))

        # 停止条件
        if (self.max_depth is not None and depth >= self.max_depth) or \
           n_samples < self.min_samples_split or n_classes == 1:
            leaf_value = self._most_common_label(y)
            return TreeNode(value=leaf_value)

        # 寻找最佳分裂
        best_feature, best_threshold = self._best_split(X, y)

        # 如果无法找到有效分裂则返回叶节点
        if best_feature is None:
            return TreeNode(value=self._most_common_label(y))

        # 根据最佳分裂点划分数据
        left_idxs = X[:, best_feature] <= best_threshold
        right_idxs = ~left_idxs

        # 递归构建左右子树
        left = self._build_tree(X[left_idxs], y[left_idxs], depth+1)
        right = self._build_tree(X[right_idxs], y[right_idxs], depth+1)

        return TreeNode(best_feature, best_threshold, left, right)

    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_idxs = X[:, feature] <= threshold
                right_idxs = ~left_idxs

                if len(y[left_idxs]) == 0 or len(y[right_idxs]) == 0:
                    continue

                # 计算基尼指数
                gini = self._gini_index(y[left_idxs], y[right_idxs])

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

        return best_feature, best_threshold

    def _gini_index(self, y_left, y_right):
        """计算基尼指数"""
        n = len(y_left) + len(y_right)
        p_left = len(y_left) / n
        p_right = len(y_right) / n

        return p_left * self._gini(y_left) + p_right * self._gini(y_right)

    def _gini(self, y):
        """计算基尼系数"""
        counts = Counter(y)
        gini = 1
        for label in counts:
            prob = counts[label] / len(y)
            gini -= prob ** 2
        return gini

    def _most_common_label(self, y):
        """返回出现次数最多的类别"""
        counts = Counter(y)
        return counts.most_common(1)[0][0]

    def predict(self, X):
        """预测"""
        return np.array([self._traverse_tree(x, self.root) for x in X])

    def _traverse_tree(self, x, node):
        """遍历决策树进行预测"""
        if node.value is not None:
            return node.value

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

预剪枝是在决策树生成过程中提前停止树的构建，常用策略包括：