kmeans.cpp

Kmeans algorithm in C++,output a result.txt containing clustering result.

/****************************************************************************
*                                                                           *
*  KMEANS                                                                   *
*                                                                           *
*****************************************************************************/

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

// FUNCTION PROTOTYPES


// DEFINES
#define         SUCCESS         1
#define         FAILURE         0
#define         TRUE            1
#define         FALSE           0
#define         MAXVECTDIM      20
#define         MAXPATTERN      200
#define         MAXCLUSTER      100

int             clusPat[MAXPATTERN];

char *f2a(double x, int width){
   char cbuf[255];
   char *cp;
   int i,k;
   int d,s;
	cp=fcvt(x,width,&d,&s);
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,".");
         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];  //Index of Vectors belonging to this cluster
   int          NumMembers;
};

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

class System {
private:
   double       fif[MAXVECTDIM];
   double       Pattern[MAXPATTERN][MAXVECTDIM+1];
   aCluster     Cluster[MAXCLUSTER];
   int          NumPatterns;          // Number of patterns
   int          SizeVector;           // Number of dimensions in vector
   int          NumClusters;          // Number of clusters
   void         DistributeSamples();  // Step 2 of K-means algorithm
   int          CalcNewClustCenters();// Step 3 of K-means algorithm
   double       EucNorm(int, int);   // Calc Euclidean norm vector
   int          FindClosestCluster(int); //ret indx of clust closest to pattern
                                         //whose index is arg
public:
   system();
   int LoadPatterns(char *fname, char *fifFileName);      // Get pattern data to be clustered
   void InitClusters();                // Step 1 of K-means algorithm
   void RunKMeans();                   // Overall control K-means process
   void ShowClusters();                // Show results on screen
   void SaveClusters();     // Save results to file
   void ShowCenters();
};

void System::ShowCenters(){
int i,j;
printf("Cluster centers:\n");
for (i=0; i<NumClusters; i++) {
   Cluster[i].Member[0]=i;
   printf("ClusterCenter[%d]=(",i);
   for(j=0;j<SizeVector;j++) {
	  printf("%2.3f,",Cluster[i].Center[j]);
	  if(j==(SizeVector-1)) printf(")\n");
	}/* endfor */
  } /* endfor */
printf("\n");
}

int System::LoadPatterns(char *fname, char *fifFileName){
   FILE *InFilePtr;
   FILE *FIF;
   int    i,j;
   double x;
if((InFilePtr = fopen(fname, "r")) == NULL)
    return FAILURE;
if((FIF = fopen(fifFileName, "r")) == NULL)
    return FAILURE;

fscanf(InFilePtr, "%d", &NumPatterns);  // Read # of patterns
fscanf(InFilePtr, "%d", &SizeVector);   // Read dimension of vector
fscanf(InFilePtr, "%d", &NumClusters);  // Read # of clusters for K-Means
for (i=0; i<NumPatterns; i++) {         // For each vector
   for (j=0; j<SizeVector; j++) {       // create a pattern
      fscanf(InFilePtr,"%lg",&x);       // consisting of all elements
      Pattern[i][j]=x;
	  } /* endfor */
   } /* endfor */
printf("Input patterns:\n");
for (i=0; i<NumPatterns; i++)  {
	printf("Pattern[%d]=(",i);
	for(j=0;j<SizeVector;j++) {
	printf("%2.3f,",Pattern[i][j]);
	if(j==(SizeVector-1)) printf(")\n");
	}
  } /* endfor */
for(i=0;i<SizeVector;i++){
  double a;
  fscanf(FIF, "%lg", &a);
  this->fif[i]=a;
  printf("fif[%d]=%2.3f",i, this->fif[i]);
}
printf("\n--------------------\n");
return SUCCESS;
}
//***************************************************************************
// InitClusters                                                             *
//   Arbitrarily assign a vector to each of the K clusters                  *
//   We choose the first K vectors to do this                               *
//***************************************************************************
void System::InitClusters(){
int i,j;
printf("Initial cluster centers:\n");
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 */

printf("\n");
for (i=0; i<NumClusters; i++) {
	printf("ClusterCenter[%d]=(",i);
	for(j=0;j<SizeVector;j++) {
	  printf("%2.3f,",Cluster[i].Center[j]);
	  if(j==(SizeVector-1)) printf(")\n");
	}/* endfor */
  } /* endfor */
printf("\n--------------------\n");
}

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

double System::EucNorm(int p, int c){   // Calc Euclidean norm of vector difference
double dist,x;                          // between pattern vector, p, and cluster
int i;                                  // center, c.
char zout[128];
char znum[40];
char *pnum;

pnum=&znum[0];
strcpy(zout,"d=sqrt(");
printf("The distance from pattern %d to cluster %d is calculated as:\n",p,c);
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,4));
   if (i==0)
      strcat(zout,"+");
   dist += (Cluster[c].Center[i]-Pattern[p][i])*(Cluster[c].Center[i]-Pattern[p][i]) * this->fif[i];
   } /* endfor */
printf("%s)\n",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);
   printf("Distance from pattern %d to cluster %d is %f\n\n",pat,i,sqrt(d));
   if (d<MinDist) {
      MinDist=d;
      ClustID=i;
      } /* endif */
   } /* endfor */
if (ClustID<0) {
   printf("Aaargh");
   exit(0);
   } /* endif */

return ClustID;
}

void System::DistributeSamples(){
int i,pat,Clustid,MemberIndex;
//Clear membership list for all current clusters
for (i=0; i<NumClusters;i++){
   Cluster[i].NumMembers=0;
   }
for (pat=0; pat<NumPatterns; pat++) {
   //Find cluster center to which the pattern is closest
   Clustid= FindClosestCluster(pat);
   printf("patern %d assigned to cluster %d\n",pat,Clustid);
   Pattern[pat][SizeVector]=Clustid;
   clusPat[pat]=Clustid; //???????????????????????????????????????????????????????????????????
  
   //printf("Pattern[%d][%d]=%d\n\n",pat,SizeVector,clusPat[pat]);//Clustid
   printf("Pattern[%d][%d]=%d\n\n",pat,SizeVector,(int)Pattern[pat][SizeVector]);//Clustid
   
   //post this pattern to the cluster
   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 nc1[255];
   char nc2[255];
   char *pnc1;
   char *pnc2;
   char *fpv;

	pnc1=&nc1[0];
	pnc2=&nc2[0];
	ConvFlag=TRUE;
	printf("The new cluster centers are now calculated as:\n");
	for (i=0; i<NumClusters; i++) {  //for each cluster
		char *xs;
		char *ys;
		xs=new char[2550];
		ys=new char[2550];
		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++) {            // clear workspace
      tmp[j]=0.0;
      } /* endfor */
   for (j=0; j<Cluster[i].NumMembers; j++) { //traverse member vectors
      VectID=Cluster[i].Member[j];
      for (k=0; k<SizeVector; k++) {         //traverse elements of vector
         tmp[k] += Pattern[VectID][k];       // add (member) pattern elmnt into temp
         if (k==0) {
              strcat(xs,f2a(Pattern[VectID][k],3));
            } else {
              strcat(ys,f2a(Pattern[VectID][k],3));
              } /* endif */
         } /* endfor */
      if(j<Cluster[i].NumMembers-1){
         strcat(xs,"+");
         strcat(ys,"+");
         }
        else {
         strcat(xs,")");
         strcat(ys,")");
         }
      } /* endfor */
   for (k=0; k<SizeVector; k++) {            //traverse elements of vector
      tmp[k]=tmp[k]/Cluster[i].NumMembers;
      if (tmp[k] != Cluster[i].Center[k])
         ConvFlag=FALSE;
      Cluster[i].Center[k]=tmp[k];
      } /* endfor */
   printf("\n");
   printf("%s,\n",xs);
   printf("%s\n",ys);
  delete xs;
  delete ys; 
	} /* endfor */

	return ConvFlag;
}

void System::ShowClusters(){
   int cl;
for (cl=0; cl<NumClusters; cl++) {
   printf("\nCLUSTER %d ==>[%f,%f]\n", cl,Cluster[cl].Center[0],Cluster[cl].Center[1]);
   } /* endfor */
}

void System::SaveClusters(){
FILE *r;
r=fopen("C:\\KMEANS\\Debug\\result.txt","w+");
int i,j;
printf("将结果保存至C:\\KMEANS\\Debug\\result.txt\n");
for (i=0; i<NumPatterns; i++)  {

	for(j=0;j<SizeVector;j++) {
	fprintf(r,"%2.3f,",Pattern[i][j]);
	if(j==(SizeVector-1)) fprintf(r,"%d\n",clusPat[i]);
	}
  } 
}


main(int argc, char *argv[]) {
   System kmeans;
if (argc<2) {
   printf("USAGE: KMEANS PATTERN_FILE\n");
   exit(0);
   }
if (kmeans.LoadPatterns(argv[1],argv[2])==FAILURE ){
   printf("UNABLE TO READ PATTERN_FILE:%s\n",argv[1]);
   exit(0);
   }

	kmeans.InitClusters();
	kmeans.RunKMeans();
	kmeans.SaveClusters();
}