kmeans.cpp

聚类算法研究

// KMEANS.cpp: implementation of the KMEANS class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "gqk_mini2.h"
#include "KMEANS.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

KMEANS::KMEANS()
{
	K = 3;
}

KMEANS::~KMEANS()
{

}

void KMEANS::start (int vn , int vs , float vd[] , char rst[])
{
	int  i;

	result = rst;
	initiate (vn , vs , vd);

	for (i = 1 ; i < 50 ; i++)
	{
		showresult ();
		if (allocate () == 1)break;
	}	
	
	showresult ();
	free (datafield);
	free (tempcenter);
	for (i = 0 ; i < K ; i++)
		free (group[i].center);
}

void KMEANS::initiate (int vn , int vs , float vd[])
{
	int  i , j , size;
	float  d;
	vectornum = vn;
	vectorsize = vs;

	size = vectornum * (vectorsize + 1);
	datafield = (float *) calloc (size , sizeof (float));
	tempcenter = (float *) calloc (vectorsize , sizeof (float));

	for (i = 0 ; i < vectornum ; i++)
	{
		for (j = 0 ; j < vectorsize ; j++)
		{
			d = vd[ i * vectorsize + j ];
			write (i , j + 1 , d);
		}
		write (i , 0 , -1);
	}

	group = (struct GROUP *) calloc (K , sizeof (g));	
	for (i = 0 ; i < K ; i++)
	{
		group[i].center = (float*) calloc ((vectorsize) , sizeof (d));
		group[i].groupsize = 0;
	}
	
	for (i = 0 ; i < K ; i++)
	{
		for (j = 0 ; j < vectorsize ; j++)
		{
			*(group[i].center + j) = data (i , j + 1);
		}
	}
}

int  KMEANS::allocate()
{
	int  i , j , k , flag , index;
	float  D , D1 , sum;	
	for (i = 0 ; i < K ; i++)
	{
		group[i].groupsize = 0;
	}

	for (i = 0 ; i < vectornum ; i++)//按距离分配到各聚类域
	{
		D = distance (group[0].center , vector(i));
		k = 0;
		for(j = 1 ; j < K ; j++)
		{
			D1 = distance (group[j].center , vector(i));
			if(D > D1)
			{
				k = j;
				D = D1;
			}
		}

		write (i , 0 , (float) k);		
		group[k].groupsize++;
	}
	
	flag = 1;
	for (index = 0 ; index < K ; index++)//计算新的聚类中心
	{
		for (j = 0 ; j < vectorsize ; j++)
			tempcenter[j] = 0.0;
		sum = (float) group[index].groupsize;
		for (i = 0 ; i < vectornum ; i++)
		{
			if (index == (int) data (i , 0))
				for (j = 0 ; j < vectorsize ; j++)
					tempcenter[j] += data (i , j + 1) / sum;
		}
		for (j = 0 ; j < vectorsize ; j++)
		{
			if ( tempcenter[j] != group[index].center[j])
			{
				group[index].center[j] = tempcenter[j];
				flag = 0;
			}
		}
	}
	return flag;	
}

void  KMEANS::showresult()
{
	char tmp[500]={'\0'};
	int  i , j , k;
	for (i = 0 ; i < K ; i++)
	{	
		sprintf(tmp,"\r\n第%3d组聚类中心坐标为:" , i + 1);
		strcat(result,tmp);
		for (j = 0 ; j < vectorsize ; j++){
			sprintf(tmp," %10f " , group[i].center[j]);
			strcat(result,tmp);
		}
		sprintf(tmp," \r\n聚类包含的样本点的坐标为:\r\n ");
		strcat(result,tmp);
		for (j = 0 ; j < vectornum ; j++)
		{
			if (data (j , 0) == i)
			{
				for (k = 0 ; k < vectorsize ; k++)
				{
					sprintf(tmp," %10f " , data (j , k + 1));
					strcat(result,tmp);
				}
				sprintf(tmp," \r\n ");
				strcat(result,tmp);
			}
		}	
	}
	sprintf(tmp," \r\n ");
	strcat(result,tmp);
}

float  KMEANS::data (int i , int j)
{
	return *(datafield + i * (vectorsize + 1) + j);
}

void  KMEANS::write (int i , int j , float data)
{
	*(datafield + i * (vectorsize + 1) + j) = data;
}

float  * KMEANS::vector (int i)
{ 
	return datafield + i * (vectorsize + 1) + 1;
}

float  KMEANS::distance (float  * x , float  * y)
{
	int  i;
	float  z;
	for (i = 0 , z = 0 ; i < vectorsize ; i++)
		z = z + ((* (x + i)) - (* (y + i)))*((* (x + i))-(* (y + i)));
	return (float) sqrt (z);
}