fence.cpp

模糊K近邻分类器

//该函数实现对exemplar部分的训练
/*
   输入参数：
   prototype -- 指向prototype部分的指针
   N -- prototype部分的结点个数
   exemplar -- 指向exemplar部分指针的指针
   M -- exemplar部分结点的个数
   sample -- 输入模式
   L -- 输入模式的维数
   classnum -- 输入模式属于的类号
   输出参数：
   经过更新以后exemplar部分的结点个数
*/

#include <math.h>
#include <iostream.h>
#include <assert.h>
#include <stdio.h>
#include "FuzzyNN.h"
#include "tools.h"

int fence(ProtoNode *prototype,int N,ExemNode **exemplar,int M,FuzzyNum *sample,int L,int classnum)
{
	double rou; //结点大小指定参数限制
	
	int *candidate; //用来标记每个exemplar结点是否满足候选条件
	candidate=new int[M+1];
	mcheck(candidate);

	int i,j,k;
	for(i=1;i<=M;i++)
		candidate[i]=0;

	//cout<<"请输入对exemplar结点大小进行限制的参数:"<<endl;
	//cin>>rou;
	rou=0.3;

	//计算对当前输入模式，哪个结点胜出
	int pmark;
	int emark;

    //-计算s1,s2,...,sN，并求其最大值
	double *s;
	s=new double[N+1];
	mcheck(s);
	
	for(j=1;j<=N;j++)
	{
		s[j]=0;
		for(i=1;i<=L;i++)
			s[j]+=(coa(sample[i])-coa((prototype[j].w)[i]))*(coa(sample[i])-coa((prototype[j].w)[i]));
		s[j]=s[j]/L;
		s[j]=sqrt(s[j]);
		s[j]=1-s[j];
	}

	double pmax; //s1,s2,...,sN中的最大值
	int pindex; //最大值对应的下标

	pmax=s[1];
	pindex=1;
	for(i=2;i<=N;i++)
		if(s[i]>pmax)
		{
			pmax=s[i];
			pindex=i;
		}

	//-如果*exemplar不为空的话，计算r1,r2,...,rM，并求其最大值
    double emax=0; //r1,r2,...,rM中的最大值
	int eindex=0; //最大值对应的下标

	if((*exemplar)!=NULL)
	{
		double *r;
		r=new double[M+1];
		mcheck(r);

		j=0;
		ExemNode *p=*exemplar;
		int flag;
		while(p!=NULL)
		{
			j++;
			r[j]=0;
			flag=1;
			for(i=1;i<=L;i++)
				if(!((p->v)[i].w1<=sample[i].w1 && (p->v)[i].w2>=sample[i].w2))
					flag=0;
			if(flag)
			{
				for(i=1;i<=L;i++)
					r[j]+=(sample[i].w1-(p->v)[i].w1)*(sample[i].w1-(p->v)[i].w1)+(sample[i].w2-(p->v)[i].w2)*(sample[i].w2-(p->v)[i].w2);
				r[j]=r[j]/L;
				r[j]=sqrt(r[j]);
				r[j]=2-r[j];
			}
			p=p->next;
		}

        emax=r[1];
	    eindex=1;
	    for(i=2;i<=M;i++)
		   if(r[i]>emax)
		   {
			  emax=r[i];
			  eindex=i;
		   }
		delete []r;
	}
	
	if((*exemplar)==NULL)
	{
		pmark=pindex;
		emark=0;
	}
	else
	{
		if(pmax>emax)
		{
			pmark=pindex;
			emark=0;
		}
		else
		{
			pmark=0;
			emark=eindex;
		}
	}

	ExemNode *p,*q;
	k=0;
	int flag;
	p=*exemplar;
	while(p!=NULL)
	{
		k++; //记录exemplar结点当前的索引号
		if(p->classnum==classnum)
		{
			ExemNode E;
			E.classnum=classnum;
			E.v=new FuzzyNum[L+1];
			mcheck(E.v);
			E.h=NULL;
			E.next=NULL;
			for(i=1;i<=L;i++)
			{
				if((p->v)[i].w1<sample[i].w1)
				{
					(E.v)[i].w1=(p->v)[i].w1;
					(E.v)[i].a=(p->v)[i].a;
				}
				else
				{
					(E.v)[i].w1=sample[i].w1;
					(E.v)[i].a=sample[i].a;
				}

				if((p->v)[i].w2>sample[i].w2)
				{
					(E.v)[i].w2=(p->v)[i].w2;
					(E.v)[i].b=(p->v)[i].b;
				}
				else
				{
					(E.v)[i].w2=sample[i].w2;
					(E.v)[i].b=sample[i].b;
				}
			}
			flag=1;//假设E结点满足候选条件

			//检查E结点是否和其他的结点重叠
			q=*exemplar;
			while(q!=NULL)
			{
				int *overlap;
				overlap=new int[L+1];
				mcheck(overlap);
				int flag0=0; // 检查是否出现零
				for(i=1;i<=L;i++)
				{
					overlap[i]=0;
					if((E.v)[i].w1<=(q->v)[i].w1 && (q->v)[i].w1<(E.v)[i].w2 && (E.v)[i].w2<=(q->v)[i].w2)overlap[i]=1;
					if((q->v)[i].w1<=(E.v)[i].w1 && (E.v)[i].w1<(q->v)[i].w2 && (q->v)[i].w2<=(E.v)[i].w2)overlap[i]=2;
					if((E.v)[i].w1<(q->v)[i].w1 && (q->v)[i].w1<=(q->v)[i].w2 && (q->v)[i].w2<(E.v)[i].w2)overlap[i]=3;
					if((q->v)[i].w1<(E.v)[i].w1 && (E.v)[i].w1<=(E.v)[i].w2 && (E.v)[i].w2<(q->v)[i].w2)overlap[i]=4;
				}
				for(i=1;i<=L;i++)
					if(overlap[i]==0)
					{
						flag0=1;
						break;
					}
				if(!(q->classnum==E.classnum || sum(overlap,L)==3*L || sum(overlap,L)==4*L || flag0))flag=0;
				assert(overlap);
				delete []overlap;
				q=q->next;
			}

			//检查E结点的大小是否满足要求
			if(flag)
			{
			if(emark==0)
			{
				if(!(size(E,L)<=rou))flag=0;
			}
			else
			{
				q=*exemplar;
			    for(i=1;i<emark;i++)//这里将q移动到exemplar第emark个结点
				  q=q->next;
			    if(!(size(E,L)<=rou*size(*q,L)))flag=0;
			}
			q=*exemplar;
			while(q!=NULL)
			{
				int *overlap;
				overlap=new int[L+1];
				mcheck(overlap);
	
				for(i=1;i<=L;i++)
				{
					overlap[i]=0;
					if((E.v)[i].w1<=(q->v)[i].w1 && (q->v)[i].w1<(E.v)[i].w2 && (E.v)[i].w2<=(q->v)[i].w2)overlap[i]=1;
					if((q->v)[i].w1<=(E.v)[i].w1 && (E.v)[i].w1<(q->v)[i].w2 && (q->v)[i].w2<=(E.v)[i].w2)overlap[i]=2;
					if((E.v)[i].w1<(q->v)[i].w1 && (q->v)[i].w1<=(q->v)[i].w2 && (q->v)[i].w2<(E.v)[i].w2)overlap[i]=3;
					if((q->v)[i].w1<(E.v)[i].w1 && (E.v)[i].w1<=(E.v)[i].w2 && (E.v)[i].w2<(q->v)[i].w2)overlap[i]=4;
				}
			 
			    if(sum(overlap,L)==3*L)
				{
					if(!(size(*q,L)<=rou*size(E,L)))flag=0;
				}
				delete []overlap;
				q=q->next;
			}
			}
			//将满足候选条件的加入candidate
			if(flag)
			{
				candidate[k]=1;
			}
		}
     p=p->next;	
     }

	 if(sum(candidate,M)==0) //没有满足候选条件，要新建一个exemplar结点
	 {
		    ExemNode* Enew;
			Enew=new ExemNode;
			mcheck(Enew);
			Enew->classnum=classnum;
			Enew->v=new FuzzyNum[L+1];
			mcheck(Enew->v);
			Enew->h=NULL;
			Enew->next=NULL;
			for(i=1;i<=L;i++)
			{
				(Enew->v)[i].w1=sample[i].w1;
				(Enew->v)[i].w2=sample[i].w2;
				(Enew->v)[i].a=sample[i].a;
				(Enew->v)[i].b=sample[i].b;
			}
			p=*exemplar;
			if(p==NULL)*exemplar=Enew;
			else
			{
				while((p->next)!=NULL)
					p=p->next;
				p->next=Enew;
			}
	 }
	 else
	 {
		  double max;
		  int index;

		  max=-100;
		  index=0;
		  for(j=1;j<=M;j++)
		  {
			  if(candidate[j]==1)
			  {
				  //计算第i个exemplar结点和输入模式的相似性
				  p=*exemplar;
			    for(i=1;i<j;i++)
				  p=p->next;

				double s=0;
	         	for(i=1;i<=L;i++)
		        	s+=(coa(sample[i])-coa((p->v)[i]))*(coa(sample[i])-coa((p->v)[i]));
	        	s=s/L;
	        	s=sqrt(s);
	        	s=1-s;
				if(s>max)
				{
					max=s;
					index=j;
				}
			  }
		  }

            p=*exemplar;
			for(j=1;j<index;j++)
				p=p->next;
		  	for(i=1;i<=L;i++)
			{
				if((p->v)[i].w1<sample[i].w1)
				{
					(p->v)[i].w1=(p->v)[i].w1;
					(p->v)[i].a=(p->v)[i].a;
				}
				else
				{
					(p->v)[i].w1=sample[i].w1;
					(p->v)[i].a=sample[i].a;
				}

				if((p->v)[i].w2>sample[i].w2)
				{
					(p->v)[i].w2=(p->v)[i].w2;
					(p->v)[i].b=(p->v)[i].b;
				}
				else
				{
					(p->v)[i].w2=sample[i].w2;
					(p->v)[i].b=sample[i].b;
				}
			}
	 }
     
	 delete []s;
     int temp=sum(candidate,M);
	 delete [] candidate;
	 if(temp==0)return(M+1);
	 else return M;
}