C4.5决策树算法：从理论到Python实战指南

1次阅读

没有评论

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

决策树是一种模仿人类决策过程的树形结构模型。想象你要判断今天是否适合打网球，可能会先看天气（晴朗 / 多云 / 下雨），再考虑湿度高低——这就是决策树的思考方式。

在众多决策树算法中，ID3 和 C4.5 是最经典的两种：

ID3 算法 ：使用信息增益选择特征，但会偏向取值多的特征（比如把「身份证号」当作特征时会得到虚假的高信息增益）
C4.5 改进 ：引入信息增益比（信息增益 / 特征固有值），有效克服了取值数目带来的偏差

举个生活化的例子：选择餐厅时，如果用「菜品数量」作为评判标准（类似 ID3），可能会选到虽有 100 道菜但都难吃的餐厅；而用「好评率 / 菜品数量」（类似信息增益比）就能找到真正优质的餐厅。

计算过程就像做菜要分步骤：

计算数据集总熵（衡量混乱程度）
计算每个特征的条件熵
用公式：信息增益比 = (总熵 - 条件熵)/ 特征固有值

Python 实现片段：

def calc_info_gain_ratio(dataset, feature):
    base_entropy = calc_entropy(dataset)
    cond_entropy = calc_cond_entropy(dataset, feature)
    iv = -sum([(len(subset)/len(dataset))*math.log(len(subset)/len(dataset),2) 
               for subset in get_subsets(dataset, feature)])
    return (base_entropy - cond_entropy) / iv

C4.5 处理连续特征像给身高分段：

将连续值排序（如 150,155,160,…180cm）
取相邻值中点作为候选划分点（152.5,157.5,…）
选择使信息增益比最大的划分点

就像给盆栽修剪枝叶防止过度生长，C4.5 采用悲观剪枝：

计算节点误差率上限
如果剪枝后整体误差率不超过上限就剪枝
通过参数 confidence_factor 控制剪枝强度

处理连续值的技巧：

# 连续值离散化示例
def discretize_continuous(data, feature_idx):
    values = sorted([sample[feature_idx] for sample in data])
    split_points = [(values[i]+values[i+1])/2 for i in range(len(values)-1)]
    best_split = max(split_points, key=lambda x: calc_split_gain(data, feature_idx, x))
    return ['<='+str(best_split), '>'+str(best_split)]

用 Graphviz 展示决策树更直观：

from graphviz import Digraph

def visualize_tree(node, graph=None):
    if graph is None:
        graph = Digraph(format='png')
    graph.node(name=str(id(node)), label=node.label)
    for value, child in node.children.items():
        graph.edge(str(id(node)), str(id(child)), label=value)
        visualize_tree(child, graph)
    return graph

使用 sklearn 内置数据集演示完整流程：