解题思路

  1. 计算整个数据集的信息熵
  2. 对每个特征：
    • 计算条件熵（按特征取值划分子集）
    • 计算特征固有值（属性熵）
    • 计算信息增益比
  3. 选择信息增益比最大的特征

代码解析

import sys
from math import log

def calcInfoEnt(data):
    """计算数据集的信息熵"""
    numEntres = len(data)
    labelcnt = {}  # 统计各类标签数量
    for item in data:
        label = item[-1]  # 最后一列为标签
        labelcnt[label] = labelcnt.get(label, 0) + 1
    
    infoEnt = 0.0
    for count in labelcnt.values():
        prob = count / numEntres  # 计算概率
        infoEnt -= prob * log(prob, 2)  # 累加熵值
    return infoEnt

def create_sub_dataset(dataSet, i, value):
    """根据特征值划分子集（移除当前特征列）"""
    res = []
    for item in dataSet:
        if item[i] == value:
            # 拼接特征i前后的列
            curr_data = item[:i] + item[i+1:]
            res.append(curr_data)
    return res

def calc_max_info_gain_ratio(dataSet):
    """计算信息增益比最大的特征"""
    n = len(dataSet[0]) - 1  # 特征数（最后一列为标签）
    total_entropy = calcInfoEnt(dataSet)  # 总信息熵
    best_feature = 0  # 最佳特征索引
    best_gain_ratio = 0.0  # 最佳信息增益比
    
    for i in range(n):  # 遍历每个特征
        # 获取特征i的所有取值
        unique_val = set(item[i] for item in dataSet)
        
        cur_info_ent = 0.0  # 条件熵
        info_V = 0.0  # 属性熵（特征固有值）
        
        for val in unique_val:
            # 划分子集（特征i取值为val的样本）
            sub_dataset = create_sub_dataset(dataSet, i, val)
            prob = len(sub_dataset) / len(dataSet)  # 当前取值概率
            
            # 累加条件熵
            cur_info_ent += prob * calcInfoEnt(sub_dataset)
            
            # 累加属性熵（跳过概率为0的情况）
            if prob > 0:
                info_V -= prob * log(prob, 2)
        
        # 计算信息增益
        info_gain = total_entropy - cur_info_ent
        
        # 计算信息增益比（避免除零错误）
        if info_V == 0:
            gain_ratio = 0.0
        else:
            gain_ratio = info_gain / info_V
        
        # 更新最佳特征
        if gain_ratio > best_gain_ratio:
            best_gain_ratio = gain_ratio
            best_feature = i
    
    return best_feature

if __name__ == "__main__":
    data = eval(sys.stdin.readline().strip())
    result = calc_max_info_gain_ratio(data)
    print(result)

关键函数说明

  1. calcInfoEnt(data)：

    • 计算数据集的信息熵
    • 遍历数据统计标签分布
    • 根据熵公式计算结果

  2. create_sub_dataset(dataSet, i, value)：

    • 根据特征值划分子集
    • 移除当前特征列
    • 返回新子集

  3. calc_max_info_gain_ratio(dataSet)：

    • 计算总信息熵
    • 遍历每个特征：
      • 计算条件熵（各子集熵的加权和）
      • 计算属性熵（特征取值分布的熵）
      • 计算信息增益比
    • 返回信息增益比最大的特征索引

总结

信息增益比通过引入特征固有值，解决了信息增益对多值特征的偏好问题。本题实现的关键步骤：

  1. 正确计算数据集的信息熵
  2. 按特征取值划分子集
  3. 分别计算条件熵和属性熵
  4. 综合得出信息增益比
  5. 选择增益比最大的特征

该算法能有效识别最具判别力的特征，优化电商平台的推荐系统。