信息增益、信息增益率计算 以及 最佳特征挑选 的Python实现
导读：决策树是一种基于信息的学习算法。在决策树算法中需要不断地挑选出最佳特征，而挑选最佳特征地依据就是信息增益率。
增益本身就具有相对地特性，表征某事物从一个状态到另一个状态后，某个指标的变化量。
在决策树算法中，信息增益指的是依据某个特征的取值划分数据集时，数据集划分后相对于划分前，所能导致减少的信息不确定度。
这也就是说信息增益即不确定度的降低值。当我们以信息熵（香浓熵，简称熵）作为不确定性的度量时，以数据集划分前的原始熵减去数据集划分后的剩余熵得到的值就是信息增益。
1. 求解信息增益
1.1 已经准备好的接口
（1）划分数据集函数（仅展示接口，具体内容请参阅【博文1】）
def dividing_data_set(date_set,node_feature,node_feature_value): """ 划分数据集 整个划分方法的思想是"记录索引-重索引"。简而言之就是先记住特征取值为指定取值的索引号，然 后依据记录索引号保对其它特征下同索引号的元素进行保留。最终实现留下当前划分数据条的目的。 Parameters ---------- date_set： "dict"结构的数据集，其中键为”labels“的键值对对应为标签集（源于x_train），其余 的对应为特征取值键值对（源于y_train）。 node_feature：可以是num、str等类型，但是必须和date_set中的键的类型保持一致。表示需要划分 数据集的节点处对应的特征名。 node_feature_value：是对应与 node_feature 的一个特定取值。 Returns ------- result : dict 返回子数据集字典，其形式与date_set保持一致。其中键`labels`对应的值类似是子标签集数组。 """
（2）混杂度求取函数（仅展示接口，具体内容请参阅【博文2】）
def impurity(anArray, impurity_t="entropy"): """ 计算混杂度 Parameters ---------- impurity_t： str，表示混杂度的度量方式，只能是{"entropy","gini"}中的一个。 anArray： an Array like object，由某特征依次对应每条数据下的取值构成。 Return result: float 为计算得到的impurity的数值。 """
1.2 使用实例讲解
这里采用【博文1】中的例子：
import numpy as np # 定义模拟数据 x_train = np.array([[1, 4, 2, 0, 3, 1, 1, 0, 1, 4, 2, 4, 4, 2, 4, 2, 0, 2, 2, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 3, 1, 3, 1, 3, 1, 1, 0, 1, 4, 3, 4, 4, 2], [0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 2, 3, 0, 3, 1, 1, 0, 0, 4, 2, 2, 4, 1, 1, 0, -1, 0, 4, 0, -1, -1, 0, 0, 0, 0, 0, 0, 2], [4, 2, 2, 3, 1, 2, 1, 1, 0, 2, 1, 1, 1, 0, 3, 0, 3, 2, 2, 0, 0, 0, 0, 3, 1, 1, 2, 3, 4, 3, 1, 1, 3, 1, 2, 1, 1, 0, 1, 2, 2, 1, 0], [1, 4, 2, 2, 3, 1, 1, 0, 0, 2, 1, 1, 1, 0, 3, 4, 2, 2, 4, 1, 0, 1, 0, 3, 2, 2, 4, 3, 1, 2, -1, 2, 2, 1, 0, 1, -1, 0, 1, 1, 1, 0, 0], [1, 2, 2, 1, 3, 1, 1, 0, 0, 2, 2, 1, 1, 0, 0, 4, 1, 2, 1, 0, 0, 0, 0, 2, 1, 1, 2, 3, 3, 0, -1, 2, 1, 3, 1, 1, 0, 0, 2, 3, 2, 1, 0], [1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 3, 3, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 3, 2, 4, 2, 2, -1, 2, 2, 3, 0, 0, 0, 0, 2, 2, 2, 2, 0], [1, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 2, 0, 3, 2, 1, 1, 0, 2, 2, 1, 0, 3, 3, 2, 1, 1, 3, 0, -2, -1, -1, 0, 1, 0, 2, 2, 1], [0, 0, 3, 3, 2, 0, 0, 0, 0, 3, 3, 3, 0, 2, 1, 3, 3, 3, 2, 1, 1, 0, 0, 3, 4, 4, 1, 2, 1, 0, 1, 2, 2, 1, -1, -1, 0, 0, 2, 1, 2, 1, 2], [2, 4, 2, 0, 2, 1, 0, 1, 0, 2, 2, 3, 4, 2, 2, 3, 0, 2, 0, 1, 1, 0, 0, 0, 3, 3, 0, 4, 2, 2, 1, 3, 1, 4, 0, -1, 1, 0, 3, 1, 2, 4, 0], [1, 4, 1, 0, 1, 0, 0, 0, 0, 3, 2, 3, 3, 4, 4, 1, 0, 1, 0, 1, 0, 1, 0, 0, 2, 1, 4, 2, 0, 4, 1, 3, 1, 3, -1, 0, -1, 0, 3, 2, 3, 2, 3]],) y_train = np.array([1, 0, 0, 1, 0, 0, 1, 0, 0, 1]) features = ["feature_"+str(i) for i in range(43)] # 产生43个不同的特征名字 # 转换为数据集字典 date_set = dict(zip(features,x_train.T)) date_set.update({"labels":y_train}) # 将标签集（labels，也就是输出y们）也加入数据集
在【博文1】中，我们是假设了"feature_13"最为node_feature，也就是第一个”最佳特征“。但是当时只是假设的，并不是计算得出。到了本文，我的的任务就是要算出所有节点划分数据集前后的信息增益，取其最大者为真实的最佳特征。
不过我们仍然可以以"feature_13"为例，计算"feature_13"在划分前后的信息增益。
1.3 信息增益计算的实现
计算数据集划分前labels的熵作为划分前的熵，数据集划分后各个子数据集labels熵的和作为数据集划分后的熵。以此直接求取信息增益。
def gain(impurity_t, impurity_before_divide, data_set, probable_feature): """ 计算信息增益 需要传入数据集划分前的不纯度、划分数据集所依赖特征对应的取值数组。考虑到在同一个节点测试不同子特征增益时都有用 到划分前的不纯度，为了提升运行效率故在gain()外计算好该节点分裂前的不纯度后再传入gain()函数。其中数据集划分前的 熵就是划分前的标签集labels的熵。其中按某特征划分后的不确定度，为依该特征各个取值划分的子数据集的中的标签集（即 该特征划分完后所有的子标签集）的不确定度总和。 Parameters ---------- impurity_t: str,不纯度的度量方式，只能是{"entropy","gini"}中的一个。 impurity_before_divide: float，表示数据集划分前的不纯度。 data_set： dict，划分前的数据集。 probable_feature: str，用于划分数据集的特征。 Return ------ result: float，表征信息增益值。 """ impurity_after_divide = 0 # 初始化数据集划分后的不存度为0 for value in set(date_set[probable_feature]): # 获取该特征所有的取值并使用集合去重，遍历之 one_sublabel_array = dividing_data_set( # 获取该子数据集中的标签集数组 date_set = date_set, node_feature = probable_feature, node_feature_value = value )['labels'] impurity_after_divide = impurity(one_sublabel_array,impurity_t) # 累加每个子数据标签集的不存度 return impurity_before_divide - impurity_after_divide # 做差得到这个特征的增益并返回 impurity_t = "entropy" # 使用信息熵度量混杂度 impurity_before_divide = impurity(date_set["labels"],impurity_t) # 数据集划分前labels的混杂度 probable_feature = "feature_13" # 假设当前划分数据集用该特征 gain(impurity_t, impurity_before_divide, date_set, probable_feature)
Out[i]: 0.9709505944546686
2. 使用信息增益存在的问题与信息增益率
由于取值越连续则不确定度越大，直接使用信息增益往往容易导致取值数量越多的特征则越容易被挑选出来。为了平衡特征取值趋于连续带来的影响，我们使用信息增益率作为信息增益的替代方案以选取最佳特征。
改为求解信息增益率的算法如下：
def gain_rate(impurity_t, impurity_before_divide, data_set, probable_feature): """ 计算信息增益率 相对于信息增益的计算，信息增益率还要求解出由于该特征的不同取值带来的不确度。 - 若由于特征取值带来的不确定度为0，说明无特征取值连续化影响，直接返回信息增益； - 若特征取值带来的不确定度不是0，则使用信息增益除以特征取证带来的不确定度。 Parameters ---------- impurity_t: str,不纯度的度量方式，只能是{"entropy","gini"}中的一个。 impurity_before_divide: float，表示数据集划分前的不纯度。 data_set： dict，划分前的数据集。 probable_feature: str，用于划分数据集的特征。 Return ------ result: float，表征信息增益值。 """ impurity_after_divide = 0 # 初始化数据集划分后的不存度为0 for value in set(date_set[probable_feature]): # 获取该特征所有的取值并使用集合去重，遍历之 one_sublabel_array = dividing_data_set( # 获取该子数据集中的标签集数组 date_set = date_set, node_feature = probable_feature, node_feature_value = value )['labels'] impurity_after_divide = impurity(one_sublabel_array,impurity_t) # 累加每个子数据标签集的不存度 gain = impurity_before_divide - impurity_after_divide # 做差得到这个特征的增益 feature_impurity = impurity(data_set[probable_feature],impurity_t) gain_rate = gain/feature_impurity if feature_impurity > 0 else gain return gain_rate impurity_t = "entropy" # 使用信息熵度量混杂度 impurity_before_divide = impurity(date_set["labels"],impurity_t) # 数据集划分前labels的混杂度 probable_feature = "feature_13" # 假设当前划分数据集用该特征 gain_rate(impurity_t, impurity_before_divide, date_set, probable_feature)
Out[i]:0.7134285408041596
3. 基于信息增益率的最佳特征挑选
这是本节最为简单的部分了，需要完成的工作包括：
- 获取当前节点处所有的特征；
- 依次假设每一个特征就是当前节点处分裂的最佳特征，划分数据集从而计算出这些特征各自再划分前后的信息增益率；
- 比较：选取上一步中，实际划分前后信息增益率最大者作为当前节点处的最佳特征返回之。
实现代码如下：
def best_feature(impurity_t,date_set): """ 求取节点处的最佳特征 Parameters ---------- date_set: dict，与某个节点处的对应的数据集 Return ------ result： str，数据集date_set所属节点处可用于分裂的最佳特征 """ features = [i for i in date_set if i != "labels"] # 获取数据集中当前节点处所有特征 impurity_before_divide = impurity(date_set["labels"],impurity_t) # 数据集划分前labels的混杂度 max_gain_rate = -1 # 不会小于0，因此随便给个负数初始值 the_best_feature = "" for probable_feature in features: rate = gain_rate(impurity_t, impurity_before_divide, date_set, probable_feature) if rate > max_gain_rate: max_gain_rate = rate the_best_feature = probable_feature return the_best_feature impurity_t = "entropy" best_feature(impurity_t,date_set)
Out[i]:‘feature_8’
