度矩陣為對角矩陣，度為與節點的相連的個數
圖論的數學領域中的拉普拉斯矩陣（也被稱為導納矩陣，吉爾霍夫矩陣或離散拉普拉斯）是圖的矩陣表示。
拉普拉斯矩陣 結合 吉爾霍夫理論 可以用來計算圖的最小生成樹的個數。拉普拉斯矩陣還可用來尋找圖的其他屬性：譜圖理論spectral graph theory.
黎曼幾何的cheeger不等式有涉及了拉普拉斯矩陣的離散模拟。這或許是譜圖理論中最重要的定理也是在算法應用中最有用的facts.它通過拉普拉斯矩陣的第二特征值來近似圖的最小割。
拉普拉斯矩陣是 度矩陣 和 鄰接矩陣的差。度矩陣是一個對角矩陣，其包含了每個頂點的度。在處理有向圖時，根據應用來選擇入度或出度。
前面介紹過k-means聚類方法，這個方法簡單易懂，主要在于如何定義距離計算公式（一般使用歐氏距離），如何選擇k值，這兩個問題。這次我們介紹譜聚類，它是k-means的更新版。我們計劃從這樣幾個方面介紹譜聚類：k-measn聚類有什麼缺點？譜聚類的基本思想，以及譜聚類的算法步驟。
那麼k-means到底有什麼問題呢？我們為什麼需要改進它呢~
當樣本維數增大時，k-means的計算會困難。因為在k-means中，輸入計算的是歐氏空間中的原始向量；
k-means求得的是一種局部最優的聚類政策，sse不一定就是最小的；
譜聚類是一種基于圖論的聚類方法。将樣本看成頂點，樣本的相似度看作帶權邊。這樣，把樣本集劃分成k個簇的過程就等同于一個圖的分割問題。
如下圖所示，每個頂點是一個樣本，共有7個樣本（實際中一個樣本是特征向量）。邊的權值就是樣本之間的相似度。然後我們需要分割，分割之後要使得連接配接不同組之間的邊的權重盡可能低（組間相似度小），組内部的邊的權重盡可能高（組内相似度高）。
比如我們把中間的邊去掉，就滿足上面的簇間相似性最小，簇内相似性最大。如下圖：
譜聚類算法主要有下面這幾步：
1）計算得到圖的鄰接矩陣e，以及拉普拉斯矩陣l；
給定樣本的原始特征，我們需要計算兩兩樣本之間的相似度值，才能構造出鄰接矩陣e。我們一般使用高斯核函數來計算相似度。公式如下：
其中xi和xj是兩個樣本的原始特征向量，我們可以計算出它們二者之間的相關性。注意，鄰接矩陣的對角線元素一緻等于零。這樣我們就得到了鄰接矩陣e。
拉普拉斯矩陣l=d-e, 其中d為上面圖的度矩陣，度是圖論中的概念，也就是矩陣e行或列的元素之和。後面我們就要基于矩陣l來進行研究。
2）聚類劃分準則
關于劃分準則的問題是聚類技術中的核心。譜聚類被看作屬于圖論領域的問題，那個其劃分也會和邊的權重有關。
準則1：最小化進行分割時去掉的邊的權重之和。
這個準則直覺地讓分割之後簇之間的相似度最小了。但是有個問題，就是這個準則沒有考慮到簇的大小，容易造成一個樣本就能分為一個簇。為了避免這個問題，有了下面的準則。
準則2：考慮簇的大小。
這個準則2相比于準則1的改進，類似于c4.5中的增益比率和id3的資訊增益的改進。在ratiocut中，如果某一組包含的頂點數越少，那麼它的值就越大。在一個最小化問題中，這相當于是懲罰，也就是不鼓勵将組分得太小。現在隻要将最小化ratiocut解出來，分割就完成了。不幸的是，這是個np難問題。想要在多項式時間内解出來，就要對這個問題作一個轉化了。在轉化的過程中，就用到上面提到的l的那一組性質，經過若幹推導，最後可以得到這樣的一個問題：
這個問題和線性鑒别分析lda中的目标函數轉化過程類似。這個問題可以轉化為特征分解，我們對拉普拉斯矩陣l做特征分解，取前k個最小的特征值對應的特征向量，這些k個特征向量組成了新的樣本特征矩陣，維數為n*k.
接下來，我們n*k的矩陣的每一行都看作k維空間中的向量，也就是每個樣本現在隻有k維，每一行看作一個點進行k-means聚類。聚類得到改行屬于哪一個簇，那麼原來的樣本就屬于該簇。
是以說，譜聚類的聚類過程隻需要資料之間的相似度矩陣就可以，而k-means聚類是拿樣本的原始特征向量來聚類，這是它們的不同。