聯(lián)合Laplacian正則項(xiàng)和特征自適應(yīng)的數(shù)據(jù)聚類算法?

鄭建煒 , 李卓蓉,2 , 王萬良 , 陳婉君

1(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,浙江 杭州 310023)

2(浙江大學(xué)城市學(xué)院 計(jì)算機(jī)與計(jì)算科學(xué)學(xué)院,浙江 杭州 310015)

聚類分析是數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)之一,旨在無標(biāo)簽情形下對(duì)數(shù)據(jù)進(jìn)行分組,使組內(nèi)數(shù)據(jù)盡可能相似而組間數(shù)據(jù)盡可能不同,被廣泛應(yīng)用于圖像分割[1]、目標(biāo)分簇[2]、深度學(xué)習(xí)模型[3]等科學(xué)應(yīng)用領(lǐng)域.在大數(shù)據(jù)背景下,實(shí)際輸入數(shù)據(jù)除“海量樣本”特點(diǎn)外,還具有極高的特征維數(shù).以在線文本數(shù)據(jù)為例,當(dāng)采用矢量空間描述每個(gè)文檔時(shí),大詞匯量往往導(dǎo)致樣本維數(shù)達(dá)到5 000以上.此外,一張解析度為256×256的圖像矢量化后的維數(shù)則是65 536.受“維數(shù)災(zāi)難”限制,對(duì)高維數(shù)據(jù)進(jìn)行合理高效的聚類分析是一個(gè)極具挑戰(zhàn)性的問題.過高的樣本維度包含冗余的特征信息和異常噪聲,不僅降低了后續(xù)聚類操作的運(yùn)算效率,也影響了其他性能指標(biāo).針對(duì)該問題,常見的思路是引入特征選擇進(jìn)行維數(shù)預(yù)約簡,然后在子空間進(jìn)行相似度矩陣構(gòu)建并對(duì)嵌入數(shù)據(jù)實(shí)施譜聚類分析.

特征選擇(feature selection,簡稱FS)[4]從原始樣本空間中挑選最具代表性的維數(shù)子集,其核心問題依據(jù)特定準(zhǔn)則評(píng)價(jià)各子集的優(yōu)劣并確定選擇結(jié)果.傳統(tǒng)搜索策略[5]的缺點(diǎn)是直接利用數(shù)據(jù)的統(tǒng)計(jì)指標(biāo)對(duì)每個(gè)特征進(jìn)行單獨(dú)評(píng)分并取分值較高者為結(jié)果集,缺乏整體的優(yōu)劣評(píng)判標(biāo)準(zhǔn)[6].針對(duì)此問題,學(xué)者們開展了聯(lián)合特征選擇研究,通過稀疏正則化約束[7]進(jìn)行特征選擇并兼顧子空間學(xué)習(xí).Cai等人[8]結(jié)合流形學(xué)習(xí)和l1正則化模型進(jìn)行稀疏的聯(lián)合特征選擇.所選用的l1范數(shù)雖然意義明確,但其稀疏性僅作用于獨(dú)立的特征點(diǎn)[9].更多的算法[10]通過對(duì)投影矩陣約束l2,1范數(shù)以保證行稀疏,選擇矩陣非零行對(duì)應(yīng)的特征集合為最優(yōu)特征子集.在評(píng)價(jià)準(zhǔn)則方面,通常選擇能有效保持?jǐn)?shù)據(jù)本質(zhì)結(jié)構(gòu)的特征,采用圖論模型刻畫全局結(jié)構(gòu)、局部流形以及鑒別性信息等.多簇特征選擇法(multi-clusters FS,簡稱MCFS)[8]首先計(jì)算高維數(shù)據(jù)的低維流形嵌入,然后對(duì)投影矩陣采用l1范數(shù)進(jìn)行稀疏約束,根據(jù)回歸系數(shù)對(duì)每個(gè)特征進(jìn)行排序,最終選擇最易保持局部流形結(jié)構(gòu)的特征.局部學(xué)習(xí)聚類(local learning based clustering for FS,簡稱LLCFS)[11]將特征關(guān)聯(lián)性引至內(nèi)置的正則化局部學(xué)習(xí)模型,使得演化的Laplacian圖能夠迭代優(yōu)化.自適應(yīng)結(jié)構(gòu)學(xué)習(xí)(FS with adaptive structure learning,簡稱FSASL)[12]旨在結(jié)合全局信息挖掘以及局部流形學(xué)習(xí)進(jìn)行樣本結(jié)構(gòu)保持,兼顧了稀疏性和保局性兩種優(yōu)勢(shì).局部保持得分法(locality preserving score,簡稱LPS)[13]則從誤差抑制的角度出發(fā),對(duì)每個(gè)特征的重構(gòu)能力進(jìn)行排序,獲得最優(yōu)的子特征集.上述算法采用獨(dú)立的步驟按序進(jìn)行子空間學(xué)習(xí)和聚類操作,其弊端是無法達(dá)到聚類目標(biāo)的整體最優(yōu)效果.常見的解決方案是將子空間聚類融合為聯(lián)合優(yōu)化整體,通過聚類指標(biāo)和降維指標(biāo)互相反饋優(yōu)化模型的各約束項(xiàng).鑒別嵌入聚類法(discriminative embedded clustering,簡稱DEC)[14]聯(lián)合Fisher鑒別投影和k-means提出一致性的分簇框架,但其受限于k-means的本質(zhì)約束,無法適應(yīng)單流形多環(huán)分布數(shù)據(jù).非負(fù)鑒別法(nonnegative discriminative FS,簡稱NDFS)[15]將聚類標(biāo)簽反饋于特征選擇步驟,提升了特征子集的鑒別性,然而其特征選擇過程缺乏結(jié)構(gòu)性意義,且算法容易陷入局部最優(yōu)點(diǎn).

提升相似度矩陣(或稱為關(guān)聯(lián)矩陣、鄰接矩陣)結(jié)構(gòu)是進(jìn)一步改進(jìn)子空間聚類性能的關(guān)鍵思想,也是譜聚類算法的核心步驟.Wang等人[16]基于局部線性嵌入思想[17]構(gòu)建Laplacian圖,獲得了良好的標(biāo)簽傳播性能.Elhamifar等人[18]則以全局線性表示系數(shù)作為關(guān)聯(lián)矩陣構(gòu)建基礎(chǔ),通過l1范數(shù)提出了稀疏子空間聚類法(sparse subspace clustering,簡稱SSC).SSC假設(shè)每個(gè)數(shù)據(jù)由同一子空間中其他樣本稀疏表示,挖掘不同組的表示關(guān)系,但其缺乏空間分布結(jié)構(gòu)考慮.Liu等人[19]提出了低秩表示(low-rank representation,簡稱LRR)聚類法,利用核范數(shù)約束系數(shù)矩陣,獲得更好的全局性.SSC和LRR以輸入樣本子空間相互獨(dú)立或正交為假設(shè),其理想狀態(tài)下的相似矩陣具有刻畫子空間屬性的塊對(duì)角結(jié)構(gòu).進(jìn)一步,Lu等人[20]給出了一組強(qiáng)制塊對(duì)角條件,并指出:在數(shù)據(jù)充分并且子空間相互獨(dú)立的前提下,正則項(xiàng)滿足該條件可保證相似矩陣具有塊對(duì)角結(jié)構(gòu).Feng等人[21]將對(duì)應(yīng)的拉普拉斯矩陣進(jìn)行低秩約束,并添加至SSC和LRR以保證塊對(duì)角狀態(tài),獲得更優(yōu)的相似度結(jié)構(gòu).此外,在系數(shù)矩陣優(yōu)化問題上,新晉算法都采用Laplacian正則項(xiàng)約束提升相似度矩陣的塊對(duì)角結(jié)構(gòu)[22?24],非負(fù)稀疏Laplacian正則約束的LRR模型(non-negative sparse Laplacian regularized LRR,簡稱NSLLRR)[22]以非負(fù)性、稀疏性為條件,增加超圖拉普拉斯約束,具有良好的樣本表示能力.Hu等人[23]提出的光滑表示聚類模型(smooth representation clustering,簡稱SMR)基于增強(qiáng)型組效應(yīng)條件進(jìn)行相似性度量,算法在保證高質(zhì)量聚類性能的前提下獲得了大幅度效率提升.為更好地逼近低秩結(jié)構(gòu),分組低秩結(jié)構(gòu)模型(low-rank structure,簡稱LRS)[24]引入組指示規(guī)化對(duì)各簇樣本進(jìn)行Schattenp范數(shù)正則項(xiàng)約束,其缺陷是抗噪性差且模型運(yùn)算效率較低.

綜上所述,現(xiàn)存的特征選擇型算法缺乏樣本間關(guān)聯(lián)結(jié)構(gòu)描述,導(dǎo)致次優(yōu)的聚類性能;而Laplacian正則型表示模型則都采用原始數(shù)據(jù)直接構(gòu)建關(guān)聯(lián)矩陣,獨(dú)立于表示系數(shù)更新操作,也不具備整體算法的最優(yōu)性.雖然魯棒子空間分割法(robust subspace segmentation,簡稱RSS)[25]實(shí)現(xiàn)了重構(gòu)系數(shù)和相似度矩陣的兼顧學(xué)習(xí),具有更優(yōu)的結(jié)構(gòu)挖掘能力,但缺乏特征優(yōu)選機(jī)制,對(duì)現(xiàn)實(shí)高維數(shù)據(jù)的抗噪性弱,且其自表示框架受稀疏性、非負(fù)性等約束的影響,運(yùn)行效率較低,樣本規(guī)模尺度化能力有待進(jìn)一步提高.針對(duì)現(xiàn)存算法的問題,本文基于自適應(yīng)近鄰進(jìn)行圖拉普拉斯學(xué)習(xí),將低維嵌入、特征選擇和簇結(jié)構(gòu)學(xué)習(xí)納入同一框架,提出一種兼顧自適應(yīng)特征優(yōu)選和簇結(jié)構(gòu)學(xué)習(xí)的聚類模型,即聯(lián)合拉普拉斯正則項(xiàng)和自適應(yīng)特征學(xué)習(xí)(joint Laplacian regularization and adaptive feature learning,簡稱LRAFL)的數(shù)據(jù)聚類算法,具體工作如下.

1) 提出一種圖Laplacian矩陣更新策略,保證其秩結(jié)構(gòu)與目標(biāo)聚類數(shù)的一致性,使得模型優(yōu)化結(jié)果直接具備分簇塊對(duì)角結(jié)構(gòu),規(guī)避了后續(xù)k-means、譜分解等操作;

2) 將特征學(xué)習(xí)機(jī)制融入Laplacian矩陣構(gòu)建框架,在保證噪聲特征抑制的前提下,去除高復(fù)雜度的表示系數(shù)學(xué)習(xí)過程,提升模型求解效率;

3) 設(shè)計(jì)具備唯一最優(yōu)解的參數(shù)優(yōu)化方案,對(duì)模型部分待定參數(shù)進(jìn)行推演分析,給出更具指示意義的設(shè)定方法,進(jìn)一步加速模型實(shí)現(xiàn)效率.

1 相關(guān)工作

本節(jié)介紹譜聚類算法中的兩個(gè)關(guān)鍵步驟,即相似度矩陣構(gòu)建和拉普拉斯正則約束項(xiàng),其中,前者用于挖掘數(shù)據(jù)分布結(jié)構(gòu),而后者是引導(dǎo)塊對(duì)角狀態(tài)的核心技術(shù).

1.1 相似度矩陣構(gòu)建

傳統(tǒng)的相似圖構(gòu)建方法如ε鄰域圖、k近鄰圖、全連接圖等都存在著明顯的缺陷,包括:(1) 分析尺度選擇困難;(2) 參數(shù)敏感性強(qiáng);(3) 多尺度數(shù)據(jù)適應(yīng)度弱;(4) 抗噪性差等等.為解決存在的問題,Wang等人[16]在鄰域圖基礎(chǔ)上通過線性表示計(jì)算相似度權(quán)值,提升了算法抗噪性;Zelnik-Manor等人[26]提出自校正譜分簇算法,緩解了第1個(gè)和第3個(gè)缺陷.Cheng等人[27]引入稀疏表示進(jìn)行鄰域圖構(gòu)建,可以有效解決第1個(gè)和第4個(gè)問題,也規(guī)避了高敏感性的待定參數(shù)ε和k,但其正則項(xiàng)參數(shù)的敏感性仍然較強(qiáng),且存在l1范數(shù)求解運(yùn)行效率低的問題.Huang等人[28]采用非負(fù)和加權(quán)限制替代文獻(xiàn)[27]中的l1范數(shù)約束,提出了單純型稀疏表示(simplex sparse representation,簡稱SSR)鄰域圖構(gòu)建方法,能有效解決上述前3個(gè)問題;而且算法不需要人工設(shè)定參數(shù),運(yùn)行效率和實(shí)現(xiàn)簡易度亦優(yōu)于其他對(duì)比算法.

給定數(shù)據(jù)集X=[x1,x2,…,xn]∈Rm×n,其中,xi是第i個(gè)m維輸入樣本,n是訓(xùn)練樣本總數(shù).定義鄰域圖模型S,其元素sij表示數(shù)據(jù)點(diǎn)xi與xj互為近鄰的概率,si∈Rn表示S的第i個(gè)列向量.SSR的目標(biāo)函數(shù)為

其中,X?i=[x1,…,xi?1,0,xi+1,…,xn]表示剔除第i個(gè)輸入數(shù)據(jù)的訓(xùn)練樣本集,0是m×1的零向量,1是元素全為1的n×1向量.公式(1)通過重構(gòu)表示能力說明高權(quán)值系數(shù)的成對(duì)樣本具有更高的概率互為近鄰,具有天然的樣本稀疏性和奇異點(diǎn)抗噪性,其缺點(diǎn)是不具備特征稀疏性,因此不適于高維度冗余數(shù)據(jù)應(yīng)用.

1.2 Laplacian正則約束

Laplacian矩陣構(gòu)建的方式多樣,且各算法的作者都稱自己的譜分析矩陣為Laplacian.給定對(duì)稱的相似度矩陣S,RatioCut[29]所構(gòu)建的Laplacian矩陣為L=D?S,其中,對(duì)角矩陣D稱為度矩陣,相應(yīng)的對(duì)角元素NCut[30]將上述L進(jìn)行規(guī)范化操作,即Ls=D?1/2LD?1/2或Lns=D?1L,其中,前者是對(duì)稱矩陣而后者是非對(duì)稱矩陣.當(dāng)給定非對(duì)稱的S時(shí),則相應(yīng)的非規(guī)范化Laplacian矩陣計(jì)算為L=D?(ST+S)/2[13,31],其中,度矩陣D的對(duì)角元素為在經(jīng)典譜聚類算法中,無論Laplacian矩陣形式如何,后續(xù)操作都對(duì)該矩陣進(jìn)行特征求解,并針對(duì)前c個(gè)特征矢量進(jìn)行k-means聚類,其中,c是數(shù)據(jù)簇結(jié)構(gòu)目標(biāo).

最近,Hu等人[23]以譜聚類為基礎(chǔ),結(jié)合低秩重構(gòu)表示思想將一般的表示型譜聚類模型歸納為

其中,α>0是平衡參數(shù),A(X)表示字典矩陣,Z是系數(shù)矩陣,||?||l表示合適的范數(shù).公式(2)前半部分刻畫了重構(gòu)表示A(X)Z逼近數(shù)據(jù)X的程度,后半部分是Laplacian譜約束正則項(xiàng).

稀疏子空間聚類對(duì)公式(2)的正則項(xiàng)采用某種稀疏度量,從而使Z具有特定目標(biāo)結(jié)構(gòu).常見的包括SSC的l1范數(shù)約束、LRR的核范數(shù)約束以及SMR和RSS的組效應(yīng)約束等等.考慮到塊對(duì)角結(jié)構(gòu)的相似矩陣能更好地刻畫簇結(jié)構(gòu)屬性,Feng等人[25]利用相似度矩陣對(duì)角塊個(gè)數(shù)與Laplacian矩陣秩約束之間的關(guān)系,對(duì)圖拉普拉斯矩陣添加秩約束:

其中,c表示對(duì)角塊的個(gè)數(shù),也即簇目標(biāo)數(shù).將上述秩約束添加至子空間聚類模型,可保證清晰的塊對(duì)角結(jié)構(gòu),具體目標(biāo)模型描述為

其中,λ是平衡參數(shù);diag(Z)=0用于約束對(duì)角元素zii=0,以避免平凡解.

2 LRAFL算法描述

結(jié)合現(xiàn)有工作,考慮到自適應(yīng)鄰域?qū)W習(xí)和塊對(duì)角Laplacian矩陣對(duì)聚類效果的重要性以及自表示學(xué)習(xí)的復(fù)雜性,本節(jié)將公式(1)和公式(4)中的表示系數(shù)轉(zhuǎn)變?yōu)猷徲蚪Y(jié)構(gòu)約束,并輔以稀疏性、參數(shù)自學(xué)習(xí)、特征尋優(yōu)以及簇結(jié)構(gòu)直接確定等優(yōu)勢(shì),提出一種兼顧特征選擇和譜聚類的算法LRAFL.首先對(duì)該算法目標(biāo)函數(shù)的構(gòu)建過程進(jìn)行描述,然后給出了模型求解優(yōu)化方案.

2.1 目標(biāo)函數(shù)構(gòu)建

探索數(shù)據(jù)的局部連通性,即相似度權(quán)值,是聚類任務(wù)的典型策略[32].根據(jù)本文開始部分的描述,常規(guī)的表示系數(shù)[18,19]和線性關(guān)聯(lián)[16]都存在計(jì)算效率低以及缺乏全局最優(yōu)等弊端,本節(jié)直接以相似度計(jì)算為基礎(chǔ),輔以特征加權(quán)、低秩塊對(duì)角約束等構(gòu)建目標(biāo)函數(shù).首先給定任意輸入數(shù)據(jù)xi和xj,其距離與相似度權(quán)值sij應(yīng)呈反比關(guān)系,即短距離對(duì)應(yīng)大權(quán)值、長距離對(duì)應(yīng)小權(quán)值.因此,結(jié)合公式(1)對(duì)權(quán)值的概率條件約束,一種自然的相似度計(jì)算方法為

然而,公式(5)具有平凡解,僅xi的最近鄰樣本獲得概率相似度1而余下的sij=0.另一方面,如果在不包含任何距離信息約束下求解式:

則得到另一種平凡解,即所有樣本都是xi的近鄰且概率相似度為1/n,可以看作相似度賦值的先驗(yàn)分布,其本質(zhì)則是l2范數(shù)約束條件[33].結(jié)合公式(5)和公式(6),xi的鄰域相似度計(jì)算為

其中,第2項(xiàng)為正則項(xiàng),β是正則化參數(shù).聯(lián)合所有的輸入數(shù)據(jù)xi,i=1,…,n,則完整的相似度計(jì)算可以描述為

通過第2.2節(jié)模型優(yōu)化求解過程可知,公式(8)中各相似度矢量si具有稀疏的閉式解,模型優(yōu)化效率高且能夠有效抑制奇異噪聲樣本.

其次,為引入特征優(yōu)選機(jī)制,使算法具有奇異特征抑制性能,采用特征加權(quán)因子w∈Rm×1將公式(8)調(diào)整為

其中,⊙表示元素相乘符號(hào).與公式(5)和公式(6)類似,直接以公式(9)為目標(biāo)函數(shù)會(huì)出現(xiàn)平凡解.即:當(dāng)w取零向量且相似度為1/n時(shí),模型值最小.因此,進(jìn)一步將相似度約束條件添加至w權(quán)值矢量,即:

其中,d≤m表示選擇后有效特征數(shù).公式(10)第1部分用于相似度矩陣構(gòu)建,子項(xiàng)在特征優(yōu)選約束下,使鄰近的樣本對(duì)具有更高的相似度權(quán)值,而非近鄰樣本對(duì)具有較低的相似度權(quán)值,余下部分是特征加權(quán)矢量和相似度值的l2范數(shù)約束,用于規(guī)避平凡解并引導(dǎo)模型未知量具有光滑的數(shù)值結(jié)構(gòu).

文獻(xiàn)[14]等聚類算法通過投影矩陣進(jìn)行特征提取,相比較而言,公式(10)采用特征選擇操作擁有的優(yōu)勢(shì)包括:(1) 所采用的矢量操作較特征提取算法的特征分解操作效率更高;(2) 對(duì)于輸入數(shù)據(jù)不同特征的支撐作用具有更加明確的物理意義;(3) 可以在不指定特征子集規(guī)模的前提下進(jìn)行加權(quán)賦值,而特征提取必須指定子空間維數(shù).此外,通過對(duì)公式(10)模型中相似矩陣S和特征權(quán)值矢量w進(jìn)行交替優(yōu)化,可同時(shí)實(shí)現(xiàn)流形結(jié)構(gòu)學(xué)習(xí)和聯(lián)合特征選擇.通過S的迭代更新和優(yōu)化,使得近鄰關(guān)系具有自適應(yīng)性,從而確保特征選擇及譜聚類不再基于固定不變的圖Laplacian結(jié)構(gòu).

與其他譜聚類算法相似,公式(10)得到的相似矩陣S不能直接用于數(shù)據(jù)聚類,需進(jìn)行譜分析且利用k-means得到聚類結(jié)果[32].根據(jù)定理1可知:當(dāng)Laplacian矩陣Ls的秩為n?c時(shí),則相應(yīng)的相似矩陣S恰好具有c分簇對(duì)角結(jié)構(gòu),無需額外的k-means操作.為實(shí)現(xiàn)該目標(biāo),將文獻(xiàn)[20]中的低秩約束(即公式(3))引入公式(10),則有:

其中,rank(Ls)=n?c約束項(xiàng)與定理1中的零特征值重根數(shù)等價(jià).然而,直接對(duì)公式(11)求解非常困難[21],本文根據(jù)命題1進(jìn)一步將公式(11)調(diào)整為

其中,符號(hào)tr是矩陣的跡,F∈Rn×c是Laplacian矩陣Ls相應(yīng)c個(gè)最小特征值的特征矢量.公式(12)是最后的LRAFL模型目標(biāo)函數(shù),基于自適應(yīng)鄰域?qū)W習(xí)構(gòu)建圖Laplacian矩陣,將低維嵌入、特征選擇和譜聚類納入同一框架,并添加非負(fù)加和約束以及等價(jià)低秩約束,模型結(jié)果具有明確的塊對(duì)角結(jié)構(gòu).

定理1[21,32].相似矩陣S對(duì)應(yīng)的拉普拉斯矩陣Ls中,特征值為0的重根數(shù)與相似矩陣S中塊結(jié)構(gòu)的數(shù)量相等.

命題1.最小化Tr(FTLsF)與rank(Ls)=n?c具有等價(jià)性,其中,F∈Rn×c.

證明:假設(shè)σi(Ls)是Laplacian矩陣第i小的特征值,根據(jù)拉普拉斯矩陣的半正定性[32],σi(Ls)≥0成立,因此對(duì)Ls秩約束為n?c等同于約束.再根據(jù)Ky Fan定理[34],即:

2.2 模型優(yōu)化求解

在公式(12)中,相似矩陣S和特征權(quán)值向量w相互耦合,投影矩陣F的構(gòu)建又依賴于相似矩陣和拉普拉斯矩陣,因此不能直接對(duì)其求取閉合解.本節(jié)采用交替優(yōu)化的方法,依次對(duì)不同未知變量進(jìn)行單變量優(yōu)化,其中,每一次迭代都是一個(gè)凸優(yōu)化過程.

首先,當(dāng)固定相似矩陣S時(shí),則F由Ls的前c個(gè)最小特征值所對(duì)應(yīng)的特征向量構(gòu)成,因此F也是固定矩陣.Ls是一個(gè)實(shí)對(duì)稱半正定矩陣,通過奇異值分解可得到Ls=LLT.從而,目標(biāo)函數(shù)(12)可以調(diào)整為

其中,W是以w為對(duì)角元素的對(duì)角矩陣,Y=XL,而yij是Y矩陣對(duì)應(yīng)的元素.公式(13)是一個(gè)典型的二次規(guī)劃問題,常見的數(shù)值最優(yōu)化技術(shù)包括內(nèi)映射牛頓法、有效集算法等[35]都能夠?qū)χM(jìn)行迭代優(yōu)化獲得特征權(quán)值矢量w.為進(jìn)一步提升效率,本文提出一種閉式求解方案,將公式(13)進(jìn)一步調(diào)整為

綜上所述,完整的LRAFL如算法1描述.值得注意的是:在公式(12)目標(biāo)函數(shù)下,如忽略算法1的迭代框架,即先令sij=1,依公式(13)求解特征權(quán)值w;再固定w,聯(lián)合優(yōu)化S和F,可得到LRAFL模型的獨(dú)立優(yōu)化版(Ind),獲得目標(biāo)函數(shù)的快速解.然而該版本以模型次優(yōu)性為代價(jià),其實(shí)際應(yīng)用性能弱于算法1.為有效平衡模型的實(shí)施性能和運(yùn)行效率,通過設(shè)置收斂條件(見第3節(jié)描述),可使模型在Im<15次迭代內(nèi)停止.

算法1.LRAFL描述.

輸入:數(shù)據(jù)集X,聚類目標(biāo)c,迭代總數(shù)Im,平衡參數(shù)γ,β,λ,有效特征數(shù)d;

輸出:具有c分塊對(duì)角結(jié)構(gòu)的相似矩陣S,特征加權(quán)向量w.

1.初始化特征加權(quán)向量w0,設(shè)λ=0,通過公式(20)得到初始相似矩陣S0,并計(jì)算投影矩陣F0;

2.設(shè)迭代次數(shù)t=1;

3.固定相似矩陣和投影矩陣,依公式(15)計(jì)算特征加權(quán)向量wt,其中,Ls=D?S;

4.固定wt,根據(jù)公式(20)更新相似矩陣St并計(jì)算投影矩陣Ft;

5.如滿足收斂條件或迭代t≥Im,則輸出結(jié)果,算法中止;反之,令t=t+1,轉(zhuǎn)至第3步.

3 LRAFL算法描述

通過算法1可見,LRAFL在實(shí)施過程中包含平衡參數(shù)γ,β,λ以及有效特征數(shù)d等待定參數(shù),各類參數(shù)的優(yōu)選過程不僅耗時(shí)而且對(duì)算法在不同數(shù)據(jù)集中的輸出效果影響較大.因此,分析不同參數(shù)的具體實(shí)現(xiàn)推薦值是一個(gè)公知問題.此外,算法的收斂性和復(fù)雜度分析也對(duì)其具體的應(yīng)用推廣有著較大的影響.

3.1 參數(shù)設(shè)定細(xì)節(jié)

從公式(15)可見,特征加權(quán)向量w的取值由有效特征數(shù)d∈(0,m]和正則項(xiàng)平衡參數(shù)γ>0決定.具體實(shí)施過程中,可根據(jù)輸入數(shù)據(jù)對(duì)其中一個(gè)參數(shù)進(jìn)行指示推薦,減少算法的計(jì)算開銷.首先,當(dāng)輸入純凈數(shù)據(jù)時(shí),可以認(rèn)為所有的特征都是有效的,不同維數(shù)依wi的取值具有不同的貢獻(xiàn)度,即d=m.不失一般性,假設(shè)w1≥w2≥…≥wm≥0按照從大到小的順序排列,依特征加權(quán)的非負(fù)性,令wm>0,則有:

將其中的γ代入公式(15),得到w的最終計(jì)算方法為

其中,僅存的人工設(shè)定參數(shù)d具有明確的物理意義,可依據(jù)輸入數(shù)據(jù)按經(jīng)驗(yàn)設(shè)定.

從公式(20)可見,相似矩陣中列向量si的取值由正則項(xiàng)參數(shù)βi>0決定.一般情況下,當(dāng)?shù)玫降南嗨凭仃嘢全連通時(shí),根據(jù)定理1可知數(shù)據(jù)為單簇結(jié)構(gòu),無法直接獲得F∈Rn×c矩陣.此外,在實(shí)際應(yīng)用中,數(shù)據(jù)局部鄰域關(guān)系更能刻畫本質(zhì)結(jié)構(gòu),往往僅考慮數(shù)據(jù)點(diǎn)xi的k個(gè)鄰域樣本而非所有輸入數(shù)據(jù)進(jìn)行連接,而且稀疏的相似矩陣還能有效降低后續(xù)過程的計(jì)算量.因此,公式(20)中的n可由k替代且k<

由于k是正整數(shù)并且有明確的物理意義,因此公式(20)僅需調(diào)整k求相似度矩陣,比直接調(diào)整β更為便捷.

從命題1可知,Tr(FTLsF)與rank(Ls)=n?c等價(jià),因此在目標(biāo)函數(shù)的更新過程中,取足夠大的λ參數(shù)值時(shí),Tr(FTLsF)無限接近于0,可直接獲得具有c分簇結(jié)構(gòu)的相似矩陣S.因此,λ的取值可在算法運(yùn)行中自適應(yīng)確定,隨機(jī)給定一個(gè)初始化值λ(如λ=β),每次迭代計(jì)算投影矩陣后,分別計(jì)算.給定接近于0的常數(shù)ε(本文選為1e?10),當(dāng)ρ1>ε時(shí),說明Tr(FTLsF)值不夠接近于0,則增加λ值;反之,當(dāng)ρ2<ε時(shí),說明Tr(FTLsF)值過小,則減少λ值;當(dāng)ρ1<ε<ρ2時(shí),說明Ls矩陣恰好具有c塊對(duì)角結(jié)構(gòu),模型收斂.

綜上所述,雖然在算法1的描述中LRAFL有4個(gè)待設(shè)參數(shù),但算法具體實(shí)施過程中僅d(或γ)值和k值需要作調(diào)整測試,而且各參數(shù)都有明確的意義和設(shè)置推薦,保證算法應(yīng)用過程的快速實(shí)現(xiàn).

3.2 收斂性和復(fù)雜度分析

LRAFL采用交替更新法進(jìn)行模型迭代求解,在固定部分變量的前提下優(yōu)化余下未知變量.根據(jù)算法1的描述,每次迭代的關(guān)鍵步驟公式(15)和公式(20)都是閉式解,因此其單個(gè)變量更新是唯一解.命題2說明所提算法在迭代過程中使目標(biāo)函數(shù)(12)的值逐步下降,并最終收斂.

命題2.算法1的目標(biāo)函數(shù)值隨迭代過程逐步下降.

證明:假設(shè)在迭代t時(shí)有相似矩陣St,則在t+1次迭代中,固定St并優(yōu)化Ft+1和wt+1,以下不等式成立:

類似地,在固定Ft+1和wt+1時(shí)優(yōu)化相似矩陣,則有不等式:

聯(lián)合公式(28)和公式(29)可知,目標(biāo)函數(shù)(12)的值隨迭代過程逐步下降,命題2得證.□

值得注意的是:為避免LRAFL算法進(jìn)入局部收斂,可以嘗試不同的初始化方案,例如w可以簡單地初始化為元素值為1/d的列向量,亦可在非負(fù)加和約束下取隨機(jī)值.此外,還可以在迭代循環(huán)外先初始化相似矩陣S,包括k近鄰法或ε鄰域法等,依不同輸入數(shù)據(jù)集嘗試不同的初始化方案,能使LRAFL有效逼近全局最優(yōu)解.

算法1的關(guān)鍵耗時(shí)步驟是3個(gè)未知變量的更新操作,包括w,S和F.其中,w依公式(15)計(jì)算,其運(yùn)算復(fù)雜度是O(d);S中的列向量依公式(20)計(jì)算,其運(yùn)算復(fù)雜度是O(k),因此相似矩陣S的整體復(fù)雜度是O(k2);投影矩陣F通過Laplacian矩陣的特征分解獲得,其復(fù)雜度是O(n3).一般情況下,d<

4 LRAFL算法描述

4.1 合成數(shù)據(jù)實(shí)驗(yàn)

首先人工產(chǎn)生了5類獨(dú)立的子空間,其環(huán)境維數(shù)為250,本質(zhì)維數(shù)為4.對(duì)任意子空間,隨機(jī)產(chǎn)生100個(gè)單位樣本并將其中的50%疊加高斯噪聲干擾,噪聲等級(jí)為{0,0.3,0.6}.圖1顯示了幾種具有相似性矩陣構(gòu)建能力的聚類算法所生成的鄰域圖,包括LPS[13],RSS[25],LRS[24]和LRAFL.

Fig.1 Affinity on synthesized data with different levels of noise corruption圖1 五簇合成數(shù)據(jù)在不同噪聲等級(jí)下的相似性結(jié)構(gòu)

其中,圖1(a)～圖1(c)分別是無噪聲干擾、30%噪聲干擾和60%噪聲干擾下的效果,所有算法的參數(shù)優(yōu)選過程遵從第4.2節(jié)的描述.從圖1可見:在第1行無噪聲干擾環(huán)境下,4種算法都獲得了高質(zhì)量的相似度矩陣,為實(shí)現(xiàn)高性能的聚類結(jié)果奠定基礎(chǔ).然而,隨著高斯噪聲的引入,LRS的相似矩陣完全處于紊亂狀態(tài),無法體現(xiàn)5分簇結(jié)構(gòu).類似地,LPS的相似矩陣也趨于模糊,由5分簇結(jié)構(gòu)逐漸退化為3分簇結(jié)構(gòu);RSS的關(guān)聯(lián)矩陣在趨于模糊的基礎(chǔ)上,不同組結(jié)構(gòu)的相似度值亦呈現(xiàn)不平衡特性.對(duì)比可見:所提算法LRAFL具有更為清晰的5簇相似度矩陣,受噪聲干擾的影響小于其他幾種算法.值得注意的是:從圖1(a.3)可見,LRS在干凈環(huán)境下的相似矩陣非常清晰.然而,其類內(nèi)相似度完全一致,說明LRS對(duì)同簇?cái)?shù)據(jù)不具備多態(tài)區(qū)分性,解釋了其較弱的抗噪能力.

為進(jìn)一步說明LRAFL的特征選擇和數(shù)據(jù)聚類能力,采用人造的雙半環(huán)數(shù)據(jù)進(jìn)行效果驗(yàn)證.數(shù)據(jù)分為2簇,每簇100個(gè)樣本點(diǎn)并隨機(jī)疊加15%的高斯白噪聲.圖2顯示了LRAFL在不同位置分布情形下的雙半環(huán)數(shù)據(jù)特征選擇結(jié)果,其中,圖2(a)將數(shù)據(jù)左右放置,圖2(b)將其投影至高特征權(quán)值對(duì)應(yīng)的坐標(biāo)軸,圖2(c)是上下分布的數(shù)據(jù),圖2(d)同理將其投影至高權(quán)值對(duì)應(yīng)的坐標(biāo).可見:當(dāng)輸入數(shù)據(jù)分別處于左右和上下分布時(shí),LRAFL分別以橫坐標(biāo)和縱坐標(biāo)作為高權(quán)值特征,說明其具有鑒別特征選擇效果.此外,圖3將雙半環(huán)數(shù)據(jù)交叉放置,并采用RSS,LRS和LRAFL進(jìn)行聚類對(duì)比,從中可見RSS和LRS兩者的聚類結(jié)果都存在明顯的錯(cuò)誤,而LRAFL的聚類結(jié)果與輸入簇結(jié)構(gòu)完全吻合,表明其成功地將原始數(shù)據(jù)分成了2個(gè)類別,聚類效果優(yōu)于RSS和LRS.

Fig.2 Feature selection of LRAFL under different distribution of two-moon synthetic data圖2 不同位置分布情形下的雙半環(huán)數(shù)據(jù)特征選擇結(jié)果

Fig.3 Clustering results on the two-moon synthetic data by RSS,LRS,and LRAFL圖3 交叉分布情形下的雙半環(huán)數(shù)據(jù)聚類效果對(duì)比

4.2 真實(shí)數(shù)據(jù)實(shí)驗(yàn)

通過7個(gè)不同的數(shù)據(jù)集和11種算法驗(yàn)證LRAFL模型的聚類性能,即準(zhǔn)確度(AC)[25]和歸一化互信息(NMI)[31]兩個(gè)指標(biāo).測試數(shù)據(jù)包含3個(gè)人臉數(shù)據(jù)集(Orl,YaleB[23],Jaffe[12])、1個(gè)語音字母數(shù)據(jù)集(Isolet)、2個(gè)生物數(shù)據(jù)集(Yeast,Lung)和1個(gè)對(duì)象數(shù)據(jù)集(Coil[12]).為方便橫向?qū)Ρ?所有帶參考文獻(xiàn)的數(shù)據(jù)集都依原文進(jìn)行預(yù)處理,余下數(shù)據(jù)則保持原始形式.表1給出了各數(shù)據(jù)集的細(xì)節(jié)描述.對(duì)比算法包含LLCFS[11],MCFS[8],NDFS[15],FSASL[12],LPS[13],kmeans[32],DEC[14],SMR[23],LRS[24],RSS[25]和NSLLRR[22].

Table 1 Summary of the benchmark datasets and the number of selected features表1 數(shù)據(jù)集描述和實(shí)驗(yàn)中的特征選擇數(shù)

為獲得各算法的最優(yōu)實(shí)驗(yàn)結(jié)果,在實(shí)現(xiàn)時(shí),需要對(duì)其人工參數(shù)進(jìn)行網(wǎng)格搜索.在實(shí)驗(yàn)中,所有算法的正則參數(shù)和鄰域參數(shù)范圍分別設(shè)為{10?2,…,102}和{3,6,9,12,15}.表2和表3分別給出了所有對(duì)比算法通過10次隨機(jī)初始化獲得的準(zhǔn)確度和歸一化互信息指標(biāo).圖4列出了各算法的平均AC和NMI指標(biāo).

Table 2 Aggregated clustering results measured by AC (%) of the competing methods表2 所有算法在不同數(shù)據(jù)集下的聚類準(zhǔn)確度指標(biāo)對(duì)比

Table 3 Aggregated clustering results measured by NMI (%) of the competing methods表3 所有算法在不同數(shù)據(jù)集下的聚類互信息指標(biāo)對(duì)比

Fig.4 Average clustering results measured by AC and NMI (%) of the competing methods圖4 各算法的平均聚類準(zhǔn)確度和歸一化互信息對(duì)比

從表2和表3可知,

· 首先,依據(jù)樣本的分布結(jié)構(gòu)及特征量差異,各算法的聚類性能落差較大.例如:Yeast數(shù)據(jù)集的維數(shù)較低,其類間間隔相對(duì)緊湊;而YaleB,Orl受光照、表情等影響較大.LRAFL在這3個(gè)數(shù)據(jù)集中的AC指標(biāo)分別僅為49.73%,63.44%和61.50%.此外,Lung和Jaffe因?yàn)榫哂兄庇^的分布結(jié)構(gòu)比較容易實(shí)現(xiàn)聚類,其對(duì)應(yīng)的LRAFL聚類AC指標(biāo)分別達(dá)到了92.66%和99.20%;

· 其次,對(duì)比經(jīng)典的k-means算法,DEC,NDFS和FSASL等特征選擇型算法都提升了聚類性能,而重構(gòu)表示型算法,如SMR和NSLLRR則具有更加優(yōu)秀的結(jié)果.RSS受表示系數(shù)次優(yōu)解影響,性能落差較大,在YaleB中獲得了65.78%的最高聚類精度,但在Jaffe和Orl中則僅獲得了32.39%和21.25%的AC結(jié)果,遜于基準(zhǔn)模型k-means;

· 最后,LRAFL兼顧了特征優(yōu)選機(jī)制和塊對(duì)角Laplacian目標(biāo)矩陣,其綜合性能優(yōu)于其他算法,在AC和NMI中分別贏得了4個(gè)和6個(gè)最高值,尤其在Jaffe和Coil中,分別獲得了98.76%和97.05%的最高NMI.圖4進(jìn)一步表明,LRAFL在各數(shù)據(jù)上的綜合AC和NMI指標(biāo)高于其他算法.

LRAFL聚類模型包含特征優(yōu)選權(quán)值w和簇結(jié)構(gòu)逼近投影矩陣F用于塊對(duì)角結(jié)構(gòu)的相似度矩陣S構(gòu)建.為進(jìn)一步評(píng)估各子項(xiàng)的貢獻(xiàn)度以及聯(lián)合w,S迭代更新的優(yōu)勢(shì),將LRAFL算法分為無特征權(quán)值版(Nw)、無投影矩陣版(NF)、獨(dú)立優(yōu)化版Ind以及原始LRAFL模型(Ori),其中,Nw是對(duì)目標(biāo)函數(shù)式(12)中的特征加權(quán)部分去除,聯(lián)合優(yōu)化S和F;NF指剔除公式(12)中的投影矩陣F,聯(lián)合優(yōu)化w和S.圖5對(duì)比了4個(gè)版本在真實(shí)數(shù)據(jù)集中的準(zhǔn)確度和歸一化互信息指標(biāo).從圖5可知,LRAFL原始版在所有測試數(shù)據(jù)中的聚類指標(biāo)都高于其減化版本.此外,NF在各LRAFL減化版中效果最差,說明塊對(duì)角Laplacian矩陣結(jié)構(gòu)對(duì)聚類問題的關(guān)鍵性,與正文理論分析一致;Nw版的聚類效果略遜于Ind版,說明特征優(yōu)選機(jī)制能改善聚類分析效果;最后,Ind版與Ori版的性能差距則進(jìn)一步驗(yàn)證了LRAFL模型聯(lián)合迭代更新的優(yōu)勢(shì).

Fig.5 Clustering accuracy and NMI w.r.t.different versions of LRAFL圖5 不同版本的LRAFL算法準(zhǔn)確度和歸一化互信息對(duì)比

為進(jìn)一步驗(yàn)證所提算法性能在不同特征選擇量下的表現(xiàn),圖6將LRAFL與其他幾種性能較優(yōu)的特征選擇算法進(jìn)行對(duì)比,包括MCFS,NDFS,FSASL和DEC,選用的數(shù)據(jù)集為Jaffe和Lung,其中,前者的特征維數(shù)較少(676),后者的特征維數(shù)較高(3 312).從圖6可見,LRAFL在不同特征空間中的AC和NMI指標(biāo)都優(yōu)于其他算法,說明自適應(yīng)特征學(xué)習(xí)機(jī)制能夠有效地區(qū)分輸入高維特征的優(yōu)劣,進(jìn)一步優(yōu)化性能.隨著有效特征維數(shù)的增加,不同算法的聚類性能都有所提升.然而,當(dāng)維數(shù)進(jìn)一步增加時(shí),冗余特征導(dǎo)致算法的性能不增反降.相比較而言,LRAFL除特征選擇之外又添加了特征有效性加權(quán)機(jī)制,因此其精度曲線較為平坦.

Fig.6 Clustering accuracy and NMI w.r.t.different selected features圖6 不同特征尋優(yōu)下的分簇準(zhǔn)確度和歸一化互信息對(duì)比

Fig.6 Clustering accuracy and NMI w.r.t.different selected features (Continued)圖6 不同特征尋優(yōu)下的分簇準(zhǔn)確度和歸一化互信息對(duì)比(續(xù))

4.3 算法效率分析

運(yùn)行效率是算法應(yīng)用能力的另一關(guān)鍵指標(biāo),本節(jié)選擇在不同數(shù)據(jù)集中綜合聚類性能表現(xiàn)較為突出的幾種算法進(jìn)行計(jì)算效率對(duì)比.指標(biāo)測試時(shí)含參數(shù)優(yōu)選過程,表4顯示了各算法在各數(shù)據(jù)中的運(yùn)行時(shí)間(單位:s).

算法運(yùn)行平臺(tái)為Intel Core i5 CPU,雙核主頻2.80GHz,內(nèi)存4GB,32位Win7操作系統(tǒng)和Matlab2014b軟件環(huán)境.

根據(jù)表4結(jié)果并結(jié)合表2、表3可知:LRAFL不僅在綜合聚類效果上優(yōu)于對(duì)比算法,而且其運(yùn)行效率也具有明顯的優(yōu)越性.以Jaffe為例,LRAFL僅需要4.76s完成參數(shù)優(yōu)選和聚類分析運(yùn)算,而排名第2的NDFS算法則耗費(fèi)了近80s時(shí)間.此外,部分表示型聚類算法,如SMR,RSS和NSLLRR,以運(yùn)行效率為代價(jià),在YaleB,ISOLET等數(shù)據(jù)集中取得了較LRAFL略優(yōu)的聚類效果,但從表4可見,其運(yùn)行時(shí)間呈指數(shù)級(jí)增長,基本較LRFAL慢10倍以上,尤其是NSLLRR模型,其綜合聚類性能高于除LRAFL的其他對(duì)比算法,但是受非負(fù)系數(shù)矩陣構(gòu)建以及多個(gè)人工可調(diào)參數(shù)影響,運(yùn)行效率遠(yuǎn)遠(yuǎn)低于所有競爭算法,嚴(yán)重影響其應(yīng)用擴(kuò)展能力.

Table 4 Aggregated results measured by elapsed time of the competing methods表4 所有算法在不同數(shù)據(jù)集下的運(yùn)行效率對(duì)比

4.4 參數(shù)敏感度分析

根據(jù)上述實(shí)驗(yàn)結(jié)果所示,所有聚類算法都有不同的人設(shè)參數(shù)待選,對(duì)算法應(yīng)用效果和效率都有極大的影響.因此,所提算法的參數(shù)個(gè)數(shù)及其對(duì)不同設(shè)定值的敏感性是影響算法應(yīng)用能力的又一指標(biāo).LRAFL算法有兩個(gè)待選參數(shù)——鄰域數(shù)k和正則數(shù)γ,圖7給出了其在不同選值范圍下的聚類準(zhǔn)確度性能變化,選用的數(shù)據(jù)集包括YaleB,Jaffe,Yeast和Orl.

從圖7結(jié)果可知:LRAFL算法的兩個(gè)參數(shù)中,γ對(duì)不同選值的敏感度較小,而且其選擇過程也較為直觀.本文采用2x<300取值,其中,x∈{?1,2,4,8,16}.k對(duì)不同選值的敏感度較大,但具體應(yīng)用過程中,k的取值范圍非常清晰,一般以10為中心向兩邊測試,減少了應(yīng)用難度.此外,鄰域數(shù)k是所有算法的待定參數(shù),如何對(duì)其進(jìn)行優(yōu)選仍是一個(gè)公知問題.

Fig.7 Clustering accuracy of LRAFL w.r.t.different parameters圖7 LRAFL參數(shù)優(yōu)選下的聚類準(zhǔn)確度

5 總結(jié)

本文提出了一種新的數(shù)據(jù)聚類算法LRAFL,兼顧自適應(yīng)特征優(yōu)選和簇結(jié)構(gòu)學(xué)習(xí)兩個(gè)關(guān)鍵目標(biāo).特征優(yōu)選通過輸入數(shù)據(jù)的重構(gòu)表示進(jìn)行自適應(yīng)權(quán)值計(jì)算,并依權(quán)值高低進(jìn)行有效特征篩選.簇結(jié)構(gòu)學(xué)習(xí)通過對(duì)Laplacian矩陣強(qiáng)制進(jìn)行c秩約束,獲得精確的數(shù)據(jù)相似度矩陣,直接進(jìn)行c簇結(jié)構(gòu)劃分.LRAFL能夠同時(shí)進(jìn)行特征選擇和數(shù)據(jù)聚類,且模型待設(shè)參數(shù)的物理意義明確,實(shí)現(xiàn)過程簡潔直觀.此外,設(shè)計(jì)了一種快速高效的模型求解算法,并給出了相應(yīng)的算法復(fù)雜度分析和收斂性分析.通過大量人工合成數(shù)據(jù)和現(xiàn)實(shí)公開數(shù)據(jù)集驗(yàn)證了所提算法在精度、歸一化互信息、運(yùn)行效率和參數(shù)敏感度上較現(xiàn)存算法具有明顯的優(yōu)勢(shì).對(duì)比特征選擇型算法,LRAFL在聚類效果和運(yùn)行效率上都具有優(yōu)越的實(shí)驗(yàn)結(jié)果;對(duì)比表示型算法,LRAFL雖然在部分?jǐn)?shù)據(jù)集中無法獲得更高的精度指標(biāo),但其運(yùn)行效率卻具有指數(shù)級(jí)的提升.

通過實(shí)驗(yàn)發(fā)現(xiàn),所提算法LRAFL在應(yīng)用過程中需要人工設(shè)定參數(shù)k和γ,雖然可以通過經(jīng)驗(yàn)方式進(jìn)行指引設(shè)置,且γ的取值對(duì)最終結(jié)果的影響較小,但仍然會(huì)削弱所提算法的應(yīng)用擴(kuò)展能力.因此,后續(xù)將集中進(jìn)行待定參數(shù)的自適應(yīng)確定或參數(shù)簡化工作.此外,各聚類算法在不同的數(shù)據(jù)集中表現(xiàn)差異較大,不同先驗(yàn)樣本分布對(duì)算法的性能影響仍不清楚,對(duì)其進(jìn)行理論分析也是后續(xù)的工作之一.