程序流程圖：  K-means核心功能函數，首先，隨機選擇K-中心點（中心點坐標為簇中所有點的x坐標的平均值，y坐標的平均值，該點用于記錄位置，不屬于原始數據集）；循環判斷中心點是否不變，若是，將二維點對信息寫入clustering文件，程序結束。否則，對于每個二維數據點，選擇與其距離最近的中心點，將點cluster編號更新為中心點的cluster編號。然后對于K-簇，重新計算K-中心點，進入下一個循環判斷。 計算簇中心是否不變可以采用SSE方式，具體實現代碼中已給出，或者直接循環運行多次（不推薦）。 ~~~ /* K-means Algorithm 15S103182 Ethan */ #include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <ctime> #include <cstdlib> #include <limits> using namespace std; /* run this program using the console pauser or add your own getch, system("pause") or input loop */ typedef struct Point{ float x; float y; int cluster; Point (){} Point (float a,float b,int c){ x = a; y = b; cluster = c; } }point; float stringToFloat(string i){ stringstream sf; float score=0; sf<<i; sf>>score; return score; } vector<point> openFile(const char* dataset){ fstream file; file.open(dataset,ios::in); vector<point> data; while(!file.eof()){ string temp; file>>temp; int split = temp.find(',',0); point p(stringToFloat(temp.substr(0,split)),stringToFloat(temp.substr(split+1,temp.length()-1)),0); data.push_back(p); } file.close(); return data; } float squareDistance(point a,point b){ return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } void k_means(vector<point> dataset,int k){ vector<point> centroid; int n=1; int len = dataset.size(); srand((int)time(0)); //random select centroids while(n<=k){ int cen = (float)rand()/(RAND_MAX+1)*len; point cp(dataset[cen].x,dataset[cen].y,n); centroid.push_back(cp); n++; } for(int i=0;i<k;i++){ cout<<"x:"<<centroid[i].x<<"\ty:"<<centroid[i].y<<"\tc:"<<centroid[i].cluster<<endl; } //cluster int time = 100; int oSSE = INT_MAX; int nSSE = 0; while(abs(oSSE-nSSE)>=1){ // while(time){ oSSE = nSSE; nSSE = 0; //update cluster for all the points for(int i=0;i<len;i++){ n=1; float shortest = INT_MAX; int cur = dataset[i].cluster; while(n<=k){ float temp=squareDistance(dataset[i],centroid[n-1]); if(temp<shortest){ shortest = temp; cur = n; } n++; } dataset[i].cluster = cur; } //update cluster centroids int *cs = new int[k]; for(int i=0;i<k;i++) cs[i] = 0; for(int i=0;i<k;i++){ centroid[i] = point(0,0,i+1); } for(int i=0;i<len;i++){ centroid[dataset[i].cluster-1].x += dataset[i].x; centroid[dataset[i].cluster-1].y += dataset[i].y; cs[dataset[i].cluster-1]++; } for(int i=0;i<k;i++){ centroid[i].x /= cs[i]; centroid[i].y /= cs[i]; } cout<<"time:"<<time<<endl; for(int i=0;i<k;i++){ cout<<"x:"<<centroid[i].x<<"\ty:"<<centroid[i].y<<"\tc:"<<centroid[i].cluster<<endl; } //SSE for(int i=0;i<len;i++){ nSSE += squareDistance(centroid[dataset[i].cluster-1],dataset[i]); } // time--; } fstream clustering; clustering.open("clustering.txt",ios::out); for(int i=0;i<len;i++){ clustering<<dataset[i].x<<","<<dataset[i].y<<","<<dataset[i].cluster<<"\n"; } clustering.close(); // cout<<endl; // for(int i=0;i<centroid.size();i++){ // cout<<"x:"<<centroid[i].x<<"\ty:"<<centroid[i].y<<"\tc:"<<centroid[i].cluster<<endl; // } } int main(int argc, char** argv) { vector<point> dataset = openFile("dataset3.txt"); k_means(dataset,7); return 0; } ~~~ 數據文件格式：（x，y） 運行結果格式：（x，y，cluster） 具體文件格式見DBSCAN篇：http://blog.csdn.net/k76853/article/details/50440182 圖形化展現：  總結： K-means算法運行速度快，實現簡便。但K-means算法對具有變化大小，變化密度，非圓形狀等特點的數據具有局限性。解決方法是增加K的大小，增加cluster數量，使得數據的特征能夠更加明顯。對于數據初始中心點的選擇，采用隨機的方式可能無法產生理想的聚類，這時可以采用二分K-means方法，或層次聚類進行處理。