决策树C4.5算法详解及实现

C4.5决策树是一种广泛使用的机器学习算法，它用于分类任务。它是在ID3算法的基础上改进的，主要通过生成决策树来构建分类模型。C4.5通过以下步骤工作：

1. 数据集分裂

C4.5通过选择具有最高信息增益率的特征来分裂数据集。信息增益率（Gain Ratio）是在决策树构建过程中用于选择最优分裂特征的度量标准。它是基于信息增益进行的改进，旨在解决信息增益偏向于取值较多的属性的问题。具体实现信息增益率需要以下几个步骤：

1. 计算数据集的熵（Entropy）

熵用于衡量数据集的纯度或混乱度。假设数据集 $(S$) 中有 $(n$) 类，那么熵 $(Entropy(S)$) 的计算公式为：
$$Entropy(S)=-\sum _{i=1}^n{p}_i{\log }_2(p_i)$$
其中，$(p_i$) 是第 $(i$) 类在数据集$(S$) 中出现的概率。

熵越高，数据集的混乱度越高；熵越低，数据集越接近纯净。

2. 计算信息增益（Information Gain）

信息增益度量的是某个属性 $(A$) 在分裂数据集 $(S$) 后带来的熵的减少。计算步骤如下：

• 假设属性 $(A$) 有 $(v$) 个不同取值，将数据集 $(S$) 按照 $(A$) 的不同取值划分为 $(v$) 个子集$(S_1,S_2,...,S_v$)。

• 计算划分后数据集的条件熵：
  $$Entropy(S|A)=\sum _{j=1}^v\frac{|S_j|}{|S|}Entropy(S_j)$$
  其中，$(|S_j|$) 是子集 $(S_j$) 中样本的数量，$(|S|$) 是原始数据集的样本数量。

• 计算信息增益：
  $$Gain(S,A)=Entropy(S)-Entropy(S|A)$$
  信息增益表示属性 $(A$) 划分数据集后带来的熵的减少。信息增益越大，意味着通过该属性的划分能让数据集变得更加纯净。

3. 计算分裂信息（Split Information）

分裂信息衡量的是属性 $(A$) 划分数据集的固有不确定性。它的计算公式为：
$$SplitInfo(A)=-\sum _{j=1}^v\frac{|S_j|}{|S|}{\log }_2\left(\frac{|S_j|}{|S|}\right)$$
分裂信息越大，表示属性$(A$) 的取值越多，数据集的划分越细致。

4. 计算信息增益率（Gain Ratio）

信息增益率是在信息增益的基础上，除以分裂信息来防止属性值过多的偏倚。公式为：
$$GainRatio(A)=\frac{Gain(S,A)}{SplitInfo(A)}$$
信息增益率通过对信息增益进行归一化，避免选择取值较多的属性（如ID号、日期等）导致的偏倚。最终，在构建决策树时，选择信息增益率最高的属性作为最优分裂属性。

5. 选择最优特征

在所有候选特征中，计算每个特征的信息增益率，并选择具有最大信息增益率的特征进行数据集划分。

例子：

假设我们有一个小数据集 $(S$) ，包含水果分类问题，属性$(A$) 可能是水果的颜色，取值为红色、绿色、黄色等。在计算信息增益时，属性颜色可能划分出多个子集（红色的水果、绿色的水果等），然后通过计算该划分带来的熵减少量得到信息增益。最终，通过计算分裂信息，得到信息增益率。这个过程会在所有候选属性上执行，从而选择最佳分裂特征。

特点

1. 处理连续属性

C4.5可以处理连续属性。它通过计算属性的多个分裂点并找到能带来最大信息增益率的分裂点来处理数值型数据。例如，它可以把数值型属性转换为“< 某个阈值”和“>= 某个阈值”的二元划分。

2. 处理缺失值

C4.5能够处理数据集中存在缺失值的情况。它通过估算该特征对分类的贡献进行处理，而不是简单地删除缺失数据。

3. 剪枝（Pruning）

决策树的一个问题是容易过拟合。C4.5通过后剪枝方法来减少树的复杂性，从而提高泛化能力。剪枝通过在构建树后删除那些对分类贡献较小的分支来实现。

总结

C4.5通过使用信息增益率来选择最优的分裂特征，能够处理连续值和缺失值，并通过后剪枝来防止过拟合。这使得它比ID3更加灵活和实用，尤其在复杂的实际应用中。

全部代码

import numpy as np
from collections import Counter
from TreeDisp import visualize_tree

# 计算熵
def entropy(y):
    counts = np.bincount(y)
    probabilities = counts / len(y)
    return -np.sum([p * np.log2(p) for p in probabilities if p > 0])


# 根据特征值划分数据集
def split_dataset(X, y, feature_index, threshold):
    left_indices = X[:, feature_index] <= threshold
    right_indices = X[:, feature_index] > threshold
    return X[left_indices], X[right_indices], y[left_indices], y[right_indices]


# 计算信息增益
def information_gain(y, y_left, y_right):
    p_left = len(y_left) / len(y)
    p_right = len(y_right) / len(y)
    return entropy(y) - (p_left * entropy(y_left) + p_right * entropy(y_right))

#计算分裂信息
def Split_Information(y, y_left, y_right):
    p_left = len(y_left) / len(y)
    p_right = len(y_right) / len(y)
    return - (p_left * np.log2(p_left) + p_right * np.log2(p_right))

def Gain_Ratio(y, y_left, y_right):

    return information_gain(y, y_left, y_right)/Split_Information(y, y_left, y_right)

# 选择最佳分裂点
def best_split(X, y):
    best_gain_ratio = -1
    best_feature_index = 0
    best_threshold = 0
    n_features = X.shape[1]

    for feature_index in range(n_features):
        thresholds = np.unique(X[:, feature_index])
        for threshold in thresholds:
            X_left, X_right, y_left, y_right = split_dataset(X, y, feature_index, threshold)
            if len(y_left) == 0 or len(y_right) == 0:
                continue
            gain_ratio = Gain_Ratio(y, y_left, y_right)
            if gain_ratio > best_gain_ratio:
                best_gain_ratio = gain_ratio
                best_feature_index = feature_index
                best_threshold = threshold

    return best_feature_index, best_threshold


# 构建决策树节点
class Node:
    def __init__(self, feature_index=None, threshold=None, left=None, right=None, value=None):
        self.feature_index = feature_index  # 用于分裂的特征索引
        self.threshold = threshold  # 分裂点
        self.left = left  # 左子树
        self.right = right  # 右子树
        self.value = value  # 叶节点的值（类标签）


# 递归构建决策树
def build_tree(X, y, depth=0, max_depth=10):
    n_samples, n_features = X.shape
    n_labels = len(np.unique(y))

    # 停止条件：数据纯度高或达到最大深度
    if n_labels == 1 or depth == max_depth:
        leaf_value = Counter(y).most_common(1)[0][0]
        return Node(value=leaf_value)

    # 找到最佳分裂点
    feature_index, threshold = best_split(X, y)

    # 分裂数据集
    X_left, X_right, y_left, y_right = split_dataset(X, y, feature_index, threshold)

    # 构建左、右子树
    left_subtree = build_tree(X_left, y_left, depth + 1, max_depth)
    right_subtree = build_tree(X_right, y_right, depth + 1, max_depth)

    return Node(feature_index, threshold, left_subtree, right_subtree)


# 预测新样本
def predict(sample, tree):
    if tree.value is not None:
        return tree.value
    feature_value = sample[tree.feature_index]
    if feature_value <= tree.threshold:
        return predict(sample, tree.left)
    else:
        return predict(sample, tree.right)


# 使用决策树模型进行训练和预测
def decision_tree_classifier(X_train, y_train, X_test, max_depth=10):
    tree = build_tree(X_train, y_train, max_depth=max_depth)
    dot_tree = visualize_tree(tree, iris.feature_names)
    dot_tree.render('iris_tree_1', format='png', cleanup=True)  # 将图保存为 PNG 文件
    predictions = [predict(sample, tree) for sample in X_test]
    return np.array(predictions)


# 测试手动实现的决策树
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# 加载数据集
iris = load_iris()
X = iris.data
y = iris.target

# 划分训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# 使用手动实现的决策树进行训练和预测
y_pred = decision_tree_classifier(X_train, y_train, X_test, max_depth=5)

# 评估模型
accuracy = accuracy_score(y_test, y_pred)
print(f'Accuracy: {accuracy * 100:.2f}%')