m.cpp

该程序是模式识别课程里的K均值算法程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <math.h>

// 宏定义
#define  SUCCESS   1
#define  FAILURE   0
#define  TRUE   1
#define  FALSE   0
#define  MAXVECTDIM  20
#define  MAXPATTERN  20
#define  MAXCLUSTER  10
#define  SIZEVECTOR  2   //维数
#define  ResultsFile  "Results.txt"

char *f2a(double x, int width) //将x精确到小数点后width位
{
 char cbuf[255];
 char *cp;
 int i,k;
 int d,s;
cp=fcvt(x,width,&d,&s);/*函数名: fcvt
　　     功 能: 把一个浮点数转换为字符串
　　     用 法: char *fcvt(double value, int ndigit, int *decpt, int *sign);*/

if (s) 
{
 strcpy(cbuf,"-");
}
else 
{
 strcpy(cbuf," ");
} /* endif */
if (d>0) 
{
 for (i=0; i<d; i++) 
 {
  cbuf[i+1]=cp[i];
 } /* endfor */
 cbuf[d+1]=0;
 cp+=d;
 strcat(cbuf,".");
 strcat(cbuf,cp);
} 
else
{
 if (d==0)
 {
  strcat(cbuf,"0.");
  strcat(cbuf,cp);
 }
 else
 {
  k=-d;
  strcat(cbuf,".");
  for (i=0; i<k; i++)
  {
   strcat(cbuf,"0");
  } /* endfor */
  strcat(cbuf,cp);
 } /* endif */
} /* endif */
cp=&cbuf[0];
return cp;
}

// ***** Defined structures & classes *****
struct aCluster
{
 double       Center[MAXVECTDIM];
 int          Member[MAXPATTERN];  
 int          NumMembers;
};

struct aVector
{
 double       Center[MAXVECTDIM];
 int          Size;
};

class System
{
private:
 double  Pattern[MAXPATTERN][MAXVECTDIM+1];
 aCluster Cluster[MAXCLUSTER];
 FILE  *OutFile;     //存放结果文件
 int   NumPatterns;          // 数组的个数
 int   NumClusters;          // 类数相当于k
 void  DistributeSamples();  
 int   CalcNewClustCenters();
 double  EucNorm(int, int);    
 int   FindClosestCluster(int); 
                                        
public:
 system();
 int LoadPatterns(char *fname);     
 void InitClusters();                
 void RunKMeans();                  
 void ShowClusters();               
 void ShowCenters();
 void WriteResults();
 void CloseResults();
};

 void System::ShowCenters()
{
 int i;
 fprintf(OutFile,"\n求出新的聚类点为:\n");
 for (i=0; i<NumClusters; i++)
 {
  Cluster[i].Member[0]=i;
  fprintf(OutFile,"最合适的第%d个点为:ClusterCenter[%d]=(%2.1f,%2.1f)\n",i+1,i,Cluster[i].Center[0],Cluster[i].Center[1]);
 } /* endfor */
 fprintf(OutFile,"\n");
}

void System::WriteResults()
{
 if( ( OutFile = fopen(ResultsFile, "w" ) ) == NULL ) 
 { 
  printf( "输出结果文件打开失败！\npress any key to continue..." ); 
  getchar();
  exit(0);
 } 
}

void System::CloseResults()
{
 fclose(OutFile);
}

int System::LoadPatterns(char *fname)
{
 FILE *InFilePtr;
 int    i,j;
 double x;
 if((InFilePtr = fopen(fname, "r")) == NULL)
 {
  getchar();
  return FAILURE;
 }
 fscanf(InFilePtr, "%d", &NumPatterns); 
 fscanf(InFilePtr, "%d", &NumClusters);  
 for (i=0; i<NumPatterns; i++)           
 {
  for (j=0; j<SIZEVECTOR; j++)        
  {
   fscanf(InFilePtr,"%lg",&x);     
   Pattern[i][j]=x;
  } /* endfor */
 } /* endfor */
 fprintf(OutFile,"从文件中读取的%d个点的坐标数据如下:\n",NumPatterns);
 for (i=0; i<NumPatterns; i++)
 {
  fprintf(OutFile,"Pattern[%d]=(%2.1f,%2.1f)\n",i,Pattern[i][0],Pattern[i][1]);//2.1f
 } /* endfor */
 fprintf(OutFile,"\n");
 return SUCCESS;
}

void System::InitClusters()
{
 int i,j;
 fprintf(OutFile,"假设前%d个点为聚类点:\n",NumClusters);
 for (i=0; i<NumClusters; i++)
 {
  //Cluster[i].Member[0]=i;
  for (j=0; j<SIZEVECTOR; j++)
  {
   Cluster[i].Center[j]=Pattern[i][j];
  } /* endfor */
 } /* endfor */
for (i=0; i<NumClusters; i++)
 {
  fprintf(OutFile,"ClusterCenter[%d]=(%2.1f,%2.1f)\n",i,Cluster[i].Center[0],Cluster[i].Center[1]);
 } /* endfor */
 fprintf(OutFile,"\n");
}

void System::RunKMeans()
{
 int converged;
 int pass;
 pass=1;
 converged=FALSE;
 while (converged==FALSE)
 {
  fprintf(OutFile,"\nPASS=%d\n\n",pass++);
  DistributeSamples();//归类
  converged=CalcNewClustCenters();
  ShowCenters();
 } /* endwhile */
}

double System::EucNorm(int p, int c)    
{
 double dist,x;                      
 int i;                              
 char zout[128];
 char znum[40];
 char *pnum;

 pnum=&znum[0];
 strcpy(zout,"d=(");
fprintf(OutFile,"聚类点ClusterCenter[%d]与Pattern[%d]的距离为:",c,p);
 dist=0;
 for (i=0; i<SIZEVECTOR ;i++)
 {
  x=(Cluster[c].Center[i]-Pattern[p][i])*(Cluster[c].Center[i]-Pattern[p][i]);
  strcat(zout,f2a(x,1));
  if (i==0)strcat(zout,"+");
  dist += (Cluster[c].Center[i]-Pattern[p][i])*(Cluster[c].Center[i]-Pattern[p][i]);
 } /* endfor */
 fprintf(OutFile,"%s)",zout);
 return dist;
}

int System::FindClosestCluster(int pat)
{
 int i, ClustID;
 double MinDist, d;
 MinDist =9.9e+99;
 ClustID=-1;
 for (i=0; i<NumClusters; i++)
 {
  d=EucNorm(pat,i);
  fprintf(OutFile," = %2.1f\n",d);
  if (d<MinDist)
  {
   MinDist=d;
   ClustID=i;
  } /* endif */
 } /* endfor */
 if (ClustID<0)
 {
  fprintf(OutFile,"Aaargh");
  exit(0);
 } /* endif */
 return ClustID;
}

void System::DistributeSamples()
{
 int i,pat,Clustid,MemberIndex;   
 for (i=0; i<NumClusters;i++)
 {
  Cluster[i].NumMembers=0;
 }
 for (pat=0; pat<NumPatterns; pat++)   
 {
  Clustid= FindClosestCluster(pat);
  fprintf(OutFile,"发现点Patern[%d] 更接近于聚类点ClusterCenter[%d]\n\n",pat,Clustid);  
  MemberIndex=Cluster[Clustid].NumMembers;
  Cluster[Clustid].Member[MemberIndex]=pat;
  Cluster[Clustid].NumMembers++; 
 } /* endfor*/
}

int  System::CalcNewClustCenters()
{
 int ConvFlag,VectID,i,j,k;
 double tmp[MAXVECTDIM];
 char xs[255];
 char ys[255];
 char nc1[20];
 char nc2[20];
 char *pnc1;
 char *pnc2;
 
 pnc1=&nc1[0];
 pnc2=&nc2[0];
 ConvFlag=TRUE;
 fprintf(OutFile,"新的聚类点计算公式为:\n");
 for (i=0; i<NumClusters; i++)             
 {
  pnc1=itoa(Cluster[i].NumMembers,nc1,10);
  pnc2=itoa(i,nc2,10);
  strcpy(xs,"Cluster Center");
  strcat(xs,nc2);
  strcat(xs,"(1/");
  strcpy(ys,"(1/");
  strcat(xs,nc1);
  strcat(ys,nc1);
  strcat(xs,")(");
  strcat(ys,")(");
  for (j=0; j<SIZEVECTOR; j++)            
  {
   tmp[j]=0.0;
  } /* endfor */
  for (j=0; j<Cluster[i].NumMembers; j++) 
  {
   VectID=Cluster[i].Member[j];
   for (k=0; k<SIZEVECTOR; k++)       
   {
    tmp[k] += Pattern[VectID][k];   
    if (k==0)
    {
     strcat(xs,f2a(Pattern[VectID][k],1));
    }
    else
    {
     strcat(ys,f2a(Pattern[VectID][k],1));
    } /* endif */
   } /* endfor */
   if(j<Cluster[i].NumMembers-1)
   {
    strcat(xs,"+");
    strcat(ys,"+");
   }
   else
   {
    strcat(xs,")");
    strcat(ys,")");
   }
  } /* endfor */
  for (k=0; k<SIZEVECTOR; k++)          
  {
   tmp[k]=tmp[k]/Cluster[i].NumMembers;
   if (tmp[k] != Cluster[i].Center[k])
    ConvFlag=FALSE;
   Cluster[i].Center[k]=tmp[k];
  } /* endfor */
  fprintf(OutFile,"%s,\n",xs);
  fprintf(OutFile,"%s\n",ys);
 } /* endfor */
 fprintf(OutFile,"\n\n");
 for (i=0; i<NumClusters; i++)
 {
  fprintf(OutFile,"在聚类第%d个内的点有:\n",i+1);
  for (j=0; j<Cluster[i].NumMembers; j++) 
  {
   fprintf(OutFile,"  %d  ",Cluster[i].Member[j]);
  }
  fprintf(OutFile,"\n");
 }
 return ConvFlag;
}

void System::ShowClusters()
{
 int cl;
 for (cl=0; cl<NumClusters; cl++)
 {
  fprintf(OutFile,"\n聚类点%d坐标为:==>[%2.1f,%2.1f]\n", cl+1,Cluster[cl].Center[0],Cluster[cl].Center[1]);
 } /* endfor */
}

void main()
{
 System kmeans;
 char ReadFileName;
 kmeans.WriteResults();
 printf("请输入存放数据的文件名：");
 scanf("%s",&ReadFileName);
 if (kmeans.LoadPatterns(&ReadFileName)==FAILURE)
 {
  printf("对不起，文件%s不存在。\n",&ReadFileName);
  getchar();
  exit(0);
 }
 kmeans.InitClusters();
 kmeans.RunKMeans();
 kmeans.ShowClusters();
 kmeans.CloseResults();
}