决策树实战：如何用CART算法构建高精度分类模型

1次阅读

没有评论

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

传统 ID3 和 C4.5 算法在实际应用中存在两个主要问题：

连续值处理困难 ：ID3 只能处理离散特征，C4.5 虽能处理连续值但需要排序和多次分割计算，当特征维度较高时效率显著下降
特征选择偏差 ：ID3 采用信息增益（Information Gain）倾向于选择取值多的特征，C4.5 的信息增益比（Gain Ratio）虽然有所改进，但在某些情况下仍会出现不理想的分裂

与 ID3/C4.5 相比，CART（Classification and Regression Trees）具有以下特点：

二叉树结构 ：每个节点只产生两个分支，简化决策路径
基尼系数 /Gini Index：作为分裂标准，计算量比信息熵更小
通用性 ：既可处理分类任务（基尼系数），也可处理回归任务（最小二乘）

数学表达式：
$$Gini(D) = 1 – \sum_{k=1}^K (p_k)^2$$
其中 $p_k$ 是第 k 类样本在数据集 D 中的比例

对于数据集 D 和特征 A 的某个分割点，分裂后的基尼指数为：

def calc_gini(left_labels, right_labels):
    """计算分裂后的基尼指数"""
    n_left, n_right = len(left_labels), len(right_labels)
    n_total = n_left + n_right

    # 计算左右子集的基尼系数
    gini_left = 1 - sum((np.sum(left_labels == k)/n_left)**2 
                       for k in np.unique(left_labels))
    gini_right = 1 - sum((np.sum(right_labels == k)/n_right)**2 
                        for k in np.unique(right_labels))

    # 加权平均
    return (n_left/n_total)*gini_left + (n_right/n_total)*gini_right

采用二分法（Binary Split）处理连续特征：

对特征值进行排序
取相邻值的中间点作为候选分割点
选择使基尼指数最小的分割点

class TreeNode:
    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, max_depth, min_samples_split):
    # 终止条件检查
    if len(y) < min_samples_split or max_depth == 0:
        return TreeNode(value=np.argmax(np.bincount(y)))

    # 寻找最佳分裂
    best_gini = float('inf')
    for feature_idx in range(X.shape[1]):
        thresholds = np.unique(X[:, feature_idx])
        for threshold in thresholds:
            left_mask = X[:, feature_idx] <= threshold
            gini = calc_gini(y[left_mask], y[~left_mask])
            if gini < best_gini:
                best_gini = gini
                best_split = (feature_idx, threshold)

    # 递归构建子树
    feature_idx, threshold = best_split
    left_mask = X[:, feature_idx] <= threshold
    left = build_tree(X[left_mask], y[left_mask], max_depth-1, min_samples_split)
    right = build_tree(X[~left_mask], y[~left_mask], max_depth-1, min_samples_split)

    return TreeNode(feature_idx, threshold, left, right)