CART决策树算法深度解析：从数学原理到工程实践

1次阅读

没有评论

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

决策树是一种常见的机器学习方法，它通过树状结构对数据进行分类或回归。CART（Classification and Regression Trees）是其中最著名的算法之一，由 Breiman 等人于 1984 年提出。

CART 算法使用基尼系数 (Gini Index) 作为分裂标准，这与 ID3 和 C4.5 使用的信息增益 (Information Gain) 有所不同。

基尼系数：衡量数据集的不纯度，值越小表示纯度越高
```
Gini(D) = 1 - Σ(p_i)^2
```
其中 p_i 是第 i 类样本在数据集 D 中的比例
信息增益：基于信息熵的概念，表示特征对信息不确定性的减少程度
```
Gain(D,A) = Entropy(D) - Σ(|D_v|/|D|)*Entropy(D_v)
```

分裂标准
CART：基尼系数（分类）或最小二乘误差（回归）
ID3：信息增益
C4.5：信息增益比
输出类型
CART：可处理分类和回归问题
ID3/C4.5：仅处理分类问题
特征类型
CART：支持连续和离散特征
ID3：仅支持离散特征
C4.5：支持离散特征，可处理缺失值
树结构
CART：二叉树结构
ID3/C4.5：多叉树结构

以下是 CART 决策树的简化实现，包含特征选择、树构建和预测过程。

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

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.tree = 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 = None
        best_threshold = None

        for feature in range(X.shape[1]):
            thresholds = np.unique(X[:, feature])
            for threshold in thresholds:
                left_idx = X[:, feature] <= threshold
                right_idx = ~left_idx

                gini_left = self._gini(y[left_idx])
                gini_right = self._gini(y[right_idx])

                weighted_gini = (len(y[left_idx]) * gini_left + 
                                len(y[right_idx]) * gini_right) / len(y)

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

        return best_feature, best_threshold, best_gini

    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, threshold, gini = self._best_split(X, y)

        if gini == float('inf'):
            return TreeNode(value=np.argmax(np.bincount(y)))

        left_idx = X[:, feature] <= threshold
        right_idx = ~left_idx

        left_subtree = self._build_tree(X[left_idx], y[left_idx], depth+1)
        right_subtree = self._build_tree(X[right_idx], y[right_idx], depth+1)

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

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

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

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

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