CART决策树算法实战：从理论到CSDN最佳实践

1次阅读

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

在实际工程中应用 CART 决策树时，常遇到几个典型问题：

连续特征处理：与 ID3 只能处理离散特征不同，CART 需要高效找到连续值的最佳分割点。传统遍历法在特征维度高时计算代价大
模型解释性：虽然决策树本身具备可解释性，但过度复杂的树结构反而会降低业务说服力
过拟合风险：特别是在数据噪声较大时，容易生成深度过大的树
工程部署：需要平衡预测性能与模型体积，尤其在嵌入式设备场景

特性	ID3	C4.5	CART
分裂标准	信息增益	信息增益比	基尼系数 /MSE
特征类型	仅离散	离散 + 连续	离散 + 连续
缺失值处理	不支持	权重分配法	代理分裂
时间复杂度	O(mnlog(n))	O(mn²log(n))	O(mnlog(n))
输出类型	多分类	多分类	分类 / 回归

import numpy as np

def gini_impurity(y):
    """ 计算基尼不纯度（分类任务）时间复杂度：O(c)，c 为类别数
    """
    _, counts = np.unique(y, return_counts=True)
    p = counts / len(y)
    return 1 - np.sum(p**2)

class DecisionNode:
    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              # 叶节点预测值

def build_tree(X, y, depth=0, max_depth=5):
    # 终止条件 1：样本纯净或达到最大深度
    if len(np.unique(y)) == 1 or depth >= max_depth:
        return DecisionNode(value=np.mean(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 threshold in thresholds:
            left_idx = X[:, feature_idx] <= threshold
            gini = (len(y[left_idx]) * gini_impurity(y[left_idx]) + 
                    len(y[~left_idx]) * gini_impurity(y[~left_idx])) / len(y)

            if gini < best_gini:
                best_gini = gini
                best_feature = feature_idx
                best_thresh = threshold

    # 终止条件 2：无法继续降低不纯度
    if best_gini >= gini_impurity(y):
        return DecisionNode(value=np.mean(y))

    # 递归构建子树
    left_idx = X[:, best_feature] <= best_thresh
    left = build_tree(X[left_idx], y[left_idx], depth+1, max_depth)
    right = build_tree(X[~left_idx], y[~left_idx], depth+1, max_depth)

    return DecisionNode(feature_idx=best_feature, 
                        threshold=best_thresh,
                        left=left, right=right)

CCP（代价复杂度剪枝）：适合需要严格控制模型体积的场景，通过交叉验证选择 α 参数
REP（错误率降低剪枝）：计算简单但容易欠剪枝，适合快速原型开发
PEP（悲观剪枝）：不需要验证集，在小数据集上表现稳定

当特征之间存在高度相关性时，重要性评分会被分散
采用置换重要性 (permutation importance) 更可靠
对于 One-Hot 编码特征，需要合并同类特征的重要性

from sklearn.preprocessing import KBinsDiscretizer

# 等频分箱（解决数据倾斜问题）discretizer = KBinsDiscretizer(n_bins=10, 
                              encode='ordinal', 
                              strategy='quantile')
X_binned = discretizer.fit_transform(X_continuous)