doi: 10.12052/gdutxb.180023
陈平华1，黄辉1，麦淼2，周宏虹3
（1. 广东工业大学 计算机学院，广东 广州 510006；2. 广东南方报业传媒集团有限公司，广东 广州 510601；
3. 广东省科技创新监测研究中心，广东 广州 510033）
摘要: 针对传统单标签特征选择算法不能直接应用于多标签数据的问题, 提出一种多标签特征选择算法——MML-RF算法. 在ReliefF的基础上, MML-RF算法提出新的类内最近邻样本查方式, 并结合多标签的贡献值改进特征权值的计算方法, 能很好地适应多标签数据的特点; 同时为了减少特征冗余, MML-RF算法以互信息作为特征冗余度量方式, 提出一种去冗余方法, 能够得到更小的特征子集. 实验表明, MML-RF多标签特征选择算法得到的特征子集规模较小, 且在多标签数据集上具有很好的分类效果, 能够提升多标签学习和数据挖掘工作的效率. 关键词: 特征选择；多标签学习；ReliefF；互信息；特征冗余
中图分类号: TP181 文献标志码: A 文章编号: 1007–7162(2018)05–0020–06
Multi-label Feature Selection Algorithm Based on ReliefF and
Mutual Information
Chen Ping-hua1, Huang Hui1, Mai Miao2, Zhou Hong-hong3
(1. School of Computers, Guangdong University of Technology, Guangzhou 510006, China; 2. Guangdong Nanfang Media
Group, Guangzhou 510601, China; 3. Guangdong Science and Technology Innovation Monitoring and Research Center,
Guangzhou 510033, China)
Abstract: In view of the problem that the traditional feature selection algorithm can not be applied to the multi-label learning context, a MML-RF algorithm is presented. The MML-RF improves the way of defining and searching nearest neighbor on the basis of the ReliefF, and introduces a new parameter to consider the contribution values of different labels. The improved weighting formula enables MML-RF to be used to the multi-label dataset.
MML-RF algorithm makes use of mutual information as the measure of feature redundancy, and puts forward a solution to redundancy, which can get smaller subset of features. Experiments show that the feature subset of MML-RF is smaller, and has good classification effect on multi-label dataset, which can further enhance the efficiency of subsequent multi-label learning and data mining.
Key words: feature selection; multi-label learning; ReliefF; mutual information; feature redundancy
特征选择是机器学习和数据挖掘工作中的重要环节，可以移除不相关和冗余的特征，从而降低数据维度提高算法效率. 特征选择算法旨在到一个小数量的特征集合用以描述整个数据集，且描述效果能够接近甚至超越原始的特征集合[1-4].
特征选择已经被广泛应用于单标签数据的学习中，即每个实例只有一个类别与之相关联的数据集.其中，ReliefF是经典的单标签特征选择算法[5]，其核心思想是利用特征与类别之间的相关性来评判特征的分类能力，通过各特征的相关性大小得到平均权重. 特征的权重越大，表示该特征的分类能力越强；反之，表示该特征分类能力越弱. ReliefF算法运行效率高，且特征选择能力优秀[6-8].
然而在实际问题中，一个实例通常能够被同时标记为多个类别，称之为多标签分类问题[9-10]. 比如一部电影可以被同时标记为“剧情片”和“动作片”. 目
第 35 卷第 5 期广东工业大学学报Vol. 35 No. 5 2018 年 9 月Journal of Guangdong University of Technology September 2018
收稿日期：2018-01-29
基金项目：国家自然科学基金资助项目(61572144); 广东省科技计划项目(2013B091300009, 2014B070706007, 2017B030307002)作者简介：陈平华(1967–)，男，教授，主要研究方向为大数据与推荐系统.
通信作者：黄辉(1991–)，男，硕士研究生，主要研究方向为数据挖掘、机器学习，E-mail：daniel_allo@163
前，多标签数据集上的机器学习和数据挖掘等领域的研究和工作已经成为热点，越来越多的研究领域需要应用到多标签分类算法，如生物信息学、情感分析、文本情感注释和文本挖掘等[11-12]. 因此开展多标签特征选择算法的研究，具有重要的理论意义和应用价值.
现阶段关于多标签特征选择算法的研究较少，解决多标签问题的常用方法是数据转化法，即将一条多标签数据转化为多条单标签数据或者将该多标签集合作为一个新标签，进而对处理后的数据运用单标签特征选择算法. 然而数据转化法忽略了标签之间的关系，而这恰恰是多标签分类问题的核心所在，
导致该类方法得到的特征子集性能不佳，解释性略差. 另一种解决多标签问题的方法是适应型特征选择算法，即将单标签特征选择算法进行扩展与改进，综合考虑多个标签的相互关系，使该类方法更加适应于多标签数据集的特点. 算法适应型方法已经成为解决多标签问题的重点研究方向[13-16].
通过对多标签数据的研究，在传统单标签特征选择算法ReliefF 的基础上，提出一种可以适用于多标签数据集的特征选择方法，即MML-RF 算法(Modified Multi-Label ReliefF Algorithm). 相比于传统的数据转化方法，MML-RF 不需要对数据进行标签转换；相较于传统ReliefF 算法，MML-RF 算法通过重新定义最近邻样本的概念，综合考虑标签对特征的贡献，能够实现多标签分类问题的特征选择. 此外，算法引入互信息作为特征冗余的度量方式，提出了一种能够有效除去冗余的方法，解决了传统ReliefF 系列算法不能去冗余的缺点.
1 ReliefF 特征选择算法
由Kira 等在1992年提出的Relief 算法只适用于二
分类数据的特征选择，Kononenko 在Kira 等的研究成果基础上提出了ReliefF 算法用于解决多类问题[17].ReliefF 的基本原理和Relief 相似，前者选择k 个同类最近邻样本和不同类最近邻样本的操作是其与后者的基本区别. ReliefF 算法在处理多类问题时，每次从训练样本集中随机取出一个样本R ，每次从样本点R 的同类的样本集中出k 个近邻样本，从不同类的样本集中分别出k 个近邻样本，然后
不断随机地选取多个样本点进行特征权重的更新，得到特征权重排名，并设定阈值来选择有效特征.
D ={(x 1,y 1),(x 2,y 2),···,(x n ,y n )}x i ∈R p p y i ∈R q 记训练数据为，其中为数据的特征空间，为特征个数；为
q L j ,(j =1,2,···,q )q j i L j y i (L j )=1y i (L j )=0R i q ∑j =1
y (L j )=1数据的类标签空间，为类标签个数. 记
为个标签中的第个，则在样本空
间中，若第个样本属于第个类，则记为；反之，则记为. 在单标签数据集中，每一个样本只能属于一种类别，则对于某样本点，有
.
m k k class(R i )R i di ff(A ,R 1,R 2)R 1R 2A P (C )C P (C )[1−P (class(R i ))]M j (C )C j ReliefF 算法流程见算法1，其中样本点选取个数
和近邻数的选取由数据集实际情况决定，的取值
一般设定为10. 表示样本点所属于的标签类型，表示样本和在特征上的距离. 表示第类样本的概率，不同类样本的贡献使用其类的先验概率加权，并在总和中将样本概率除以因子，保证不同类样本的概率权重总和为1. 表示第类数据中的第个样本点.
算法1 ReliefF 算法
m k 输入：训练集D ，取样次数，最近邻数W 输出：特征的贡献权重向量W (A =1:p )=0.01) 初始化i =1:m
2) for R i
3) 在D 中随机选择样本点R i k H j
4) 到与同类的个最近邻样本C class(R i )R i k M j (C )
5) 对于每个，分别到与不同类的个最近邻样本A =1:p
6) for 7) 更新每个特征的贡献权值
8) end for 9) end for
算法1输出为特征的权重向量，权值越大的特征被认为对样本的分类贡献越大，随后通过设定阈值剔除无效和冗余的特征，达到特征选择和数据降维的目的. 由算法1的步骤4)和步骤5)可知，其仅适用于单标签数据，本文将针对多标签数据的特征选择问题做进一步的研究.
2 MML-RF 多标签特征选择算法
2.1 多标签特征选择算法MLRF
在多标签问题中，每一个实例都有可能属于多
第 5 期陈平华，等：结合ReliefF 和互信息的多标签特征选择算法21
个类别，所以传统的ReliefF 算法受限于其最近邻样本的定义和寻方法，并不能适用于多标签问题.
R i n L ′={L 1,L 2,···,L n }L ′R i L i ′(i =1,2,···,n )k 针对ReliefF 算法这一缺点，本文通过调整最近邻类内样本的寻方式和引入多标签贡献值的分配方法，提出MLRF(Multi-label ReliefF Algorithm)多标签特征选择算法. 对于算法随机选出的样本点，查其最近邻时首先应获得该样本点所拥有的个类标签，记为，然后将作为样本点
的类内标签，在中分别寻个类
内最近邻样本，并修改权值计算公式为
D (N (C H ))D (M (C M ))R i 式(1)中，和分别表示样本
与同类最近邻点和不同类最近邻点的平均距离.
C N C M R i N j (C N )M j (C M )C N C M j 其中，和分别表示样本点的同类和不同类的标签，和分别表示第类和第类中的第个最近邻点，其他函数和定义与算法1相同.上述操作从改进类内点的查方式和类内平均距离的计算上做出了改进，所得式(1)的特征权值计算公式可以很好地适应多标签数据的特点.
ω=∆L ′/∆L ∆(·)L L ′
ω此外，由于在多标签数据集中拥有较多标签的实例往往被定义得更加具体，也更具解释性，本文假设拥有标签越多的实例，在多标签分类问题上的贡献越大；相反，越有较少标签的实例，可能存在定义模糊的问题，应当适当削弱其对多标签分类问题的贡献. 本文在式(1)的基础上，加入多标签的贡献参数
参与迭代更新权值，使改进的特征权值
公式能更好地适应多标签数据的特点. 其中操作表示读取全体类标签集合和样本类内标签集合
的元素个数，即表示样本点所属标签类数目占所
有标签类数目的比值.
改进后的特征权值计算式如式(4)所示：
综上所述，本文在改进类内点定义和查方式，以及引入多标签贡献这两个方面对ReliefF 算法进行了扩展与改进，得到多标签特征选择算法MLRF ，算
法具体流程见算法2所示：
算法2 MLRF 算法
m k 输入：训练集D ，取样次数，最近邻数W 输出：特征的贡献权重向量W (A =1:p )=0.01) 初始化i =1:m
2) for R i
3) 在D 中随机选择样本点C H =class(R i )R i H j (C H )
4) 对于每个，分别到与同类的k 个最近邻样本C M
class(R i )R i k M j (C M )
5) 对于每个，分别到与不同类的个最近邻样本A =1:p
6) for 7) 更新每个特征的贡献权值
8) end for
9) end for
游园记新疆自贸区算法2结合了ReliefF 算法的核心思想，通过改进类内点的定义和查方法，同时引入多标签贡献参数，使改进后的算法能很好地适用于多标签情境下的特征选择工作.2.2 特征集冗余度度量
上节所提MLRF 算法虽然能够用于多标签数据的特征提取，但也具有传统ReliefF 算法不能去除特征冗余的缺点，即得到的特征子集仍存在冗余项，可以结合特征去冗余的方法对其进行改进. 特征的冗余性通常使用互信息来度量，互信息是信息论中的一种信息度量方式[18]，它可以看作是一个变量中所包含的关于另一个变量的信息量.
互信息的计算如式(5)所示：
H (·)
I (X ,Y )式(5)中，X 和Y 为向量，表示其信息熵. 互信息反映了X 和Y 的相关性程度，其值越大，代表变量间的相关性越强[19]. 实际使用中，可以使用信息熵作为分母，补偿互信息对取值较多的属性的偏
置，
并将互信息标准化得
将特征向量表示为X i 和X j ，特征间的冗余度使用互信息作为度量，则有
由式(7)可推得单个特征与特征集合S 之间冗余山核桃采摘机
度计算式
22广 东 工 业 大 学 学 报第 35 卷
|S |S S S R (S )式(8)中，表示特征集合中包含的特征数量，X j 为特征集合中的特征项. 由式(5)和(8)可得特征子集的冗余度为
式(9)结合式(6)可得标准化的特征集合冗余度
2.3 MML-RF 多标签特征选择算法
特征选择的目标是选择出对于标签分类有益的特征，并排除冗余的特征. 为了在MLRF 算法的基础上，进一步得到精简有效的特征子集，本文引入互信息作为特征冗余的度量方式，并提出了一种去冗余方法，结合所提MLRF 算法后得到MML-RF(Modified Multi-Label ReliefF Algorithm)多标签特征选择算法.
S S S f S f MML-RF 算法的基本思想是：运行多标签特征选择算法MLRF ，筛选无关特征得到特征子集，随后通过判别评价准则，进一步在中进行去冗余操作得到. 输出的特征子集应尽可能与类标签相关，即对于类标签分类有益，且特征之间的冗余度应尽可能的低
. 基于此原则，构建评价准则如下
W (S )S R s (S )S 式(11)中，表示运行MLRF 算法后，集合
中各特征的权值之和，表示集合的标准化冗
余度，结合式(10)有
εMML-RF 算法步骤：首先运行上节提出的MLRF 多标签特征选择算法，得到按MLRF 评分排序的特征集和相应的权重向量，并设定阈值进行初步筛选，本文阈值设为0.8~0.85之间. 随后通过序列后向搜索的方式进行子集搜索，即每次从候选特征集中移除一个表现最差的特征，评价移除该特征后的特征集合性能，评价方式使用式(12)的评估准则. 此外，本文为了避免算法陷入局部最优解，在子集评判过程中加入容忍度，代表算法允许评分下降的最大范围，使得整个搜索过程尽可能可以跳出局部最优解. 算法的具体流程如算法3所示.
算法3 MML-RF 算法
D δ输入：训练集，MLRF 参数，阈值S f 输出：特征子集，权重向量W f
S 0
1) 运行MLRF 算法，得到权重向量W 0和特征集δS S t S f 2) 根据阈值，得到，初始化和|S |>03) whil
e {i =|S |:1
4) for S t =S −F i S 5) //按后向顺序从中依次删除评
分最低的特征
Φ(S t )>Φ(S )+ε6) if ()S f ←S t 7) then //输出结果Φ(S t )>Φ(S )8) else if ()S t Φ(S t )S ←S t 9) then 记录及，S ←S t 10) else 11) end for }
S t Φ(S t )12) 查记录中的及f =arg max f (Φ(S t ))S t 13) 出使得的S f ←S t S f 14) 置，输出及W f 15) end while
F i i 其中，代表排名第个的特征. 步骤6)到10)表示候选特征集在删除排名最末的特征后，评分有较大提高才能直接输出相应特征集合，而对于评分只有略微提高的这部分候选集合，等到搜索过程完毕通过比较得到其中评分最高的特征集合，如步骤13)所示，对比过程还能结合特征集合的规模进行综合分析.
传统基于互信息的去冗余方法一般只能两两比较特征冗余，不能整体地对特征集合做出评价.MML-RF 算法使用改进的序列后向搜索方法进行子集的搜索和生成，可以对特征集合进行综合的考虑，且容忍度的引入可以使算法在一定程度上跳出局部最优解. 在子集评价方面，算法根据MLRF 权重和冗余度
度量共同构建了性能评价指标，评价过程并不依赖于分类学习器，属于过滤式方法，保持了ReliefF 系列算法运行高效的优点. 最后，本文通过实验验证了MML-RF 算法较之同类算法在整体性能略有提高的基础上，能够去除冗余特征，得到规模较小且有效的特征子集.
3 实验分析
3.1 实验信息
本文实验采用Mulan 多标签分类库[20]中的3个数据集Emotions 、Yeast 和Enron （如表1所示）. 为验证MML-RF 算法在多标签数据集的有效性，本文采用
第 5 期陈平华，等：结合ReliefF 和互信息的多标签特征选择算法23
MLkNN[21]多标签分类算法来评价数据集运行MML-RF算法提取特征的分类性能.
表 1 数据集信息
Tab.1 Data sets
数据集样本特征数类标签
Emotions593726
Yeast 2 41710314
Enron 1 702 1 00153
表1中，Emotions为音乐情感分类数据集；Yeast为酵母菌基因功能分类数据集；Enron为安然邮件信息数据集. 上述3个多标签数据集样本数量较为合理，且具有不同规模的特征和标签数量.
实验采用如下5个多分类性能评价标准，对实验结果进行评估[19].
(1) Hamming Loss(HL)：汉明损失，用于考察样本在单个标记上的误分类情况，该项取值越小，算法性能越好.
(2) One-Error(OE)：一类错误，用于考察样本类别排序最前端的标记不属于标记集合的情况，该项取值越小，算法性能越好.
(3) Coverage(CV)：覆盖率，用于考察样本标签排序序列覆盖所有相关标签的搜索深度情况，该项取值越小，算法性能越好.湖南人文科技学院学报
(4) Ranking Loss(RL)：排列损失，用于考察样本的类标记排序中出现排序错误的情况，该项取值越小，算法性能越好.
(5) Average Precision(AP)：平均精度，用于考察样本的预测标签排序序列中的相关标签仍为样本标签的情况，该项取值越大，算法性能越好.
3.2 实验结果及分析
实验使用MML-RF多标签特征选择算法和ReliefF-ML算法[22]，分别得到不同数据集下的特征排序序列，并使用MLkNN多标签分类模型作为分类器，k值取10，平滑参数为1，测试采用5层交叉验证.得到平均分类精度等各项参数，并通过比较两种算法取到最佳平均分类精度时的多项性能指标及其特征子集规模，说明算法在特征选择和数据降维方面的能力.
由表2可得，MML-RF算法在Emotions、Yeast和Enron 3个数据集上选取的特征子集规模较之ReliefF-ML算法，分别减少36.2%、41.5%和33.8%.
在选取特征比例分别为80%、80%和50%时，ReliefF-ML算法在数据集上得到的特征子集分类效果达到最好；而MML-RF算法在3个数据集上特征子集占比分别为51.4%、46.6%和33.1%左右时即能达到最佳的分类效果.可以得知M M L-R F算法在Emotions和Yeast数据集上特征降维能力优秀，能得到更
小比例的特征子集；而在Enron数据集原本千维级别特征的基础上，算法仅使用33%左右比例的特征即可达到最佳分类性能. 综上所述，MML-RF所得到的特征子集规模更小，能够很好地减小数据规模.
表 2 算法所选特征子集数量
Tab.2 The selected feature sets
数据集原始特征羟基酪醇
盐酸储罐
ReliefF-ML MML-RF
所选特征选择比例/%所选特征选择比例/% Emotions7258803751.4 Yeast10382804844.6 Enron 1 0015005033133.1两种算法在多标签分类器下的分类性能，如表3所示. 在Emotions数据集上，MML-RF算法在各项度量参数上较之ReliefF-ML算法均有提高；在Yeast数据集上，MML-RF算法的分类精度基本持平于ReliefF-ML，而其他4项度量参数均有所提升；在Enron数据集上，MML-RF在分类精度上较之ReliefF-ML有较大提升，RL和OE指标也均有所提高，只有HL和CV值略高于ReliefF-ML. 由上述结果可知，经过MML-RF算法进行多标签特征提取后的数据多项分类性能得到了优化，整体表现优于ReliefF-ML 算法.
表 3 两种算法性能参数对比
Tab.3 Performance comparison of two algorithms
算法HL OE CV RL AP MML-RF(Emotions)0.215 30.268 1 1.880 30.168 10.796 8 ReliefF-ML(Emotions)0.217 60.268 5 1.885 60.170 80.794 3 MML-RF(Yeast)0.210 80.257 1 6.462 90.181 30.763 9 ReliefF-ML(Yeast)0.211 20.259 3 6.505 80.186 70.764 3 MML-RF(Enron)0.066 40.453 426.423 40.243 80.501 8 ReliefF-ML(Enron)0.063 70.473 625.334 00.257 70.491 3
综上所述，MML-RF算法能够有效地去除特征冗余，获得规模更小的特征子集，并且在整体性能上略优于同类的适应型算法，经其输出的特征子集更加精简和有效.
4 结论
本文对传统ReliefF单标签特征选择算法进行了
24广东工业大学学报第 35 卷
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议