clustermanager.cpp

Go to the documentation of this file.

//----------------------------------------------------------------------
//      File:           clustermanager.cpp
//      Description:    k-means Clustering Algorithm
//----------------------------------------------------------------------

//-----------k-means Clustering Algorithm--------------------
/* input : database D of m records r(1) to r(m) and a desired number of clusters k

   output : Set of k cluters( i.e. their centers) with minimum squared error
     begin:
        1. Randomly choose k records as centroids for k clusters
        2. repeat
            2.1 Assign each record r(i), to a cluster such that the distance between r(i) and the cluster centroid( mean) is the smallest among the k clusters;
            2.2 Recalculate the centroid(mean) for each cluster based on the records assigned to the cluster until no change end;


Distance(r(j),r(k)) = sqrt(sqr(|r(j1)-r(k1)|)+
                sqr(|r(j2)-r(k2)|)+
                sqr(|r(j3)-r(k3)|)+....+
                sqr(|r(jn)-r(kn)|)
*/

using namespace std;   // so as to make std available

//include files

#include <iostream>   // for enabling input output streams
#include <unistd.h>   // for file IO
#include <stdio.h>    // for standard IO
#include <cstring>    // for string functionality
#include <cstdlib>    // C standard library routines
#include <fcntl.h>    // manipulate the file descriptor
#include <cmath>      // math routines
#include <string>     // string manipulations   
#include <vector>     // vector manipulations
#include <iterator>   // using iterators for STL support

#ifndef FRAMEMFCCTABLEINCLUDED
#include "framemfcctable.cpp"
#endif

#ifndef REPOSITORYMANAGERINCLUDED
#include "repositorymanager.cpp"
#endif

#ifndef FRAMEINCLUDED
#include "frame.cpp"
#endif

#ifndef PARAMETERSINCLUDED
#include "parameters.cpp"
#endif

#define CLUSTERMANAGERINCLUDED

/* The class clustermanager contains all the data structures needed to store the data points and the cluster centroids and also the functionality that implements the k-means clustering algorithm*/

class clustermanager
{
        // data members
private:
        long int current;
        vector<double> dist;                      // distance of each cluster center from the current data point
        vector<double> centroid;                  //stores the MFCC parameters of a particular cluster center.
        vector<vector<double> > cluster_centers;  // centers of the clusters
        vector<unsigned long int> indices;        //indices of frames (in mfcc table) to be added to the repository
        vector<int> count;                        // count of members in each cluster currently

public :

  framemfcctable fmtbl; //avoiding wrapper functions

  // the class functionality

  clustermanager() // constuctor for the clustermanager class
  {
   int i;
    for(i=0;i<k;i++)
    {
       dist.push_back(0); // initialising the distance array
       count.push_back(0);    
    }
       current=0;
  }


  void showcenters()
  {
    int i,j;
    cout<<"\n Cluster centers are ";
    for(i=0;i<k;i++)
    {
      for(j=0;j<MAX_DIM;j++)
      {
        cout<< "\t" << cluster_centers[i][j];
      }
    cout<< "\n";
    }
  }



// This function 'initialize()' selects the first k data points as the random cluster centroids.

  int initcentroids(int iter)
  {
    unsigned int i,j;
    vector<double> temp;
        int status=SUCCESS;
    //    vector<int>::iterator  i1=count.begin();
    srand(i);
    for(i=0;i<k;i++) 
    {
      if(!iter)
        {
 j=(int) ((float)fmtbl.nFrames()*rand()/(RAND_MAX+1.0));
           temp=fmtbl.getFrameMFCC(j,&status);
        cluster_centers.push_back(temp);
        }
count[i]=0;//(iter==0)?1:0;

    }
    current=0;//(iter==0)?k:0;
    return SUCCESS;
  }

  int start()
  {
    int iter;
    for(iter=0;iter<NO_OF_ITER;iter++)
    {
      initcentroids(iter);
      while(distance())
      {
        recalculate1(minimum());
        current++; 
      }
    }
    return SUCCESS;
  }

  // The function 'distance()' calculates the distance between the current data point and the k cluster centroids.
  //m is the index of the data point in the input file

  int  distance()
  {
    int j,i;
    int status=SUCCESS;
    double temp=0.0;
    vector<double> cur_mfcc; 
    cur_mfcc=fmtbl.getFrameMFCC(current,&status);
    if(!status)
      return FAILURE;
    for(i=0;i<k;i++)
    {
      temp=0;
      for(j=0;j<MAX_DIM;j++)
      {
        temp+=(cur_mfcc[j]-cluster_centers[i][j])*(cur_mfcc[j]-cluster_centers[i][j]);
      }
      temp=sqrt(temp);
      dist[i]=temp;
    }
    return SUCCESS;
  }



  int  distance(vector<double> mfcc)
  {
    int j,i;
    int status=SUCCESS;
    double temp=0.0; 
    for(i=0;i<k;i++)
    {
      temp=0;
      for(j=0;j<MAX_DIM;j++)
      {
        temp+=(mfcc[j]-cluster_centers[i][j])*(mfcc[j]-cluster_centers[i][j]);
      }
      temp=sqrt(temp);
      dist[i]=temp;
    }
    return SUCCESS;
  }



  int minimum()
  {
    int i,pos=0;
    double least=dist[0];
    for(i=0;i<k;i++)
      if(dist[i]<least)
      {
        least=dist[i];
        pos=i;
      }
    return pos;
  }

  int recalculate1(int min)
  {
    int i;
    int status=SUCCESS;
    vector<double> cur_mfcc; 
    cur_mfcc=fmtbl.getFrameMFCC(current,&status);
    if(!status)
      return FAILURE;
    count[min]++;
    for(i=0;i<MAX_DIM;i++)
    {
    cluster_centers[min][i]=(cluster_centers[min][i]*(count[min]-1)+cur_mfcc[i])/(float)count[min];
    }
    return SUCCESS;
  }

  vector<unsigned long int> getIndices(void)
  {
    unsigned long int pos=0;
    vector<double> cur_mfcc;
    int status=SUCCESS;
    double temp=0,oldtemp;
    int i;
    frame  frptr;
    string framename;
    for(i=0;i<k;i++)
    {
      pos=0;
      oldtemp=VERY_HIGH_VALUE;
      indices.push_back(i);
      cur_mfcc= fmtbl.getFrameMFCC(pos,&status);
      while(status)
      {
        temp=0; 
        for(int j=0;j<MAX_DIM;j++)
        {
          temp+=(cur_mfcc[j]-cluster_centers[i][j])*(cur_mfcc[j]-cluster_centers[i][j]);
        }
        temp=sqrt(temp);
        if(temp<oldtemp)
        {
          indices[i]=pos;
          oldtemp=temp;
        }
        pos++;
        cur_mfcc= fmtbl.getFrameMFCC(pos,&status);
      }
    }
    return indices;
  }
    //indices is now filled with the indices of the framemfcctable for the frames to be made permanent in the repository.

  vector<vector<double> >  getcentroids(void)
  {
     return cluster_centers; //theoretical value of cluster centers
  }

  //gets the cluster centers from the codebook which is being managed by repositorymanager
  int getallclustercenters(string email)
  { 
    repositorymanager repmgr(email);
    for(unsigned int i=0;i<k;i++)
    {
      cluster_centers.push_back(repmgr.getClusterCenter(i));
    }
    return SUCCESS;
  }

  unsigned int compare(vector<double> mfcc)
  {
    distance(mfcc);
    return  minimum();
  }


};

---