C4.5决策树算法头歌实战：从原理到Python实现

1次阅读

没有评论

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

决策树作为最直观的机器学习算法之一，因其模型可解释性强、接近人类决策过程的特点，成为分类问题中的入门首选工具。今天我们就用 Python 手把手实现经典改进版本——C4.5 算法。

C4.5 在 ID3 基础上做了两个关键改进：

用信息增益比替代信息增益，解决 ID3 对取值多属性的偏好问题
增加对连续特征的处理能力

信息增益比的计算分三步走：

先计算信息增益 $Gain(D,a)$
再计算属性 a 的固有值 $IV(a)$（类似熵的计算）
最后求比值 $Gain\_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}$

处理连续值时，需要先排序然后寻找最佳分割点：

def choose_best_split(feature_values):
    unique_vals = sorted(set(feature_values))
    split_points = [(unique_vals[i]+unique_vals[i+1])/2 
                   for i in range(len(unique_vals)-1)]
    # 计算每个分割点的信息增益比
    best_gain_ratio = 0
    for point in split_points:
        # 分割后计算信息增益比...
        current_ratio = calc_gain_ratio(...)
        if current_ratio > best_gain_ratio:
            best_point = point
    return best_point

def create_tree(dataset, features):
    # 终止条件 1：所有样本属于同一类别
    if len(set(dataset[-1])) == 1:
        return dataset[-1][0]

    # 终止条件 2：没有可用特征
    if not features:
        return majority_vote(dataset[-1])

    # 选择最佳划分特征
    best_feature = select_best_feature(dataset)
    tree = {best_feature: {}}

    # 递归构建子树
    for value in get_values(dataset, best_feature):
        sub_dataset = split_dataset(dataset, best_feature, value)
        tree[best_feature][value] = create_tree(sub_dataset, 
                                              features.remove(best_feature))
    return tree

import graphviz 

def visualize_tree(tree):
    dot = graphviz.Digraph()
    build_graph(dot, tree)
    return dot

# 递归构建图节点
def build_graph(dot, tree, parent_node=None, edge_label=None):
    if isinstance(tree, dict):
        for node, branches in tree.items():
            dot.node(str(id(node)), str(node))
            if parent_node:
                dot.edge(str(id(parent_node)), str(id(node)), label=edge_label)
            for value, subtree in branches.items():
                build_graph(dot, subtree, node, str(value))
    else:
        dot.node(str(id(tree)), str(tree), shape='box')
        if parent_node:
            dot.edge(str(id(parent_node)), str(id(tree)), label=edge_label)