http://blog.csdn.net/cai0538/article/details/7061922

這是一篇關于k均值算法的小文章，程序使用的是上一個人的，不過，為程序稍微多做了一些注解，方便理解。

同時也參考了

http://www.cnblogs.com/CBDoctor/archive/2011/10/24/2222358.html

K-means算法是最簡單的一種聚類算法。算法的目的是使各個樣本與所在類均值的誤差平方和達到最小（這也是評價K-means算法最后聚類效果的評價標準）

K-means聚類算法的一般步驟：

初始化。輸入基因表達矩陣作為對象集X，輸入指定聚類類數N，并在X中隨機選取N個對象作為初始聚類中心。設定迭代中止條件，比如最大循環次數或者聚類中心收斂誤差容限。

進行迭代。根據相似度準則將數據對象分配到最接近的聚類中心，從而形成一類。初始化隸屬度矩陣。

更新聚類中心。然后以每一類的平均向量作為新的聚類中心，重新分配數據對象。

反復執行第二步和第三步直至滿足中止條件。#include?<iostream>?? #include?<fstream>?? #include?<vector>?? #include?<math.h>?? #define?k?3?? using?namespace?std;??//存放元組的屬性信息?? struct?Tuple{??float?attr1;??float?attr2;?? };??//計算兩個元組間的歐幾里距離?? float?getDistXY(Tuple?t1,?Tuple?t2)??? {??return?sqrt((t1.attr1?-?t2.attr1)?*?(t1.attr1?-?t2.attr1)?+?(t1.attr2?-?t2.attr2)?*?(t1.attr2?-?t2.attr2));?? }??//根據質心，決定當前元組屬于哪個簇，?其中means[]數組保存到額是每個簇的質心 //這個函數大概是讓每一個元素與所有的質心通過距離比較，計算它應該屬于哪個簇。返回簇的索引 int?clusterOfTuple(Tuple?means[],Tuple?tuple){??float?dist=getDistXY(means[0],tuple);??float?tmp;??int?label=0;//標示屬于哪一個簇//只有k個簇，所以對于每一個元素只需要判斷它距離哪一個簇的質心最近就好了。for(int?i=1;i<k;i++){??tmp=getDistXY(means[i],tuple);??if(tmp<dist)?{dist=tmp;label=i;}??}??return?label;????? }//獲得給定簇集的平方誤差?? float?getVar(vector<Tuple>?clusters[],?Tuple?means[]){??float?var?=?0;??for?(int?i?=?0;?i?<?k;?i++)??{??//計算第k個簇中的平方誤差之和vector<Tuple>?t?=?clusters[i];?//獲得第i簇的所有元素，?means[i]表示該簇的質心?for?(int?j?=?0;?j<?t.size();?j++)??{??var?+=?getDistXY(t[j],?means[i]);??}??}??//cout<<"sum:"<<sum<<endl;??return?var;??}//獲得當前簇的均值（質心）?? Tuple?getMeans(vector<Tuple>?cluster){??int?num?=?cluster.size();??double?meansX?=?0,?meansY?=?0;??Tuple?t;??for?(int?i?=?0;?i?<?num;?i++)??{??meansX?+=?cluster[i].attr1;??meansY?+=?cluster[i].attr2;??}??t.attr1?=?meansX?/?num;??t.attr2?=?meansY?/?num;??return?t;??//cout<<"sum:"<<sum<<endl;?? }?? void?KMeans(vector<Tuple>?tuples){?//tuples?包含所有的數據集，而我們要把它分成k簇，沒一簇包含幾個數據，所以在這里定義了的是大小為k的vector，大小會自增長，//這k個簇分別對應的質心為means[k]中的元素。vector<Tuple>?clusters[k];?//k個元組，表示k個簇的質心??Tuple?means[k];int?i=0;??//默認一開始將前K個元組的值作為k個簇的質心（均值）??for(i=0;i<k;i++){??means[i].attr1=tuples[i].attr1;??means[i].attr2=tuples[i].attr2;??}??int?lable=0;??//根據默認的質心給簇賦值。遍歷，分別求出每個元素所屬于的簇，并壓入相應的簇的數組for(i=0;i!=tuples.size();++i){??lable=clusterOfTuple(means,tuples[i]);??clusters[lable].push_back(tuples[i]);??}??//輸出剛開始的簇??for(lable=0;lable<k;lable++){??cout<<"第"<<lable+1<<"個簇："<<endl;??vector<Tuple>?t?=?clusters[lable];??for?(i?=?0;?i<?t.size();?i++)??{??cout<<"("<<t[i].attr1<<","<<t[i].attr2<<")"<<"???";??}?????cout<<endl;??}??float?oldVar=-1;??//該函數求出對于所有簇，假如說k=3，也就是3個簇平方誤差之和。float?newVar=getVar(clusters,means);??//第一次newVal和oldVal都是在while循環外獲得的，但是第二次就是在循環內部獲得的。//從循環內跳出到執行while判決，則說明上次的簇的質心和簇都已經建立完畢//如果判斷為假，說明還要繼續進入循環，修改簇的質心和簇。while(abs(newVar?-?oldVar)?>=?1)?//當新舊函數值相差不到1即準則函數值不發生明顯變化時，算法終止??{??//在更新每個簇的中心以后，需要清空每個簇。這是為了在新的中心確定以后，繼續以此迭代往相應的簇中添加數據。for?(i?=?0;?i?<?k;?i++)?//更新每個簇的中心點??{??means[i]?=?getMeans(clusters[i]);??//cout<<"means["<<i<<"]:"<<means[i].attr1<<"??"<<means[i].attr2<<endl;??}??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]);??}??//輸出當前的簇??for(lable=0;lable<k;lable++){??cout<<"第"<<lable+1<<"個簇："<<endl;??vector<Tuple>?t?=?clusters[lable];??for?(i?=?0;?i<?t.size();?i++)??{??cout<<"("<<t[i].attr1<<","<<t[i].attr2<<")"<<"???";??}?????cout<<endl;??}??}??}??int?main(void){??char?fname[256];??cout<<"請輸入存放數據的文件名：?";??cin>>fname;??cout<<endl;??ifstream?infile;??infile.open(fname,ios::in);??if(!infile){??cout<<"不能打開輸入的文件"<<fname<<endl;??return?0;??}??int?count=0;??vector<Tuple>?tuples;??Tuple?tuple;??//從文件流中讀入數據??while(!infile.eof()){??count++;??if(count%2==1)?infile>>tuple.attr1;??else?{??infile>>tuple.attr2;??tuples.push_back(tuple);??}??}??//int?k;??//cout<<"請輸入期望的簇的個數："??//cin>>k;??//cout<<endl;??//輸出文件中的元組信息??for(vector<Tuple>::size_type?ix=0;ix!=tuples.size();++ix)??cout<<"("<<tuples[ix].attr1<<","<<tuples[ix].attr2<<")"<<"????";??cout<<endl;??KMeans(tuples);??cout<<"請觀看結果";int?b;cin>>b;if?(0?==?b)?{return?0;}return?0;?? }??

同時也參考了 http://www.cnblogs.com/leoo2sk/archive/2010/09/20/k-means.html 其中上文的例子生動有趣，順便也調侃了一下中國足球，當然這又是后話了。 所謂聚類問題，就是給定一個元素集合D，其中每個元素具有n個可觀察屬性，使用某種算法將D劃分成k個子集，要求每個子集內部的元素之間相異度盡可能低，而不同子集的元素相異度盡可能高。其中每個子集叫做一個簇。 ? k均值算法的計算過程非常直觀：

????? 1、從D中隨機取k個元素，作為k個簇的各自的中心。

????? 2、分別計算剩下的元素到k個簇中心的相異度，將這些元素分別劃歸到相異度最低的簇。

????? 3、根據聚類結果，重新計算k個簇各自的中心，計算方法是取簇中所有元素各自維度的算術平均數。

????? 4、將D中全部元素按照新的中心重新聚類。

????? 5、重復第4步，直到聚類結果不再變化。

????? 6、將結果輸出。

希望能夠幫助讀者快速的理解k-均值算法

總結

以上是生活随笔為你收集整理的关于k-均值算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。