谱聚类

广义上来说,任何在算法中用到SVD/特征值分解的,都叫Spectral Algorithm。顺便说一下,对于任意矩阵只存在奇异值分解,不存在特征值分解。对于正定的对称矩阵,奇异值就是特征值,奇异向量就是特征向量。

传统的聚类算法,如K-Means、EM算法都是建立在凸球形样本空间上,当样本空间不为凸时,算法会陷入局部最优,最终结果受初始参数的选择影响比较大。而谱聚类可以在任意形状的样本空间上聚类,且收敛于全局最优解。

谱聚类和CHAMELEON聚类很像,都是把样本点的相似度放到一个带权无向图中,采用“图划分”的方法进行聚类。只是谱聚类算法在进行图划分的时候发现计算量很大,转而求特征值去了,而且最后还在几个小特征向量组成的矩阵上进行了K-Means聚类

Simply speaking,谱聚类算法分为3步:

  1. 构造一个N×N的权值矩阵W,Wij表示样本i和样本j的相似度,显然W是个对称矩阵。相似度的计算方法很多了,你可以用欧拉距离、街区距离、向量夹角、皮尔森相关系数等。并不是任意两个点间的相似度都要表示在图上,我们希望的权值图是比较稀疏的,有2种方法:权值小于阈值的认为是0;K最邻近方法,即每个点只和跟它最近的k个点连起来,CHAMELEON算法的第1阶段就是这么干的。再构造一个对角矩阵D,Dii为W第i列元素之和。最后构造矩阵L=D-W。可以证明L是个半正定和对称矩阵。
  2. 求L的前K小特征值对应的特征向量(这要用到奇异值分解了)。把K个特征向量放在一起构造一个N×K的矩阵M。
  3. 把M的每一行当成一个新的样本点,对这N个新的样本点进行K-Means聚类。

原文来自:博客园(华夏35度)http://www.cnblogs.com/zhangchaoyang 作者:Orisun

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 聚类算法总结

    (本文转自网上,具体出处忘了是哪里的,好像是上海一位女士在网上的博文,此处转载,用以备查,请原作者见谅) 聚类算法总结: --------------...

    AIHGF
  • 谱聚类

    基于无向加权图G=(V,E),其中每个顶点vi对应一个xi,顶点vi和vj间的边有权值wij≥0

    AIHGF
  • SVD在推荐系统中的应用

    参考自:http://www.igvita.com/2007/01/15/svd-recommendation-system-in-ruby/

    AIHGF
  • 理解谱聚类

    聚类是典型的无监督学习问题,其目标是将样本集划分成多个类,保证同一类的样本之间尽量相似,不同类的样本之间尽量不同,这些类称为簇(cluster)。与有监督的分类...

    SIGAI学习与实践平台
  • 聚类算法,k-means,高斯混合模型(GMM)

    什么是聚类算法?聚类是一种机器学习技术,它涉及到数据点的分组。给定一组数据点,我们可以使用聚类算法将每个数据点划分为一个特定的组。理论上,同一组中的数据点应该具...

    大数据技术与机器学习
  • 机器学习(5):几个重要矩阵

    1 可逆矩阵 矩阵A首先是方阵,并且存在另一个矩阵B,使得它们的乘积为单位阵,则称B为A的逆矩阵。如下所示,利用numpy模块求解方阵A的逆矩阵,B,然后再看一...

    double
  • 机器学习中的线性代数:关于常用操作的新手指南

    大数据文摘
  • 【图像分类】简述无监督图像分类发展现状

    无监督图像分类问题是图像分类领域一项极具挑战的研究课题,本文介绍了无监督图像分类算法的发展现状,供大家参考学习。

    用户1508658
  • 深度学习中的基础线代知识-初学者指南

    导语:在经过一天之后,我们的活动人数已经达到40人了,感谢大家对小编的支持,同时在本文末附上前一天的众筹榜单。希望能跟小伙伴们度过愉快的6天! ? 上过 Jer...

    IT派
  • 数据挖掘算法及相关应用

    我们生活在信息爆炸的时代,每时每刻都在产生海量的数椐。我们在微博、微信、社交网站、门户网站、移动终端等众多的设备商产生的海量数据,面临着无法处理数据的困境。例如...

    黄成甲

扫码关注云+社区

领取腾讯云代金券