這篇是在找normalization cut 時候找到的，算是轉錄再轉錄
來源網址是
http://blog.xuite.net/coke750101/coketech/19917487
| 作者: | Sam.Tzeng. [ 週一 3月 10, 2008 3:09 pm ] |
| 文章標題 : | Spectral Clustering |
Spectral Clustering
轉自bbs.sjtu.edu.cn
什麼叫Spectral Algorithm?
廣義上來說，任何在演算法中用到SVD/特徵值分解的，都叫Spectral Algorithm。從很老很老的PCA/LDA，到比較近的Spectral Embedding/Clustering，都屬於這類。
為什麼要用SVD/特徵值分解?
其實並不是為用而用，而是不得不用。目前在研究領域碰到的很多基礎問題都是NP-hard的，找一個比較好的近似演算法要費很大的精力；就算找到多項式的近似方法，也會出現實際使用上仍然太慢/解陷入局部極小等問題。
比如說用K-means聚類，建模本身已經夠簡單了，但它是NP-hard的，用傳統的EM迭代作近似解會陷入局部極小。
反 之，SVD理論上只有唯一解，演算法速度相對又快，並且有大量理論結果及周邊性質支持，可以算是一個很理想地能將NP-hard問題“靠”上去的模型；它 的另一個好處是，作為帶約束二次規劃的一種特殊情況，它對運算式為二次的目標函數的“相容性”比較好，“靠”所要求的數學技巧不高，任何人，任何方向都能 拿來試試。
Spectral Algorithm的幾個方向:
傳統的如PCA/LDA用來做線性降維，2000年左右的一些Spectral Embedding及Spectral Clustering，還有周邊的一些，如Low-rank approximation等等。
為什麼先做降維再做K-means，效果會更好呢？
另外，有趣的是K-means可以用PCA來做近似解。K-means是說找到K個點，使得所有點到這K個點的距離平方和最小；
而SVD是說找到一個子空間，使得所有點到這個子空間的距離平方和最小。於是這兩者就建立了聯繫，K-means便relax到SVD上去了。
Spectral Clustering/Embedding:
Spectral Clustering可算是Spectral Algorithm的重頭戲。
所謂Clustering，就是說聚類，把一堆東西（合理地）分成兩份或者K份。從數學上來說，聚類的問題就相當於Graph Partition的問題，即給定一個圖G = (V, E)，如何把它的頂點集劃分為不相交的子集，使得這種劃分最好。其難點主要有兩個：
1. 這個“合理”其實相當難達到，隨便設一個目標函數可能達不到希望的結果。大家可以看了看[1] Ravi Kannan and Adrian Vetta, On clusterings: good, bad and spectral，這裏詳細地討論了一下準則的選擇問題。
2. 即使我們定義了一個相當好的聚類準則，如何優化它又是一個問題。
對於1，在Spectral Clustering這一塊，各家有各家的想法。主要有以下幾種：
a) 大名鼎鼎的Normalized Cut[2]，還有一些變種如Ratio Cut/Minmax cut.
b) 和代數圖論緊密相聯的Minimum conductance[1].
c) 沒有準則，但有證明的演算法[3]
d) 不基於圖，而是reformulate原來的聚類方法，使之變成SVD能解的問題[4]。
2則完全被1的選取所決定。
Normalized Cut:
在 圖上，定義什麼樣的聚類最好，最簡單的方法是圈定K個不相交頂點集之後，希望頂點集之間的邊，其權值的和最小。(邊上的權值代表的是兩頭的頂點鄰近的程 度，或者說相似度）這就是所謂MinCut（最小割）問題。二類分類的最小割不是NP-hard的，但是這不能讓人感到開心，因為MinCut這個準則對 於聚類不好。
具體來說，Mincut完全可能將離大部隊過遠的單個頂點與其他頂點分開, 形成兩類。
事實上，我們不僅僅要讓割邊的權和最小，而且要讓這K個頂點集都差不多大，這樣才符合聚類給人的直觀感覺。
於是在MinCut的基礎上，出現了Normalized Cut. 思路很簡單，將Cut normalize一下，除以表現頂點集大小的某種量度(如 vol A = 所有A中頂點集的度之和)。
也就是Normalize Cut(A, B) = Cut(A, B) / volA + cut(A, B) / volB
然而這樣一改，NP-hard就來了。這幾乎是所有組合優化問題的惡夢。
怎麼辦呢？把組合優化問題連續化，即所謂減少約束，進行適當的relax。那麼為什麼會和SVD扯上的呢？
很簡單，聚類是東西分成不相交集，也就是有正交的含義在裏面；只是分東西必須是0-1式的，這種離散化，就是np-hard的原因。我們把正交約束保留，但把離散變成連續的，聚類就變成了尋找（列）正交陣的優化問題，那正是SVD的火力所在！
就這樣，通過這種巧妙的relax，NP-hard問題有了近似解。且不說這近似解的質量如何，這種方法是相當令人振奮的。（關於Normalized Cut近似解的質量, 似乎沒有什麼文章能夠給出嚴格的證明，只是實際效果不錯就是了。）
值得一提的是，Normalized Cut還和圖上的Markov chain有緊密的關係[5]。Normalized Cut這個量度，換成Markov chain的語言就是在圖上隨機遊走，子集間相互“串門”的概率大小。相當有趣。
Minimum conductance:
Minimum conductance是另一種Graph Partition的準則，和Normalized Cut看起來相當像，然而分析方法卻完全不同。Minimum conductance是圖上的一種不變數，在代數圖論中，它被稱為Cheeger constant, 是指遍曆所有的子集分劃(A, B)，邊割除上min(vol A, vol B)的最小值。 vol是圖上頂點集大小的量度（這個量度和Normalized Cut所用的量度是一樣的）。
這個按理說比Normalized Cut所用的量度更難處理，因為有min函數。然而，有趣的是在代數圖論中有這樣的結論，圖上的Laplace矩陣的第二小特徵值（第一小是0）是Cheeger constant的一個估計:
2 * Cheeger constant <= \lambda <= (Cheeger constant)^2 / 2
OK，SVD再次登場，找到Laplace矩陣的第二小特徵值，然後用相應特徵向量做圖的割，雖然差了點，但不會比Minimum conductance的割差到哪里去。並且差多少，是有理論界的。
沒有準則，但有證明的演算法
有時候寫準則是很麻煩的，反過來說，不用準則直接給出演算法及證明，難度更大然而更靈活。[1]給出了一個遞迴演算法，不斷地把圖分成兩塊，直到某個終止條件被滿足，這樣能做K類分類。
[1] 還給出了證明，保證這樣聚類出來的質量。相比之下，Normalized Cut對於對多類分類，無法給出這樣的界，儘管它也是不斷地二類分下去。另外，[3]給出了一個能直接做多類分類的方法：先Spectral再K- mean. 它沒有目標函數准則，卻能用矩陣擾動理論，證明至少在稍許偏離理想情況下演算法是work的。
這種做法，給一直遵循從目標函數到演算法這一步驟的我以很大的啟發。原來自己走的路一直是很窄的啊。
Reformulate原來的聚類方法:
或許Spectral Clustering給我們留下最重要的，並不是那麼多演算法，而是將SVD融入優化問題的思路，即所謂的spectral relaxation。
[4]正是使用了這條思路，將K-means重新建模，以離散化連續，relax成可以用SVD解的問題，並解之。[4]就數學技巧而言只能說一般般，但是用上了，就會出來很有趣的東西。
其他一些聚類方法:
此 外，還有其他的一些用到Spectral Algorithm的聚類方法。如[7]裏面，Spectral Algorithm用來將點集分成樹狀，然後在樹上以其他準則（如K-means) 將樹葉合併回去，形成最終的聚類結果。在樹上很多本來np-hard的問題就變成可以用動態規劃解了。
Spectral Embedding，一些非線性降維的方法:
除了Spectral clustering, Spectral Embedding即用spectral algorithm來進行非線性降維，也是譜演算法的應用之一。
這個和流形學習有一定聯繫，Salu大哥對此方面極為精通，呵呵。
Laplacian Eigenmap[9]是其中一個很有名的方法。它也是使用圖的Laplace矩陣，優化一個二次函數，解SVD得到的。只是這裏不像聚類，沒有relax的過程，因此得到的就是精確解。
一些周邊:
1. Low-rank approximation
目前來說，解SVD已經算相當快了，但是仍然滿足不了某些應用的胃口。因此解SVD的方法也有了一些發展。用隨機演算法是一個趨勢。
2. Semi-definite Programming(SDP)
作為Spectral algorithm的競爭對手，把一些聚類問題relax到SDP在理論上會有更好的結果，不過實驗上看不出差別[11]。而且要命的是......實在太複雜了。
一些有用的資料和website:
http://crd.lbl.gov/~cding/Spectral/
這 個不用說了，查spectral clustering第一個就是它。不過頁面上附的Tutorial實在不行，單看是幾乎不懂的。還是老老實實看Selected References裏的paper比較好。http://www.cc.gatech.edu/~vempala/papers /spectral.html
[1] Ravi Kannan and Adrian Vetta, On clusterings: good, bad and spectral. Jour
nal of the ACM (JACM) 51(3), 497--515, 2004.
[2] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE. Trans.
on Pattern Analysis and Machine Intelligence, 22:888--905, 2000.
[3] A.Y. Ng, M.I. Jordan, and Y. Weiss. On spectral clustering: Analysis and a
n algorithm. Proc. Neural Info. Processing Systems (NIPS 2001), 2001.
[4] H. Zha, C. Ding, M. Gu, X. He, and H.D. Simon. Spectral relaxation for K-m
eans clustering. Advances in Neural Information Processing Systems 14 (NIPS 20
01). pp. 1057-1064, Vancouver, Canada. Dec. 2001.
[5] M. Meila and J. Shi. A random walks view of spectral segmentation. Int'l W
orkshop on AI & Stat (AI-STAT 2001).
[6] F.R.K. Chung. Spectral Graph Theory. Amer. Math. Society Press, 1997.
[7] A Divide-and-Merge Methodology for Clustering (D. Cheng, R. Kannan and G.
Wang) Proc. of the ACM Symposium on Principles of Database Systems, 2005.
[8] H. Zha, X. He, C. Ding, M. Gu & H. Simon. Bipartite Graph Partitioning and
Data Clustering, Proc. of ACM 10th Int'l Conf. Information and Knowledge Mana
gement (CIKM 2001), pp.25-31, 2001, Atlanta.
[9] M. Belkin and P. Niyogi. Laplacian Eigenmaps and Spectral Techniques for E
mbedding and Clustering, Advances in Neural Information Processing Systems 14
(NIPS 2001), pp: 585-591, MIT Press, Cambridge, 2002.
[10] E.P. Xing and M.I. Jordan. On semidefinite relaxation for normalized k-cu
t and connections to spectral clustering. Tech Report CSD-03-1265, UC Berkeley
, 2003. |
|
No comments:
Post a Comment