Python实现C4.5算法

基础：

1. 不同的决策树算法有着不同的特征选择方案。ID3用信息增益，C4.5用信息增益率，CART用gini系数。
2. 能够处理连续型属性数据，不需要对连续型属性进行离散化处理。
3. 基本思想是将数据集递归地划分为小的子集，直到子集中样本的所有特征属性均相同或无法继续划分为止。
4. C4.5算法并不直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
5. 选取分裂节点，对于连续性属性，它的分裂节点是任意相邻两个取值的中点，最后得到所有分裂点的信息熵，选择信息熵最小，即信息增益最大 的作为分裂点。注意：这里用信息增益最大而不是信息增益率最大。

具体步骤：

1. 选择当前节点的最优划分属性，即使得信息增益率最大的属性，如果不存在则该节点为叶子节点。
2. 对选择的最优属性的每个取值，分别构建一个子节点，并将样本点分配到这些子节点中。
3. 对每个子节点，递归地执行步骤1-2，直至满足终止条件，即到达叶子节点或无法继续划分。
4. 构建好决策树，用它进行测试数据的分类预测。

计算：

• 信息增益率：增益率是用前面的信息增益Gain(D, a)和属性a对应的"固有值"(intrinsic value)的比值来共同定义的。属性 a 的可能取值数目越多(即 V 越大)，则 IV(a) 的值通常会越大。
  -

实例代码：

import pandas as pd
import numpy as np
from math import log2
 
# 读入数据集
data = {
   'have_house': ['yes', 'no', 'no', 'yes', 'no', 'no', 'yes', 'no', 'no', 'no'],
        'marital_status': ['single', 'married', 'single', 'married', 'divorced', 'married', 'divorced', 'single', 'married', 'single'],
        'annual_income': [125, 100, 70, 120, 95, 60, 220, 85, 75, 90],
        'late_payment': ['no', 'no', 'no', 'no', 'yes', 'no', 'no', 'yes', 'no', 'yes']}
df = pd.DataFrame(data)
 
# 将文本属性转为数值属性
df['have_house'] = df['have_house'].apply(lambda x: 1 if x == 'yes' else 0)            # 如果有房产，转换为1，否则转换为0
df['marital_status'] = df['marital_status'].map({
   'single': 0, 'married': 1, 'divorced': 2})  # 将婚姻状况转换为0-2的数字，表示单身、已婚和离异
df['late_payment'] = df['late_payment'].apply(lambda x: 1 if x == 'yes' else 0)       # 如果拖欠贷款，转换为1，否则转换为0
 
# 定义C4.5算法所需的函数
def calc_entropy(data):
    """计算信息熵"""
    counts = data.value_counts()  # 统计各类别样本的数量
    probs = counts / len(data)    # 计算各类别样本的概率
    entropy = -sum(probs * np.log2(probs))  # 根据公式计算信息熵
    return entropy
 
def calc_conditional_entropy(data, feature, threshold):
    """计算条件熵"""
    low_subset = data[data[feature] < threshold]['late_payment']  # 获取年收入小于阈值的目标变量列
    high_subset = data[data[feature] >= threshold]['late_payment']  # 获取年收入大于等于阈值的目标变量列
    prob_low = len(low_subset) / len(data)   # 计算前一部分的出现概率
    prob_high = len(high_subset) / len(data)  # 计算后一部分的出现概率
    entropy = prob_low * calc_entropy(low_subset) + prob_high * calc_entropy(high_subset)  # 计算条件熵
    return entropy
 
def calc_information_gain(data, feature):
    """计算信息增益"""
    base_entropy = calc_entropy(data['late_payment'])                # 计算全局信息熵
    sorted_values = sorted(data[feature].unique())                   # 对连续属性的取值进行排序
    thresholds = [(sorted_values[i] + sorted_values[i+1]) / 2 for i in range(len(sorted_values)-1)]  # 计算各个分割点的阈值
    info_gains = []
    for threshold in thresholds:
        cond_entropy = calc_conditional_entropy(data, feature, threshold)
        info_gain = base_entropy - cond_entropy
        info_gains.append(info_gain)
    best_threshold_index = 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45