譜聚類算法及其應用綜述

李玲俐

摘要：由于性能優越，譜聚類成為近年來聚類算法研究的熱點。譜聚類算法可以在任意形狀的樣本空間上聚類，并能獲得全局最優解。介紹了譜圖的基本理論及其劃分準則，探討了譜聚類算法，并針對當前譜聚類應用展望了未來研究方向。

關鍵詞關鍵詞：譜聚類；譜圖理論；圖劃分；應用研究

DOIDOI：10.11907/rjdk.161229

中圖分類號：TP312文獻標識碼：A文章編號文章編號：16727800（2016）007005403

0引言

聚類就是按照事物的某些特征，把事物分成若干類或簇，使得在同一個類內的對象之間最大程度相似，而不同類之間的對象最大程度不同。聚類分析在數據挖掘、空間數據處理、金融數據分類和入侵檢測技術等領域中都得到了廣泛應用。傳統的聚類算法，如Kmeans和模糊C均值算法（Fuzzy CMeans，FCM）等大都建立在凸球形樣本空間上，如果樣本空間不為凸，算法就會陷入局部最優。因此，學者們開始研究一種新的聚類方法——譜聚類（Spectral Clustering，SC）算法。該算法由給定的樣本數據集定義一個描述數據點之間相似度的親和矩陣，并計算矩陣的特征值和特征向量，再選擇合適的特征向量聚類不同的數據點。譜聚類算法是一個判別式算法，其思想相對簡單易于實現，具有識別非凸分布的聚類能力，適合處理許多實際應用問題。本文著重介紹譜聚類的基本理論、算法描述、當前應用及未來研究方向。

1譜聚類基本理論與算法描述

1.1圖劃分原理

譜聚類是一種基于圖論的聚類方法。譜圖理論是將數據聚類問題轉化成圖的多路劃分問題，通過分割子圖來聚類數據點。譜聚類能對任意形狀的樣本空間聚類，并能獲得全局最優解，其基本思想是通過對樣本數據的Laplacian（拉普拉斯）矩陣進行特征分解而得到的特征向量進行聚類。

4結語

針對kmeans算法易受初始聚類中心影響的問題，首先用人工魚群算法的全局尋優能力搜索初始聚類中心。

為了處理大規模數據，本文提出基于Mapreduce的afsa_km算法。實驗結果表明，并行化的afsa_km算法比kmeans算法有更高的準確率，基于Mapreduce實現的afsa_km算法具有良好的加速比和擴展性，效率也有很大提高。 假定將每個數據樣本看作圖中的頂點V，且樣本中的數據對之間都有一定的相似性，由樣本間的相似度，將頂點間的邊E賦權重值W，得到一個無向加權圖G=（V，E），V={v1，v2，...vn}表示點集。圖G中，可將聚類問題轉化為在圖G上的圖劃分問題。圖論中的劃分準則一般有Minimum Cut、Average Cut、Normalized Cut、Minmax Cut、Ratio Cut、MN Cut等，劃分準則的好壞對聚類結果的優劣產生很大影響。

1.1.1最小割集準則（Minimum Cut）

譜圖分割過程中，圖的邊值代表頂點之間的相關性大小，假設G被劃分為A、B兩個子圖，最小割集的代價函數為：Cut（A，B）=∑i∈A，j∈BWij其中，A∩B=φ，A∪B=V，權重Wij表示Vi與Vj之間的關系。屬于子圖A的頂點和屬于子圖B的頂點之間的所有邊的和最小化，表示兩個子圖之間的相關性越小。Wu和Leahy[2]提出最小化上述Cut值來劃分圖G，即最小割集準則，是最常見也是最簡單的評價方法。用該準則對一些圖像進行分割也能產生不錯的效果。該準則的缺點是分割圖像時容易出現偏向小區域的情況。

1.1.2規范割集準則（Normalized Cut）

根據譜圖理論，Shi和Malik[3]提出新的目標代價函數NCut為：NCut（A，B）=Cut（A，B）Vol（A，V）+Cut（A，B）Vol（B，V）其中，Vol（A，V）

規范割集準則即最小化NCut函數。與Minimum Cut相比，該準則能平衡類內樣本間的相似度，也能平衡類間樣本間的相異度，即可以避免偏向小區域分割。一般的聚類算法中，采用NCut準則的情況比較多。

1.1.3比例割集準則（Ratio Cut）

為兼顧孤立點和均衡化問題，Hagen和Kahng[4]提出了比例割集準則，其目標代價函數RCut為：RCut（A，B）=Cut（A，B）min（|A|，|B|）其中，|A|、|B|分別表示子圖A、B中頂點的個數，Cut（A，B）是最小割集準則的代價函數。最小化RCut函數引入了一個規模參數作為分母，加大了類間相似性，減低了過分分割的可能性，這是優于最小割集準則的方面，但該準則會使運行速度降低。

1.1.4平均割集準則（Average Cut）

Sarkar和Soundararajan[5]提出平均割集準則，其目標函數AvCut為：AvCut=Cut（A，B）|A|+Cut（A，B）|B|AvCut同NCut函數一樣，最小化目標函數都能產生較準確的劃分，兩個都考慮了邊界損失與分割區域之間的相關性比例。而AvCut準則更容易導致欠分割或易分割出只包含幾個少數頂點的極小子圖的缺點。

1.1.5最小最大割集準則（MinMax Cut）

最大最小割集準則[6]是為了能夠使類內頂點的連接度強，類間的連續強度能夠最小化，其目標函數MCut為：MCut=Cut（A，B）Vol（A，A）+Cut（A，B）Vol（B，B）可以看出，最小化MCut函數不僅要最小化Cut（A，B），還需要最大化Vol（A，A）和Vol（B，B）。該函數不易出現分割出只包含幾個頂點的較小子圖，傾向于產生平衡割集，可以有效避免孤立點的出現，但實現速度較慢。

1.1.6多路規范割集準則（Multiway Normalized Cut）

Meila和Xu[7]在NCut割集函數的基礎上，將圖G分割成k個子圖，將規范割集準則擴展到k類，這就是多路規范割集準則。其目標函數為：MNCut=Cut（A1，V-A1）Vol（A1，V）+Cut（A2，V-A2）Vol（A2，V）+...

+Cut（Ak，V-Ak）Vol（Ak，V）可以看出，當k值為2，即分割成2個子圖，聚類成兩類時，MNCut函數和NCut函數是相同的。多路規范割集準則在實際應用中更有效、合理，只是優化問題和最小化問題比較難于解決。

1.2譜聚類算法描述

譜聚類算法大多處理兩類問題，多類聚類一般通過兩路劃分方法來實現。假定k是最終分類個數。譜聚類算法不是直接對數據點集的親密度矩陣S進行分析而得出分類結果，而是要先計算k個最大的特征值和特征向量，沒有充分利用包含有用劃分信息的其它特征向量，其計算量較大，計算效率低，并且需要由用戶事先給出聚類個數k。然后，用這些特征向量構造一個對稱矩陣Q，最后對Q進行親密度分析才得到數據集的最終聚類。因此，譜聚類算法得到的矩陣Q只是原始親密度矩陣S的一個近似，近似的程度與k值相關，k越大，Q和S的誤差越小。Q對比S的優勢主要體現在對Q進行親密度分析，比對S直接進行分析以實現的分類要容易。

目前，已經出現了許多譜聚類模型和算法，如PF算法、SM算法、SLH算法、KVV算法、MCut算法等幾種迭代譜聚類算法；還有多路譜聚類算法，包括MS算法和NJW算法等。

2當前研究和應用

2.1圖像分割應用

譜聚類算法最初應用在圖像分割中。Shi和Malik采用2way NCut的譜聚類算法對圖進行迭代分割，得到滿意的聚類效果。但傳統譜聚類算法易受到彩色圖像大小和相似性測度的影響，會導致計算量大和分割精度低的問題。文獻提出了一種譜聚類分割算法，該算法基于超像素集測地線特征。先對彩色圖像進行預分割得到超像素集，以超像素集為基礎構造加權圖，利用測地線距離特征和顏色特征構造權值矩陣，再應用NJW算法得到最終的分割結果，實驗表明該算法在分割精度和計算復雜度上都有較大改善。

2.2半監督學習應用

文獻提出了一種有約束的半監督譜聚類特征向量選擇算法。該算法通過大量的監督信息尋找能體現數據結構特征的向量組合，來獲得優于傳統譜聚類算法的聚類性能，采用MNIST手寫體數據集和UCI標準數據集進行仿真實驗，結果驗證了該算法的有效性和魯棒性。

2.3大數據分析應用

李斌等提出了一種新的聚類算法NGKCA。首先利用譜聚類NJW算法對大數據集進行列降維和數據歸一化處理，其次引入對初始值不敏感的粒子群算法對數據集進行行降維從而選出臨時的聚類中心集，接著通過全局kmeans算法獲取聚類中心點，最后使用粒子群算法調整聚類中心點獲取最終的聚類劃分。實驗結果表明，該算法具有更好的穩定性和更高的檢測率、更優的時間復雜度，適用于解決大數據環境下的聚類問題。

2.4其它應用

朱正偉提出基于譜聚類的入侵檢測技術，采用KDD CUP99數據集實驗，結果表明譜聚類的檢測率和誤報率普遍優于Kmeans和層次聚類算法。周林等提出基于譜聚類的聚類集成算法。先利用譜聚類的內在特性構造多樣性的聚類成員，然后用連接三元組算法計算相似度矩陣，再對該矩陣使用譜聚類算法以得到集成結果。最后，用Nystrom采樣算法有效降低了算法的計算復雜度，使得算法能擴展到大規模應用。實驗結果表明，較之其它常見的聚類集成算法，該算法更優越、更有效，能較好地解決數據聚類、圖像分割等問題。

3研究展望

譜聚類算法是應用矩陣譜分析理論得到聚類數據的新特征，利用新的數據特征對原數據進行聚類。從國內外研究現狀來看，譜聚類算法已被廣泛運用于各個領域，并取得很好的效果。但是，譜聚類算法仍然存在一些亟待深入研究的問題：

（1）如何智能地確定需要聚類的個數。這不僅僅是譜聚類，也是其它很多聚類算法所面臨的困難和挑戰。目前已有的譜聚類算法中，如RCut、NLDR（Nonlinear Dimensionality Reduction，非線性降維）算法能夠自適應確定聚類個數，但是聚類效果并不是很理想，亟需改進。

（2）如何解決模糊聚類問題。譜聚類算法來源于譜圖分割領域，圖分割后一般子圖與子圖之間是不重疊的。譜聚類算法在面對這種情況時往往聚類效果不佳。

（3）如何運用到海量數據中。譜聚類算法涉及到求解大型矩陣的特征值分解問題，其計算復雜度高、計算量和存儲量太大，不利于在大規模數據中計算和擴展，這對譜聚類的應用前景非常不利。雖然己經有研究者提出優化這一問題的方法，但仍然是未來研究的方向。

（4）如何與深度學習相融合。近年來深度學習發展迅猛，文獻介紹了譜算法中算子譜刻畫映射的能力，學者們開始思考將譜聚類算法與深度學習相結合并幫助提高算法效率。

參考文獻：

蔡曉妍，戴冠中，楊黎斌.譜聚類算法綜述[J].計算機科學，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.