譜聚類算法及其應(yīng)用綜述

李玲俐

摘要：由于性能優(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.