谱聚类是一种基于图论的聚类算法,他的思想是将数据集转化称为无向带权图,然后将在各图划分成为两个或两个以上的最优子图,这些最优图的内部尽量相似,子图间的距离尽量远。
将所有数据看做图中间的点,点与点之间用边相连,距离较远的两个点权值低反之高,然后切图,切图的目标就是切图之后子图之间的距离尽量远,图内差异性尽量小(这里的差异是指点与点之间距离尽量小)。
input:dataset(x1,x2,...,xn)
output:cluster(c1,c2,...,ck)
无向图:没有方向的图,也可以说没有出度好入度,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切图。
cv,图形聚类等
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。