Categories

Calendar

February 2018
M T W T F S S
« Jun    
 1234
567891011
12131415161718
19202122232425
262728  

漫谈 Clustering (4): Spectral Clustering

cluster_logo本文是“漫谈 Clustering 系列”中的第 6 篇,参见本系列的其他文章

如果说 K-meansGMM 这些聚类的方法是古代流行的算法的话,那么这次要讲的 Spectral Clustering 就可以算是现代流行的算法了,中文通常称为“谱聚类”。由于使用的矩阵的细微差别,谱聚类实际上可以说是一“类”算法。

Spectral Clustering 和传统的聚类方法(例如 K-means)比起来有不少优点:

  • K-medoids 类似,Spectral Clustering 只需要数据之间的相似度矩阵就可以了,而不必像 K-means 那样要求数据必须是 N 维欧氏空间中的向量。
  • 由于抓住了主要矛盾,忽略了次要的东西,因此比传统的聚类算法更加健壮一些,对于不规则的误差数据不是那么敏感,而且 performance 也要好一些。许多实验都证明了这一点。事实上,在各种现代聚类算法的比较中,K-means 通常都是作为 baseline 而存在的。 :p
  • 计算复杂度比 K-means 要小,特别是在像文本数据或者平凡的图像数据这样维度非常高的数据上运行的时候。

突然冒出这么一个要求比 K-means 要少,结果比 K-means 要好,算得还比 K-means 快的东西,实在是让人不得不怀疑是不是江湖骗子啊。所以,是骡子是马,先拉出来溜溜再说。不过,在 K-medoids 那篇文章中曾经实际跑过 K-medoids 算法,最后的结果也就是一个 accuracy ,一个数字又不能画成图表之类的,看起来实在是没意思,而且 K-means 跑起来实在是太慢了,所以这里我还是稍微偷懒一下,直接引用一下一篇论文里的结果吧。

结果来自论文 Document clustering using locality preserving indexing 这篇论文,这篇论文实际上是提的另一种聚类方法(下次如果有机会也会讲到),不过在它的实验中也有 K-means 和 Spectral Clustering 这两组数据,抽取出来如下所示:

k TDT2 Reuters-21578
K-means SC K-means SC
2 0.989 0.998 0.871 0.923
3 0.974 0.996 0.775 0.816
4 0.959 0.996 0.732 0.793
9 0.852 0.984 0.553 0.625
10 0.835 0.979 0.545 0.615

其中 TDT2 和 Reuters-21578 分别是两个被广泛使用的标准文本数据集,虽然在不同的数据集上得出来的结果并不能直接拿来比较,但是在同一数据集上 K-means 和 SC (Spectral Clustering) 的结果对比就一目了然了。实验中分别抽取了这两个数据集中若干个类别(从 2 类到 10 类)的数据进行聚类,得出的 accuracy 分别在上表中列出(我偷懒没有全部列出来)。可以看到,Spectral Clustering 这里完胜 K-means 。

spectral_clustering这么强大的算法,再戴上“谱聚类”这么一个高深莫测的名号,若不是模型无比复杂、包罗宇宙,就肯定是某镇山之宝、不传秘籍吧?其实不是这样,Spectral Clustering 不管从模型上还是从实现上都并不复杂,只需要能求矩阵的特征值和特征向量即可──而这是一个非常基本的运算,任何一个号称提供线性代数运算支持的库都理应有这样的功能。而关于 Spectral Clustering 的秘籍更是满街都是,随便从地摊上找来一本,翻开便可以看到 Spectral Clustering 算法的全貌:

  1. 根据数据构造一个 Graph ,Graph 的每一个节点对应一个数据点,将相似的点连接起来,并且边的权重用于表示数据之间的相似度。把这个 Graph 用邻接矩阵的形式表示出来,记为 W 。一个最偷懒的办法就是:直接用我们前面在 K-medoids 中用的相似度矩阵作为 W
  2. W 的每一列元素加起来得到 N 个数,把它们放在对角线上(其他地方都是零),组成一个 N\times N 的矩阵,记为 D 。并令 L = D-W
  3. 求出 L 的前 k 个特征值(在本文中,除非特殊说明,否则“前 k 个”指按照特征值的大小从小到大的顺序)\{\lambda\}_{i=1}^k 以及对应的特征向量 \{\mathbf{v}\}_{i=1}^k
  4. 把这 k 个特征(列)向量排列在一起组成一个 N\times k 的矩阵,将其中每一行看作 k 维空间中的一个向量,并使用 K-means 算法进行聚类。聚类的结果中每一行所属的类别就是原来 Graph 中的节点亦即最初的 N 个数据点分别所属的类别。

就是这么几步,把数据做了一些诡异的变换,然后还在背后偷偷地调用了 K-means 。到此为止,你已经可以拿着它上街去招摇撞骗了。不过,如果你还是觉得不太靠谱的话,不妨再接着往下看,我们再来聊一聊 Spectral Clustering 那几个“诡异变换”背后的道理何在。

其实,如果你熟悉 Dimensional Reduction (降维)的话,大概已经看出来了,Spectral Clustering 其实就是通过 Laplacian Eigenmap 的降维方式降维之后再做 K-means 的一个过程──听起来土多了。不过,为什么要刚好降到 k 维呢?其实整个模型还可以从另一个角度导出来,所以,让我们不妨先跑一下题。

在 Image Processing (我好像之前有听说我对这个领域深恶痛绝?)里有一个问题就是对图像进行 Segmentation (区域分割),也就是让相似的像素组成一个区域,比如,我们一般希望一张照片里面的人(前景)和背景被分割到不同的区域中。在 Image Processing 领域里已经有许多自动或半自动的算法来解决这个问题,并且有不少方法和 Clustering 有密切联系。比如我们在谈 Vector Quantization 的时候就曾经用 K-means 来把颜色相似的像素聚类到一起,不过那还不是真正的 Segmentation ,因为如果仅仅是考虑颜色相似的话,图片上位置离得很远的像素也有可能被聚到同一类中,我们通常并不会把这样一些“游离”的像素构成的东西称为一个“区域”,但这个问题其实也很好解决:只要在聚类用的 feature 中加入位置信息(例如,原来是使用 R、G、B 三个值来表示一个像素,现在加入 x、y 两个新的值)即可。

另一方面,还有一个经常被研究的问题就是 Graph Cut ,简单地说就是把一个 Graph 的一些边切断,让他被打散成一些独立联通的 sub-Graph ,而这些被切断的边的权值的总和就被称为 Cut 值。如果用一张图片中的所有像素来组成一个 Graph ,并把(比如,颜色和位置上)相似的节点连接起来,边上的权值表示相似程度,那么把图片分割为几个区域的问题实际上等价于把 Graph 分割为几个 sub-Graph 的问题,并且我们可以要求分割所得的 Cut 值最小,亦即:那些被切断的边的权值之和最小,直观上我们可以知道,权重比较大的边没有被切断,表示比较相似的点被保留在了同一个 sub-Graph 中,而彼此之间联系不大的点则被分割开来。我们可以认为这样一种分割方式是比较好的。

实际上,抛开图像分割的问题不谈,在 Graph Cut 相关的一系列问题中,Minimum cut (最小割)本身就是一个被广泛研究的问题,并且有成熟的算法来求解。只是单纯的最小割在这里通常并不是特别适用,很多时候只是简单地把和其他像素联系最弱的那一个像素给分割出去了,相反,我们通常更希望分割出来的区域(的大小)要相对均匀一些,而不是一些很大的区块和一些几乎是孤立的点。为此,又有许多替代的算法提出来,如 Ratio Cut 、Normalized Cut 等。

不过,在继续讨论之前,我们还是先来定义一下符号,因为仅凭文字还是很难表述清楚。将 Graph 表示为邻接矩阵的形式,记为 W,其中 w_{ij} 是节点 i 到节点 j 的权值,如果两个节点不是相连的,权值为零。设 AB 为 Graph 的两个子集(没有交集),那么两者之间的 cut 可以正式定义为:

\displaystyle
\text{cut}(A, B) = \sum_{i\in A, j\in B} w_{ij}

先考虑最简单的情况,如果把一个 Graph 分割为两个部分的话,那么 Minimum cut 就是要最小化 \text{cut}(A, \bar{A}) (其中 \bar{A} 表示 A 的补集)。但是由于这样经常会出现孤立节点被分割出来的情况,因此又出现了 RatioCut :

\displaystyle
\text{RatioCut}(A, B) = \frac{\text{cut}(A, \bar{A})}{|A|} + \frac{\text{cut}(A, \bar{A})}{|\bar{A}|}

以及 NormalizedCut :

\displaystyle
\text{NCut}(A, B) = \frac{\text{cut}(A, \bar{A})}{\text{vol}(A)} + \frac{\text{cut}(A, \bar{A})}{\text{vol}(\bar{A})}

其中 |A| 表示 A 中的节点数目,而 \text{vol}(A) = \sum_{i\in A}w_{ij} 。两者都可以算作 A 的“大小”的一种度量,通过在分母上放置这样的项,就可以有效地防止孤立点的情况出现,达到相对平均一些的分割。事实上,Jianbo Shi 的这篇 PAMI paper:Normalized Cuts and Image Segmentation 正是把 NormalizedCut 用在图像分割上了。

搬出 RatioCut 和 NormalizedCut 是因为它们和这里的 Spectral Clustering 实际上有非常紧密的联系。看看 RatioCut ,式子虽然简单,但是要最小化它却是一个 NP 难问题,不方便求解,为了找到解决办法,让我们先来做做变形。

V 表示 Graph 的所有节点的集合,首先定义一个 N 维向量 f

\displaystyle 
f_i = \left\{\begin{array}{ll}\sqrt{|\bar{A}|/|A|} &
\text{if } v_i \in A \\
-\sqrt{|A|/|\bar{A}|} & \text{if } v_i \in \bar{A}
\end{array}\right. 

再回忆一下我们最开始定义的矩阵 L=D-W ,其实它有一个名字,叫做 Graph Laplacian ,不过,我们后面可以看到,其实有好几个类似的矩阵都叫做这个名字:

Usually, every author just calls “his” matrix the graph Laplacian.

其实也可以理解,就好象现在所有的厂家都说自己的技术是“云计算”一样。这个 L 有一个性质就是:

\displaystyle 
f'Lf = \frac{1}{2}\sum_{i,j=1}^N w_{ij}(f_i-f_j)^2

这个是对任意向量 f 都成立的,很好证明,只要按照定义展开就可以得到了。把我们刚才定义的那个 f 带进去,就可以得到

\displaystyle 
\begin{aligned} f'Lf &= \frac{1}{2}\sum_{i,j=1}^N
w_{ij}(f_i-f_j)^2 \\
&= \frac{1}{2}\sum_{i\in A, j\in\bar{A}}
w_{ij}\left(\sqrt{\frac{|\bar{A}|}{|A|}}+\sqrt{\frac{|A|}{|\bar{A}|}}\right)^2
+ \sum_{i\in \bar{A}, j\in A}
w_{ij}\left(-\sqrt{\frac{|\bar{A}|}{|A|}}-\sqrt{\frac{|A|}{|\bar{A}|}}\right)^2
\\
&=
\text{cut}(A,\bar{A})\left(\frac{|\bar{A}|}{|A|}+\frac{|A|}{|\bar{A}|}+2\right)
\\
&=\text{cut}(A,\bar{A})\left(\frac{|A|+|\bar{A}|}{|A|} +
\frac{|A|+|\bar{A}|}{|\bar{A}|}\right)\\
&=|V|\cdot\text{RatioCut}(A,\bar{A})
\end{aligned}

另外,如果令 \mathbf{1} 为各个元素全为 1 的向量的话,直接展开可以很容易得到 f'\mathbf{1} = \sum f_i = 0\|f\|^2 = \sum f_i^2 = n 。由于 |V| 是一个常量,因此最小化 RatioCut 就等价于最小化 f'Lf ,当然,要记得加上附加条件 f \bot \mathbf{1} 以及 \|f\| = \sqrt{n}

问题转化到这个样子就好求了,因为有一个叫做 Rayleigh quotient 的东西:

\displaystyle 
R(A, x) = \frac{x'Ax}{x'x}

他的最大值和最小值分别等于矩阵 A 的最大的那个特征值和最小的那个特征值,并且极值在 x 等于对应的特征向量时取到。由于 f'f = \sqrt{n} 是常数,因此最小化 f'Lf 实际上也就等价于最小化 R(L, f) ,不过由于 L 的最小的特征值为零,并且对应的特征向量正好为 \mathbf{1} (我们这里仅考虑 Graph 是联通的情况),不满足 f \bot \mathbf{1} 的条件,因此我们取第二个小的特征值,以及对应的特征向量 v

到这一步,我们看起来好像是很容易地解决了前面那个 NP 难问题,实际上是我们耍了一个把戏:之前的问题之所以 NP 难是因为向量 f 的元素只能取两个值 \sqrt{|\bar{A}|/|A|}-\sqrt{|A|/|\bar{A}|} 中的一个,是一个离散的问题,而我们求的的特征向量 v 其中的元素可以是任意实数,就是说我们将原来的问题限制放宽了。那如何得到原来的解呢?一个最简单的办法就是看 v 的每个元素是大于零还是小于零,将他们分别对应到离散情况的 \sqrt{|\bar{A}|/|A|}-\sqrt{|A|/|\bar{A}|} ,不过我们也可以采取稍微复杂一点的办法,用 k=2 的 K-means 来将 v 的元素聚为两类。

到此为止,已经有 Spectral Clustering 的影子了:求特征值,再对特征向量进行 K-means 聚类。实际上,从两类的问题推广到 k 类的问题(数学推导我就不再详细写了),我们就得到了和之前的 Spectral Clustering 一模一样的步骤:求特征值并取前 k 个最小的,将对应的特征向量排列起来,再按行进行 K-means 聚类。分毫不差!

用类似的办法,NormalizedCut 也可以等价到 Spectral Clustering 不过这次我就不再讲那么多了,感兴趣的话(还包括其他一些形式的 Graph Laplacian 以及 Spectral Clustering 和 Random walk 的关系),可以去看这篇 Tutorial :A Tutorial on Spectral Clustering

为了缓和一下气氛,我决定贴一下 Spectral Clustering 的一个简单的 Matlab 实现:

function idx = spectral_clustering(W, k)
    D = diag(sum(W));
    L = D-W;
 
    opt = struct('issym', true, 'isreal', true);
    [V dummy] = eigs(L, D, k, 'SM', opt);
 
    idx = kmeans(V, k);
end

最后,我们再来看一下本文一开始说的 Spectral Clustering 的几个优点:

  • 只需要数据的相似度矩阵就可以了。这个是显然的,因为 Spectral Clustering 所需要的所有信息都包含在 W 中。不过一般 W 并不总是等于最初的相似度矩阵——回忆一下,W 是我们构造出来的 Graph 的邻接矩阵表示,通常我们在构造 Graph 的时候为了方便进行聚类,更加强到“局部”的连通性,亦即主要考虑把相似的点连接在一起,比如,我们设置一个阈值,如果两个点的相似度小于这个阈值,就把他们看作是不连接的。另一种构造 Graph 的方法是将 n 个与节点最相似的点与其连接起来。
  • 抓住了主要矛盾,忽略了次要的东西,Performance 比传统的 K-means 要好。实际上 Spectral Clustering 是在用特征向量的元素来表示原来的数据,并在这种“更好的表示形式”上进行 K-means 。实际上这种“更好的表示形式”是用 Laplacian Eigenmap 进行降维的后的结果,如果有机会,下次谈 Dimensionality Reduction 的时候会详细讲到。而降维的目的正是“抓住主要矛盾,忽略次要的东西”。
  • 计算复杂度比 K-means 要小。这个在高维数据上表现尤为明显。例如文本数据,通常排列起来是维度非常高(比如,几千或者几万)的稀疏矩阵,对稀疏矩阵求特征值和特征向量有很高效的办法,得到的结果是一些 k 维的向量(通常 k 不会很大),在这些低维的数据上做 K-means 运算量非常小。但是对于原始数据直接做 K-means 的话,虽然最初的数据是稀疏矩阵,但是 K-means 中有一个求 Centroid 的运算,就是求一个平均值:许多稀疏的向量的平均值求出来并不一定还是稀疏向量,事实上,在文本数据里,很多情况下求出来的 Centroid 向量是非常稠密,这时再计算向量之间的距离的时候,运算量就变得非常大,直接导致普通的 K-means 巨慢无比,而 Spectral Clustering 等工序更多的算法则迅速得多的结果。

说了这么多,好像有些乱,不过也只能到此打住了。最后再多嘴一句,Spectral Clustering 名字来源于 Spectral theory ,也就是用特征分解来分析问题的理论了。

UPDATE 2011.11.23: 有不少同学问我关于代码的问题,这里更新两点主要的问题:

  1. 关于 LE 降维的维度和 Kmeans 聚类的类别数的关系:我上面的代码里,取成了一样的,但是这两者并不是要求一定要一样的。最初 Spectral Cluster 是分析聚两类的情况,就降到 1 维,然后用 thresholding 的方法来分成两类。对于K 类的情况,自然的类比就是降到 K-1 维,这也是和 LDA 保持一致。因为 Laplacian 矩阵的特征向量有一个全一的向量(对应于特征值 0 ),所以可以求 K 个特征向量然后把特征值 0 对应的那个特征向量去掉。但是在实际中并不一定要保持这两者一致的,也就是说,这个降维的维度可以作为一个参数进行调节的,选择效果好的参数。
  2. 关于示例代码:注意除非我在这里注明了是发布某个 software 或者 package 什么的,否则这里贴的代码主要都是为了示例作用,为了只显示出算法的主要部分,因此通常会省略掉一些实现细节,可以看成是“可执行的伪代码”,不推荐直接用这里的代码去跑实验之类的(包括其他 post 里的相关代码)。除非你想自己试验一下具体实现和改进,否则可以直接找网上现成的专用的 package ,比如 Spectral Clustering 可以考虑这个包

160 comments to 漫谈 Clustering (4): Spectral Clustering

  • sth4nth

    kmeans都能比sc慢,那这kmeans实现的也太烂了

  • @sth4nth
    呵呵,看来你没有仔细看我说的原因吧?不知道你说这话是有什么理论依据还是自己做过实验比较的呢?

  • sth4nth

    实验就不用说了,写过code的都知道,从理论上kmeans就不可能比sc慢。
    最简单的,对于kmeans我们也可以首先计算出所有pair wise inner product,然后用kernel kmeans进行迭代,这肯定比计算kernel矩阵的特征向量快多了。这相当是naive kmeans的dual。而在原空间上kmeans跟本不需要计算所有pairwise distance。更不用提kmeans还可以通过三角不等式还有基于spatial indexing的方法来加速了

  • @sth4nth
    恩,多谢你给的信息。确实你说的方法我都没有去了解过。看来在文章里面下的结论确实有些武断了。

  • yao

    您好,
    有两点疑问想向您请教
    1:spectral clustering的话,我用matlab实现过,测试的相似矩阵是400*400的(400张图片的相似度),但是matlab运行时间很不稳定,刚才测试的结果是104秒左右,但是第2次就跑了半个小时。

    2:我换了小点的数据12*12的,这会速度还可以接受,但是结果非常不稳定(12个图片的相似矩阵是没问题的),有时结果出错1个(这个是最好的结果),有时会多达5个。
    我明白 这个是因为随机性。但是如果这样的话,这么不稳定,我们如何检测聚类结果呢?
    再跟别的方法,比如分层聚类比较的时候,假如 偶尔一次结果比分层好 偶尔一次比分层差,这个问题如何解决呢?

    写了很长,可能是废话,本人刚刚硕士一年,接触数据挖掘的时间不长,如果说问了白痴的问题,也请您花点时间为我解释下好吗?

  • @yao
    你好!谱聚类的效果还不错吧,虽然有随机性,但是总体效果还挺好的,不过 12×12 的数据这么少,做出来稳定性不好也是自然的吧。400×400 感觉数据量也不大的,运行时间一个是解特征值,一个是做 k-means ,你可以看看瓶颈在哪里,运行时间和你的矩阵的稀疏程度有关的。不过话说回来,做这方面的东西,除非是要花心思优化算法的实现,否者一般的实验跑几个小时是很正常的事吧。 :)

  • yao

    谢谢回复
    如果可以的话,加你MSN 聊可以吗?

    总体看效果是不错,但是能否在统计学基础上,判断spectral和kmeans还有分层的结果谁更好,有没有什么方法呢?
    请问你比对过 矩阵不做稀疏处理,还有矩阵做了稀疏处理,表现如何吗?
    现在运行时间不是问题了 400*400的 2秒左右(当然是经过稀疏处理,取最近邻居那种)。
    只是 每次的结果不稳定,想证明那个方法更好,找不到路而已,因为spectral也有表现非常差的时候。

    您说的 “12×12 的数据这么少,做出来稳定性不好也是自然的吧。400×400 感觉数据量也不大的”我非常感兴趣,能具体解释下马? 基于什么原理使得矩阵越大结果越稳定呢?非常急切的期待您的回答。
    我的msn yaojiannan1985@hotmail.com 我做图像聚类的,能交个朋友吗?

  • @yao
    你好,我的 MSN 在 About 页面里应该有,不过我不怎么上的,而且最近几天也比较忙。

    其实这些东西我也是正在学,不过我可以就我自己了解的给你大致解释一下。K-means 和 Spectral Clustering 我想并没有能保证哪一个一定在所有的时候都比另一个要强,总的来说,Spectral Clustering 通常比 K-means 要好的,况且 K-means 本身也是有一定的随机性的,同样的参数前一次跑出来的结果和后一次跑出来的结果可能都不一样。但是 Spectral Clustering 既然是用 Laplacian Eigenmap 来做降维,那么它首先基于了 Laplacian Eigenmap 的一个假设,就是数据本身是分布在一个低维流形上的,如果数据本身不符合这个假设或者甚至完全抵触的话,那就不能那个保证一定能得到满意的结果了。

    对于数据量的问题,像这里讨论的机器学习算法,实际上可以算作是基于统计的模型的,就好比说一个人的行为是不可预测的,但是一个群体的行为却是可以预测的,既然要想从数据里学习到合适的模型,那数据太少的话总是会出现偏差的,这就会导致不稳定了,就是说,结果要碰运气了。

  • cerror

    @sth4nth
    你用LDA试试看……kmeans有很多优化,sc也有很多优化。

  • @cerror
    没有看过 LDA ,确实听说两者都有好多优化,不过好像在跑实验的时候都是直接用的最原始的解法。 :/

  • heshizhu

    收藏了,慢慢吸收!我转载到我QQ空间里不算侵权吧?

  • @heshizhu
    CC 协议的,不用于商业目的的话,注明出处就好了。 :)

  • heshizhu

    您好,我想请教个问题:如果只知道任意两个对象的距离(而不知道其他的对象标示),可以用那些聚类算法,不可以用那些聚类算法,最好用哪个聚类算法呢?K-Mean算法肯定不能用吧!

  • @heshizhu
    你好,像谱聚类这样的算法就可以满足你的条件,主要是看聚类算法所需要的输入参数的结构就可以了。通常用谱聚类就可以了,不过也还是要看具体的应用场景的。

  • heshizhu

    哦,非常感谢!

  • ning

    前段时间看Normalized Cut时,思想基本还能看懂,但是理论部分太抽象了,看了你的解释之后,基本上有点明白了,非常感谢!

  • Chrysalis

    作为最后k-means clustering的对象,为什么解出来的Eigenvectors要以Eigenvalue的大小来排列。有什么依据来着??

  • @Chrysalis
    因为目标函数的值就等于特征值的和,所以取特征值最小的那些对应的特征向量。

  • Chrysalis

    @pluskid
    答得不是我问的,我问的是选好特征向量之后,为什么要按照特征值大小来排列进而做最后的clustering。现在想应该是没有这个规定,因为最后做clustering是K-means 如果是用欧式距离的话 选定的那些特征向量如何排列都不会对距离产生影响。
    当然在如何选特征向量上,是因该按照特征值大小来选取的,我理解的对不对??

  • Chrysalis

    spectral clustering最tricky的地方,就是选择了适当的vector “f”和对f的relaxation, 从而使得”对graph partition的objective function求极值问题”转化到了”关于Rayleigh Quotient求极值”的问题。

  • Chrysalis

    文中的Rayleigh Quotient拼写有错误..

  • @Chrysalis
    因为选的时候已经排好序了,没有必要再把他打乱一下…… -.-///

    好的,fixed typo……而且发现我一直都读错了,原来源自这里啊

  • dreaminyale

    你好,请问能说下在对高维文本数据的处理中,你所提到的高效的对稀疏矩阵求特征值和特征向量的方法具体有哪些么?谢谢

  • @dreaminyale
    你好,我说的是 matlab 具有处理这样情况的能力,至于具体是什么算法,请去查阅数值计算相关的内容 (比如 Power Method 之类的)。

  • dreaminyale

    你好,请问你能说下Graph Cut和Spectral Clustering到底是什么关系么?谢谢!

  • @dreaminyale
    你好,我的理解是 Graph Cut 和 Spectral Clustering 在数学推导上是一样的,也就是说在本质上是一样的,应该可以看作同样的数学模型在不同领域的应用或者说是从不同的理解角度来看待同一个问题。

  • C6H5NO2

    我的理解,Spectral Clustering跟clustering并没有多少关系,重点还是Laplacian Eigenmap的降维。
    降维的作用是把(高维)欧式空间的距离转换为流形上的距离。如果数据确实分布在某个低维流形上,那么这样做对于kmeans这类基于基于距离的算法是有意义的。
    降维方法,或者说流形学习的方法,似乎目前并不完善。比方说,需要把数据降到多少维,很多时候都会难以把握。更夸张的是,JLMR上有一篇文章 “Manifold Learning: The Price of Normalization”,专门讲Laplacian Eigenmap, LLE, Hessian LLE, Diffusion Map等基于”spectral”的方法是如何的不靠谱。

    • Binbin

      同意前半部分观点。如果数据是欧氏的,那么K-means应该是最优的。(不知道有没这样的结论)但问题往往是数据不是欧氏,所以大家的做法是利用数据本身的结构把数据映射到欧氏空间中,再做K-means。

      “Manifold Learning: The Price of Normalization”是从isometry的角度来看降维的,而spectral methods更多的考虑是映射的光滑性,因此它的观点是spectral methods往往都不是isometry。

      • C6H5NO2

        可是聚类本身就是基于metric的……
        如果高维到低维不能isometry,那降维后的聚类就没有太大意义吧

        • Binbin

          降维和聚类各有各的准则,而且这些准则往往是不一样的。比如单纯降维考虑的是isometry。聚类的话有很多准则,比如spectral clustering考虑的是smoothness(or locality), diffusion map考虑的是preserve diffusion distance。虽然说聚类本身是基于metric,但是这个metric不是standard的,需要去定义。

  • @C6H5NO2
    恩,我也有这样的感觉,谢谢你提供的这个信息,我去看一看这篇文章,似乎很有趣的样子。 :)

  • 恭王府

    感谢,请LZ继续加油~!

  • mengqiuwang

    我看了一些关于sc的论文吧,但是没找到一篇确实提出可行的image segmentation的方法,我想找一篇是确切地提出怎么算识别率的方法,请楼主帮帮忙吧,解决一下这个问题。

  • mengqiuwang

    我的mail是 mengqiuwang7@gmail.com,希望知道sc的image segmentation的识别率计算方法的高手跟我联系哈,主要就是你聚出了那几类,但是如何确定那就是你要多那一类呢,又没有中心点。

  • @mengqiuwang
    你好,不是太明白你的问题,image segmentation 的识别率是什么意思?中心点又是什么?

  • mengqiuwang

    可能我没有表述清楚吧,我的意思是说,假如有很多幅图片吧,每幅图片里面有河流、花草、山川,那么你对这幅图片进行了sc,最后形成了五类吧,你如何确定这五类里面哪一类是河流,哪一类是山川,哪一类又是花草呢?

    • Wico

      Laplace Eigenmap的降维结果是一一对应的,可以聚了类找回点的原像,然后用原像的总体特征分类,比如总体色值,山偏绿,海偏蓝,或者其他一些如纹理。至于什么特征是山,什么特征是海,cluster是不可能知道的,因为根本没概念,只能有事先的参数或样本决定

  • @mengqiuwang
    这个是没有办法做的吧,除非你有事先标记好的训练数据用于训练分类模型的话,但是这个属于分类的问题了,和 clustering 或者 segmentation 应该相对独立的,可以看作后续的处理过程。

    这个大概要参考 Image Classification 方面的论文了,这个我也没有做过,估计可能要提取 SIFT 特征然后做 visual vocabulary 之类的方法来做,总之都是要有训练数据才行的。

  • syx

    你好,我关注你的日志好久了,请问你有谱聚类算法的matlab实现代码吗?我正在做这个毕业设计,我做的是改进NJW的算法,希望你可以发给我谱聚类的matlab源代码好吗?呵呵非常感谢你,我是真的愁的不知道怎么办好了。
    邮箱:sunyxrizhao@yahoo.com.cn

  • @syx
    你好,我这里没有现成的可以直接用 code ,不过你 Google spectral clustering matlab 能找到很多啦。

  • gaohaidong

    我是过来ym pluskid的,跟着何晓飞在做吗?博士还是硕士?

  • gaohaidong

    硕士也搞得这么理论。。。是明年上毕也吗?

  • @gaohaidong
    我不是很清楚哪年,反正现在研一嘛…… =.=

  • GSM

    不知楼主是否看过Jb Shi 和Malik 写的大名鼎鼎的Normailized Cut 算法的源代码,我看后感觉代码和论文有些地方有出入,代码反映出来的算法是基于边缘的图像分割算法,跟区域关系不太大。不知楼主认同这个观点不?

  • feina1

    同学你好,仔细拜读了你的clustering系列,让我也萌生了写些自己总结的想法。

    想问的是,spectral clustering中,最后的一步是k means吧,但此时每个数据点的维度是否只是1呢(即就是在第二小的特征向量上作聚类)? 总觉得到这里有些怪怪的。

    谢谢指教!

    • 你好,维度不一定是 1 的,比如可以取 k 个最小特征值对应的特征向量来聚类,这样维度是 k 。

    • dongchen

      如果是分两类(k=2),并且是用Laplacian求second smallest eigenvalue,那么其实降低后的维度就是1,推广到k类维度就是k-1。这是因为Laplacian的smallest eigenvector是值全为1的向量。

  • wwt

    同学你好 请问下 我在有些资料上看的是前k个最大特征值对应的特征向量
    再用kmeans聚类
    或者是只取第2小的特征值对应的特征向量
    是什么原因啊?难道是解的方程不同么?

  • […] 漫谈 Clustering (4): Spectral Clustering by pluskid, on 2009-02-25, in Machine Learning 47 comments […]

  • zhanxw

    有个笔误:
    其中 \\bar{A} 表示 A 的子集
    不是 子集 应该是 补集

  • edtuer

    请问关于谱聚类的阶次选取有何切实可行的办法
    毕竟实际问题很难判断降到几维比较合适
    请能谈谈吗?谢谢

    • 随便说说:还是应该从问题出发,分析一下数据是什么样的结构。
      要不就用cross validation选取合适的参数(比如到底是几维)

    • 这个问题很困难啊,我是不知道有什么在实际中能有什么特别灵的办法。通常实际问题有它特定的结构可以分析。有时候通常会采用的一个启发式的办法就是把维度设成聚类类别数或者类别数减一。不过就聚类来说,选取合适的类别数本身就是很困难的问题啦!

  • edtuer

    我运行了博主的matlab程序,频繁的在特征值分解处出warning

    opt = struct(‘issym’, true, ‘isreal’, true);
    [eV eD] = eigs(L, D, k, ‘SM’, opt);

    Warning: Matrix is close to singular or badly scaled.
    Results may be inaccurate. RCOND = 9.628061e-017.

    一些背景:我的similarity矩阵比较稀疏。

    请问,一,这会不会影响结果的准确性?是否有办法消除warnings?
    二,有没有其他的spectral clustering程序可供参考?

    多谢多谢

    • 你好,网上应该有很多其他 spectral clustering 的程序的,我这个为了示例作用,写得比较简单,不推荐直接拿去实际中使用。不过对于你说的那个 warning ,是数据的问题,也和你的 similarity 矩阵构造有关系,如果确定前面的步骤都是合理的话,仅在求特征值一步,去除那个 warning 可以参考我最近的一篇 blog 文章:求最小的几个特征值

  • Ian

    我以前专门讨论过谱聚类和Kmeans聚类,后来发现其实这两个算法是一回事,只不过k取不同的值而已。具体分析在这里:Image Clustering using Local Discriminant Models and Global Integration

  • Ian

    我让同学画的。任何一个拉普拉斯矩阵都对应一个图,这个图的权可以认为是similarity,比如在appendix里我就写出了那个图的边的权,虽然不是很严谨。更严谨的也可以写出来,但是太麻烦了,我就没放上去

Leave a Reply

 

 

 

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>