譜聚類是一直讓我很郁悶的一個聚類方法，因為光知道做法，不知道原理，這樣用起來的時候真心很虛，就是很納悶，為啥這麼做就可以呢？
譜聚類是利用相似矩陣或其他派生矩陣的結構特征，将樣本劃分到不相交類别中，并使類内樣本相似度很高，而類别間樣本相似度較低的一類技術，是一種啟發式的聚類算法。
現在就介紹一下譜聚類的原理吧
由于實體與實體之間的互相作用，産生了大量的複雜資料集，我們可以用數學中的圖論的概念來表達這類複雜的資料，其中結點表示的實體，邊表示實體之間的的互相作用。
不放我們先簡單介紹一點圖論的知識吧。
圖G由一一系列的結點和邊組成，G={V，E}，圖的結構由鄰接矩陣A來表示。
其中如果結點i和j相接，則Aij=1，如果不相接，Aij=0
圖既可以是有向的也可以是無向圖，無向圖的鄰接矩陣使對稱的，這都比較好了解。
當然了，這裡都是用1/0表示兩個節點之間是有關系的，我們當然可以對邊進行權重，如果聯系大的話我們的權值就大，這樣的話，我們既可以用距離公式，算兩個樣本點的距離，那麼這個鄰接矩陣A就是一個權重邊的鄰接矩陣，矩陣中的每一個元素也代表着兩個樣本的距離。
圖的拉普拉斯矩陣可由鄰接矩陣導出：
D是對角陣，表示的樣本i到其他所有樣本的距離的加和：
這個di也叫結點i的度，我們現在說一下這個未正則的拉普拉斯矩陣的性質：
a. L是對稱半正定的
b. 各特征值為實數且非負，最小值為0，是以，是以，可以将特征值排列：
c. 零特征值的個數等于圖連接配接部分的數目，對應的特征向量可以作為一個訓示向量，表示給定的結點屬于那一部分，我們可以通過一幅圖來表示這個特性：
如上圖所示，拉普拉斯矩陣0特征值的個數為3個，這就表明其由3個互相分離的部分，同樣我們從右邊的表中可以看出，12345為一部分，678為一部分，10111213為一部分，是以，特征向量矩陣的行表示出結點屬于那一部分。
是不是和聚類有些相近了呢！！！
我們直接套用在聚類架構下來看看這個譜聚類：
a: 定義樣本之間的相似度，形成相似度矩陣A
b: 通過相似度矩陣計算拉普拉斯矩陣
c: 對拉普拉斯矩陣進行特征分解，選擇前k小的特征值的特征向量，構成n*k維特征向量矩陣
d: 利用K-means算法，将n個按照特征向量行劃分的k維樣本劃分到k個類别中去。
完活，僅此而已，真心不難！！！
另外，我們求相似矩陣的時候，有很多種方式，這裡介紹兩種：
首先定義兩節點邊上的權值，這些權值用以衡量兩節點的相似性，權值的定義方法也有很多種，我們假定一個鄰接矩陣A，矩陣元素Aij = s(xi，xj)，
s(xi，xj)是樣本x和y之間的相似度。我們設定一個ε鄰域，當樣本之間的距離小于這個ε鄰域是，結點之間就存在一條邊：
除此之外，我們還可以用高斯相似度來做：
當然了，拉普拉斯矩陣的形式也有三種：
剛剛介紹的那種是未正則的拉普拉斯矩陣，除此之外還有：
規範化拉普拉斯矩陣(正則化拉普拉斯矩陣)：
(非對稱)随機遊走拉普拉斯矩陣：
需要注意的是，随機遊走拉普拉斯矩陣最終取的是前k大的，而非前k小的。