多维数据聚类.cpp

多维数据聚类多维数据聚类多维数据聚类多维数据聚类多维数据聚类多维数据聚类多维数据聚类多维数据聚类多维数据聚类多维数据聚类

//***********引入库函数

#include "iostream.h"
#include "math.h"
#include "stdlib.h"
#include "iomanip.h"
#include "time.h"
#include "fstream.h"

//*************定义常量

const int TRUE=1;
const int FALSE=0;

//************定义全局变量

int YangBenShuMu;               //聚类样本数目
int Weishu;                     //样本维数
int K;                          //分类数
double *DataSet;                //指向浮点型的指针
int WanCheng=0;                 //判断完成
int Row=3;                      




//**********类GETDATA  设定全局变量，维数，样本数，和类别数等

class GETDATA{

public:	      //类的各种方法
	GETDATA();
	void Display();   
	void Initial();  
	void Input();
    void chongxinshuruK();   

};

GETDATA::GETDATA()
{

} 

void GETDATA::Display()
{
	int i,j;	
}

//****************初始化数据，输入数据的属性

void GETDATA::Initial()
{

	char ch;	
	GETDATA::Display();
	cout<<endl<<"***********************针对处理多维数的k means 聚类算法 *********************** ";
	cout<<endl<<"                                                                             ";
 
		GETDATA::Input();
}


//**************** 输入待聚类数据的属性，包括维数，个数，类别数

void GETDATA::Input()
{
	char flag;
	int i,j;
	double s=0;

	cout<<endl<<" 请依次输入所要处理的数据的属性: 数据维数  数据数目  数据类别数"<<endl;
	cout<<endl<<" 数据维数: ";
	cin>>Weishu;
	cout<<endl<<" 数据数目: ";
	cin>>YangBenShuMu;
	cout<<endl<<"  分类数：";
	cin>>K;
	cout<<endl<<"***************************输入所要处理的数据********************************** "<<endl;
	cout<<endl<<"                                                                             ";
	delete[]DataSet;
	DataSet=new double[Weishu*YangBenShuMu];	

				for(i=0;i<YangBenShuMu;i++)
				{
					cout<<endl<<" 请输入第"<<i+1<<" 个数据的"<<Weishu<<" 个分量";

					for(j=0;j<Weishu;j++)

						cin>>DataSet[i*Weishu+j];
				}

}



void GETDATA::chongxinshuruK()  //如有需要，可重新输入K分类数，0则退出
{
	cout<<endl<<"-----重新输入K值------如果 k==0 ，推出 ！";
    cin>>K;
    if (K==0)
    exit(0);
    
}

//*********构建类kmeans ：根据设定的K,YangBenShuMu,Weishu等来实现聚类

class kmeans
{
public:
	struct DataType //数据类型
	{
	double *data;
	int father;
	double *uncle;
	};

	struct ClusterType//簇的类型
	{
	double *center;
	int sonnum;
	
	};

	kmeans();
	void Initialize();
	void KMeans();
	void DisPlay();
	void GetDataset(DataType *p1,double *p2,int YangBenShuMu,int dim);
	void GetValue(double *str1,double *str2,int dim);
	int  FindFather(double *p,int k);
	double SquareDistance(double *str1,double *str2,int dim);
	int	Compare(double *p1,double *p2,int dim);
	void NewCenterPlus(ClusterType *p1,int t,double *p2,int dim);
	void NewCenterReduce(ClusterType *p1,int t,double *p2,int dim);
	double Compare(DataType *p1,ClusterType *c1,DataType *p2,ClusterType *c2);

DataType *DataMember, *KResult,*CurrentStatus,*NewStatus;
ClusterType * ClusterMember,*NewCluster,*CurrentCluster;
	 
}; 



//************建立公共的构造函数Kmeans*******

kmeans::kmeans()
{	
	int i;

	DataMember=new DataType[YangBenShuMu];
	ClusterMember=new ClusterType[K];

	for(i=0;i<YangBenShuMu;i++)
	{
		DataMember[i].data=new double[Weishu];	
	
		DataMember[i].uncle=new double[K];
	}	

	for(i=0;i<K;i++)

		ClusterMember[i].center=new double[Weishu];

	    GetDataset(DataMember,DataSet,YangBenShuMu,Weishu);

			
}


//****************初始化参数*****

void kmeans::Initialize( )
{
		 
}

void kmeans::KMeans()
{
	
	int i,j,M=1;
	int pa,pb,fa;
	ClusterType *OldCluster;	

	//初始化聚类中心

	OldCluster=new ClusterType[K];

	for(i=0;i<K;i++)
	{
		GetValue(ClusterMember[i].center,DataMember[i].data,Weishu);
		ClusterMember[i].sonnum=1;

		OldCluster[i].center=new double[Weishu];
		GetValue(OldCluster[i].center,ClusterMember[i].center,Weishu);
	}


	for(i=0;i<YangBenShuMu;i++)  
	{
		for(j=0;j<K;j++)
		{
			DataMember[i].uncle[j]=SquareDistance(DataMember[i].data,ClusterMember[j].center,Weishu);
		}

		    pa=DataMember[i].father=FindFather(DataMember[i].uncle,K);

		if(i>=K)
		{
			ClusterMember[pa].sonnum+=1;

			NewCenterPlus(ClusterMember,pa,DataMember[i].data,Weishu);

			GetValue(OldCluster[pa].center,ClusterMember[pa].center,Weishu);
		} 
	}

	//开始聚类，直到聚类中心不再发生变化。

	while(!WanCheng)
	{
		//一次聚类循环：1.重新归类；2.修改类中心
		for(i=0;i<YangBenShuMu;i++)  
		{
			for(j=0;j<K;j++)
			{
				DataMember[i].uncle[j]=SquareDistance(DataMember[i].data,ClusterMember[j].center,Weishu);
			}
			
			    fa=DataMember[i].father;

		    if(fa!=FindFather(DataMember[i].uncle,K)&&ClusterMember[fa].sonnum>1)
			{

				pa=DataMember[i].father;
				ClusterMember[pa].sonnum-=1;

				pb=DataMember[i].father=FindFather(DataMember[i].uncle,K);
				ClusterMember[pb].sonnum+=1;

				NewCenterReduce(ClusterMember,pa,DataMember[i].data,Weishu);
				NewCenterPlus(ClusterMember,pb,DataMember[i].data,Weishu);
				
			}					

		}
			
		//判断聚类是否完成，WanCheng=1,停止聚类

        //若每个簇的收敛距离都小于给定的参数则结束类聚，否则继续迭代

		WanCheng=0;

		for(j=0;j<K;j++)

			if(Compare(OldCluster[j].center,ClusterMember[j].center,Weishu))

				break;

		if(j==K)

			WanCheng=1;

			
		for(j=0;j<K;j++)

			GetValue(OldCluster[j].center,ClusterMember[j].center,Weishu);
	
	}

}



 //************************************
 //        需要调用的函数          ****   
 //************************************


void kmeans::NewCenterPlus(ClusterType *p1,int t,double *p2,int dim)
{
	int i;
	for(i=0;i<dim;i++)
		p1[t].center[i]=p1[t].center[i]+(p2[i]-p1[t].center[i])/(p1[t].sonnum);
}


void kmeans::NewCenterReduce(ClusterType *p1,int t,double *p2,int dim)
{
	int i;
	for(i=0;i<dim;i++)
		p1[t].center[i]=p1[t].center[i]+(p1[t].center[i]-p2[i])/(p1[t].sonnum);
}


void kmeans::GetDataset(DataType *p1,double *p2,int YangBenShuMu,int dim)
{
	int i,j;
	for(i=0;i<YangBenShuMu;i++)
	{
		for(j=0;j<dim;j++)
			p1[i].data[j]=p2[i*dim+j];
	}
}

void kmeans::GetValue(double *str1,double *str2,int dim)
{
	int i;
	for(i=0;i<dim;i++)	
	str1[i]=str2[i];
}

int  kmeans::FindFather(double *p,int k)
{
	int i,N=0;
	double min=30000;
	for(i=0;i<k;i++)	
		if(p[i]<min)
		{
			min=p[i];
			N=i;
		}
	return N;
}

double kmeans::SquareDistance(double *str1,double *str2,int dim)
{
	double dis=0;
	int i;
	for(i=0;i<dim;i++)
		dis=dis+(double)(str1[i]-str2[i])*(str1[i]-str2[i]);
	return dis;
}

int	kmeans::Compare(double *p1,double *p2,int dim)
{
	int i;
	for(i=0;i<dim;i++)
		if(p1[i]!=p2[i])
			return 1;
	return 0;
}	



//************************************
//           显示聚类结果         ****   
//************************************



void kmeans::DisPlay()
{
	int i,N,j,t;
	ofstream  result("聚类过程结果显示.txt",ios::ate);
	for(i=0;i<K;i++)
	{
		N=0;
		cout<<endl<<endl<<"******************** 第 "<<i+1<<" 类样本:*******************"<<endl;
		result<<endl<<endl<<"******************** 第 "<<i+1<<" 类样本:*******************"<<endl;
		for(j=0;j<YangBenShuMu;j++)
			if(DataMember[j].father==i)
			{
				cout<<" [";
				for(t=0;t<Weishu;t++)
				cout<<" "<<setw(5)<<DataMember[j].data[t];
				cout<<" ]  ";				
				if((N+1)%Row==0)
					cout<<endl;

				result<<" [";
				for(t=0;t<Weishu;t++)
				result<<" "<<setw(5)<<DataMember[j].data[t];
				result<<" ]  ";				
				if((N+1)%Row==0)
					result<<endl;

				N=N+1;
			}
	}


  
	result.close();


	

}


//************************************
//            主函数入口          ****   
//************************************


void main()
{
	//用户输入数据
	srand((unsigned)time(NULL));
	GETDATA getdata;
	getdata.Initial();
	ofstream file("聚类过程结果显示.txt",ios::trunc);   //聚类结果存入“聚类结果显示.txt”文件

	//k-均值聚类方法聚类
	kmeans kmeans;   
	
	kmeans.KMeans(); //逐个样本聚类

	cout<<endl<<"****************************K-均值聚类结果：******************************";
    cout<<endl<<" ";
	file<<endl<<"****************************K-均值聚类结果：******************************"<<endl;

/*
	file.close();*/

     kmeans.DisPlay();   
/*
	chongxinshuruK();

    kmeans.KMeans(); //逐个样本聚类*/
    while (1)
    {
        getdata.chongxinshuruK() ;
	
        kmeans.KMeans();
        
	    cout<<endl<<"****************************K-均值聚类结果：******************************";
        cout<<endl<<" ";
    	file<<endl<<"****************************K-均值聚类结果：******************************"<<endl;
        kmeans.DisPlay();
    }

//	file.close();
	
   	kmeans.DisPlay();      
	cout<<endl<<"  ";
	cout<<endl<<"  ";
	cout<<endl<<"程序已经运行结束!"<<endl;
	cout<<endl<<"  ";	
    cout<<endl<<"聚类结果已经汇总在本程序文件夹“聚类过程结果显示.txt”内!"<<endl;
    file.close();
}