文档介绍：聚类算法实践( 3) —— PCCA 、 SOM 、 Affinity Propagation 男人海洋发表于 2013-08-25 19:46 来源: 数据之城这篇日志是这个系列里算法部分的最后一篇, 关注的是几个相对***一点的聚类算法: PCCA 、 SOM 和 Affinity Propagation 。 PCCA 是设计来专门用于马尔科夫模型的一种聚类算法; SOM 是基于神经网络模型的自组织聚类;最后的 Affinity Propagation 则是在 07 年才在 Science 发表的一种较新颖的算法。 6、 PCCA PCCA 算法的全称是 Perron Cluster Cluster Analysis ,名称里有两个 cluster 是因为这样简写就可以和 PCA 区分开来( 无语……)。 PCCA 并不是设计来处理传统的聚类问题的, 而是专门用于得到马尔科夫链中的 cluster 。当然,对于一般的聚类问题,只要根据系统特点构造出一个概率转移矩阵,也可以使用 PCCA 算法。要解释马尔科夫模型中的 cluster ,让我们想象有一只跳蚤在了数据点间跳跃转移。它下一个时刻跳到特定数据点上的概率, 只跟它当前落在哪个数据点上有关, 这显然是一个经典的马尔可夫过程。再让我们假定, 跳蚤在点与点之间的跃迁概率跟数据点的“距离”成反比。如果数据点可以分成几个分界明显的 cluster ,跳蚤大多数时间就只会在某个 cluste r 内部的数据点间转移,在 cluster 之间的跳跃则相对罕见。先解释一下马尔科夫模型的一些性质。马尔科夫模型需要的是一个转移矩阵 A ,元素 A(i,j) 表示系统从状态 i 转移到状态 j 的概率。矩阵的每一列元素之和必须为 1 ,这是因为转移概率总和必须为 1。转移矩阵有一个本征值为 1 的本征矢量, 对应着系统的稳态, 亦即系统到达这个状态后,它在各个状态的概率分布就不会再发生变化。为了说明 PCCA 的原理,我们直接来考虑最为极端的情况,也就是系统由几个完全分离的 cluster 所构成。对于最为极端的情况,如果系统只能在 cluster 内部转移,而完全不会在 cluster 之间转移, 那么转移矩阵 A 就会是分块矩阵的形式, 比如下面的系统就可以分为两个完全不连通的 cluster ,如下面的矩阵。这样的一个矩阵存在着不止一个本征值为 1 的本征矢量, 因为它的每个分块都可以看做一个转移矩阵, 都会对应着一个稳态。比如对于上面的矩阵 A, 下面两个本征矢的本征值都为1。如果我们得到的矢量都是这样的理想形式, 那么聚类就很简单了, 只要得到本征值为 1 的全部本征矢,把对应的元素大于 0 的数据点归为一类就可以。十分可惜的是,由于这两个本征矢量是简并的,它们线性叠加产生的矢量也是矩阵的本征值为 1 的本征矢量,比如这个矢量: 因此 PCCA 算法的思路, 就是要从计算得到实际本征矢量, 反推得到理想矢量, 从而实现聚类。如果将计算得到的 k 个本征值为 1 的本征列矢量并排合并,成为一个 N*k 的矩阵,那么矩阵的每一行可以看成对应与数据点的一个坐标。对于理想本征矢( 对应下图蓝色基矢), 数据点都是落在坐标轴上( 因为除了所属的 cluster 所对应的那个本征值, 其余的维度都是 0), 比如下图