ltiCompetitiveAgglomeration.h

/*
 * Copyright (C) 2004, 2005, 2006
 * Lehrstuhl fuer Technische Informatik, RWTH-Aachen, Germany
 *
 * This file is part of the LTI-Computer Vision Library (LTI-Lib)
 *
 * The LTI-Lib is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License (LGPL)
 * as published by the Free Software Foundation; either version 2.1 of
 * the License, or (at your option) any later version.
 *
 * The LTI-Lib is distributed in the hope that it will be
 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with the LTI-Lib; see the file LICENSE.  If
 * not, write to the Free Software Foundation, Inc., 59 Temple Place -
 * Suite 330, Boston, MA 02111-1307, USA.
 */


/*--------------------------------------------------------------------
 * project ....: LTI-Lib: Image Processing and Computer Vision Library
 * file .......: ltiCompetitiveAgglomeration.h
 * authors ....: Benjamin Winkler
 * organization: LTI, RWTH Aachen
 * creation ...: 21.1.2004
 * revisions ..: $Id: ltiCompetitiveAgglomeration.h,v 1.3 2006/02/07 18:15:12 ltilib Exp $
 */

#ifndef _LTI_COMPETITIVE_AGGLOMERATION_H_
#define _LTI_COMPETITIVE_AGGLOMERATION_H_

#include "ltiVector.h"
#include "ltiCentroidClustering.h"
#include "ltiL2Distance.h"

namespace lti {
  /**
   * This class implements the centroid clustering algorithm presented in
   * "Clustering by Competitive Agglomeration" from Frigui and Krishnapuram, Pattern Recognition,
   * Vol. 30, No. 7, pp. 1109-1119, 1997.
   * The algorithm is a fuzzy clustering algorithm, which reduces a given partition to an optimal
   * number of clusters. Here, the initial partition is generated by first performing a fuzzy-C-Means
   * run on the data.
   * Note: since the number of clusters will only be decreased by this algorithm, the fuzzy-C-Means
   * parameters should be modified such that the number of clusters is chosen to be much larger than
   * the expected number of clusters.
   */
  class competitiveAgglomeration : public centroidClustering {
  public:
    /**
     * The parameters for the class competitiveAgglomeration
     */
    class parameters : public centroidClustering::parameters {
    public:
      /**
       * Default constructor
       */
      parameters();

      /**
       * Copy constructor
       * @param other the parameters object to be copied
       */
      parameters(const parameters& other);

      /**
       * Destructor
       */
      ~parameters();

      /**
       * Returns name of this type
       */
      const char* getTypeName() const;

      /**
       * Copy the contents of a parameters object
       * @param other the parameters object to be copied
       * @return a reference to this parameters object
       */
      parameters& copy(const parameters& other);

      /**
       * Copy the contents of a parameters object
       * @param other the parameters object to be copied
       * @return a reference to this parameters object
       */
      parameters& operator=(const parameters& other);


      /**
       * Returns a pointer to a clone of the parameters
       */
      virtual classifier::parameters* clone() const;

      /**
       * Write the parameters in the given ioHandler
       * @param handler the ioHandler to be used
       * @param complete if true (the default) the enclosing begin/end will
       *        be also written, otherwise only the data block will be written.
       * @return true if write was successful
       */
      virtual bool write(ioHandler& handler,const bool complete=true) const;

      /**
       * Read the parameters from the given ioHandler
       * @param handler the ioHandler to be used
       * @param complete if true (the default) the enclosing begin/end will
       *        be also written, otherwise only the data block will be written.
       * @return true if write was successful
       */
      virtual bool read(ioHandler& handler,const bool complete=true);

#     ifdef _LTI_MSC_6
      /**
       * This function is required by MSVC only, as a workaround for a
       * very awful bug, which exists since MSVC V.4.0, and still by
       * V.6.0 with all bugfixes (so called "service packs") remains
       * there...  This method is also public due to another bug, so please
       * NEVER EVER call this method directly: use read() instead
       */
      bool readMS(ioHandler& handler,const bool complete=true);

      /**
       * This function is required by MSVC only, as a workaround for a
       * very awful bug, which exists since MSVC V.4.0, and still by
       * V.6.0 with all bugfixes (so called "service packs") remains
       * there...  This method is also public due to another bug, so please
       * NEVER EVER call this method directly: use write() instead
       */
      bool writeMS(ioHandler& handler,const bool complete=true) const;
#     endif

      // ------------------------------------------------
      // the parameters
      // ------------------------------------------------

      /**
       * The cardinality factor defines the importance of merging nearby clusters
       * relative to covering the data optimally. Larger values will result in fewer
       * clusters, with a value of 0.0 no cluster will be discarded, thus leading to
       * the same result as the fuzzy C-Means algorithm.
       * Default value is 5.0
       */
      double cardinalityFactor;

      /**
       * As the cardinality factor relies heavily on the data, the distance measure
       * and the number of clusters, a decay function is used that starts with the
       * given cardinality factor and exponentially decreases the value with each
       * iteration: exp(-iteration / timeConstant). This should result in finding
       * the optimal number of clusters faster.
       * The default time constant is 10.0
       */
      double timeConstant;


      /**
       * The initial number of clusters must be larger than the expected optimal
       * number of clusters.
       * Default is 20.
       */
      int initialNumberOfClusters;

      /**
       * The number of iterations to be used for fuzzy c-means pre-classification.
       * Default: 10.
       */
      int initialIterations;

      /**
       * The cardinality describes the amount of data that is being covered by the cluster.
       * If the cardinality of a cluster drops below a given threshold, it will be discarded.
       * The default value for this threshold is 5.0
       */
      double minimumCardinality;

      /**
       * Bias the algorithm either towards hard clustering (nearby 1) or
       * fuzzy clustering (bigger 1); this parameter must be bigger than 1.
       * Default is 2.0
       */
      double fuzzifier;

      /**
       * The maximum number of iterations serves as one of two convergence criteria, the other one
       * being convergenceThreshold.
       * Default value is 100.
       */
      int maxIterations;

      /**
       * The algorithm converges, when the centroids remain stable. If the sum of the L2 distance
       * of the relative movements of the centroids in one iteration is below the convergence threshold,
       * the algorithm terminates.
       * Default: 0.02
       */
      double convergenceThreshold;

    };

    /**
     * Default constructor
     */
    competitiveAgglomeration();

    /**
     * Construct a classifier using the given parameters
     */
    competitiveAgglomeration(const parameters& par);

    /**
     * Copy constructor
     * @param other the object to be copied
     */
    competitiveAgglomeration(const competitiveAgglomeration& other);

    /**
     * Destructor
     */
    virtual ~competitiveAgglomeration();

    /**
     * Returns the name of this type ("competitiveAgglomeration")
     */
    virtual const char* getTypeName() const;
    

    /**
     * Copy data of "other" classifier.
     * @param other the classifier to be copied
     * @return a reference to this classifier object
     */
    competitiveAgglomeration& copy(const competitiveAgglomeration& other);

    /**
     * Alias for copy member
     * @param other the classifier to be copied
     * @return a reference to this classifier object
     */
    competitiveAgglomeration& operator=(const competitiveAgglomeration& other);

    /**
     * Returns a pointer to a clone of this classifier.
     */
    virtual classifier* clone() const;

    /**
     * Returns used parameters
     */
    const parameters& getParameters() const;

    /**
     * train clusters from given data.
     */
    bool train(const lti::dmatrix& input);

    /**
     * calls centroidClustering::train
     */
    bool train(const lti::dmatrix& input, ivector& ids) {
      return centroidClustering::train(input, ids);
    }


  private:

    // fuzzify this value (distance ^ fuzzifier)
    inline double fuzzify(const double& distance) const {
      return lti::pow(distance, fuzzifier);
    }

    // update distance matrix
    void updateDistance(const dmatrix &trainingData);

    // calculate the proportional alpha value, based on the iteration, the time constant,
    // the partition and the distance matrix
    double calculateAlpha(int iteration, double timeConstant) const;

    // update the cardinality of all clusters
    void updateCardinality();

    // update the partition matrix
    void updateMembership(double cardinalityFactor);

    // remove cluster k, adapt all matrices accordingly
    void discardCluster(int k);

    // calculate centroids from the partition matrix
    void updatePrototypes(const dmatrix &trainingData);

    // internal data
    l2Distance<double> distFunc;
    dmatrix distanceMatrix;
    dmatrix partitionMatrix;
    dvector clusterCardinality;

    // for faster access
    int numberOfClusters;
    int numberOfPoints;
    int numberOfDimensions;
    double fuzzifier;
  };
}

#endif