在Spark2.0版本中（不是基于RDD API的MLlib），共有四种聚类方法： 
            （1）K-means 
            （2）Latent Dirichlet allocation (LDA) 
            （3）Bisecting k-means（二分k均值算法） 
            （4）Gaussian Mixture Model (GMM)。 
            基于RDD API的MLLib中，共有六种聚类方法： 
            （1）K-means 
            （2）Gaussian mixture 
            （3）Power iteration clustering (PIC) 
            （4）Latent Dirichlet allocation (LDA)** 
            （5）Bisecting k-means 
            （6）Streaming k-means 
            多了Power iteration clustering (PIC)和Streaming k-means两种。 
           本文将PIC,即幂迭代聚类。其它方法在我Spark机器学习系列里面都有介绍。

概述

           谱聚类（Spectral Clustering）相信大家可能非常熟悉（如果不熟悉的话相关资料也比较多），而幂迭代聚类（Power iteration clustering）则也许会比较陌生。其实这两者之间有很多相似的地方，但是算法还是有较大差异的，这些后面会慢慢道来。 
            幂迭代聚类来自Frank Lin 和William W. Cohen这两位卡内基梅隆大学大牛，发表于ICML 2010。深入了解算法则需要看看大牛的原文。 
            这里给出链接http://www.cs.cmu.edu/~wcohen/postscript/icml2010-pic-final.pdf 
           如果具备一定的谱聚类和Graphx图计算的知识，就比较容易理解幂迭代聚类，不过不太懂也没有关系，Graphx图计算可以简单看看我的Spark系列博文，谱聚类后面会简单介绍一下，另外算法的数学基础是幂迭代求特征值，我后面会详细介绍。 
           两位大牛提出一种简单且可扩展的图聚类方法，称之为幂迭代聚类（PIC）。在数据归一化的逐对相似矩阵上，使用截断的幂迭代，PIC寻找数据集的一个超低维嵌入（低纬空间投影，embedding ），这种嵌入恰好是很有效的聚类指标，使它在真实数据集上总是好于广泛使用的谱聚类方法（比如说NCut）。PIC在大数据集上非常快，比基于当前（2010年）最好的特征向量计算技术实现的NCut还要快1000倍。 
       We present a simple and scalable graph clustering method called power iteration clustering (PIC). PIC finds a very low-dimensional embedding of a dataset using truncated power iteration on a normalized pair-wise similarity matrix of the data. This embedding turns out to be an effective cluster indicator, consistently outperforming widely used spectral methods such as NCut on real datasets. PIC is very fast on large datasets, running over 1,000 times faster than an NCut implementation based on the state-of-the-art IRAM eigenvector computation technique.

幂迭代法求矩阵的主特征值

           首先还是理清基本的数学算法，这样后面分析就容易多了。“幂迭代”法求特征值，也有直接就叫做“幂法”求特征值的，也是最基础的一种特征值迭代法求解方法。 
           适合计算大型稀疏矩阵的主特征值，即按模最大的特征值，同时也得到了对应的特征向量（这不就是为大数据集，通常还是稀疏矩阵量身打造的吗？呵呵）。 
        它的优点是方法简单，理论依据是迭代的收敛性（这两点要看完下面的过程才能深刻的理解）        幂法基本思想是:若我们求某个n阶方阵AA的特征值和特征向量,先任取一个非零初始向量v(0)v(0),进行如下的迭代计算,直到收敛（下面都是对｛v(k)，   k=0,1,...v(k)，   k=0,1,...｝序列而言的）： 
v(k+1)=Av(k)       k=0,1,...v(k+1)=Av(k)       k=0,1,...       当kk增大时,序列的收敛情况与绝对值最大的特征值有密切关系,分析这一序列的极限,即可求出按模最大的特征值和特征向量。 
       假定矩阵AA有n个线性无关的特征向量.n个特征值按模由大到小排列: 
│λ1│>=│λ2│>=…>=│λn│      (2)│λ1│>=│λ2│>=…>=│λn│      (2)
       其相应的特征向量为: 
e1,e2,…,en      (3)e1,e2,…,en      (3)
       它们构成n维空间的一组正交基.任取的初始向量v(0))v(0))当然可以由它们的线性组合给出： 
v(0)=c1e1+c2e2+…+cnen      (4)v(0)=c1e1+c2e2+…+cnen      (4)
由此知,构造的向量序列有 
v(k)=Av(k−1)=A2v(k−2)=…=Akv(0) =c1<