NICE_VisLearning/math/cluster/RandomClustering.cpp

/**
 * @file RandomClustering.cpp
* @brief Clustering by randomly picking some samples from the set of features as representatives
* @author Alexander Freytag
* @date 03-06-2013 (dd-mm-yyyy)
 */

#ifdef NICE_USELIB_OPENMP
#include <omp.h>
#endif

#include <iostream>
#include <map>

#include "vislearning/math/distances/genericDistance.h"

#include "vislearning/math/cluster/RandomClustering.h"

#include <set>

using namespace OBJREC;

using namespace std;

using namespace NICE;



RandomClustering::RandomClustering(const int & _noClusters, const std::string & _distanceType) :
  noClusters(_noClusters), distanceType(_distanceType)
{
}

RandomClustering::RandomClustering( const NICE::Config *conf, const std::string & _section)
{  
  this->noClusters = conf->gI( _section, "noClusters", 20);
  
  this->distanceType = conf->gS( _section, "distanceType", "euclidean" );
  this->distancefunction = GenericDistanceSelection::selectDistance(distanceType);  
}

RandomClustering::~RandomClustering()
{
}

int RandomClustering::compute_prototypes(const NICE::VVector & _features, NICE::VVector & _prototypes,
    std::vector<double> & _weights, const std::vector<int> & _assignment)
{
  
  int noFeatures ( _features.size() );
  
  std::set<int, std::greater<int> > chosenIdx;
  
  //empty init
  chosenIdx.clear();
  
  //pick k distinct cluster representatives randomly
  for (int cnt = 0; cnt < this->noClusters; cnt++)
  {
    int idx;
    do
    {
      idx = rand() % noFeatures;
    }
    while ( chosenIdx.find ( idx ) != chosenIdx.end() );
                             
    //if a new (distinct) idx was computed, insert it into the set of randomly picked indicees
    chosenIdx.insert ( idx );
  }
  
  _prototypes.resize( this->noClusters ); 
  
  int clusterCnt ( 0 );
  for ( std::set<int>::const_iterator idxIt = chosenIdx.begin(); idxIt != chosenIdx.end(); idxIt++, clusterCnt++ )
  {
     _prototypes[clusterCnt] = _features[ *idxIt ];
  }

  return 0;
}

double RandomClustering::compute_assignments(const NICE::VVector & _features,
                                    const NICE::VVector & _prototypes,
                                    std::vector<int> & _assignment)
{
  _assignment.resize( _features.size() );
  
  int index = 0;
  for (NICE::VVector::const_iterator i = _features.begin(); i != _features.end(); i++, index++)
  {

    const NICE::Vector & x = *i;
    double mindist = std::numeric_limits<double>::max();
    int minclass = 0;

    int c = 0;
           
    for (NICE::VVector::const_iterator j = _prototypes.begin(); j
        != _prototypes.end(); j++, c++)
    {

      const NICE::Vector & p = *j;
      double distance = this->distancefunction->calculate(p, x);
      
      if (distance < mindist)
      {
        minclass = c;
        mindist = distance;
      }
    }

    _assignment[index] = minclass;
  }

  return 0.0;
}

double RandomClustering::compute_weights(const NICE::VVector & _features,
                                std::vector<double> & _weights,
                                std::vector<int> & _assignment)
{
  _weights.resize( this->noClusters );
  
  //initalization
  for (int k = 0; k < noClusters; k++)
    _weights[k] = 0;

  int j = 0;

  //increase weight for every assignment
  for (NICE::VVector::const_iterator i = _features.begin(); i != _features.end(); i++, j++)
  {
    int k = _assignment[j];
    _weights[k]++;
  }

  //normalize weights
  for (int k = 0; k < noClusters; k++)
    _weights[k] = _weights[k] / _features.size();

  return 0.0;
}

void RandomClustering::cluster(const NICE::VVector & _features,
                      NICE::VVector & _prototypes,
                      std::vector<double> & _weights,
                      std::vector<int> & _assignment)
{
  //randomly pick cluster centers
  this->compute_prototypes( _features, _prototypes, _weights, _assignment );
  
  //compute assignments for every cluster
  this->compute_assignments( _features, _prototypes, _assignment );
  
  //compute corresponding weights
  this->compute_weights( _features, _weights, _assignment );
}