谱聚类

在多元统计和数据聚类中,谱聚类技术利用数据相似度矩阵的谱(特征值)在较少维度聚类之前执行降维。 相似性矩阵作为输入提供,并由对数据集中每对点的相对相似性的定量评估组成。

简介

中文名= = = = = =谱聚类


英文名

Spectral clustering

定义及描述

谱聚类算法是利用矩阵的特征向量进行聚点的聚类算法。

谱聚类是一种基于降维的聚类算法,它由两部分组成,第一部分是对数据进行一定的变换,使得交织在一起的数据分开,第二部分是使用传统的K-means算法对变换后的数据聚类。下图中的数据单纯的使用K-means会得到非常差的结果,如第四列的数据图,但是使用谱聚类可以实现非常好的聚类效果。如下图,是python sklearn中经典聚类算法的比较,第四列就是谱聚类的结果展示图。

那么,谱聚类的整体过程展示图如下:

首先是展示的带聚类数据,将数据进行变化,在用k-means等方法进行聚类,展示聚类结果,红色为一类,绿色为一类。

谱聚类是从图论中演化出来的算法,后来在聚类中得到了广泛的应用。它的主要思想是把所有的数据看做空间中的点,这些点之间可以用边连接起来。距离较远的两个点之间的边权重值较低,而距离较近的两个点之间的边权重值较高,通过对所有数据点组成的图进行切图,让切图后不同的子图间边权重和尽可能的低,而子图内的边权重和尽可能的高,从而达到聚类的目的。例子如图下所示:

算法步骤

谱聚类算法将数据集中的每个对象看作是图的顶点X,将顶点间的相似度量化作为相应顶点连接边E的权值,这样就得到一个基于相似度的无向加权图G(X, E),于是聚类问题就可以转化为图的划分问题。基于图论的最优划分准则就是使划分成的子图内部相似度最大,子图之间的相似度最小。

虽然根据不同的准则函数及谱映射方法,谱聚类算法有着不同的具体实现方法,但是这些实现方法都可以归纳为下面主要步骤:

  1. 确认输入参数,一个描述数据相似性图的临接矩阵W,和聚类的目标类数目k;
  2. 计算次数矩阵D和拉普拉斯矩阵L;
  3. 计算特征值方程Ly=λDy的前k个特征向量,记为y1,⋯,yk;
  4. 用y1,⋯,yk按列排成矩阵Y∈Rn∗k;
  5. Y的第i行的行向量记为x′i(i≤n);
  6. 对x′i使用K-means聚类;
  7. 将x′i划分的类别分配为xi的类别,即class(xi)=class(x′i);
  8. 输出聚类结果

上面的步骤只是谱聚类算法的一个总体框架,由于划分准则、相似度矩阵计算方法等因素的差别,具体的算法实现同样会有所差别,但其本质依然是图划分问题的连续放松形式。

实例讲解:

数据的相似性图

数据本身可以看成一个个的点,如果我们给某些点之间加上一条无向带权边,那么数据的结构就是一个图G=(X,E),这里X表示图中的数据点的合集,E表示带权的边。

如果这里边带的权代表这两点之间的相似程度的话,那么这个图就叫做数据的相似性图(Similarity graph)。比如下图的左边是七个数据点,右边是带了权的相似性图。

数据的相似性图不是唯一的,可以用基于不同度量的不同方法来构建该图,最常见的构建方法是对第i个数据点,离该点最近的p个数据点使用它们之间的欧几里得距离作为相似性的度量,其他较远的点相似性程度都为0。一旦构建好了相似性图G,我们就可以写下用来描述这个图的临接矩阵W。

首先算法对每个数据点标个号,比如在这个图中从1到7来标记每个数据点

临接矩阵W中元素Wij表示第ii个点xi到第j个点xj的权值(相似程度),因为xi到xj的相似程度和xj到xi的相似程度是一样的,所以对任意i,j都有wij=wji,所以W是一个对称矩阵。比如上图中的临接矩阵就是这样的:

最小割Minimum cut

在将数据从点集的结构转换为了图的结构后,可以引入更多图论中的概念来帮助理解聚类的本质。比如说最小割的概念(Minimum cut);还有的分割方式会在下面罗列。

最小割是指去掉图中的一些带权边,在使得图从联通图变为不联通图的前提下,尽可能的让去掉的边权值之和尽可能小。对于数据的相似性图来说,最小割就是要去除一些很弱的相似性,把数据点从一个互相连接的整体分为两个或者多个独立的部分,这其实就是一个聚类的过程。去除的权值就是聚类后不同组别间的相似程度,并且希望这个值尽可能的小,也就是希望不同组别之间的差距尽可能的大。下图一个最小割的例子,通过去掉权值为0.1和0.2的两条边,将数据点划分为了两个部分,也就是聚为了两类。

Normalized Cut

首先说明一下使用的记号,X代表全部数据点,Xi代表第i个数据点;A.B分别代表X的两个互斥子集,同时它们也可以被看成数据点聚成的两类。记cut(A,B)为A和B两类间的类间相似度,assoc(A,X)为A和X间的相似度。

其实这里cutcut和assocassoc的定义是一样的,但是为了它们两个的含义不同,cut是用来衡量类间的相似性,assoc是用来衡量类内的相似性。

比如说对于下图来说,

cut(A,B)=0.2+0.1=0.3

assoc(A,X)=0.8+0.7+0.7+0.9+0.2+0.1=3.4

assoc(B,X)=0.7+0.7+0.7+0.1+0.2=2.4

Normalized cut被定义为

谱聚类的本质就是要找到能最小化Ncut(A,B)的A和B。

谱聚类的求解

要求解谱聚类,即要解出哪些数据点属于A,哪些数据点属于B,为了数学描述的方便,我们用一个n维向量c来表示谱聚类的解。ci∈-1,1如果第i个数据点属于A,那么ci=−1,否则第i个点属于B,那么ci=1。先将要最小化的目标Ncut(A,B)转化为和向量c有关的形式。

这里出现的di是之前提到过的次数矩阵(Degree Matrix)的对角元。它表示所有与A类中点相连的边的权值占总权值的比例,那么有

b=k/(1-k)带入,

再记y=(1+c)−b(1−c),原优化目标可以转化为:

然而这个优化问题是一个NP难问题,但幸运的是,可以用松弛法来解决这个问题,首先将y的取值范围松弛到Rn上,然后记L=D−W,一般我们称矩阵LL为拉普拉斯矩阵,然后优化问题转化为:

这个优化目标是一个典型的瑞丽商(Rayleigh Quotient)的形式,依照标准的解法,将该优化问题转化为

然后取拉格朗日函数

对y求导,求出最小值。

【描述来源:论文, URL:http://papers.nips.cc/paper/2092-on-spectral-clustering-analysis-and-an-algorithm.pdf】

发展历史

描述

谱聚类最初出现模型于20世纪70年代,1973年,Donath和Hoffman第一次提出提出利用邻接矩阵的特征向量对图进行划分。同年,Fiedler发现利用图的拉普拉斯矩阵的第二特征向量(次小特征值所对应的特征向量)可以完成图的二分。同比之下,Hoffman和Fieder当时发表的东西更受大家认可,因为其很好地解决了谱聚类极小化问题里的NP-hard问题。近些年,谱聚类法逐渐成为最流行的聚类方法之一,并在机器学习、数据挖掘、模式识别、图像分析和生物信息学领域得到广泛的应用。

利用特征向量来解决谱聚类中的f向量选取问题,在许多不同的领域被重新发现和重新应用。同年,计算机科学家们HoffmanFiedler发现利用倒数第二小的特征向量,显然更加符合f向量的选取,

搜索集群的算法其实非常困难的,因为它在计算上很难搜索所有可能的集群。即使是一个相对较小的图,一个有100个节点的,不同分区的数目也超过了宇宙中原子数量的估计数,是20个数量级。对于几个不同的应用,物理学家,计算机科学家和统计学家已经产生了许多算法来克服这些计算上的挑战。通常,这些算法旨在通过一些经验目标函数来发现近似“最佳”集群的集群(福纳托(2010)或Fjallstrom(1998),以便从物理或工程中对这些算法进行全面的评估。

von Luxburg在2007中论文认为谱聚类很受欢迎既受欢迎,随着谱聚类日渐成熟,现在已经发现了许多不同的谱聚类的应用,如负载平衡和并行计算[Van Driessche and Roose (1995),Hendrickson和Leland(1995),分区电路进行非常大规模的集成设计Hagen和Kahng(1992)和稀疏矩阵划分Pothen, Simonand Liou(1990)。谱聚类的详细历史Spielman和邓(2007)和·von Luxburg和Bousquet(2008)在中可以找到。

以下介绍了划分规则的演变。

划分准则

谱聚类算法将聚类问题转化为图的划分问题之后,基于图论的划分准则的优劣直接影响到聚类结果的好坏。常见的划分准则有Mini cut,Average cut,Normalized cut,Min-max cut,Ratio cut,MNcut等。

  • 最小割集准则

在对图像分割中产生了较好的效果,但是该准则容易产生分割出只包含几个顶点的较小子图的歪斜分割现象。

  • 规范割集准则

在2000年Shi和Malik根据谱图理论建立了2-way划分的规范割目标函数,此方法通过计算分割之后的连接边损失值在各个子图与所有顶点之间的连接边权重总值中所占比例之和来衡量划分的优劣。

  • 比例割集准则

对于超大规模集成电路设计中的电路层次设计和分支划分问题,最大流最小割算法能够发现其中的类结构(clustering structure),但是在实际中该算法通常会产生规模非常不一致的电路分支;Kemighan-Lin算法采用固定参数的方式可以得到规模具有一定可比性的分支划分,由于电路中的分支倾向于自然结合的形成,所以通过预先设定分支规模进行划分的方法存在明显的局限。针对以上的现象Wei和Cheng提出了比例割集准则。

  • 平均割集准则

在计算机视觉中,图像原始像素条理有序地分组可以通过寻找场景结构图(Scene Structure Graph)中松散耦合的结点来完成,于是原始像素的聚合问题就转化为场景结构图的分割。Sarkar和Soundararajan提出了一种最小化两两分割之间相似度的计算方法并把它命名为平均割集准则。

  • 最小最大割集准则

Mini cut准则容易出现分割出只包含几个顶点的较小子图的歪斜分割现象,Ratio cut和Normalized cut等在一定程度上可以避免这种现象,但是当类间重叠严重时歪斜分割现象仍旧会发生。Chris Ding等人提出的基于Min-max cut的图划分方法充分体现了“子图内部相似度最大,子图之间的相似度最小”原则,能够产生比较平衡划分。

上述五种划分都是不断地将图划分为2个子图的反复迭代运算过程,当划分函数的最小值满足一定的条件时迭代过程便会终止,相应的函数可以称为2-way划分函数。

  • 多路规范割集准则

Meilă和Xu[认为可以同时把图划分为k个子图并于2004年提出了一种k-way规范割目标函数,而且对于参数k的选取问题也作了分析说明。可以发现当k=2时,MNcut与Ncut两者是等价的。

主要事件

年份

事件

相关论文

1973

Donath, W. E., & Hoffman, A. J.第一次提出用特征向量来进行谱聚类

Donath, W. E., & Hoffman, A. J. (1973). Lower bounds for the partitioning of graphs. IBM Journal of Research and Development, 17(5), 420-425.

2002

Ng, A. Y., Jordan, M. I., & Weiss, Y.对谱聚类进行调整使得在MATLAB中只需要更少的代码,并且效果也有显著提高

Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm. In Advances in neural information processing systems (pp. 849-856).

2007

Von Luxburg, U.对谱聚类进行综述

Von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and computing, 17(4), 395-416.

发展分析

瓶颈

首先,谱聚类有各种各样的算法以稍微不同的方式使用特征向量。第二,许多算法都没有证据证明它们会实际计算出一个合理的聚类。

未来发展方向

  • 如何构造相似度矩阵

如何创建相似度矩阵W,使其更加真实地反映数据点之间的近似关系,使得相近点之间的相似度更高,相异点之间的相似度更低,是谱聚类算法必须要解决的一个问题。

  • 如何自动确定聚类数目

由相似度矩阵得到拉普拉斯矩阵后,接下来要确定所需特征向量的数目,它与最终的聚类数目相等。虽然该数目可以由人工确定,但是准确地给出对聚类效率和最终的聚类质量有直接影响的数目值是个非常困难的问题。因此,如何自动确定聚类数目成为谱聚类需要解决的关键问题之一。

  • 如何选择特征向量

大多情况下的谱聚类算法直接选择前k个最大特征值对应的特征向量用于新向量空间的构造。

  • 如何解决模糊聚类的问题

尽管在文档聚类中,谱聚类取得了很好的效果。但是在文档聚类中,单个词可能属于多个类,单个文档可能是多主题的文档。这就需要我们用模糊聚类的方法解决。如何确定基于模糊聚类与谱方法的联合:如何建立模糊标准的图划分的目标函数等都是谱聚类算法在模糊聚类中所面临的问题。如何运用到大规模学习问题中:由于谱聚类算法需要求解特征值和特征向量,所以计算复杂度相对较大,针对目前强烈的大规模数据处理要求研究高效、可扩展、适宜大规模学习问题的谱聚类算法。

  • 如何提高谱聚类的运行速度

在谱聚类算法的聚类过程中需要求解矩阵的特征值与特征向量,求解非稀疏矩阵特征向量的复杂度O(n),所以处理大规模数据集的时候,计算中形成的矩阵空间非常大,求解过程不但会非常耗时,而且所需要的内存空间也非常大,面临着内存溢出的危险,对计算机内存容量的要求变得较高。因此,如何提高算法的运行速度,降低运行所需的内存空间,减少算法运行的时间和空间代价是谱聚类算法在不断扩展应用领域的过程中所面临的另一关键问题。

Contributor: Ruining Cai

相关人物
Alan Jerome Hoffman
Alan Jerome Hoffman
简介
相关人物