kmeans.cpp

聚类研究

// kmeans.cpp: implementation of the Ckmeans class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "cluster.h"
#include "kmeans.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
#define LITTLE_CIRCLE 50
#define LARGE_CIRCLE 100
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Ckmeans::Ckmeans()
{
	E1 = E2 =0.0;
    Cw = NULL;
	p = NULL;
	den = NULL;
	Cl_k = 0;
}
void Ckmeans::KMeans(const int count ,const int k )
{
//	initiate();
	double sum_x ,sum_y ;
	sum_x = sum_y = 0.0;
	do{
		int i,j,n;
		for( i = 0; i < count; i++)
		{
			int m = select(i,count,k);
			Cw[m].num[Cw[m].count++] = i;
		}
		for(  n = 0; n < k; n++)
		{
			for( j = 0; j < Cw[n].count ; j++)
			{
				sum_x += p[ Cw[n].num[j] ].x;
				sum_y += p[ Cw[n].num[j] ].y;
			}
			Cw[n].w.x = (int)(sum_x/Cw[n].count);
			Cw[n].w.y = (int)(sum_y/Cw[n].count);
			sum_x = 0.0;
			sum_y = 0.0;
		}
		for(i = 0; i< k;i++)
			for(j = 0; j<Cw[i].count ;j++)
				E1 += distance( Cw[i].w,p[ Cw[i].num[j] ] );
		if( (0 <= E1 - E2 && E1 - E2 < CONST_CHANGE) || ( E2 -E1 >= 0 && E2 - E1 < CONST_CHANGE) )
			break;
		E2 = E1;
		E1 = 0.0;
		for(  n = 0; n < k; n++)
		{
			Cw[n].count = 0;
		}
	}while(true);
//	show();

}

long Ckmeans::distance(point p1,point p2)
{
	long dis = 
		(p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
	return dis;
}

int Ckmeans::select(int n,int count,int k)
{
	if(n > count) 
	{
		AfxMessageBox("n > count");
		exit(0);
	}
	long *dis = new long[k];
	int result; 
	bool find = false;
	for(int i = 0; i<k ;i++)
		dis[i] = distance(Cw[i].w,p[n]);
	for(int m = 0;m < k;m++)
	{
		for(int j= 0; j<k; j++)
			if(dis[m] > dis[j])
			{
				find = true;
			    break;
			}
    	if( find == false )
		{
		result = m ;
		break;
		}
		find = false;
	}
	return result;
}
void Ckmeans::dense(int count)
{
	den = new int[count];
	for(int k = 0;k < count; k++)
		den[k] = 0;
	for(int i = 0;i < count; i++)
		for(int j = 0;j < count; j++)
		{
			if( distance(p[i],p[j]) <= LITTLE_CIRCLE * LITTLE_CIRCLE)
				den[j]++;
		}
	int *center = new int[255],n = 0;
	for(int m = 0 ; m < 255; m++)
		center[m] = 0;
	center[n] = max_den(count);
	den[ center[n] ] = 0;
	n++;
	int temp;
	bool over;
	do{
		over= false;
         temp = max_den(count);
		 for( int ii = 0; ii < n ; ii++)
			 if( distance(p[center[ii]],p[temp]) <= LARGE_CIRCLE*LARGE_CIRCLE )
				 den[ temp ] = 0;
		 if( den[temp] )
			 center[ n++ ] = temp;
		 for(int jj = 0; jj < count; jj++)
			 if(den[jj]) 
				 over = true;
		if( !over ) break;
	}while(true);
    if( Cw ) delete [] Cw;
	Cw = new C_point[n];
	for(int j1 = 0; j1 < n; j1++)
	{
		Cw[j1].w.x = p[ center[j1] ].x;
		Cw[j1].w.y = p[ center[j1] ].y;
		Cw[j1].num = new int[count];
		Cw[j1].count = 0;
	}
	Cl_k = n;
    KMeans(count,n);
    delete[] center;
}

int Ckmeans::max_den(int count)
{
	bool find ;
	for( int i = 0; i < count ; i++ )
		
	{
		find = true;
		for(int j = 0 ; j < count ; j++)
			if( den[i] < den[j] ) 
			{
				find = false;
				break;
			}
        if( find ) 
			break;
	}
	return i;
}