C4.5树之信息增益率

import numpy as np

def entropy(labels):
    """计算熵"""
    _, counts = np.unique(labels, return_counts=True)
    probabilities = counts / len(labels)
    return -np.sum(probabilities * np.log2(probabilities))

def conditional_entropy(feature, labels):
    """计算条件熵"""
    unique_values = np.unique(feature)
    total = len(labels)
    cond_ent = 0
    for value in unique_values:
        subset = labels[feature == value]
        weight = len(subset) / total
        cond_ent += weight * entropy(subset)
    return cond_ent

def information_gain(feature, labels):
    """计算信息增益"""
    return entropy(labels) - conditional_entropy(feature, labels)

def feature_entropy(feature):
    """计算特征熵（把特征列当做标签）"""
    return entropy(feature)

def information_gain_ratio(feature, labels):
    """计算信息增益率"""
    ig = information_gain(feature, labels)
    fe = feature_entropy(feature)
    return ig / fe if fe > 0 else 0

# 1. 模拟ID3偏向多值特征的问题
print("=== ID3偏向多值特征的问题 ===")
labels = np.array(['A', 'A', 'B', 'B', 'A', 'B'])

# 特征B：取值多（6个不同值）
feature_many = np.array(['a', 'b', 'c', 'd', 'e', 'f'])
# 特征A：取值少（2个不同值）
feature_few = np.array(['x', 'x', 'x', 'y', 'y', 'y'])

ig_many = information_gain(feature_many, labels)
ig_few = information_gain(feature_few, labels)

print(f"多值特征 - 信息增益: {ig_many:.4f}")
print(f"少值特征 - 信息增益: {ig_few:.4f}")
print(f"ID3会选择: 多值特征（信息增益大）")

# 2. C4.5的解决方案
print("\n=== C4.5的解决方案 ===")
fe_many = feature_entropy(feature_many)
fe_few = feature_entropy(feature_few)

igr_many = information_gain_ratio(feature_many, labels)
igr_few = information_gain_ratio(feature_few, labels)

print(f"多值特征 - 特征熵: {fe_many:.4f}, 信息增益率: {igr_many:.4f}")
print(f"少值特征 - 特征熵: {fe_few:.4f}, 信息增益率: {igr_few:.4f}")
print(f"C4.5会选择: 信息增益率大的特征")

# 3. 惩罚系数分析
print("\n=== 惩罚系数分析 ===")
penalty_many = 1 / fe_many if fe_many > 0 else 0
penalty_few = 1 / fe_few if fe_few > 0 else 0

print(f"多值特征 - 特征熵: {fe_many:.4f}, 惩罚系数: {penalty_many:.4f}")
print(f"少值特征 - 特征熵: {fe_few:.4f}, 惩罚系数: {penalty_few:.4f}")
print("特征熵越大 → 惩罚系数越小")

# 4. 完整计算示例
print("\n=== 完整计算示例 ===")
# 6个样本，3个A，3个B
labels = np.array(['A', 'A', 'A', 'B', 'B', 'B'])
# 特征：4个alpha，2个beta
feature = np.array(['alpha', 'alpha', 'alpha', 'alpha', 'beta', 'beta'])

print(f"数据: labels={labels}")
print(f"特征: feature={feature}")

ent = entropy(labels)
cond_ent = conditional_entropy(feature, labels)
ig = information_gain(feature, labels)
fe = feature_entropy(feature)
igr = information_gain_ratio(feature, labels)

print(f"\n1. 熵 H(D): {ent:.4f}")
print(f"2. 条件熵 H(D|A): {cond_ent:.4f}")
print(f"3. 信息增益 g(D,A): {ig:.4f}")
print(f"4. 特征熵 H_A(D): {fe:.4f}")
print(f"5. 信息增益率 g_R(D,A): {igr:.4f}")
print(f"6. 惩罚系数: {1/fe:.4f}")