cluster.cpp

用ＶＩＳＵＡＬC++编写的聚类分析程序,图像识别.(各种算法),具有非常大的价值.

		{
			return -1;
		}

		return (1-result);
	}
	else if (distype==4)//Tanimoto
	{
		int *t1,*t2;
		int a,b1,b2;
		 
		a=0;b1=0;b2=0;
		t1=new int [N*N];
		t2=new int [N*N];
		for(int i=0; i<N*N; i++)
		{
			t1[i]=mCenter1.feature[i]>0.2? 1:0;
			t2[i]=mCenter2.feature[i]>0.2? 1:0;
		}
		
		for ( i=0; i<N*N; i++)
		{
			a+=t1[i]*t2[i];
			b1+=t1[i]*t1[i];
			b2+=t2[i]*t2[i];
		}
		delete	[]t1;
		delete	[]t2;
		if ((b2*b1-a)!=0)
		result=(double)(a/(b1+b2-a));
		else 
		{
			return -1;
		}
		return (1-result);
	}
	else
		return -1;	
}

/************************************************************
*函数名称		GetDistance(double *dis, int i, int j)
*参数			double *dis    指向模糊距离数组的指针大小为[patternnum*patternnum]
*				int i			数组的第i行
*				int j			数组的第j列
*返回值		    double
*函数功能		返回模糊距离数组中第i行第j列的模糊积
*************************************************************/
double CCluster::GetDistance(double *dis, int i, int j)
{
	double result;
	result=0;

	for(int t=0;t<patternnum;t++)
	{
		double td=dis[i*patternnum+t]<dis[t*patternnum+j]? dis[i*patternnum+t]:dis[t*patternnum+j];
		if (result<td)
			result=td;
	}
	return result;
}
/************************************************************
*函数名称		GetFuzzyDistance(CCluster::Pattern pattern1,CCluster::Pattern pattenr2, int distype)
*参数			CCluster::Pattern pattern1    样品1
*				CCluster::Pattern pattern2    样品2
*				int distype					  距离计算形式：1，欧氏距离；2，数量积；
*															3，相关系数
*															4，最大最小法；5，算数平均法; 
*															6,几何平均最小法
*返回值         double
*功能			计算两个样品的模糊距离，距离模式由参数distype给出
************************************************************/
double CCluster::GetFuzzyDistance(CCluster::Pattern pattern1,CCluster::Pattern pattern2, int distype)
{
	switch	(distype)
	{
	case 1://欧氏距离
		{
				double max=0;
				for (int i=0; i<patternnum-1; i++)
					for (int j=i+1; j<patternnum; j++)
						if (max<GetDistance(m_pattern[i],m_pattern[j],1))
							max=GetDistance(m_pattern[i],m_pattern[j],1);
				return (max-GetDistance(pattern1,pattern2,1))/max;
		}
	case 2://数量积
		{
			double temp,max;
			max=0;
			for (int i=0; i<patternnum-1; i++)
				for (int j=0; j<patternnum; j++)
				{
					temp=0;
					for (int k=0; k<N*N; k++)
					{
						temp+=m_pattern[i].feature[k]*m_pattern[j].feature[k];
					}
					if (max<temp)
						max=temp;
				}
			temp=0;
			for ( i=0; i<N*N; i++)
			{
				temp+=pattern1.feature[i]*pattern2.feature[i];
			}
			return (temp/max);
		}
	case 3://相关系数
		{
			double ap1,ap2;
			ap1=0;ap2=0;
			for (int i=0; i<N*N; i++)
			{
				ap1+=pattern1.feature[i];
				ap2+=pattern2.feature[i];
			}
			ap1/=N; 
			ap1/=N;

			double a,b1,b2;
			a=0;b1=0;b2=0;

			for (i=0; i<N*N; i++)
			{
				a+=(pattern1.feature[i]-ap1)*(pattern2.feature[i]-ap2);
				b1+=(pattern1.feature[i]-ap1)*(pattern1.feature[i]-ap1);
				b2+=(pattern2.feature[i]-ap2)*(pattern2.feature[i]-ap2);
			}
			if (b2*b1!=0)
				return (a/sqrt(b1*b2));
		}
	case 4://最大最小法
		{
			double min ,max;
			min=0; max=0;
			for (int i=0; i<N*N; i++)
			{
				min+=pattern1.feature[i]<pattern2.feature[i]? pattern1.feature[i]:pattern2.feature[i];
				max+=pattern1.feature[i]<pattern2.feature[i]? pattern2.feature[i]:pattern1.feature[i];
			}
			if (max!=0)
			return (min/max);
		}
	case 5://算数平均法
		{
			double min ,max;
			min=0; max=0;
			for (int i=0; i<N*N; i++)
			{
				min+=pattern1.feature[i]<pattern2.feature[i]? pattern1.feature[i]:pattern2.feature[i];
				max+=pattern1.feature[i]+pattern2.feature[i];
			}
			if (max!=0)
			return (2*min/max);	
		}
	case 6://几何平均最小法
		{
			double min ,max;
			min=0; max=0;
			for (int i=0; i<N*N; i++)
			{
				min+=pattern1.feature[i]<pattern2.feature[i]? pattern1.feature[i]:pattern2.feature[i];
				max+=sqrt(pattern1.feature[i]*pattern2.feature[i]);
			}
			if (max!=0)
			return (min/max);			
		}
	default:
		return -1;
	}
}

/************************************************************
*函数名称		Zuilinjinguize()
*参数			void
*返回值		    void
*函数功能		按照最临近规则对全体样品进行分类
************************************************************/
void CCluster::Zuilinjinguize()//最临近规则
{
	GetFeature();

	double  T;//阈值
	int		distype;//距离模式（欧氏、余弦。。。）
	int     i,j;

///////////////输出阈值参考值/////////////////////
	double minous,maxous,mincos,maxcos,minbcos,maxbcos,mintan,maxtan;

	minous=MAX; mincos=MAX; minbcos=MAX; mintan=MAX;
	maxous=0; maxcos=0; maxbcos=0; maxtan=0;

	for (  i=0;i<patternnum-1;i++)//计算四种距离模式的参考值
		for ( j=i+1;j<patternnum;j++)
		{
			if (minous>GetDistance(m_pattern[i],m_pattern[j],1))
				minous=GetDistance(m_pattern[i],m_pattern[j],1);
			if (maxous<GetDistance(m_pattern[i],m_pattern[j],1))
				maxous=GetDistance(m_pattern[i],m_pattern[j],1);

			if (mincos>GetDistance(m_pattern[i],m_pattern[j],2))
				mincos=GetDistance(m_pattern[i],m_pattern[j],2);
			if (maxcos<GetDistance(m_pattern[i],m_pattern[j],2))
				maxcos=GetDistance(m_pattern[i],m_pattern[j],2);

			if (minbcos>GetDistance(m_pattern[i],m_pattern[j],3))
				minbcos=GetDistance(m_pattern[i],m_pattern[j],3);
			if (maxbcos<GetDistance(m_pattern[i],m_pattern[j],3))
				maxbcos=GetDistance(m_pattern[i],m_pattern[j],3);
			
			if (mintan>GetDistance(m_pattern[i],m_pattern[j],4))
				mintan=GetDistance(m_pattern[i],m_pattern[j],4);
			if (maxtan<GetDistance(m_pattern[i],m_pattern[j],4))
				maxtan=GetDistance(m_pattern[i],m_pattern[j],4);
		}
	DlgInfor mDlgInfor;
	mDlgInfor.ShowInfor(minous,maxous,mincos,maxcos,minbcos,maxbcos,mintan,maxtan);

////////////////////////读入阈值和距离形式///////////////
	if (mDlgInfor.DoModal()==IDOK)
	{
		T=mDlgInfor.m_T;
		distype=mDlgInfor.m_DisType;
	}
	else return;
	centernum=1;
	m_center=new Center[patternnum];

    //将第一个样品作为第一个中心
	for ( i=0;i<N*N;i++)
		m_center[0].feature[i]=m_pattern[0].feature[i];
	m_center[0].index=1;
	m_center[0].patternnum=1;
	m_pattern[0].category=1;

	for ( i=1;i<patternnum;i++)//对所有模版进行归类
	{
		double centerdistance=MAX;
		int index=1;
		//找到距离最近的中心index，记录最小距离centerdistance
		for (int j=0;j<centernum;j++)
		{	
			double dis= GetDistance(m_pattern[i],m_center[j],distype);
			if (dis<centerdistance)
			{
				centerdistance=dis;
				index=j;
			}
		}

		if (centerdistance<T)//距离小于阈值则将样品归入该类
		{
			m_pattern[i].category=m_center[index].index;
			CalCenter(&m_center[j]);
		}
		else //新建聚类中心
		{
			centernum++;
			m_pattern[i].category=centernum;
			for (int m=0;m<N*N;m++)
				m_center[centernum-1].feature[m]=m_pattern[i].feature[m];
			m_center[centernum-1].index=centernum;
		}
	}//end of all pattern
	delete []m_center;
}


/************************************************************
*函数名称		Zuidazuixiaojulifa()
*参数			void
*返回值		void
*函数功能		按照最大最小距离规则对全体样品进行分类
************************************************************/
void CCluster::Zuidazuixiaojulifa()
{
	GetFeature();

	int	distype;//距离的形式（欧氏、余弦。。。）
	int i,j;

	DlgInfor mDlgInfor;
	mDlgInfor.ShowInfor(1);
	if (mDlgInfor.DoModal()==IDOK)
	{
		distype=mDlgInfor.m_DisType;
	}
	else return;
	
	double maxdistance=0;//记录两类间的最大距离，用做类分割阈值

	int index=1;//记录距离第一个中心最远的样品

	m_center=new Center[patternnum];

	for ( i=0;i<N*N;i++)//第一个聚类中心
		m_center[0].feature[i]=m_pattern[0].feature[i];
	m_center[0].index=1;
	m_pattern[0].category=1;

	for( i=1;i<patternnum;i++)//第二个聚类中心
		if (maxdistance<GetDistance(m_pattern[i],m_center[0],distype))
		{
			maxdistance=GetDistance(m_pattern[i],m_center[0],distype);
			index=i;
		}
	for ( i=0;i<N*N;i++)//第二个聚类中心
		m_center[1].feature[i]=m_pattern[index].feature[i];
	
	m_center[1].index=2;
	m_pattern[index].category=2;

	centernum=2;

	for ( i=1;i<patternnum;i++)//对所有模板分类
	{
		
		double tdistance=MAX;
		index=0;//记录样品距离最近的中心
		for ( j=0;j<centernum;j++)//2
			if (tdistance>GetDistance(m_pattern[i],m_center[j],distype))
			{
				tdistance=GetDistance(m_pattern[i],m_center[j],distype);
				index=j;
			}

		if (tdistance>maxdistance/2)//样品到最近中的距离大于阈值，建立新的聚类中心
		{
				++centernum;
				for (int m=0;m<N*N;m++)
					m_center[centernum-1].feature[m]=m_pattern[i].feature[m];
				m_center[centernum-1].index=centernum;
				m_pattern[i].category=centernum;
		}
		else//归入index类中
		{
			m_pattern[i].category=m_center[index].index;
			CalCenter(&m_center[index]);
		}
			
	}
	delete []m_center;

}
/************************************************************
*函数名称		Zuiduanjulifa()
*参数			void
*返回值 		void
*函数功能		按照最短距离法对全体样品进行分类
************************************************************/
void CCluster::Zuiduanjulifa()//最短距离法
{
	GetFeature();

	double  T;//阈值
	int		distype;//距离的形式（欧氏、余弦。。。）
	int     i,j;

	double minous,maxous,mincos,maxcos,minbcos,maxbcos,mintan,maxtan;

	minous=MAX; mincos=MAX; minbcos=MAX; mintan=MAX;
	maxous=0; maxcos=0; maxbcos=0; maxtan=0;
	//计算四种距离模式的参考值
	for (  i=0;i<patternnum-1;i++)
		for ( j=i+1;j<patternnum;j++)
		{
			if (minous>GetDistance(m_pattern[i],m_pattern[j],1))
				minous=GetDistance(m_pattern[i],m_pattern[j],1);
			if (maxous<GetDistance(m_pattern[i],m_pattern[j],1))
				maxous=GetDistance(m_pattern[i],m_pattern[j],1);

			if (mincos>GetDistance(m_pattern[i],m_pattern[j],2))
				mincos=GetDistance(m_pattern[i],m_pattern[j],2);
			if (maxcos<GetDistance(m_pattern[i],m_pattern[j],2))
				maxcos=GetDistance(m_pattern[i],m_pattern[j],2);

			if (minbcos>GetDistance(m_pattern[i],m_pattern[j],3))
				minbcos=GetDistance(m_pattern[i],m_pattern[j],3);
			if (maxbcos<GetDistance(m_pattern[i],m_pattern[j],3))
				maxbcos=GetDistance(m_pattern[i],m_pattern[j],3);
			
			if (mintan>GetDistance(m_pattern[i],m_pattern[j],4))
				mintan=GetDistance(m_pattern[i],m_pattern[j],4);
			if (maxtan<GetDistance(m_pattern[i],m_pattern[j],4))
				maxtan=GetDistance(m_pattern[i],m_pattern[j],4);
		}
	DlgInfor mDlgInfor;
	mDlgInfor.ShowInfor(minous,maxous,mincos,maxcos,minbcos,maxbcos,mintan,maxtan);

	if (mDlgInfor.DoModal()==IDOK)
	{
		T=mDlgInfor.m_T;
		distype=mDlgInfor.m_DisType;
	}
	else return;

    //初始化，所有样品各分一类 
	centernum=patternnum;
	m_center=new Center[centernum];
	for ( i=0;i<patternnum;i++)
	{
		m_pattern[i].category=i+1;

		for (j=0;j<N*N;j++)
			m_center[i].feature[j]=m_pattern[i].feature[j];
		m_center[i].index=i+1;
	}

	while (1)
	{
		int pi,pj;
		double mindis;

		pi=0;
		pj=0;
		mindis=MAX;
		//寻找距离最近的两类pi、pj，记录最小距离mindis
		for ( i=0;i<patternnum-1;i++)
			for ( j=i+1;j<patternnum;j++)
				if (m_pattern[i].category!=m_pattern[j].category)
					if (GetDistance(m_pattern[i],m_pattern[j],distype)<mindis)
					{
						mindis=GetDistance(m_pattern[i],m_pattern[j],distype);
						pi=i;
						pj=j;
					};
		if (mindis<=T)//距离小于阈值，合并pi、pj类
		{
			if (pi>pj)//将较大类号归入较小类号
			{
				int temp=pi;
				pi=pj;
				pj=temp;
			}
			int tcenter=m_pattern[pj].category;
			for ( i=0;i<patternnum;i++)
			{
				if (m_pattern[i].category==tcenter)
					m_pattern[i].category=m_pattern[pi].category;
				if (m_pattern[i].category>tcenter)//保持序号的连续性
					m_pattern[i].category--;
			}
		}
		else break;//最小距离大于阈值，退出循环
	}
	delete []m_center;

}
/************************************************************
*函数名称		Zuichangjulifa()
*参数			void
*返回值		    void
*函数功能		按照最长距离法对全体样品进行分类
************************************************************/
void CCluster::Zuichangjulifa()//最长距离法
{
	GetFeature();

	double  T;//阈值
	int		distype;//距离的形式（欧氏、余弦。。。）
	int     i,j;

	double minous,maxous,mincos,maxcos,minbcos,maxbcos,mintan,maxtan;

	minous=MAX; mincos=MAX; minbcos=MAX; mintan=MAX;
	maxous=0; maxcos=0; maxbcos=0; maxtan=0;
	//计算四种距离模式的参考值
	for (  i=0;i<patternnum-1;i++)
		for ( j=i+1;j<patternnum;j++)
		{
			if (minous>GetDistance(m_pattern[i],m_pattern[j],1))
				minous=GetDistance(m_pattern[i],m_pattern[j],1);
			if (maxous<GetDistance(m_pattern[i],m_pattern[j],1))
				maxous=GetDistance(m_pattern[i],m_pattern[j],1);

			if (mincos>GetDistance(m_pattern[i],m_pattern[j],2))
				mincos=GetDistance(m_pattern[i],m_pattern[j],2);
			if (maxcos<GetDistance(m_pattern[i],m_pattern[j],2))
				maxcos=GetDistance(m_pattern[i],m_pattern[j],2);

			if (minbcos>GetDistance(m_pattern[i],m_pattern[j],3))
				minbcos=GetDistance(m_pattern[i],m_pattern[j],3);
			if (maxbcos<GetDistance(m_pattern[i],m_pattern[j],3))
				maxbcos=GetDistance(m_pattern[i],m_pattern[j],3);
			
			if (mintan>GetDistance(m_pattern[i],m_pattern[j],4))
				mintan=GetDistance(m_pattern[i],m_pattern[j],4);
			if (maxtan<GetDistance(m_pattern[i],m_pattern[j],4))
				maxtan=GetDistance(m_pattern[i],m_pattern[j],4);
		}
	DlgInfor mDlgInfor;
	mDlgInfor.ShowInfor(minous,maxous,mincos,maxcos,minbcos,maxbcos,mintan,maxtan);

	if (mDlgInfor.DoModal()==IDOK)
	{
		T=mDlgInfor.m_T;
		distype=mDlgInfor.m_DisType;
	}
	else return;

    //初始化，所有样品各归一类
	for ( i=0;i<patternnum;i++)
	{
		m_pattern[i].category=i+1;
	}
 
	centernum=patternnum;

	while (1)
	{
		int pi,pj;
		double mindis,maxdis;

		pi=0;
		pj=0;
		mindis=MAX;
        //求两类间的最大距离，找出所有类间距离中最小的为mindis，记录类号pi，pj
		for ( i=1;i<=centernum-1;i++)
			for ( j=i+1;j<=centernum;j++)
			{
   				maxdis=-1;
				for (int m=0;m<patternnum-1;m++)
					for (int n=m+1;n<patternnum;n++)
					{
						if ((m_pattern[m].category==i)&&(m_pattern[n].category==j)||((m_pattern[m].category==j)&&(m_pattern[n].category==i)))
							if (GetDistance(m_pattern[m],m_pattern[n],distype)>maxdis)
							{
								maxdis=GetDistance(m_pattern[m],m_pattern[n],distype);
							}
					}
				if ((maxdis<mindis)&&(maxdis!=-1))
				{
					mindis=maxdis;
					pi=i;
					pj=j;
				}
			}
		if (mindis<T)//距离小于阈值，合并pi、pj类
		{
			int tcenter=pj;
			for ( i=0;i<patternnum;i++)
			{
				if (m_pattern[i].category==tcenter)
					m_pattern[i].category=pi;
				if (m_pattern[i].category>tcenter)//对样品排序，保持类号的连续性
					m_pattern[i].category--;
			}
			centernum--;