GestureRecognitionToolkit  Version: 1.0 Revision: 04-03-15
The Gesture Recognition Toolkit (GRT) is a cross-platform, open-source, c++ machine learning library for real-time gesture recognition.
KMeans.cpp
1 /*
2  GRT MIT License
3  Copyright (c) <2012> <Nicholas Gillian, Media Lab, MIT>
4 
5  Permission is hereby granted, free of charge, to any person obtaining a copy of this software
6  and associated documentation files (the "Software"), to deal in the Software without restriction,
7  including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense,
8  and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so,
9  subject to the following conditions:
10 
11  The above copyright notice and this permission notice shall be included in all copies or substantial
12  portions of the Software.
13 
14  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
15  LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
16  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
17  WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
18  SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
19  */
20 
21 #include "KMeans.h"
22 
23 namespace GRT{
24 
25 //Register the KMeans class with the Clusterer base class
26 RegisterClustererModule< KMeans > KMeans::registerModule("KMeans");
27 
28 //Constructor,destructor
29 KMeans::KMeans(const UINT numClusters,const UINT minNumEpochs,const UINT maxNumEpochs,const double minChange,const bool computeTheta){
30 
31  this->numClusters = numClusters;
32  this->minNumEpochs = minNumEpochs;
33  this->maxNumEpochs = maxNumEpochs;
34  this->minChange = minChange;
35  this->computeTheta = computeTheta;
36 
38  nchg = 0;
39  finalTheta = 0;
40  numTrainingIterationsToConverge = 0;
41  trained = false;
42 
43  classType = "KMeans";
44  clustererType = classType;
45  debugLog.setProceedingText("[DEBUG KMeans]");
46  errorLog.setProceedingText("[ERROR KMeans]");
47  trainingLog.setProceedingText("[TRAINING KMeans]");
48  warningLog.setProceedingText("[WARNING KMeans]");
49 }
50 
51 KMeans::KMeans(const KMeans &rhs){
52 
53  classType = "KMeans";
54  clustererType = classType;
55  debugLog.setProceedingText("[DEBUG KMeans]");
56  errorLog.setProceedingText("[ERROR KMeans]");
57  trainingLog.setProceedingText("[TRAINING KMeans]");
58  warningLog.setProceedingText("[WARNING KMeans]");
59 
60  if( this != &rhs ){
61 
63  this->nchg = rhs.nchg;
64  this->computeTheta = rhs.computeTheta;
65  this->finalTheta = rhs.finalTheta;
66  this->clusters = rhs.clusters;
67  this->assign = rhs.assign;
68  this->count = rhs.count;
69  this->thetaTracker = rhs.thetaTracker;
70 
71  //Clone the Clusterer variables
72  copyBaseVariables( (Clusterer*)&rhs );
73  }
74 
75 }
76 
78 }
79 
81 
82  if( this != &rhs ){
83 
85  this->nchg = rhs.nchg;
86  this->computeTheta = rhs.computeTheta;
87  this->finalTheta = rhs.finalTheta;
88  this->clusters = rhs.clusters;
89  this->assign = rhs.assign;
90  this->count = rhs.count;
91  this->thetaTracker = rhs.thetaTracker;
92 
93  //Clone the Clusterer variables
94  copyBaseVariables( (Clusterer*)&rhs );
95  }
96 
97  return *this;
98 }
99 
100 bool KMeans::deepCopyFrom(const Clusterer *clusterer){
101 
102  if( clusterer == NULL ) return false;
103 
104  if( this->getClustererType() == clusterer->getClustererType() ){
105  //Clone the KMeans values
106  KMeans *ptr = (KMeans*)clusterer;
107 
109  this->nchg = ptr->nchg;
110  this->computeTheta = ptr->computeTheta;
111  this->finalTheta = ptr->finalTheta;
112  this->clusters = ptr->clusters;
113  this->assign = ptr->assign;
114  this->count = ptr->count;
115  this->thetaTracker = ptr->thetaTracker;
116 
117  //Clone the Clusterer variables
118  return copyBaseVariables( clusterer );
119  }
120  return false;
121 }
122 
123 bool KMeans::train_(ClassificationData &trainingData){
124 
125  if( trainingData.getNumSamples() == 0 ){
126  errorLog << "train_(ClassificationData &trainingData) - The training data is empty!" << endl;
127  return false;
128  }
129 
130  //Set the numClusters as the number of classes in the training data
131  numClusters = trainingData.getNumClasses();
132 
133  //Convert the labelled training data to a training matrix
134  UINT M = trainingData.getNumSamples();
135  UINT N = trainingData.getNumDimensions();
136  MatrixDouble data(M,N);
137  for(UINT i=0; i<M; i++){
138  for(UINT j=0; j<N; j++){
139  data[i][j] = trainingData[i][j];
140  }
141  }
142 
143  //Run the K-Means algorithm
144  return train_( data );
145 }
146 
147 bool KMeans::train_(UnlabelledData &trainingData){
148 
149  //Convert the training data into one matrix
150  UINT M = trainingData.getNumSamples();
151  UINT N = trainingData.getNumDimensions();
152  MatrixDouble data(M,N);
153  for(UINT i=0; i<M; i++){
154  for(UINT j=0; j<N; j++){
155  data[i][j] = trainingData[i][j];
156  }
157  }
158 
159  return train_(data);
160 }
161 
163 
164  trained = false;
165 
166  if( numClusters == 0 ){
167  errorLog << "train_(MatrixDouble &data) - Failed to train model. NumClusters is zero!" << endl;
168  return false;
169  }
170 
171  if( data.getNumRows() == 0 || data.getNumCols() == 0 ){
172  errorLog << "train_(MatrixDouble &data) - The number of rows or columns in the data is zero!" << endl;
173  return false;
174  }
175 
177  numInputDimensions = data.getNumCols();
178 
179  clusters.resize(numClusters,numInputDimensions);
180  assign.resize(numTrainingSamples);
181  count.resize(numClusters);
182 
183  //Randomly pick k data points as the starting clusters
184  Random random;
185  vector< UINT > randIndexs(numTrainingSamples);
186  for(UINT i=0; i<numTrainingSamples; i++) randIndexs[i] = i;
187  std::random_shuffle(randIndexs.begin(), randIndexs.end());
188 
189  //Copy the clusters
190  for(UINT k=0; k<numClusters; k++){
191  for(UINT j=0; j<numInputDimensions; j++){
192  clusters[k][j] = data[ randIndexs[k] ][j];
193  }
194  }
195 
196  return trainModel( data );
197 }
198 
199 bool KMeans::predict_(VectorDouble &inputVector){
200 
201  if( !trained ){
202  return false;
203  }
204 
205  if( inputVector.size() != numInputDimensions ){
206  return false;
207  }
208 
209  if( useScaling ){
210  for(UINT n=0; n<numInputDimensions; n++){
211  inputVector[n] = scale(inputVector[n], ranges[n].minValue, ranges[n].maxValue, 0, 1);
212  }
213  }
214 
215  const double sigma = 1.0;
216  const double gamma = 1.0 / (2*SQR(sigma));
217  double sum = 0;
218  double dist = 0;
219  UINT minIndex = 0;
220  bestDistance = numeric_limits<double>::max();
222  maxLikelihood = 0;
223  if( clusterLikelihoods.size() != numClusters )
224  clusterLikelihoods.resize( numClusters );
225  if( clusterDistances.size() != numClusters )
226  clusterDistances.resize( numClusters );
227 
228  for(UINT i=0; i<numClusters; i++){
229 
230  //We don't need to compute the sqrt as it works without it and is faster
231  dist = 0;
232  for(UINT j=0; j<numInputDimensions; j++){
233  dist += SQR( inputVector[j]-clusters[i][j] );
234  }
235 
236  clusterDistances[i] = dist;
237  clusterLikelihoods[i] = exp( - SQR(gamma * dist) ); //1.0/(1.0+dist); //This will give us a value close to 1 for a dist of 0, and a value closer to 0 when the dist is large
238 
239  sum += clusterLikelihoods[i];
240 
241  if( dist < bestDistance ){
242  bestDistance = dist;
243  minIndex = i;
244  }
245  }
246 
247  //Normalize the likelihood
248  for(UINT i=0; i<numClusters; i++){
249  clusterLikelihoods[i] /= sum;
250  }
251 
252  predictedClusterLabel = clusterLabels[ minIndex ];
253  maxLikelihood = clusterLikelihoods[ minIndex ];
254 
255  return true;
256 }
257 
259 
260  if( numClusters == 0 ){
261  errorLog << "trainModel(MatrixDouble &data) - Failed to train model. NumClusters is zero!" << endl;
262  return false;
263  }
264 
265  if( clusters.getNumRows() != numClusters ){
266  errorLog << "trainModel(MatrixDouble &data) - Failed to train model. The number of rows in the cluster matrix does not match the number of clusters! You should need to initalize the clusters matrix first before calling this function!" << endl;
267  return false;
268  }
269 
270  if( clusters.getNumCols() != numInputDimensions ){
271  errorLog << "trainModel(MatrixDouble &data) - Failed to train model. The number of columns in the cluster matrix does not match the number of input dimensions! You should need to initalize the clusters matrix first before calling this function!" << endl;
272  return false;
273  }
274 
275  Timer timer;
276  UINT currentIter = 0;
277  UINT numChanged = 0;
278  bool keepTraining = true;
279  double theta = 0;
280  double lastTheta = 0;
281  double delta = 0;
282  double startTime = 0;
283  thetaTracker.clear();
284  finalTheta = 0;
285  numTrainingIterationsToConverge = 0;
286  trained = false;
287  converged = false;
288 
289  //Scale the data if needed
290  ranges = data.getRanges();
291  if( useScaling ){
292  data.scale(0,1);
293  }
294 
295  //Init the assign and count vectors
296  //Assign is set to K+1 so that the nChanged values in the eStep at the first iteration will be updated correctly
297  for(UINT m=0; m<numTrainingSamples; m++) assign[m] = numClusters+1;
298  for(UINT k=0; k<numClusters; k++) count[k] = 0;
299 
300  //Run the training loop
301  timer.start();
302  while( keepTraining ){
303  startTime = timer.getMilliSeconds();
304 
305  //Compute the E step
306  numChanged = estep( data );
307 
308  //Compute the M step
309  mstep( data );
310 
311  //Update the iteration counter
312  currentIter++;
313 
314  //Compute theta if needed
315  if( computeTheta ){
316  theta = calculateTheta(data);
317  delta = lastTheta - theta;
318  lastTheta = theta;
319  }else theta = delta = 0;
320 
321  //Check convergance
322  if( numChanged == 0 && currentIter > minNumEpochs ){ converged = true; keepTraining = false; }
323  if( currentIter >= maxNumEpochs ){ keepTraining = false; }
324  if( fabs( delta ) < minChange && computeTheta && currentIter > minNumEpochs ){ converged = true; keepTraining = false; }
325  if( computeTheta ) thetaTracker.push_back( theta );
326 
327  trainingLog << "Epoch: " << currentIter << "/" << maxNumEpochs;
328  trainingLog << " Epoch time: " << (timer.getMilliSeconds()-startTime)/1000.0 << " seconds";
329  trainingLog << " Theta: " << theta << " Delta: " << delta << endl;
330  }
331  trainingLog << "Model Trained at epoch: " << currentIter << " with a theta value of: " << theta << endl;
332 
333  finalTheta = theta;
334  numTrainingIterationsToConverge = currentIter;
335  trained = true;
336 
337  //Setup the cluster labels
338  clusterLabels.resize(numClusters);
339  for(UINT i=0; i<numClusters; i++){
340  clusterLabels[i] = i+1;
341  }
342  clusterLikelihoods.resize(numClusters,0);
343  clusterDistances.resize(numClusters,0);
344 
345  return true;
346 }
347 
348 UINT KMeans::estep(const MatrixDouble &data) {
349  UINT k,m,n,kmin;
350  double dmin,d;
351  nchg = 0;
352  kmin = 0;
353 
354  //Reset Count
355  for (k=0; k < numClusters; k++) count[k] = 0;
356 
357  //Search for the closest center and reasign if needed
358  for (m=0; m < numTrainingSamples; m++) {
359  dmin = 9.99e+99; //Set dmin to a really big value
360  for (k=0; k < numClusters; k++) {
361  d = 0.0;
362  for (n=0; n < numInputDimensions; n++)
363  d += SQR( data[m][n]-clusters[k][n] );
364  if (d <= dmin){ dmin = d; kmin = k; }
365  }
366  if ( kmin != assign[m] ){
367  nchg++;
368  assign[m] = kmin;
369  }
370  count[kmin]++;
371  }
372  return nchg;
373 }
374 
375 void KMeans::mstep(const MatrixDouble &data) {
376  UINT n,k,m;
377 
378  //Reset means to zero
379  for (k=0; k<numClusters; k++)
380  for (n=0;n<numInputDimensions;n++)
381  clusters[k][n] = 0.;
382 
383  //Get new mean by adding assigned data points and dividing by the number of values in each cluster
384  for(m=0; m < numTrainingSamples; m++)
385  for(n=0; n < numInputDimensions; n++)
386  clusters[ assign[m] ][n] += data[m][n];
387 
388  for (k=0; k < numClusters; k++) {
389  if (count[k] > 0){
390  for (n=0; n < numInputDimensions; n++){
391  clusters[k][n] /= double(count[k]);
392  }
393  }
394  }
395 }
396 
397 double KMeans::calculateTheta(const MatrixDouble &data){
398 
399  double theta = 0;
400  double sum = 0;
401  UINT m,n,k = 0;
402  for(m=0; m < numTrainingSamples; m++){
403  k = assign[m];
404  sum = 0;
405  for(n=0; n < numInputDimensions; n++){
406  sum += SQR(clusters[k][n] - data[m][n]);
407  }
408  theta += sqrt(sum);
409  }
410  theta /= numTrainingSamples;
411 
412  return theta;
413 
414 }
415 
416 bool KMeans::saveModelToFile(fstream &file) const{
417 
418  if( !file.is_open() ){
419  errorLog << "saveModelToFile(fstream &file) - Failed to save model, file is not open!" << endl;
420  return false;
421  }
422 
423  file << "GRT_KMEANS_MODEL_FILE_V1.0\n";
424 
425  if( !saveClustererSettingsToFile( file ) ){
426  errorLog << "saveModelToFile(fstream &file) - Failed to save clusterer settings to file!" << endl;
427  return false;
428  }
429 
430  if( trained ){
431  file << "Clusters:\n";
432 
433  for(UINT k=0; k<numClusters; k++){
434  for(UINT n=0; n<numInputDimensions; n++){
435  file << clusters[k][n] << "\t";
436  }file << endl;
437  }
438  }
439 
440  return true;
441 
442 }
443 
444 bool KMeans::loadModelFromFile(fstream &file){
445 
446  //Clear any previous model
447  clear();
448 
449  if(!file.is_open()){
450  errorLog << "loadModelFromFile(string filename) - Failed to open file!" << endl;
451  return false;
452  }
453 
454  string word;
455  file >> word;
456  if( word != "GRT_KMEANS_MODEL_FILE_V1.0" ){
457  return false;
458  }
459 
460  if( !loadClustererSettingsFromFile( file ) ){
461  errorLog << "loadModelFromFile(string filename) - Failed to open file!" << endl;
462  return false;
463  }
464 
465  if( trained ){
466  file >> word;
467  if( word != "Clusters:" ){
468  return false;
469  }
470 
471  //Resize the buffers
472  clusters.resize(numClusters,numInputDimensions);
473 
474  //Load the data
475  for(UINT k=0; k<numClusters; k++){
476  for(UINT n=0; n<numInputDimensions; n++){
477  file >> clusters[k][n];
478  }
479  }
480  }
481 
482  return true;
483 }
484 
487 
488  numTrainingSamples = 0;
489  nchg = 0;
490  finalTheta = 0;
491  thetaTracker.clear();
492  assign.clear();
493  count.clear();
494 
495  return true;
496 }
497 
500 
501  numTrainingSamples = 0;
502  nchg = 0;
503  finalTheta = 0;
504  thetaTracker.clear();
505  assign.clear();
506  count.clear();
507  clusters.clear();
508 
509  return true;
510 }
511 
512 bool KMeans::setComputeTheta(const bool computeTheta){
513  this->computeTheta = computeTheta;
514  return true;
515 }
516 
517 bool KMeans::setClusters(const MatrixDouble &clusters){
518  clear();
519  numClusters = clusters.getNumRows();
520  numInputDimensions = clusters.getNumCols();
521  this->clusters = clusters;
522  return true;
523 }
524 
525 
526 }//End of namespace GRT
UINT getNumSamples() const
virtual bool clear()
Definition: KMeans.cpp:498
virtual bool reset()
Definition: KMeans.cpp:485
virtual bool clear()
Definition: Clusterer.cpp:139
bool loadClustererSettingsFromFile(fstream &file)
Definition: Clusterer.cpp:176
UINT numTrainingSamples
Number of training examples.
Definition: KMeans.h:190
KMeans & operator=(const KMeans &rhs)
Definition: KMeans.cpp:80
Definition: AdaBoost.cpp:25
virtual bool reset()
Definition: Clusterer.cpp:125
UINT numClusters
Number of clusters in the model.
Definition: Clusterer.h:249
unsigned int getNumCols() const
Definition: Matrix.h:538
virtual ~KMeans()
Definition: KMeans.cpp:77
bool scale(const double minTarget, const double maxTarget)
bool saveClustererSettingsToFile(fstream &file) const
Definition: Clusterer.cpp:154
KMeans(const UINT numClusters=10, const UINT minNumEpochs=5, const UINT maxNumEpochs=1000, const double minChange=1.0e-5, const bool computeTheta=true)
Definition: KMeans.cpp:29
virtual bool deepCopyFrom(const Clusterer *clusterer)
Definition: KMeans.cpp:100
bool copyBaseVariables(const Clusterer *Clusterer)
Definition: Clusterer.cpp:84
This class implements the KMeans clustering algorithm.
double scale(const double &x, const double &minSource, const double &maxSource, const double &minTarget, const double &maxTarget, const bool constrain=false)
Definition: MLBase.h:339
bool start()
Definition: Timer.h:59
signed long getMilliSeconds() const
Definition: Timer.h:100
string getClustererType() const
Definition: Clusterer.cpp:257
void clear()
Definition: Matrix.h:511
bool trainModel(MatrixDouble &data)
Definition: KMeans.cpp:258
virtual bool saveModelToFile(fstream &file) const
Definition: KMeans.cpp:416
virtual bool train_(MatrixDouble &data)
Definition: KMeans.cpp:162
unsigned int getNumRows() const
Definition: Matrix.h:531
UINT getNumDimensions() const
bool setClusters(const MatrixDouble &clusters)
Definition: KMeans.cpp:517
virtual bool predict_(VectorDouble &inputVector)
Definition: KMeans.cpp:199
virtual bool loadModelFromFile(fstream &file)
Definition: KMeans.cpp:444
std::vector< MinMax > getRanges() const
UINT nchg
Number of values changes.
Definition: KMeans.h:191
virtual bool resize(const unsigned int r, const unsigned int c)
Definition: Matrix.h:234
UINT predictedClusterLabel
Stores the predicted cluster label from the most recent predict( )
Definition: Clusterer.h:250