谱聚类
原创
定义：
谱聚类是一种基于图论的聚类算法，他的思想是将数据集转化称为无向带权图，然后将在各图划分成为两个或两个以上的最优子图，这些最优图的内部尽量相似，子图间的距离尽量远。
大致流程：
将所有数据看做图中间的点，点与点之间用边相连，距离较远的两个点权值低反之高，然后切图，切图的目标就是切图之后子图之间的距离尽量远，图内差异性尽量小（这里的差异是指点与点之间距离尽量小）。
谱聚类算法流程：
input:dataset(x1,x2,...,xn)
output:cluster(c1,c2,...,ck)
- 根据输入的数据构建数据集的相似矩阵S
- 根据相似S矩阵构建邻接矩阵W，度矩阵D
- 计算拉普拉斯矩阵L
- 构建标准化后的拉普拉斯矩阵D(**- 1/2)LD(** 1/2)
- 计算D(**- 1/2)LD(** 1/2)最小的k1个特征值所各自对应的特征向量f
- 将各自对应的特征向星f组成的矩阵按行标准化，最终组成nxk1维的特征矩阵F
- 对F中的每一行作为一 个k1维的样本，共个样本，用输入的聚类方法进行聚类，聚类维数为k2。
- 得到output
概念解释：
无向图：没有方向的图，也可以说没有出度好入度，Wij=Wji
度：和某个定点连接的所有边的权重之和
例子：
邻接矩阵W：比如数字1对应第一行，和它相连的有2和5，那就在第2,第5列那里标记为1，其他数字同理，就得到了邻接矩阵。
度矩阵D：把W的每一列的数字之和放到到对角线的位置：
拉普拉斯矩阵：拉普拉斯矩阵的定义就是L=D-W,则对应的L矩阵如下：
无向图G的切图:就是将图G(V,E)切成相互没有连接的k个子图
那么如何切图可以让子图内的点权重和高，子图间的点权重和低呢:
先定义两个子图A和B之间的切图权重为:
再定义有k个子图的切图cut为: 即所有子图Ai与其补集A;之间的切图权重之和:
这样当我们最小化这个cut时，就相当于让子图间的点权重和低，以最小化cut标，在一个问题，就是有时候最小cut的切图式，却不是最优的。
为避免最小切图导致的切图效果不佳，需要对每个子图的规模做出限定，一般有两种切图方式，RatioCut，Ncut，常用的是 Ncut切图。
面临的问题：
- 相似度矩阵的构建问题：业界一般使用高斯相似函数或者k近邻来作为相似度量，一般建议使用k近邻的方式来计算相似度权值
- 聚类数目的给定
- 如何选择特征向量
- 如何提高谱聚类的执行效率
应用：
cv,图形聚类等
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。