谱聚类综述

大数据 waitig 697℃ 百度已收录 0评论

聚类

  在了解谱聚类之前,首先需要知道聚类,聚类通俗的讲就是将一大堆没有标签的数据根据相似度分为很多簇(就是一坨坨的),将相似的聚成一坨,不相似的再聚成其他很多坨。一般的聚类算法存在的问题是k值的选择(就是簇的数量事先不知道),相似性的度量(如何判断两个样本点是否相似),如何不陷入局部最优等问题,流行的算法有k-means等一系列算法。

 

谱聚类

  顾名思义就是一种聚类算法,这个谱字应该指的就是谱图的意思,简单的来讲就是将聚类问题转化为图的分割问题,将图中相似的点聚在一起,但是这个图是从哪里来的呢???这就涉及到谱聚类的步骤了,以下是各种谱聚类算法的通俗框架。

  输入:相似性矩阵S,簇的数量k

  k值只能靠猜测了。

  这个相似性矩阵怎么得到呢?

  假设有一堆数据x1,x2,,,xn,sij = s(xi,xj),至于这个相似性度量函数s就有很多种选取方法了,最简单的就是欧氏距离了,然后就构造出了一个相似性矩阵S = (siji,j = 1….n

  1. 根据邻接矩阵S构造出一个有权无向图
  2. 有了图就可以计算图的Laplacian L(拉普拉斯矩阵)
  3. 再算出L的前k个特征向量 v1,…..vk
  4. 将特征向量作为列向量构造出特征空间V
  5. 再对V的行用k-means聚类出簇C1,…..Cn

  输出:簇

  算法可修改之处:

  • 比如相似图的构造就有knn图,全连接图,ε-neighborhood图
  • Laplacian矩阵也分为规范Laplacian和非规范Laplacian,其中非规范Laplacian也有两种。

    规范Laplacian L = D – W,D为节点的度矩阵,W为节点的权重矩阵

    非规范Laplacian

       Lsym = D-1/2LD-1/2 = I – D-1/2WD-1/2

       Lrw = D-1L = I – D-1W

  • 特征向量的选择,v不一定是L的特征向量,选择出的向量也不一定为前k个

 

谱聚类的引出

  看到这里是不是觉得一切都那么的自然,但是这个东东为啥能被人想出来呢???

  最根本的原因在于图的最优分割问题是一个NP难的问题,在得到一个基于样本相似度的无向加权图G=(V,E)之后,可以有很多种基于图论的方法来切割G,使得子图的内部相似度最大,子图间的相似度最小,切割的方法也有很多种,比如Ncut,Rcut,Avcut等多种切割方法,一般用来切割k=2的问题效果还不错,但涉及到多路规范切割(k>2)的时候,优化问题就难以解决了。

  各种切割方法的解释详见下述论文。

 

谱聚类的优势

  只要保证相似性图的稀疏,谱聚类对于大数据量的样本效率就会很高。

  而且谱聚类的求解不涉及到凸优化问题。

谱聚类的缺点

  缺点很明显k值只能靠猜测

  

由于博主是刚开始看论文的小白,所以有什么不足之处,欢迎大家指正。

 

参考文献:

  • 蔡晓妍 戴冠中 杨黎斌      谱聚类算法综述
  • Ulrike von Luxburg          A Tutorial on Spectral Clustering

本文由【waitig】发表在等英博客
本文固定链接:谱聚类综述
欢迎关注本站官方公众号,每日都有干货分享!
等英博客官方公众号
点赞 (0)分享 (0)