algorithm.cpp

模式识别二维链表实现isodata算法 早期试验

// Algorithm.cpp: implementation of the CAlgorithm class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Algorithm.h"
#include "iostream.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"




//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CAlgorithm::CAlgorithm()
{
	srand(time(NULL));


}

CAlgorithm::~CAlgorithm()
{

}


int CAlgorithm::Step1()//参数设置、模式输入、随机产生初始分类
{
//	ParaSet();
//	PatternInput();
	int i;
	for(i=1;i<=Nc;i++)
	{
		AddNullCluster();
		AddPatToClus(SelectPattern(Random(UnClusPatNum)),GetClusPointer(i));
		
		
	}
	for(i=1;i<=ClusNum;i++)
			CalClusCent(GetClusPointer(i));
	return 0;	
}

int CAlgorithm::Step2()//根据模式与每个类之间的距离,将其加入距离最小的一个类
{
	int minpos;
	double temp1=0,temp2=10000000;
	PATTERN_S *p;
	//计算模式与每个类之间的距离,将其加入距离最小的一个类
		while (UnClusPatNum!=0)
		{
			minpos=1;
			temp1=0;
			temp2=10000000;

			p=SelectPattern(1);
			for(int i=1;i<=ClusNum;i++)
			{
				
				temp1=CalPatClusCentDis(p,GetClusPointer(i));
				
				if(temp2>temp1)
				{
					temp2=temp1;
					minpos=i;
				}
				
			}
			AddPatToClus(p,GetClusPointer(minpos));
		}


	return 0;
}

int CAlgorithm::Step3()//如果类太小,合并并返回第二步
{
	int i;
	int del=0;
	int temp=ClusNum;
	for(i=1;i<=temp;i++)
	{
		if(GetClusPointer(i)==NULL)
			break;

		if(CountPattern(GetClusPointer(i)->pPat)<Thn)
		{
			DeleteCluster(i);
			del=1;
		}
	}
	if(del==0)
		return 0;
	else
		return 2;

}
int CAlgorithm::Step4()//计算类心、模式类心平均距离
{

	int i;
	for(i=1;i<=ClusNum;i++)
	{	
		CalClusCent(GetClusPointer(i));
		CalPatCentMeanDis(GetClusPointer(i));
	}
	CalTotalMeanDis();

		

	return 0;
}

int CAlgorithm::Step5()//根据类的数量判断是交分裂处理还是交给合并处理
{	
	if(Ip==I)
	{
		ThD=0;
		return 9;
	}
	if(ClusNum<=c/2)
		return 6;
	if(ClusNum>=2*c)
		return 9;
	if((ClusNum>c/2)&&(ClusNum<2*c))
	{
		if((int)c%2==0)return 9;
		if((int)c%2==1)return 6;
	}
	return 0;
}

int CAlgorithm::Step6_7()//计算类内距离的标准差矢量的最大值
{
	int i;
	for(i=1;i<=ClusNum;i++)
	{	
		CalClusMaxBiaozhuncha(GetClusPointer(i));//计算类内距离的标准差矢量的最大值
	}

	return 0;
}


int CAlgorithm::Step8()//根据类内距离的标准差矢量的最大值判断是否分裂并分裂
{	
	CLUSTER_S *pTemp;
	int i;
	int sepornot=0;
	for(i=1;i<=ClusNum;i++)
	{
		pTemp=GetClusPointer(i);
		if(pTemp->MaxBiaozhuncha>Ths&&((pTemp->PatCentMeanDis>TotalMeanDis&&CountPattern(pTemp->pPat)>2*(Thn+1))||ClusNum<=c/2))
		{
			SeperateCluster(pTemp);
			sepornot=1;
		}
		
	}
	if(sepornot==1)
	{
		Ip++;
		return 2;
	}

		return 0;
}

int CAlgorithm::Step9_10()//根据类心间距离判断是否合并并合并
{
	int i,j;
	int time=0;
	double temp1,temp2;
	int pos1=0,pos2=0;
	do
	{
		temp1=0;
		temp2=9999999999;
	for(i=1;i<ClusNum;i++)
		for(j=i+1;j<=ClusNum;j++)
		{
			if(GetClusPointer(i)->CombineOrNot==0&&GetClusPointer(j)->CombineOrNot==0)
			{
				temp1=CalClusCentDis(i,j);
				if(temp1<temp2)
				{
					temp2=temp1;
					pos1=i;
					pos2=j;
				}
			}
		}
		if(temp2<ThD)
		{
			CombineCluster(pos1,pos2);
			time++;
		}
	}
	while(temp2<ThD&&time<L);
	for(i=1;i<=ClusNum;i++)
		GetClusPointer(i)->CombineOrNot=0;
	return 0;
}


int CAlgorithm::Step11()//判断是否继续迭代或结束
{	
	if(Ip==I)
		return 0;
	else 
	{
		Ip++;
		return 2;
	}

}

int CAlgorithm::ParaSet()
{
	c=4;//预期的类数
	Nc=10;//初始聚类中心个数
	Thn=3;//每一类中允许的最小模式数目
	Ths=10;//类内各个分量分布的标准差上限
	ThD=10;//两类中心之间的最小距离下限
	L=2;//在每次迭代中可以合并的类的最多对数
	I=4;//允许的最多迭代次数
	k=0.5;//类分裂时用的系数k



	PatNum=20;//设定模式的个数
	PatDim=2;//设定模式的维数



	UnClusPatNum=0;
	ClusNum=0;
	Ip=0;//实际迭代的次数

	pPattern=NULL;
	pCluster=NULL;


	return 0;

}

int CAlgorithm::PatternInput()//读入模式数据
{	
	PATTERN_S *pTemp;
	PATTERN_S *pEnd;
	

	int i,j;
	
	cout<<"模式的个数为:"<<PatNum;
	cout<<"模式的维数为:"<<PatDim<<endl;
	cout<<"请输入模式数据:"<<endl;

	
	for(i=0;i<PatNum;i++)
	{
		pTemp=new PATTERN_S;
		
		for(j=0;j<PatDim;j++)
			
		{
			if(j==0)
				pTemp->pat=new double[PatDim];
			cin>>pTemp->pat [j];
		}

		cout<<endl;

		
		if(pPattern==NULL)
		{
			pPattern=pTemp;
			pEnd=pTemp;

		}
		else 
		{
			pEnd->pNext=pTemp;
		}
		pEnd=pTemp;

		
	}
	pEnd=pTemp;
	pEnd->pNext =NULL;
	UnClusPatNum=PatNum;

	
	return 0;	
}

int CAlgorithm::PatternOutput()////显示模式数据
{
	PATTERN_S *pTemp;
	pTemp=pPattern;
	int i;

	while(pTemp!=NULL)
	{
		for(i=0;i<PatDim;i++)
		{
			cout<<pTemp->pat[i]<<"  ";
		}
		cout<<endl;
		pTemp=pTemp->pNext;
	}
	return 0;
}



int CAlgorithm::AddCluster(CLUSTER_S *p)//添加一个类节点
{
	CLUSTER_S *pTemp;
	if(p==NULL)
		return 1;


	if(pCluster==NULL)//在空链条加入
	{

		pCluster=p;
		ClusNum++;
		return 0;
	}
	else //在尾部加入
	{
		pTemp=pCluster;
		while(pTemp->pNext!=NULL)
		{
			pTemp=pTemp->pNext;
		}
		pTemp->pNext=p;
		ClusNum++;
		return 0;
	}
}


int CAlgorithm::DeleteCluster(int position)////删除一个类
{
	CLUSTER_S *pTemp;
	CLUSTER_S *pDel;

	pTemp=pCluster;

	if(pTemp==NULL||position<1||position>ClusNum)
		return 1;


	if(position==1)//在链条头删除
	{

		pCluster=pCluster->pNext;
		FreePatInClus(pTemp->pPat);
		delete pTemp;
		ClusNum--;
		return 0;
	}
	else //在指定位置删除
	{
		for(int i=1;i<position-1;i++)
			pTemp=pTemp->pNext;
		
		pDel=pTemp->pNext;
		pTemp->pNext=pDel->pNext;
		FreePatInClus(pDel->pPat);
		delete pDel;
		ClusNum--;
		return 0;
	}
}




int CAlgorithm::AddPatToClus(PATTERN_S *p,CLUSTER_S *c)
{
	if(p==NULL||c==NULL)//输入为空
		return 1;

	PATTERN_S *pTemp;

	pTemp=c->pPat;
	if(pTemp==NULL)//类中模式指针为空
	{
		c->pPat=p;

		return 0;
	}

	while(pTemp->pNext!=NULL)
	{
		pTemp=pTemp->pNext;
	}
	pTemp->pNext=p;
	return 0;
}





PATTERN_S* CAlgorithm::SelectPattern(int position)//根据位置参数返回模式结构指针
{
	if(position<1||position>UnClusPatNum)
		return NULL;

	PATTERN_S *pTemp;
	PATTERN_S *pSel;
	pTemp=pPattern;
	if(pTemp==NULL)
		return NULL;
	if(position==1)
	{
		pPattern=pPattern->pNext;
		pTemp->pNext=NULL;
		UnClusPatNum--;
		return pTemp;
	}
	else
	{
		for(int i=1;i<position-1;i++)
			pTemp=pTemp->pNext;
		pSel=pTemp->pNext;
		pTemp->pNext=pSel->pNext;
		pSel->pNext=NULL;
		UnClusPatNum--;
		return pSel;

		
	}


}

int CAlgorithm::CalClusCent(CLUSTER_S *c)//计算类中心
{	
	if(c==NULL)//空类
		return 1;

	double *pCenter;//临时类心
	double *pDelCent;
	pCenter=new double[PatDim];
	for(int i=0;i<PatDim;i++)
		pCenter[i]=0;
	

	PATTERN_S *pTemp;//临时模式指针
	pTemp=c->pPat;
	int length=CountPattern(pTemp);//模式链长度

	if(pTemp==NULL)//模式链为空
	{
		c->pCenter=NULL;
		return 1;
	}

	//求类心
	do
		{
			for(i=0;i<PatDim;i++)
			{
				pCenter[i]+=pTemp->pat[i];
			}
			pTemp=pTemp->pNext;
		}
	while(pTemp!=NULL);

	for(i=0;i<PatDim;i++)
	{
		pCenter[i]=pCenter[i]/length;
	}
		
		pDelCent=c->pCenter;
		c->pCenter=pCenter;
		delete []pDelCent;


	return 0;
}


int CAlgorithm::DisplayPattern(PATTERN_S *p)
{
	PATTERN_S *pTemp;
	pTemp=p;
	int i;
	if(pTemp==NULL)
	{
		cout<<"此模式为空"<<endl;
		return 0;
	}


	while(pTemp!=NULL)
	{
		for(i=0;i<PatDim;i++)
		{
			cout<<pTemp->pat[i]<<"  ";
		}
		cout<<endl;
		pTemp=pTemp->pNext;
	}
	return 0;
}
int CAlgorithm::DisplayCluster(CLUSTER_S *c)
{
	if(c==NULL)
	{
		cout<<"此类为空"<<endl;
		return 0;
	}

	if(c->pCenter==NULL)
		cout<<"类心为空"<<endl;
	else
	{
		cout<<"类心是"<<"   ";
		for(int i=0;i<PatDim;i++)
		{
			cout<<c->pCenter[i]<<"  ";
		}
	}
	cout<<endl;
	cout<<"是否在一个循环内被合并过"<<c->CombineOrNot<<endl;

	cout<<"模式到类心的平均距离:"<<c->PatCentMeanDis<<endl;
	cout<<"类内距离的标准差矢量最大值"<<c->MaxBiaozhuncha<<endl;
	cout<<"类内距离的标准差矢量最大值位置"<<c->MaxBiaozhunchaPos<<endl;
	PATTERN_S *pTemp;
	pTemp=c->pPat;
	cout<<"此类中模式信息:"<<endl;

	DisplayPattern(pTemp);

	cout<<endl;

	return 0;