谱聚类

谱聚类是广泛使用的聚类算法,比起传统的K-Means算法,谱聚类对数据分布的适应性更强,聚类效果也很优秀,同时聚类的计算量也小很多,更加难能可贵的是实现起来也不复杂。谱聚类是从图论中演化出来的算法,后来在聚类中得到了广泛的应用。它的主要思想是把所有的数据看做空间中的点,这些点之间可以用边连接起来。距离较远的两个点之间的边权重值较低,而距离较近的两个点之间的边权重值较高,通过对所有数据点组成的图进行切图,让切图后不同的子图间边权重和尽可能的低,而子图内的边权重和尽可能的高,从而达到聚类的目的。


建立邻接矩阵的方法有ϵ-邻近法,K邻近法和全连接法,在实际的应用中,使用全连接法来建立邻接矩阵是最普遍的,而在全连接法中使用高斯核函数是最普遍的。无向图切图有RatioCut和Ncut两种方法。
下面以Ncut总结的谱聚类算法流程。
输入:样本集X=(x1,x2,…,xn),相似矩阵的生成方式, 降维后的维度k1, 聚类方法,聚类后的维度k2。输出: 簇划分C(c1,c2,…ck2).
1) 计算点与所有点的相似性Sij
2)根据Sij构建加权邻接矩阵W,构建度矩阵D
3)计算出拉普拉斯矩阵L
4)构建标准化后的拉普拉斯矩阵D−1/2LD−1/2
5)计算D−1/2LD−1/2最小的k1个特征值所各自对应的特征向量
6) 将各自对应的特征向量组成n×k1维的特征矩阵U
7) 将U转化为H,按行标准化
7)对H中的每一行作为一个k1维的样本,共n个样本,用输入的聚类方法进行聚类,聚类维数为k2。
8)得到簇划分C(c1,c2,…ck2).
谱聚类算法的主要优点有:
1)谱聚类只需要数据之间的相似度矩阵,因此对于处理稀疏数据的聚类很有效。这点传统聚类算法比如K-Means很难做到
2)由于使用了降维,因此在处理高维数据聚类时的复杂度比传统聚类算法好。
谱聚类算法的主要缺点有:
1)如果最终聚类的维度非常高,则由于降维的幅度不够,谱聚类的运行速度和最后的聚类效果均不好。
2) 聚类效果依赖于相似矩阵,不同的相似矩阵得到的最终聚类效果可能很不同。
参会人员:
教师:安宁老师,杨矫云
学生:陈绪,韩朋,江思源,李雨龙,明鉷,唐晨,滕越,肖勇博,严金戈,
姚小慧,殷越
请假人员:景波,刘杰

anyShare分享到:
This entry was posted in 例会. Bookmark the permalink.

发表评论