PLearn 0.1
Public Member Functions | Static Public Member Functions | Public Attributes | Static Public Attributes | Static Protected Member Functions | Private Types | Private Member Functions
PLearn::KMeansClustering Class Reference

#include <KMeansClustering.h>

Inheritance diagram for PLearn::KMeansClustering:
Inheritance graph
[legend]
Collaboration diagram for PLearn::KMeansClustering:
Collaboration graph
[legend]

List of all members.

Public Member Functions

 KMeansClustering ()
 Default constructor.
virtual void build ()
 Simply calls inherited::build() then build_().
virtual void makeDeepCopyFromShallowCopy (CopiesMap &copies)
 Transforms a shallow copy into a deep copy.
virtual string classname () const
virtual OptionListgetOptionList () const
virtual OptionMapgetOptionMap () const
virtual RemoteMethodMapgetRemoteMethodMap () const
virtual KMeansClusteringdeepCopy (CopiesMap &copies) const
virtual int outputsize () const
 Returns the size of this learner's output, (which typically may depend on its inputsize(), targetsize() and set options).
virtual void forget ()
 (Re-)initializes the PLearner in its fresh state (that state may depend on the 'seed' option) And sets 'stage' back to 0 (this is the stage of a fresh learner!).
virtual void train ()
 The role of the train method is to bring the learner up to stage==nstages, updating the train_stats collector with training costs measured on-line in the process.
virtual void computeOutput (const Vec &input, Vec &output) const
 Computes the output from the input.
virtual void computeCostsFromOutputs (const Vec &input, const Vec &output, const Vec &target, Vec &costs) const
 Computes the costs from already computed output.
virtual TVec< string > getTestCostNames () const
 Returns the names of the costs computed by computeCostsFromOutpus (and thus the test method).
virtual TVec< string > getTrainCostNames () const
 Returns the names of the objective costs that the train method computes and for which it updates the VecStatsCollector train_stats.

Static Public Member Functions

static string _classname_ ()
static OptionList_getOptionList_ ()
static RemoteMethodMap_getRemoteMethodMap_ ()
static Object_new_instance_for_typemap_ ()
static bool _isa_ (const Object *o)
static void _static_initialize_ ()
static const PPathdeclaringFile ()

Public Attributes

int n_clusters_
 The number of clusters.
Mat clusters_
 The learned centroids.

Static Public Attributes

static StaticInitializer _static_initializer_

Static Protected Member Functions

static void declareOptions (OptionList &ol)
 Declares this class' options.

Private Types

typedef PLearner inherited

Private Member Functions

void build_ ()
 This does the actual building.

Detailed Description

This class implements the K-means algorithm. The outputs contain the negative squared euclidian distance to each centroid.

Definition at line 56 of file KMeansClustering.h.


Member Typedef Documentation

Reimplemented from PLearn::PLearner.

Definition at line 59 of file KMeansClustering.h.


Constructor & Destructor Documentation

PLearn::KMeansClustering::KMeansClustering ( )

Default constructor.

Definition at line 50 of file KMeansClustering.cc.


Member Function Documentation

string PLearn::KMeansClustering::_classname_ ( ) [static]

Reimplemented from PLearn::PLearner.

Definition at line 58 of file KMeansClustering.cc.

OptionList & PLearn::KMeansClustering::_getOptionList_ ( ) [static]

Reimplemented from PLearn::PLearner.

Definition at line 58 of file KMeansClustering.cc.

RemoteMethodMap & PLearn::KMeansClustering::_getRemoteMethodMap_ ( ) [static]

Reimplemented from PLearn::PLearner.

Definition at line 58 of file KMeansClustering.cc.

bool PLearn::KMeansClustering::_isa_ ( const Object o) [static]

Reimplemented from PLearn::PLearner.

Definition at line 58 of file KMeansClustering.cc.

Object * PLearn::KMeansClustering::_new_instance_for_typemap_ ( ) [static]

Reimplemented from PLearn::Object.

Definition at line 58 of file KMeansClustering.cc.

StaticInitializer KMeansClustering::_static_initializer_ & PLearn::KMeansClustering::_static_initialize_ ( ) [static]

Reimplemented from PLearn::PLearner.

Definition at line 58 of file KMeansClustering.cc.

void PLearn::KMeansClustering::build ( ) [virtual]

Simply calls inherited::build() then build_().

Reimplemented from PLearn::PLearner.

Definition at line 74 of file KMeansClustering.cc.

References PLearn::PLearner::build(), and build_().

Here is the call graph for this function:

void PLearn::KMeansClustering::build_ ( ) [private]

This does the actual building.

Reimplemented from PLearn::PLearner.

Definition at line 70 of file KMeansClustering.cc.

Referenced by build().

{
}

Here is the caller graph for this function:

string PLearn::KMeansClustering::classname ( ) const [virtual]

Reimplemented from PLearn::Object.

Definition at line 58 of file KMeansClustering.cc.

void PLearn::KMeansClustering::computeCostsFromOutputs ( const Vec input,
const Vec output,
const Vec target,
Vec costs 
) const [virtual]

Computes the costs from already computed output.

Implements PLearn::PLearner.

Definition at line 235 of file KMeansClustering.cc.

References PLearn::argmax(), and PLearn::TVec< T >::resize().

{
    // Compute the costs from *already* computed output.
    costs.resize(1);
    int cluster = argmax(output);
  
    costs[0] = - output[cluster];
}

Here is the call graph for this function:

void PLearn::KMeansClustering::computeOutput ( const Vec input,
Vec output 
) const [virtual]

Computes the output from the input.

Output contains negative euclidian distance to the centroid of each cluster.

Reimplemented from PLearn::PLearner.

Definition at line 225 of file KMeansClustering.cc.

References clusters_, j, n_clusters_, outputsize(), PLearn::powdistance(), and PLearn::TVec< T >::resize().

{
    // Compute the output from the input.
    int nout = outputsize();
    output.resize(nout);

    for (int j=0; j<n_clusters_; j++)
        output[j] = -powdistance(clusters_(j), input, 2);
}

Here is the call graph for this function:

void PLearn::KMeansClustering::declareOptions ( OptionList ol) [static, protected]

Declares this class' options.

Reimplemented from PLearn::PLearner.

Definition at line 60 of file KMeansClustering.cc.

References PLearn::OptionBase::buildoption, clusters_, PLearn::declareOption(), PLearn::PLearner::declareOptions(), PLearn::OptionBase::learntoption, and n_clusters_.

{
    declareOption(ol, "n_clusters", &KMeansClustering::n_clusters_, OptionBase::buildoption,
                  "The number of clusters.");
    declareOption(ol, "clusters", &KMeansClustering::clusters_, OptionBase::learntoption,
                  "The learned centroids.");
    // Now call the parent class' declareOptions
    inherited::declareOptions(ol);
}

Here is the call graph for this function:

static const PPath& PLearn::KMeansClustering::declaringFile ( ) [inline, static]

Reimplemented from PLearn::PLearner.

Definition at line 87 of file KMeansClustering.h.

KMeansClustering * PLearn::KMeansClustering::deepCopy ( CopiesMap copies) const [virtual]

Reimplemented from PLearn::PLearner.

Definition at line 58 of file KMeansClustering.cc.

void PLearn::KMeansClustering::forget ( ) [virtual]

(Re-)initializes the PLearner in its fresh state (that state may depend on the 'seed' option) And sets 'stage' back to 0 (this is the stage of a fresh learner!).

Reimplemented from PLearn::PLearner.

Definition at line 93 of file KMeansClustering.cc.

References clusters_, PLearn::VMat::getExample(), i, PLearn::PLearner::inputsize(), j, PLearn::VMat::length(), PLearn::manual_seed(), n_clusters_, PLERROR, PLearn::TMat< T >::resize(), PLearn::TVec< T >::resize(), PLearn::PLearner::seed_, PLearn::PLearner::stage, PLearn::PLearner::targetsize(), PLearn::PLearner::train_set, and PLearn::uniform_multinomial_sample().

Referenced by train().

{
    if (n_clusters_ <= 0)
        PLERROR("In KMeansClustering::build_(): number of clusters (%d) should be > 0", n_clusters_);

    static Vec input;  // static so we don't reallocate/deallocate memory each time...
    static Vec target; // (but be careful that static means shared!)

    input.resize(inputsize());    // the train_set's inputsize()
    target.resize(targetsize());  // the train_set's targetsize()
    clusters_.resize(n_clusters_, inputsize());

    real weight;
    
    manual_seed(seed_);
  
    // Build a vector of samples indexes to initialize clusters centers.
    Vec start_idx(n_clusters_, -1.0);
    int idx;
    for (int i=0; i<n_clusters_; i++)
    {
        bool uniq=false;
        while (!uniq)
        {
            uniq=true;
            idx = uniform_multinomial_sample(train_set.length());
            for (int j=0; j < n_clusters_ && start_idx[j] != -1.0; j++)
                if (start_idx[j] == idx)
                {
                    uniq=false;
                    break;
                }
        }
        start_idx[i] = idx;
        train_set->getExample(idx,input,target,weight);
        clusters_(i) << input;
    }

    stage = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

OptionList & PLearn::KMeansClustering::getOptionList ( ) const [virtual]

Reimplemented from PLearn::Object.

Definition at line 58 of file KMeansClustering.cc.

OptionMap & PLearn::KMeansClustering::getOptionMap ( ) const [virtual]

Reimplemented from PLearn::Object.

Definition at line 58 of file KMeansClustering.cc.

RemoteMethodMap & PLearn::KMeansClustering::getRemoteMethodMap ( ) const [virtual]

Reimplemented from PLearn::Object.

Definition at line 58 of file KMeansClustering.cc.

TVec< string > PLearn::KMeansClustering::getTestCostNames ( ) const [virtual]

Returns the names of the costs computed by computeCostsFromOutpus (and thus the test method).

Implements PLearn::PLearner.

Definition at line 245 of file KMeansClustering.cc.

Referenced by getTrainCostNames().

{
    // Return the names of the costs computed by computeCostsFromOutpus
    // (these may or may not be exactly the same as what's returned by getTrainCostNames).
    return TVec<string>(1, "squared_reconstruction_error");
}

Here is the caller graph for this function:

TVec< string > PLearn::KMeansClustering::getTrainCostNames ( ) const [virtual]

Returns the names of the objective costs that the train method computes and for which it updates the VecStatsCollector train_stats.

Implements PLearn::PLearner.

Definition at line 252 of file KMeansClustering.cc.

References getTestCostNames().

{
    // Return the names of the objective costs that the train method computes and 
    // for which it updates the VecStatsCollector train_stats
    // (these may or may not be exactly the same as what's returned by getTestCostNames).
    return getTestCostNames();
}

Here is the call graph for this function:

void PLearn::KMeansClustering::makeDeepCopyFromShallowCopy ( CopiesMap copies) [virtual]

Transforms a shallow copy into a deep copy.

Reimplemented from PLearn::PLearner.

Definition at line 81 of file KMeansClustering.cc.

References clusters_, PLearn::deepCopyField(), and PLearn::PLearner::makeDeepCopyFromShallowCopy().

Here is the call graph for this function:

int PLearn::KMeansClustering::outputsize ( ) const [virtual]

Returns the size of this learner's output, (which typically may depend on its inputsize(), targetsize() and set options).

Implements PLearn::PLearner.

Definition at line 88 of file KMeansClustering.cc.

References n_clusters_.

Referenced by computeOutput().

{
    return n_clusters_;
}

Here is the caller graph for this function:

void PLearn::KMeansClustering::train ( ) [virtual]

The role of the train method is to bring the learner up to stage==nstages, updating the train_stats collector with training costs measured on-line in the process.

Implements PLearn::PLearner.

Definition at line 134 of file KMeansClustering.cc.

References PLearn::TVec< T >::clear(), clusters_, PLearn::dist(), forget(), PLearn::VMat::getExample(), i, PLearn::PLearner::inputsize(), j, PLearn::VMat::length(), n_clusters_, PLearn::PLearner::nstages, PLearn::PLearner::nTrainCosts(), PLASSERT, PLearn::powdistance(), PLearn::TMat< T >::resize(), PLearn::TVec< T >::resize(), PLearn::PLearner::stage, PLearn::PLearner::targetsize(), PLearn::PLearner::train_set, and PLearn::PLearner::train_stats.

{
    // The role of the train method is to bring the learner up to stage==nstages,
    // updating train_stats with training costs measured on-line in the process.

    PLASSERT( n_clusters_ > 0 );
  
    static Vec input;  // static so we don't reallocate/deallocate memory each time...
    static Vec target; // (but be careful that static means shared!)

    input.resize(inputsize());    // the train_set's inputsize()
    target.resize(targetsize());  // the train_set's targetsize()
    clusters_.resize(n_clusters_, inputsize());
    
    real weight;

    if(!train_stats)  // make a default stats collector, in case there's none
        train_stats = new VecStatsCollector();

    if(nstages<stage) // asking to revert to a previous stage!
        forget();  // reset the learner to stage=0

    Vec samples_per_cluster(n_clusters_);
  
    Mat new_clusters(n_clusters_,train_set->inputsize());
    TVec<int> cluster_idx(train_set.length());
    TVec<int> old_cluster_idx(train_set.length());
    Vec train_costs(nTrainCosts());
    clusters_.resize(n_clusters_,train_set->inputsize());

    bool stop = false;
    // Training loop.
    while(!stop && stage<nstages)
    {
        // Clear statistics of previous epoch.
        train_stats->forget();

        // Init.
        new_clusters.clear();
        samples_per_cluster.clear();
        old_cluster_idx << cluster_idx;
        train_costs.clear();

        // Redistribute points in closest centroid.
        for (int i=0; i<train_set.length(); i++)
        {
            train_set->getExample(i,input,target,weight);
            real dist, bestdist=1E300;
            int bestclust=0;
      
            if (n_clusters_ > 1)
                for (int j=0; j<n_clusters_; j++)
                    if ((dist = powdistance(clusters_(j), input, 2)) < bestdist)
                    {
                        bestdist = dist;
                        bestclust = j;
                    }
      
            cluster_idx[i] = bestclust;
            samples_per_cluster[bestclust] += weight;
            new_clusters(bestclust) += input * weight;
            train_costs[0] += bestdist;
        }

        train_costs[0] /= train_set.length();

        // Update train statistics.
        train_stats->update(train_costs);
        train_stats->finalize(); // finalize statistics for this epoch

        // Compute new centroids.
        for (int i=0; i<n_clusters_; i++)
            if (samples_per_cluster[i]>0)
                new_clusters(i) /= samples_per_cluster[i];
        clusters_ << new_clusters;

        // Check if things have changed (if not, stop training).
        stop=true;
        if (n_clusters_ > 1)
            for (int i=0;i<train_set.length();i++)
                if (old_cluster_idx[i] != cluster_idx[i])
                {
                    stop=false;
                    break;
                }

        ++stage; // next stage
    }
}

Here is the call graph for this function:


Member Data Documentation

Reimplemented from PLearn::PLearner.

Definition at line 87 of file KMeansClustering.h.

The learned centroids.

Definition at line 66 of file KMeansClustering.h.

Referenced by computeOutput(), declareOptions(), forget(), makeDeepCopyFromShallowCopy(), and train().

The number of clusters.

Definition at line 63 of file KMeansClustering.h.

Referenced by computeOutput(), declareOptions(), forget(), outputsize(), and train().


The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines