李玲俐
摘要:由于性能優(yōu)越,譜聚類成為近年來聚類算法研究的熱點。譜聚類算法可以在任意形狀的樣本空間上聚類,并能獲得全局最優(yōu)解。介紹了譜圖的基本理論及其劃分準則,探討了譜聚類算法,并針對當(dāng)前譜聚類應(yīng)用展望了未來研究方向。
關(guān)鍵詞關(guān)鍵詞:譜聚類;譜圖理論;圖劃分;應(yīng)用研究
DOIDOI:10.11907/rjdk.161229
中圖分類號:TP312文獻標識碼:A文章編號文章編號:16727800(2016)007005403
0引言
聚類就是按照事物的某些特征,把事物分成若干類或簇,使得在同一個類內(nèi)的對象之間最大程度相似,而不同類之間的對象最大程度不同。聚類分析在數(shù)據(jù)挖掘、空間數(shù)據(jù)處理、金融數(shù)據(jù)分類和入侵檢測技術(shù)等領(lǐng)域中都得到了廣泛應(yīng)用。傳統(tǒng)的聚類算法,如Kmeans和模糊C均值算法(Fuzzy CMeans,F(xiàn)CM)等大都建立在凸球形樣本空間上,如果樣本空間不為凸,算法就會陷入局部最優(yōu)。因此,學(xué)者們開始研究一種新的聚類方法——譜聚類(Spectral Clustering,SC)算法。該算法由給定的樣本數(shù)據(jù)集定義一個描述數(shù)據(jù)點之間相似度的親和矩陣,并計算矩陣的特征值和特征向量,再選擇合適的特征向量聚類不同的數(shù)據(jù)點。譜聚類算法是一個判別式算法,其思想相對簡單易于實現(xiàn),具有識別非凸分布的聚類能力,適合處理許多實際應(yīng)用問題。本文著重介紹譜聚類的基本理論、算法描述、當(dāng)前應(yīng)用及未來研究方向。
1譜聚類基本理論與算法描述
1.1圖劃分原理
譜聚類是一種基于圖論的聚類方法。譜圖理論是將數(shù)據(jù)聚類問題轉(zhuǎn)化成圖的多路劃分問題,通過分割子圖來聚類數(shù)據(jù)點。譜聚類能對任意形狀的樣本空間聚類,并能獲得全局最優(yōu)解,其基本思想是通過對樣本數(shù)據(jù)的Laplacian(拉普拉斯)矩陣進行特征分解而得到的特征向量進行聚類。
4結(jié)語
針對kmeans算法易受初始聚類中心影響的問題,首先用人工魚群算法的全局尋優(yōu)能力搜索初始聚類中心。
為了處理大規(guī)模數(shù)據(jù),本文提出基于Mapreduce的afsa_km算法。實驗結(jié)果表明,并行化的afsa_km算法比kmeans算法有更高的準確率,基于Mapreduce實現(xiàn)的afsa_km算法具有良好的加速比和擴展性,效率也有很大提高。 假定將每個數(shù)據(jù)樣本看作圖中的頂點V,且樣本中的數(shù)據(jù)對之間都有一定的相似性,由樣本間的相似度,將頂點間的邊E賦權(quán)重值W,得到一個無向加權(quán)圖G=(V,E),V={v1,v2,...vn}表示點集。圖G中,可將聚類問題轉(zhuǎn)化為在圖G上的圖劃分問題。圖論中的劃分準則一般有Minimum Cut、Average Cut、Normalized Cut、Minmax Cut、Ratio Cut、MN Cut等,劃分準則的好壞對聚類結(jié)果的優(yōu)劣產(chǎn)生很大影響。
1.1.1最小割集準則(Minimum Cut)
譜圖分割過程中,圖的邊值代表頂點之間的相關(guān)性大小,假設(shè)G被劃分為A、B兩個子圖,最小割集的代價函數(shù)為:Cut(A,B)=∑i∈A,j∈BWij其中,A∩B=φ,A∪B=V,權(quán)重Wij表示Vi與Vj之間的關(guān)系。屬于子圖A的頂點和屬于子圖B的頂點之間的所有邊的和最小化,表示兩個子圖之間的相關(guān)性越小。Wu和Leahy[2]提出最小化上述Cut值來劃分圖G,即最小割集準則,是最常見也是最簡單的評價方法。用該準則對一些圖像進行分割也能產(chǎn)生不錯的效果。該準則的缺點是分割圖像時容易出現(xiàn)偏向小區(qū)域的情況。
1.1.2規(guī)范割集準則(Normalized Cut)
根據(jù)譜圖理論,Shi和Malik[3]提出新的目標代價函數(shù)NCut為:NCut(A,B)=Cut(A,B)Vol(A,V)+Cut(A,B)Vol(B,V)其中,Vol(A,V)
規(guī)范割集準則即最小化NCut函數(shù)。與Minimum Cut相比,該準則能平衡類內(nèi)樣本間的相似度,也能平衡類間樣本間的相異度,即可以避免偏向小區(qū)域分割。一般的聚類算法中,采用NCut準則的情況比較多。
1.1.3比例割集準則(Ratio Cut)
為兼顧孤立點和均衡化問題,Hagen和Kahng[4]提出了比例割集準則,其目標代價函數(shù)RCut為:RCut(A,B)=Cut(A,B)min(|A|,|B|)其中,|A|、|B|分別表示子圖A、B中頂點的個數(shù),Cut(A,B)是最小割集準則的代價函數(shù)。最小化RCut函數(shù)引入了一個規(guī)模參數(shù)作為分母,加大了類間相似性,減低了過分分割的可能性,這是優(yōu)于最小割集準則的方面,但該準則會使運行速度降低。
1.1.4平均割集準則(Average Cut)
Sarkar和Soundararajan[5]提出平均割集準則,其目標函數(shù)AvCut為:AvCut=Cut(A,B)|A|+Cut(A,B)|B|AvCut同NCut函數(shù)一樣,最小化目標函數(shù)都能產(chǎn)生較準確的劃分,兩個都考慮了邊界損失與分割區(qū)域之間的相關(guān)性比例。而AvCut準則更容易導(dǎo)致欠分割或易分割出只包含幾個少數(shù)頂點的極小子圖的缺點。
1.1.5最小最大割集準則(MinMax Cut)
最大最小割集準則[6]是為了能夠使類內(nèi)頂點的連接度強,類間的連續(xù)強度能夠最小化,其目標函數(shù)MCut為:MCut=Cut(A,B)Vol(A,A)+Cut(A,B)Vol(B,B)可以看出,最小化MCut函數(shù)不僅要最小化Cut(A,B),還需要最大化Vol(A,A)和Vol(B,B)。該函數(shù)不易出現(xiàn)分割出只包含幾個頂點的較小子圖,傾向于產(chǎn)生平衡割集,可以有效避免孤立點的出現(xiàn),但實現(xiàn)速度較慢。
1.1.6多路規(guī)范割集準則(Multiway Normalized Cut)
Meila和Xu[7]在NCut割集函數(shù)的基礎(chǔ)上,將圖G分割成k個子圖,將規(guī)范割集準則擴展到k類,這就是多路規(guī)范割集準則。其目標函數(shù)為:MNCut=Cut(A1,V-A1)Vol(A1,V)+Cut(A2,V-A2)Vol(A2,V)+...
+Cut(Ak,V-Ak)Vol(Ak,V)可以看出,當(dāng)k值為2,即分割成2個子圖,聚類成兩類時,MNCut函數(shù)和NCut函數(shù)是相同的。多路規(guī)范割集準則在實際應(yīng)用中更有效、合理,只是優(yōu)化問題和最小化問題比較難于解決。
1.2譜聚類算法描述
譜聚類算法大多處理兩類問題,多類聚類一般通過兩路劃分方法來實現(xiàn)。假定k是最終分類個數(shù)。譜聚類算法不是直接對數(shù)據(jù)點集的親密度矩陣S進行分析而得出分類結(jié)果,而是要先計算k個最大的特征值和特征向量,沒有充分利用包含有用劃分信息的其它特征向量,其計算量較大,計算效率低,并且需要由用戶事先給出聚類個數(shù)k。然后,用這些特征向量構(gòu)造一個對稱矩陣Q,最后對Q進行親密度分析才得到數(shù)據(jù)集的最終聚類。因此,譜聚類算法得到的矩陣Q只是原始親密度矩陣S的一個近似,近似的程度與k值相關(guān),k越大,Q和S的誤差越小。Q對比S的優(yōu)勢主要體現(xiàn)在對Q進行親密度分析,比對S直接進行分析以實現(xiàn)的分類要容易。
目前,已經(jīng)出現(xiàn)了許多譜聚類模型和算法,如PF算法、SM算法、SLH算法、KVV算法、MCut算法等幾種迭代譜聚類算法;還有多路譜聚類算法,包括MS算法和NJW算法等。
2當(dāng)前研究和應(yīng)用
2.1圖像分割應(yīng)用
譜聚類算法最初應(yīng)用在圖像分割中。Shi和Malik采用2way NCut的譜聚類算法對圖進行迭代分割,得到滿意的聚類效果。但傳統(tǒng)譜聚類算法易受到彩色圖像大小和相似性測度的影響,會導(dǎo)致計算量大和分割精度低的問題。文獻提出了一種譜聚類分割算法,該算法基于超像素集測地線特征。先對彩色圖像進行預(yù)分割得到超像素集,以超像素集為基礎(chǔ)構(gòu)造加權(quán)圖,利用測地線距離特征和顏色特征構(gòu)造權(quán)值矩陣,再應(yīng)用NJW算法得到最終的分割結(jié)果,實驗表明該算法在分割精度和計算復(fù)雜度上都有較大改善。
2.2半監(jiān)督學(xué)習(xí)應(yīng)用
文獻提出了一種有約束的半監(jiān)督譜聚類特征向量選擇算法。該算法通過大量的監(jiān)督信息尋找能體現(xiàn)數(shù)據(jù)結(jié)構(gòu)特征的向量組合,來獲得優(yōu)于傳統(tǒng)譜聚類算法的聚類性能,采用MNIST手寫體數(shù)據(jù)集和UCI標準數(shù)據(jù)集進行仿真實驗,結(jié)果驗證了該算法的有效性和魯棒性。
2.3大數(shù)據(jù)分析應(yīng)用
李斌等提出了一種新的聚類算法NGKCA。首先利用譜聚類NJW算法對大數(shù)據(jù)集進行列降維和數(shù)據(jù)歸一化處理,其次引入對初始值不敏感的粒子群算法對數(shù)據(jù)集進行行降維從而選出臨時的聚類中心集,接著通過全局kmeans算法獲取聚類中心點,最后使用粒子群算法調(diào)整聚類中心點獲取最終的聚類劃分。實驗結(jié)果表明,該算法具有更好的穩(wěn)定性和更高的檢測率、更優(yōu)的時間復(fù)雜度,適用于解決大數(shù)據(jù)環(huán)境下的聚類問題。
2.4其它應(yīng)用
朱正偉提出基于譜聚類的入侵檢測技術(shù),采用KDD CUP99數(shù)據(jù)集實驗,結(jié)果表明譜聚類的檢測率和誤報率普遍優(yōu)于Kmeans和層次聚類算法。周林等提出基于譜聚類的聚類集成算法。先利用譜聚類的內(nèi)在特性構(gòu)造多樣性的聚類成員,然后用連接三元組算法計算相似度矩陣,再對該矩陣使用譜聚類算法以得到集成結(jié)果。最后,用Nystrom采樣算法有效降低了算法的計算復(fù)雜度,使得算法能擴展到大規(guī)模應(yīng)用。實驗結(jié)果表明,較之其它常見的聚類集成算法,該算法更優(yōu)越、更有效,能較好地解決數(shù)據(jù)聚類、圖像分割等問題。
3研究展望
譜聚類算法是應(yīng)用矩陣譜分析理論得到聚類數(shù)據(jù)的新特征,利用新的數(shù)據(jù)特征對原數(shù)據(jù)進行聚類。從國內(nèi)外研究現(xiàn)狀來看,譜聚類算法已被廣泛運用于各個領(lǐng)域,并取得很好的效果。但是,譜聚類算法仍然存在一些亟待深入研究的問題:
(1)如何智能地確定需要聚類的個數(shù)。這不僅僅是譜聚類,也是其它很多聚類算法所面臨的困難和挑戰(zhàn)。目前已有的譜聚類算法中,如RCut、NLDR(Nonlinear Dimensionality Reduction,非線性降維)算法能夠自適應(yīng)確定聚類個數(shù),但是聚類效果并不是很理想,亟需改進。
(2)如何解決模糊聚類問題。譜聚類算法來源于譜圖分割領(lǐng)域,圖分割后一般子圖與子圖之間是不重疊的。譜聚類算法在面對這種情況時往往聚類效果不佳。
(3)如何運用到海量數(shù)據(jù)中。譜聚類算法涉及到求解大型矩陣的特征值分解問題,其計算復(fù)雜度高、計算量和存儲量太大,不利于在大規(guī)模數(shù)據(jù)中計算和擴展,這對譜聚類的應(yīng)用前景非常不利。雖然己經(jīng)有研究者提出優(yōu)化這一問題的方法,但仍然是未來研究的方向。
(4)如何與深度學(xué)習(xí)相融合。近年來深度學(xué)習(xí)發(fā)展迅猛,文獻介紹了譜算法中算子譜刻畫映射的能力,學(xué)者們開始思考將譜聚類算法與深度學(xué)習(xí)相結(jié)合并幫助提高算法效率。
參考文獻:
蔡曉妍,戴冠中,楊黎斌.譜聚類算法綜述[J].計算機科學(xué),2008,35(7):1418.
WU Z,LEAHY R.An optimal graph theoretic approach to data clustering:theory and its application to image segmentation[J].IEEE Trans on PAMI,1993,15(11):11011113.
SHI J,MALIK J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888905.
HAGEN L,KAHNG A B.New spectral methods for ratio cut partitioning and clustering[J].ComputerAided Design,1992,11(9):10741085.
SARKAR S,SOUNDARARAJAN P.Supervised learning of large perceptual organization:Graph spectral partitioning and learning automata[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2000,22(5):504525.