HierarchicalClustering.cpp

/*
 GRT MIT License
 Copyright (c) <2012> <Nicholas Gillian, Media Lab, MIT>

 Permission is hereby granted, free of charge, to any person obtaining a copy of this software
 and associated documentation files (the "Software"), to deal in the Software without restriction,
 including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense,
 and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so,
 subject to the following conditions:

 The above copyright notice and this permission notice shall be included in all copies or substantial
 portions of the Software.

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
 LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#define GRT_DLL_EXPORTS
#include "HierarchicalClustering.h"

GRT_BEGIN_NAMESPACE

//Define the string that will be used to identify the object
const std::string HierarchicalClustering::id = "HierarchicalClustering";
std::string HierarchicalClustering::getId() { return HierarchicalClustering::id; }
    
//Register the HierarchicalClustering class with the Clusterer base class
RegisterClustererModule< HierarchicalClustering > HierarchicalClustering::registerModule( HierarchicalClustering::getId() );

HierarchicalClustering::HierarchicalClustering() : Clusterer( HierarchicalClustering::getId() )
{
    M = N = 0;
}
    
HierarchicalClustering::HierarchicalClustering(const HierarchicalClustering &rhs) : Clusterer( HierarchicalClustering::getId() )
{
    *this = rhs;
}

HierarchicalClustering::~HierarchicalClustering(){

}
    
HierarchicalClustering& HierarchicalClustering::operator=(const HierarchicalClustering &rhs){
    
    if( this != &rhs ){
        
        this->M = rhs.M;
        this->N = rhs.N;
        this->clusters = rhs.clusters;
        this->distanceMatrix = rhs.distanceMatrix;
        
        //Clone the Clusterer variables
        copyBaseVariables( (Clusterer*)&rhs );
    }
    
    return *this;
}
    
bool HierarchicalClustering::deepCopyFrom(const Clusterer *clusterer){
    
    if( clusterer == NULL ) return false;
    
    if( this->getId() == clusterer->getId() ){
        //Clone the HierarchicalClustering values
        const HierarchicalClustering *ptr = dynamic_cast<const HierarchicalClustering*>(clusterer);
        
        this->M = ptr->M;
        this->N = ptr->N;
        this->clusters = ptr->clusters;
        this->distanceMatrix = ptr->distanceMatrix;
        
        //Clone the Clusterer variables
        return copyBaseVariables( clusterer );
    }
    return false;
}

bool HierarchicalClustering::reset(){
    
    Clusterer::reset();
    
    return true;
}

bool HierarchicalClustering::clear(){
    
    Clusterer::clear();
    
    M = 0;
    N = 0;
    clusters.clear();
    distanceMatrix.clear();
    
    return true;
}

bool HierarchicalClustering::train_(ClassificationData &trainingData){
 
 if( trainingData.getNumSamples() == 0 ){
  return false;
 }

    //Convert the labelled training data to a training matrix
 M = trainingData.getNumSamples();
    N = trainingData.getNumDimensions();

    MatrixFloat data(M,N);
    for(UINT i=0; i<M; i++){
        for(UINT j=0; j<N; j++){
            data[i][j] = trainingData[i][j];
        }
    }

 return train_( data );
}

bool HierarchicalClustering::train_(UnlabelledData &trainingData){
    
    if( trainingData.getNumSamples() == 0 ){
  return false;
 }

    //Convert the training data into one matrix
 M = trainingData.getNumSamples();
    N = trainingData.getNumDimensions();

    MatrixFloat data(M,N);
    for(UINT i=0; i<M; i++){
        for(UINT j=0; j<N; j++){
            data[i][j] = trainingData[i][j];
        }
    }
 
 return train( data );
}

bool HierarchicalClustering::train_(MatrixFloat &data){
 
 trained = false;
    clusters.clear();
    distanceMatrix.clear();
    
    if( data.getNumRows() == 0 || data.getNumCols() == 0 ){
  return false;
 }
 
    //Set the rows and columns
    M = data.getNumRows();
 N = data.getNumCols();
    
    //Build the distance matrix
    distanceMatrix.resize(M,M);

    //Build the distance matrix
    for(UINT i=0; i<M; i++){
        for(UINT j=0; j<M; j++){
            if( i== j ) distanceMatrix[i][j] = grt_numeric_limits< Float >::max();
            else{
                distanceMatrix[i][j] = squaredEuclideanDistance(data[i], data[j]);
            }
        }
    }

    //Build the initial clusters, at the start each sample gets its own cluster
    UINT uniqueClusterID = 0;
    Vector< ClusterInfo > clusterData(M);
    for(UINT i=0; i<M; i++){
        clusterData[i].uniqueClusterID = uniqueClusterID++;
        clusterData[i].addSampleToCluster(i);
    }
    
    trainingLog << "Starting clustering..." << std::endl;
    
    //Create the first cluster level, each sample is it's own cluster
    UINT level = 0;
    ClusterLevel newLevel;
    newLevel.level = level;
    for(UINT i=0; i<M; i++){
        newLevel.clusters.push_back( clusterData[i] );
    }
    clusters.push_back( newLevel );
    
    //Move to level 1 and start the search
    level++;
    bool keepClustering = true;
    
    while( keepClustering ){
        
        //Find the closest two clusters within the cluster data
        Float minDist = grt_numeric_limits< Float >::max();
        Vector< Vector< UINT > > clusterPairs;
        UINT K = (UINT)clusterData.size();
        for(UINT i=0; i<K; i++){
            for(UINT j=0; j<K; j++){
                if( i != j ){
                    Float dist = computeClusterDistance( clusterData[i], clusterData[j]  );
             
                    if( dist < minDist ){
                        minDist = dist;
                        Vector< UINT > clusterPair(2);
                        clusterPair[0] = i;
                        clusterPair[1] = j;
                        clusterPairs.clear();
                        clusterPairs.push_back( clusterPair );
                    }
                    
                }
            }
        }
        
        if( minDist == grt_numeric_limits< Float >::max() ){
            keepClustering = false;
            warningLog << "train_(MatrixFloat &data) - Failed to find any cluster at level: " << level << std::endl;
            return false;
        }else{
        
            //Merge the two closest clusters together and create a new level
            ClusterLevel newLevel;
            newLevel.level = level;
            
            //Create the new cluster
            ClusterInfo newCluster;
            newCluster.uniqueClusterID = uniqueClusterID++;
            
            const UINT numClusterPairs = clusterPairs.getSize();
            
            for(UINT k=0; k<numClusterPairs; k++){
                //Add all the samples in the first cluster to the new cluster
                UINT numSamplesInClusterA = clusterData[ clusterPairs[k][0] ].getNumSamplesInCluster();
                for(UINT i=0; i<numSamplesInClusterA; i++){
                    UINT index = clusterData[ clusterPairs[k][0] ][ i ];
                    newCluster.addSampleToCluster( index );
                }
                
                //Add all the samples in the second cluster to the new cluster
                UINT numSamplesInClusterB = clusterData[ clusterPairs[k][1] ].getNumSamplesInCluster();
                for(UINT i=0; i<numSamplesInClusterB; i++){
                    UINT index = clusterData[ clusterPairs[k][1] ][ i ];
                    newCluster.addSampleToCluster( index );
                }
                
                //Compute the cluster variance
                newCluster.clusterVariance = computeClusterVariance( newCluster, data );
                
                //Remove the two cluster pairs (so they will not be used in the next search
                UINT idA = clusterData[ clusterPairs[k][0] ].getUniqueClusterID();
                UINT idB = clusterData[ clusterPairs[k][1] ].getUniqueClusterID();
                UINT numRemoved = 0;
                Vector< ClusterInfo >::iterator iter = clusterData.begin();
                while( iter != clusterData.end() ){
                    if( iter->getUniqueClusterID() == idA || iter->getUniqueClusterID() == idB ){
                        iter = clusterData.erase( iter );
                        if( ++numRemoved >= 2 ) break;
                    }else iter++;
                }
            }
            
            //Add the merged cluster to the clusterData
            clusterData.push_back( newCluster );
            
            //Add the new level and cluster data to the main cluster buffer
            newLevel.clusters.push_back( newCluster );
            
            clusters.push_back( newLevel );
            
            //Update the level
            level++;
        }
        
        //Check to see if we should stop clustering
        if( level >= M ){
            keepClustering = false;
        }
        
        if( clusterData.size() == 0 ){
            keepClustering = false;
        }
        
        trainingLog << "Cluster level: " << level << " Number of clusters: " << clusters.back().getNumClusters() << std::endl;
    }
    
    //Flag that the model is trained
    trained = true;
    
    //Setup the cluster labels
    clusterLabels.resize(numClusters);
    for(UINT i=0; i<numClusters; i++){
        clusterLabels[i] = i+1;
    }
    clusterLikelihoods.resize(numClusters,0);
    clusterDistances.resize(numClusters,0);

 return true;
}
    
bool HierarchicalClustering::printModel(){
    
    UINT K = (UINT)clusters.size();
    
    std::cout << "Hierarchical Clustering Model\n\n";
    for(UINT k=0; k<K; k++){
        UINT numClusters = clusters[k].getNumClusters();
        UINT numSamples = 0;
        for(UINT i=0; i<numClusters; i++){
            numSamples += clusters[k][i].getNumSamplesInCluster();
        }
        
        std::cout << "Level: " << clusters[k].level << "\tNumClusters: " << numClusters << "\tNumSamples: " << numSamples << std::endl;
        for(UINT i=0; i<numClusters; i++){
             std::cout << "ClusterVariance: " << clusters[k][i].clusterVariance << std::endl;
             std::cout << "Indexs: ";
            UINT numSamplesInCluster = clusters[k][i].getNumSamplesInCluster();
            for(UINT j=0; j<numSamplesInCluster; j++){
                 std::cout << clusters[k][i][j] << "\t";
            }
             std::cout << std::endl;
        }
    }

    return true;
}
    
Float HierarchicalClustering::squaredEuclideanDistance(const Float *a,const Float *b){
    Float dist = 0;
    for(UINT i=0; i<N; i++){
        dist += SQR( a[i] - b[i] );
    }
    return dist;
}
    
Float HierarchicalClustering::computeClusterDistance( const ClusterInfo &clusterA, const ClusterInfo &clusterB ){
    
    Float minDist = grt_numeric_limits< Float >::max();
    const UINT numSamplesA = clusterA.getNumSamplesInCluster();
    const UINT numSamplesB = clusterB.getNumSamplesInCluster();
    
    //Find the minimum distance between the two clusters
    for(UINT i=0; i<numSamplesA; i++){
        for(UINT j=0; j<numSamplesB; j++){
            if( distanceMatrix[ clusterA[i] ][ clusterB[j] ] < minDist ){
                minDist = distanceMatrix[ clusterA[i] ][ clusterB[j] ];
            }
        }
    }
    
    return minDist;
}
    
Float HierarchicalClustering::computeClusterVariance( const ClusterInfo &cluster, const MatrixFloat &data ){
    
    VectorFloat mean(N,0);
    VectorFloat std(N,0);
    
    //Compute the mean
    UINT numSamples = cluster.getNumSamplesInCluster();
    for(UINT j=0; j<N; j++){
        for(UINT i=0; i<numSamples; i++){
            UINT index = cluster[i];
            mean[j] += data[ index ][j];
        }
        mean[j] /= Float( numSamples );
    }
    
    //Compute the std dev
    for(UINT j=0; j<N; j++){
        for(UINT i=0; i<numSamples; i++){
            std[j] += grt_sqr( data[ cluster[i] ][j] - mean[j] );
        }
        std[j] = grt_sqrt( std[j] / Float( numSamples-1 ) );
    }
    
    Float variance = 0;
    for(UINT j=0; j<N; j++){
        variance += std[j];
    }
    return variance/N;
}

bool HierarchicalClustering::saveModelToFile( std::fstream &file ) const{
    
    if( !file.is_open() ){
        errorLog << "saveModelToFile(string filename) - Failed to open file!" << std::endl;
        return false;
    }
    
    file << "GRT_HIERARCHICAL_CLUSTERING_FILE_V1.0\n";
    
    if( !saveClustererSettingsToFile( file ) ){
        errorLog << "saveModelToFile(fstream &file) - Failed to save cluster settings to file!" << std::endl;
        return false;
    }
    
    if( trained ){
        file << "M: " << M << std::endl;
        file << "N: " << N << std::endl;
        file << "NumLevels: " << clusters.getSize() << std::endl;
        
        for(UINT i=0; i<clusters.getSize(); i++){
            file << "Level: " << clusters[i].getLevel() << std::endl;
            file << "NumClusters: " << clusters[i].getNumClusters() << std::endl;
        }
    }
    
    return true;
    
}

bool HierarchicalClustering::loadModelFromFile( std::fstream &file ){
    
    std::string word;
    
    //Clear any previous model
    clear();
    
    file >> word;
    if( word != "GRT_HIERARCHICAL_CLUSTERING_FILE_V1.0" ){
        return false;
    }
    
    if( !loadClustererSettingsFromFile( file ) ){
        errorLog << "loadModelFromFile(fstream &file) - Failed to load cluster settings from file!" << std::endl;
        return false;
    }
        
    return true;
}

GRT_END_NAMESPACE