NICE_VisLearning/math/cluster/SpectralCluster.cpp

/** 
* @file SpectralCluster.cpp
* @brief spectral clustering by kmeans-clustering of eigenvectors
* @author Erik Rodner
* @date 11/13/2007

*/

#include <iostream>

#include <core/vector/Distance.h>
#include <core/vector/Eigen.h>
#include <map>
#include "vislearning/math/cluster/SpectralCluster.h"

using namespace OBJREC;

using namespace std;
using namespace NICE;

SpectralCluster::SpectralCluster ( int _noClasses, double alpha ) : noClasses(_noClasses), kmeans(_noClasses)
{
    this->alpha = alpha;
}

SpectralCluster::~SpectralCluster()
{
}

void SpectralCluster::getSimilarityMatrix ( const VVector & features, 
					    NICE::Matrix & laplacian,
					    double alpha )
{
    NICE::Matrix distances ( laplacian );
    double mindist = numeric_limits<double>::max();
    double maxdist = - numeric_limits<double>::max();
    long int count = 0;
    double mean = 0.0;
    double stddev = 0.0;
    NICE::EuclidianDistance<double> distance;

    for ( int i = 0 ; i < (int)features.size() ; i++ )
    {
	const NICE::Vector & xi = features[i];
	for ( int j = i ; j < (int)features.size() ; j++ )
	{
	    const NICE::Vector & xj = features[j];
	    // double sim = xi * xj;
	    double dist = distance.calculate ( xi, xj );
	    distances(i, j) = dist;

	    if ( dist < mindist )
		mindist = dist;
	    if ( dist > maxdist )
		maxdist = dist;

	    count++;
	    mean += dist;
	}
    }
    mean /= count;

    for ( int i = 0 ; i < (int)features.size() ; i++ )
	for ( int j = i ; j < (int)features.size() ; j++ )
	{
	    double d = ( mean - distances(i, j) );
	    stddev += d*d;
	}

    stddev /= count;

    double norm = alpha / (2.0 * stddev);

    for ( int i = 0 ; i < (int)features.size() ; i++ )
	for ( int j = i ; j < (int)features.size() ; j++ )
	{
	    double sim = exp(-distances(i, j) * norm );
	    
	    laplacian(i, j) = - sim;
	    laplacian(j, i) = - sim;
	}
}

void SpectralCluster::computeLaplacian ( const VVector & features,
					 NICE::Matrix & laplacian, int method, double alpha )
{
    laplacian.set(0.0);
    getSimilarityMatrix(features, laplacian, alpha);
    
    NICE::Vector d ( laplacian.rows() );
    d.set(0.0);
    for ( int i = 0 ; i < (int)laplacian.rows(); i++ )
    {
		for ( int j = 0 ; j < (int)laplacian.cols(); j++ )
	    	d[i] -=laplacian(i, j);
    }

    // Now we got the negative weight matrix laplacian : -W
    // and the degree matrix : D

        // calculate normalization
    // D^-1 * L
    if ( method == L_RW_NORMALIZED ) 
    {
	// L = D^-1 L_unnormalized = I - D^-1*W
		for ( int i = 0 ; i < (int)laplacian.rows() ; i++ )
			for ( int j = 0 ; j < (int)laplacian.cols() ; j++ )
				laplacian(i, j) *= (1.0/d[i]);

		for ( int i = 0 ; i < (int)laplacian.rows() ; i++ )
	    	laplacian(i, i) += 1.0;

    } else if ( method == L_UNNORMALIZED ) {
	// unnormalized version
	// L = D - W
		for ( int i = 0 ; i < (int)laplacian.rows() ; i++ )
	    	laplacian(i, i) += d[i];
    }
}

void SpectralCluster::cluster ( const VVector & features,
				VVector & prototypes,
				std::vector<double> & weights,
				std::vector<int>    & assignment )
{

    if ( features.size() <= 0 ) {
	fprintf (stderr, "FATAL ERROR: not enough features vectors provided\n");
	exit(-1);
    }

    const NICE::Vector & x = features[0];
    int dimension = x.size();

    NICE::Matrix laplacian ( features.size(), features.size() );

    computeLaplacian ( features, laplacian, L_RW_NORMALIZED, alpha );
    //computeLaplacian ( features, laplacian, L_UNNORMALIZED, alpha );

    NICE::Matrix eigvect;
    NICE::Vector eigvals;
    NICE::eigenvectorvalues ( laplacian, eigvect, eigvals );

    std::map<double, int> eigvals_sorted;
	for ( int i = 0 ; i < (int)eigvals.size(); i++ ) 
    {
	eigvals_sorted.insert ( make_pair( eigvals[i], i ) );
    }

    VVector spectral_features;

	for ( int i = 0 ; i < (int)eigvect.rows() ; i++ )
    {
	NICE::Vector eigvec_k ( noClasses );
	map<double, int>::const_iterator k = eigvals_sorted.begin();
	for ( int j = 0 ; j < noClasses ; j++ )
	{
	    int eigval_index = k->second;
	    eigvec_k[j] = eigvect(i, eigval_index ) ;
	    k++;
	}

	spectral_features.push_back ( eigvec_k );
    }

    kmeans.cluster ( spectral_features, prototypes, weights, assignment ); 

    // recompute prototypes

    for ( int k = 0 ; k < noClasses ; k++ )
    {
	prototypes[k].resize( dimension );
	prototypes[k].set(0);
	weights[k] = 0;
    }

    int j = 0;
    for ( VVector::const_iterator i  = features.begin();
                                              i != features.end();
	                                      i++, j++ )
    {
	int k = assignment[j];
	
	NICE::Vector & p = prototypes[k];
	const NICE::Vector & x = *i;
	p += x;
	weights[k]++;
    }

    for ( int k = 0 ; k < noClasses ; k++ )
    {
	NICE::Vector & p = prototypes[k];
	if ( weights[k] <= 0 ) {
	    fprintf (stderr, "FATAL ERROR: spectral clustering produced empty cluster !\n");
	    exit(-1);
	}
	p *= ( 1.0 / weights[k] );
	weights[k] = weights[k] / features.size();
    }
}