融合邻域判别指数的混合式特征选择算法

李校林,吴 腾,郭有庆

1(重庆邮电大学 通信与信息工程学院,重庆 400065)2(重庆邮电大学 通信新技术应用研究中心,重庆 400065)3(重庆信科设计有限公司,重庆 401121)

1 引 言

随着信息增长速度的加快,过多的数据给人类带来了极大的麻烦,然而,在巨大的数据体积中隐藏着大量的潜在价值和非常有用的信息[1].在统计学、信号处理、社交网络情感分析和可视化等领域中,机器学习方法得到普及,数据的特征维数的提升,使得算法复杂性呈指数级上升,另外高维特征中存在许多冗余信息和噪声信息,这些都会影响决策结果的精度,给信息处理工作带来了巨大的挑战[2].特征选择是分类和回归问题中一种数据降维的有效方法,能够去除特征中对决策结果无效的信息,并且保留数据之间的联系,用较少的特征子集使机器学习算法达到更高的分类精度[3].

目前,主流的特征选择方法分为过滤型(filter),封装型(wrapper)[4].过滤型方法首先利用判决指标对特征与目标集之间的关联性进行评价,然后进行排序留下前N个关联性强的特征作为最优特征子集,最后再经过训练器的学习,过滤型方法的特征选择过程与训练学习算法之间相互独立,因此这种算法有比较扎实的理论基础,计算速度快,在特征降维方面高效且扩展性强;缺点是所选特征子集没有经过具体学习算法的验证,预测或分类的准确率较低[5].相对于基于判决准则的过滤式方法,采用特征聚类的算法具有良好的效果.Zhou等人提出了一种高维数据集的无监督属性聚类算法(UACA),采用相似度系数MIC(Maximum Information)来评价每一对属性之间的相关性,在此基础上采用了最优k-mode聚类算法[6].封装型方法需要预设学习算法,在训练过程中以分类器的分类精度为判决准则进行特征选择[7],该方法需要对所有的特征子集进行训练,因此分类的准确率较高,但算法的效率过低.filter方法是当前特征选择的一个研究热点,得到了广泛的应用.互信息是一个随机变量中包含另一个随机变量的信息量,具有很好的鲁棒性.许多基于互信息的特征选择算法被相继提出,如MIFS、JMI、mRMR[8]、FCBF[9]等.这些算法都是利用互信息进行改进去除特征中的冗余特征,取得了更高的分类精度,但是当数据量和特征维数过高时,决策效率会变差.

以上各研究者提出的方法虽可在数据集上取得良好的实验效果,但只适用于特征单一的数据集,同时忽略了特征之间的相关性,特征选择时会误删掉重要的特征信息,难以处理高维特征的数据集.为了解决此问题,提出一种混合式特征选择算法NDI-RF,在特征过滤阶段,在互信息的基础上考虑特征之间的相关性,引入邻域判别指数判决条件,通过图论聚类[10]快速删除冗余特征,保留相关特征.在封装算法中,采用随机森林和后项序列搜索的方法对特征子集进行评估,并对随机森林特征选择的随机性进行改进,得到具有最高分类准确率的最优特征子集.

2 相关概念

2.1 邻域判别指数相关概念

给定一个决策表[U,A,D],其中U={x1,x2,…,xn}是决策表中所有样本对象的集合,A={a1,a2,…,an}是描述样本的一组特征集,D是一个决策属性集,该属性集将样本空间划分为r类,U/D={D1,D2,…,Dr}.样本空间中的相似关系可用相似矩阵RB表示,一般表示为RB=(rij)n×n,其中rij∈{0,1},i,j=1,2,…,n采用以下度量计算rij:

(1)

其中xl=[xl1,xl2,…,xls]T,l=i,j代表两个样本,B为属性子集且属性维数为s,两个样本的距离公式为:

(2)

阈值ε为邻域半径,用来控制样本的相似度.另外,RB有两个重要的性质:

1)自反性:∀x∈U,(x,x)∈RB

定义1.给定一个决策表U,A,D,其中U={x1,x2,…,xn},B⊆A,ε为邻域半径,是特征子集B的邻域相似关系,则B的邻域判别指数[11]定义为:

(3)

1)如果ε1≤ε2,则Hε1(B)≥Hε2(B).

2)如果B1⊆B2,则Hε(B1)≤Hε(B2).

(4)

联合判别指数代表联合特征子集的识别能力,它随着新的特征集的增加而增加,但不具备单调性,Hε(B1,B2)≥Hε(B1),Hε(B1,B2)≥Hε(B1)当且仅当B1⊆B2时,有Hε(B1,B2)=Hε(B2).

定义3.将在B2条件下B1的条件判别指数定义为:

(5)

并且Hε(B1|B2)≥0.仅当B1⊆B2时,Hε(B1|B2)=0.

条件判别指数是在已知一个特征子集后,通过引入一个新的特征子集来增加判别信息,从而增加特征的识别能力.

定义4.特征子集B1,B2的相互判别指数定义为:

(6)

相互判别指数有如公式(7)所示的性质,其与邻域判别指数和条件判别指数的关系如图1所示.

Iε(B1;B2)=Iε(B2;B1)Iε(B1;B2)=Hε(B1)+Hε(B2)-Hε(B1,B2)

(7)

Iε(B1;B2)=Hε(B1)-Hε(B1|B2)=Hε(B2)-Hε(B2|B1)

图1 判别指标关系图Fig.1 Discriminant indicator relationship diagram

2.2 特征选择的重要依据

上述所提出的邻域判别指标可以用来衡量特征子集的区分能力.根据条件判别指数的定义,在所选择的特征子集中加入一个新的特征可以增加或降低条件判别指数,条件判别指数Hε(D|B)的减小反映出新特征子集的区分能力增加.因此,特征的重要性定义如下.

定义5.给定一个决策集[U,A,D],B⊆A,a∈A-B,特征a相对于B和D的重要程度定义为:

SI(a,B,D)=Hε(D|B)-Hε(D|B∪{a})

(8)

当B=Ø时,Hε(D|B)=Hε(D).特征a的重要程度取决于将a加到特征子集B后判别信息的增量.

假设特征b∈B,如果Iε(D;B)≤Iε(D;B-{b}),则b在B中成为冗余的.如果B中的任何属性b相对于D是不可缺少的,则称b为依赖项.如果B满足以下条件,则B称为A相对于D的约简:

1)Iε(D;B)≥Iε(D;A)

2)Iε(D;B-{b})

(9)

3 混合式特征选择算法

3.1 基于邻域判别指数的特征过滤算法(NDI)

本文在考虑特征之间的交互作用的基础上,提出采用邻域判别指数作为filter模型的特征选择判别条件,引入图论聚类的思想的快速选择算法,主要分为两步:

1)利用图论聚类的方法对特征进行聚类;

2)从每个目标类中选择与目标类密切相关的最具代表性的特征集群形成约简特征子集.考虑到大数据环境下特征维数多,为了保证特征维数约简的效率,分别在第一步和第二步中采用了最小生成树(MST)方法和冗余窗口[12]来提高算法的效率.NDI特征过滤算法的具体步骤如下:

1)构造完全图.将初始特征集A={a1,a2,…,an}中的每个特征作为一个单独的特征子集Bi,i=1,2,…,n.计算每个特征子集的邻域判别指数Hε(Bi)作为完全图中每个结点的权值;计算相互判别指数Iε(Bi;Bj)作为完全图中每一条边的权值.

2)生成最小生成树.对于高维数据集生成的完全图过于密集且各条边交织在一起,对后续图的剪枝操作带来困难.本文采用Prim算法生成最小生成树[13],使得在包含所有结点的情况下让边的权值的总和达到最小.

3)树的剪枝.根据相互判别指数的理论可知0≤Iε(Bi;Bj)≤logn,将最小生成树中的边的权值满足Iε(Bi;Bj)<δ的边去掉,就能保证剩余的边的两个特征集之间有一定的相关性,形成一个特征类簇,具体思想如图2所示.其中,δ的值要根据特征维数n具体的设定.

4)代表特征的选择.设约简特征子集S=Ø,对于每一个剪枝后的特征类簇,计算每个结点与决策属性集之间D的相互判别指数Iε(D;Bi),选择使Iε(D;Bi)最大的特征Bi作为每个簇的代表特征,每个代表特征能覆盖对应特征类簇的大部分信息.其余的特征作为剩余特征.

5)去除冗余,生成约简特征集.根据定义5中的SI(a,B,D)判断剩余的每个特征是否为对应特征类簇的冗余项或依赖项.若是冗余项,则从特征子集中剔除,若是依赖项,则加入约简特征子集S中.

图2 图论聚类思想Fig.2 Graph theory clustering

NDI算法的伪代码如下：

输入:[U,A,D]-决策表;δ-设定的阈值;ε-邻域半径

输出:S-约简特征子集

//Part1:构造完全图G

1.fori=1 tondo

2.ai∈AasBithenB=B∪{Bi};

3.G=NULL

4.for each pair of features {Bi,Bj}∈Bdo

5. B-Correlation=Iε(Bi;Bj)

6. AddBiand/orBjtoGwith B-Correlation as the weight of the corresponding edge;

//Part2:利用Prim 算法构造最小生成树

7.minSpanTree=Prim(G);

8.Forest= minSpanTree

//Part3:剪枝

9.for each edgeBij∈Forestdo

10. ifIε(Bi;Bj)<δthenForest=Forest-Bij

//Part4:代表特征的选择

11.for each treeTi∈Forestdo

//Part5:生成约简特征集S

13.S=φ

18.returnS.

为了降低特征选择算法中去除冗余,采用冗余窗口机制.假设步骤4)生成的代表特征为F0,剩余特征为Fi(i=1,2,…,m).首先将代表特征F0压入约简特征子集S中,并将计数器设置为1,然后计算特征F1是否为依赖项,若是,将F1压入S中,计数器置为2.下一步将计算F2和F3的依赖程度.冗余窗口机制可以根据S现有特征的个数并行计算剩余特征的依赖程度,在保证了系统的准确性的同时,提高特征维数约简的效率.

3.2 特征选择算法

针对某些特征之间往往高度相关的数据集,诸如医学数据、网络数据、地理信息等,利用过滤式特征选择方法并不能保证选择出最优的特征子集.基于wrapper特征选择算法直接用所选的特征子集来训练分类器,根据分类器在数据集上的表现性能来评价特征子集的优劣.在特征选择过程中,搜索策略和评价准则是最重要的因素.序列搜索能够获得较好结果的同时降低时间开销,但是序列搜索基于贪心思想[14],易于收敛于局部最优值.为了解决这类问题,采用随机森林(RF)作为封装器[15],与序列后项搜索(SBS)相结合的方式进行进一步的精细化特征选择.

首先根据特征重要性度量值对特征进行降序排序,然后对特征进行后项搜索,每次迭代删除最不重要的几个特征进行,逐次迭代并且计算每次迭代的分类精度,获取分类精度最高的那次迭代所对应的特征集作为最优的特征选取结果.在每次迭代中采用10折交叉验证来计算分类准确率.具体的算法步骤如下:

1)数据初始化.将原始数据集随机分为10份,其中1份作为测试数据集,其他9份作为训练数据集.

2)构建RF分类器.构建多棵决策树组成随机森林对新数据进行分类,分类结果由最终每棵树的投票结果决定[16].为了解决传统随机森林算法在构建决策树的过程中选择特征的随机性问题所造成的分类准确率两级分化严重以及没有充分考虑特征之间的关联性.对特征排序和选择过程进行改进,具体步骤为:

①采用Bootstrap方法在训练数据集中随机抽样,获得n个样本;

③采用等比规则依次从特征子集中选取特征权重高的特征和权重低的特征组成新的特征子集.构造决策树,组成随机森林,计算每个特征的重要性值,对数据集进行分类并计算分类准确率.

3)采用10折交叉验证计算平均分类准确率.重复10次步骤2),计算10次分类的平均准确率,并记录对应的特征子集.

4)特征删除.根据特征重要性度量值对特征进行降序排序,删除最不重要的l个特征,形成新的特征子集.

5)最优特征子集的选取.重复步骤2)～步骤4),最终选择使分类准确率最高的特征子集作为最优特征子集.

算法的伪代码如下:

SBS-RF算法:

输入:约简特征子集S,其中有N个特征,原始数据集U;

输出:验证集上的最大分类正确率TGMaxAcc及其对应的特征子集TGSort;

1.初始化:读入原始数据集,设置TGMaxAcc=0,TGSort=null;

2.fort=1,2,…,|N/l|

3.将原始数据集随机分成10份

4.设置局部的平均分类准确率MeanAcc=0

5.fori=1,2,…,10

6.初始化10次交叉验证中的每次迭代的正确率为Acc=0

7.在数据集T上建立RF分类器

8.在验证集上进行分类

9.比较分类结果,计算分类准确率Acc

10.计算平均分类准确率MeanAcc=MeanAcc+Acc/10

11.对特征的重要性度量进行降序排序

12.if(TGMaxAcc≤MeanAcc)

thenTGMaxAcc=MeanAcc

13.去掉特征重要性排序中较低的l个特征,得到新的特征集T

14.end for.

15.end for.

4 实验结果与分析

为了验证本文特征选择算法的有效性和可行性,做了两方面的对比试验.1)分类准确率方面,比较原始特征集、mRMR、FAST、NEREA和本文提出的NDI-RF算法所选择出的最优特征子集在多个分类器上的分类精度,以验证本文算法的有效性;2)比较了多种算法在各类数据集上所选择的最优特征子集的平均大小.在进行分类性能评估时采用Na?ve Bayes分类器、SVM分类器、KNN分类器.实验硬件环境为Windows 10系统,Intel core i7-6500U处理器,16G内存.实验软件环境为Matlab 2016b,Weka分类软件.

表1 数据表信息
Table 1 Data sheet information

ID名称特征数类别数样本数1wine1331782zoo1771013Ionosphere3423514sonar6022085realdisp120314196elephant232213917tr12.wc313858058fqs-nowe3202256

本文所用实验数据集下载于UCI机器学习数据库,各个数据集的详细信息如表1所示.其中数据集1～4为低维小样本数据,数据集5～8为高维大样本数据.

4.1 邻域半径ε对特征选择结果的影响

由于实验过程中需要确定邻域半径ε的大小对最优特征子集的影响,本文采用SVM分类器来确定最优特征子集的邻域半径ε.以数据集wine,realdisp,fqs-nowe为例,首先将数据集属性标准化为[0,1]区间,通过在[0,1]内调整ε的大小来确定对应的最优特征子集和最佳分类精度,设置ε的变化步长为0.05.图3-图5反映了NDI-RF算法所选的最优特征子集大小和分类精度随ε的变化趋势.

实验结果表明,邻域半径ε的选择对NDI-RF算法的性能有很大影响,随着ε取值变化的不同,分类准确率和最优特征子集的大小都会发生变化.从图3-图5可以得出数据集1,数据集5,数据集8获得最佳分类性能所对应的ε值分别为0.6,0.2,0.25.按照此方法,在保证分类准确率的前提下选择最优特征子集较小的ε为最优邻域半径的取值.经过实验,数据集2,数据集3,数据集4,数据集6,数据集7所获得的最优邻域半径ε分别为0.45,0.3,0.6,0.55,0.3.

图3 特征子集大小和分类准确率变化趋势(wine)Fig.3 Feature subset size and classification accuracy trend(wine)

4.2 NDI-RF算法的性能

为了比较本文提出的混合式算法NDI-RF的分类准确率,分别比较了原始特征集、mRMR、FAST、NEREA等特征选择算法选择出来的最优特征集在三种分类器上的分类准确率,在使用KNN分类器进行分类时取K值为3.从表2-表4可以看出NDI-RF算法在平均分类准确率上明显优于其他算法.在低维数据集中NEREA算法的分类精度与NDI-RF相近,但在高维数据集中NDI-RF算法的性能要明显优于其他的特征选择算法,这是由于NDI-RF算法在特征处理的过程中采用邻域信息考虑了特征之间的相关性,通过图论聚类剔除冗余特征,保留了特征与目标类之间的关联,在训练封装器阶段,采用特征权重和等比分配机制克服了随机森林分类不平稳的问题.

图4 特征子集大小和分类准确率变化趋势(realdisp)Fig.4 Feature subset size and classification accuracy trend(realdisp)

图5 特征子集大小和分类准确率变化趋势(fqs-nowe)Fig.5 Feature subset size and classification accuracy trend(fqs-nowe)

表2 各算法在Naïve Bayes分类器上分类准确率对比(%)
Table 2 Comparison of classification accuracy of algorithms on Naïve Bayes classifier(%)

ID原始特征mRMRFASTNEREANDI-RF194.3296.5896.0997.3297.05289.6087.2193.8894.5694.86378.2385.4090.5289.2190.15482.2681.9488.7592.2091.92580.0488.5689.6891.2493.02675.3482.9893.5492.7093.84772.2784.8879.9380.2088.42870.5686.2590.5688.6595.64平均值80.3386.7290.3690.7693.11

在评价NDI-RF算法选择的最有特征子集大小方面,采用十倍交叉验证法统计每个算法所选特征子集的平均大小,如图6和图7所示.从图中可以看出,NDI-RF算法在低维数据集上所选择的特征子集大小与其他算法相差不大,在wine数据集上略高于NEREA算法,在Ionosphere数据集上略高于FAST算法.在高维特征的选择上,NDI-RF算法均小于其他算法所选的特征子集大小,能够有效的降低特征维数,体现了NDI-RF算法处理高维数据的优越性.

表3 各算法在SVM分类器上分类准确率对比(%)
Table 3 Comparison of classification accuracy of algorithms on SVM(%)

ID原始特征mRMRFASTNEREANDI-RF190.5094.5894.0996.3298.25277.3088.2490.3292.5695.70380.5388.4094.5291.4193.52478.2691.9492.7591.2094.95576.0485.5689.6489.2490.02678.6490.4092.6494.5695.65776.4585.4589.9390.2096.42870.5682.4589.1294.6593.64平均值78.5388.3791.6292.5194.76

图6 低维数据集上所选择的特征子集平均大小Fig.6 Average size of feature subsets selected on low-dimensional data sets

图7 高维数据集上所选择的特征子集平均大小Fig.7 Average size of feature subsets selected on high-dimensional data sets

表4 各算法在3NN分类器上分类准确率对比(%)Table 4 Comparison of classification accuracy of algorithms on 3NN(%)

5 结束语

特征选择是解决分类和回归问题中的一种重要的数据预处理技术.目前大部分特征选择方法仅仅是删除冗余和对决策结果无关的属性信息,缺乏对特征之间相关性的考虑,没有进一步的精细化特征子集的性能.为了解决此问题,提出一种融合图论聚类方法和随机森林选择相结合的混合式特征选择算法.在聚类过程中采用邻域判别指数来确定特征之间的相关性,保留相关特征,剔除冗余特征.在训练封装器阶段,采用随机森林和后项序列搜索方法平衡算法的收敛值,对所选特征子集的具体分类性能进行准确评估,最终选择最高分类准确率所对应的特征子集为本次选择的最优特征子集.最终在多个UCI 数据集的实验结果验证了本文算法的有效性,在低维数据和高维数据中都获得了较高的分类准确率,在最优特征子集的选择方面,NDI-RF算法体现出更好的性能.