基本介紹
- 中文名：譜聚類算法
- 原理：譜圖理論基礎
- 運用：計算機視覺 、VLS I 設計
- 領域：計算機
算法步驟,劃分準則,典型的算法,算法的新進展,面臨的問題,
算法步驟
譜聚類算法將數據集中的每個對象看作是圖的頂點V，將頂點間的相似度量化作為相應頂點連線邊E的權值，這樣就得到一個基於相似度的無向加權圖G(V, E)，於是聚類問題就可以轉化為圖的劃分問題。基於圖論的最優劃分準則就是使劃分成的子圖內部相似度最大，子圖之間的相似度最小。
雖然根據不同的準則函式及譜映射方法，譜聚類算法有著不同的具體實現方法，但是這些實現方法都可以歸納為下面三個主要步驟：
1) 構建表示對象集的相似度矩陣W；
2) 通過計算相似度矩陣或拉普拉斯矩陣的前k個特徵值與特徵向量，構建特徵向量空間；
3) 利用K-means或其它經典聚類算法對特徵向量空間中的特徵向量進行聚類。
上面的步驟只是譜聚類算法的一個總體框架，由於劃分準則、相似度矩陣計算方法等因素的差別，具體的算法實現同樣會有所差別，但其本質依然是圖劃分問題的連續放鬆形式。
劃分準則
譜聚類算法將聚類問題轉化為圖的劃分問題之後，基於圖論的劃分準則的優劣直接影響到聚類結果的好壞。常見的劃分準則有Mini cut，Average cut，Normalized cut，Min-max cut，Ratio cut，MNcut等。
最小割集準則
在對圖像分割中產生了較好的效果，但是該準則容易產生分割出只包含幾個頂點的較小子圖的歪斜分割現象。
規範割集準則
在2000年Shi和Malik根據譜圖理論建立了2-way劃分的規範割目標函式，此方法通過計算分割之後的連線邊損失值在各個子圖與所有頂點之間的連線邊權重總值中所占比例之和來衡量劃分的優劣。
比例割集準則
對於超大規模積體電路設計中的電路層次設計和分支劃分問題，最大流最小割算法能夠發現其中的類結構（clustering structure），但是在實際中該算法通常會產生規模非常不一致的電路分支；Kemighan-Lin算法採用固定參數的方式可以得到規模具有一定可比性的分支劃分，由於電路中的分支傾向於自然結合的形成，所以通過預先設定分支規模進行劃分的方法存在明顯的局限。針對以上的現象Wei和Cheng提出了比例割集準則。
平均割集準則
在計算機視覺中，圖像原始像素條理有序地分組可以通過尋找場景結構圖(Scene Structure Graph)中鬆散耦合的結點來完成，於是原始像素的聚合問題就轉化為場景結構圖的分割。Sarkar和Soundararajan[62]提出了一種最小化兩兩分割之間相似度的計算方法並把它命名為平均割集準則。
最小最大割集準則
Mini cut準則容易出現分割出只包含幾個頂點的較小子圖的歪斜分割現象，Ratio cut和Normalized cut等在一定程度上可以避免這種現象，但是當類間重疊嚴重時歪斜分割現象仍舊會發生。Chris Ding等人提出的基於Min-max cut的圖劃分方法充分體現了“子圖內部相似度最大，子圖之間的相似度最小”原則，能夠產生比較平衡劃分。
上述五種劃分都是不斷地將圖劃分為2個子圖的反覆疊代運算過程，當劃分函式的最小值滿足一定的條件時疊代過程便會終止，相應的函式可以稱為2-way劃分函式。
多路規範割集準則
Meilă和Xu[64]認為可以同時把圖劃分為k個子圖並於2004年提出了一種k-way規範割目標函式，而且對於參數k的選取問題也作了分析說明。
我們可以發現當k=2時，MNcut與Ncut兩者是等價的。
典型的算法
根據譜聚類算法所使用的劃分準則，可以把算法分為二路譜聚類算法和多路譜聚類算法，前者使用2-way劃分準則而後者使用k-way劃分準則。
二路譜聚類算法
SM算法。Meliă指出Ncut和MNcut的差異之處僅在於所使用的譜映射不同。多路規範割集準則在實際套用中合理有效，但其最佳化問題通常難以解決。Shi和Malik認為第二小特徵值對應的特徵向量，即Fiedler向量包含了圖的劃分信息，根據啟發式規則在此向量中尋找劃分點i使在該點上得到的Ncut(A,B)值最小，最後把向量中的值與Ncut準則函式的最小值進行比較，大於等於該值的點劃分為一類，小於該值的點則劃分到另外一類。
SLH算法。SLH重定位算法計算相似度矩陣W的前k個特徵向量，參數k需要事先指定。
KVV算法。根據啟發式規則在Fiedler向量中尋找劃分點i使在該點上得到的Rcut(A,B)值最小的劃分點，與SM算法相似；不同之處僅在於SM算法是尋找使Ncut(A,B)值最小的劃分點。雖然在實際問題中KVV算法存在運行速度相對較慢的缺陷，但是算法減少了過分割的可能性。
Mcut算法。Ding根據譜圖理論將最小最大割集準則函式的最最佳化問題轉化為下式的第二小特徵值的求解。
多路譜聚類算法
MS算法[70]。Meilă把基於馬爾可夫鏈隨機遊動過程的機率轉移矩陣運用到相似度矩陣的構造中，研究了這種隨機遊動的機率轉移矩陣的特徵值和特徵向量，在隨機遊動的框架下了對Ncut進行了機率解釋。該算法是用隨機遊動矩陣P的前k個非零特徵值對應的特徵向量構造矩陣，然後將矩陣中的行看成R空間中的點進行聚類，步驟與NJW算法相似。MS算法在實際的圖像分割中取得了良好的效果，但是度矩陣D中對角線元素值之間存在較大的差別時就會導致較差的聚類效果。
算法的新進展
Meila和Shi將相似性解釋為Markov鏈中的隨機遊動，分析了這種隨機遊動的機率轉移矩陣P=DW的特徵向量(W為相似度矩陣)，並且利用隨機遊動對Ncut進行了機率的解釋，提出了基於隨機遊動的新的算法。同時，在這個解釋框架下提出了多個特徵相似矩陣組合下的譜聚類方法，在圖像分割中取得了很不錯的效果。
Cu等人分析了核k-means的方法，發現最小化核k-means的目標函式等同於一個由數據向量組成的Gram矩陣的跡最大化問題。同時，跡最大化問題的鬆散解可以通過Gram矩陣的部分特徵分解獲得，首次用譜鬆散的方法獲得核k-means的目標函式的全局最優解。Dhillon[29]在此基礎上，又研究了加權核k-means的目標函式，將其與Ncut目標函式建立聯繫，提出了一個可以單調遞減Ncut值的新穎的加權核k-means算法。
Ncut是一個很好的聚類目標函式。它的求解是一個NP難問題。傳統的方法是寬鬆的譜鬆散方法。Xing與Jordan[分析了對Ncut的半正定規劃(SDP)模型。根據該模型，對Ncut提出了一個比譜鬆散更緊的下限。同時指出了Ncut本身不能得到最優的聚類，但它可以通過不同的鬆散方法獲得合理的聚類。
譜聚類方法不僅用於無監督學習中，也用於有約束的半監督學習中。Kamvar等人將PageRank[32]的隨機遊動模型運用到相似度矩陣中，根據已知樣本的類別修正相似度矩陣。然後根據譜聚類算法獲得聚類結果。Bach與Jordan則是根據一個基於已知劃分與Ncut譜鬆散結果的誤差，提出了新的目標函式，通過最小化新的目標函式推出新的譜聚類算法。
王玲，薄列峰，焦李成認為在聚類搜尋過程中充分利用先驗信息會顯著提高聚類算法的性能，並分析了在聚類過程中僅利用成對限制信息存在的不足，提出利用數據集本身固有空間一致性先驗信息的具體方法。在經典的譜聚類算法中同時引入兩類先驗信息的基礎上提出一種密度敏感的半監督譜聚類算法，兩類先驗信息在指導聚類搜尋的過程中能夠起到相輔相成的作用，使得算法相對於僅利用成對限制信息的聚類算法在聚類性能上有了顯著的提高。
王娜，李霞提出了一種基於監督信息特性的主動學習策略，找出同一類中距離相對較遠的數據對象對和不同類中距離相對較近的數據對象對組成監督信息並將其引入譜聚類算法，構建新穎的主動半監督譜聚類算法，結果優於採用隨機選取監督信息的譜聚類性能。
面臨的問題
儘管譜聚類具有堅實的理論基礎，相對於其它聚類方法具有許多優勢，在實踐中的套用領域在不斷擴展，取得了不錯的效果[38]，但是它仍然需要改進，尤其在下述幾個方面：
如何構造相似度矩陣
如何創建相似度矩陣W，使其更加真實地反映數據點之間的近似關係，使得相近點之間的相似度更高，相異點之間的相似度更低，是譜聚類算法必須要解決的一個問題。高斯相似函式（Wij=exp(-||xi-xj||^2/2σ^2)）是經典譜聚類算法中計算兩點間相似度的常用方法，雖然該函式使原始的譜聚類算法取得了一些成功，但尺度參數σ的選取問題使該函式具有明顯的局限性。NJW算法[7]通過預先指定幾個尺度參數σ的值，分別執行譜聚類，最後選取使聚類結果最好的σ作為參數，這種做法消除了尺度參數σ選取的人為因素，卻增加了運算時間。
近年來，為了避免參數的選擇問題，有學者提出在計算相似度時不使用高斯核函式。如Gong 等人[41]借鑑Wang Fei和Zhang Changshui[42]在半監督中使用的方法，將每個點的k 近鄰對該點進行線性近似表示時所占的權重作為兩點間的相似度。通過求n 個二次規劃問題，就可以求得相似度矩陣W，降低了譜聚類算法對參數的敏感性，使算法更穩定。
如何自動確定聚類數目
由相似度矩陣得到拉普拉斯矩陣後，接下來要確定所需特徵向量的數目，它與最終的聚類數目相等。雖然該數目可以由人工確定，但是準確地給出對聚類效率和最終的聚類質量有直接影響的數目值是個非常困難的問題。因此，如何自動確定聚類數目成為譜聚類需要解決的關鍵問題之一。
如何選擇特徵向量
大多情況下的譜聚類算法直接選擇前k 個最大特徵值對應的特徵向量用於新向量空間的構造。2008 年Xiang等人[44]提出了“向量相關度”的概念，在使用該定義對向量的相關度進行衡量的基礎上選出相關度最高的k 個特徵向量用於新向量空間的構造。實驗結果表明運用此方法選取擁有較高相關度和較多信息量的特徵向量可以得到更加令人滿意的聚類效果。
如何解決模糊聚類的問題
儘管在文檔聚類中，譜聚類取得了很好的效果。但是在文檔聚類中，單個詞可能屬於多個類，單個文檔可能是多主題的文檔。這就需要我們用模糊聚類的方法解決。如何確定基於模糊聚類與譜方法的聯合：如何建立模糊標準的圖劃分的目標函式等都是譜聚類算法在模糊聚類中所面臨的問題。如何運用到大規模學習問題中：由於譜聚類算法需要求解特徵值和特徵向量，所以計算複雜度相對較大，針對目前強烈的大規模數據處理要求研究高效、可擴展、適宜大規模學習問題的譜聚類算法。
如何提高譜聚類的運行速度
