www.pudn.com > cluster_KM_DS.rar > 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= 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 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; 
}