k-means.cpp

k-means算法 C++实现

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

// FUNCTION PROTOTYPES


// DEFINES
#define         SUCCESS         1
#define         FAILURE         0
#define         TRUE            1
#define         FALSE           0
#define         MAXVECTDIM      200
#define         MAXPATTERN      200
#define         r               10
#define         k               (MAXVECTDIM-r)/(r-1)
#define		    MAXCAPACITY      2000
// ***** Defined structures & classes *****
struct aMark{
   double x;
   double y;
}
struct aCluster {
   aMark       Center[MAXVECTDIM];
   int         Member[MAXPATTERN];  //Index of Vectors belonging to this cluster
   int         NumMembers;
};

struct aVector {
   aMark       Center[MAXVECTDIM];
   double      Capacity;
};
struct infor {
   double di;
   double ca;
}

void bubble_Sort(infor a[],int n){
  int chang=1;
  for(int i=n-1;i>=1&&chang;i--){
    chang=0;
    for(int j=0;j<i;j++){
      if(a[j].di>a[j+1].di){
        infor t;
        t=a[j+1];
        a[j+1]=a[j];
        a[j]=t;
        chang=1;
     }
   }
 }   
}

void InitClusters(){
int i,j;
aMark       Pattern[MAXCLUSTER][MAXVECTDIM];
aCluster     Cluster[MAXCLUSTER];
printf("Initial cluster centers:\n");
for (i=0; i<k; i++) {
   Cluster[i].Member[0]=i;
   for (j=0; j<MAXVECTDIM; j++) {
      Cluster[i].Center[j]=Pattern[i][j];
      } /* endfor */
   } /* endfor */
printf("\n");
}

infor EucNorm(int p, int c){   // Calc Euclidean norm of vector difference
double d;                             // between pattern vector, p, and cluster
double tDist=0.0;                         // center, c.
int i; 
aVector Vector[MAXVECTDIM]; 
double total=0.0; 
infor  it;                             
printf("The distance from pattern %d to cluster %d is calculated as:\n",c,p);
dist=0;
for (i=0; i<MAXVECTDIM;i++){
   d=(Cluster[c].Center[i].x-Pattern[p][i].x)*(Cluster[c].Center[i].x-Pattern[p][i].x)+(Cluster[c].Center[i].y-Pattern[p][i].y)*(Cluster[c].Center[i].y-Pattern[p][i].y);
   if (i==0)
     printf("this vector is error!");
   tDist += x;
   total+=vector.Capacity;
   } /* endfor */
it.di=tDist;
it.ca=total;
return it;
}

int FindClosestCluster(int pat){
   int i;
   int t;
   infor it[k];
t=k;
for (i=0; i<t; i++) {
   it[i]=EucNorm(pat,i);
   printf("Distance from pattern %d to cluster %d is %f\n\n",pat,i,sqrt(it[i].di));
}
bubble_Sort(it,t);
while(it[t].ca>=(MAXCAPACITY/K)){
    it[t]=it[t-1];
	t=t-1;
}
return t;
}

void DistributeSamples(){
int i,pat,Clustid,MemberIndex;
//Clear membership list for all current clusters
for (i=0; i<k;i++){
   Cluster[i].NumMembers=0;
   }
for (pat=0; pat<MAXVECTDIM; pat++) {
   //Find cluster center to which the pattern is closest
   Clustid= FindClosestCluster(pat);
   printf("patern %d assigned to cluster %d\n\n",pat,Clustid);
   //post this pattern to the cluster
   MemberIndex=Cluster[Clustid].NumMembers;
   Cluster[Clustid].Member[MemberIndex]=pat;
   Cluster[Clustid].NumMembers++;
   } /* endfor */
}

int  CalcNewClustCenters(){
   int ConvFlag,VectID,i,j,k;
   double tmp[MAXVECTDIM];
ConvFlag=TRUE;
printf("The new cluster centers are now calculated as:\n");
for (i=0; i<k; i++) {              //for each cluster
   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
         } /* endfor */
      } /* 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 */
   } /* endfor */
return ConvFlag;
}