深入解析CART决策树的计算步骤：从数学原理到Python实现

1次阅读

没有评论

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

在构建决策树时，我们需要一个指标来衡量数据的不纯度（Impurity）。最常用的两个指标是基尼系数（Gini Index）和熵（Entropy）。

基尼系数公式 ：
```
Gini(p) = 1 - Σ(p_i)^2
```
其中 p_i 是第 i 类样本的比例。基尼系数计算的是随机抽取两个样本，它们类别不一致的概率。
熵的公式 ：
```
Entropy(p) = -Σp_i * log2(p_i)
```
熵衡量的是系统的不确定性，值越大表示混乱程度越高。
关键区别 ：
计算效率：基尼系数不涉及对数运算，计算速度更快
结果差异：两者在大多数情况下选择的分裂点相似，但熵对不纯度变化更敏感
实际应用：sklearn 默认使用基尼系数，因其计算开销更小

决策树的核心是递归地选择最优特征和分裂点。对于每个特征，我们需要：

对连续特征：
排序所有可能的分割点
计算每个分割点的基尼指数增益
选择增益最大的分割点
对分类特征：
考虑所有可能的子集划分
计算每种划分的基尼指数
选择最优划分方式

基尼增益计算公式 ：

ΔGini = Gini(D) - (|D_left|/|D|)*Gini(D_left) - (|D_right|/|D|)*Gini(D_right)

以下是使用 numpy 实现的 CART 决策树核心代码：

import numpy as np

class Node:
    def __init__(self, feature_idx=None, threshold=None, left=None, right=None, value=None):
        self.feature_idx = feature_idx  # 分裂特征索引
        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

    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_thresh = None, None

        for feature_idx in range(X.shape[1]):
            thresholds = np.unique(X[:, feature_idx])
            for thresh in thresholds:
                left_idx = X[:, feature_idx] <= thresh
                gini = self._gini(y[left_idx]) * np.sum(left_idx)/len(y) + \
                       self._gini(y[~left_idx]) * np.sum(~left_idx)/len(y)
                if gini < best_gini:
                    best_gini = gini
                    best_feature = feature_idx
                    best_thresh = thresh
        return best_feature, best_thresh

    def fit(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, thresh = self._best_split(X, y)
        left_idx = X[:, feature] <= thresh
        node = Node(feature_idx=feature, threshold=thresh,
                   left=self.fit(X[left_idx], y[left_idx], depth+1),
                   right=self.fit(X[~left_idx], y[~left_idx], depth+1))
        return node

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

# 加载数据
iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

# 训练模型
tree = DecisionTree(max_depth=3)
root = tree.fit(X_train, y_train)

# 预测函数（需自行实现）def predict(node, x):
    if node.value is not None:
        return node.value
    if x[node.feature_idx] <= node.threshold:
        return predict(node.left, x)
    else:
        return predict(node.right, x)