决策树实战：深入解析CART算法原理与实现细节

1次阅读

没有评论

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

决策树作为经典的机器学习算法，在实际应用中常常遇到几个关键问题：

过拟合问题 ：当特征维度较高时，决策树容易生长得过深，导致在训练集上表现很好但在测试集上泛化性能差。
连续值处理 ：传统 ID3 算法只能处理离散特征，无法直接处理现实数据中常见的连续值特征。
性能平衡 ：模型的可解释性和预测性能往往需要权衡，过于简单的树可能欠拟合，复杂的树又难以解释。

这些痛点正是 CART 算法试图解决的问题。

特征选择标准 ：
ID3 使用信息增益（Information Gain）
C4.5 使用信息增益比（Gain Ratio）
CART 使用基尼系数（Gini Index）或均方误差（MSE）
树结构 ：
ID3/C4.5 生成的是多叉树
CART 生成的是二叉树
处理能力 ：
CART 可以直接处理连续值特征
CART 可以同时处理分类和回归任务

基尼系数的计算公式为：

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

其中 $p_k$ 是数据集中第 k 类样本所占的比例。

信息增益的计算基于信息熵：

$$ Ent(D) = -\sum_{k=1}^K p_k \log_2 p_k $$

两者都是衡量数据不纯度的指标，但基尼系数的计算不需要对数运算，效率更高。

分类树 ：
使用基尼系数作为分裂标准
叶子节点输出类别
回归树 ：
使用均方误差（MSE）作为分裂标准
叶子节点输出连续值

def gini_index(groups, classes):
    """
    计算基尼系数
    :param groups: 分割后的左右子集
    :param classes: 所有类别列表
    :return: 基尼系数
    """
    n_instances = float(sum(len(group) for group in groups))
    gini = 0.0
    for group in groups:
        size = float(len(group))
        if size == 0:
            continue
        score = 0.0
        for class_val in classes:
            p = [row[-1] for row in group].count(class_val) / size
            score += p * p
        gini += (1.0 - score) * (size / n_instances)
    return gini

def build_tree(node, max_depth, min_size, depth):
    """
    递归构建决策树
    :param node: 当前节点
    :param max_depth: 最大深度
    :param min_size: 最小样本数
    :param depth: 当前深度
    """left, right = node['groups']
    del(node['groups'])

    # 检查是否满足停止条件
    if not left or not right:
        node['left'] = node['right'] = to_terminal(left + right)
        return
    if depth >= max_depth:
        node['left'], node['right'] = to_terminal(left), to_terminal(right)
        return

    # 处理左子节点
    if len(left) <= min_size:
        node['left'] = to_terminal(left)
    else:
        node['left'] = get_split(left)
        build_tree(node['left'], max_depth, min_size, depth+1)

    # 处理右子节点
    if len(right) <= min_size:
        node['right'] = to_terminal(right)
    else:
        node['right'] = get_split(right)
        build_tree(node['right'], max_depth, min_size, depth+1)

def prune_tree(node, test_data):
    """
    后剪枝
    :param node: 当前节点
    :param test_data: 测试数据
    """
    if isinstance(node, dict):
        left_data = [row for row in test_data if row[node['index']] < node['value']]
        right_data = [row for row in test_data if row[node['index']] >= node['value']]

        prune_tree(node['left'], left_data)
        prune_tree(node['right'], right_data)

        if not isinstance(node['left'], dict) and not isinstance(node['right'], dict):
            left = [row[-1] for row in left_data]
            right = [row[-1] for row in right_data]

            # 尝试合并
            merged = left + right
            error_before = sum(1 for i in range(len(left)) if left[i] != node['left']) + \
                          sum(1 for i in range(len(right)) if right[i] != node['right'])
            error_after = sum(1 for i in range(len(merged)) if merged[i] != mode(merged))

            if error_after <= error_before:
                node['left'], node['right'] = None, None
                node['value'] = mode(merged)

max_depth：控制树的最大深度，防止过拟合
min_samples_split：节点分裂所需最小样本数
min_samples_leaf：叶节点所需最小样本数
max_features：寻找最佳分裂时考虑的特征数

使用 class_weight 参数调整类别权重
对少数类样本进行过采样
使用代价敏感学习

from sklearn.tree import export_graphviz
import graphviz

dot_data = export_graphviz(
    clf,
    out_file=None,
    feature_names=feature_names,
    class_names=target_names,
    filled=True,
    rounded=True,
    special_characters=True
)
graph = graphviz.Source(dot_data)
graph.render("decision_tree")

训练时间：O(n_features * n_samples * log(n_samples))
预测时间：O(depth)

基于特征被用于分裂节点时的信息增益总和
通过置换特征计算准确率下降程度

from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(
    n_estimators=100,
    max_depth=5,
    min_samples_split=2,
    random_state=42
)
rf.fit(X_train, y_train)