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.
HierarchicalClustering.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 "HierarchicalClustering.h"
22 
23 namespace GRT{
24 
25 //Register the HierarchicalClustering class with the Clusterer base class
26 RegisterClustererModule< HierarchicalClustering > HierarchicalClustering::registerModule("HierarchicalClustering");
27 
29  M = N = 0;
30  classType = "HierarchicalClustering";
31  clustererType = classType;
32  debugLog.setProceedingText("[DEBUG HierarchicalClustering]");
33  errorLog.setProceedingText("[ERROR HierarchicalClustering]");
34  trainingLog.setProceedingText("[TRAINING HierarchicalClustering]");
35  warningLog.setProceedingText("[WARNING HierarchicalClustering]");
36 }
37 
39  classType = "HierarchicalClustering";
40  clustererType = classType;
41  debugLog.setProceedingText("[DEBUG HierarchicalClustering]");
42  errorLog.setProceedingText("[ERROR HierarchicalClustering]");
43  trainingLog.setProceedingText("[TRAINING HierarchicalClustering]");
44  warningLog.setProceedingText("[WARNING HierarchicalClustering]");
45  *this = rhs;
46 }
47 
49 
50 }
51 
53 
54  if( this != &rhs ){
55 
56  this->M = rhs.M;
57  this->N = rhs.N;
58  this->clusters = rhs.clusters;
59  this->distanceMatrix = rhs.distanceMatrix;
60 
61  //Clone the Clusterer variables
62  copyBaseVariables( (Clusterer*)&rhs );
63  }
64 
65  return *this;
66 }
67 
69 
70  if( clusterer == NULL ) return false;
71 
72  if( this->getClustererType() == clusterer->getClustererType() ){
73  //Clone the HierarchicalClustering values
75 
76  this->M = ptr->M;
77  this->N = ptr->N;
78  this->clusters = ptr->clusters;
79  this->distanceMatrix = ptr->distanceMatrix;
80 
81  //Clone the Clusterer variables
82  return copyBaseVariables( clusterer );
83  }
84  return false;
85 }
86 
88 
90 
91  return true;
92 }
93 
95 
97 
98  M = 0;
99  N = 0;
100  clusters.clear();
101  distanceMatrix.clear();
102 
103  return true;
104 }
105 
107 
108  if( trainingData.getNumSamples() == 0 ){
109  return false;
110  }
111 
112  //Convert the labelled training data to a training matrix
113  M = trainingData.getNumSamples();
114  N = trainingData.getNumDimensions();
115 
116  MatrixDouble data(M,N);
117  for(UINT i=0; i<M; i++){
118  for(UINT j=0; j<N; j++){
119  data[i][j] = trainingData[i][j];
120  }
121  }
122 
123  return train_( data );
124 }
125 
127 
128  if( trainingData.getNumSamples() == 0 ){
129  return false;
130  }
131 
132  //Convert the training data into one matrix
133  M = trainingData.getNumSamples();
134  N = trainingData.getNumDimensions();
135 
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  return train( data );
144 }
145 
147 
148  trained = false;
149  clusters.clear();
150  distanceMatrix.clear();
151 
152  if( data.getNumRows() == 0 || data.getNumCols() == 0 ){
153  return false;
154  }
155 
156  //Set the rows and columns
157  M = data.getNumRows();
158  N = data.getNumCols();
159 
160  //Build the distance matrix
161  distanceMatrix.resize(M,M);
162 
163  //Build the distance matrix
164  for(UINT i=0; i<M; i++){
165  for(UINT j=0; j<M; j++){
166  if( i== j ) distanceMatrix[i][j] = numeric_limits<double>::max();
167  else{
168  distanceMatrix[i][j] = squaredEuclideanDistance(data[i], data[j]);
169  }
170  }
171  }
172 
173  //Build the initial clusters, at the start each sample gets its own cluster
174  UINT uniqueClusterID = 0;
175  vector< ClusterInfo > clusterData(M);
176  for(UINT i=0; i<M; i++){
177  clusterData[i].uniqueClusterID = uniqueClusterID++;
178  clusterData[i].addSampleToCluster(i);
179  }
180 
181  trainingLog << "Starting clustering..." << endl;
182 
183  //Create the first cluster level, each sample is it's own cluster
184  UINT level = 0;
185  ClusterLevel newLevel;
186  newLevel.level = level;
187  for(UINT i=0; i<M; i++){
188  newLevel.clusters.push_back( clusterData[i] );
189  }
190  clusters.push_back( newLevel );
191 
192  //Move to level 1 and start the search
193  level++;
194  bool keepClustering = true;
195 
196  while( keepClustering ){
197 
198  //Find the closest two clusters within the cluster data
199  double minDist = numeric_limits<double>::max();
200  vector< vector< UINT > > clusterPairs;
201  UINT K = (UINT)clusterData.size();
202  for(UINT i=0; i<K; i++){
203  for(UINT j=0; j<K; j++){
204  if( i != j ){
205  double dist = computeClusterDistance( clusterData[i], clusterData[j] );
206 
207  if( dist < minDist ){
208  minDist = dist;
209  vector< UINT > clusterPair(2);
210  clusterPair[0] = i;
211  clusterPair[1] = j;
212  clusterPairs.clear();
213  clusterPairs.push_back( clusterPair );
214  }
215 
216  }
217  }
218  }
219 
220  if( minDist == numeric_limits<double>::max() ){
221  keepClustering = false;
222  warningLog << "train_(MatrixDouble &data) - Failed to find any cluster at level: " << level << endl;
223  return false;
224  }else{
225 
226  //Merge the two closest clusters together and create a new level
227  ClusterLevel newLevel;
228  newLevel.level = level;
229 
230  //Create the new cluster
231  ClusterInfo newCluster;
232  newCluster.uniqueClusterID = uniqueClusterID++;
233 
234  const UINT numClusterPairs = (UINT)clusterPairs.size();
235 
236  for(UINT k=0; k<numClusterPairs; k++){
237  //Add all the samples in the first cluster to the new cluster
238  UINT numSamplesInClusterA = clusterData[ clusterPairs[k][0] ].getNumSamplesInCluster();
239  for(UINT i=0; i<numSamplesInClusterA; i++){
240  UINT index = clusterData[ clusterPairs[k][0] ][ i ];
241  newCluster.addSampleToCluster( index );
242  }
243 
244  //Add all the samples in the second cluster to the new cluster
245  UINT numSamplesInClusterB = clusterData[ clusterPairs[k][1] ].getNumSamplesInCluster();
246  for(UINT i=0; i<numSamplesInClusterB; i++){
247  UINT index = clusterData[ clusterPairs[k][1] ][ i ];
248  newCluster.addSampleToCluster( index );
249  }
250 
251  //Compute the cluster variance
252  newCluster.clusterVariance = computeClusterVariance( newCluster, data );
253 
254  //Remove the two cluster pairs (so they will not be used in the next search
255  UINT idA = clusterData[ clusterPairs[k][0] ].getUniqueClusterID();
256  UINT idB = clusterData[ clusterPairs[k][1] ].getUniqueClusterID();
257  UINT numRemoved = 0;
258  vector< ClusterInfo >::iterator iter = clusterData.begin();
259  while( iter != clusterData.end() ){
260  if( iter->getUniqueClusterID() == idA || iter->getUniqueClusterID() == idB ){
261  iter = clusterData.erase( iter );
262  if( ++numRemoved >= 2 ) break;
263  }else iter++;
264  }
265  }
266 
267  //Add the merged cluster to the clusterData
268  clusterData.push_back( newCluster );
269 
270  //Add the new level and cluster data to the main cluster buffer
271  newLevel.clusters.push_back( newCluster );
272 
273  clusters.push_back( newLevel );
274 
275  //Update the level
276  level++;
277  }
278 
279  //Check to see if we should stop clustering
280  if( level >= M ){
281  keepClustering = false;
282  }
283 
284  if( clusterData.size() == 0 ){
285  keepClustering = false;
286  }
287 
288  trainingLog << "Cluster level: " << level << " Number of clusters: " << clusters.back().getNumClusters() << endl;
289  }
290 
291  //Flag that the model is trained
292  trained = true;
293 
294  //Setup the cluster labels
295  clusterLabels.resize(numClusters);
296  for(UINT i=0; i<numClusters; i++){
297  clusterLabels[i] = i+1;
298  }
299  clusterLikelihoods.resize(numClusters,0);
300  clusterDistances.resize(numClusters,0);
301 
302  return true;
303 }
304 
305 bool HierarchicalClustering::printModel(){
306 
307  UINT K = (UINT)clusters.size();
308 
309  cout << "Hierarchical Clustering Model\n\n";
310  for(UINT k=0; k<K; k++){
311  UINT numClusters = clusters[k].getNumClusters();
312  UINT numSamples = 0;
313  for(UINT i=0; i<numClusters; i++){
314  numSamples += clusters[k][i].getNumSamplesInCluster();
315 
316  }
317 
318  cout << "Level: " << clusters[k].level << "\tNumClusters: " << numClusters << "\tNumSamples: " << numSamples << endl;
319  for(UINT i=0; i<numClusters; i++){
320  cout << "ClusterVariance: " << clusters[k][i].clusterVariance << endl;
321  cout << "Indexs: ";
322  UINT numSamplesInCluster = clusters[k][i].getNumSamplesInCluster();
323  for(UINT j=0; j<numSamplesInCluster; j++){
324  cout << clusters[k][i][j] << "\t";
325  }
326  cout << endl;
327  }
328  }
329 
330  return true;
331 }
332 
333 double HierarchicalClustering::squaredEuclideanDistance(const double *a,const double *b){
334  double dist = 0;
335  for(UINT i=0; i<N; i++){
336  dist += SQR( a[i] - b[i] );
337  }
338  return dist;
339 }
340 
341 double HierarchicalClustering::computeClusterDistance( const ClusterInfo &clusterA, const ClusterInfo &clusterB ){
342 
343  double minDist = numeric_limits<double>::max();
344  const UINT numSamplesA = clusterA.getNumSamplesInCluster();
345  const UINT numSamplesB = clusterB.getNumSamplesInCluster();
346 
347  //Find the minimum distance between the two clusters
348  for(UINT i=0; i<numSamplesA; i++){
349  for(UINT j=0; j<numSamplesB; j++){
350  if( distanceMatrix[ clusterA[i] ][ clusterB[j] ] < minDist ){
351  minDist = distanceMatrix[ clusterA[i] ][ clusterB[j] ];
352  }
353  }
354  }
355 
356  return minDist;
357 }
358 
359 double HierarchicalClustering::computeClusterVariance( const ClusterInfo &cluster, const MatrixDouble &data ){
360 
361  VectorDouble mean(N,0);
362  VectorDouble std(N,0);
363 
364  //Compute the mean
365  UINT numSamples = cluster.getNumSamplesInCluster();
366  for(UINT j=0; j<N; j++){
367  for(UINT i=0; i<numSamples; i++){
368  UINT index = cluster[i];
369  mean[j] += data[ index ][j];
370  }
371  mean[j] /= double( numSamples );
372  }
373 
374  //Compute the std dev
375  for(UINT j=0; j<N; j++){
376  for(UINT i=0; i<numSamples; i++){
377  std[j] += SQR( data[ cluster[i] ][j] - mean[j] );
378  }
379  std[j] = sqrt( std[j] / double( numSamples-1 ) );
380  }
381 
382  double variance = 0;
383  for(UINT j=0; j<N; j++){
384  variance += std[j];
385  }
386  return variance/N;
387 }
388 
389 bool HierarchicalClustering::saveModelToFile(fstream &file) const{
390 
391  if( !file.is_open() ){
392  errorLog << "saveModelToFile(string filename) - Failed to open file!" << endl;
393  return false;
394  }
395 
396  file << "GRT_HIERARCHICAL_CLUSTERING_FILE_V1.0\n";
397 
398  if( !saveClustererSettingsToFile( file ) ){
399  errorLog << "saveModelToFile(fstream &file) - Failed to save cluster settings to file!" << endl;
400  return false;
401  }
402 
403  if( trained ){
404  file << "M: " << M << endl;
405  file << "N: " << N << endl;
406  file << "NumLevels: " << clusters.size() << endl;
407 
408  for(UINT i=0; i<clusters.size(); i++){
409  file << "Level: " << clusters[i].getLevel() << endl;
410  file << "NumClusters: " << clusters[i].getNumClusters() << endl;
411  }
412  }
413 
414  return true;
415 
416 }
417 
419 
420  string word;
421 
422  //Clear any previous model
423  clear();
424 
425  file >> word;
426  if( word != "GRT_HIERARCHICAL_CLUSTERING_FILE_V1.0" ){
427  return false;
428  }
429 
430  if( !loadClustererSettingsFromFile( file ) ){
431  errorLog << "loadModelFromFile(fstream &file) - Failed to load cluster settings from file!" << endl;
432  return false;
433  }
434 
435  return true;
436 }
437 
438 
439 }//End of namespace GRT
UINT getNumSamples() const
HierarchicalClustering & operator=(const HierarchicalClustering &rhs)
virtual bool clear()
Definition: Clusterer.cpp:139
bool loadClustererSettingsFromFile(fstream &file)
Definition: Clusterer.cpp:176
virtual bool train_(MatrixDouble &data)
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 bool train(ClassificationData trainingData)
Definition: MLBase.cpp:80
bool saveClustererSettingsToFile(fstream &file) const
Definition: Clusterer.cpp:154
virtual bool loadModelFromFile(fstream &file)
bool copyBaseVariables(const Clusterer *Clusterer)
Definition: Clusterer.cpp:84
virtual bool deepCopyFrom(const Clusterer *clusterer)
virtual bool saveModelToFile(fstream &file) const
string getClustererType() const
Definition: Clusterer.cpp:257
void clear()
Definition: Matrix.h:511
unsigned int getNumRows() const
Definition: Matrix.h:531
UINT getNumDimensions() const
virtual bool resize(const unsigned int r, const unsigned int c)
Definition: Matrix.h:234
This class implements a basic Hierarchial Clustering algorithm.