譜聚類算法是一種常用的無監(jiān)督機(jī)器學(xué)習(xí)算法，其性能優(yōu)于其他聚類方法。 此外，譜聚類實(shí)現(xiàn)起來非常簡單，并且可以通過標(biāo)準(zhǔn)線性代數(shù)方法有效地求解。 在譜聚類算法中，根據(jù)數(shù)據(jù)點(diǎn)之間的相似性而不是k-均值中的絕對位置來確定數(shù)據(jù)點(diǎn)屬于哪個類別下。具體區(qū)別可通過下圖直觀看出：
譜聚類算法實(shí)現(xiàn)
譜聚類算法的基本思想是先根據(jù)樣本點(diǎn)計(jì)算相似度矩陣，然后計(jì)算度矩陣和拉普拉斯矩陣，接著計(jì)算拉普拉斯矩陣前k個特征值對應(yīng)的特征向量，最后將這k個特征值對應(yīng)的特征向量組成
的矩陣U，U的每一行成為一個新生成的樣本點(diǎn)，對這些新生成的樣本點(diǎn)進(jìn)行k-means聚類，聚成k類，最后輸出聚類的結(jié)果。即該算法可分為4個基本步驟：
Python實(shí)現(xiàn)
下面就開始通過代碼實(shí)現(xiàn)譜聚類算法。首先加載必要的庫：
通常我們的數(shù)據(jù)集是由樣本(行)及其特征(列)組成的， 但是譜聚類算法只能應(yīng)用于下圖所示的節(jié)點(diǎn)連接的圖形。
因此，我們必須對數(shù)據(jù)進(jìn)行轉(zhuǎn)換，以便從行和列轉(zhuǎn)換為圖形。 假設(shè)我們有以下數(shù)據(jù)集。 我們可以清楚地看到數(shù)據(jù)可以分為三個集群。
X = np.array([ [1, 3], [2, 1], [1, 1], [3, 2], [7, 8], [9, 8], [9, 9], [8, 7], [13, 14], [14, 14], [15, 16], [14, 15]])plt.scatter(X[:,0], X[:,1], alpha=0.7, edgecolors='b')plt.xlabel('Weight')plt.ylabel('Height')
首先，我們構(gòu)造NxN的相似性矩陣，其中N是樣本數(shù)。 矩陣的每一個點(diǎn)為每對點(diǎn)之間的歐氏距離。然后我們通過相似性矩陣來創(chuàng)建鄰接矩陣，通過設(shè)置一個閾值，比較相似性矩陣與閾值的大小關(guān)系，如果距離大于閾值就設(shè)置為0，否則為1。然后可以使用鄰接矩陣來構(gòu)建圖。 如果鄰接矩陣的單元格中有1，那么我們在列和行的節(jié)點(diǎn)之間繪制一條邊。創(chuàng)建的鄰接矩陣如下：
接下來我們通過networkx來可視化節(jié)點(diǎn)圖形。定義繪圖函數(shù)draw_graph():
def draw_graph(G): pos = nx.spring_layout(G) nx.draw_networkx_nodes(G, pos) nx.draw_networkx_labels(G, pos) nx.draw_networkx_edges(G, pos, width=1.0, alpha=0.5)
下面我們隨機(jī)創(chuàng)建一個圖并輸出其鄰接矩陣。
當(dāng)我們構(gòu)建好鄰接矩陣，我們就可以開始構(gòu)造度矩陣。對于度矩陣的每一行，我們通過對鄰接矩陣中相應(yīng)行的所有元素求和來表示度矩陣的對角線。然后，我們通過從度矩陣中減去鄰接矩陣來計(jì)算拉普拉斯矩陣。計(jì)算代碼和計(jì)算結(jié)果如下：
# degree matrixD = np.diag(np.sum(np.array(W.todense()), axis=1))print('degree matrix:')print(D)# laplacian matrixL = D - Wprint('laplacian matrix:')print(L)根據(jù)得到拉普拉斯矩陣，我們就可以利用它的一個特殊屬性來分類我們的數(shù)據(jù)。即如果圖（W）具有K個連通分量，則L具有特征值為0的K個特征向量。因此，因?yàn)樵谖覀儺?dāng)前的例子中我們只有一個分量，所以只有一個特征值等于0。計(jì)算特征值與特征向量代碼如下:
可以看到，計(jì)算的特征值中只有一個為0。與我們的結(jié)論完全吻合。下邊我們再來驗(yàn)證一個有兩個連通分量的示例。
G = nx.Graph()G.add_edges_from([[1, 2],[1, 3], [1, 4], [2, 3], [2, 7],[3, 4],[4, 7], [1, 7], [6, 5], [5, 8],[6, 8], [9, 8], [9, 6]])draw_graph(G)W = nx.adjacency_matrix(G)print(W.todense())
計(jì)算得到的特征值和特征向量如下，可以看到特征值中有兩個0.
接下來我們就根據(jù)特征向量對數(shù)據(jù)進(jìn)行聚類分析。
得到聚類標(biāo)簽如下：
到此，我們已經(jīng)基本實(shí)現(xiàn)了譜聚類算法，總的來說，譜聚類算法的原理并不復(fù)雜，實(shí)現(xiàn)起來也比較容易，文中代碼比較散亂，大家可以根據(jù)文中的思路將代碼組合起來，這將更有助于學(xué)習(xí)理解譜聚類算法原理。
