fcmadlg.cpp

改进的动态聚类算法

	if(repcount==0)
	{
	   preJ=limit;
	   firstJ=limit;
	}
	else
       e=limit-preJ;
	if(e<=0)
		preJ=limit;
	//-------------作用：更精确的调整中心---------------------|

	repcount+=1;

 }while(limit>=threshold&&repcount<repeatNum);

  //==================>计算有效性函数K<==================//
    
	float variance=0.0;
    float Dmin=0.0;
		
    CoreBelonged();     
	variance=CalVariance();
	Dmin=CalDmin();
	K=C*Dmin/(variance);  //有效性函数K


      //float comp=0.0;   有效性函数S
	  //float sep=0.0;
  	  //comp=CalComp(C,NodeNum);
	  //sep=CalSep(C);
	  //S=comp/(sep);
	  
     //------------------------------------------------------|
 	if(C==2)
	{
		Km.maxK=K;
		Km.preJ=preJ;
		SaveCoreAndUmatrix(C,NodeNum);   //save U
		coreinitsave=coreinit;
		//C=(float)pow((double)2,(double)n);
		C=C*2;
	}
	else
	{
		if(K!=0.0)
		{
			//K曾递增趋势，增加C值<----第1层判断
			if(Km.maxK<K)        
			{
				Km.maxK=K;	
				Km.preJ=preJ;
				SaveCoreAndUmatrix(C,NodeNum);//save U
				coreinitsave=coreinit;
			    //C=(float)pow((double)2,(double)n);
			    C=C*2;
			}
		    else
			{                      
			    Km.c=C/2;//K单调递增至最大值!
			    break;
			}
		}
		else    //K=0======>中心出现重叠，或者距离相当的近了趋于0
		{
			Km.c=C/2;//K单调递增至最大值!
			break;
		}
	}				

}

    temp3.Format("迭代次数:%d  阀值:%f   实测收敛值:%f",repcount,threshold,Km.preJ);
	AfxMessageBox("聚类算法迭代结束!");
	m_result.Format("判定最优类数: %d",Km.c);
	m_process.Format("正在输出结果，请等待...");
	UpdateData(false);
   //=========================================>输出结果
	CString temp1,temp2;
	temp4.Format("*******FCMA聚类算法结果**********************\r\n最优聚类数：%d\r\n中心坐标为：\r\n",Km.c);
		
	coreinitsave+=temp4;
	m_corematrix+=coreinitsave;

		
	for(int c=0;c<Km.c;c++)  //显示聚类中心坐标
	{  
		temp2.Format("%f  %f\r\n",(*(CorematrixSave+c)).x,(*(CorematrixSave+c)).y);
		m_corematrix+=temp2;
	}


	m_Umatrix+="***************************************************************************************************************************************************************************************\r\n\r\n";
	m_Umatrix+=wholeinitcore;//0909
	m_Umatrix+=temp3;	        
	m_corematrix+="*******************************************\r\n\r\n";
	m_process="";
	m_process.Format("自动聚类已完成!");
	
	UpdateData(false);
	
	//===================>重新置空STRING
	m_Umatrix="";
	m_corematrix="";
	coreinit="";
	m_result="";
	temp="";temp0="";temp3="";temp4="";
	temp1="";temp2="";
	
    //return true;

}

float CFCMADlg::Caldistance(int dccordcn,int coreid,int dataindex,int coreid2,int data1,int data2)
{
	float distance=0.0;  //平方距离
	if(dccordcn==0)      //0 core--node
	{
	    distance=((*(coredata+coreid)).x-(*(nodedata+dataindex)).x)*((*(coredata+coreid)).x-(*(nodedata+dataindex)).x)+
		         ((*(coredata+coreid)).y-(*(nodedata+dataindex)).y)*((*(coredata+coreid)).y-(*(nodedata+dataindex)).y);
		return distance;
	}
	else
	{
	   if(dccordcn==1)   //1 core--core
	   {
		distance=((*(coredata+coreid)).x-(*(coredata+coreid2)).x)*((*(coredata+coreid)).x-(*(coredata+coreid2)).x)+
			     ((*(coredata+coreid)).y-(*(coredata+coreid2)).y)*((*(coredata+coreid)).y-(*(coredata+coreid2)).y);
		return distance;
	   }
	   if(dccordcn==2)  //2  node--node
	   {
		distance=((*(nodedata+data1)).x-(*(nodedata+data2)).x)*((*(nodedata+data1)).x-(*(nodedata+data2)).x)+
			     ((*(nodedata+data1)).y-(*(nodedata+data2)).y)*((*(nodedata+data1)).y-(*(nodedata+data2)).y);
		return distance;
	   }
	   else
		   return 0.0;
	}

}

bool CFCMADlg::CalCorepos()
{
	float sumx=0.0,sumy=0.0,   //求聚类中心公式的分子
		  sumu=0.0,            //求聚类中心公式的分母
		  sumline=0.0;
		
	for(int k=0;k<C;k++)
	{
		for(int n=0;n<NodeNum;n++)
		{ 
			//sumline+=Umatrix[k][n];  //sumline--->U矩阵行和
			sumline+=(*(Umatrix+(k*NodeNum+n)));
		}
	}
    //----------------聚类数C>=2,所以不会出现U矩阵整行都为0的情况
	if(sumline==0.0)  //如果U矩阵整行都为0====>退出程序，聚类中心初始化不好   
	{
		AfxMessageBox("聚类中心初始化不好");
		return false;
	}

	for(int i=0;i<C;i++)
	{
		for(int j=0;j<NodeNum;j++)
		{ 
			if((*(Umatrix+(i*NodeNum+j)))!=0.0)               
			{
				sumx+=(float)pow((double)*(Umatrix+(i*NodeNum+j)),(double)m)*((*(nodedata+j)).x);
				sumy+=(float)pow((double)*(Umatrix+(i*NodeNum+j)),(double)m)*((*(nodedata+j)).y);
				sumu+=(float)pow((double)*(Umatrix+(i*NodeNum+j)),(double)m);
			}
			   
		}
		//coredata[i].x=sumx/sumu;
		//coredata[i].y=sumy/sumu;
		(*(coredata+i)).x=sumx/sumu;
		(*(coredata+i)).y=sumy/sumu;
		sumx=0.0;
		sumy=0.0;
		sumu=0.0;
	}
	return true;

}

float CFCMADlg::CalDmin()   //计算各中心间最短距离 **
{
	float coredmin=0.0;
	float temp=0.0;
	int   count=1;
	//1.要计算中心点两两间距离   2.求这些距离的最小值
	for(int i=0;i<C-1;i++)
	{
		for(int j=i+1;j<C;j++)
		{
			temp=Caldistance(1,i,0,j,0,0);
			if(count==1)
			{
				coredmin=temp;
				count++;
			}
			else
				coredmin=min(temp,coredmin);
		}
	}

	return coredmin;

}

float CFCMADlg::CalVariance()//int coreindex 计算类的方差    **  ??以隶属度做归属判定准则<---方法有待探讨
{
	float sumV=0.0;         
	float dik=0.0;          //数据K和中心I的距离
	float U=0.0;            //U   **0905
	float Var=0.0;

	for(int i=0;i<C;i++)
	{
		for(int k=0;k<NodeNum;k++)
		{
			if((*(nodedata+k)).id==i)   //数据属于同个类
			{
				dik=Caldistance(0,i,k,0,0,0);
				sumV+=(*(Umatrix+(i*NodeNum+k)))*dik;
			}
		}
	}
	//Var=sumV/U;
	//return Var;

    return sumV;
}

void CFCMADlg::CoreBelonged()//计算各个数据点属于哪个类
{
	float temp=0.0;
	for(int k=0;k<NodeNum;k++)
	{
		for(int i=0;i<C;i++)      //找隶属度最大值
		{
			if(i==0)//temp=Umatrix[i][k];
				temp=*(Umatrix+(i*NodeNum+k));
			temp=max((*(Umatrix+(i*NodeNum+k))),temp);
		}
		for(int j=0;j<C;j++)
		{
			if(temp==(*(Umatrix+(j*NodeNum+k))))
				//nodedata[k].id=j;
				(*(nodedata+k)).id=j;
		}
	}

}

void CFCMADlg::SaveCoreAndUmatrix(int coreNum,int nodeNum)
{
	for(int i=0;i<coreNum;i++)
	{

        (*(CorematrixSave+i)).x=(*(coredata+i)).x;
		(*(CorematrixSave+i)).y=(*(coredata+i)).y;

		//CorematrixSave[i].x=coredata[i].x;CorematrixSave[i].y=coredata[i].y;
		/*for(int k=0;k<nodeNum;k++)    <-------暂时不需要输出U矩阵
		{
			UmatrixSave[i][k]=Umatrix[i][k];
		}*/
	}

}




void CFCMADlg::CutPeak(int c,bool firstcut)    //减法聚类
{
	int index=0;
	if(firstcut)
	{
		for(int i=0;i<c;i++)
		{
		   index=CalMaxDensitydata(i,nodedata);
		//coredata[i].x=nodedata[index].x;
		//coredata[i].y=nodedata[index].y;
		   //(*(coredata+i)).x=(*(nodedata+index)).x;
		   //(*(coredata+i)).y=(*(nodedata+index)).y;
           //0909+
		   coreXsave[i]=(*(nodedata+index)).x;
		   coreYsave[i]=(*(nodedata+index)).y;
		}
	}
	else
	{
		for(int j=c/2;j<c;j++)
		{
			index=CalMaxDensitydata(j,nodedata);
		    //(*(coredata+j)).x=(*(nodedata+index)).x;
		    //(*(coredata+j)).y=(*(nodedata+index)).y;
            //0909+
			coreXsave[j]=(*(nodedata+index)).x;
		    coreYsave[j]=(*(nodedata+index)).y;
		}
	}

}

int CFCMADlg::CalMaxDensitydata(int c,Node *nodedata)
{
	float maxd=0.0;
	float Ra=0.324f;    //Ra
	float Rb=0.415f;  //Rb=1.25Ra
	float temp2=0.0;
	float distance=0.0;
	float distance2=0.0;
	float aaa=0.0;
	
	float temp=(float)pow((double)(Ra/2),(double)2);
	float temp1=(float)pow((double)(Rb/2),(double)2);
	if(c==0)
	{
        for(int i=0;i<NodeNum;i++)
		{
			for(int j=0;j<NodeNum;j++)
			{
				distance=Caldistance(2,0,0,0,i,j);//nodedata[i].density+=(float)exp(-distance/temp);
				((*(nodedata+i)).density)+=(float)exp(-distance/temp);
			}
			if(i==0)
			{
				maxd=(*(nodedata+i)).density;
			}
			else
				maxd=max(maxd,(*(nodedata+i)).density);
   		}
		for(int a=0;a<NodeNum;a++)
		{
			if((*(nodedata+a)).density==maxd)
			{
				prec=a;
				savemax=maxd;
				return a;
			}
		}
	}
	else
	{
		for(int m=0;m<NodeNum;m++)
		{
				distance2=Caldistance(2,0,0,0,m,prec);
				temp2=(float)exp(-distance2/temp1);  
				aaa=savemax*temp2;
				//TRACE("%d  %f  %f  %f  %f\n",m,nodedata[m].density,nodedata[prec].density,temp2,aaa);
				(*(nodedata+m)).density=(*(nodedata+m)).density-aaa;
				//TRACE("%d  %f\n",m,nodedata[m].density);
				if(m==0)
				{
					maxd=(*(nodedata+m)).density;
				}
				else
				{
					maxd=max(maxd,(*(nodedata+m)).density);
				}
		}
		for(int b=0;b<NodeNum;b++)
		{
			if((*(nodedata+b)).density==maxd)
			{
				prec=b;
				savemax=maxd;
				return b;
			}
		}
	}

	return NULL;
				
}

void CFCMADlg::OnCancel() 
{
	// TODO: Add extra cleanup here
	//===================>释放内存
	GlobalFreePtr(nodedata);
	GlobalFreePtr(coredata);
	GlobalFreePtr(Idata);
	GlobalFreePtr(Qdata);
	GlobalFreePtr(Umatrix);
	GlobalFreePtr(CorematrixSave);
	//GlobalFreePtr(UmatrixSave1);

	CDialog::OnCancel();
}


/*float CFCMADlg::CalComp(int c, int nodenum)  //计算紧密性
{
	float comp=0.0;
	float dik=0.0;
    float dik2=0.0;
	float Vik=0.0;
	float temp=0.0;

	for(int i=0;i<c;i++)
	{
		for(int k=0;k<nodenum;k++)
		{
			if((*(nodedata1+k)).id==i)   //数据属于同个类 
			{
				dik=Caldistance(0,i,k,0,0,0);
				Vik=CalVik(i,k);
				temp=(float)pow((double)(*(Umatrix1+(i*nodeNum+k))),(double)m)*Vik;
				comp+=dik/temp;
			}
		}
	}

	return comp;

}*/

/*float CFCMADlg::CalSep(int c)                //计算分离性
{
	float temp=0.0;
	float temp1=0.0;
	float sep=0.0;
	float Di=0.0;
	float Dk=0.0;

	int   count=1;
	//1.要计算中心点两两间距离   2.求这些距离的最小值
	for(int i=0;i<c-1;i++)
	{
		for(int j=i+1;j<c;j++)
		{
			temp=Caldistance(1,i,0,j,0,0);
			Di=CalVariance(i);
			Dk=CalVariance(j);
			temp1=temp/(Di*Di+Dk*Dk);
			if(count==1)
			{
				sep=temp1;
				count++;
			}
			else
				sep=min(temp1,sep);
		}
	}

	return sep;

}*/

/*float CFCMADlg::CalVik(int i, int k)        //i==coreindex,k==nodeindex
{
	float Vik=0.0;
	float dik=0.0;
	float Di=0.0;

	dik=Caldistance(0,i,k,0,0,0);
	Di=CalVariance(i);
	Vik=1/(1+dik/Di);

	return Vik;
}*/