当前位置:牛骨文开发手册数据结构与算法小五的算法学习之路 》 聚类算法-K-means-C++实现

程序流程图:

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<<"	y:"<<centroid[i].y<<"	c:"<<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<<"	y:"<<centroid[i].y<<"	c:"<<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<<"
";
	}
	clustering.close();
//	cout<<endl;
//	for(int i=0;i<centroid.size();i++){
//		cout<<"x:"<<centroid[i].x<<"	y:"<<centroid[i].y<<"	c:"<<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方法,或层次聚类进行处理。