决策树实战：深入解析CART算法构造流程与工程实现

1次阅读

没有评论

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

在机器学习实践中，决策树虽具有解释性强的优势，但常面临以下典型问题：

过拟合风险 ：当树深度不受控时，模型会记忆训练数据噪声，导致测试集性能骤降
特征重要性误判 ：默认的特征选择策略可能高估高基数特征（如用户 ID）的贡献度
数值稳定性问题 ：在类别不平衡场景下，信息增益计算可能产生数值下溢

CART(Classification and Regression Trees) 采用基尼系数（Gini Impurity）作为分裂标准，其定义为：

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

其中 $p_k$ 表示第 $k$ 类样本在数据集 $D$ 中的比例。对于特征 $A$ 将数据集划分为 $D_1$ 和 $D_2$ 后的基尼指数为：

$$
Gini_index(A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)
$$

算法	分裂标准	树类型	缺失值处理
ID3	信息增益	多叉树	不支持
C4.5	信息增益比	多叉树	加权分配
CART	基尼系数	二叉树	替代节点

class TreeNode:
    def __init__(self, feature_idx:int=None, threshold:float=None,
                 left=None, right=None, value=None):
        # 分裂特征索引（非叶节点）self.feature_idx = feature_idx  
        # 分裂阈值（连续特征）self.threshold = threshold 
        # 左右子树指针
        self.left = left  
        self.right = right
        # 叶节点的预测值
        self.value = value

def gini_impurity(y: np.ndarray) -> float:
    """计算基尼不纯度（时间复杂度 O(C)）"""
    if len(y) == 0:
        return 0
    p = np.bincount(y) / len(y)
    return 1 - np.sum(p ** 2)

当前节点样本数小于 min_samples_leaf
所有特征分裂增益小于 min_impurity_decrease
达到 max_depth 限制

预排序技术 ：对连续特征预先排序，加速最优分裂点查找
内存布局优化 ：使用 Fortran-contiguous 数组提高缓存命中率
并行化分裂 ：利用 joblib 实现特征级别的并行计算

特征离散化 ：对连续特征进行等频分箱，避免决策边界敏感
类别不平衡处理 ：
采用 class_weight=’balanced’ 参数
使用 SMOTE 过采样少数类
后剪枝验证 ：通过 ccp_alpha 参数进行代价复杂度剪枝

import matplotlib.pyplot as plt

def plot_feature_importance(model, feature_names):
    plt.barh(range(len(feature_names)), model.feature_importances_)
    plt.yticks(range(len(feature_names)), feature_names)
    plt.xlabel('Feature Importance')
    plt.show()