孟田田 周水生 田昕潤(rùn)

MENG Tiantian1, ZHOU Shuisheng1, TIAN Xinrun1

近年來(lái),隨著信息技術(shù)的高速發(fā)展,大量的數(shù)據(jù)出現(xiàn)在實(shí)際生活中,增長(zhǎng)速度迅猛.大規(guī)模的數(shù)據(jù)為機(jī)器學(xué)習(xí)[1]、圖像處理[2]、模式識(shí)別[3]等領(lǐng)域提供豐富的信息.然而,高維數(shù)據(jù)不可避免地包含冗余信息,這可能導(dǎo)致機(jī)器學(xué)習(xí)算法過(guò)擬合,甚至產(chǎn)生“維數(shù)災(zāi)難”.如何處理這些大規(guī)模數(shù)據(jù)也成為實(shí)際應(yīng)用中的一大挑戰(zhàn).為了避免維數(shù)災(zāi)難,挖掘數(shù)據(jù)中的有效信息,降維作為數(shù)據(jù)預(yù)處理的一種重要手段[4],受到學(xué)者們?cè)絹?lái)越多的關(guān)注.

降維主要有兩種方式: 特征選擇[5-6]和特征提取[7-8].特征提取是對(duì)原始特征空間進(jìn)行映射或變換,得到原始特征線性組合或非線性組合生成的一組特征.與特征提取不同,特征選擇是在原始特征空間中進(jìn)行,通過(guò)某種評(píng)價(jià)策略,從原始特征集上選擇最具有代表性的特征子集.因此,相比特征提取,特征選擇保留數(shù)據(jù)的原始物理意義,具有更強(qiáng)的可解釋性.

根據(jù)數(shù)據(jù)標(biāo)簽的使用情況,特征選擇可分為3類:監(jiān)督特征選擇[9-10]、半監(jiān)督特征選擇[11]和無(wú)監(jiān)督特征選擇[12].在實(shí)際生活中,數(shù)據(jù)標(biāo)簽的獲取成本很高,因此無(wú)監(jiān)督特征選擇具有重要的研究意義和研究?jī)r(jià)值.

根據(jù)評(píng)價(jià)策略的不同,特征選擇也可分為:過(guò)濾式特征選擇[13-14]、包裹式特征選擇[15]和嵌入式特征選擇[16-17].過(guò)濾式特征選擇先對(duì)原始特征進(jìn)行“過(guò)濾”,再將過(guò)濾后的特征用于后續(xù)的學(xué)習(xí)任務(wù).包裹式特征選擇把最終使用的學(xué)習(xí)器的性能作為特征子集的評(píng)價(jià)標(biāo)準(zhǔn),由于計(jì)算成本較高,不適用于大規(guī)模數(shù)據(jù)集.嵌入式特征選擇結(jié)合過(guò)濾式特征選擇與包裹式特征選擇的優(yōu)點(diǎn),將特征選擇過(guò)程嵌入模型構(gòu)建中,使選擇的特征可提高算法的性能.

由于局部結(jié)構(gòu)在流形學(xué)習(xí)中具有良好性能,可獲取數(shù)據(jù)的分布流形信息,選擇更好地保持?jǐn)?shù)據(jù)流形結(jié)構(gòu)的特征,因此流形學(xué)習(xí)越來(lái)越多地引用至嵌入式無(wú)監(jiān)督特征選擇方法.Cai等[18]提出MCFS(Multi-cluster Feature Selection),通過(guò)譜分析獲取局部流形結(jié)構(gòu),再利用l1范數(shù)稀疏約束選擇特征.Yang等[19]提出UDFS(Unsupervised Discriminative Feature Selection),將判別分析和投影矩陣的結(jié)構(gòu)稀疏l2,1范數(shù)最小化融合到一個(gè)聯(lián)合框架，進(jìn)行無(wú)監(jiān)督特征選擇.

此外,由于譜分析理論可提供豐富的流形結(jié)構(gòu)信息,并且數(shù)據(jù)結(jié)構(gòu)通常以圖的形式捕獲,因此基于圖的特征選擇方法吸引學(xué)者們的關(guān)注.Shang等[20]在子空間學(xué)習(xí)的特征選擇框架的基礎(chǔ)上,引入圖正則化的思想,在特征空間上構(gòu)造特征映射,保留特征流形上的幾何結(jié)構(gòu)信息.Nie等[21]提出SOGFS(Structured Optimal Graph Feature Selection),將相似性矩陣構(gòu)造和特征選擇過(guò)程構(gòu)建到同一框架中,同時(shí)進(jìn)行局部結(jié)構(gòu)學(xué)習(xí)和特征選擇.Li 等[22]提出GURM(Generalized Uncorrelated Regression Model),加入基于最大熵原理的圖正則化項(xiàng).Zhang等[23]提出EGCFS(Unsupervised Feature Selection via Adap-tive Graph Learning and Constraint),通過(guò)自適應(yīng)圖學(xué)習(xí)方法,將相似矩陣的構(gòu)造嵌入優(yōu)化過(guò)程中,將類間散點(diǎn)矩陣最大化的思想和自適應(yīng)圖結(jié)構(gòu)集成到一個(gè)統(tǒng)一的框架中.

由于稀疏性是真實(shí)世界數(shù)據(jù)的固有屬性,因此稀疏學(xué)習(xí)是基于圖的無(wú)監(jiān)督特征選擇的常用方法之一.許多特征選擇方法應(yīng)用正則化項(xiàng)實(shí)現(xiàn)稀疏學(xué)習(xí),如l1范數(shù)、l2,0范數(shù)、l2,1范數(shù)等.在特征選擇任務(wù)中,矩陣的l2,0范數(shù)可約束矩陣的非零行個(gè)數(shù),恰好為選擇特征的個(gè)數(shù),因此顯然是特征選擇的最佳選擇.由于l2,0范數(shù)的非凸性,優(yōu)化問(wèn)題是個(gè)NP難題.在現(xiàn)有的特征選擇研究中,大部分考慮矩陣的l2,1范數(shù)實(shí)現(xiàn)稀疏性.通過(guò)l2,1范數(shù)正則化進(jìn)行特征選擇,需要對(duì)所有特征評(píng)分、排序,逐個(gè)選擇評(píng)分最高的特征,未考慮特征之間的相關(guān)性.由于l2,0范數(shù)約束正則化參數(shù)為選擇特征的個(gè)數(shù),在學(xué)習(xí)過(guò)程中動(dòng)態(tài)選擇一組最好的特征,并且不需要花費(fèi)時(shí)間進(jìn)行正則化參數(shù)的調(diào)節(jié).因此,學(xué)者們針對(duì)求解l2,0范數(shù)約束的特征選擇問(wèn)題進(jìn)行研究.Cai等[24]引入松弛變量,通過(guò)增廣拉格朗日函數(shù)進(jìn)行優(yōu)化.Du等[25]提出啟發(fā)式更新過(guò)程,在每次迭代中貪婪搜索最優(yōu)解.Nie等[26]采用與文獻(xiàn)[27]類似的方法,通過(guò)投影矩陣的滿秩分解,將l2,0約束問(wèn)題轉(zhuǎn)換為矩陣跡的優(yōu)化問(wèn)題進(jìn)行求解.

盡管上述方法都是對(duì)l2,0范數(shù)特征選擇問(wèn)題進(jìn)行求解,但在實(shí)際優(yōu)化過(guò)程中,仍需要通過(guò)某種方式排序選擇特征,這意味著這些方法依然是l2,1范數(shù)的變體,沒有從根本上解決l2,1范數(shù)正則化存在的問(wèn)題.為此,本文提出解決l2,0范數(shù)組稀疏的特征選擇方法,即基于l2,0范數(shù)稀疏性和模糊相似性的圖優(yōu)化無(wú)監(jiān)督組特征選擇方法(Unsupervised Group Feature Selection Method for Graph Optimization Based onl2,0-norm Sparsity and Fuzzy Similarity, F-SUGFS).引入0-1特征選擇向量,將l2,0范數(shù)約束轉(zhuǎn)換為特征選擇向量的0-1整數(shù)約束,并利用l2-box將離散的0-1整數(shù)約束轉(zhuǎn)化為2個(gè)連續(xù)約束,通過(guò)交替方向乘子法(Alternating Direction Method of Mul-tipliers, ADMM)進(jìn)行求解,動(dòng)態(tài)選擇一組最優(yōu)的特征,實(shí)現(xiàn)組特征選擇.最后,引入模糊相似因子,進(jìn)一步擴(kuò)展方法.在多個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證本文方法的有效性.

1 相關(guān)工作

對(duì)于矩陣X∈Rd×n,XT表示矩陣的轉(zhuǎn)置，tr(X)表示矩陣的跡，rank(X)表示矩陣的秩.X的l2,0范數(shù)定義為

其中a=0時(shí)‖a‖0=0,否則‖a‖0=1.X的l2,1范數(shù)定義為

對(duì)于向量r∈Rd×1，r的l2范數(shù)定義為

diag(r)表示對(duì)角矩陣,對(duì)角元素為向量r的元素.1d表示d×1維列向量,元素全為1.

1.1 相似性圖學(xué)習(xí)

(1)

定理1[28]拉普拉斯矩陣LS的特征值0的重?cái)?shù)等于具有相似性矩陣S的圖中連通分量的個(gè)數(shù).

在將數(shù)據(jù)劃分為c簇的聚類任務(wù)中,理想的鄰居分配是相似圖的連通成分恰好為聚類數(shù)c.根據(jù)定理1,約束拉普拉斯矩陣LS的秩

rank(LS)=n-c,

其中

度矩陣D為對(duì)角矩陣,對(duì)角線元素

令σ1,σ2,…,σc為拉普拉斯矩陣最小的c個(gè)特征值,則rank(LS)=n-c等價(jià)于

根據(jù)文獻(xiàn)[29]:

具有c個(gè)連通分量的相似圖構(gòu)造如下:

如圖1所示,使用一個(gè)聚類數(shù)為3的數(shù)據(jù)集顯示自適應(yīng)概率近鄰相似圖和具有精確聯(lián)通分量的相似圖之間的差異.若Sij>0,連接數(shù)據(jù)點(diǎn)xi和它的近鄰xj.由(a)構(gòu)造的相似圖互相連通,只有1個(gè)連通分量,由(b)構(gòu)造的相似圖互不連通,有3個(gè)連通分量,恰好為該數(shù)據(jù)集的聚類數(shù),因此具有精確連通分量的相似性矩陣可學(xué)習(xí)準(zhǔn)確的數(shù)據(jù)結(jié)構(gòu)信息.

(a)自適應(yīng)概率近鄰相似圖

1.2 基于稀疏學(xué)習(xí)的無(wú)監(jiān)督特征選擇

給定數(shù)據(jù)矩陣

X=[x1,x2,…,xn]∈Rd×n,

xi∈Rd×1為第i個(gè)樣本,d為原始特征維數(shù).X還可表示為

X=[f1,f2,…,fd]T,

fi∈Rn×1為第i個(gè)特征,n為樣本點(diǎn)的個(gè)數(shù).無(wú)監(jiān)督特征選擇的目標(biāo)為在不利用標(biāo)簽信息的情況下,從原始數(shù)據(jù)中選擇最具有代表性的k個(gè)特征子集,k為選擇特征的個(gè)數(shù),k?d.

根據(jù)流形學(xué)習(xí)理論,高維數(shù)據(jù)中的信息可由低維流形表示.投影矩陣

W=[w1,w2,…,wd]T∈Rd×m,

將數(shù)據(jù)點(diǎn)投影到低維空間,即

對(duì)于特征選擇任務(wù),W的第i行wi衡量第i個(gè)特征的重要性.當(dāng)

‖wi‖≠0

時(shí),選擇第i個(gè)特征fi,當(dāng)

‖wi‖=0

時(shí),舍棄第i個(gè)特征fi.若選擇k個(gè)特征,則理想情況為W恰好有k個(gè)非零行,即

‖W‖2,0=k,

因此選擇精確個(gè)數(shù)的特征選擇任務(wù)即為求解

(2)

其中，g(·)的目標(biāo)是學(xué)習(xí)一個(gè)投影矩陣W,與原始數(shù)據(jù)矩陣X以最佳線性組合近似低維流形,從而選擇更好地保持?jǐn)?shù)據(jù)流行結(jié)構(gòu)的特征.

由于非凸非光滑性，難以求解l2,0范數(shù)優(yōu)化問(wèn)題,因此大部分研究使用W的l2,1正則化項(xiàng)代替W的l2,0范數(shù)約束,即

基于l2,1范數(shù)正則化模型求解的投影矩陣W不同于l2,0范數(shù)約束直接選擇W的非零行對(duì)應(yīng)的特征,而是通過(guò)‖wi‖2的大小衡量特征的重要性,排序選擇最大的‖wi‖2對(duì)應(yīng)的特征,未考慮特征的相關(guān)性,單個(gè)選擇最優(yōu)的特征.此外,由于l2,1范數(shù)正則化問(wèn)題中的正則化參數(shù)λ無(wú)明確的含義,需要花費(fèi)時(shí)間對(duì)其進(jìn)行調(diào)優(yōu),而l2,0范數(shù)約束的參數(shù)k具有明確意義,即選擇特征的數(shù)量,因此不需要進(jìn)行參數(shù)的調(diào)節(jié).

由于l2,0范數(shù)約束的上述優(yōu)勢(shì),學(xué)者們現(xiàn)已提出一些解決l2,0范數(shù)約束模型[24-27].實(shí)際上,模型仍類似l2,1范數(shù)，通過(guò)某種排序選擇特征,而沒有實(shí)現(xiàn)組特征選擇.而本文提出將問(wèn)題(2)轉(zhuǎn)化為0-1整數(shù)約束,直接選擇得分為1對(duì)應(yīng)特征的方法,在優(yōu)化過(guò)程中動(dòng)態(tài)選擇一組最優(yōu)的特征.

在真實(shí)數(shù)據(jù)集MSRA25上利用l2,0范數(shù)和l2,1范數(shù)進(jìn)行特征選擇的區(qū)別如圖2所示.2種方法均在數(shù)據(jù)集上選擇10個(gè)特征.橫坐標(biāo)表示數(shù)據(jù)集的256個(gè)特征,縱坐標(biāo)表示2種不同特征選擇方法對(duì)應(yīng)的特征得分.圖2(a)為基于l2,1范數(shù)的EGCFS[23],將求解的投影矩陣W的‖wi‖2大小作為特征評(píng)分,需要對(duì)分?jǐn)?shù)進(jìn)行排序,選擇得分前10的特征.然而,從(a)中可觀察到,大多數(shù)分?jǐn)?shù)非常相近,因此根據(jù)得分大小單個(gè)選擇的特征可能不是一組最佳的特征子集.圖2(b)為本文提出的組特征選擇方法.引入元素為0或1的特征選擇向量,并且約束元素為1的個(gè)數(shù)為選擇特征的個(gè)數(shù),可通過(guò)直接選擇得分為1的特征得到一組特征子集,實(shí)現(xiàn)組特征選擇.

(a)EGCFS

2 基于l2,0范數(shù)稀疏性和模糊相

似性的圖優(yōu)化無(wú)監(jiān)督特征選擇

方法

2.1 模型建立

傳統(tǒng)的基于圖的無(wú)監(jiān)督特征選擇方法包括兩個(gè)階段：構(gòu)造相似性矩陣和通過(guò)稀疏正則化進(jìn)行特征選擇.僅從原始數(shù)據(jù)矩陣中構(gòu)造相似性矩陣,在后續(xù)特征選擇任務(wù)中保持不變,那么由于原始數(shù)據(jù)通常包含噪聲和冗余信息,導(dǎo)致學(xué)習(xí)的相似性矩陣次優(yōu).本文提出基于l2,0范數(shù)稀疏性的無(wú)監(jiān)督組特征選擇方法(Unsupervised Group Feature Selection Method for Graph Optimization Based onl2,0-norm Sparsity, SUGFS)，將相似性矩陣學(xué)習(xí)與特征選擇統(tǒng)一到同一框架,同時(shí)學(xué)習(xí)具有精確連通分量的相似性矩陣S和具有l(wèi)2,0范數(shù)約束的投影矩陣W.圖學(xué)習(xí)可為特征選擇提供精確的數(shù)據(jù)結(jié)構(gòu)信息,而特征選擇過(guò)程又可為圖學(xué)習(xí)去除冗余信息,具體公式描述如下：

(3)

其中k為選擇特征的個(gè)數(shù),α、β為正則化參數(shù),投影矩陣W∈Rd×m,d為原始特征維數(shù),m為投影維數(shù).

替代約束

‖W‖2,0=k,

直接選擇k個(gè)特征.將式(3)中WT替換為WTdiag(r),得

s.t.WTW=I,FTF=I,

(4)

這樣,通過(guò)特征選擇向量r∈{0,1}d,可實(shí)現(xiàn)組特征選擇,同時(shí)選擇一組最優(yōu)的特征而不是逐個(gè)選擇特征.

此外,受FCM(FuzzyC-means)在K-means聚類的基礎(chǔ)上引入模糊因子以提高聚類精度的啟發(fā),本文引入模糊相似因子ρ(ρ>1)，進(jìn)一步擴(kuò)展模型(4),提出基于l2,0范數(shù)稀疏性和模糊相似性的圖優(yōu)化無(wú)監(jiān)督組特征選擇方法(F-SUGFS)，具體公式描述如下：

(5)

2.2 SUGFS求解過(guò)程

為了求解SUGFS,將目標(biāo)函數(shù)(4)分解為4個(gè)子問(wèn)題,交替求解4個(gè)變量W,S,F,r.

2.2.1固定W,S,F,求解r

優(yōu)化變量r∈{0,1}d為一個(gè)0-1整數(shù)約束,不易求解.本文利用lp-box[30]中p=2的情況,稱為l2-box，求解r的0-1整數(shù)規(guī)劃問(wèn)題,將離散的0-1整數(shù)約束轉(zhuǎn)化為2個(gè)連續(xù)的約束.具體方法如下.

命題1l2-box 二元集r∈{0,1}d等價(jià)于一個(gè)“盒子”Sb與一個(gè)d-1維球體Sp的交集:

其中

l2-box在二維情況下的幾何解釋如圖3所示.當(dāng)d=2,r為二維向量(x,y)時(shí),r的0-1約束為r∈{0,1}d,即

圖3 l2-box在二維空間的幾何解釋

x∈{0,1},y∈{0,1}.

根據(jù)命題1,

Sb={x∈[0,1],y∈[0,1]}

為一個(gè)實(shí)心正方形,

根據(jù)命題1,固定W,S,F,模型(4)變?yōu)?/p>

其中，

定義增廣拉格朗日函數(shù):

其中，η1∈Rd,η2∈Rd,η3∈R,為3個(gè)等式約束的拉格朗日乘子,σ>0為懲罰參數(shù).

為了求解模型(4),利用ADMM迭代更新變量r,r1,r2和拉格朗日乘子η1,η2,η3.

1)更新變量r,r1,r2:

(6)

其中，

PSb(a)=min{1d,max{0d,a}},

2)更新拉格朗日乘子η1,η2,η3：

2.2.2固定S,r,F,求解W

當(dāng)S,r,F固定時(shí),模型(4)變?yōu)?/p>

(7)

W∈Rd×m的最優(yōu)解為A的最小的m個(gè)特征值對(duì)應(yīng)的特征向量,其中

A=diag(r)XLSXTdiag(r).

2.2.3固定W,S,r,求解F

當(dāng)W,S,r固定時(shí),F的最優(yōu)解為

(8)

F∈Rn×c的最優(yōu)解為L(zhǎng)S的最小的c個(gè)特征值對(duì)應(yīng)的特征向量.

2.2.4固定W,r,F,求解S

當(dāng)W,r,F固定時(shí),模型(4)變?yōu)?/p>

(9)

可驗(yàn)證

(10)

其中fi為F∈Rn×c的第i行.

將式(10)代入式(9),可得

(11)

其中

相似性矩陣S的第i行Si表示第i個(gè)數(shù)據(jù)與其它數(shù)據(jù)點(diǎn)的相似性,因此可獨(dú)立求解每個(gè)Si:

(12)

其中

單純性約束的Si可利用文獻(xiàn)[31]求解：

(13)

其中，

的根.

相似性矩陣S表示數(shù)據(jù)間的相似性,距離越近的數(shù)據(jù)具有越高的相似性.因此在實(shí)際應(yīng)用中,希望學(xué)習(xí)一個(gè)稀疏的Si,使每個(gè)數(shù)據(jù)xi只與距離xi最近的l個(gè)數(shù)據(jù)點(diǎn)相似,相似度大于0,與較遠(yuǎn)的數(shù)據(jù)點(diǎn)相似度為0.這樣可獲得良好的性能,提高效率.

假設(shè)數(shù)據(jù)點(diǎn)xi與其余數(shù)據(jù)點(diǎn)的距離由小到大為

di,1,di,2,… ,di,l,di,l+1,… ,di,n,

因?yàn)榕cxi距離最近的數(shù)據(jù)為xi本身,di,1=0,所以xi的l個(gè)近鄰為di,2,di,3,…,di,l+1對(duì)應(yīng)的數(shù)據(jù).為了使S具有稀疏性,每個(gè)Si僅有固定的l個(gè)非零元素,在實(shí)際求解過(guò)程中,利用式(13)求解di,2,… ,di,r,di,r+1對(duì)應(yīng)位置的Si,2,Si,3,…,Si,r+1,其余元素為0.

2.3 F-SUGFS求解過(guò)程

在SUGFS的基礎(chǔ)上,引入模糊相似因子ρ>1,進(jìn)一步拓展為F-SUGFS,SUGFS表示為ρ=1的特殊情況,F-SUGFS變量W,r,F的求解與SUGFS類似.下面僅給出相似性矩陣S的求解.

當(dāng)變量W,r,F固定時(shí),模型(5)轉(zhuǎn)化為

(14)

其中

式(14)的增廣拉格朗日函數(shù)定義為

對(duì)Sij求偏導(dǎo)等于0,得

(15)

其中

綜上所述,F-SUGFS步驟如算法1所示.

算法1F-SUGFS

輸入數(shù)據(jù)矩陣X∈Rd×n,選擇特征個(gè)數(shù)k,

最近鄰個(gè)數(shù)l,投影矩陣維數(shù)m,聚類數(shù)c

輸出特征選擇向量r

初始化求解式(1),初始化相似性矩陣S,拉普拉

斯矩陣

WTW=I的投影矩陣W,求解式(11),初

始化F.

循環(huán)直至收斂.

step 1 利用ADMM求解r.

step 2 求解式(7),更新W,為A的最小m個(gè)特征值對(duì)應(yīng)的特征向量.

step 3 求解式(8),更新F,為L(zhǎng)S的最小c個(gè)特征值對(duì)應(yīng)的特征向量.

step 4 求解相似性矩陣S.當(dāng)ρ=1時(shí)求解式(13);當(dāng)ρ>1時(shí)求解式(15).

step 5 更新拉普拉斯矩陣LS.

2.4 收斂性分析

算法1交替求解4個(gè)變量W,S,F,r,并且在每次迭代中單調(diào)減小式(4)中的目標(biāo)函數(shù)值,具體分析如下.

使用g(Wt,St,Ft,rt)表示t次迭代時(shí)的目標(biāo)函數(shù)(4),則有

2.2.1節(jié)中利用l2-box ADMM更新0-1向量r,根據(jù)文獻(xiàn)[30]可得lp-box ADMM生成的變量序列的收斂性,即

g(Wt,St,Ft,rt)≥g(Wt,St,Ft,rt+1).

其次,根據(jù)2.2.2節(jié)和2.2.3節(jié),Wt+1和Ft+1為目標(biāo)函數(shù)第t次迭代時(shí)的最優(yōu)解：

因此有

g(Wt,St,Ft,rt)≥g(Wt+1,St,Ft+1,rt+1).

最后根據(jù)式(12)和式(13),得

g(Wt,St,Ft,rt)≥g(Wt+1,St+1,Ft+1,rt+1).

同理可證F-SUGFS的收斂性.

2.5 復(fù)雜度分析

根據(jù)算法1的步驟,分析每步的時(shí)間復(fù)雜度.

step 1中通過(guò)ADMM過(guò)程求解r,這個(gè)過(guò)程的主要步驟為計(jì)算式(6),需要計(jì)算d×d矩陣的逆,時(shí)間復(fù)雜度為O(d3),假設(shè)step 1需要t1次迭代,因此step 1總共耗時(shí)O(t1d3).考慮LS的稀疏性,step 2和step 3的時(shí)間復(fù)雜度為O(n2l).step 4中需要獨(dú)立求解S的每行,時(shí)間復(fù)雜度為O(n2m+ndm).假設(shè)算法1需要迭代t2次,算法1的整體時(shí)間復(fù)雜度為

O(n2mt2+d3t1t2).

為了說(shuō)明F-SUGFS與其它無(wú)監(jiān)督特征選擇方法在計(jì)算復(fù)雜度上的差異,5種無(wú)監(jiān)督特征選擇方法的計(jì)算復(fù)雜度如下.LS(Laplacian Score)[14]為O(n2d)，MCFS為O(n2d+ck3+nck2)，UDFS為O(n2c+d3)，SOGFS為O(n2m+d3)，EGCFS為O(n2m+d3).

由對(duì)比結(jié)果可看出,過(guò)濾式的特征選擇方法LS具有較低的計(jì)算復(fù)雜度.相比其余4種嵌入式特征選擇,MCFS計(jì)算復(fù)雜度較低.由于基于圖的特征選擇方法大多需要特征分解,因此算法1的時(shí)間復(fù)雜度與基于圖的特征選擇算法SOGFS和EGCFS的時(shí)間復(fù)雜度相似.

3 實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)條件為Windows 10系統(tǒng),8 GB內(nèi)存,Intel(R)Core(TM)i7-4790 CPU @3.60 GHz,MatlabR2018b.

3.1 實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)在8個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行,包括人臉數(shù)據(jù)集(MSRA25,Yale,COIL20)、生物數(shù)據(jù)集(Colon,Prostate_GE,GLIOMA,Lung)、語(yǔ)音字母識(shí)別數(shù)據(jù)集ISOLET、面部表情數(shù)據(jù)集JAFFE.數(shù)據(jù)集具體信息如表1所示.

表1 實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證本文方法性能,對(duì)比如下無(wú)監(jiān)督特征選擇方法.

1)Baseline.基線方法,不進(jìn)行特征選擇,使用原始數(shù)據(jù)進(jìn)行K-means聚類任務(wù).

2)LS[14].經(jīng)典的過(guò)濾式特征選擇算法,基本思想是根據(jù)特征的局部保持能力對(duì)特征進(jìn)行評(píng)估,選擇得分最高的前K個(gè)特征作為最終選擇的特征子集.

3)MCFS[18].通過(guò)具有l(wèi)1范數(shù)正則化的回歸模型衡量特征的重要性,最近鄰個(gè)數(shù)設(shè)置為5.

4)UDFS[19].正則化參數(shù)取值范圍為

{10-2,10-1,1,10,102,103}.

5)SOGFS[21].同時(shí)進(jìn)行局部結(jié)構(gòu)學(xué)習(xí)和l2,1范數(shù)正則化的特征選擇.正則化參數(shù)取值范圍為

{10-2,10-1,1,10,102,103},

6)EGCFS[23].利用嵌入的圖學(xué)習(xí)和約束選擇不相關(guān)但有區(qū)別的特征.正則化參數(shù)α、γ取值范圍為

{10-2,10-1,1,10,102,103}.

8)F-SUGFS.本文設(shè)置參數(shù)ρ=2,與SUGFS進(jìn)行對(duì)比.

3.2 評(píng)估指標(biāo)

為了評(píng)估所有無(wú)監(jiān)督特征選擇方法的性能,將選擇的特征用于基于K-means的聚類任務(wù).為了避免K-means隨機(jī)初始化的影響,運(yùn)行10次K-means聚類取平均結(jié)果.在評(píng)估每種方法的性能時(shí),使用2個(gè)經(jīng)典的聚類算法評(píng)估指標(biāo):準(zhǔn)確率(Accurary, ACC)及歸一化互信息(Normalized Mutual Informa-tion, NMI).ACC和NMI值越大說(shuō)明方法性能越優(yōu).

3.3 實(shí)驗(yàn)結(jié)果

圖4為8種無(wú)監(jiān)督特征選擇方法在9個(gè)數(shù)據(jù)集上選擇特征個(gè)數(shù)與ACC和NMI的關(guān)系.在MSRA25數(shù)據(jù)集上選擇50～200個(gè)特征,間隔30.其余數(shù)據(jù)集上選擇50～300個(gè)特征,間隔50.

由圖4可看出，大部分特征選擇方法僅選擇少量特征進(jìn)行聚類的結(jié)果便優(yōu)于Baseline,表明特征選擇的必要性和有效性.特征選擇可去除冗余、不相關(guān)特征及噪聲,選擇具有代表性的特征,提高聚類精度.

通過(guò)實(shí)驗(yàn)可看出,并不是選擇越多特征聚類效果越優(yōu).一般情況下,聚類精度會(huì)隨選擇特征個(gè)數(shù)的增多呈現(xiàn)先增大后減小的趨勢(shì).因?yàn)殡S著選擇特征個(gè)數(shù)的增多,可能因此冗余特征或噪聲被選擇，從而影響實(shí)驗(yàn)結(jié)果.

由圖4也可直觀看出,在大部分?jǐn)?shù)據(jù)集上,本文方法在選擇較少的特征時(shí)就取得比其他方法更高的聚類精度和歸一化互信息.在面部表情數(shù)據(jù)集JAFFE和人臉數(shù)據(jù)集Yale上,SUGFS和F-SUGFS效果均較顯著.

由圖4還可觀察到,除了ISOLET、Lung數(shù)據(jù)集,本文方法在其余7個(gè)數(shù)據(jù)集上無(wú)論選擇多少特征,均超過(guò)Baseline.相比其它嵌入式特征選擇方法,過(guò)濾式特征選擇方法LS在多個(gè)數(shù)據(jù)集上性能較差,這是因?yàn)檫^(guò)濾式特征選擇未考慮針對(duì)后續(xù)學(xué)習(xí)器以選擇特征子集.

(a1)ACC (a2)NMI

表2和表3為各方法在9個(gè)數(shù)據(jù)集上的最佳聚類結(jié)果(ACC和NMI),其中黑體數(shù)字為最佳值,斜體數(shù)字為次優(yōu)值.由表可看出，本文方法在7個(gè)數(shù)據(jù)集上都取得最佳聚類結(jié)果,F-SUGFS取得和SUGFS同樣好的結(jié)果,并且在高維數(shù)據(jù)集GLIOMA與Prostate_GE上SUGFS的性能均有所提高.

表2 各方法在9個(gè)數(shù)據(jù)集上的最高ACC值對(duì)比

表3 各方法在9個(gè)數(shù)據(jù)集上的最高NMI值對(duì)比

表4和表5為各方法在9個(gè)數(shù)據(jù)集上均選擇100個(gè)特征的聚類結(jié)果,表中黑體數(shù)字表示最優(yōu)值，斜體數(shù)字表示次優(yōu)值.表6給出本文方法與5種特征選擇方法的運(yùn)行時(shí)間對(duì)比.

表6 各方法在9個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比

由表4和表5可看出，本文方法選擇特定個(gè)數(shù)的特征依然獲得較優(yōu)結(jié)果,體現(xiàn)本文方法的穩(wěn)定性.

表4 各方法在9個(gè)數(shù)據(jù)集上選擇100個(gè)特征的ACC值

表5 各方法在9個(gè)數(shù)據(jù)集上選擇100個(gè)特征的的NMI值

對(duì)比SOGFS,本文的l2,0范數(shù)約束在不同數(shù)據(jù)集上均取得顯著優(yōu)勢(shì),表明l2-box求解的0-1約束特征選擇向量的有效性.對(duì)比Baseline,本文方法明顯提高Baseline的聚類精度,在Yale數(shù)據(jù)集上提升最快,ACC和NMI值均提高20%左右,在COIL20數(shù)據(jù)集上提升約15%,在其余數(shù)據(jù)集上平均提升約8%.

由表6可知，與2.5節(jié)復(fù)雜度分析一致,過(guò)濾式特征選擇方法LS的運(yùn)行時(shí)間最短,但從圖4的實(shí)驗(yàn)結(jié)果來(lái)看,LS選擇的特征聚類效果較差.本文方法與基于圖的無(wú)監(jiān)督特征選擇方法SOGFS和EGCFS具有相近的運(yùn)行時(shí)間,隨著數(shù)據(jù)集維數(shù)的增大,運(yùn)行時(shí)間也變長(zhǎng),但從表1和表2的聚類效果來(lái)看,本文方法具有較優(yōu)性能.因此,本文方法是一種相對(duì)高效的無(wú)監(jiān)督特征選擇方法.

4 結(jié)束語(yǔ)

本文提出基于l2,0范數(shù)稀疏性的圖優(yōu)化無(wú)監(jiān)督組特征選擇方法(SUGFS),利用l2,0范數(shù)約束,可同時(shí)選擇一組最優(yōu)的特征子集.為了求解非凸的l2,0范數(shù)約束,引入元素為0-1的特征選擇向量,將投影矩陣的l2,0范數(shù)約束轉(zhuǎn)化為向量的0-1整數(shù)規(guī)劃問(wèn)題,進(jìn)而利用l2-box ADMM進(jìn)行求解.同時(shí)引入模糊相似性因子,可根據(jù)不同數(shù)據(jù)集進(jìn)行調(diào)節(jié),適用于不同數(shù)據(jù)集,性能較優(yōu).通過(guò)實(shí)驗(yàn)驗(yàn)證本文方法的有效性.本文方法在大部分?jǐn)?shù)據(jù)集上聚類效果都得到明顯提升,但當(dāng)數(shù)據(jù)集維數(shù)較大時(shí),效率會(huì)有所下降.因此,如何加速本文方法是今后研究方向之一.