深入解析CART决策树与随机森林的数学原理及实现

1次阅读

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

决策树和随机森林是机器学习中非常经典且实用的算法，广泛应用于分类和回归问题。决策树通过树状结构对数据进行划分，每个内部节点表示一个特征判断，每个分支代表一个判断结果，而叶子节点则对应最终的决策结果。随机森林则通过集成多棵决策树，利用投票或平均的方式提升模型的泛化能力和鲁棒性。

这两种算法在金融风控、医疗诊断、推荐系统等领域都有广泛应用，因其易于理解和解释而备受青睐。

CART（Classification and Regression Trees）是一种二叉决策树算法，其核心在于如何选择最优的特征和分裂点。常用的分裂准则包括基尼系数（Gini Index）和信息增益（Information Gain）。

基尼系数用于衡量数据的不纯度，定义为：

$$
Gini(D) = 1 – \sum_{k=1}^{K} p_k^2
$$

其中，(D)是数据集，(K)是类别数，(p_k)是第 (k) 类样本在 (D) 中的比例。对于某个特征 (A) 和分裂点 (s)，将数据集分为(D_1) 和(D_2)，基尼系数的减少量为：

$$
\Delta Gini(A, s) = Gini(D) – \frac{|D_1|}{|D|} Gini(D_1) – \frac{|D_2|}{|D|} Gini(D_2)
$$

选择使 (\Delta Gini) 最大的特征和分裂点作为最优分裂。

信息增益基于信息熵，信息熵定义为：

$$
H(D) = -\sum_{k=1}^{K} p_k \log_2 p_k
$$

信息增益的计算公式为：

$$
Gain(A, s) = H(D) – \frac{|D_1|}{|D|} H(D_1) – \frac{|D_2|}{|D|} H(D_2)
$$

同样，选择使信息增益最大的特征和分裂点作为最优分裂。

随机森林通过集成多棵决策树来提升模型的性能。其核心思想包括：

Bagging（Bootstrap Aggregating）：每棵树在训练时使用不同的自助采样（Bootstrap Sample）数据集，增加模型的多样性。
随机特征选择：在每棵树的分裂过程中，随机选择部分特征进行分裂，进一步降低模型的方差。

最终，分类问题通过投票决定结果，回归问题通过平均预测值得到最终输出。

以下是一个简化的 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 = ~left_indices
                gini_left = self._gini(y[left_indices])
                gini_right = self._gini(y[right_indices])
                gini = (np.sum(left_indices) * gini_left + np.sum(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 = ~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 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)

以下是一个简化的随机森林实现：

from sklearn.utils import resample

class RandomForest:
    def __init__(self, n_trees=100, max_depth=None, max_features=None):
        self.n_trees = n_trees
        self.max_depth = max_depth
        self.max_features = max_features
        self.trees = []

    def fit(self, X, y):
        for _ in range(self.n_trees):
            X_sample, y_sample = resample(X, y)
            tree = DecisionTree(max_depth=self.max_depth)
            tree.fit(X_sample, y_sample)
            self.trees.append(tree)

    def predict(self, X):
        predictions = np.array([tree.predict(X) for tree in self.trees])
        return np.array([np.argmax(np.bincount(predictions[:, i])) for i in range(X.shape[0])])