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

1次阅读

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

决策树是机器学习中最直观且易于理解的算法之一，而 C4.5 作为 ID3 算法的改进版本，在实际应用中表现更为出色。本文将从原理到代码实现，带你一步步构建 C4.5 决策树，并分享一些实战中的小技巧。

C4.5 算法是 Ross Quinlan 在 ID3 算法基础上提出的改进版本，主要解决了 ID3 算法的一些局限性。它的核心思想是通过递归地选择最优特征来划分数据集，直到满足停止条件。

与 ID3 使用信息增益不同，C4.5 使用信息增益比来选择划分特征。这解决了 ID3 倾向于选择取值较多的特征的问题。

计算公式：

 信息增益比 = 信息增益 / 特征固有值

其中特征固有值是特征取值的熵，衡量了特征取值的分散程度。

C4.5 可以处理连续值特征，这是它相对于 ID3 的一个重要改进。处理方法是：

对连续特征值进行排序
计算每两个相邻值的中间点作为候选划分点
选择信息增益比最大的划分点

C4.5 还能处理缺失值，它会根据已知值的比例来分配样本权重。

特征选择标准：ID3 使用信息增益，C4.5 使用信息增益比
特征类型：ID3 只能处理离散值，C4.5 可以处理连续值
缺失值：ID3 不能处理缺失值，C4.5 可以
剪枝：ID3 没有剪枝，C4.5 有后剪枝
多叉树：ID3 是多叉树，C4.5 可以是二叉树

下面我们来实现一个简化版的 C4.5 决策树。为了清晰起见，我们省略了一些细节处理（如缺失值处理），重点展示核心逻辑。

import numpy as np
import pandas as pd
from math import log

# 计算数据集的经验熵
def calc_entropy(dataset):
    n = len(dataset)
    label_counts = {}
    for data in dataset:
        label = data[-1]
        label_counts[label] = label_counts.get(label, 0) + 1
    entropy = 0.0
    for key in label_counts:
        prob = float(label_counts[key]) / n
        entropy -= prob * log(prob, 2)
    return entropy

# 划分数据集
def split_dataset(dataset, axis, value):
    sub_dataset = []
    for data in dataset:
        if data[axis] == value:
            reduced_data = data[:axis]
            reduced_data.extend(data[axis+1:])
            sub_dataset.append(reduced_data)
    return sub_dataset

# 计算信息增益比
def calc_info_gain_ratio(dataset, base_entropy, axis):
    feature_values = [data[axis] for data in dataset]
    unique_values = set(feature_values)
    new_entropy = 0.0
    iv = 0.0  # 特征固有值
    for value in unique_values:
        sub_dataset = split_dataset(dataset, axis, value)
        prob = len(sub_dataset) / float(len(dataset))
        new_entropy += prob * calc_entropy(sub_dataset)
        iv -= prob * log(prob, 2)
    info_gain = base_entropy - new_entropy
    if iv == 0:  # 避免除以 0
        return 0
    return info_gain / iv

# 选择最佳划分特征
def choose_best_feature(dataset):
    num_features = len(dataset[0]) - 1
    base_entropy = calc_entropy(dataset)
    best_info_gain_ratio = 0.0
    best_feature = -1
    for i in range(num_features):
        info_gain_ratio = calc_info_gain_ratio(dataset, base_entropy, i)
        if info_gain_ratio > best_info_gain_ratio:
            best_info_gain_ratio = info_gain_ratio
            best_feature = i
    return best_feature

# 构建决策树
def create_tree(dataset, labels):
    class_list = [data[-1] for data in dataset]
    # 如果所有类别相同，停止划分
    if class_list.count(class_list[0]) == len(class_list):
        return class_list[0]
    # 如果没有特征可划分，返回出现次数最多的类别
    if len(dataset[0]) == 1:
        return majority_cnt(class_list)

    best_feat = choose_best_feature(dataset)
    best_feat_label = labels[best_feat]
    my_tree = {best_feat_label: {}}
    del(labels[best_feat])
    feat_values = [data[best_feat] for data in dataset]
    unique_values = set(feat_values)

    for value in unique_values:
        sub_labels = labels[:]
        my_tree[best_feat_label][value] = create_tree(split_dataset(dataset, best_feat, value), sub_labels)
    return my_tree

C4.5 通过剪枝来防止过拟合。主要有两种剪枝方法：