k_mean.cpp

K均值KMean聚类算法

//20个点，分两类
#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;

#define N_CLASS 4	//分类数
#define N_POINT 20	//点的个数
#define VERY_BIG 999999999.9	//超过程序中可能遇到的所有数的一个值，也就是无穷大

struct Point{
	double x;
	double y;
};
struct Index{
	int in_class;//哪一类
	int in_length;//类大小
};
//求size个点的新聚心
void Average(struct Point *c, int size, struct Point *p);
//比较两个长度相同的向量是否所有对应元素相等
bool SameVector(vector<Point> &y, vector<Point> &z, int size);
//比较两个浮点值是否相等
bool DoubleCompare(double a, double b);

int main(void)
{
	vector<Point> p;//点向量
	vector<Point> z;//聚心向量
	vector<Point> y;//备份聚心向量
	Point c[N_CLASS][N_POINT];//20个点分两类
	Index index[N_CLASS];
	int i=0, j=0;
	double d;

	cout << "请输入 "<< N_POINT << " 个点"<< "进行聚类分析，将分成 " << N_CLASS << " 个类" <<endl;
	Point temp;
	for(i=0;i<N_POINT;i++){
		cin >> temp.x >> temp.y;
		p.push_back(temp);
		if(i<N_CLASS)//选择N_CLASS个聚心
		{
			z.push_back(temp);
		}
	}
	int k=0;
	int min_index, class_index;	
	do{
		for(i=0;i<N_CLASS;i++){
			index[i].in_class = i;
			index[i].in_length = 0;
		}
		y.clear();//初始化

		for(i=0;i<N_POINT;i++)	
		{
			double min_d=VERY_BIG;
			for(j=0;j<N_CLASS;j++)	
			{
				d = sqrt( (p[i].x - z[j].x)*(p[i].x - z[j].x) + (p[i].y - z[j].y)*(p[i].y - z[j].y) );
				if(d < min_d)
				{
					min_d = d;
					min_index = i;
					class_index = j;//保留最小的
				}
			}
			//划分类,将min_index点话奋进class_index类
			c[ class_index ][ index[class_index].in_length ].x = p[min_index].x;
			c[ class_index ][ index[class_index].in_length ].y = p[min_index].y;
			index[class_index].in_length++;			
		}
		//保存旧聚心
		for(vector<Point>::iterator itr_z=z.begin();itr_z!=z.end();itr_z++)
			y.push_back(*itr_z);

		//求新聚心
		for(i=0;i<N_CLASS;i++)
		{
			Average(c[i], index[i].in_length, &z[i]);
		}
		k++;
//		if(k==100)
//			break;
	}while(!SameVector(y, z, y.size()));

	cout<<"分类结果是:"<<endl;
	for(i=0;i<N_CLASS;i++)
	{
		cout<< "以"<< "( "<<z[i].x << " , " << z[i].y <<" )"<<"为聚心"<< "有以下的点"<<endl;
		for(j=0;j<index[i].in_length;j++)
			cout << "( " << c[i][j].x << " , " << c[i][j].y << " )" << endl;
	}
	cout << "共迭代"<< k <<"次"<< endl;
	return 0;
}
//求size个点的新聚心
void Average(struct Point *c, int size, struct Point *p)
{
	int i;
	for(i=0;i<size;i++)
	{
		p->x+=c[i].x;
		p->y+=c[i].y;
	}
	p->x /= size;
	p->y /= size;
}

bool SameVector(vector<Point> &y, vector<Point> &z, int size)
{
	int i;
	for(i=0;i<size;i++)
	{
		if(!DoubleCompare(y[i].x, z[i].x) || !DoubleCompare(y[i].y, z[i].y) )
			return false;
	}
	return true;
}

bool DoubleCompare(double a, double b)
{
	if( abs(a - b) < 0.00001 )
		return true;
	return false;
}