RandomClustering.cpp 4.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158
  1. /**
  2. * @file RandomClustering.cpp
  3. * @brief Clustering by randomly picking some samples from the set of features as representatives
  4. * @author Alexander Freytag
  5. * @date 03-06-2013 (dd-mm-yyyy)
  6. */
  7. #ifdef NICE_USELIB_OPENMP
  8. #include <omp.h>
  9. #endif
  10. #include <iostream>
  11. #include <map>
  12. #include "vislearning/math/distances/genericDistance.h"
  13. #include "vislearning/math/cluster/RandomClustering.h"
  14. #include <set>
  15. using namespace OBJREC;
  16. using namespace std;
  17. using namespace NICE;
  18. RandomClustering::RandomClustering(const int & _noClusters, const std::string & _distanceType) :
  19. noClusters(_noClusters), distanceType(_distanceType)
  20. {
  21. }
  22. RandomClustering::RandomClustering( const NICE::Config *conf, const std::string & _section)
  23. {
  24. this->noClusters = conf->gI( _section, "noClusters", 20);
  25. std::cerr << "RandomClustering::RandomClustering -- noClusters: " << this->noClusters << std::endl;
  26. this->distanceType = conf->gS( _section, "distanceType", "euclidean" );
  27. this->distancefunction = GenericDistanceSelection::selectDistance(distanceType);
  28. }
  29. RandomClustering::~RandomClustering()
  30. {
  31. }
  32. int RandomClustering::compute_prototypes(const NICE::VVector & _features, NICE::VVector & _prototypes,
  33. std::vector<double> & _weights, const std::vector<int> & _assignment)
  34. {
  35. int noFeatures ( _features.size() );
  36. std::set<int, std::greater<int> > chosenIdx;
  37. //empty init
  38. chosenIdx.clear();
  39. //pick k distinct cluster representatives randomly
  40. for (int cnt = 0; cnt < this->noClusters; cnt++)
  41. {
  42. int idx;
  43. do
  44. {
  45. idx = rand() % noFeatures;
  46. }
  47. while ( chosenIdx.find ( idx ) != chosenIdx.end() );
  48. //if a new (distinct) idx was computed, insert it into the set of randomly picked indicees
  49. chosenIdx.insert ( idx );
  50. }
  51. _prototypes.resize( this->noClusters );
  52. int clusterCnt ( 0 );
  53. for ( std::set<int>::const_iterator idxIt = chosenIdx.begin(); idxIt != chosenIdx.end(); idxIt++, clusterCnt++ )
  54. {
  55. _prototypes[clusterCnt] = _features[ *idxIt ];
  56. }
  57. return 0;
  58. }
  59. double RandomClustering::compute_assignments(const NICE::VVector & _features,
  60. const NICE::VVector & _prototypes,
  61. std::vector<int> & _assignment)
  62. {
  63. _assignment.resize( _features.size() );
  64. int index = 0;
  65. for (NICE::VVector::const_iterator i = _features.begin(); i != _features.end(); i++, index++)
  66. {
  67. const NICE::Vector & x = *i;
  68. double mindist = std::numeric_limits<double>::max();
  69. int minclass = 0;
  70. int c = 0;
  71. for (NICE::VVector::const_iterator j = _prototypes.begin(); j
  72. != _prototypes.end(); j++, c++)
  73. {
  74. const NICE::Vector & p = *j;
  75. double distance = this->distancefunction->calculate(p, x);
  76. if (distance < mindist)
  77. {
  78. minclass = c;
  79. mindist = distance;
  80. }
  81. }
  82. _assignment[index] = minclass;
  83. }
  84. return 0.0;
  85. }
  86. double RandomClustering::compute_weights(const NICE::VVector & _features,
  87. std::vector<double> & _weights,
  88. std::vector<int> & _assignment)
  89. {
  90. _weights.resize( this->noClusters );
  91. //initalization
  92. for (int k = 0; k < noClusters; k++)
  93. _weights[k] = 0;
  94. int j = 0;
  95. //increase weight for every assignment
  96. for (NICE::VVector::const_iterator i = _features.begin(); i != _features.end(); i++, j++)
  97. {
  98. int k = _assignment[j];
  99. _weights[k]++;
  100. }
  101. //normalize weights
  102. for (int k = 0; k < noClusters; k++)
  103. _weights[k] = _weights[k] / _features.size();
  104. return 0.0;
  105. }
  106. void RandomClustering::cluster(const NICE::VVector & _features,
  107. NICE::VVector & _prototypes,
  108. std::vector<double> & _weights,
  109. std::vector<int> & _assignment)
  110. {
  111. //randomly pick cluster centers
  112. this->compute_prototypes( _features, _prototypes, _weights, _assignment );
  113. //compute assignments for every cluster
  114. this->compute_assignments( _features, _prototypes, _assignment );
  115. //compute corresponding weights
  116. this->compute_weights( _features, _weights, _assignment );
  117. }