深入解析CART决策树与随机森林的数学描述：从理论到工程实践

1次阅读

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

CART 决策树以其直观的可解释性和高效的计算性能，成为工业界处理结构化数据的首选工具。随机森林通过集成学习显著提升模型泛化能力，在金融风控和推荐系统等场景表现卓越。两者的组合既能应对复杂非线性关系，又能保持对高维数据的处理效率。

基尼系数定义为：
$$Gini(p) = \sum_{k=1}^K p_k(1-p_k) = 1-\sum_{k=1}^K p_k^2$$
信息熵的数学表达为：
$$H(X) = -\sum_{i=1}^n p(x_i)\log p(x_i)$$

适用场景对比：
– 基尼系数计算效率更高（无对数运算）
– 熵对不纯度更敏感，适合特征取值较分散的场景
– 实际差异通常 <2%，sklearn 默认使用基尼系数

设当前节点样本集合为 $D$，分裂后左右子节点为 $D_L,D_R$，通过拉格朗日乘数法求解最优分裂点：
$$\mathcal{L}(s) = Gini(D) – \frac{|D_L|}{|D|}Gini(D_L) – \frac{|D_R|}{|D|}Gini(D_R) + \lambda(\sum p_k-1)$$
求导可得最优分裂阈值应满足：
$$\frac{\partial \mathcal{L}}{\partial s} = 0$$

给定训练集 $X$，Bootstrap 采样生成 $B$ 个子集：
$$\hat{X}b = {x$$
最终预测结果为：
$$\hat{f}(x) = \frac{1}{B}\sum_{b=1}^B f_b(x)$$},…,x_{bn}}, x_{bi} \sim X \text{with replacement

class TreeNode:
    def __init__(self, gini, n_samples):
        self.gini = gini
        self.n_samples = n_samples
        self.feature_idx = None
        self.threshold = None
        self.children = {}

class DecisionTree:
    def _gini(self, y):
        _, counts = np.unique(y, return_counts=True)
        return 1 - np.sum((counts/len(y))**2)

    def _best_split(self, X, y):
        best_gini = float('inf')
        for feat_idx in range(X.shape[1]):
            thresholds = np.unique(X[:, feat_idx])
            for thresh in thresholds:
                left_idx = X[:, feat_idx] <= thresh
                gini = self._gini(y[left_idx])*left_idx.sum()/len(y) + \
                       self._gini(y[~left_idx])*(~left_idx).sum()/len(y)
                if gini < best_gini:
                    best_gini = gini
                    best_feat = feat_idx
                    best_thresh = thresh
        return best_feat, best_thresh

class RandomForest:
    def __init__(self, n_trees=100, max_depth=10):
        self.n_trees = n_trees
        self.max_depth = max_depth

    def _bootstrap(self, X, y):
        idx = np.random.choice(len(X), size=len(X), replace=True)
        return X[idx], y[idx], set(range(len(X))) - set(idx)

    def fit(self, X, y):
        self.trees = []
        self.oob_scores = []
        for _ in range(self.n_trees):
            X_sample, y_sample, oob_idx = self._bootstrap(X, y)
            tree = DecisionTree(max_depth=self.max_depth)
            tree.fit(X_sample, y_sample)
            self.trees.append(tree)

            if oob_idx:
                oob_pred = tree.predict(X[list(oob_idx)])
                self.oob_scores.append(accuracy_score(y[list(oob_idx)], oob_pred))

使用 Cython 加速关键循环
预排序特征值加速分裂点搜索
并行化特征选择与树构建

使用稀疏矩阵存储 (csc_matrix)
特征分块加载与计算
增量式特征重要性评估

from skopt import BayesSearchCV

params = {'n_estimators': (100, 500),
    'max_depth': (3, 15),
    'min_samples_split': (2, 10)
}

opt = BayesSearchCV(RandomForest(),
    params,
    n_iter=30,
    cv=5
)
opt.fit(X_train, y_train)