K均值聚类是当前机器学习的一个热门，也是聚类中比较实用的方法。K均值聚类也存在这一些问题：首先，K值的确定比较困难。对于N个样本点，K值可以取2到N中任意一个整数，K值的选取会对收敛过程及最终结果产生较大影响，这一点在下面的实验中可以看到。其次，初始聚类中心选择的好坏也会在很大程度上影响迭代过程。另外，聚类完成后，聚类中心有可能只是收敛到局部最小值，而不是全局最优解。当然很多这个领域的专家已经对这些问题进行了研究，也提出了一些有效的方法。

       通常我们使用批量K均值聚类，也就是在每轮迭代中考虑所有样本点，从而改进聚类中心。但是批量K均值聚类对于高维数大样本集进行聚类的效果可不是怎么乐观。为此我做了一个实验，Matlab代码如下：

function [  ] = testKmeans( classnumber , k )

%   Test the convergence  of batch kmeans

%   classnumber is the real number of classes of samples

width = 128;                样本维数

X = zeros(100*classnumber , width);      每个实际类中选取100个样本，每个样本128维    

for i = 1: classnumber

    temp = randn(100 , width) + ones(100,width)*i;    一个样本的每一维都服从相同的高斯分布

    start = (i-1)*100+1;

    last = i*100;

    X(start:last ,:) = temp;       所有样本保存在X矩阵中

end

kmeans(X,k);       进行batch K均值聚类

end

对于不同的K值的选取，实验结果如下：

k=2、3、4、5、6、7、8、9、11、13、14、21、25、38，算法在1000个循环内收敛。

k=10、12、15、16、17、18、19、20、21、22、23……40，算法在1000个循环内不收敛。http://www/uc/myshow/blog/misc/gif/E___6706EN00SIGG.gifK-means Clustering）" TITLE="连续/在线k均值聚类（Sequential K-means Clustering）" />

        从上面的实验结果中可以看出，K值的选取对这个高维数大样本集的聚类结果有很大的影响。然而在实际的应用中会存在很多这种样本集，相比而言，这还只是一个比较简单的样本集。另外一个问题是，在使用batch K均值聚类进行聚类时占用的系统资源（主要是CPU和内存）会很大，所以对于高维数大样本集问题batch K均值聚类似乎不是很好的选择。

       Sequential K-means（连续K均值或者说在线K均值）的提出很好的解决了这个问题。从她的名称中也可以直观的想到，这种方法每次使用一个样本点来更新聚类中心，而不是每一轮迭代用所有的样本点来更新聚类中心。伪代码如下：

* Make initial guesses for the means m1, m2, ..., mk

* Set the counts n1, n2, ..., nk to zero

* Until interrupted

        * Acquire the next example, x

        * If mi is closest to x

                  * Increment ni

                  * Replace mi by mi + (1/ni)*( x - mi)

       * end_if

* end_until

      这个算法的实现比较简单，根据伪代码可以很容易的写出具体的实现。当然还可以对该伪代码中均值的计算方法 mi + (1/ni)*( x - mi)进行修改，例如可以使用常数a，得到mi + a*( x - mi )等等。我对Sequential K-means方法进行了测试，发现这种方法的聚类效果还是挺好的，并且对系统资源的占用也是比较少的。

参考链接：http://www.cs.princeton.edu/courses/archive/fall08/cos436/Duda/C/sk_means.htm