kmeansalg.cpp

Clusting using aco with Visual C

// KmeansAlg.cpp: implementation of the CKmeansAlg class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "antclusting.h"
#include "KmeansAlg.h"
#include "math.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

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

CKmeansAlg::CKmeansAlg()
{

}

CKmeansAlg::~CKmeansAlg()
{

}

DataObject * CKmeansAlg::WarSelect(DataObject* OBJ, DataObject *CEN, int k, int n, int tag)
{
	int m,i,j,randnumber;    //OBJ是用来存放全部数据对象的数组，CEN是用来存放中心点的数组，
                             //k是预先指定的分类数, n是全部数据对象个数，tag是算法种类
                                   
	static int bei=0;
	double *Min;
	int total;
	double distance;
	float	xx,yy;
	int test=0;
	double E,Ebk;                   //E为评估函数值，此处的评估函数采用平方误差函数
	                                 //Ebk为前一次已求E值的一个备份
	DataObject TEMP;
	Min=new double[n];
	srand((unsigned)time(NULL));
	for(i=0;i<k;i++)
	{	
	randnumber=rand()%n;
	CEN[i].x=OBJ[randnumber].x;
    CEN[i].y=OBJ[randnumber].y;
    CEN[i].clusterNo=OBJ[randnumber].clusterNo ;
    CEN[i].m_pfa=NULL; 
/*	(GEN+i)->m_pfa=new float[m_nViewPropNum];
	for(int j=0;j<m_nViewPropNum;j++ )
		(float)*((m_pOriDataObj+i)->m_pfa+j)=(float)*((dataObj+i)->m_pfa+j) ;
*/
	}
//任意随机选出k个对象作为簇中心
	bei=bei*k;
//初始化各对象到中心点的距离
	E=0;
	int all_count=0;
	int oo=0;
	do
	{ //使立即能显示结果
	 for(m=1;m<=n;m++)    Min[m]=1000000000000000000;
	 for(i=1;i<=n;i++)
		{
		for(j=0;j<k;j++)
		{ distance=sqrt(pow(OBJ[i].x-CEN[j].x,2)+pow(OBJ[i].y-CEN[j].y,2));
			if(distance<Min[i])
			{	Min[i]=distance;
				OBJ[i].clusterNo=j+bei;  //将每个对象赋给最类似的簇
			}
			}
		}
	 if(tag==0)   //使用k-平均方法 ，中心点的计算用所有点的平均来获取
	 {
	 for(i=0;i<k;i++)
		{total=0;
		 xx=0;
		 yy=0;
		for(j=1;j<=n;j++)
			{if(OBJ[j].clusterNo==i+bei)
				{xx+=OBJ[j].x;
				 yy+=OBJ[j].y;
				 total++;
				}
			}
		if(total!=0)
		{
		 CEN[i].x=xx/total;
		 CEN[i].y=yy/total;
		}
		else continue;
		}//更新每个簇的平均值
	}
	 ////////////////////
	 if(tag==1)                   ///使用k-平均，中心点的计算用最大减最小的方法获取
	 {  float minX,minY,maxX,maxY;
	for(i=0;i<k;i++)
		{	minX=2000;
			maxX=0;
			minY=2000;
			maxY=0;
		for(j=1;j<=n;j++)
		{
			if(OBJ[j].clusterNo==i+bei)
			{
				if(OBJ[j].x<minX)
					minX=OBJ[j].x;
				if(OBJ[j].x>maxX)
					maxX=OBJ[j].x;
				if(OBJ[j].y<minY)
					minY=OBJ[j].y;
				if(OBJ[j].y>maxY)
					maxY=OBJ[j].y;
			}
		}
	    CEN[i].x=minX+(maxX-minX)/2;
		CEN[i].y=minY+(maxY-minY)/2;
	}


	 }
	 ///////////////////////////
if(tag==2)                           /////使用k-中心点法
{   
	int A[1000];
	double E1,E2;             //E1用来存放原中心点的簇内代价函数值，
	                         //E2用来存放新中心点的簇内代价函数值
	for(i=0;i<1000;i++)
		{A[i]=0;
		}
	E1=0;E2=0;
	for(i=0;i<k;i++)
		for(j=1;j<=n;j++)
		{
		if(OBJ[j].clusterNo==i+bei)	
		E1+=pow(OBJ[j].x-CEN[i].x,2)+pow(OBJ[j].y-CEN[i].y,2);
		}
	int rnumber;
		rnumber=rand()%n+1;
		oo++;
	if(A[rnumber]==0)
	{
		TEMP=CEN[OBJ[rnumber].clusterNo%k];
	CEN[OBJ[rnumber].clusterNo%k]=OBJ[rnumber];
	for(i=0;i<k;i++)
		for(j=1;j<=n;j++)
		{if(OBJ[j].clusterNo==i+bei)	
		E2+=pow(OBJ[j].x-CEN[i].x,2)+pow(OBJ[j].y-CEN[i].y,2);
		}
	A[rnumber]=1;
	if(E2>E1)
	{
		CEN[OBJ[rnumber].clusterNo%k]=TEMP;
	}
	}
	if(oo==n){E=Ebk;}
	else {E=1;Ebk=2;}
}
	 ///////////////////////////
	if(tag==0||tag==1)
	{Ebk=E;
	E=0;
	for(i=0;i<k;i++)
		for(j=1;j<=n;j++)
		{if(OBJ[j].clusterNo==i+bei)	
		E+=pow(OBJ[j].x-CEN[i].x,2)+pow(OBJ[j].y-CEN[i].y,2);
		}//计算收敛函数	
	all_count++;
	}
}while(E!=Ebk);//知道不再发生变化

	bei++;
//	delete[] Min;
//	Min=NULL;
	return OBJ;
}