谱聚类(Spectral Clustering, SC)是一种基于图论的聚类方法。
将带权无向图划分为两个或两个以上的最优子图,使子图内部尽量相似,而子图间距离尽量距离较远,以达到常见的聚类的目的。
"带权无向图"这个词太学术了,我们换一种叫法,即:相似度矩阵。
假设我们有一个相似度矩阵,矩阵中存的是所有对象的两两相似度。
那么这个矩阵应该有如下性质:
- 矩阵为N * N,N为对象总数
- 矩阵对角线的值为0,自己和自己相似个毛啊
- 矩阵为对称矩阵,及相似度是无向的
我们将该矩阵记为:W。
谱聚类的任务就是根据这个相似度矩阵,将这一大堆对象,分成不同的小堆,小堆内部的对象彼此都很像,小堆之间则不像。
谱聚类本身也提供了好几种不同的分割(cut)方法,每种方法对应一种优化目标。
本文只介绍其中比较常见,也是比较实用,而且实现起来也比较经济的一种:Nomarlized cut.
说白了,就是你最应该掌握和使用的一种,好了,进入正题。
当你得到一个相似度矩阵W后,即可通过以下几个步骤,来得到对应的图分割方案:
1. 计算对角矩阵D[N*N]。,公式如下:
D矩阵为对角矩阵,对角线上的值为W矩阵中对应行或列的和。
2. 计算拉普拉斯矩阵(Laplacian) L:
3. 归一化L矩阵
4. 计算归一化后L矩阵的K个最小特征值及对应的特征向量
将K个特征向量竖着并排放在一起,形成一个N*K的特征矩阵,记为Q。
5. 对特征矩阵Q做kmeans聚类,得到一个N维向量C。
分别对应相似度矩阵W中每一行所代表的对象的所属类别,这也就是最终的聚类结果。
此外:
关于第3步中,对拉普拉斯矩阵归一化时,归一化公式进行变换得到:
令:
则在第4步中,我们可以将求L的K个最小特征值及其对应的特征向量的问题,转化为求矩阵E的K个最大的特征值及其对应的特征向量。
---可以证明:L的K个最小特征值对应的特征向量,分别对应于E的K个最大的特征值对应的特征向量。
且矩阵L的最小特征值为0,对应于矩阵E最大的特征值为1.矩阵L的第K小特征值等于1-矩阵E的第K大特征值
之所以要这么做,是因为在数值计算中,求矩阵的最大特征值,往往要比求最小特征值更方便和高效。
OK,至此,谱聚类就完成了,关于谱聚类的其他问题,诸如公式的推导,以及谱聚类的物理意义等,可参考博文:谱聚类算法。
谱聚类的实现很简单,按照上述5个步骤按部就班即可,在matlab中只需寥寥数行:
function C = SpectralClustering(W, k) [n,m] = size(W) s = sum(W); D = full(sparse(1:n, 1:n, s)); E = D^(-1/2)*W*D^(-1/2); [Q, V] = eigs(E, k); C = kmeans(Q, k); end
在整个实现过程中,比较麻烦的就是E矩阵特征值的求解。
在自己实现时,可以调用已有的线性代数的包来完成这一步。
相关推荐
谱聚类算法即python实现,包括python sklearn库中关于谱聚类参数的描述,较详细地说明谱聚类算法中各个参数的含义并且给出一些调参方法。
【图像分割】基于谱聚类算法实现图像分割matlab源码.md
谱聚类算法实现信号分类,并对原有算法进行了优化
MYAP:基于划分的聚类AP(Affinity Propagation Clustering Algorithm )算法的底层实现--近邻传播聚类算法 Adaptive-DBSCAN:自适应的基于密度的空间聚类(Adaptive Density-Based Spatial Clustering of ...
为了解决初值敏感问题,提出了基于CMT-FCM(借鉴历史知识的类中心距离极大化聚类算法)的自适应谱聚类算法。该算法以样本空间的标准差作为尺度参数,实现了尺度参数的自适应选取,提高了算法效率;而通过借鉴历史...
k-均值聚类算法实现灰度图像分割,输入图像矩阵和聚类中心个数,返回为最终的聚类中心
包括K-Means,二分K-Means算法,谱聚类算法,高斯混合聚类算法等常用聚类算法实现,并且有注释解释代码、
java版的DBSCAN聚类算法实现,是典型的算法思路实现,遍历未访问的所有点,如果是核心点,就新建一个簇,然后遍历其邻域内的所有点集A,不断扩展,如果簇内的点时核心点,就将其邻域所有点纳入点集A,并从点集移除已...
K-means聚类算法是一种迭代求解的聚类分析算法,其步骤是随机选取K个对象作为初始的聚类中心,然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象...
K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-...
名称:DPC聚类算法 功能:聚类数据集 类别:密度聚类算法
最近在Science上的一篇基于密度的聚类算法《Clustering by fast search and find of density peaks》引起了大家的关注(在我的博文“论文中的机器学习算法——基于密度峰值的聚类算法”中也进行了中文的描述)。...
基于K-means聚类算法的图像分割 算法的基本原理: 基于K-means聚类算法的图像分割以图像中的像素为数据点,按照指定的簇数进行聚类,然后将每个像素点以其对应的聚类中心替代,重构该图像。 算法步骤: ①随机选取...
模糊 C 均值聚类(FCM),即众所周知的模糊 ISODATA,是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。 1973 年, Bezdek 提出了该算法,作为早期硬 C 均值聚类(HCM)方法的一种改进。本代码是基于...
这几天由于工作需要,对DBSCAN聚类算法进行了C++的实现。时间复杂度O(n^2),主要花在算每个点领域内的点上。算法很简单,现共享大家参考,也希望有更多交流。 数据点类型描述如下: 代码如下:#include using ...
利用matlab语言实现了协同模糊聚类算法
K-MEANS聚类算法的实现K-MEANS聚类算法的实现
能够递归实现输电断面的识别;功能强大;谱聚类算法,IEEE39,14节点测试通过。可以自由拓展,对电力系统研究方向的同学有用
针对自调节谱聚类算法的缺陷,提出一种新的自适应谱聚类算法。它用全局平均N近邻距离作为比例参数σ,利用本征矢差异来估计最佳聚类分组数k,达到了比前者更好的效果,且更容易实现。在彩色图像分割实际应用中的实验结果...
对主要聚类算法进行实现:基于划分的聚类算法,基于密度的聚类算法,基于层次的聚类算法。并且重点实现“基于快速搜索与寻找密度峰值的聚类”算法,并对其进行改进:自动获取聚类中心数