kmean.cpp

K均值法

#include "stdlib.h"
#include "stdio.h"
#include "math.h"

//求两个2维向量之间的模
double dist(double *x1,double*x2)
{
	return(pow(pow(x1[0]-x2[0],2)+pow(x1[1]-x2[1],2),0.5));
}

//k均值函数
//centernum设定的初始中心数目
//samplenum输入样本点个数
//iteration最大迭代次数
//x样本点坐标数组
void kmean(int centernum,int samplenum,int iteration,double **x)
{
	int i,j,l,*xcla,*temp,temp1;
	double **center,**centernew,**d;

	//存放每个样本点应属于哪个聚类中心
	xcla=(int*)malloc(samplenum*sizeof(int));
	
	//中心赋初值
	if(centernum==2)
	{
		//存放中心点坐标
		center=(double**)malloc(centernum*sizeof(double*));
		for(i=0;i<centernum;i++)
			center[i]=(double*)malloc(2*sizeof(double));
		//存放新的中心点坐标
		centernew=(double**)malloc(centernum*sizeof(double*));
		for(i=0;i<centernum;i++)
			centernew[i]=(double*)malloc(2*sizeof(double));
		//存放所有样本到每个中心点之间的距离
		d=(double**)malloc(samplenum*sizeof(double*));
		for(i=0;i<samplenum;i++)
			d[i]=(double*)malloc(centernum*sizeof(double));
		//存放每个中心聚集样本个数
		temp=(int*)malloc(centernum*sizeof(int));
	
		center[0][0]=5;center[0][1]=0;
		center[1][0]=6;center[1][1]=0;
		centernew[0][0]=5;centernew[0][1]=0;
		centernew[1][0]=6;centernew[1][1]=0;
	}
	else
		if(centernum==3)
		{
			center=(double**)malloc(centernum*sizeof(double*));
			for(i=0;i<centernum;i++)
				center[i]=(double*)malloc(2*sizeof(double));
			//存放新的中心点坐标
			centernew=(double**)malloc(centernum*sizeof(double*));
			for(i=0;i<centernum;i++)
				centernew[i]=(double*)malloc(2*sizeof(double));
			//存放所有样本到每个中心点之间的距离
			d=(double**)malloc(samplenum*sizeof(double*));
			for(i=0;i<samplenum;i++)
				d[i]=(double*)malloc(centernum*sizeof(double));
			//存放每个中心聚集样本个数
			temp=(int*)malloc(centernum*sizeof(int));

			center[0][0]=5;center[0][1]=0;
			center[1][0]=6;center[1][1]=0;
			center[2][0]=5.5;center[2][1]=0.5;
			centernew[0][0]=5;centernew[0][1]=0;
			centernew[1][0]=6;centernew[1][1]=0;
			centernew[2][0]=5.5;centernew[2][1]=0.5;
		}
		else
			if(centernum==0)
			{
				printf("\nInput the total number of centers:");
				scanf("%d",&centernum);
				center=(double**)malloc(centernum*sizeof(double*));
				for(i=0;i<centernum;i++)
					center[i]=(double*)malloc(2*sizeof(double));
				//存放新的中心点坐标
				centernew=(double**)malloc(centernum*sizeof(double*));
				for(i=0;i<centernum;i++)
					centernew[i]=(double*)malloc(2*sizeof(double));
				//存放所有样本到每个中心点之间的距离
				d=(double**)malloc(samplenum*sizeof(double*));
				for(i=0;i<samplenum;i++)
					d[i]=(double*)malloc(centernum*sizeof(double));
				//存放每个中心聚集样本个数
				temp=(int*)malloc(centernum*sizeof(int));

				printf("\nInput original center coordinates:");
				for(i=0;i<centernum;i++)
				{
					printf("\nCenter %d: X=?",i+1);
					scanf("%lf",&center[i][0]);
					centernew[i][0]=center[i][0];
					printf("\nCenter %d: Y=?",i+1);
					scanf("%lf",&center[i][1]);
					centernew[i][1]=center[i][1];
				}
			}
			else
			{
				printf("\nWrong center total number!\n");
				exit(0);
			}
	//迭代开始
	for(l=0;l<iteration;l++)
	{
		//样本分类
		for(i=0;i<samplenum;i++)
		{
			for(j=0;j<centernum;j++) d[i][j]=dist(x[i],centernew[j]);
			temp1=0;
			for(j=1;j<centernum;j++) if(d[i][temp1]>d[i][j]) temp1=j;
			xcla[i]=temp1;
			printf("\nxcla[%d]=%d",i,xcla[i]);
		}
		//计算新中心
		for(i=0;i<centernum;i++)
		{
			centernew[i][0]=0;centernew[i][1]=0;
			temp[i]=0;
			for(j=0;j<samplenum;j++)
			if(xcla[j]==i)
			{
				centernew[i][0]+=x[j][0];
				centernew[i][1]+=x[j][1];
				temp[i]++;
			}
			if(temp[i]!=0)
			{
				centernew[i][0]/=temp[i];
				centernew[i][1]/=temp[i];
			}
			printf("\n%d   centernew[%d][0]=%f		centernew[%d][1]=%f",l,i,centernew[i][0],i,centernew[i][1]);
			printf("\ntemp[%d]=%d",i,temp[i]);
		}
		//判断新旧中心点坐标是否一致
		for(i=0;i<centernum;i++)
		{
			if(dist(centernew[i],center[i])<10e-6) temp[i]=-1;
			else temp[i]=-2;
			center[i][0]=centernew[i][0];
			center[i][1]=centernew[i][1];
		}
		//判断新的聚类中心位置是否所有都已经不再变化
		//是，计算完毕，退出，否继续迭代
		temp1=0;
		for(i=0;i<centernum;i++) if(temp[i]==-1) temp1++;
		if(temp1==centernum)
		{
			printf("\nThe k_mean net has convergenced!\n\nThe result of centers are:\n");
			for(i=0;i<centernum;i++) printf("\ncenter[%d][0]=%f		center[%d][1]=%f",i,centernew[i][0],i,centernew[i][1]);
			exit(0);
		}
	}
	printf("\nThe k_mean net has not convergenced!\n\nThe result of centers are:\n");
	for(i=0;i<centernum;i++) printf("\ncenter[%d][0]=%f		center[%d][1]=%f",i,centernew[i][0],i,centernew[i][1]);
}

void main()
{
	int i;
	double **sample;

	sample=(double**)malloc(15*sizeof(double*));
	for(i=0;i<15;i++)
		sample[i]=(double*)malloc(2*sizeof(double));
	
	sample[0][0]=5;sample[0][1]=0;
	sample[1][0]=6;sample[1][1]=0;
	sample[2][0]=5;sample[2][1]=1;
	sample[3][0]=6;sample[3][1]=1;
	sample[4][0]=5.5;sample[4][1]=0.5;
	sample[5][0]=0;sample[5][1]=9;
	sample[6][0]=0;sample[6][1]=10;
	sample[7][0]=1;sample[7][1]=9;
	sample[8][0]=1;sample[8][1]=10;
	sample[9][0]=0.5;sample[9][1]=9.5;
	sample[10][0]=5;sample[10][1]=9;
	sample[11][0]=5;sample[11][1]=10;
	sample[12][0]=6;sample[12][1]=9;
	sample[13][0]=6;sample[13][1]=10;
	sample[14][0]=5.5;sample[14][1]=9.5;

	kmean(3,15,1000,sample);
}