㊀第53卷第1期郑州大学学报(理学版)Vol.53No.1
㊀
2021年3月
J.Zhengzhou Univ.(Nat.Sci.Ed.)
Mar.2021
收稿日期:2020-06-25
基金项目：山西省应用基础研究项目(201801D221170)㊂
作者简介：刘吉超(1994 )，男，硕士研究生，主要从事粒计算与数据挖掘研究,E-mail:34360736@qq；通信作者：王锋(1984 )，女，副教授，主要从事数据挖掘与知识发现研究,E-mail:sxuwangfeng@126㊂
基于Relief-F 的半监督特征选择算法
刘吉超,㊀王㊀锋
(山西大学计算机与信息技术学院㊀山西太原030006)
摘要：传统的Relief-F 算法主要用于处理有标记数据集㊂针对部分标记数据集，引入一种基于耦合学习的数据样本相似度，设计了一种面向符号数据的基于Relief-F 算法的半监督特征选择算法㊂为有效验证新算法的可行性，实验分析中选取了5组UCI 数据集和3种常用机器学习分类器来进行验证，实验结果进一步验证了算法的有效性㊂关键词：特征选择；耦合相似度;Relief-F 算法；半监督学习
中图分类号:TP181㊀㊀㊀㊀㊀文献标志码:A㊀㊀㊀㊀㊀文章编号:1671-6841(2021)01-0042-05
DOI :10.13705/j.issn.1671-6841.2020196
0㊀引言
大数据背景下，随着数据获取工具的迅速发展和数据存储技术的不断进步，数据库中存储的数据集的规模也越来越庞大，这给传统的数据挖掘技术带来了严峻而全新的挑战㊂众所周知，为数据样本确定类标签需要耗费一定的时间以及相应的技术支撑㊂而随着数据规模的日趋庞大，为所有数据样本确定类标签的代价也随之变得异常昂贵㊂这显然也是目前大数据背景下分类问题中面临的挑战之一㊂面对规模异常庞大的数据集，通常只能为其中一小部分确定类标签，而大量存在的是无标记的数据样本㊂为有效处理这类数据集，众多研究者引入了半监督学习机制来处理部分标记数据的学习任务[1
-
6]
㊂
特征选择是数据挖掘技术中一种常用的数据预处理技术，对给定数据集进行有效特征子集的选取，只保留对学习任务贡献较大的特征，可有效提高学习模型的泛化能力，降低过拟合以及计算耗时[7
-13]
㊂面对部分
标记数据集，半监督特征选择算法也引起了众多研究者的广泛关注，并取得了一定的研究成果㊂文献[14]
将有标记样本和无标记样本相结合度量特征的相关性，设计了基于图论的半监督处理机制㊂文献[15]同时基于无标记样本和有标记样本来构造基于数据的图结构，进行特征选择㊂文献[16]设计了基于多目标优化理论的半监督特征子集选取机制㊂文献[17]通过计算特征间相关性来构造特征的近邻，进行有效特征子集的选取㊂文献[18]将流形学习引入特征选择中，提出了基于流形正则化的半监督特征选择方法㊂此外，文献[19-20]基于粗糙集理论，定义了半监督意义下新的特征重要度的度量，并给出了相应的特征选择算法㊂文献[21]基于最大相关最小冗余的特征选择求解策略，分别基于有标记数据和无标记数据给
出了相关性和冗余性的计算公式，并给出了相应的半监督特征选择求解过程㊂在此基础上，为进一步充分利用数据库中大量无标记数据集，本文基于Relief-F 算法设计一种面向符号数据的半监督特征选择算法㊂
Relief-F 系列算法的主要特点是基于分析近邻样本对类别的区分能力来确定特征的权重，即特征重要
度㊂其核心思想是：一个优秀的特征应该使得同类的样本更加靠近，而使得不同类的样本更加分散㊂Relief-F
系列算法提出以来已经在许多算法和应用中被广泛使用㊂针对部分标记的符号数据，本文中首先引入了一种基于耦合学习的样本相似度度量，可更有效地度量符号型数据样本的相似性[22-23]
㊂在此基础上，将Relief-F
算法进行拓展用于处理部分标记数据㊂本文首先介绍了基于耦合学习的数据样本相似度，然后提出了基于Relief-F 的半监督特征选择算法，最
后为实验结果及分析㊂
㊀第1期
刘吉超，等：基于Relief-F 的半监督特征选择算法1㊀对象的耦合相似度
数据样本间的相似度依赖于样本对各个特征取值之间的相似度㊂对于符号型数据，由于数据取值的无序性，显然不能通过计算距离直接比较㊂一些研究者通过分析数据取值间的耦合特性，提出了基于耦合学习的符号取值相似度度量(coupled attribute similarity for objects,CASO )[20]㊂基于耦合的数据取值相似度既考虑
了同一特征内部特征取值之间的相似性(intra-coupled attribute value similarity,IaASV )，同时又考虑了其余特
征对当前特征取值相似性的贡献(inter-coupled attribute value similarity,IeASV )㊂该相似度主要通过分析属性
值的频率分布和特征间的依赖聚合度来确定最终的相似度度量[23]，具体介绍如下㊂
定义1㊀给定一个信息表S n ˑm ，则数据表中的对象u x ㊁u y 之间的对象耦合相似度CASO (u x ,u y )为
CASO (u x ,u y )=
ðm
j =1
δ
Ia j
(v x j ,v y j )㊃δIe j (v x j ,v y
j ,{V k }k ʂj ),
其中:δIa
j
为IaASV ;δIe j
为IeASV ;m 表示特征的个数;v x j ㊁v y
j 为在特征j 下u x ㊁u y 所对应的属性值㊂
定义2㊀给定一个信息表S n ˑm ，对于给定属性值v x j ㊁v y
j 的特征内耦合属性相似度为δIa
j
(v x j
,v y j
)=
G j ({v x j })㊃G j ({v y j })G j ({v x j })+
G j ({v y j })
+
G j ({v x j })㊃G j ({v y j })
,
其中:G j ({v x j })㊁G j ({v y j })为在特征j 下属性值等于v x j ㊁v y
j 的集合㊂
IaASV 是从属性值的频率分布的角度来形容同一特征下属性值之间的相似程度[23]㊂定义2考虑了在
同一特征内部属性值v x j ㊁v y j 之间的关系㊂但是实际数据中，同一特征下的不同取值之间的相似度不仅取决于
它们本身，还取决于它们所处的环境，即其余特征对它们相似度的影响㊂因此，在定义2的基础上，定义3给
出了A j 以外的特征A t (A t ʂA j )对A j 上取值v x j ㊁v y j 间相似度的度量㊂
定义3㊀给定一个信息表S n ˑm ，对于给定属性值v x j ㊁v y
j 的特征间耦合属性相似度为δIe
(v x j
,v y j
,{V k }k ʂj )=
ð
n
k =1,k ʂj
αk δj
k
(v x j ,v y
j ,V k ),δj k
(v x j ,v y
j ,V k )
=ðv k ɪɘ
min{P
k j
({v k }v x j ),P k j ({v k }v y j )},
P k j ({Vᶄk }
v j )=G k ({Vᶄk })ɘG j ({v j })
G j ({v j })
,
其中:αk 是特征A k (k ʂj )的权重参数,ðm k =1
αk =1;δj k
(v x j ,v y j ,V k )是属性值v x j ㊁v y
j 在特征A k (k ʂj )下的特征
间耦合相似度；在δj
k
(v x j ,v y j ,V k )的公式中v k 的取值为在特征A j 中取值为v x j ㊁v y
j 的集合与在特征A k (k ʂj )
中取值集合的交集;P k j ({v k }v x j )㊁P k j ({v k }v y j )表示的是在特征A j 的属性值为v x j ㊁v y
j 的情况下，特征
A k (k ʂj )取值为v k 的结果[22
-23]
㊂
2㊀基于Relief-F 的半监督特征选择算法
经典Relief-F 特征选择算法的核心思想是，首先从数据集中随机选择一个样本，然后分别从该样本的同类和不同类中均选择出k 个最近邻样本，通过分析该样本同其近邻间的距离(或相似度)来更新特征的权重㊂其更新权重的意义在于减去选定样本与其同类近邻在该特征上的差异，增加选定样本与其不同类近邻
在该特征上的差异㊂在此基础上重复抽取多个样本，上述过程重复迭代多次，最终每个特征得到一个平均权重㊂最后根据权重值的大小可对特征进行排序㊂
为更好地度量符号数据样本间的相似度，本节中引入定义1~3的耦合相似度(CASO )来求解给定样本的近邻，并在此基础上，将半监督学习机制引入经典Relief-F 算法中，对其进行拓展㊂具体的算法思想为：先从有标记数据中随机抽取数据样本s (假设s 的类别为y i )，然后从其余每一类y j (i ʂj )中选择一个s 的最近邻x j ；在所有未标记数据中计算并选取出s 和所有x j 的k 个最近邻样本；基于在无标记数据集中求解到的所
有近邻并结合Relief-F 算法更新特征的权重㊂该算法的具体算法流程介绍如下㊂
3
4
郑州大学学报(理学版)第53卷算法1㊀基于Relief-F的半监督特征选择算法(semi-supervised feature selection based on Relief-F,SFSR)㊂输入：训练集S=S1ɣS2，其中S1为有标记数据,S2为无标记数据，特征个数m，类别集C㊂
输出：特征的权重值w k(k=1,2, ,m)㊂
步骤1初始化特征权重w k=0,k=1,2, ,m㊂
步骤2循环执行步骤2.1~2.4M次㊂
㊀步骤2.1从有标记样本集S1中随机选择一个样本s,s的类别为c q(c qɪC)㊂
㊀步骤2.2从无标记样本集S2中，基于定义1求解s的d个近邻，标记为H q t(t=1,2, ,d)㊂
㊀步骤2.3在其余的每一类c pɪC(pʂq)中基于定义1求解样本s的一个最近邻样本x，并在无标记样本集中求解x的d个近邻，记为M p t(t=1,2, ,d)㊂
㊀步骤2.4基于公式(1)更新所有特征的权重
w k =w
k
-ðd t=1D(A k,s,H q t)Md+ðpʂq P(c p)
1-P(c p)
ðd t=1D(A k,s,M p t)Md,(1)
其中:D(A i,x,y)=
0,v x i=v y i
1,v x iʂv y i
{;P(c p)表示类别为c p的样本的概率㊂
步骤3返回结果w k(k=1,2, ,m)㊂
算法1对经典Relief-F算法的拓展主要有两个方面:1)引入基于耦合学习的相似度度量来计算给定样本的近邻;2)从无标记样本中寻给定样本的近邻，充分利用了无标记样本信息㊂而基于样本近邻来更新特征权重的公式(步骤2.4)仍是使用的经典Relief-F算法中的更新公式㊂
3㊀实验分析
为验证上述提出的基于Relief-F的半监督特征选择算法，选取了5组UCI数据集㊂实验程序所用语言为Python3.6，程序开发平台为Anaconda Spyder㊂程序所运行的计算机配置为:CPU Inter(R)Core TM i5-3230, 2.60GHz；内存为8GB；操作系统为Windows7㊂数据集的描述见表1㊂
表1㊀数据集描述
Table1㊀Data sets
数据集样本数特征数类别数
cancer68392
dermatology366336
backup-large3073519
tic-tac-toe95892
car172864
㊀㊀在实际情况中，大部分数据集中已标记的数据占比都比较小，因此在本实验中考虑了数据集中无标记数据占总数据集70%㊁80%㊁90%这三种情况㊂由于针对面向符号数据的半监督特征选择算法的研究还相对较少，实验中所选取的对比试验为前向半监督算法(FSFS)[24]㊂在此基础上，本节中选取了机器学习中常用的三个分类器logistic㊁支持向量机(SVM)㊁朴素贝叶斯(NBC)来进一步验证特征选择结果的有效性㊂表2~4分别给出了三种情况下由特征选择算法SFSR和FSFS对表1中5个数据集选择得到的特征个数和由选择结果诱导的分类精度的比较㊂其中N表示特征选择结果中特征的个数，分类精度表示由特
征选择结果分别在上述三个分类器上通过十折交叉验证得到分类精度，表中数值的前面部分表示十次分类正确率的均值，后面部分表示平均绝对误差㊂本节中使用的分类器和精度计算方法均集成在数据挖掘软件weka中㊂另外，表2~4中加粗的内容表示由不同特征选择算法得到的特征选择结果在相同分类器上得到的分类精度较高的值，例如表2数据集backup-large由本文算法得到的选择结果在分类器logistics和SVM上分类精度高于由算法FSFS的结果在这两个分类器上的精度，而在分类器NBC上的分类精度则低于算法FSFS的选择结果在该分类器上的精度㊂
44
㊀第1期
刘吉超，等：基于Relief-F 的半监督特征选择算法
表2㊀无标记数据为70%的情况下特征选择结果的分类精度比较
Table 2㊀The experimental results of classification accuracy on feature subsets with 70%unlabeled objects
数据集FSFS
SFSR
N logistic SVM
NBC N
logistic SVM
NBC cancer
40.9277ʃ0.2651
0.9277ʃ0.26510.9267ʃ0.2489
40.9383ʃ0.2344
0.9382ʃ0.26780.9427ʃ0.2365
dermatology 11
0.8169ʃ0.2109
0.8251ʃ0.3182
0.8251ʃ0.2063100.8688ʃ0.1779
0.8470ʃ0.3197
0.8743ʃ0.1780
backup-large
90.7752ʃ0.1338
0.6450ʃ0.2139
0.8111ʃ0.1221
80.8078ʃ0.1205
0.7134ʃ0.2138
0.8085ʃ0.1324
tic-tac-toe 80.7119ʃ0.4399
0.7077ʃ0.5406
0.7119ʃ0.4369
80.7119ʃ0.4399
0.7077ʃ0.5406
0.7119ʃ0.4369
car
40.6973ʃ0.3024
0.7002ʃ0.3580
0.7031ʃ0.2978
4
0.7338ʃ0.2889
0.7054ʃ0.3529
0.7292ʃ0.2865
表3㊀无标记数据为80%的情况下特征选择结果的分类精度比较
Table 3㊀The experimental results of classification accuracy on feature subsets with 80%unlabeled objects
数据集FSFS
SFSR
N logistic SVM
NBC N
logistic SVM
NBC cancer
40.9180ʃ0.2345
0.9151ʃ0.29140.9224ʃ0.2590
50.9465ʃ0.2539
0.9281ʃ0.28630.9340ʃ0.2886
dermatology 90.8552ʃ0.8980
0.8607ʃ0.3172
0.8579ʃ0.187580.8469ʃ0.1966
0.8716ʃ0.3152
0.8716ʃ0.1847
backup-large
90.7752ʃ0.1258
0.7134ʃ0.2137
0.7817ʃ0.1283
90.8078ʃ0.1169
0.7948ʃ0.2136
0.8241ʃ0.1235
tic-tac-toe 80.7139ʃ0.4429
0.7004ʃ0.5473
0.6931ʃ0.4400
80.7119ʃ0.4399
0.7077ʃ0.5406
0.7119ʃ0.4369
car
4
0.8299ʃ0.2402
0.8362ʃ0.3371
0.8356ʃ0.2341
5
0.8570ʃ0.2266
0.8611ʃ0.3321
0.8670ʃ0.2242
表4㊀无标记数据为90%的情况下特征选择结果的分类精度比较
Table 4㊀The experimental results of classification accuracy on feature subsets with 90%unlabeled objects
数据集FSFS
SFSR
N logistic SVM
NBC N
logistic SVM
NBC cancer
40.9283ʃ0.2270
0.9238ʃ0.27590.9195ʃ0.2514
50.9439ʃ0.2299
0.9312ʃ0.26230.9521ʃ0.2707
dermatology 90.8470ʃ0.1997
0.8639ʃ0.3186
0.8716ʃ0.180490.8525ʃ0.1920
0.8652ʃ0.3179
0.8443ʃ0.1908
backup-large
90.7133ʃ0.1516
0.6645ʃ0.2141
0.7394ʃ0.1374
100.7980ʃ0.1219
0.7231ʃ0.2138
0.7687ʃ0.1313
在常用的正则化计算方法中 属于tic-tac-toe 80.7140ʃ0.4406
0.7056ʃ0.5426
0.7046ʃ0.4377
80.7057ʃ0.4423
0.7098ʃ0.5387
0.7056ʃ0.4423
car
5
0.7899ʃ0.2634
0.7922ʃ0.3430
0.8090ʃ0.2499
5
0.8315ʃ0.2398
0.8391ʃ0.3356
0.8287ʃ0.2331
㊀㊀由表2~4的实验结果可得，本文所设计的基于Relief-F 的SFSR 算法在5个UCI 数据集上选择出的特征子集所得出的分类精度结果大部分都高于或持平于FSFS 算法所得出的结果㊂上述实验结果进一步验证了本文提出的基于Relief-F 的SFSR 算法的有效性㊂但是由于本文新算法在求解样本近邻过程中使用的相似度度量需要综合考虑特征取值在所有特征下的相似度，因此新算法的计算效率还有待进一步提高㊂下一步的研究工作会包括对算法效率的探索和分析㊂
4㊀结论
针对符号型部分标记数据集，本文通过引入一种基于耦合学习的数据样本相似度，设计了一种基于Relief-F 算法的半监督特征选择算法，算法中综合考虑了有标记数据和无标记数据来求解选定样本的近邻，进而更新特征的权重值㊂为有效验证提出新算法的可行性，实验分析中选取了5组UCI 数据集和3种常用
机器学习分类器来对新算法的性能进行验证，实验结果进一步验证了算法的有效性㊂该算法可以充分利
用无标记数据信息来更新特征权重值，所得出的特征子集也有效提高了分类器的分类精度㊂为后续的半监督数据挖掘技术提供了可以借鉴的新思路㊂
参考文献:
[1]㊀BENABDESLEM K,HINDAWI M.Efficient semi-supervised feature selection:constraint,relevance,and redundancy [J].
5
4
64
郑州大学学报(理学版)第53卷IEEE transactions on knowledge and data engineering,2014,26(5):1131-1143.
[2]㊀HUSSAIN A,CAMBRIA E.Semi-supervised learning for big social data analysis[J].Neurocomputing,2018,275:1662-
1673.
[3]㊀NAKATANI Y,ZHU K Y,UEHARA K.Semisupervised learning using feature selection based on maximum density subgraphs
[J].Systems and computers in Japan,2007,38(9):32-43.
[4]㊀FORESTIER G,WEMMERT C.Semi-supervised learning using multiple clusterings with limited labeled data[J].Information
sciences,2016,361/362:48-65.
[5]㊀陈潇，李逸薇，刘欢，等.基于网络表示的半监督问答文本情感分类方法[J].郑州大学学报(理学版),2020,52(2):
52-58.
CHEN X,LEE S,LIU H,et al.A semi-supervised sentiment classification method towards question-answering text based on network representation[J].Journal of Zhengzhou university(natural science edition),2020,52(2):52-58.
[6]㊀刘杰，刘欢，李寿山，等.基于双语对抗学习的半监督情感分类[J].郑州大学学报(理学版),2020,52(2):59-63.
LIU J,LIU H,LI S S,et al.Semi-supervised sentiment classification with bilingual adversarial learning[J].Journal of Zhengzhou university(natural science edition),2020,52(2):59-63.
[7]㊀岳文琦，张楠，童向荣，等.混合决策信息系统的模糊效用三支决策模型[J].郑州大学学报(理学版),2020,52(1):
24-32.
YUE W Q,ZHANG N,TONG X R,et al.Fuzzy utility three-way decisions model in hybrid decision information systems[J].
Journal of Zhengzhou university(natural science edition),2020,52(1):24-32.
[8]㊀解滨，董新玉，梁皓伟.基于三支动态阈值K-means聚类的入侵检测算法[J].郑州大学学报(理学版),2020,52(2):
64-70.
XIE B,DONG X Y,LIANG H W.An algorithm of intrusion detection based on three-way dynamic threshold K-means clustering [J].Journal of Zhengzhou university(natural science edition),2020,52(2):64-70.
[9]㊀DASH M,CHOI K,SCHEUERMANN P,et al.Feature selection for clustering-a filter solution[C]ʊIEEE International Confer-
ence on Data Mining.Maebashi City,2002:115-122.
[10]DASH M,LIU H.Feature selection for classification[J].Intelligent data analysis,1997,1(1/2/3/4):131-156.
[11]LIANG J Y,WANG F,DANG C Y,et al.A group incremental approach to feature selection applying rough set technique[J].
IEEE transactions on knowledge and data engineering,2014,26(2):294-308.
[12]WANG C Z,HU Q H,WANG X Z,et al.Feature selection based on neighborhood discrimination index[J].IEEE transactions
on neural networks and learning systems,2018,29(7):2986-2999.
[13]KOHAVI R,JOHN G H.Wrappers for feature subset selection[J].Artificial intelligence,1997,97(1/2):273-324.
[14]ZHAO Z,LIU H.Semi-supervised feature selection via spectral analysis[C]ʊProceedings of the2007SIAM International Con-
ference on Data Mining.Minneapolis,2007:641-646.
[15]NAKATANI Y,ZHU K Y,UEHARA K.Semisupervised learning using feature selection based on maximum density subgraphs
[J].Systems and computers in Japan,2007,38(9):32-43.
[16]HANDL J,KNOWLES J.Semi-supervised feature selection via multiobjective optimization[C]ʊThe IEEE International Joint
Conference on Neural Network.Vancouver,2006:3319-3326.
[17]IZUTANI A,UEHARA K.A modeling approach using multiple graphs for semi-supervised learning[C]ʊInternational Confer-
ence on Discovery Science.Budapest,2008:296-307.
[18]REN J T,QIU Z Y,FAN W,et al.Forward semi-supervised feature selection[C]ʊPacific-Asia Conference on Knowledge Dis-
covery and Data Mining.Osaka,2008:970-976.
[19]LIU K Y,YANG X B,YU H L,et al.Rough set based semi-supervised feature selection via ensemble selector[J].Knowl-
edge-based systems,2019,165:282-296.
[20]DAI J H,HU Q H,ZHANG J H,et al.Attribute selection for partially labeled categorical data by rough set approach[J].
IEEE transactions on cybernetics,2017,47(9):2460-2471.
[21]XU J,TANG B,HE H B,et al.Semisupervised feature selection based on relevance and redundancy criteria[J].IEEE trans-
actions on neural networks and learning systems,2017,28(9):1974-1984.
[22]WANG C,DONG X J,ZHOU F,et al.Coupled attribute similarity learning on categorical data[J].IEEE transactions on neu-
ral networks and learning systems,2015,26(4):781-797.
(下转第53页)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。