kaverage.cpp

模式识别中的K－均值算法演示

// KAverage.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#include "math.h"
#include <list>
using namespace std;

#define  eps   0.00001

struct Point
{
	int sequence;
	int x;
	int y;
};

struct Pointf
{
	float x;
	float y;
};



float CalDistance(Point x1,Pointf x2)
{
	return sqrtf((x1.x-x2.x)*(x1.x-x2.x)+(x1.y-x2.y)*(x1.y-x2.y));
}

float CalDistancef(Pointf x1,Pointf x2)
{
	return sqrtf((x1.x-x2.x)*(x1.x-x2.x)+(x1.y-x2.y)*(x1.y-x2.y));
}


int main(int argc, char* argv[])
{

	
	Point pts[20]={
	{1,0,0},{2,1,0},{3,0,1},{4,1,1},{5,2,1},
	{6,1,2},{7,2,2},{8,3,2},{9,6,6},{10,7,6},
	{11,8,6},{12,6,7},{13,7,7},{14,8,7},{15,9,7},
	{16,7,8},{17,8,8},{18,9,8},{19,8,9},{20,9,9}
	};
	int i;

	printf("样本集为:\n");

	for(i=0;i<20;i++)
	{
		printf("(%d,%d)  ",pts[i].x,pts[i].y);

		if((i+1)%5==0)
		{
			printf("\n");
		}

	}

	printf("\n");
	printf("\n");


	list<Point*> S1;
	list<Point*> S2;

	Pointf Z1,Z2,Z1new,Z2new;

	int m=0,n=9;
	
	printf("请输入初始聚类中心Z1(0)和Z2(0)的序号(0--19):");
	scanf("%d %d",&m,&n);
	printf("\n");

	if(m<0||m>19||n<0||n>19)
	{
		printf("序号错误\n");
		printf("请输入初始聚类中心Z1(0)和Z2(0)的序号(0~19):");
		scanf("%d %d",&m,&n);
		printf("\n");
	}
	
	Z1.x=(float)(pts[m].x);
	Z1.y=(float)(pts[m].y);
	Z2.x=pts[n].x;
	Z2.y=pts[n].y;

	Z1new.x=0.0;
	Z1new.y=0.0;
	Z2new.x=0.0;
	Z2new.y=0.0;


    list<Point*>::iterator j;

	int k=-1;
	float sumx=0.0;
	float sumy=0.0;
	int count=0;

	while(true)
	{
		k++;

		printf("Z1(%d)=(%.3f,%.3f),Z2(%d)=(%.3f,%.3f)\n",k,Z1.x,Z1.y,k,Z2.x,Z2.y);
		
		for(i=0;i<20;i++)
		{
			if(CalDistance(pts[i],Z1)<CalDistance(pts[i],Z2))
			{
				S1.push_back(&pts[i]);
			}
			else
			{
				S2.push_back(&pts[i]);
			}
		}
		
		
		printf("S1(%d):",k);		
		for(j=S1.begin();j!=S1.end();j++)
		{
			printf("%d,",(*j)->sequence);
			count++;
			sumx+=(*j)->x;
			sumy+=(*j)->y;
		}
		printf("\n");

		Z1new.x=sumx/count;
		Z1new.y=sumy/count;
		count=0;
		sumx=0.0;
		sumy=0.0;
	
		printf("S2(%d):",k);		
		for(j=S2.begin();j!=S2.end();j++)
		{
			printf("%d,",(*j)->sequence);	
			count++;
			sumx+=(*j)->x;
			sumy+=(*j)->y;
		}
		printf("\n");

		Z2new.x=sumx/count;
		Z2new.y=sumy/count;
		count=0;
		sumx=0.0;
		sumy=0.0;

		S1.clear();
		S2.clear();

		if(CalDistancef(Z1,Z1new)<eps&&CalDistancef(Z2,Z2new)<eps\
			||CalDistancef(Z1,Z2new)<eps&&CalDistancef(Z2,Z1new)<eps)
		{
			break;
		}
		else
		{
			Z1.x=Z1new.x;
			Z1.y=Z1new.y;
			Z2.x=Z2new.x;
			Z2.y=Z2new.y;
		}
		printf("\n");
		printf("\n");
	}

	printf("经过%d次循环之后收敛\n",k+1);

	printf("\n");
	printf("\n");
		
	return 0;
}