1 .基本k均值算法[1]选择k个点作为初始质心repeat，将每个点指派给最近的质心，形成k个簇，并重新计算每个簇的质心until簇保持不变或达到最大迭代次数的时间复杂度这里，t是反复次数，k是簇数，m是记录数，n是维数
空间复杂度： o(mk ) n，其中k是簇数，m是记录数，n是维数
2 .注意问题)1) k决定kmenas算法如何首先选择k个初始重心。 这里，k是用户指定的参数，也就是期望的集群的数目。 这样做的前提是您知道数据集包含多少个群集，但通常不知道数据的分布情况。 事实上，聚类是发现数据分布的手段，陷入了鸡与蛋的矛盾中。 为了有效地确定k值，这里提供了几种方法，如果有更好的方法请考虑。
1 .与分级聚类相结合的[2]产生良好聚类结果的一个有趣策略是首先使用分级聚集算法来确定结果的粗糙度数目，找到第一聚类，然后使用迭代重排来改进该聚类
2 .稳定性方法(3)稳定性方法对一个数据集进行两次重采样生成两个数据子集，再用相同的聚类算法对两个数据子集进行聚类，生成具有k个聚类的两个聚类结果，再生成两个聚类结果两个聚类结果具有较高的相似度表明k个聚类反映了稳定的聚类结构，其相似度可用于估计聚类个数。 用以下方法尝试多个k，找到合适的k值。
3 .系统进化方法[3]系统进化方法将一个数据集视为伪热力学系统，当数据集分为k个簇时，系统称为处于状态k。 系统从初始状态K=1出发，经过分裂过程和合并过程，系统演化为其稳定平衡状态Ki，对应的聚类结构决定最优类数Ki。 系统演化方法可以为所有集群之间的相对边界距离或可分离度提供，适用于与明显分离的集群结构略微重叠的集群结构。
利用canopy算法进行初始划分[4]基于canopy方法的聚类算法将聚类过程分为两个阶段
Stage1，聚类中花费最多的是计算对象的相似性时。 Canopy Method在第一阶段选择简单、计算成本低的方法计算对象的相似性，将相似对象放在一个子集上。 这个子集被称为Canopy，通过一系列的计算可以得到几个Canopy。 复印之间可以重叠，但不存在不属于任何复印的对象
阶段2，在每个Canopy中使用传统的聚类方法，例如k均值，不在不属于同一Canopy的对象之间进行相似性计算。
从这个方法中至少可以看到两个优点。 首先，如果Canopy过大且Canopy之间不重叠，则需要计算后续相似性的对象数量将大幅减少。 其次，k均值这种聚类方法需要人为地指出k的值，Stage1中得到的Canopy个数可以完全是这个k的值，在一定程度上减少了选择k的盲目性。
其他方法，例如贝叶斯信息基准方法(BIC )可以参考文献[5]。
(2)选择初始质心选择合适的初始质心是基本k均值算法的重要步骤。 常见的方法是随机选择初始质心，但聚类质量往往较差。 解决初始质心选择问题的一种常见方法是每次都使用一组不同的随机初始质心多次运行，以选择具有最小毛衣(误差平方和)的簇集。 此策略很简单，但根据数据集和搜索的群集数量，效果可能会很差。 第二种有效的方法是对样本进行采样，并使用分层聚类技术进行聚类。 从层次聚类中提取k个聚类，并将这些聚类的重心作为初始重心。 该方法通常有效，但仅在以下情况下有效。 (1)样本相对较小，例如数百至数千个分层聚类开销较大)； )2)选择样本大小k小的第三初始质心的方法是随机选择第一个点，或将所有点的质心作为第一个点。 然后，对于每个后续的初始重心，选择距离已经选择的初始重心最远的点。 使用此方法，可以确保选定的初始质心不仅是随机的，而且是零散的。 但是，这种方法可能会选择离群点。 另外，求出距离现在的初始重心位置最远的点的开销也非常大。 为了克服这个问题，该方法通常被用于点样本。 因为离群点很少(多的话就不是离群点)，所以很多时候不会在随机样本中出现。 计算量也大幅减少。 第四种方法是上述的canopy算法。 (3)距离测量常用的距离测量方法有愉快的白开水距离和余弦相似度。 两者都是评价个体间差异的大小。 愉快的白开水距离测量受指标不同的单位刻度的影响，一般首先需要标准化，同时距离越大个体间差异越大的空间矢量馀弦夹角相似度度量不受指标刻度的影响，馀弦值在区间[-1，1 ]，值越大差异越小但是，针对具体应用，在什么情况下使用高草丛距离，在什么情况下使用余弦相似度？ 在几何意义上，将n维向量空间的线段设为由底边和原点构成的三角形，其顶角的大小不确定。 也就是说，对于两个空间向量，即使两点之间的距离一定，他们的夹角余弦值也可以自由变化。 感性认识中，当两用户得分倾向一致时，但得分值差异较大，余弦相似度倾向给出更好的解。 举个极端的例子，两个用户只评价两个商品，向量分别为(3，3 )和(5，5 )，这两个用户的认知其实是1
样的，但是欧式距离给出的解显然没有余弦值合理。[6]（4）质心的计算 对于距离度量不管是采用欧式距离还是采用余弦相似度，簇的质心都是其均值，即向量各维取平均即可。对于距离对量采用其它方式时，这个还没研究过。 （5）算法停止条件 一般是目标函数达到最优或者达到最大的迭代次数即可终止。对于不同的距离度量，目标函数往往不同。当采用欧式距离时，目标函数一般为最小化对象到其簇质心的距离的平方和，如下：
当采用余弦相似度时，目标函数一般为最大化对象到其簇质心的余弦相似度和，如下：
（6）空聚类的处理 如果所有的点在指派步骤都未分配到某个簇，就会得到空簇。如果这种情况发生，则需要某种策略来选择一个替补质心，否则的话，平方误差将会偏大。一种方法是选择一个距离当前任何质心最远的点。这将消除当前对总平方误差影响最大的点。另一种方法是从具有最野性的鲜花的簇中选择一个替补的质心。这将分裂簇并降低聚类的总SSE。如果有多个空簇，则该过程重复多次。另外，编程实现时，要注意空簇可能导致的程序bug。 3.适用范围及缺陷 Kmenas算法试图找到使平凡误差准则函数最小的簇。当潜在的簇形状是凸面的，簇与簇之间区别较明显，且簇大小相近时，其聚类结果较理想。前面提到，该算法时间复杂度为O(tKmn)，与样本数量线性相关，所以，对于处理大数据集合，该算法非常高效，且伸缩性较好。但该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。 4.实现 #include <iostream>#include <sstream>#include <fstream>#include <vector>#include <math.h>#include <stdlib.h>#define k 3//簇的数目using namespace std;//存放元组的属性信息typedef vector<double> Tuple;//存储每条数据记录int dataNum;//数据集中数据记录数目int dimNum;//每条记录的维数//计算两个元组间的欧几里距离double getDistXY(const Tuple& t1, const Tuple& t2) {double sum = 0;for(int i=1; i<=dimNum; ++i){sum += (t1[i]-t2[i]) * (t1[i]-t2[i]);}return sqrt(sum);}//根据质心，决定当前元组属于哪个簇int clusterOfTuple(Tuple means[],const Tuple& tuple){double dist=getDistXY(means[0],tuple);double tmp;int label=0;//标示属于哪一个簇for(int i=1;i<k;i++){tmp=getDistXY(means[i],tuple);if(tmp<dist) {dist=tmp;label=i;}}return label;}//获得给定簇集的平方误差double getVar(vector<Tuple> clusters[],Tuple means[]){double var = 0;for (int i = 0; i < k; i++){vector<Tuple> t = clusters[i];for (int j = 0; j< t.size(); j++){var += getDistXY(t[j],means[i]);}}//cout<<"sum:"<<sum<<endl;return var;}//获得当前簇的均值（质心）Tuple getMeans(const vector<Tuple>& cluster){int num = cluster.size();Tuple t(dimNum+1, 0);for (int i = 0; i < num; i++){for(int j=1; j<=dimNum; ++j){t[j] += cluster[i][j];}}for(int j=1; j<=dimNum; ++j)t[j] /= num;return t;//cout<<"sum:"<<sum<<endl;}void print(const vector<Tuple> clusters[]){for(int lable=0; lable<k; lable++){cout<<"第"<<lable+1<<"个簇："<<endl;vector<Tuple> t = clusters[lable];for(int i=0; i<t.size(); i++){cout<<i+1<<".(";for(int j=0; j<=dimNum; ++j){cout<<t[i][j]<<", ";}cout<<")n";}}}void KMeans(vector<Tuple>& tuples){vector<Tuple> clusters[k];//k个簇Tuple means[k];//k个中心点int i=0;//一开始随机选取k条记录的值作为k个簇的质心（均值）srand((unsigned int)time(NULL));for(i=0;i<k;){int iToSelect = rand()%tuples.size();if(means[iToSelect].size() == 0){for(int j=0; j<=dimNum; ++j){means[i].push_back(tuples[iToSelect][j]);}++i;}}int lable=0;//根据默认的质心给簇赋值for(i=0;i!=tuples.size();++i){lable=clusterOfTuple(means,tuples[i]);clusters[lable].push_back(tuples[i]);}double oldVar=-1;double newVar=getVar(clusters,means);cout<<"初始的的整体误差平方和为："<<newVar<<endl; int t = 0;while(abs(newVar - oldVar) >= 1) //当新旧函数值相差不到1即准则函数值不发生明显变化时，算法终止{cout<<"第 "<<++t<<" 次迭代开始："<<endl;for (i = 0; i < k; i++) //更新每个簇的中心点{means[i] = getMeans(clusters[i]);}oldVar = newVar;newVar = getVar(clusters,means); //计算新的准则函数值for (i = 0; i < k; i++) //清空每个簇{clusters[i].clear();}//根据新的质心获得新的簇for(i=0; i!=tuples.size(); ++i){lable=clusterOfTuple(means,tuples[i]);clusters[lable].push_back(tuples[i]);}cout<<"此次迭代之后的整体误差平方和为："<<newVar<<endl; }cout<<"The result is:n";print(clusters);}int main(){char fname[256];cout<<"请输入存放数据的文件名： ";cin>>fname;cout<<endl<<" 请依次输入: 维数 样本数目"<<endl;cout<<endl<<" 维数dimNum: ";cin>>dimNum;cout<<endl<<" 样本数目dataNum: ";cin>>dataNum;ifstream infile(fname);if(!infile){cout<<"不能打开输入的文件"<<fname<<endl;return 0;}vector<Tuple> tuples;//从文件流中读入数据for(int i=0; i<dataNum && !infile.eof(); ++i){string str;getline(infile, str);istringstream istr(str);Tuple tuple(dimNum+1, 0);//第一个位置存放记录编号，第2到dimNum+1个位置存放实际元素tuple[0] = i+1;for(int j=1; j<=dimNum; ++j){istr>>tuple[j];}tuples.push_back(tuple);}cout<<endl<<"开始聚类"<<endl;KMeans(tuples);return 0;}
这里是随机选取的初始质心，以鸢尾花的数据集为例，原数据集中1-50为一个簇，51-100为第二个簇，101到150为第三个簇：
第一次运行结果 SSE=97.5905
第二次运行结果 SSE=98.1404
。。。
第五次运行结果 SSE=123.397
由于初始质心是随机选取的，前两次还算正常，运行到第五次时，第一个簇基本包括了后51-150个记录，第二个簇和第三个簇包含了第1-50个记录，可能的原因就是随机选择初始点时，有两个初始点都选在了1-50个记录中。
参考：
[1]cjdrs-xsddm Tan等著，《数据挖掘导论》，2011
[2]Jiawei Han等著，《数据挖掘概念与技术》，2008
[3]聚类分析中类数估计方法的实验比较
[4]http://www.cnblogs.com/vivounicorn/archive/2011/09/23/2186483.html
[5]一种基于贝叶斯信息准则的k均值聚类方法
[6]http://www.zhihu.com/question/19640394?nr=1¬i_id=8736954