clustering.cpp

能计算用户输入的聚类

//////////////////////////////////////////////////////////////
/*程序作用：数据挖掘考试专用，聚类分析的K-平均算法          */
/*程序编写：黄 伟                                           */
/*编写日期：2008-4-24                                       */
//////////////////////////////////////////////////////////////
#include <stdlib.h>
#include<iostream>
#include<math.h>
using namespace std;

float **Temp,**Center;//Temp为状态矩阵，Center为中心坐标；
int Dimension,Num;    //Dimension为点的维数，Num为点的个数；
float *dis;           //dis为距离数组

//////////////////////////////////////////////////////////////
/*函数作用：两点a和b之间的距离                              */
/*函数输入：a,b两点，First和Second分别为点序号和所在聚分类号*/
/*函数返回：两点间的距离                                    */
//////////////////////////////////////////////////////////////
float Distance(float **a,float **b,int First,int Second)
{
	float t=0.0;
	for(int j=0;j<Dimension;j++)
			t+=(a[First][j]-b[Second][j])*(a[First][j]-b[Second][j]);
	t=sqrt(t);
	return t;
}


/////////////////////////////////////////////////////////////
/*函数作用：计算中心坐标                                   */
/*函数输入：a为待确定点，center为已确定的中心。id为聚分类号*/
/*函数返回：返回真值                                       */
/////////////////////////////////////////////////////////////
bool CenterCoord(float **a,float **center,int id)
{
	int count;
	for(int j=0;j<Dimension;j++)
		{
			count=0;
			for(int i=0;i<Num;i++)
				if(Temp[id][i]==1)//在ID簇类
				{	
					count++;
					center[id][j]+=a[i][j];	
				}
				center[id][j]/=count;
		}
		return true;
}


/////////////////////////////////////////////////////////////
/*函数作用：选取点c到最近聚分类的编号                      */
/*函数输入：c为待确定点，k为聚分类号                       */
/*函数返回：返回聚分类号                                   */
/////////////////////////////////////////////////////////////
int GetMin(float *c,int k)
{
	int ID=0;
	float Min=c[0];
	if (k==1)
		return k-1;
	else{
	
		for(int i=0;i<k;i++)
		{
			if(Min>c[i])
				Min=c[i];
		}
		for(i=0;i<k;i++)
		{
			if(Min==c[i])
			{
				ID=i;
				break;
			}
		}
		
	}    
	return ID;
}


////////////////////////////////////////////////////////////////
/*函数作用：判断中心坐标是否还在变化                          */
/*函数输入：center,LastCenter为两个中心坐标矩阵，k为聚分类层号*/        
/*函数返回：返回真值                                          */
////////////////////////////////////////////////////////////////
bool IsEqual(float **center,float **LastCenter,int k)
{
	
	for (int i=0;i<k;i++)
	{
		for (int j=0;j<Dimension;j++)
		{ 		  
			if(!(center[i][j]==LastCenter[i][j]))
				return false;
		}	 
	}
   return true;
}

int main(int agv,char*agc[])
{
	cout<<"*************************************************************"<<endl;
	cout<<"*                     欢迎使用本程序！                      *"<<endl;
	cout<<"*         本程序是数据挖掘中的聚类分析K-平均算法问题        *"<<endl;
	cout<<"*           程序由黄伟编写，学习交流QQ：283824505	    *"<<endl;	
	cout<<"*                       2008-4-24                           *"<<endl;
	cout<<"*************************************************************"<<endl;	
	//_COORD sr;
	//sr.X = 0;
	//sr.Y = 0; 
	//DWORD size; 
	//HANDLE wr = (HANDLE)GetStdHandle(STD_OUTPUT_HANDLE);
	//SetConsoleCursorPosition(wr, sr);
	//WriteConsole(wr, "", 0, &size, NULL);   //类似WriteFile
	//
	int i,j,K;
	float **Dot,**LastCenter;
	int *ID;	
	cout<<"请输入点的个数：";
	cin>>Num;
	cout<<"请输入点的维数:";
	cin>>Dimension;


	Dot=new float*[Num];
	for(i=0;i<Num;i++)
		Dot[i]=new float[Dimension];
	
	cout<<"=================输入点==================="<<endl;
	for(i=0;i<Num;i++)
		for(j=0;j<Dimension;j++)
			cin>>Dot[i][j];

	cout<<"输入K分聚类的K值：";
	cin>>K;
	ID=new int[K];
	dis=new float[K];//欧氏距离
	cout<<"输入预制中心点的编号(第一个点为0,依次往后推)："<<endl;

	for(i=0;i<K;i++)
	{
		cin>>ID[i];	
		dis[i]=0.0;
	}



	//状态矩阵
	Temp=new float*[K];  
	for(i=0;i<K;i++)
		Temp[i]=new float[Num];

	for(i=0;i<K;i++)
		for(j=0;j<Num;j++)
		{
			if(ID[i]==j)
				Temp[i][j]=1;
			else
				Temp[i][j]=0;
		}
        //中心坐标
		Center=new float *[K];
		for(i=0;i<K;i++)
			Center[i]=new float[Dimension];

       //临时中心坐标
		LastCenter=new float *[K];
		for(i=0;i<K;i++)
			LastCenter[i]=new float[Dimension];
       //临时中心坐标初始化
		for(i=0;i<K;i++)
			for(j=0;j<Dimension;j++)
			{
				LastCenter[i][j]=0.0;
			}

		
      
       //初始化,将选取的分类点赋给中心坐标
		for(i=0;i<K;i++)
			for(j=0;j<Num;j++)
			{
				if(Temp[i][j]==1)
				{
					for (int c=0;c<Dimension;c++)
					{
						Center[i][c]=Dot[j][c];
					}
				}				
			}
		
			int Times=1;      
			while (!IsEqual(Center,LastCenter,K))
			{
				cout<<"第"<<Times<<"次划分结果："<<endl;
				for (i=0;i<K;i++)
				 for (j=0;j<Dimension;j++)
				 {
					// printf("中心坐标C(%f,%f)=",Center[i][j]);
					std::cout<<"中心坐标C("<<i<<","<<j<<")="<<Center[i][j]<<endl;
				 }
				for (i=0;i<Num;i++)
				{
					for (j=0;j<K;j++)
					{
						dis[j]=Distance(Dot,Center,i,j);
					cout<<"||A"<<i<<"C"<<j<<"||="<<dis[j]<<endl;
					}
					int id=GetMin(dis,K);
					Temp[id][i]=1;
					for (j=0;j<K;j++)//去掉上一次所求的点所在聚类的标记				
						if (j!=id)
							Temp[j][i]=0;																
				}

				if(Times==1)
				{
					for(i=0;i<K;i++)					
						CenterCoord(Dot,LastCenter,i);

					for(i=0;i<K;i++)
						for (j=0;j<Dimension;j++)
						{
							Center[i][j]=LastCenter[i][j];
							LastCenter[i][j]=0.0;
						}                        
				}

				if (Times!=1)
				{
					for(i=0;i<K;i++)
						for (j=0;j<Dimension;j++)
						{
							LastCenter[i][j]=Center[i][j];
							Center[i][j]=0.0;
						}
					for (i=0;i<K;i++)
						CenterCoord(Dot,Center,i);
				}
				cout<<"第"<<Times<<"次划分结果为："<<endl;
				for(i=0;i<K;i++)
					for(j=0;j<Num;j++)
					{
						cout<<Temp[i][j]<<" ";
						if ((j+1)/Num==1)
							cout<<endl;							
					}
					cout<<endl;
				Times++;
			}	
			cout<<"总共计算的次数为："<<Times-1<<endl;
			cout<<"计算完成！"<<endl;		



			delete LastCenter;
			delete Center;
			delete Temp;
			delete Dot;
			getchar();
			getchar();
			return true;
}