决策树实战：CART算法构建流程详解与性能优化指南

1次阅读

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

在风控评分、医疗诊断等业务场景中，决策树因其 玻璃盒模型 特性广受青睐：

分类规则可直观呈现为 if-then 逻辑链
特征重要性可通过节点分裂顺序量化
无需数据标准化处理

但传统 ID3 算法存在明显短板：

仅支持离散特征，需手动分箱处理年龄、收入等连续变量
采用信息增益偏向多值特征，易生成过宽浅的树
缺乏剪枝机制，在噪声数据上表现不稳定

维度	ID3	C4.5	CART
特征选择标准	信息增益	信息增益比	基尼系数 / 均方误差
树结构	多叉树	多叉树	二叉树
连续值处理	不支持	自动离散化	最优切分点
计算复杂度	O(n·log(n))	O(n²)	O(n·log(n))
过拟合控制	无	悲观剪枝	代价复杂度剪枝

定义数据集 $D$ 的基尼指数：

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

其中 $C_k$ 是第 $k$ 类样本子集。几何意义可理解为：从数据集随机抽取两个样本，其类别不一致的概率。当所有样本同属一类时，基尼指数为 0（完全纯净）。

对特征 $A$ 的候选划分点 $a$，计算分裂后的加权基尼指数：

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

其中 $D_1$ 和 $D_2$ 是根据特征 $A$ 是否满足条件 $a$ 划分的子集。遍历所有可能的分裂点，选择使 $Gini_split$ 最小的特征和切分点。

实际编码时需要设置停止条件：

当前节点样本数小于 min_samples_split
所有特征已用完或基尼指数低于 min_impurity_decrease
树深度达到 max_depth

采用后序遍历递归构建二叉树，每个节点存储：

分裂特征和阈值
左右子节点指针
当前节点的预测类别（叶节点有效）

import numpy as np

def gini_impurity(y):
    _, counts = np.unique(y, return_counts=True)
    probabilities = counts / len(y)
    return 1 - np.sum(probabilities ** 2)

# 示例：计算二分类数据的基尼指数
y = np.array([0, 1, 1, 0, 1])
print(f'Gini: {gini_impurity(y):.4f}')  # 输出 0.48

def find_best_split(X, 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 thresh in thresholds:
            left_mask = X[:, feature_idx] <= thresh
            gini_left = gini_impurity(y[left_mask])
            gini_right = gini_impurity(y[~left_mask])
            weighted_gini = (np.sum(left_mask) * gini_left + 
                            np.sum(~left_mask) * gini_right) / len(y)

            if weighted_gini < best_gini:
                best_gini = weighted_gini
                best_feature = feature_idx
                best_thresh = thresh

    return best_feature, best_thresh

from graphviz import Digraph

def plot_tree(tree, feature_names):
    dot = Digraph()

    def add_nodes(node, parent=None, edge_label=''):
        node_id = str(id(node))
        if node.is_leaf:
            dot.node(node_id, f'class={node.pred_class}')
        else:
            dot.node(node_id, 
                    f'{feature_names[node.feature_idx]} <= {node.threshold:.2f}')
            add_nodes(node.left, node_id, 'Yes')
            add_nodes(node.right, node_id, 'No')
        if parent:
            dot.edge(parent, node_id, label=edge_label)

    add_nodes(tree)
    return dot

等频分桶：保证每个区间样本量相近，适合长尾分布
基于聚类分桶：用 K -Means 自动寻找密集区间
动态调整阈值：在分裂点附近±5% 范围微调，避免硬截断

from sklearn.tree import DecisionTreeClassifier

params = {'max_depth': [3, 5, 7],  # 限制树深度
    'min_samples_split': [10, 30],  # 节点最小样本数
    'min_impurity_decrease': [0.001, 0.01],  # 分裂最小增益
    'ccp_alpha': [0, 0.01]  # 代价复杂度参数
}

grid_search = GridSearchCV(DecisionTreeClassifier(), param_grid=params, cv=5)
grid_search.fit(X_train, y_train)