C45决策树实战：从数据清洗到模型调优的全流程解决方案

1次阅读

没有评论

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

决策树算法在机器学习中扮演着重要角色，而 ID3 作为早期经典算法存在两个明显缺陷：

偏向多值特征：信息增益计算时，属性取值越多越容易被选中（如 ID 类特征）
无法处理连续值：只能处理离散型特征，现实数据中连续值普遍存在

C45 算法的核心改进在于引入 信息增益比（Gain Ratio）：

$$
GainRatio(D,A) = \frac{Gain(D,A)}{IV(A)}
$$

其中 $IV(A)$ 是特征 A 的固有值（Intrinsic Value）：

$$
IV(A) = -\sum_{v=1}^{V} \frac{|D_v|}{|D|} \log_2 \frac{|D_v|}{|D|}
$$

这个分母起到了归一化作用，有效缓解了 ID3 对多值特征的偏好问题。

对于连续特征，C45 采用二分法寻找最佳分割点：

def find_best_split(series, labels):
    unique_values = sorted(series.unique())
    best_gain = -1
    best_threshold = None

    for i in range(1, len(unique_values)):
        threshold = (unique_values[i-1] + unique_values[i])/2
        left_mask = series <= threshold
        current_gain = calc_gain_ratio(labels, left_mask)
        if current_gain > best_gain:
            best_gain = current_gain
            best_threshold = threshold

    return best_threshold, best_gain

class TreeNode:
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature  # 分裂特征
        self.threshold = threshold  # 分裂阈值(连续特征)
        self.left = left  # 左子树
        self.right = right  # 右子树
        self.value = value  # 叶节点预测值

def build_tree(X, y, depth=0, max_depth=5):
    # 终止条件：样本纯净或达到最大深度
    if len(np.unique(y)) == 1 or depth >= max_depth:
        return TreeNode(value=np.argmax(np.bincount(y)))

    # 寻找最佳分裂特征
    best_feature, best_threshold, best_gain = select_best_feature(X, y)

    # 预剪枝：增益小于阈值则停止
    if best_gain < 0.01:
        return TreeNode(value=np.argmax(np.bincount(y)))

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

    return TreeNode(feature=best_feature, threshold=best_threshold, 
                   left=left, right=right)

后剪枝 采用悲观剪枝（Pessimistic Pruning）：

def prune_tree(node, X_val, y_val):
    if node.value is not None:  # 叶节点无需剪枝
        return

    # 递归剪枝子树
    if node.left: prune_tree(node.left, X_val, y_val)
    if node.right: prune_tree(node.right, X_val, y_val)

    # 计算当前节点错误率
    original_error = calc_error_rate(node, X_val, y_val)

    # 计算如果合并为叶节点的错误率
    majority_class = get_majority_class(node, X_val, y_val)
    merged_error = np.sum(y_val != majority_class) / len(y_val)

    # 决定是否剪枝
    if merged_error <= original_error:
        node.left = node.right = None
        node.value = majority_class

方法	优点	缺点
直接删除	实现简单	可能损失重要信息
众数 / 均值填充	保留样本量	可能引入偏差
建立预测模型填充	最接近真实分布	计算成本高

CCP 参数 ：sklearn 的ccp_alpha 参数控制剪枝强度，建议从 0 开始网格搜索
深度限制：初始设置max_depth=5，根据验证集表现逐步调整
叶节点样本数 ：min_samples_leaf 建议设置在总样本量的 1%-5%

from sklearn.ensemble import RandomForestClassifier

# 基于 C45 决策树的随机森林
rf = RandomForestClassifier(
    criterion='entropy',  # 使用信息熵分裂
    max_features='sqrt',  # 特征采样
    n_estimators=200,
    ccp_alpha=0.01  # 成本复杂度剪枝
)

建树过程：$O(n\times m\times d)$，其中 n 是样本数，m 是特征数，d 是树深度
预测过程：$O(d)$，与特征数量无关

大数据优化建议：

使用近似算法选择分裂点
对连续特征进行分桶预处理
采用分布式实现如 Spark MLlib

对于取值特别多的类别特征（如用户 ID、邮编）：

目标编码：用目标变量均值编码类别
聚类降维：先对类别进行聚类合并
统计特征提取：计算各类别的统计量作为新特征

# 目标编码示例
from category_encoders import TargetEncoder

te = TargetEncoder()
X_train_encoded = te.fit_transform(X_train[['category']], y_train)
X_test_encoded = te.transform(X_test[['category']])