Python 譜聚類算法從零開始

網(wǎng)摘文苑 2019-08-31

展開全文

譜聚類算法是一種常用的無監(jiān)督機器學習算法，其性能優(yōu)于其他聚類方法。此外，譜聚類實現(xiàn)起來非常簡單，并且可以通過標準線性代數(shù)方法有效地求解。在譜聚類算法中，根據(jù)數(shù)據(jù)點之間的相似性而不是k-均值中的絕對位置來確定數(shù)據(jù)點屬于哪個類別下。具體區(qū)別可通過下圖直觀看出：

Python 譜聚類算法從零開始

譜聚類算法實現(xiàn)

譜聚類算法的基本思想是先根據(jù)樣本點計算相似度矩陣，然后計算度矩陣和拉普拉斯矩陣，接著計算拉普拉斯矩陣前k個特征值對應的特征向量，最后將這k個特征值對應的特征向量組成

Python 譜聚類算法從零開始

的矩陣U，U的每一行成為一個新生成的樣本點，對這些新生成的樣本點進行k-means聚類，聚成k類，最后輸出聚類的結果。即該算法可分為4個基本步驟：

構造相似性圖
確定鄰接矩陣W，度矩陣D和拉普拉斯矩陣L
計算矩陣L的特征向量
訓練k均值模型并使用它來對數(shù)據(jù)進行分類

Python實現(xiàn)

下面就開始通過代碼實現(xiàn)譜聚類算法。首先加載必要的庫：

import numpy as npfloat_formatter = lambda x: '%.3f' % xnp.set_printoptions(formatter={'float_kind':float_formatter})from sklearn.datasets.samples_generator import make_circlesfrom sklearn.cluster import SpectralClustering, KMeansfrom sklearn.metrics import pairwise_distancesfrom matplotlib import pyplot as pltimport networkx as nximport seaborn as snssns.set()

通常我們的數(shù)據(jù)集是由樣本(行)及其特征(列)組成的，但是譜聚類算法只能應用于下圖所示的節(jié)點連接的圖形。

Python 譜聚類算法從零開始

因此，我們必須對數(shù)據(jù)進行轉換，以便從行和列轉換為圖形。假設我們有以下數(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')

Python 譜聚類算法從零開始

首先，我們構造NxN的相似性矩陣，其中N是樣本數(shù)。矩陣的每一個點為每對點之間的歐氏距離。然后我們通過相似性矩陣來創(chuàng)建鄰接矩陣，通過設置一個閾值，比較相似性矩陣與閾值的大小關系，如果距離大于閾值就設置為0，否則為1。然后可以使用鄰接矩陣來構建圖。如果鄰接矩陣的單元格中有1，那么我們在列和行的節(jié)點之間繪制一條邊。創(chuàng)建的鄰接矩陣如下：

W = pairwise_distances(X, metric='euclidean')vectorizer = np.vectorize(lambda x: 1 if x < 5 else 0)W = np.vectorize(vectorizer)(W)print(W)

Python 譜聚類算法從零開始

接下來我們通過networkx來可視化節(jié)點圖形。定義繪圖函數(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)

下面我們隨機創(chuàng)建一個圖并輸出其鄰接矩陣。

G = nx.random_graphs.erdos_renyi_graph(10, 0.5)draw_graph(G)W = nx.adjacency_matrix(G)print(W.todense())

Python 譜聚類算法從零開始

當我們構建好鄰接矩陣，我們就可以開始構造度矩陣。對于度矩陣的每一行，我們通過對鄰接矩陣中相應行的所有元素求和來表示度矩陣的對角線。然后，我們通過從度矩陣中減去鄰接矩陣來計算拉普拉斯矩陣。計算代碼和計算結果如下：

# 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)

Python 譜聚類算法從零開始

根據(jù)得到拉普拉斯矩陣，我們就可以利用它的一個特殊屬性來分類我們的數(shù)據(jù)。即如果圖（W）具有K個連通分量，則L具有特征值為0的K個特征向量。因此，因為在我們當前的例子中我們只有一個分量，所以只有一個特征值等于0。計算特征值與特征向量代碼如下:

e, v = np.linalg.eig(L)# eigenvaluesprint('eigenvalues:')print(e)# eigenvectorsprint('eigenvectors:')print(v)

Python 譜聚類算法從零開始

可以看到，計算的特征值中只有一個為0。與我們的結論完全吻合。下邊我們再來驗證一個有兩個連通分量的示例。

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())

Python 譜聚類算法從零開始