谱聚类

import matplotlib.pyplot as plt
import numpy as np
from numpy import linalg as LA
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics.pairwise import rbf_kernel
from sklearn.preprocessing import normalize 
plt.rcParams['axes.unicode_minus']=False
plt.rcParams['font.sans-serif']=['SimHei']
def similarity_function(points):
    """
    相似性函数，利用径向基核函数计算相似性矩阵，对角线元素置为0   
    """
    res=rbf_kernel(points)
    for i in range(len(res)):
        res[i,i]=0
    return res 
def spectral_clustering(points,k):
    W=similarity_function(points)
    D=np.diag(np.sum(W,axis=1))
    Dn=np.sqrt(LA.inv(D))
    #Dn=np.diag(np.power(np.sum(W,axis=1),-0.5))
    #拉普拉斯矩阵：L=Dn*(D-W)*Dn=I-Dn*W*Dn
    L=np.eye(len(points))-np.dot(np.dot(Dn,W),Dn)
    eigvals,eigvecs=LA.eig(L)
    #前k小的特征值对应的索引，argsort函数
    indices=np.argsort(eigvals)[:k]
    #取出前k小的特征值对应的特征向量并进行正则化
    k_smallest_eigenvectors=normalize(eigvecs[:, indices])
    #利用KMeans进行聚类
    return KMeans(n_clusters=k).fit_predict(k_smallest_eigenvectors) 
X,y=make_blobs()
labels=spectral_clustering(X,5) 
plt.style.use('ggplot')
#原数据
fig,(ax0,ax1)=plt.subplots(ncols=2)
ax0.scatter(X[:,0], X[:,1],c=y)
ax0.set_title('原数据')
#谱聚类
ax1.scatter(X[:,0], X[:,1],c=labels)
ax1.set_title('谱聚类')
plt.show()