目录

一.引言

二.PIC 理论

1.谱聚类

2.快速迭代聚类

三.PIC 实战

1.数据准备

2.构建 PIC

3.预测与展示

四.总结

一.引言

前面介绍了 K-means 聚类与高斯混合聚类，本文介绍另外一种聚类方法 Power Iteration Cluster 快速迭代聚类，简称 PIC。快速迭代聚类是谱聚类的一种，是由 Lin 和 Cohen 开发的可拓展图聚类算法。

二.PIC 理论

1.谱聚类

谱聚类是最近聚类研究的一个热点问题，是建立在图论理论上的一种新的聚类算法。谱聚类基于谱图原理，根据数据集的相似度矩阵进行聚类，它具有更强的数据分布适应性。

A.计算相似度矩阵

前面我们讲到过 GraphEmbedding -GraphEmbedding 之获取图结构，里面有带权图的概念。谱聚类思想为将带权无向图划分为两个或两个以上的最优子图，要求子图内尽量相似而不同子图间距离尽量较远，以达到每个子图构成一个聚类 cluster 的目的。在无向图中，对于点1和点2，我们可以定义两点之间的距离 dst 为 w，从而构建相似度矩阵：

其中 D 为度矩阵，W为相似度矩阵。后续涉及到特征值与特征向量的计算，通过对特征向量使用类似 K-means 的算法衡量相似度并按照 K 进行聚类。

2.快速迭代聚类

关于 PIC 完整的推理与论文描述大家可以参考：Power Iteration Clustering。下面对算法做简单分解：

A.Input

输入一个按行归一化的关联矩阵 W 和期望的聚类 Cluster 数目，并随机选取一个初始化向量 v0。

B.Repeat

令

C.Until

不断增加 t，直到：

K-Means、GMM 高斯混合聚类两种聚类算法，几种算法各有优势：

K-Means 简单高效，适用于线性可分的数据以及快速聚类，可以获得聚类中心并重复使用。

GMM 高斯混合聚类其实本质上是数据分布拟合，相比 K-Means 其可以获得多个 GM 高斯分布模型，并获得每个样本属于不同聚类的概率。

PIC 快速迭代聚类通过 Laplcae 矩阵分解获取特征值特征向量，更适合非凸模型数据的聚类，但不可复用。