作者：Neerja Doshi
編譯：ronghuaiyang

導(dǎo)讀

什么是聚類？

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

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

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

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

譜聚類如何工作？

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

譜聚類的步驟有哪些？

譜聚類包括三個步驟：

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

步驟1—計(jì)算相似圖

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

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

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

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

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

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

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

計(jì)算圖的拉普拉斯矩陣

我們上面例子的圖的拉普拉斯矩陣

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

我們考慮下面的例子：

我們計(jì)算L的特征值和特征向量。

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

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

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

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

特征向量v2給出一個2分聚類

對于k聚類，我們需要修改拉普拉斯矩陣，對它進(jìn)行歸一化

我們得到：

歸一化的拉普拉斯矩陣

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

優(yōu)點(diǎn)：

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

缺點(diǎn):

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

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