|
譜聚類算法是一種常用的無(wú)監(jiān)督機(jī)器學(xué)習(xí)算法，其性能優(yōu)于其他聚類方法。 此外，譜聚類實(shí)現(xiàn)起來(lái)非常簡(jiǎn)單，并且可以通過(guò)標(biāo)準(zhǔn)線性代數(shù)方法有效地求解。 在譜聚類算法中，根據(jù)數(shù)據(jù)點(diǎn)之間的相似性而不是k-均值中的絕對(duì)位置來(lái)確定數(shù)據(jù)點(diǎn)屬于哪個(gè)類別下。具體區(qū)別可通過(guò)下圖直觀看出： 譜聚類算法實(shí)現(xiàn) 譜聚類算法的基本思想是先根據(jù)樣本點(diǎn)計(jì)算相似度矩陣，然后計(jì)算度矩陣和拉普拉斯矩陣，接著計(jì)算拉普拉斯矩陣前k個(gè)特征值對(duì)應(yīng)的特征向量，最后將這k個(gè)特征值對(duì)應(yīng)的特征向量組成 的矩陣U，U的每一行成為一個(gè)新生成的樣本點(diǎn)，對(duì)這些新生成的樣本點(diǎn)進(jìn)行k-means聚類，聚成k類，最后輸出聚類的結(jié)果。即該算法可分為4個(gè)基本步驟：
Python實(shí)現(xiàn) 下面就開(kāi)始通過(guò)代碼實(shí)現(xiàn)譜聚類算法。首先加載必要的庫(kù)： 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ù)集是由樣本(行)及其特征(列)組成的， 但是譜聚類算法只能應(yīng)用于下圖所示的節(jié)點(diǎn)連接的圖形。 因此，我們必須對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)換，以便從行和列轉(zhuǎn)換為圖形。 假設(shè)我們有以下數(shù)據(jù)集。 我們可以清楚地看到數(shù)據(jù)可以分為三個(gè)集群。 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ù)。 矩陣的每一個(gè)點(diǎn)為每對(duì)點(diǎn)之間的歐氏距離。然后我們通過(guò)相似性矩陣來(lái)創(chuàng)建鄰接矩陣，通過(guò)設(shè)置一個(gè)閾值，比較相似性矩陣與閾值的大小關(guān)系，如果距離大于閾值就設(shè)置為0，否則為1。然后可以使用鄰接矩陣來(lái)構(gòu)建圖。 如果鄰接矩陣的單元格中有1，那么我們?cè)诹泻托械墓?jié)點(diǎn)之間繪制一條邊。創(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) 接下來(lái)我們通過(guò)networkx來(lái)可視化節(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)建一個(gè)圖并輸出其鄰接矩陣。 G = nx.random_graphs.erdos_renyi_graph(10, 0.5)draw_graph(G)W = nx.adjacency_matrix(G)print(W.todense()) 當(dāng)我們構(gòu)建好鄰接矩陣，我們就可以開(kāi)始構(gòu)造度矩陣。對(duì)于度矩陣的每一行，我們通過(guò)對(duì)鄰接矩陣中相應(yīng)行的所有元素求和來(lái)表示度矩陣的對(duì)角線。然后，我們通過(guò)從度矩陣中減去鄰接矩陣來(lái)計(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ù)得到拉普拉斯矩陣，我們就可以利用它的一個(gè)特殊屬性來(lái)分類我們的數(shù)據(jù)。即如果圖（W）具有K個(gè)連通分量，則L具有特征值為0的K個(gè)特征向量。因此，因?yàn)樵谖覀儺?dāng)前的例子中我們只有一個(gè)分量，所以只有一個(gè)特征值等于0。計(jì)算特征值與特征向量代碼如下: e, v = np.linalg.eig(L)# eigenvaluesprint('eigenvalues:')print(e)# eigenvectorsprint('eigenvectors:')print(v) 可以看到，計(jì)算的特征值中只有一個(gè)為0。與我們的結(jié)論完全吻合。下邊我們?cè)賮?lái)驗(yàn)證一個(gè)有兩個(gè)連通分量的示例。 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ì)算得到的特征值和特征向量如下，可以看到特征值中有兩個(gè)0.
接下來(lái)我們就根據(jù)特征向量對(duì)數(shù)據(jù)進(jìn)行聚類分析。 U = np.array(v[:, i[1]])km = KMeans(init='k-means++', n_clusters=3)km.fit(U)km.labels_ 得到聚類標(biāo)簽如下：
到此，我們已經(jīng)基本實(shí)現(xiàn)了譜聚類算法，總的來(lái)說(shuō)，譜聚類算法的原理并不復(fù)雜，實(shí)現(xiàn)起來(lái)也比較容易，文中代碼比較散亂，大家可以根據(jù)文中的思路將代碼組合起來(lái)，這將更有助于學(xué)習(xí)理解譜聚類算法原理。 |
|
|
