基于l2,0范數(shù)稀疏性和模糊相似性的圖優(yōu)化無監(jiān)督組特征選擇方法

孟田田 周水生 田昕潤

MENG Tiantian1, ZHOU Shuisheng1, TIAN Xinrun1

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

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

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

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

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

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

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

盡管上述方法都是對l2,0范數(shù)特征選擇問題進行求解,但在實際優(yōu)化過程中,仍需要通過某種方式排序選擇特征,這意味著這些方法依然是l2,1范數(shù)的變體,沒有從根本上解決l2,1范數(shù)正則化存在的問題.為此,本文提出解決l2,0范數(shù)組稀疏的特征選擇方法,即基于l2,0范數(shù)稀疏性和模糊相似性的圖優(yōu)化無監(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個連續(xù)約束,通過交替方向乘子法(Alternating Direction Method of Mul-tipliers, ADMM)進行求解,動態(tài)選擇一組最優(yōu)的特征,實現(xiàn)組特征選擇.最后,引入模糊相似因子,進一步擴展方法.在多個真實數(shù)據(jù)集上的實驗驗證本文方法的有效性.

1 相關(guān)工作

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

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

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

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

1.1 相似性圖學習

(1)

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

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

rank(LS)=n-c,

其中

度矩陣D為對角矩陣,對角線元素

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

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

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

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

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

1.2 基于稀疏學習的無監(jiān)督特征選擇

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

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

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

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

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

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

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

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

對于特征選擇任務(wù),W的第i行wi衡量第i個特征的重要性.當

‖wi‖≠0

時,選擇第i個特征fi,當

‖wi‖=0

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

‖W‖2,0=k,

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

(2)

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

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

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

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

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

(a)EGCFS

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

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

方法

2.1 模型建立

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

(3)

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

替代約束

‖W‖2,0=k,

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

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

(4)

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

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

(5)

2.2 SUGFS求解過程

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

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

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

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

其中

l2-box在二維情況下的幾何解釋如圖3所示.當d=2,r為二維向量(x,y)時,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]}

為一個實心正方形,

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

其中，

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

其中，η1∈Rd,η2∈Rd,η3∈R,為3個等式約束的拉格朗日乘子,σ>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

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

(7)

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

A=diag(r)XLSXTdiag(r).

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

當W,S,r固定時,F的最優(yōu)解為

(8)

F∈Rn×c的最優(yōu)解為LS的最小的c個特征值對應(yīng)的特征向量.

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

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

(9)

可驗證

(10)

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

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

(11)

其中

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

(12)

其中

單純性約束的Si可利用文獻[31]求解：

(13)

其中，

的根.

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

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

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

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

2.3 F-SUGFS求解過程

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

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

(14)

其中

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

對Sij求偏導等于0,得

(15)

其中

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

算法1F-SUGFS

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

最近鄰個數(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個特征值對應(yīng)的特征向量.

step 3 求解式(8),更新F,為LS的最小c個特征值對應(yīng)的特征向量.

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

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

2.4 收斂性分析

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

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

2.2.1節(jié)中利用l2-box ADMM更新0-1向量r,根據(jù)文獻[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為目標函數(shù)第t次迭代時的最優(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的步驟,分析每步的時間復(fù)雜度.

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

O(n2mt2+d3t1t2).

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

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

3 實驗及結(jié)果分析

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

3.1 實驗環(huán)境

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

表1 實驗數(shù)據(jù)集

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

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

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

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

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

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

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

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

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

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

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

3.2 評估指標

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

3.3 實驗結(jié)果

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

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

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

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

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

(a1)ACC (a2)NMI

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

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

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

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

表6 各方法在9個數(shù)據(jù)集上的運行時間對比

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

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

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

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

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

4 結(jié)束語

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