On Spectral Clustering: Analysis and an algorithm

• https://github.com/Sean16SYSU/MachineLearningImplement

這是一篇引用量很高（7k+）的paper。開篇的abstract就吸引人。

• 概括： 本文提出了一種簡單的譜聚類算法，該算法易于實(shí)現(xiàn)而且表現(xiàn)的不錯(cuò)，并且基于矩陣攝動(dòng)理論，我們可以分析算法并找出可以預(yù)期的良好條件。

這篇文章的算法主要是關(guān)注與n維空間的聚類點(diǎn)。對(duì)于這類問題，一個(gè)標(biāo)準(zhǔn)的方法就是基于一個(gè)生成的方法，在這些方法當(dāng)中，比如EM算法被用來學(xué)習(xí)mixture density（混合密度）。

These approaches suffer from several drawbacks. 這些方法有些缺陷。
一個(gè)比較好的方法就是用譜方法來做聚類。這里，第一步是，選從距離矩陣中獲取最大幾個(gè)特征向量。Here, one uses the top eigenvectors of a matrix derived from the distance between points.

算法

簡直不要太感動(dòng)！這篇論文把算法寫得太清晰了！！！
給定一個(gè)點(diǎn)集$S\in R^l$，然后將這個(gè)分到k個(gè)類當(dāng)中。

定義一個(gè)親和矩陣$A\in {\mathbb{R}}^{n?n}$。其中$A_{ij}=exp(?||s_i?s_j|{|}^2/2{\sigma }^2)$ 如果i不等于j，否則為0.

定義D是一個(gè)對(duì)角矩陣。對(duì)角元素是A的第i行的求和。定義一個(gè)矩陣$L=D^{?1/2}A{D}^{?1/2}$

找到L的k個(gè)最大特征向量$x_1,x_2,x_3,...,x_k$（選出正交的避免重復(fù)的特征值）。然后得到矩陣$X=[x_1,x_2,x_3,...,x_k]\in {\mathbb{R}}^{n?k}$。注意這里是將這個(gè)作為了列向量然后得到的矩陣。

定義矩陣Y，是X的正則化了每一行的之后的結(jié)果，使得X的每一行都具有單位長度。$Y_{ij}=X_{ij}/({\sum }_j{X}_{ij}^2{)}^{1/2}$

把Y的每行都作為一個(gè)在${\mathbb{R}}^k$的點(diǎn)。聚類他們到K個(gè)不同的類，通過kmeans，或者其他上面什么方法。(降低失真 minimize distortion)

將初始的點(diǎn)分配，就按照Y的每一行所分配的對(duì)應(yīng)的類j。

實(shí)現(xiàn)

• 可以跟這篇文章做對(duì)比 Spectral clustering 譜聚類講解及實(shí)現(xiàn)

import numpy as np import numpy as np from sklearn.cluster import KMeansdef spectral_cluster(X, n_clusters=3, sigma=1): '''n_cluster : cluster into n_cluster subsetsigma: a parameter of the affinity matrix'''def affinity_matrix(X, sigma=1):N = len(X)A = np.zeros((N, N))for i in range(N):for j in range(i+1, N):A[i][j] = np.exp(-np.linalg.norm(X[i] - X[j])**2 / (2 * sigma ** 2))A[j][i] = A[i][j]return AA = affinity_matrix(X, sigma)def laplacianMatrix(A):dm = np.sum(A, axis=1)D = np.diag(dm)sqrtD = np.diag(1.0 / (dm ** 0.5))return np.dot(np.dot(sqrtD, A), sqrtD)L = laplacianMatrix(A)def largest_n_eigvec(L, n_clusters):eigval, eigvec = np.linalg.eig(L)index = np.argsort(np.sum(abs(eigvec), 0))[-n_clusters:] # n_clusters largest eigenvectors' indexes.return eigvec[:, index] newX = largest_n_eigvec(L, n_clusters)def renormalization(newX):Y = newX.copy()for i in range(len(newX)):norm = 0for j in newX[i]:norm += (newX[i] ** 2)norm = norm ** 0.5Y[i] /= normreturn YY = renormalization(newX)kmeans = KMeans(n_clusters=n_clusters).fit(Y)return kmeans.labels_

• 測(cè)試效果不錯(cuò)。但是發(fā)現(xiàn)對(duì)于那些出現(xiàn)重疊部分的數(shù)據(jù)（或者是靠的比較近（在歐式空間下）的數(shù)據(jù)，分類效果就不是很好了）

• 導(dǎo)入數(shù)據(jù)

from sklearn import datasets iris = datasets.load_iris() from sklearn.decomposition import PCA X_reduced = PCA(n_components=2).fit_transform(iris.data)

• 譜聚類版本

y = spectral_cluster(X_reduced, n_clusters=3, sigma=1) plt.scatter(X_reduced[:, 0], X_reduced[:, 1], c=y, cmap=plt.cm.Set1)

• 真實(shí)數(shù)據(jù)版本

總結(jié)

以上是生活随笔為你收集整理的【论文阅读和实现】On Spectral Clustering: Analysis and an algorithm【Python实现】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。