利用特征扰动的高维小样本数据子空间学习

曾海亮， 林耀进*， 唐 莉， 王晨曦

(1.闽南师范大学 计算机学院, 漳州 363000) (2.数据科学与智能应用福建省高等学校重点实验室, 漳州 363000)

在图像识别、文本分类、生物信息学、基因微阵列分析等研究领域,数据呈现出高维小样本特点,即特征空间呈现高维性,而样本数量过少．另外,该类数据往往伴随着属性值稀疏、噪声高、类别不平衡等问题．虽然特征空间较高的维数是获得问题准确描述的有力保障,但存在着大量冗余、不相关和噪声特征,易引发维数灾难,在分类学习过程中出现过拟合．因此,对高维小样本数据进行特征选择具有重要意义．

在高维小样本数据的特征选择过程中,不仅要选择出对分类学习性能有着极具提升作用的特征子集,而且应该注重特征选择结果的稳定性[1]．众所周知,高维小样本数据特征维数与样本数比例不协调，使得数据本身具有较强的敏感性,即训练样本在微小扰动情况下会产生不同的特征选择结果．为了同时兼具准确性和稳定性,许多专家提出了不同高维小样本数据的特征选择算法．文献[2]中提出一种基于迭代Lasso的信息基因选择方法，以获得基因数量少且分类能力较强的信息基因子集.文献[3]中解决了计算开销过大的问题，并在一定程度上解决了过拟合问题.从某种意义上讲在线流特征选择算法[4]、在线流标记特征选择[5]也是处理高维数据的一种方式.文献[6]中通过重构邻域粗糙集下近似算子，提出了基于特征和标记之间依赖关系的在线特征选择模型.文献[7]中定义一种新的具有自适应邻域的邻域粗糙集关系，并提出了一种基于这种关系的在线流特征选择方法．

在高维小样本数据中,样本蕴含的丰富信息使得特征空间具有超高维性,如基因微阵列数据中,特征有种族、血型、生长等信息;文本文档数据中,特征有样式、字体、颜色等信息;图像数据中,特征有位深、像素、饱和度等信息．这些丰富多样的特征提供了观察样本的不同视图,在基因数据中,代表种族视图的若干属性构成种族特征子空间,代表血型视图的若干属性构成血型特征子空间,代表生长视图的若干属性构成生长特征子空间,这些视图子空间构成对基因数据的完整刻画．因此,构建多个特征子空间对高维小样本数据进行分析不仅符合数据本身的特点,而且具有较好的准确率及鲁棒性．

在高维小样本数据的子空间[8]学习过程中,由于同一子空间的特征具有强相关性,而不同子空间的特征具有弱相关性．同时,子空间之间的差别构成了研究对象属性的多样性．为此,文中引入了特征扰动策略,提出了高维小样本数据的子空间学习算法．特征扰动策略是指在子空间学习过程中,通过判断特征间的相关性寻出归属不同子空间的特征．其中,子空间特征个数,即基数,取与样本个数相同，有利于化解高维小样本数据的高维性，以及降低因特征维数与样本数的比例不协调而引起的数据本身的敏感性．文中首先用邻域粗糙集[9]计算各属性重要度,选取属性重要度最高的一个属性作为基准属性,接着选取和基准属性相关性最大的前M个属性构成一个视图子空间;然后,再从余下的属性中选取属性重要度最高的属性作为基准属性,重复上述步骤,直至构造完所有子空间视图．对各个子空间利用邻域粗糙集进行特征选择,集成各个子空间选择的特征作为最终特征选择结果．实验结果证明所提模型能够较好地改善高维小样本数据的分类能力．

1 邻域粗糙集相关知识

定义1[6]给定实数空间上的非空有限集合U={x1,x2,…,xm},对于U上的任意对象xi,定义其δ-邻域为：

δ(xi)={x|x∈U,dist(x,xi)≤δ}

根据度量的性质,有:

(1)δ(xi)≠∅,因为xi∈δ(xi)

(2)xj∈δ(xi)⟹xi∈δ(xj)

定义2[10]给定样本集合U={x1,x2,…,xm},A为描述U的实数型特征集合,D为决策属性．如果A生成论域上的一簇邻域关系,则称NDT=〈U,A,D〉为一个邻域决策系统．

式中：

NBX={xi|δB(xi)⊆X,xi∈U}

定义3[10]给定一个邻域决策系统NDT=〈U,A,D〉,B⊆A,定义决策属性D对条件属性B的依赖性为：

γB(D)=Card(NBD)/Card(U)

定义4[10]给定邻域信息系统NDT=〈U,A,D〉,B⊆A,∀a∈B,如果γB-a(D)<γB(D),称a相对于B而言是必不可少的,否则,γB-a(D)=γB(D),称a是多余的．如果∀a∈B都是必不可少的,称B是独立的．如果γB-a(D)=γB(D),则表明从系统中去掉属性a,系统的正域没有发生改变,因此,各类的可区分性不变．

定义5[10]给定邻域决策系统NDT=〈U,A,D〉,称B⊆A是A的一个约简,如果B满足:

(1)∀a∈B,γB-a(D)<γB(D)

(2)γB(D)=γA(D)

该定义的条件(1)要求在一个约简中不存在多余的属性,所有的属性都应该是必不可少的;条件(2)要求约简不能降低系统的区分能力,约简应该与系统中全部条件属性具有相同的分辨能力．

定义6[10]给定邻域决策系统NDT=〈U,A,D〉,B⊆A,∀a∉B,属性a的重要度定义为：

sig(a,B,D)=γB∪a(D)-γB(D)

2 利用特征扰动的高维小样本数据子空间学习

为了降低高维小样本数据中特征空间维数与样本数之间极度不平衡带来的分类学习过程中的过拟合,文中主要利用子空间学习方法来进行高维小样本数据的特征选择．首先,利用邻域粗糙集方法依次度量各特征的重要度,选取特征重要度最高的一个特征作为基准特征,接着选取和基准特征最大相关的前M个特征构成一个视图子空间;其次,再从余下的特征中选取重要度最高的特征作为基准特征,重复上述步骤,直至构造完所有视图子空间；最后,对各个子空间利用邻域粗糙集进行特征选择,集成各个子空间的特征选择结果作为最终特征选择结果．

高维小样本数据的特征维数远远大于样本的个数,导致传统的分类学习方法失效．因此,通过学习多个特征子空间可避免过拟合现象,另外能有效地学习一组对样本具有强判别能力的特征子集．为了构建高维小样本数据的多个子空间,给定训练样本U={x1,x2,…,xm},描述样本的一组特征A={a1,a2,…,an},子空间属性个数取m,则子空间个数定义为k=「n/m⎤．

给定k个子空间,为了保证子空间内的属性具有相关性,子空间之间的属性表示描述样本的不同视角．文中将定义基准属性、基准属性子空间等．

定义7给定邻域决策系统NDT=〈U,A,D〉,∀b∈A,称属性b为基准属性,若属性b满足

定义8给定邻域决策系统NDT=〈U,A,D〉,B⊆A，b为基准属性,称以基准属性b为基准的属性子空间B为基准属性子空间,若∀a∈A-b,属性a满足：

sig(a,b,D)≤β

式中,β为使基准属性子空间里的属性个数为m的参数值．

根据定义7、8,可以构建以基准属性b为核心的子空间,反应了子空间内属性之间存在强依赖,表明了该子空间刻画了样本集的某一固有属性信息．另外,对于给定的高维小样本数据,可构建k个基准属性子空间，分别为S1={a11,a12,…,a1m},S2={a21,a22,…,a2m},…,Sk={ak1,ak2,…,akη},其中,a11,a21,…,ak1分别为基准属性子空间S1,S2,…,Sk中的基准属性．另外,基准属性子空间Sk中η=n-m×⎣n/m」．

通过定义8可以获得多个基准属性子空间,这些基准属性子空间从不同视角对样本进行刻画．但由于每个基准属性子空间内的属性存在冗余,因此需对每个基准属性子空间进行属性选择．

通过定义9,可获得每个基准属性空间的属性约简:

最后,集成基准属性空间的属性约简结果即为最终选择的属性．具体模型见图1.

众所周知,通过每个基准属性空间选择冗余性较小的属性,既可以保证得到在整个属性空间上对决策属性较重要的特征,又不会丢失对决策属性相对次要却关键的特征．

根据以上分析,利用特征扰动的高维小样本数据子空间学习，该算法具体描述如下:

算法:利用特征扰动的高维小样本数据子空间学习

输入:NDT=〈U,A,D〉

输出:约简red

步骤：

(1) ∀a∈A:计算邻域关系Na

(2)k=「n/m⎤/*计算子空间数k*/

(3) ∅→sel,∅→sub

(4) fori=1,2,…,k-1 do

(5) ∀b∈A-sel,sig(b,D)=γb(D)

(6)sig(b′,D)=maxsig(b,D)

(7)sel∪b′→sel,subi∪b′→subi

(8) forj=1,2,…,m-1 do

(9) ∀a∈A-sel,sig(a,b,D)=γb∪a(D)-γb(D)

(10)sig(a′,b,D)=minsig(a,b,D)

(11)sel∪a′→sel,subi∪a′→subi

2017年，为了得到程立生的支持，使其孩子顺利入学琼台师范学院附属幼儿园，肖某于2017年7月份在酒店包厢送给程立生现金1万元。

(12) end for

(13) end for

(14)A-sel→subk

/*余下的属性生成一个子空间*/

(15) fori=1,2,…,kdo

(16) ∅→redi/*初始化各子空间的已选特征*/

(17) ∀a∈subi-redi/*此处定义γø(D)=0*/

图1 利用特征扰动的高维小样本数据子空间学习Fig.1 Subspace learning of high dimensional small sample data using feature disturbance

(18)sig(a,redi,D)=γredi ∪a(D)-γredi(D)

(19)sig(a′,redi,D)=maxsig(a,redi,D)

(20) ifsig(a′,redi,D)>0 then

(21)redi∪a′→redi

(22) go to步骤(17)

(23) else

(24)red∪redi→red

(25) end if

(26) end for

(27) return red

分析该算法,可以看出其具有以下特点:

(1) 利用特征扰动划分基准属性子空间视图,在基准属性子空间视图中计算特征的重要度．此方法简单易行,计算复杂性较低,有效实现了对特征多样性的综合考虑．

(2) 通过计算特征空间重要度寻出基准属性,选取与基准属性高度相关的属性构建基准属性子空间视图,能有效增强特征选择的灵活性．每一个基准属性子空间视图刻画属性空间某种含义,各基准属性子空间相互独立,合在一起构成了对样本空间的完整刻画．可有效地识别出在整个条件属性空间下与决策层性弱相关却是隶属对应基准属性子空间内与决策属性强相关低冗余性的特征．

3 实验结果与分析

3.1 实验数据

为了验证SLFD算法的有效性,选取8个高维小样本数据集进行实验,其中数据集colon、leukemia、dlbcl、prostate、lung为二分类任务．数据集mll为三分类任务,数据集srbct为四分类任务,数据集car为十一分类任务,各数据集信息见表1．

表1 高维小样本数据集

3.2 实验设置

实验全部运行在3.10 GHz处理器、4 GB内存、Windows 7系统及Matlab 2013实验平台上．

为了验证算法的有效性,实验中分别与mRMR[11]、ICAP[12]、DISR[13]、MIFS[14]、CondRed[15]等经典特征选择算法，以及K-OFSD[6]、OFS-A3M[7]等在线特征选择算法进行对比．参考基于邻域粒化和粗糙逼近的数值属性约简[10]中的邻域阈值、邻域粗糙集邻域粒化阈值δ=0.1．基分类器采用RBF-SVM．实验结果采用5折交叉验证．由于mRMR、ICAP、DISR、MIFS、CondRed算法的特征选择结果以特征排序,为了比较公平,其选择的特征子集数量设置为SLFD得到的特征数．实验结果的评价指标采用分类精度、查准率、查全率和F-Score．

3.3 实验分析

表2～4分别给出了不同算法在数据集上平均查准率、平均查全率和平均F-Score值的结果．由表2可见：对平均查准率而言,在数据集prostate、lung、srbct、car上算法SLFD均优于对比算法;在三分类数据集mll上算法mRMR、DISR、MIFS优于SLFD;在数据集colon上算法mRMR和算法K-OFSD优于SLFD;在数据集leukemia上算法OFS-A3M优于SLFD;在数据集dlbcl上算法ICAP和算法OFS-A3M优于子集法算法SLFD．

由表3可见：对平均查全率而言,在数据集prostate、lung、srbct、car上算法SLFD均优于对比算法;在三分类数据集mll上算法mRMR、DISR、MIFS优于SLFD;在数据集colon上算法K-OFSD优于SLFD;在数据集leukemia上算法OFS-A3M与SLFD基本持平;在数据集dlbcl上算法ICAP和算法SLFD基本持平．

由表4可见：对平均F-Score值而言,算法SLFD在数据集prostate、lung、srbct、car上均优于对比算法;在三分类数据集mll上算法mRMR、DISR、MIFS优于SLFD;在数据集colon上算法K-OFSD优于SLFD;在数据集leukemia上算法OFS-A3M与SLFD基本持平;在数据集dlbcl上算法ICAP和算法SLFD基本持平．

表2 平均查准率

表3 平均查全率

表4 平均F-Score值

表5给出了特征选择后的平均分类精度和标准差,分类精度越高说明样本分类越准确,标准差越小说明分类稳定性越高,不难看出,在数据集dlbcl、prostate、lung、srbct、car上算法SLFD的平均分类精度均优于对比算法；在数据集dlbcl、lung、srbct上,算法SLFD的平均标准差均小于对比算法；在数据集prostate上算法K-OFSD的平均标准差小于SLFD；在十一分类数据集car上,算法K-OFSD的平均标准差与算法SLFD持平;在三分类数据集mll上算法mRMR、DISR、MIFS的平均分类精度优于SLFD,而在平均标准差方面,算法SLFD的平均标准差小于mRMR、DISR、MIFS,虽然算法SLFD的分类准确性不如算法mRMR、DISR、MIFS好,但其分类稳定性较高;在数据集colon上子集法算法K-OFSD的平均分类精度优于SLFD,而算法SLFD的平均标准差小于K-OFSD;在数据集leukemia上算法OFS-A3M的平均分类精度高于SLFD,并且平均标准差低于SLFD．

表5 平均分类精度和标准差

为了从整体上对比8种算法的分类性能随着特征选择的数目的变化情况．图1～4给出了在二分类数据集lung、四分类数据集srbct上，8种算法分别以查准率、查全率、F-Score和分类精度作为评价指标时其分类性能伴随着特征数目的变化情况．

图1 查准率指标下各算法分类性能Fig.1 Classification performance based on precision

从平行坐标图中可以直观地观察到,各个算法的查准率、查全率、F-Score都是随着特征数目的增加而逐渐提高并趋于稳定．对比算法mRMR、ICAP、DISR、MIFS、CondRed和算法K-OFSD、OFS-A3M,特征数目越多,算法SLFD的分类曲线浮动越小,稳定性最好．实验结果表明,利用特征扰动的高维小样本数据子空间学习算法SLFD的分类性能以及鲁棒性远优于对比算法．

图2 查全率指标下各算法分类性能Fig.2 Classification performance based on recall

图3 F-Score指标下各算法分类性能Fig.3 Classification performance based on F-Score

图4 分类精度指标下各算法分类性能Fig.4 Classification performance based on accuracy

4 结论

(1) 数据扰动法并不适用于小样本应用场景,如基因筛选、生物识别、癌症检测等,因为在小样本数据上,采用数据扰动法易造成过拟合．函数扰动法对小样本应用而言较为适用,其缺点在于难以根据数据集的特点选择合适的特征选择方法进行集成．

(2)特征扰动法并不存在以上问题.文中利用特征扰动对高维小样本数据进行子空间学习,通过特征与特征的相关性寻出归属不同子空间视图的特征,从而构建多个具有差异性的子空间视图,有助于化解高维小样本数据的高维性和降低高维小样本数据的敏感性．

(3)特征扰动法在高维小样本领域极具意义和研究价值,未来将致力于研究高维小样本数据,分析特征高维性、分类鲁棒性,进一步探索特征扰动的优势．