作者：Neerja Doshi
編譯：ronghuaiyang

導讀

譜聚類，了解直覺以及背後的數學原理

什麼是聚類？

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

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

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

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

譜聚類如何工作？

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

譜聚類的步驟有哪些？

譜聚類包括三個步驟：

• 計算相似圖
• 將數據投影到低維空間
• 創建集群

步驟1—計算相似圖

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

1. ε-neighborhood圖：這裡我們連接所有兩兩距離小於ε的點。所有連接的點之間的距離大致都是相同的尺度（最多是ε)，對邊進行加權不會包含進圖中數據的更多的信息，因此，ε-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. 在這兩種情況下，在連接適當的頂點後，我們通過相鄰點的相似性對邊進行加權。
6. 全連接圖：為了構造這個圖，我們簡單地將所有點連接起來，並通過相似性sij對所有邊進行加權。該圖應該對局部鄰域關係進行建模，因此使用了高斯相似函數等相似函數。

這裡的參數σ控制鄰域的寬度，類似於ε-neighborhood圖中的參數ε。

因此，當我們為這些圖中的任意一個創建鄰接矩陣時，當點很近時Aij ~ 1，當點很遠時Aij0。

考慮一下擁有1~4節點的圖，權值(或相似度)wij及其鄰接矩陣：

步驟2—將數據投影到低維空間

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

計算圖的拉普拉斯矩陣

計算圖的拉普拉斯矩陣L的全部目的是找到它的特徵值和特徵向量，以便將數據點嵌入低維空間。現在，我們可以繼續查找特徵值。我們知道：

我們考慮下面的例子：

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

步驟3—創建集群

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

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

需要注意的是，第二個特徵值表示圖中節點的緊密連接程度。對於好的、乾淨的劃分，降低第2個特徵值，讓聚類變得更好。

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

我們得到：

歸一化的拉普拉斯矩陣

譜聚類的優缺點

優點：

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

缺點:

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

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

更多內容，請關注微信公眾號：AI公園