mcamda.cpp

是数据挖掘中聚类算法的一种

#include <iostream.h>
#include "math.h" 
#include<stdio.h>        
#include<stdlib.h>        
#include<conio.h>         
#include<dos.h>            
#include<string.h>        
#include<time.h>    
#include <windows.h>                         
#define N 30000  //N为数据点个数    
struct sample  
{
	double x;
	double y;
	int f;
};
struct sample s[N],jc_min_center[30000],center_collect[200];                // s1[N]为样本点,s[N]为标准化样本点

struct sample2  
{
	double x;
	double y;
	int f;
	int num;
};
struct sample2 z1[50],z2[50]; 

struct sample3  
{
	int label;
	double x;
	double y;
	int f;
};
struct sample3 subset[200];

struct shuzu
{
	int label;
	double x;
	double y;
	int inspecttag;                //inspecttag=1表示已经作为考察对象了，避免重复
};
struct shuzu mergeaera[N],coreseed;          //N=2000;

typedef struct LNode{
	double distance;
	int cluster1;
	int cluster2;
	int mergesuccess;
    struct LNode *prior;	
	struct LNode *next;	
}LNode,*Linklist;
Linklist Q;

typedef struct LNode2{                   //定义扩展队列Span;
    int label;
	int possition_mergeaera;                   
	double x;
	double y;
    struct LNode2 *prior;	
	struct LNode2 *next;	
}LNode2,*Linklist2;
Linklist2 Span,Spanp,Spanpend,Spanpnew;

typedef struct LNode3{                   //定义扩展队列Span;
    int label;
	int possition_mergeaera;                   
	double x;
	double y;
	struct LNode3 *next;	
}LNode3,*Linklist3;
Linklist3 temp,tempsearch,tempnew;   
   
typedef struct LNode4{                   //定义扩展队列Span;  
	int label;
	double x;
	double y;
	struct LNode4 *next;	
}LNode4,*Linklist4;
Linklist4 path,pathsearch,pathnew;   
                       
FILE *infp,*outfp;          
char *filename="data_virtual_1.txt";  
char *filename2="result.txt";  
double jc1=1200,jc=0,compjc=0,jc_min=1060;
double distance=0;
int label=0,label_trace,circulate=10,CN,collectno=0,scale=100;         //mine    //子集的规模
COLORREF rgbColor;
double Eps=0.05;                         //DBSCAN的两个参数
int Minpts=3;
int mergesuccess=0;       //合并成功的标志,成功为1
//////////////////////////////////////
void k_means_progress_inter()
{      
   double d[N],md[N],mj=0,x1,x2,y1,y2;
   double sumx=0,sumy=0;
   int i,j,l,m,c[50],dcount=0; 
 //以下是K-MEANS的迭代过程
         do
	{
		for(i=1;i<=scale;i++)
		   md[i]=1000;
    	for(i=1;i<=CN;i++)
		   c[i]=0;                  //同一个类中有好多个点
		for(l=1;l<=scale;l++)
		{
			x1=subset[l].x;
			y1=subset[l].y;
			for(m=1;m<=CN;m++)
			{
				x2=z1[m].x;
				y2=z1[m].y;
				d[l]=sqrt(pow((x1-x2),2)+pow((y1-y2),2));
				if(md[l]>d[l])
				{
					md[l]=d[l];
					subset[l].f=z1[m].f;     //assign each exemplar to its nearest cluster as represented by z1[i].f
				}
			}
		}
		 
		for(i=1;i<=CN;i++)
		{
				for(j=1;j<=scale;j++)
				{if(subset[j].f!=i)
				   continue;
				 sumx=sumx+subset[j].x;
				 sumy=sumy+subset[j].y;
				 c[i]++;
				}
   				z2[i].x=sumx/c[i];//set the new center to the average count of points
      			z2[i].y=sumy/c[i];
				z2[i].f=i;
				sumx=0;
				sumy=0;   
			
		}

		for(i=1;i<=CN;i++)
		{
			x1=z2[i].x;
			y1=z2[i].y;             
			for(j=1;j<=scale;j++)
			{ if(subset[j].f==i)
			{   x2=subset[j].x;
				y2=subset[j].y;
				mj=mj+pow((x2-x1),2)+pow((y2-y1),2);   
			}
			}
			jc=jc+mj;
			mj=0;//compute the value of jc
		}
	
		for(i=1;i<=CN;i++)
			if(z2[i].x!=z1[i].x&&z2[i].y!=z1[i].y)
				z1[i]=z2[i];//update the cluster centers as sample means in each cluster
	 compjc=fabs(jc1-jc);
	 jc1=jc;
	 jc=0;
	 dcount++;
	}while(compjc>1e-6);//(dcount<1);          //continue until centers do not change anymore
    for(j=1;j<=CN;j++)
	{
	   center_collect[collectno+j].x=z1[j].x;
       center_collect[collectno+j].y=z1[j].y;
	 }	
	   collectno=collectno+CN;
}
////////////////////////////////////////
void k_means_progress()
{       
   double d[N],md[N],mj=0,x1,x2,y1,y2;
   double sumx=0,sumy=0;
   int i,j,l,m,c[50],dcount=0;
 //以下是K-MEANS的迭代过程
       do
	{
		for(i=1;i<=label_trace;i++)
		   md[i]=1000;
    	for(i=1;i<=CN;i++)
		   c[i]=0;                  //同一个类中有好多个点
		for(l=1;l<=label_trace;l++)
		{
			x1=s[l].x;
			y1=s[l].y;
			for(m=1;m<=CN;m++)
			{
				x2=z1[m].x;
				y2=z1[m].y;
				d[l]=sqrt(pow((x1-x2),2)+pow((y1-y2),2));
				if(md[l]>d[l])
				{
					md[l]=d[l];
					s[l].f=z1[m].f;     //assign each exemplar label_trace its nearest cluster as represented by z1[i].f
				}
			}
		}
		 
		for(i=1;i<=CN;i++)
		{
				for(j=1;j<=label_trace;j++)
				{if(s[j].f!=i)
				   continue;
				 sumx=sumx+s[j].x;
				 sumy=sumy+s[j].y;
				 c[i]++;
				}
   				z2[i].x=sumx/c[i];//set the new center to the average count of points
      			z2[i].y=sumy/c[i];
				z2[i].f=i;
				sumx=0;
				sumy=0;   
			
		}

		for(i=1;i<=CN;i++)
		{
			x1=z2[i].x;
			y1=z2[i].y;             
			for(j=1;j<=label_trace;j++)
			{ if(s[j].f==i)
			{   x2=s[j].x;
				y2=s[j].y;
				mj=mj+pow((x2-x1),2)+pow((y2-y1),2);   
			}
			}
			jc=jc+mj;
			mj=0;//compute the value of jc
		}
	
		for(i=1;i<=CN;i++)
			if(z2[i].x!=z1[i].x&&z2[i].y!=z1[i].y)
				z1[i]=z2[i];//update the cluster centers as sample means in each cluster
	 compjc=fabs(jc1-jc);
	 jc1=jc;
	 jc=0;
	 dcount++;
	}while(compjc>1e-6);          //continue until centers do not change anymore
 }

/////////////////////////////////////////////
void main()
{
        int i,j,l,m;   
		 int k,count,possition;//,seed;             //共有K个聚类中心
		int ii,flag,chounum;
        int distance_max_label;                                     
        double t1,t2,R;
	    double distance_max;       //by zjuan 2005-4-29
        double avgx,avgy,sx,sy,sqrx=0,sqry=0,ssumx,ssumy,minx,miny,maxx,maxy;
        double dis[700][50];
   
	infp=fopen(filename,"r");  
	while((getc(infp)!=EOF))
	{
                  fscanf(infp,"%lf",&t1);
                  fscanf(infp,"%lf",&t2);
                  fscanf(infp,"%d",&label);   
                  s[label].x=t1;  
				  s[label].y=t2;  
                  s[label].f=0;
     }  
	label_trace=label;  //label_trace 全局固定不变
    fclose(infp);                 //时间复杂度为:O(N)
	 long TimeStart=GetTickCount(); 
   srand((unsigned)time(NULL));  
   for(ii=1;ii<=circulate;ii++) 
   {
//下面是生成抽样子集的过程：(不重复抽样)    
    for(i=1;i<=scale;i++)
	{
       subset[i].label=0;
       subset[i].x=0;
	   subset[i].y=0;
	   subset[i].f=0;
	}
    flag=0;
	chounum=0;
    while(chounum<scale)
	{	
		 flag=0;
	    j=rand()%label_trace+1; 
		for(m=1;m<=chounum;m++)
		{
          if(j==subset[m].label)
		  {
			  flag=1;
		  }
		}
    	if( flag!=1)
		{
          chounum++;	 
		  subset[chounum].label=j;
          subset[chounum].x=s[j].x;
          subset[chounum].y=s[j].y;
		}	
	}
     label=rand()%scale+1;   // 这里的label是用于局部程序段了
	  k=1;
      z1[k].x=subset[label].x;
      z1[k].y=subset[label].y;
      z1[k].f=k;
   ///////////////////////////////////////
                              //initialize the first cluster centers z1[0]
	  distance_max=0; 
       for(label=1;label<=scale;label++)
		  {
             dis[label][k]=sqrt(pow((z1[k].x-subset[label].x),2)+pow((z1[k].y-subset[label].y),2));
             if(dis[label][k]>distance_max) 
			 {
                distance_max=dis[label][k];
                distance_max_label=label;
              }
          }
	   k++;  //k=2
	   z1[k].x=subset[distance_max_label].x;
       z1[k].y=subset[distance_max_label].y;
	   z1[k].f=k;                         //compute the first cluster centers z1[1]
	 double midmin;
     double average,midsum=0;
	 do
	 {
       distance_max=0; 
	   midsum=0;
	   for(label=1;label<=scale;label++)            //label都是指的数组编号，从1开始。
	   {   
		    midmin=1000;
            dis[label][k]=sqrt(pow((z1[k].x-subset[label].x),2)+pow((z1[k].y-subset[label].y),2));
		
            for(i=1;i<=k;i++)
			{  
			   if(dis[label][i]<midmin) midmin=dis[label][i];
            }
            dis[label][0]=midmin;             //对一个点，用dis[label][0]记录它到各个聚类中心距离的最小值
            if(dis[label][0]>distance_max)  
			{
				distance_max=dis[label][0];
                distance_max_label=label;
			}
         }
	    k++;  
        z1[k].x=subset[distance_max_label].x;
        z1[k].y=subset[distance_max_label].y;
	    z1[k].f=k;
        for(i=1;i<k-1;i++)
		 {
			 midsum=midsum+sqrt(pow((z1[i].x-z1[i+1].x),2)+pow((z1[i].y-z1[i+1].y),2));
         }
	   average=midsum/(k-2);
	 }while( distance_max>0.35*average);        //结束条件有待改进
	 k=k-1;        //循环条件结束则最后一个聚类中心不符合要求
     CN=k;
    k_means_progress_inter();  
}
 
/////////////////////////////////////////////////////////////第二阶段最大距离法
  label=rand()%collectno+1;   // 这里的label是用于局部程序段了
	  k=1;
      z1[k].x=center_collect[label].x;
      z1[k].y=center_collect[label].y;
      z1[k].f=k;
   ///////////////////////////////////////
                              //initialize the first cluster centers z1[0]
	  distance_max=0; 
       for(label=1;label<=collectno;label++)
		  {
             dis[label][k]=sqrt(pow((z1[k].x-center_collect[label].x),2)+pow((z1[k].y-center_collect[label].y),2));
             if(dis[label][k]>distance_max) 
			 {
                distance_max=dis[label][k];
                distance_max_label=label;
              }
          }
	   k++;  //k=2
	   z1[k].x=center_collect[distance_max_label].x;
       z1[k].y=center_collect[distance_max_label].y;
	   z1[k].f=k;                         //compute the first cluster centers z1[1]
	 double midmin;
     double average,midsum=0;
	 do
	 {
       distance_max=0; 
	   midsum=0;
	   for(label=1;label<=collectno;label++)            //label都是指的数组编号，从1开始。
	   {   
		    midmin=1000;
            dis[label][k]=sqrt(pow((z1[k].x-center_collect[label].x),2)+pow((z1[k].y-center_collect[label].y),2));