www.pudn.com > NeuralNetworkSourceCode.zip > VQ.CPP, change:2001-02-17,size:12968b


/****************************************************************************
*                                                                           *
*  VECTOR QUANTIZATION                                                      *
*                                                                           *
*****************************************************************************/

#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      20
#define         MAXCLUSTER      10

// ***** 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 VQsyst {
private:
   double       Pattern[MAXPATTERN][MAXVECTDIM+1];
   aCluster     Cluster[MAXCLUSTER];
   int          NumPatterns;          // Number of patterns
   int          SizeVector;           // Number of dimensions in vector
   int          NumClusters;          // Curr number of clusters
   double       Threshold;
   void         Attach(int,int);      // Add spec'd pattern to spec'd
                                      // Clusters membership list.
   int          AllocateCluster();    //
   void         CalcNewClustCenter(int);// find cluster center for modified
                                         // clusters
   double       EucNorm(int, int);   // Calc Euclidean norm vector
   int          FindClosestCluster(int); //ret indx of clust closest to pattern
                                         //whose index is arg
   FILE *OutFile;
public:
   VQsyst();
   int InitOutput(char *fname);
   int LoadPatterns(char *fname);      // Get pattern data to be clustered
   void RunVQ();                   // Overall control Vector Quant process
   void ShowClusters();                // Show results on screen
   void SaveClusters(char *fname);     // Save results to file
   ~VQsyst(){fclose(OutFile);}
};


//=================IMPLENTATION OF VQ METHODS================================



//***************************************************************************
// Constructor
//***************************************************************************

VQsyst::VQsyst(){
   NumClusters=0;
   }


//***************************************************************************
// InitOutput
//***************************************************************************

int VQsyst::InitOutput(char *fname) {
if((OutFile = fopen(fname, "w")) == NULL){
    printf("Unable to open file %s for output",fname);
    return FAILURE;
    }
return SUCCESS;
}

//***************************************************************************
// LoadPatterns                                                             *
//   Loads pattern information from disk.                                   *
//       1) Number of patterns to be processed                              *
//       2) Size of the vectors to be processed                             *
//       3) Max dist permitted between cluster centers                      *
//       4) Pattern definitions                                             *
//***************************************************************************

int VQsyst::LoadPatterns(char *fname){
   FILE *InFilePtr;
   int    i,j;
   double x;
if((InFilePtr = fopen(fname, "r")) == NULL)
    return FAILURE;
fscanf(InFilePtr, "%d", &NumPatterns);  // Read # of patterns
fscanf(InFilePtr, "%d", &SizeVector);   // Read dimension of vector
fscanf(InFilePtr, "%lg", &Threshold);   // Read Euc dist Threshold.
printf("The input patterns are:\n");
fprintf(OutFile,"The input patterns are:\n");
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;
      printf("Pattern[%d][%d]=%f\n",i,j,Pattern[i][j]);
      fprintf(OutFile,"Pattern[%d][%d]=%f\n",i,j,Pattern[i][j]);
      } /* endfor */
   } /* endfor */
printf("\n");
fprintf(OutFile,"\n");
return SUCCESS;
}

//***************************************************************************
// RunVQ                                                                    *
//   Provides overall control of VQ algorithm.  K clusters                  *
//   We choose the first K vectors to do this                               *
//***************************************************************************

void VQsyst::RunVQ(){
  int pat,Winner;
  double dist;

for (pat=0; pat<NumPatterns; pat++) {
   printf("\n\nPATTERN %d:\n",pat);
   fprintf(OutFile,"\n\nPATTERN %d:\n",pat);
   Winner = FindClosestCluster(pat);   // Attach the curr input to closest
                                       // cluster
   if (Winner == -1) {
      Winner=AllocateCluster();
      printf(" so allocate a new cluster %d\n",Winner);
      fprintf(OutFile," so allocate a new cluster %d\n",Winner);
      }
    else {
      printf("The closest cluster is: %d\n",Winner);
      fprintf(OutFile,"The closest cluster is: %d\n",Winner);
      dist= EucNorm(pat,Winner);
      dist= sqrt(dist);                // because eucnorm doesn't do this
      if (dist>Threshold) {
         printf("distance %f > %f", dist,Threshold);
         printf("\nTherefore cluster %d failed the distance test.\n",Winner);
         fprintf(OutFile,"distance %f > %f", dist,Threshold);
         fprintf(OutFile,"\nTherefore cluster %d failed the distance test.\n",Winner);
         Winner=AllocateCluster();     // Above threshold so allocate new
         printf("so create NEW cluster number:%d\n",Winner);
         fprintf(OutFile,"so create NEW cluster number:%d\n",Winner);
         }
       else {
         printf("Distance %f < %f", dist,Threshold);
         printf("\nTherefore cluster %d passed the distance test.\n",Winner);
         fprintf(OutFile,"Distance %f < %f", dist,Threshold);
         fprintf(OutFile,"\nTherefore cluster %d passed the distance test.\n",Winner);
         } /* endif */                 // cluster
      } /* endif */
   printf("patern %d assigned to cluster %d\n",pat,Winner);
   fprintf(OutFile,"patern %d assigned to cluster %d\n",pat,Winner);
   Attach(Winner,pat);                 // Attach pattern to winner
   CalcNewClustCenter(Winner);         // Adapt clust center
   ShowClusters(); 
   } /* endfor */
}


//***************************************************************************
// AllocateCluster                                                          *
//    Designate the next free cluster as active                             *
//***************************************************************************

int VQsyst::AllocateCluster(){
   int n;
n=NumClusters;
NumClusters++;
return n;
}

//***************************************************************************
// EucNorm                                                                  *
//   Returns the Euclidian norm between a pattern, p, and a cluster         *
//   center,c-1 he first K vectors to do this                               *
//***************************************************************************

double VQsyst::EucNorm(int p, int c){   // Calc Euclidean norm of vector difference
double dist;                            // between pattern vector, p, and cluster
int i;                                  // center, c.
dist=0;
for (i=0; i<SizeVector ;i++){
   dist += (Cluster[c].Center[i]-Pattern[p][i])*(Cluster[c].Center[i]-Pattern[p][i]);
   } /* endfor */
return dist;
}


//***************************************************************************
// Find ClosestCluster                                                      *
//   Returns the index of the cluster to which the pattern, pat, has the    *
//   closest Euclidean distance.                                            *
//***************************************************************************

int VQsyst::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);
   if (d<MinDist) {
      MinDist=d;
      ClustID=i;
      } /* endif */
   } /* endfor */
if (ClustID<0) {
   printf("No Clusters exist ");
   fprintf(OutFile,"No Clusters exist ");
   } /* endif */
return ClustID;
}


//***************************************************************************
// Attach                                                                   *
//   Adds the pattern (whose index is p) to the cluster center whose index  *
//   is p.                                                                  *
//***************************************************************************

void VQsyst::Attach(int c,int p){
int MemberIndex;

   MemberIndex=Cluster[c].NumMembers;
   Cluster[c].Member[MemberIndex]=p;
   Cluster[c].NumMembers++;
}


//***************************************************************************
// CalcNewClustCenter                                                       *
//   Calculate a new cluster center for the specified cluster,c             *
//                                                                          *
//***************************************************************************

void VQsyst::CalcNewClustCenter(int c){
   int VectID,j,k;
   double tmp[MAXVECTDIM];

   for (j=0; j<SizeVector; j++) {            // clear workspace
      tmp[j]=0.0;
      } /* endfor */
   for (j=0; j<Cluster[c].NumMembers; j++) { //traverse member vectors
      VectID=Cluster[c].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[c].NumMembers;
      Cluster[c].Center[k]=tmp[k];
      } /* endfor */
}


//***************************************************************************
// ShowClusters                                                             *
//   Display the cluster centers for each of the allocated clusters         *
//                                                                          *
//***************************************************************************

void VQsyst::ShowClusters(){
   int cl,i;
printf("\nThe new cluster centers are:");
fprintf(OutFile,"\nThe new cluster centers are:");
for (cl=0; cl<NumClusters; cl++) {
   printf("\nCLUSTER %d ==>[%f,%f]", cl,Cluster[cl].Center[0],Cluster[cl].Center[1]);
   fprintf(OutFile,"\nCLUSTER %d ==>[%f,%f]", cl,Cluster[cl].Center[0],Cluster[cl].Center[1]);
   } /* endfor */
printf("\nCLUSTER Membership");
fprintf(OutFile,"\nCLUSTER Membership");
for (cl=0; cl<NumClusters; cl++) {
   printf("\n  Cluster %d ==>{",cl);
   fprintf(OutFile,"\n  Cluster %d ==>{",cl);
   for (i=0; i<Cluster[cl].NumMembers; i++) {
      printf("%d ",Cluster[cl].Member[i]);
      fprintf(OutFile,"%d ",Cluster[cl].Member[i]);
      } /* endfor */
   printf("}\n");
   fprintf(OutFile,"}\n");
   } /* endfor */

}


//***************************************************************************
// SaveClusters                                                             *
//   Store the cluster centers for each of the allocated clusters           *
//   to the designated file                                                 *
//***************************************************************************

void VQsyst::SaveClusters(char *fname){
   FILE *OutFilePtr;
   int cl;
if((OutFilePtr = fopen(fname, "r")) == NULL){
    printf("Unable to open file %s for output",fname);
    }
  else {
   for (cl=0; cl<NumClusters; cl++) {
      fprintf(OutFilePtr,"\nCLUSTER %d ==>[%f,%f]\n",
              cl,Cluster[cl].Center[0],Cluster[cl].Center[1]);
      } /* endfor */
   fclose(OutFilePtr);
   }
}


//***************************************************************************
// Main                                                                     *
//                                                                          *
//                                                                          *
//***************************************************************************

main(int argc, char *argv[]) {
   VQsyst VQ;
if (argc<3) {
   printf("USAGE: VQ PATTERN_FILE(input) CLUSTER_FILE(output)\n");
   exit(0);
   }

if (VQ.InitOutput(argv[2])==FAILURE)
   exit (0);
if (VQ.LoadPatterns(argv[1])==FAILURE ){
   printf("UNABLE TO READ PATTERN_FILE:%s\n",argv[1]);
   exit(0);
   }
VQ.RunVQ();
}