聯合Laplacian正則項和特征自適應的數據聚類算法?

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

1(浙江工業大學 計算機科學與技術學院,浙江 杭州 310023)

2(浙江大學城市學院 計算機與計算科學學院,浙江 杭州 310015)

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

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

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

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

1) 提出一種圖Laplacian矩陣更新策略,保證其秩結構與目標聚類數的一致性,使得模型優化結果直接具備分簇塊對角結構,規避了后續k-means、譜分解等操作;

2) 將特征學習機制融入Laplacian矩陣構建框架,在保證噪聲特征抑制的前提下,去除高復雜度的表示系數學習過程,提升模型求解效率;

3) 設計具備唯一最優解的參數優化方案,對模型部分待定參數進行推演分析,給出更具指示意義的設定方法,進一步加速模型實現效率.

1 相關工作

本節介紹譜聚類算法中的兩個關鍵步驟,即相似度矩陣構建和拉普拉斯正則約束項,其中,前者用于挖掘數據分布結構,而后者是引導塊對角狀態的核心技術.

1.1 相似度矩陣構建

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

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

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

1.2 Laplacian正則約束

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

最近,Hu等人[23]以譜聚類為基礎,結合低秩重構表示思想將一般的表示型譜聚類模型歸納為

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

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

其中,c表示對角塊的個數,也即簇目標數.將上述秩約束添加至子空間聚類模型,可保證清晰的塊對角結構,具體目標模型描述為

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

2 LRAFL算法描述

結合現有工作,考慮到自適應鄰域學習和塊對角Laplacian矩陣對聚類效果的重要性以及自表示學習的復雜性,本節將公式(1)和公式(4)中的表示系數轉變為鄰域結構約束,并輔以稀疏性、參數自學習、特征尋優以及簇結構直接確定等優勢,提出一種兼顧特征選擇和譜聚類的算法LRAFL.首先對該算法目標函數的構建過程進行描述,然后給出了模型求解優化方案.

2.1 目標函數構建

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

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

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

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

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

其次,為引入特征優選機制,使算法具有奇異特征抑制性能,采用特征加權因子w∈Rm×1將公式(8)調整為

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

其中,d≤m表示選擇后有效特征數.公式(10)第1部分用于相似度矩陣構建,子項在特征優選約束下,使鄰近的樣本對具有更高的相似度權值,而非近鄰樣本對具有較低的相似度權值,余下部分是特征加權矢量和相似度值的l2范數約束,用于規避平凡解并引導模型未知量具有光滑的數值結構.

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

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

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

其中,符號tr是矩陣的跡,F∈Rn×c是Laplacian矩陣Ls相應c個最小特征值的特征矢量.公式(12)是最后的LRAFL模型目標函數,基于自適應鄰域學習構建圖Laplacian矩陣,將低維嵌入、特征選擇和譜聚類納入同一框架,并添加非負加和約束以及等價低秩約束,模型結果具有明確的塊對角結構.

定理1[21,32].相似矩陣S對應的拉普拉斯矩陣Ls中,特征值為0的重根數與相似矩陣S中塊結構的數量相等.

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

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

2.2 模型優化求解

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

首先,當固定相似矩陣S時,則F由Ls的前c個最小特征值所對應的特征向量構成,因此F也是固定矩陣.Ls是一個實對稱半正定矩陣,通過奇異值分解可得到Ls=LLT.從而,目標函數(12)可以調整為

其中,W是以w為對角元素的對角矩陣,Y=XL,而yij是Y矩陣對應的元素.公式(13)是一個典型的二次規劃問題,常見的數值最優化技術包括內映射牛頓法、有效集算法等[35]都能夠對之進行迭代優化獲得特征權值矢量w.為進一步提升效率,本文提出一種閉式求解方案,將公式(13)進一步調整為

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

算法1.LRAFL描述.

輸入:數據集X,聚類目標c,迭代總數Im,平衡參數γ,β,λ,有效特征數d;

輸出:具有c分塊對角結構的相似矩陣S,特征加權向量w.

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

2.設迭代次數t=1;

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

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

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

3 LRAFL算法描述

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

3.1 參數設定細節

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

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

其中,僅存的人工設定參數d具有明確的物理意義,可依據輸入數據按經驗設定.

從公式(20)可見,相似矩陣中列向量si的取值由正則項參數βi>0決定.一般情況下,當得到的相似矩陣S全連通時,根據定理1可知數據為單簇結構,無法直接獲得F∈Rn×c矩陣.此外,在實際應用中,數據局部鄰域關系更能刻畫本質結構,往往僅考慮數據點xi的k個鄰域樣本而非所有輸入數據進行連接,而且稀疏的相似矩陣還能有效降低后續過程的計算量.因此,公式(20)中的n可由k替代且k<

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

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

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

3.2 收斂性和復雜度分析

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

命題2.算法1的目標函數值隨迭代過程逐步下降.

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

類似地,在固定Ft+1和wt+1時優化相似矩陣,則有不等式:

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

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

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

4 LRAFL算法描述

4.1 合成數據實驗

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

Fig.1 Affinity on synthesized data with different levels of noise corruption圖1 五簇合成數據在不同噪聲等級下的相似性結構

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

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

Fig.2 Feature selection of LRAFL under different distribution of two-moon synthetic data圖2 不同位置分布情形下的雙半環數據特征選擇結果

Fig.3 Clustering results on the two-moon synthetic data by RSS,LRS,and LRAFL圖3 交叉分布情形下的雙半環數據聚類效果對比

4.2 真實數據實驗

通過7個不同的數據集和11種算法驗證LRAFL模型的聚類性能,即準確度(AC)[25]和歸一化互信息(NMI)[31]兩個指標.測試數據包含3個人臉數據集(Orl,YaleB[23],Jaffe[12])、1個語音字母數據集(Isolet)、2個生物數據集(Yeast,Lung)和1個對象數據集(Coil[12]).為方便橫向對比,所有帶參考文獻的數據集都依原文進行預處理,余下數據則保持原始形式.表1給出了各數據集的細節描述.對比算法包含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 數據集描述和實驗中的特征選擇數

為獲得各算法的最優實驗結果,在實現時,需要對其人工參數進行網格搜索.在實驗中,所有算法的正則參數和鄰域參數范圍分別設為{10?2,…,102}和{3,6,9,12,15}.表2和表3分別給出了所有對比算法通過10次隨機初始化獲得的準確度和歸一化互信息指標.圖4列出了各算法的平均AC和NMI指標.

Table 2 Aggregated clustering results measured by AC (%) of the competing methods表2 所有算法在不同數據集下的聚類準確度指標對比

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

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

從表2和表3可知,

· 首先,依據樣本的分布結構及特征量差異,各算法的聚類性能落差較大.例如:Yeast數據集的維數較低,其類間間隔相對緊湊;而YaleB,Orl受光照、表情等影響較大.LRAFL在這3個數據集中的AC指標分別僅為49.73%,63.44%和61.50%.此外,Lung和Jaffe因為具有直觀的分布結構比較容易實現聚類,其對應的LRAFL聚類AC指標分別達到了92.66%和99.20%;

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

· 最后,LRAFL兼顧了特征優選機制和塊對角Laplacian目標矩陣,其綜合性能優于其他算法,在AC和NMI中分別贏得了4個和6個最高值,尤其在Jaffe和Coil中,分別獲得了98.76%和97.05%的最高NMI.圖4進一步表明,LRAFL在各數據上的綜合AC和NMI指標高于其他算法.

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

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

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

Fig.6 Clustering accuracy and NMI w.r.t.different selected features圖6 不同特征尋優下的分簇準確度和歸一化互信息對比

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

4.3 算法效率分析

運行效率是算法應用能力的另一關鍵指標,本節選擇在不同數據集中綜合聚類性能表現較為突出的幾種算法進行計算效率對比.指標測試時含參數優選過程,表4顯示了各算法在各數據中的運行時間(單位:s).

算法運行平臺為Intel Core i5 CPU,雙核主頻2.80GHz,內存4GB,32位Win7操作系統和Matlab2014b軟件環境.

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

Table 4 Aggregated results measured by elapsed time of the competing methods表4 所有算法在不同數據集下的運行效率對比

4.4 參數敏感度分析

根據上述實驗結果所示,所有聚類算法都有不同的人設參數待選,對算法應用效果和效率都有極大的影響.因此,所提算法的參數個數及其對不同設定值的敏感性是影響算法應用能力的又一指標.LRAFL算法有兩個待選參數——鄰域數k和正則數γ,圖7給出了其在不同選值范圍下的聚類準確度性能變化,選用的數據集包括YaleB,Jaffe,Yeast和Orl.

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

Fig.7 Clustering accuracy of LRAFL w.r.t.different parameters圖7 LRAFL參數優選下的聚類準確度

5 總結

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

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