clustering.cpp

模式识别分级聚类算法

#include<math.h>
#include<iostream.h>
#include <stdio.h>
#include <stdlib.h>
#define min(x,y) (x)<(y) ? (x) : (y)
#define max(x,y)   (x)>(y)?(x):(y)
struct vector
{
	//定义结构体，放二维数组，指针为了使在同一类里的元素连起来
	double a;
	double b;
	struct vector *next;
};
double listdis(struct vector list0,struct vector list1)
{
	//定义两个结构体的距离，指针和数组的距离标准相同，方法不同。
	double distance;
	distance=sqrt(pow((list0.a-list1.a),2)+pow((list0.b-list1.b),2));
	return distance;
}
double listdis(struct vector *list0,struct vector list1)
{
	double distance;
	distance=sqrt(pow((list0->a-list1.a),2)+pow((list0->b-list1.b),2));
	return distance;
}
double listdis(struct vector *list0,struct vector *list1)
{
	double distance;
	distance=sqrt(pow((list0->a-list1->a),2)+pow((list0->b-list1->b),2));
	return distance;
}
double maxormin(double dis1,double dis2,int cho)
{
	//根据cho选择最小距离和最大距离方法，均值距离另外定义。
	double dis;
	if (cho==1)
	{
		dis=min(dis1,dis2);
	}
	else if (cho==2)
	{
		dis=max(dis1,dis2);
	}
	return dis;
}
void main()
{
	int n;
	n=8;//向量元素个数
	struct vector *list;//存放向量元素结构体动态数组
	struct vector listtemp1,listtemp11;
	struct vector *listtemp2,*listtemp3;
	list=new struct vector[n];
	int i,j,p,q,cho;
	for (i=0;i<n;i++)
	{
		list[i].next=NULL;
	}
	list[0].a=2;
	list[0].b=2;
	list[1].a=2;
	list[1].b=3;
	list[2].a=1;
	list[2].b=2;
	list[3].a=2;
	list[3].b=1;
	list[4].a=-2;
	list[4].b=-2;
	list[5].a=-3;
	list[5].b=-2;
	list[6].a=-1;
	list[6].b=-2;
	list[7].a=-2;
	list[7].b=-3;
	int *classnum,*classnumnum;
	classnum=new int[n];//合并一类则使另外一个元素置为－1，下次分类时跳过它。
	classnumnum=new int[n];//使同一类的标号串联起来
	for (i=0;i<n;i++)
	{
		classnum[i]=i;
		classnumnum[i]=0;
	}
	int mark1,mark2;//标记类里的元素的标号
	double dis1,dis2,dis3,dis4;//计算距离
	dis1=0;//存储分类过程中类间最小距离
	int temp;
	int jishu,jishu1;//计算均值距离时类元素个数
	/**界面提示语句**************/
	cout<<"please select the clustering method:"<<'\n'
		<<"1 min distance"<<'\n'
		<<"2 max distance"<<'\n'
		<<"3 mean distance"<<'\n'
		<<"your choice";
	cin>>cho;
	if ((cho!=1)&&(cho!=2)&(cho!=3))
	{
		cout<<"error choice! input again!"<<'\n';
		cin>>cho;
	}
	int classnum11=n;//类数
	while (classnum11!=2)
	{
		for (i=0;i<n;i++)//第i类与第j类比较
		{
			mark1=classnum[i];
			if (mark1==-1)
			{
				continue;
			}
			for (j=i+1;j<n;j++)
			{	
				mark2=classnum[j];
				if (mark2==-1)
				{
					continue;
				}
				if ((list[mark1].next==NULL)&&(list[mark2].next==NULL))
				{
					dis2=listdis(list[mark1],list[mark2]);
					if (dis1==0)
					{
						dis1=dis2;
						p=i;
						q=j;
					}
					else
					{
						//求最小的一个距离
						if(dis2<dis1) 
						{
							dis1=dis2;
							p=i;
							q=j;
							
						}
						
					}
				}
				else if ((list[mark1].next!=NULL)&&(list[mark2].next==NULL))
				{
					if (cho==3)
					{
						jishu=1;
						listtemp1=list[mark1];
						listtemp2=list[mark1].next;
						while (listtemp2!=NULL)
						{
							listtemp1.a+=listtemp2->a;
							listtemp1.b+=listtemp2->b;
							listtemp2=listtemp2->next;
							jishu++;
						}
						listtemp1.a=listtemp1.a/jishu;
						listtemp1.b=listtemp1.b/jishu;
						dis2=listdis(listtemp1,list[mark2]);
						if (dis1==0)
						{
							dis1=dis2;
							p=i;
							q=j;
						}
						if(dis2<dis1) 
						{
							dis1=dis2;
							p=i;
							q=j;
							
						}
					}
					else
					{
						listtemp2=&list[mark1];
						dis3=listdis(listtemp2,list[mark2]);
						while ((listtemp2->next)!=NULL)
						{
							dis4=listdis((listtemp2->next),list[mark2]);
							dis2=maxormin(dis3,dis4,cho);
							dis3=dis2;
							listtemp2=listtemp2->next;
						}
						if (dis1==0)
						{
							dis1=dis2;
							p=i;
							q=j;
						}
						if(dis2<dis1) 
						{
							dis1=dis2;
							p=i;
							q=j;
							
						}
						
					}
				}
				else if ((list[mark1].next==NULL)&&(list[mark2].next!=NULL))
				{
					if (cho==3)
					{
						jishu=1;
						listtemp1=list[mark2];
						listtemp2=list[mark2].next;
						while (listtemp2!=NULL)
						{
							listtemp1.a+=listtemp2->a;
							listtemp1.b+=listtemp2->b;
							listtemp2=listtemp2->next;
							jishu++;
						}
						listtemp1.a=listtemp1.a/jishu;
						listtemp1.b=listtemp1.b/jishu;
						dis2=listdis(listtemp1,list[mark1]);
						if (dis1==0)
						{
							dis1=dis2;
							p=i;
							q=j;
						}
						if(dis2<dis1) 
						{
							dis1=dis2;
							p=i;
							q=j;
							
						}
					}
					else
					{
						listtemp2=&list[mark2];
						dis3=listdis(listtemp2,list[mark1]);
						while ((listtemp2->next)!=NULL)
						{
							dis4=listdis((listtemp2->next),list[mark1]);
							dis2=maxormin(dis3,dis4,cho);
							dis3=dis2;
							listtemp2=listtemp2->next;
						}
						if (dis1==0)
						{
							dis1=dis2;
							p=i;
							q=j;
						}
						if(dis2<dis1) 
						{
							dis1=dis2;
							p=i;
							q=j;
							
						}
					}
					
				}
				else if ((list[mark1].next!=NULL)&&(list[mark2].next!=NULL))
				{
					if (cho==3)
					{
						jishu=1;
						jishu1=1;
						listtemp1=list[mark1];
						listtemp11=list[mark2];
						listtemp2=listtemp1.next;
						while (listtemp2!=NULL)
						{
							listtemp1.a+=listtemp2->a;
							listtemp1.b+=listtemp2->b;
							listtemp2=listtemp2->next;
							jishu++;
						}
						listtemp1.a=listtemp1.a/jishu;
						listtemp1.b=listtemp1.b/jishu;
						listtemp2=listtemp11.next;
						while (listtemp2!=NULL)
						{
							listtemp11.a+=listtemp2->a;
							listtemp11.b+=listtemp2->b;
							listtemp2=listtemp2->next;
							jishu1++;
						}
						listtemp11.a=listtemp11.a/jishu;
						listtemp11.b=listtemp11.b/jishu;
						dis2=listdis(listtemp1,listtemp11);
						if (dis1==0)
						{
							dis1=dis2;
							p=i;
							q=j;
						}
						if(dis2<dis1) 
						{
							dis1=dis2;
							p=i;
							q=j;
							
						}
					}
					else
					{
						dis2=0;
						listtemp2=&list[mark1];
						listtemp3=&list[mark2];
						while (listtemp2!=NULL)
						{
							dis3=listdis(listtemp2,listtemp3);
							if (dis2!=0)
							{
								dis3=maxormin(dis2,dis3,cho);
							}
							while ((listtemp3->next)!=NULL)
							{	
								dis4=listdis(listtemp2,listtemp3->next);
								dis2=maxormin(dis3,dis4,cho);
								dis3=dis2;
								listtemp3=listtemp3->next;
							}
							listtemp3=&list[mark2];
							listtemp2=listtemp2->next;		
						}
						if (dis1==0)
						{
							dis1=dis2;
							p=i;
							q=j;
						}
						if(dis2<dis1) 
						{
							dis1=dis2;
							p=i;
							q=j;
							
						}
					}
				}	
			}	
			
		}
		if (list[p].next==NULL)
		{
			list[p].next=&list[q];
			classnumnum[p]=q;		
		}
		else
		{
			listtemp3=list[p].next;
			temp=p;
			while (listtemp3!=NULL)
			{	
				temp=classnumnum[temp];
				listtemp3=listtemp3->next;
			}
			list[temp].next=&list[q];
			classnumnum[temp]=q;		
		}
		classnum[q]=-1;
		classnum11--;
		dis1=0;
}
for (i=0;i<n;i++)
{
	if (classnum[i]!=-1)
	{
		cout<<'\n'<<"每一类的元素："<<'\n';
		listtemp3=&list[i];
		while (listtemp3!=NULL)
		{
			cout<<listtemp3->a<<" "<<listtemp3->b<<'\n';
			listtemp3=listtemp3->next;
		}		
	}
}
delete []list;
delete []classnum;
delete []classnumnum;

}