基于信息粒度与交互信息的属性约简改进算法

张清华,李新太,2,赵 凡,2,高 满,2

（1.计算智能重庆市重点实验室（重庆邮电大学），重庆400065；2.重庆邮电大学计算机科学与技术学院，重庆400065）

1982年,波兰学者Pawlak提出粗糙集理论[1]，该理论用于处理不精确、不一致、不完备信息和知识的有效数学工具，目前已经在故障诊断、图像处理、海量数据处理、智能控制等研究领域得到广泛应用[2].

属性约简作为粗糙集理论的一个重要研究课题，其主要思想是在满足一定约束的前提下，通过删除不重要或冗余的属性，找到与原始信息系统具有相同分类能力的属性子集，从而提高数据处理与挖掘的效率[3-4].目前，经典的属性约简算法主要有:基于差别矩阵的属性约简算法[5-6]、基于正域的属性约简算法[7-8]和基于信息熵的属性约简算法[9-10].基于差别矩阵的属性约简算法，主要利用差别矩阵导出区分函数，并求解区分函数的析取范式，所有析取项均是约简结果，该方法可以找到所有约简结果，但计算复杂度较高.基于正域的属性约简算法，利用分类质量衡量属性重要度，主要保持约简结果划分到正域集合中的对象个数与全集一致，该方法时空复杂度较低.基于信息熵的属性约简算法，主要从信息观的角度计算属性重要度，利用启发式搜索策略迭代选择重要度大的属性，直到得到的属性集合与原信息系统的分类能力相同.

进一步地，随着基于粗糙集理论的属性约简研究不断深入，众多学者也从多个不同的角度对此研究进行了探索.Chen 等[11]为减少待选择属性的迭代次数从而提升约简算法的效率，提出一种基于属性组的加速策略；Jia等[12]从聚类的角度，考虑了约简过程中对象之间的属性变化，提出一种基于相似度的属性约简算法；Jiang等[13]将多粒度思想引入属性约简算法中，提出一种加速多粒度约简算法，以减少寻找约简结果的时间消耗；Yang 等[14]为提升属性约简的稳定性，考虑多个适应度函数，提出一种属性约简的集成选择器.此外，也有学者在选择候选属性时，考虑到条件属性之间的相关性对分类结果和分类准确率产生的影响，姚晟等[15]引入秩相关系数度量条件属性之间的相关性，翟俊海等[16]引入互信息来度量，提出一种最小相关性最大依赖度的属性约简算法.

经典粗糙集理论下，前向启发式正域约简算法[17]通常从空集开始构建约简集合，每一次的迭代过程都将选择候选属性集合中重要度最大的属性加入约简集合中，然而这种策略没有充分考虑到存在多个重要度最大的候选属性如何合理选择的情况，如果仅采取默认或随机选择的策略，可能导致约简集合的属性数目偏多且泛化能力较弱；同时，在剔除冗余属性时，仅用互信息度量条件属性之间的关联程度，忽略了决策属性对属性之间相关性的影响，从而影响约简结果与分类准确率.

针对以上问题，本文提出了一种基于信息粒度与交互信息的属性约简改进算法.对于选择候选属性过程中存在多个重要度最大的属性时，引入信息粒度衡量每一候选属性本身的信息量，提出一种基于信息粒度的候选属性选择优化策略；其次，对于互信息度量属性之间的关联程度存在一定不足的问题，引入信息论中交互信息的概念，在度量属性之间的关联程度时考虑决策属性提供的信息，从而更好地剔除冗余属性；然后，为了合理地设定属性冗余阈值，从数据驱动的角度，考虑全集中两两不相同的条件属性之间与决策属性的交互信息的均值作为阈值.实验结果表明，本文提出的约简算法能够获得泛化能力较强和分类准确率较高的约简结果.

1 基础知识

本节简要介绍粗糙集理论的基本概念及互信息的基础知识.

1.1 粗糙集理论

本小节简要介绍粗糙集理论等相关基础知识.

定义1（决策信息系统）[17]四元组DIS=＜U,C⋃D,V,f＞称为决策信息系统.其中U={x1,x2,…,xp}是由p个对象组成的非空有限集合，称为论域；C={c1,c2,…,cn}是由n个条件属性组成的非空有限集合；D={d}表示决策属性集合，且C⋂D= ∅；V=表示属性a的值域，f:U×AT→V是一个信息函数，f(x,a)表示为对象x的属性a赋予一个属性值，且f(x,a)∈Va，AT=C⋃D.

定义2（不可分辨关系）[17]给定一个决策信息系统DIS=＜U,C⋃D,V,f＞，对于任意属性子集B(B⊆C⋃D)，论域U上的一个不可分辨关系IND(B)定义为：

定义3（上下近似集）[17]给定一个决策信息系统DIS=＜U,C⋃D,V,f＞，B⊆C，X⊆U，在B上的不可分辨关系为IND(B)，则X关于B的上近似集、下近似集分别定义为：

其中，U/IND(B)={X|X⊆U∧∀x,y∈X∧∀b∈B∧(b(x)=b(y))}表示由不可分辨关系IND(B)在论域U上诱导的划分.进一步，关于X的正域POSB(X)、边界域BNDB(X)和负域NEGB(X)分别定义为：

定义4（约简）[17]给定一个决策信息系统DIS=＜U,C⋃D,V,f＞，B⊆C，非空子集B是关于C相对于决策属性D的一个约简，当且仅当B满足如下条件：

1)POSB(D)=POSC(D);

2)对于∀b∈B，都有POSB-{b}(D)≠POSC(D).

定义5（依赖度）[17]给定一个决策信息系统DIS=＜U,C⋃D,V,f＞，对于任意属性集合B⊆C，决策属性D依赖于条件属性集合B的依赖度定义为γB(D)=|POSB(D)|/|U|，其中 ||⋅表示集合的基数.

在经典粗糙集下的前向启发式正域约简算法中，依赖度通常为条件属性重要度的衡量指标.

1.2 互信息

本节简要介绍熵与互信息等相关概念.

定义6（Shannon 熵）[18]给定一个离散随机变量X，其值域为Vx，p(x)表示变量X取值为x的概率，x∈Vx，那么Shannon熵H(X)的定义为

定义7（条件熵）[18]给定随机离散变量X的条件下，随机离散变量Y的不确定性程度可用条件熵H(Y|X)度量，其定义为，其中p(x,y)表示变量X和Y的联合概率分布.

定义8（互信息）[18]给定两个随机离散变量X和Y，则该两个变量之间的相关程度可用互信息度量，其互信息I(X;Y)定义为I(X;Y)=H(Y)-H(Y|X)=H(X)-H(X|Y).

2 基于信息粒度与交互信息的属性约简改进算法

为了有效处理前向启发式正域约简算法中存在的不足，本文基于信息粒度与交互信息提出了一种新的属性约简算法.接下来，将详细阐述算法的相关内容与实现框架.

2.1 基于信息粒度的候选属性选择优化策略

前向启发式正域约简算法在选择候选属性的过程中，忽略了存在相同依赖度大小的条件属性，即表示存在多个依赖度最大的条件属性，如果仅从依赖度去考察属性的重要程度，可能并未知晓如何去选择属性；同时，若采用随机选择或默认选择候选属性的策略，可能得到的属性集合数目过多且泛化能力较弱.因此，本文引入信息粒度的计算方法，进一步优化候选属性的选择策略.首先给出信息粒度的相关定义及其性质.

定义9（信息粒度）[19]给定一个决策信息系统DIS=＜U,C⋃D,V,f＞，B⊆C，论域U在属性子集B上形成的等价关系划分为U/B={X1,X2,…,Xm}，那么条件属性B的信息粒度GK(B) 定义为决定的等价关系中元素的个数.

定义10（信息熵）[20]给定一个决策信息系统DIS=＜U,C⋃D,V,f＞，B⊆C，论域U在属性子集B上形成的等价关系划分为U/B={X1,X2,…,Xm}，那么条件属性B的信息熵E(B) 定义为E(B)=

那么，优化后的前向启发式正域约简算法中选择候选属性的策略分别为：

策略1若候选属性集合中存在唯一的依赖度较大的条件属性，则优先选择该属性加入约简集合中；

策略2若候选属性集合存在多个依赖度较大而且相同的条件属性，此时从候选属性本身具有的知识量去选择，利用信息粒度值的大小刻画属性知识量的多少，选择信息粒度值较小的候选属性加入约简集合中.

定理1[19]给定一个决策信息系统DIS=＜U,C⋃D,V,f＞，B⊆C，论域U在属性子集B上形成的等价关系划分为U/B={X1,X2,…,Xm}，那么信息熵E(B)与信息粒度GK(B)具有下面的关系：

由定理1可知，某一属性的信息粒度与其信息熵成反比，即信息粒度较小的属性，表示其信息熵较大，则其属性本身的混乱程度越高，从而可以提供更多有价值的信息.由此基于信息粒度的候选属性优化策略使得选择的属性往往能够朝着不确定性较低的方向发展.

2.2 基于交互信息的属性相关性度量

在约简算法中，部分学者[15-16]考虑约简集合中条件属性间的相关程度，大多以互信息指标去度量.通过考察候选属性与已选属性之间的相关性，根据预先设定的冗余阈值，从而判断是否选择保留该属性，进而使得选择的属性集合相对于决策属性的依赖度较大，而条件属性之间的相关性较小.但如果仅以互信息度量属性之间的相关程度，却忽略了决策属性的重要性，存在夸大条件属性之间相关程度的问题，使得度量的数值并不准确.如图1所示，条件属性f1和f2之间的相关程度大小为a+b，但实际上，在决策属性D下，其相关程度大小为b.

图1 互信息与交互信息示意图Fig.1 The schematic diagram of mutual and interaction information

为了更好地刻画属性之间的相关性，避免因互信息过度夸大属性与属性之间的相关程度带来的问题，本文引入信息论中的交互信息作为计算条件属性间相关程度的方法，从而达到准确去除冗余属性的目的.下面给出条件互信息与交互信息的相关定义.

定义11（条件互信息）[18]在给定随机变量Z的情况下，其余两个随机变量X和Y的相关程度可用条件互信息度量，其定义为I(X;Y|Z)=H(X|Z)+H(Y|Z)-H(X,Y|Z).

定义12（交互信息）[21]在给定随机变量Z的情况下，与其余两个随机变量X和Y之间的共同相互作用可用交互信息度量，其定义为I(X;Y;Z)=I(X;Y)-I(X;Y|Z).

交互信息的数值大小可以是正数、零或负数.当为正数时，表示变量X和Y提供相同的信息量；当为零时，表示变量X和Y在变量Z的情况下是独立的；当为负数时，表示变量X和Y提供比他们单独提供的信息量更多.

在考虑是否删除候选属性时，人为预先设定属性间统一的冗余阈值存在一定的不足，因为在不同的数据集下，其属性间的冗余阈值是有一定差异的.因此，从数据驱动角度，给出了一种确定属性之间冗余阈值的计算方法.

定义13（冗余阈值）给定一个决策信息系统DIS=＜U,C⋃D,V,f＞，其属性间的冗余阈值θ定义为θ=其中，n表示属性集合C的属性总个数，ci表示属性集合C中的第i个属性，num表示属性之间的计算总次数，即num=(n*(n- 1))/2.

因此，在确定是否保留候选属性的过程中，如果此时选择的候选属性与约简集合中的属性两两之间交互信息的均值小于阈值θ，则将该候选属性加入到约简集合中，否则将其删除.

2.3 基于信息粒度和交互信息的属性约简改进算法（IG2IAR）

IG2IAR 算法从空集开始构建约简集合，首先根据定义13 确定条件属性间的冗余阈值θ，然后根据定义5依次计算条件属性与决策属性之间的依赖度数值，选取依赖度最大的条件属性加入约简集合中；如果此时存在多个依赖度最大的条件属性，则根据定义9计算条件属性的信息粒度值，选取信息粒度值最小的条件属性加入约简集合中；加入约简集合之前，要对拟加入的条件属性和约简集合中的所有条件属性进行冗余阈值的判断，如果拟加入的条件属性和约简集合中其他条件属性的交互信息数值的平均值小于θ，则将该条件属性加入到约简集合中，反之，删除该条件属性，继续遍历除约简集合以外其他的条件属性，直至全集下划分到正域的对象个数与约简集合下划分到正域的对象个数保持一致.

下面给出IG2IAR算法的详细步骤：

算法1IG2IAR算法

输入：决策信息系统DIS=＜U,C⋃D,V,f＞；

输出：一个约简子集R.

Step 1R= ∅，R′=C-R.

Step 2对于任意的条件属性e,f∈C，计算2 个互不相同的条件属性与决策属性D之间的交互信息数值I(e;f;D)，根据定义13计算出冗余阈值θ；

Step 3重复以下步骤，直到POSC(D)=POSR(D).

Step 3.1对于R′中所有的条件属性a′∈R′，根据定义5依次计算a′相对于决策属性D的依赖度，选出依赖度最大的条件属性b= argmax{γ{a′⋃R}(D)}，仍记为a′，转到Step 3.3；若存在多个依赖度最大的属性，转到Step 3.2；

Step 3.2对于R′中所有的条件属性a′∈R′，根据定义9 依次计算a′的信息粒度，选出信息粒度最小的条件属性c= argmin{GK({a′⋃R})}，仍记为a′，转到Step 3.3；

Step 3.3对于所有已选条件属性a∈R，利用交互信息计算其相关程度大小I(a′;a;D)；

Step 3.4如果，则R′=R′-{a′}，转到Step 3；否则R=R⋃{a′}，R′=R′-{a′}，转到Step 3；

Step 4返回约简R.

3 实验分析

3.1 数据集和实验设计

为了验证提出方法的有效性，本文在10 个高维微阵列基因表达数据集[22-23]上进行了实验.基本信息由表1所示，数据集可从http://featureselection.asu.edu/datasets.php和http://csse.szu.edu.cn/staff/zhuzx/Data‐sets.html下载得到.

所有实验均在Matlab 2014b 实验平台完成，环境为PC 机，Intel(R)Core(TM)i7-7700 CPU@3.60GHz&8.0 GΒ RAM，采用SVM、KNN以及随机森林(Random Forests，RF)算法求分类准确率，设置KNN参数K为1，随机森林的树个数为10.实验采用十折交叉验证的方法进行分类，通过训练数据集进行模型训练，在测试数据集上获得分类准确率.因为本文所提方法仅处理离散型数据，所以利用公式a′(x)=将条件属性的连续型数值转化为离散值，其中，a表示低于特征a属性值的最大整数值，a(x)、mina和σa分别表示在属性a下的真实值、最小值和标准偏差值.

3.2 属性降维的参数确定

针对10 个高维基因数据集，为有效降低模型训练与分类的时间成本，采用Fisher Score[24]先对基因属性采取初步降维的策略.选择Fisher Score作为此度量方法的主要原因是计算量少，精度高，能有效降低计算的复杂度.通过计算每个基因属性的Fisher Score 值，根据需求将n个基因属性选择出来组成一个属性子集.算法2如下.

算法2基于Fisher Score的属性选择算法

输入：一个具有p个对象和n个基因属性的决策信息系统DIS=＜U,C⋃D,V,f＞；选择的期望属性数fnum；

输出：属性子集S.

Step 1获取所有基因属性的Fisher Score值；

Step 2根据每个基因属性的Fisher Score值利用排序算法对基因属性进行降序排序；

Step 3选择前fnum个Fisher Score值较大的基因特征，将该基因特征放入集合T中；

Step 4通过集合T获得降维后的基因属性子集S；

Step 5返回选择的基因属性子集S.

为了合理设置所有基因表达数据集的降维个数，采用算法2 在7 个特征维度（10，50，100，150，200，250，300）上利用10 折交叉验证在SVM 分类器上获得相应的平均分类准确率.图2 展示了10 个微阵列基因表达数据集在不同维度的基因属性子集下SVM 分类器准确率的变化趋势.由图2 可知，随着基因属性子集大小的变化，准确率在多数情况下也有所变化，但同时多数数据集在选择150维度的基因属性子集的情况下可以获得较高的分类准确率.因此，将所有数据集的fnum统一设置为150维.

图2 在10个数据集上基因特征维度变化的分类准确率的变化趋势图Fig.2 The classification accuracy via the size of gene subset on 10 gene data sets

3.3 基于信息粒度的候选属性选择优化策略的有效性验证

为了验证基于信息粒度的候选属性选择优化策略（GK_opt）的有效性，本文与传统的前向启发式搜索正域约简算法[17]（Pos_For）进行了实验对比.在10 个微阵列基因表达数据集上利用KNN 分类器，并以10折交叉验证的平均分类准确率和属性子集的平均长度来评价所选属性的质量，同时采用Wilcoxon符号秩检验[25]测试分析两种算法之间的差异性，实验结果由表2所示.

表2 Pos_For 与GK_opt之间的结果对比Tab.2 Comparison results between Pos_For and GK_opt

从表2 可以看出，在分类准确率上，在大部分基因数据集上均获得了较高的分类准确率，同时在AL‐LAML、SMK_CAN_187、Prostate_GE 和MLL 基因数据集上，虽然与Pos_For 算法选择的属性子集长度相同，但分类准确率明显优于Pos_For 算法，这表明基于信息粒度的候选属性选择优化策略，在存在多个依赖度最大的属性情况下，其属性结果的泛化能力更好.此外，在选择的属性子集长度上，TOX_171、lung、GLI_85 和CLL_SUΒ_111 基因数据集明显优于Pos_For 算法.与Pos_For 算法相比，基于信息粒度的候选属性选择优化策略的约简算法，平均准确率提升了3.07%，平均选择的特征长度降低了1.06%.进一步地，利用Wilcoxon 符号秩检验测试分析平均分类准确率的差异性，p 值为0.020 9，表明在0.05 显著性水平下，传统的前向启发式搜索正域约简算法与基于信息粒度的候选属性选择优化策略的约简算法存在显著性差异.因此，基于信息粒度的候选属性选择优化策略不仅可以使得选择的属性子集数目更少，而且属性子集的泛化能力更好，分类准确率也有一定的提升.

3.4 IG2IAR约简算法与传统的约简算法对比

为了验证IG2IAR 算法比其余传统的约简算法的优越性，本文在10 个高维基因数据集上采用十倍交叉验证方法从SVM、KNN 与随机森林分类器的平均分类准确率与选择的属性子集平均长度方面来对比其余约简算法.算法主要包括传统的前向启发式搜索正域约简算法（Pos_For）、最小相关性最大依赖度属性约简算法[16]（MS）以及最小相关性最大依赖度属性约简的改进算法[26]（MM），MS 约简算法属性之间的冗余阈值为0.65，与文献[16]相同.在SVM、KNN 和随机森林分类器下，4 个约简算法所选属性子集的平均分类准确率与约简子集的平均属性长度在表3和表4展示.

由表3 和表4 可以看出，IG2IAR 算法的分类准确率在大部分基因数据集上明显优于其他方法，而且IG2IAR算法的平均分类准确率在这三个分类器上均达到最高，同时在SVM、KNN 及随机森林分类器上，IG2IAR 算法在平均准确率上分别比其他方法高4.08%～4.46%，1%～3.84%和2.67%～4.09%.由表7可以看出，在TOX_171 和lung 数据集上，IG2IAR 算法明显优于其余三种方法，但在ALLMAL、GLI_85、Cen‐tral_Nervous_System和Ovarian_Cancer数据集上，Pos_For算法和MS算法选择的属性子集个数更少.尽管IG2IAR算法、Pos_For算法和MS算法在SMK_CAN_187、CLL_SUΒ_111、Prostate_GE和MLL数据集上选择相同数目的属性子集，除了KNN分类器上的MLL数据集与随机森林分类器下的CLL_SUΒ_111数据集以外，IG2IAR 算法均可在所有分类器上获得较高的分类准确率，由此可知IG2IAR 算法选择的属性子集，具有更好地泛化能力，可以获得较高的分类准确率.此外，本文提出的方法，所选属性子集的平均长度均值参数仅比Pos_For 算法与MS 算法小0.04，差异性较小.因此，本文提出的方法选择的属性子集长度较短，而且泛化能力更好，分类准确率也有一定的提升.

表3 SVM和KNN分类器下分类准确率的对比结果Tab.3 The comparison of classification accuracy on SVM and KNN classifier

表4 随机森林分类器下分类准确率与选择的属性子集平均长度的对比Tab.4 The comparison of classification accuracy on Random Forests classifier and the average length of selected subsets

3.5 统计分析

为了系统地探讨所有对比算法在分类准确率方面的统计性能，将采用Friedman测试[25]和Wilcoxon符号秩检验测试进行统计分析.

由表5 可知，IG2IAR 算法的平均排名优于其余三种方法.进一步地，当显著性水平为0.1 时，SVM、KNN 和随机森林分类器上的p-value 均小于0.1，即表示在显著性水平为0.1 下，所有算法在SVM、KNN与随机森林分类器下的分类准确率存在显著性差异.同时，利用Wilcoxon符号秩检验测试对比IG2IAR算法与其余算法两两之间的显著性差异，当显著性水平为0.1 时，在SVM 与随机森林分类器下，IG2IAR 算法的性能明显优于其余三种约简方法，但在KNN 分类器下，IG2IAR 算法与MM 算法之间没有显著性差异.总之，本文提出的算法总体上优于其他三种算法.

表5 所有算法在三种分类器上的Friedman测试与Wilcoxon秩和检验测试结果Tab.5 The Friedman test and Wilcoxon sign rank sum test results of all algorithms on the three classifiers

4 结论

基于前向启发式正域约简算法无法合理选择存在多个重要度最大的条件属性，同时在考虑约简集合中条件属性之间的相关性时，忽略了决策属性对条件属性之间相关性的影响程度，因此，本文提出了一种基于信息粒度的候选属性优化策略，并引入信息论中交互信息的概念度量条件属性之间的相关程度以进一步剔除冗余属性，从而保证约简集合的泛化能力，进而提出一种基于信息粒度与交互信息的属性约简改进算法.实验结果表明，本文提出的算法有较好的属性约简结果和分类准确率.