聚类算法实践（二）——谱聚类、Chameleon聚类

上一篇文章里说到的层次聚类和K-means聚类，可以说是聚类算法里面最基本的两种方法（wiki的cluster analysis页面都把它们排前两位）。这次要探讨的，则是两个相对“高级”一点的方法：谱聚类和chameleon聚类。

4、谱聚类

一般说到谱聚类，都是从降维(Dimensionality Reduction)或者是图分割(Graph Cut)的角度来理解。但是实际上，从物理学的简正模式的角度，可以更为直观地理解这个算法的本质。

这里先把基本的算法步骤写出来，然后再讨论算法的原理。

谱聚类基本步骤：

1、给出N个数据点两两之间的相似性。也就是一个N*N的相似性矩阵A，A(i,j)代表i和j两个数据点的相似度，数值越大则表示越相似。注意A(i,j)=A(j,i)，A(i,i)=0。

2、计算矩阵D，使它的对角元是A矩阵的对应的那一列（或行）的值之和，其余地方为0。也就是使得这里写图片描述

3、令B=D-A

4、求B矩阵的前k个本征值和本征矢，将数据点投影到一个k维空间。第i本征矢的第j个值，就表示第j个数据点在k维空间中第i维的投影。就是说如果把k个特征矢量并成一个N*k的矩阵，则每一行代表一个数据点在k维空间的坐标。

5、根据每个数据点的k维空间坐标，使用K-means或者其它聚类算法在k维空间对数据进行聚类。

从算法的第4、5步就可以看出，谱聚类的本质实际上就类似于PCA，先将数据点投影到一个更能反映数据特征的空间，然后再用其它办法进行聚类。这也就是一种降维的思想（实际上也可能是升维）。那么问题的关键就在于，它把数据点投影到什么空间去了？为什么这个空间更能反映数据特征？这个问题可以从图分割的角度来理解（看这里），不过我这里要从简谐振动的角度来讨论这个问题，这也是一个更为直观的理解。

简正模式

说起简谐振动，学过高中物理的童鞋都不会陌生：两个小球连上一根弹簧，就是最简单的简谐振动模型。为了简单起见，写成一维的形式，而且弹簧的平衡距离设为0，于是，当小球的坐标给定时，弹性势能就是

我们把上面那个算法套用在这个例子上试试，两个小球的“相似度”就看成是它们之间弹簧的弹性系数k，k越大，小球之间的关系自然就越紧密了。这样上面要求的矩阵就是

A = 0 k k 0

$A=\begin{matrix}0 & k\\k & 0\\\end{matrix}$

D = k 0 0 k

$D=\begin{matrix}k & 0\\0 & k\\\end{matrix}$

B = k - k - k k

$B=\begin{matrix}k & -k\\-k & k\\\end{matrix}$

给出整个系统的坐标矢量这里写图片描述，容易证明

B只有两个本征矢量，分别是
这里写图片描述

这两个本征向量就代表了体系的两个简正运动模式，向量中的值表示对应的小球在这个运动模式中的运动方向。比如p1之中两个小球往同一个方向运动，这其实是系统的整体平动，对应的本征值为0；p2则表示两个小球往相反方向运动，这就符合我们想象中这两个小球的简谐振动了。

究竟什么是简正运动模式？为什么用上面的方法就能得到系统的简正运动模式呢？其实所谓的简正模式，就类似于傅立叶分析里面，用来将原函数展开的那组相互正交的基函数组。这里所使用的，就是简谐振动这样的一种基组，将整个系统的复杂运动表示为这些简正模式的叠加。

无论我们有多少个小球，只要小球之间是以弹簧相连的，那么根据它们之间的连接方式，总是可以将系统的势能表示为这里写图片描述

但是，我们希望的是将运动方式dq去耦合，写成多个简正模式之和，也就是

所以需要对原来的B矩阵对角化，而对角化过程中得到的本征矢量和本征值，也就是所要求的简正模式以及它们的频率的平方值。

上面说了那么多关于简正模的东西，可是到底为什么要求简正模呢？这是因为谱聚类的目的是要找到一个能很好地反映数据点特征的空间，然后在新空间中进行聚类。试着想象一下，如果两个数据之间相似性很大，那么也就是说它们之间的“弹簧”弹性系数很大，就跟用一个棒子连起来一样，那么自然在运动的时候，它们就会倾向于往同一个方向运动。类似地，如果一堆数据点之间很相似，那么它们就会形成一个rigid的整体，就像一个刚体一样，刚体内部的小球喜欢一起动。而两个刚体之间，则会产生简谐运动，倾向于往不同的方向运动。

用一个简单的例子来说明这个现象，我们可以想象6个小球，分成对称的两组123和456，组内小球两两之间连在一起，两组之间则在3和4间有一根弹簧相连。这样一个结构，很明显应该是分为123和456两组。如果我们使用谱聚类，那么相似矩阵和求得的本征矢量如下

A = 011000101000110100001011000101000110

$A=\begin{matrix}0 & 1 & 1 & 0 & 0 & 0 \\1 & 0 & 1 & 0 & 0 & 0 \\1 & 1 & 0 & 1 & 0 & 0 \\0 & 0 & 1 & 0 & 1 & 1 \\0 & 0 & 0 & 1 & 0 & 1 \\0 & 0 & 0 & 1 & 1 & 0 \\\end{matrix}$
p1 = [-0.3536 -0.3536 -0.5000 -0.5000 -0.3536 -0.3536]
p2 = [-0.4440 -0.4440 -0.3251 0.3251 0.4440 0.4440]
p3 = [0.3536 0.3536 -0.5000 -0.5000 0.3536 0.3536]

这里只列出本征值最小的前3个本征矢量：第一个一样是整体平动，没有什么意义；第二个表示两组小球之间的相对运动，两组小球往不同方向运动，这是我们想要得到的结果；第三个表示每组小球内部的相对运动。

在这个结构里，组内部的相对运动相比起组间运动是很弱的，这可以从它们对应的本征值看出来。根据能均分定理，能量应该在每个简正模式之间均分，所以模式的振幅反比于它们的频率，也就是跟本征值的开方的倒数成正比，这里A2:A3:A4~3:1:1。这其实也就告诉了我们，对传统的谱聚类算法可以根据它的物理意义进行改进，根据本征值对本征矢量进行加权，而不是同一对待。这样，不重要的模式即便被考虑进来，因为振幅很小，所以也不会对结果产生什么影响。这样，我们在算法的第4步，考虑k个本征矢量来进行投影时，就不用担心会多取了多余的本征矢了，而且也可以根据本征值谱的变化来判断k的合理取值，就像在层次聚类中那样。

对PCA比较熟悉的童鞋，会发现这个方法在形式上跟主元分析有类似的地方。其实简正模分析和PCA是两个相反的思路，简正模是根据系统的性质来推断系统的特征运动模式，而PCA则是根据系统的运动结果来得到特征方向。一个是从原理来进行推断，一个则是从结果来进行反推。

聚类结果

使用谱聚类对样品1进行聚类，可以得到下图。两个结果分别对应聚类数目k取为3和8的情况，可以看到并不会像K-means那样把大的cluster分离，只会把少量异常点分离出去，总体的聚类结果十分稳定。因为算法最后还是使用了K-means进行聚类，所以我们可以想象谱聚类在投影到新空间的时候，应该是很好地把不同的cluster远远地分离了开来。
这里写图片描述

可惜，谱聚类对特殊形状的cluster的聚类效果依然不尽如人意。不过相比起K-means这样的算法，谱聚类已经辨认出一些形状信息了（有成环状的cluster，而不是都是球型的）。
这里写图片描述

5、Chameleon聚类

之前介绍的三个算法都没办法分辨出样品2的甜甜圈，而这次介绍的chameleon算法则可以说是专门用来干这活的。下面是算法的提出者在他们的文献中给出的一些测试组，可以看到这个算法就是对各类奇葩形状都应对自如……
这里写图片描述

我们不妨来想当然地考虑一下，怎样才能识别出甜甜圈结构的cluster。简单起见，考虑最极端的情况，假设数据的噪声不是像样品2那么大，而是分界很明显的三个环带。想象我们把一只甲虫放在了其中一个环带上，甲虫的视野很小，而且它会随机地走到它能看到的数据点上。如果环带之间的间距足够大，那么甲虫就不会走到其它环带上。最后，甲虫能走到的区域就是一个环形的cluster。

上面这个问题的关键就在于，要主动地把甲虫的视野变小，也就是根据近邻数据来进行聚类，然后不断延伸。这其实也就类似于层次聚类中的single-linkage，实际上single-linkage也确实可以识别出样品2。

但是这样会带来新的问题，比如对于下面的情况。在fig 4中，如果只看最近邻的连接，算法会倾向于合并c、d而不是a、b，又或者说，如果甲虫的视野足够大到会合并a和b，那么c和d也就一定会被看作一个cluster。但事实上，a、b的邻接区域较大，距离也不远（相对于a、b内部），所以是应该被认为是属于同一个cluster，而c、d则显然不应该被看作一类。fig 5则表示另外一种情况，就是过分强调邻接区域的大小，这样就会倾向于把a与c进行合并，而不是与b合并。

这里写图片描述

Chameleon算法就是努力在这两种情况之间保持平衡，既考虑Closeness，即近邻节点的靠近程度，也考虑Inter-Connectivity，即邻接区域的大小。

Chameleon本质上也是一个从下而上的层次聚类算法，不过它只考虑每个节点邻近的K个节点（K由用户给定），也就是说，只有最接近节点的其它K个节点会被认为与节点存在连接。两个节点越“接近”，连接强度越强。两个cluster的“距离”由两个参量决定：relative inter-connectivity和relative closeness。

Relative Inter-Connectivity

这里写图片描述