计算机视觉
图像处理

机器学习(十一)谱聚类算法

一、算法概述

谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。  谱聚类的求解方法有很多种,其中比较简单常用的是Nomarlized cut。其算法流程如下:

1、采用knn搜索最近k邻样本,然后构造样本相似度稀疏矩阵W(N,N)(如果不采用knn,那么构造的是全连接图,不是稀疏矩阵,如果样本多的话,求解起来速度就会很慢了),两样本之间的相似度度量可采用如下公式:

这边先定义W的对角线元素为0(Wii=0),然后归一化这个W矩阵的每一行和为1。

2、对W矩阵做归一化处理后,构造归一化的拉普拉斯矩阵L(归一化的拉普拉斯矩阵的对角线元素为1,每一行所有元素和为0),即:

L=I-W

3、求解L矩阵的前k个最小特征值对应的特征向量(k为聚类的个数),然后把这K个特征向量竖着并排在一起,形成一个新的特征向量空间数据E(N,K)的矩阵。这样E每一行对应于原始数据的每一个样本,然后我们对这N行数据做k-means聚类(也可以用其它的聚类方法),得到的聚类结果就是谱聚类的结果。

二、源码实践

  1. #coding=utf-8
  2. import numpy as np
  3. import matplotlib.pyplot as plt
  4. from sklearn.cluster   import KMeans
  5. import random
  6. #生成两个高斯分布训练样本用于测试
  7. #第一类样本类
  8. mean1 = [00]
  9. cov1 = [[10], [01]]  # 协方差矩阵
  10. x1, y1= np.random.multivariate_normal(mean1, cov1, 100).T
  11. data=[]
  12. for x,y in zip(x1,y1):
  13.     data.append([x,y])
  14. #第二类样本类
  15. mean2 = [3,3]
  16. cov2 = [[10], [01]]  # 协方差矩阵
  17. x2, y2= np.random.multivariate_normal(mean2, cov2, 100).T
  18. for x,y in zip(x2,y2):
  19.     data.append([x,y])
  20. random.shuffle(data)#打乱数据
  21. data=np.asarray(data,dtype=np.float32)
  22. #算法开始
  23. #计算两两样本之间的权重矩阵,在真正使用场景中,样本很多,可以只计算邻接顶点的权重矩阵
  24. m,n=data.shape
  25. distance=np.zeros((m,m),dtype=np.float32)
  26. for i in range(m):
  27.     for j in range(m):
  28.         if i==j:
  29.             continue
  30.         dis=sum((data[i]-data[j])**2)
  31.         distance[i,j]=dis
  32. #构建归一化拉普拉斯矩阵
  33. similarity = np.exp(-1.* distance/distance.std())
  34. for i in range(m):
  35.     similarity[i,i]=0
  36. for i in range(m):
  37.     similarity[i]=-similarity[i]/sum(similarity[i])#归一化操作
  38.     similarity[i,i]=1#拉普拉斯矩阵的每一行和为0,对角线元素之为1
  39. #计算拉普拉斯矩阵的前k个最小特征值
  40. [Q,V]=np.linalg.eig(similarity)
  41. idx = Q.argsort()
  42. Q = Q[idx]
  43. V = V[:,idx]
  44. #前3个最小特征值
  45. num_clusters =3
  46. newd=V[:,:3]
  47. #k均值聚类
  48. clf = KMeans(n_clusters=num_clusters)
  49. clf.fit(newd)
  50. #显示结果
  51. for i in range(data.shape[0]):
  52.     if clf.labels_[i]==0:
  53.         plt.plot(data[i,0], data[i,1], ‘go’)
  54.     elif clf.labels_[i]==1:
  55.         plt.plot(data[i,0], data[i,1], ‘ro’)
  56.     elif clf.labels_[i]==2:
  57.         plt.plot(data[i,0], data[i,1], ‘yo’)
  58.     elif clf.labels_[i]==3:
  59.         plt.plot(data[i,0], data[i,1], ‘bo’)
  60. plt.show()

聚类结果:

参考文献:1、http://liuzhiqiangruc.iteye.com/blog/2117144

转载注明来源:CV视觉网 » 机器学习(十一)谱聚类算法

分享到:更多 ()
扫描二维码,给作者 打赏
pay_weixinpay_weixin

请选择你看完该文章的感受:

0不错 0超赞 0无聊 0扯淡 0不解 0路过

评论 4

评论前必须登录!