文档介绍：聚类算法实践（3）——PCCA、SOM、Affinity Propagation
男人海洋 发表于 2013-08-25 19:46 来源：数据之城
      这篇日志是这个系列里算法部分的最后一篇，关注的是几个相对另类一点的聚类算法都可以看做一个转移矩阵，都会对应着一个稳态。比如对于上面的矩阵A，下面两个本征矢的本征值都为1。
      
      如果我们得到的矢量都是这样的理想形式，那么聚类就很简单了，只要得到本征值为1的全部本征矢，把对应的元素大于0的数据点归为一类就可以。十分可惜的是，由于这两个本征矢量是简并的，它们线性叠加产生的矢量也是矩阵的本征值为1的本征矢量，比如这个矢量：
      因此PCCA算法的思路，就是要从计算得到实际本征矢量，反推得到理想矢量，从而实现聚类。
       如果将计算得到的k个本征值为1的本征列矢量并排合并，成为一个N*k的矩阵，那么矩阵的每一行可以看成对应与数据点的一个坐标。对于理想本征矢（对应下图蓝色基矢），数据点都是落在坐标轴上（因为除了所属的cluster所对应的那个本征值，其余的维度都是0），比如下图的红色和黄色的数据点。但是由于实际得到的本征矢量是理想本征矢的线性叠加，所以基矢就发生了旋转（对应黑色基矢）。
      尽管如此，每个cluster的数据点落在一条直线上的性质并没有发生改变。现在的问题就变成了如何找到这些直线的方向。PCCA首先找到离原点最远的数据点，这个点相对于原点的矢量，就对应了一个理想本征矢。然后每一次都找与已知的理想矢量垂直（相对原点），而又离原点最远的数据点。只要找k次，就能找到所有的理想矢量。最后看数据点落在哪个方向上，就可以知道它们属于哪个cluster。实际情况下，矩阵并不会是完全的分块矩阵，所以除了第一个本征矢，其余本征矢量对应的本征值不会完全为1，而是接近于1。cluster之间的转移几率越小，这个算法的准确性自然越高。
聚类结果
       PCCA算法的一个优点就是，它可以根据本征值来直接得到cluster的数目，有多少个接近于1的本征值就应该分多少个cluster。当然这也是一个限制，聚类数目不能随意给定，完全由数据性质决定，如果cluster的分界不明显，那么可能聚类就完全无效。
       下面是PCCA对样品1的聚类结果。第一幅图是由算法自动判定聚类数目，正好为3，聚类十分成功；第二幅图是人为地要求分为4个cluster，结果算法就基本失效了。
       PCCA是除了Chameleon算法外，对样品2聚类结果最好的一个算法。不过它并不能正确地判断出cluster的数目，总共划分出了7个cluster，这里显示了前5个。
       PCCA可以自动判定cluster数目，而且也能得到非凸型的cluster，还可以适用于概率转移矩阵的聚类，看上去确实是一个性能比较好的聚类算法。不过，PCCA对数据的性质特征有比较强的预设，当数据性质偏离理想状况较远时，算法的稳定性有待考验。
7、SOM
      之所以尝试SOM聚类，主要是因为这是基于神经网络的一种算法，而神经网络本身又是机器学习中的一个重要方法，所以就自己实践一下体会体会。
       所谓SOM指的是Kohonen提出的竞