//////////////////////////////////////////////////////////////
/*程序作用：數據挖掘考試專用，聚類分析的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;
}