聚类算法实践2.docxVIP

聚类算法实践（2）——谱聚类、Chameleon聚类/member/index.php?uid=wyxlls男人海洋?发表于 2013-08-30 14:34 来源：数据之城 上一篇文章里说到的层次聚类和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-A4、求B矩阵的前k个本征值和本征矢，将数据点投影到一个k维空间。第i本征矢的第j个值，就表示第j个数据点在k维空间中第i维的投影。就是说如果把k个特征矢量并成一个N*k的矩阵，则每一行代表一个数据点在k维空间的坐标。5、根据每个数据点的k维空间坐标，使用K-means或者其它聚类算法在k维空间对数据进行聚类。?从算法的第4、5步就可以看出，谱聚类的本质实际上就类似于PCA，先将数据点投影到一个更能反映数据特征的空间，然后再用其它办法进行聚类。这也就是一种降维的思想（实际上也可能是升维）。那么问题的关键就在于，它把数据点投影到什么空间去了？为什么这个空间更能反映数据特征？这个问题可以从图分割的角度来理解（看这里），不过我这里要从简谐振动的角度来讨论这个问题，这也是一个更为直观的理解。简正模式?说起简谐振动，学过高中物理的童鞋都不会陌生：两个小球连上一根弹簧，就是最简单的简谐振动模型。为了简单起见，写成一维的形式，而且弹簧的平衡距离设为0，于是，当小球的坐标给定时，弹性势能就是?我们把上面那个算法套用在这个例子上试试，两个小球的“相似度”就看成是它们之间弹簧的弹性系数k，k越大，小球之间的关系自然就越紧密了。这样上面要求的矩阵就是???给出整个系统的坐标矢量，容易证明?B只有两个本征矢量，分别是??这两个本征向量就代表了体系的两个简正运动模式，向量中的值表示对应的小球在这个运动模式中的运动方向。比如p1之中两个小球往同一个方向运动，这其实是系统的整体平动，对应的本征值为0；p2则表示两个小球往相反方向运动，这就符合我们想象中这两个小球的简谐振动了。?究竟什么是简正运动模式？为什么用上面的方法就能得到系统的简正运动模式呢？其实所谓的简正模式，就类似于傅立叶分析里面，用来将原函数展开的那组相互正交的基函数组。这里所使用的，就是简谐振动这样的一种基组，将整个系统的复杂运动表示为这些简正模式的叠加。?无论我们有多少个小球，只要小球之间是以弹簧相连的，那么根据它们之间的连接方式，总是可以将系统的势能表示为?但是，我们希望的是将运动方式去耦合，写成多个简正模式之和，也就是所以需要对原来的B矩阵对角化，而对角化过程中得到的本征矢量和本征值，也就是所要求的简正模式以及它们的频率的平方值。?上面说了那么多关于简正模的东西，可是到底为什么要求简正模呢？这是因为谱聚类的目的是要找到一个能很好地反映数据点特征的空间，然后在新空间中进行聚类。试着想象一下，如果两个数据之间相似性很大，那么也就是说它们之间的“弹簧”弹性系数很大，就跟用一个棒子连起来一样，那么自然在运动的时候，它们就会倾向于往同一个方向运动。类似地，如果一堆数据点之间很相似，那么它们就会形成一个rigid的整体，就像一个刚体一样，刚体内部的小球喜欢一起动。而两个刚体之间，则会产生简谐运动，倾向于往不同的方向运动。?用一个简单的例子来说明这个现象，我们可以想象6个小球，分成对称的两组123和456，组内小球两两之间连在一起，两组之间则在3和4间有一根弹簧相连。这样一个结构，很明显应该是分为123和456两组。如果我们使用谱聚类，那么相似矩阵和求得的本征矢量如下????这里只列出本征值最小的前4个本征矢量：第一个一样是整体平动，没有什么意义；第二个表示两组小球之间的相对运动，两组小球往不同方向运动，这是我们想要得到的结果；第三、四个表示每组小球内部的相对运动。?在这个结构里，组内部的相对运动相比起组间运动是很弱的，这可以从它们对应的本征值看出来。根据能均分定理，能量应该在每个简正模式之间均分，所以模式的振幅反比于它们的频率，也就是跟本征值的