作者：Neerja Doshi
編譯：ronghuaiyang

導讀

什么是聚類？

聚類是一種廣泛使用的無監(jiān)督學習方法,。聚類是這樣分組的：集群中的點彼此相似,，而與其他集群中的點不太相似。因此,，如何在數(shù)據(jù)中尋找模式并為我們分組取決于算法,，根據(jù)使用的算法，我們可能最終得到不同的集群,。

有兩種廣泛使用的聚類方法：

1. 緊密性——相互靠近的點落在同一個集群中,，并且在緊密聚集在集群中心周圍。這種密切的關系可以用觀測值之間的距離來衡量,。比如：k—means聚類
2. 連接性——相互連接或相鄰的點放在同一個集群中,。即使兩點之間的距離更小，如果它們不相連,，它們也不會聚集在一起,。譜聚類是遵循這種方法的一種技術。

兩者之間的區(qū)別可以很容易地通過這個例子來說明：

譜聚類如何工作,？

在譜聚類中,，數(shù)據(jù)點被視為圖的節(jié)點。因此,，集群被視為一個圖的分割問題,。然后將節(jié)點映射到一個低維空間，該空間可以很容易地進行隔離,，從而形成集群,。需要注意的重要一點是，沒有對集群的形狀/形式做任何假設,。

譜聚類的步驟有哪些,？

譜聚類包括三個步驟：

• 計算相似圖
• 將數(shù)據(jù)投影到低維空間
• 創(chuàng)建集群

步驟1—計算相似圖

我們首先創(chuàng)建一個無向圖G = (V, E)，頂點集V = {v1, v2,，…,，vn} = 1,2，…,，n個數(shù)據(jù)中的觀察值,。這可以用一個鄰接矩陣來表示,，該矩陣將每個頂點之間的相似性作為其元素。要做到這一點,，我們可以計算：

1. ε-neighborhood圖：這里我們連接所有兩兩距離小于ε的點,。所有連接的點之間的距離大致都是相同的尺度（最多是ε)，對邊進行加權不會包含進圖中數(shù)據(jù)的更多的信息,，因此,，ε-neighborhood圖通常被認為是一個無權重的圖。
2. KNN圖：這里我們使用K最近鄰來連接頂點vi和頂點vj,，如果vj在vi的K個最近鄰中,，我們就把vi和vj連接起來。但是有個問題,，最近鄰可能不是對稱的,，也就是說如果有一個頂點vi以vj為最近鄰,，那么vi不一定是vj的最近鄰,。因此，我們最終得到一個有向圖,，這是一個問題,，因為我們不知道在這種情況下，兩點之間的相似性意味著什么,。有兩種方法可以使這個圖變成無向圖,。
3. 第一種方法是直接忽略邊緣的方向，即如果vi在vj的k近鄰中,，或者如果vj在vi的k近鄰中,，我們用無向邊連接vi和vj。得到的圖通常稱為k近鄰圖,。
4. 第二個選擇是連接vi和vj互為k近鄰點的情況,，得到的圖稱為相互k近鄰圖。
5. 在這兩種情況下,，在連接適當?shù)捻旤c后,，我們通過相鄰點的相似性對邊進行加權。
6. 全連接圖：為了構造這個圖,，我們簡單地將所有點連接起來,，并通過相似性sij對所有邊進行加權。該圖應該對局部鄰域關系進行建模,，因此使用了高斯相似函數(shù)等相似函數(shù),。

這里的參數(shù)σ控制鄰域的寬度，類似于ε-neighborhood圖中的參數(shù)ε,。

因此,，當我們?yōu)檫@些圖中的任意一個創(chuàng)建鄰接矩陣時,，當點很近時Aij ~ 1，當點很遠時Aij→0,。

考慮一下?lián)碛?~4節(jié)點的圖,，權值(或相似度)wij及其鄰接矩陣：

步驟2—將數(shù)據(jù)投影到低維空間

正如我們在圖1中所看到的，相同集群中的數(shù)據(jù)點可能也很遠—甚至比不同集群中的數(shù)據(jù)點還要遠,。我們的目標是空間轉換,，當這兩個點很近的時候，它們總是在同一個集群中,，當它們很遠的時候,，它們是在不同的集群中。我們需要把觀測結果投射到低維空間,。為此,，我們計算圖的拉普拉斯矩陣，這只是圖的另一種矩陣表示形式,，對于查找圖的有趣的屬性非常有用,。這可以計算為：

計算圖的拉普拉斯矩陣

計算圖的拉普拉斯矩陣L的全部目的是找到它的特征值和特征向量，以便將數(shù)據(jù)點嵌入低維空間?，F(xiàn)在,，我們可以繼續(xù)查找特征值。我們知道：

我們考慮下面的例子：

我們計算L的特征值和特征向量,。

步驟3—創(chuàng)建集群

對于這一步,，我們使用對應于第二個特征值的特征向量來為每個節(jié)點賦值。計算時,，第二個特征值為0.189,，對應的特征向量v2 =[0.41, 0.44, 0.37， -0.4,， -0.45,， -0.37]。

為了得到2聚類(2個不同的聚類),，我們首先將v2的每個元素分配給節(jié)點,，例如{node1:0.41, node2:0.44，…node6: -0.37},。然后,，我們對節(jié)點進行拆分，使值為> 0的所有節(jié)點都位于一個集群中,，而所有其他節(jié)點都位于另一個集群中,。因此，在本例中，我們在一個集群中得到節(jié)點1,、2和3,，在第二個集群中得到節(jié)點4、5和6,。

需要注意的是,，第二個特征值表示圖中節(jié)點的緊密連接程度。對于好的,、干凈的劃分,，降低第2個特征值，讓聚類變得更好,。

對于k聚類,，我們需要修改拉普拉斯矩陣，對它進行歸一化

我們得到：

歸一化的拉普拉斯矩陣

譜聚類的優(yōu)缺點

優(yōu)點：

1. 沒有對聚類的統(tǒng)計數(shù)據(jù)做出強有力的假設——聚類技術(如K-Means聚類)假設分配給聚類的點圍繞聚類中心是球形的,。這是一個強有力的假設,，可能并不總是相關的。在這種情況下,，譜聚類有助于創(chuàng)建更精確的聚類,。
2. 易于實現(xiàn)，聚類效果好,。它可以正確地將實際屬于同一簇但由于維數(shù)減少而比其他簇中的觀測值更遠的觀測值進行聚類,。
3. 對于幾千個元素的稀疏數(shù)據(jù)集,，速度相當快,。

缺點:

1. 在最后一步中使用K-Means聚類意味著聚類并不總是相同的。它們可能隨初始中心的選擇而變化,。
2. 對于大型數(shù)據(jù)集來說,，計算開銷很大——這是因為需要計算特征值和特征向量，然后我們必須對這些向量進行聚類,。對于大型,、密集的數(shù)據(jù)集，這可能會大大增加時間復雜度,。

英文原文：https:///spectral-clustering-82d3cff3d3b7