GenKMeans.H

Go to the documentation of this file.

 /*---------------------------------------------------------------------+
 | Library QgarLib, graphics analysis and recognition                  |
 | Copyright (C) 2002  Qgar Project, LORIA                             |
 |                                                                     |
 | This library is free software; you can redistribute it and/or       |
 | modify it under the terms of the GNU Lesser General Public          |
 | License version 2.1, as published by the Free Software Foundation.  |
 |                                                                     |
 | This library 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.         |
 |                                                                     |
 | The GNU Lesser General Public License is included in the file       |
 | LICENSE.LGPL, in the root directory of the Qgar packaging. See      |
 | http://www.gnu.org/licenses/lgpl.html for the terms of the licence. |
 | To receive a paper copy, write to the Free Software Foundation,     |
 | Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.       |
 |                                                                     |
 | Contact Project Qgar for any information:                           |
 |   LORIA - équipe Qgar                                               |
 |   B.P. 239, 54506 Vandoeuvre-lès-Nancy Cedex, France                |
 |   email: qgar-contact@loria.fr                                      |
 |   http://www.qgar.org/                                              |
 *---------------------------------------------------------------------*/


#ifndef __GENKMEANS_H_INCLUDED__
#define __GENKMEANS_H_INCLUDED__


/**
 * @file     GenKMeans.H
 * @brief    Header file of classes qgar::GenCluster and qgar::GenKMeans.
 *
 * @author   <a href="mailto:qgar-develop@loria.fr?subject=Qgar fwd Gérald Masini">Gérald Masini</a>
 * @date     July 3, 2001  15:57
 * @since    Qgar 2.1
 */


// For RCS/CVS use: Do not delete
/* $Id: GenKMeans.H,v 1.26 2005/10/14 17:05:46 masini Exp $ */



// STD
#include <vector>
// QGAR
#include <qgarlib/QgarErrorAlgorithm.H>



namespace qgar
{


/*---------------------------------------------------------------------*
 |                                                                     |
 |          C  L  A  S  S      G  E  N  C  L  U  S  T  E  R            |
 |                                                                     |
 *---------------------------------------------------------------------*/

/**
 * @ingroup TOOL_CLASSIF
 *
 * @class GenCluster GenKMeans.H
 *
 * @brief A cluster, as generated by the k-means algorithm implemented
 *        by class qgar::GenKMeans.
 *
 * @author <a href="mailto:qgar-develop@loria.fr?subject=Qgar fwd Jan Rendek">Jan Rendek</a>
 * @date   Apr 2, 2004  08:36
 * @since  Qgar 2.1.1
 */
template <class T> class GenCluster
{
// -------------------------------------------------------------------
// T Y P E   D E F I N I T I O N S
// -------------------------------------------------------------------
public:

  /** @name Types */
  //        =====
  //@{

  /**
   * @brief Type of the cluster elements.
   */
  typedef T value_type;

  /**
   * @brief Reference to qgar::GenCluster::value_type.
   */
  typedef value_type& reference;

  /**
   * @brief Constant reference to qgar::GenCluster::value_type.
   */
  typedef const value_type& const_reference;

  /**
   * @brief Pointer to qgar::GenImage::value_type.
   */
  typedef value_type* pointer;

  /**
   * @brief Constant pointer to qgar::GenCluster::value_type.
   */
  typedef const value_type* const_pointer;

  //@}

// -------------------------------------------------------------------
// P U B L I C    M E M B E R S
// -------------------------------------------------------------------
public:

  /** @name Constructors */
  //        ============
  //@{

  /**
   * @brief Builds a cluster.
   *
   * @param elements  the elements of the cluster
   * @param center    the center of the cluster
   */
  GenCluster(const std::vector<value_type>& elements,
             const_reference center);

  /**
   * @brief Copy constructor.
   *
   * @param other the instance to be copied
   */
  GenCluster(const GenCluster& other);

  //@}


  /** @name Operators */
  //        =========
  //@{

  /**
   * @brief Assignment operator.
   *
   * @param rhs The rhs part of the assignment
   */
  GenCluster& operator=(const GenCluster& rhs);

  //@}


  /** @name Access */
  //        ======
  //@{

  /**
   * @brief Retrieves the size of the cluster.
   *
   * @return The size of the cluster
   */
  inline size_t size() const;

  /**
   * @brief Retrieves the center of the cluster.
   *
   * @return the center of the cluster
   */
  inline const_reference center() const;

  /**
   * @brief Retrieves the elements composing the cluster.
   *
   * @return a reference to the vector containing the elements
   *   of this cluster
   */
  inline const std::vector<value_type>& elements() const;

  //@}
 
// -------------------------------------------------------------------
// P R I V A T E    M E M B E R S
// -------------------------------------------------------------------
private:

  /** @name Cluster features */
  //        ================
  //@{

  /**
   * @brief The center of the cluster.
   */
  value_type _center;
  
  /**
   * @brief The elements of the cluster.
   */
  std::vector<value_type> _elements;

  //@}


// -------------------------------------------------------------------
}; // class GenCluster





/*---------------------------------------------------------------------*
 |                                                                     |
 |            C  L  A  S  S      G  E  N  K  M  E  A  N  S             |
 |                                                                     |
 *---------------------------------------------------------------------*/


/**
 * @ingroup TOOL_CLASSIF
 *
 * @class GenKMeans GenKMeans.H "qgarlib/GenKMeans.H"
 *
 * @brief Template class for partitioning a list of objects of type
 * <b>T</b> into a (given) number of clusters using a k-means algorithm.
 *
 * @warning The class is not supposed to be derived: The destructor
 * (as any other function) is not virtual.
 *
 * @author <a href="mailto:qgar-develop@loria.fr?subject=Qgar fwd Gérald Masini">Gérald Masini</a>
 * @date   July 3, 2001  15:57
 * @since  Qgar 2.1
 */
template <class T> class GenKMeans
{
// -------------------------------------------------------------------
// D E F I N I T I O N S
// -------------------------------------------------------------------
public:

  /** @name Types */
  //        =====
  //@{

  /**
   * @brief Type of the objects to be partitioned.
   */
  typedef T value_type;

  /**
   * @brief Reference to qgar::GenKMeans::value_type.
   */
  typedef value_type& reference;

  /**
   * @brief Constant reference to qgar::GenKMeans::value_type.
   */
  typedef const value_type& const_reference;

  /**
   * @brief Pointer to qgar::GenKMeans::value_type.
   */
  typedef value_type* pointer;

  /**
   * @brief Constant pointer to qgar::GenKMeans::value_type.
   */
  typedef const value_type* const_pointer;

  //@}


  /** @name Signatures */
  //        ==========
  //@{

  /**
   * @brief Signature of the distance function.
   */
  typedef double (*DistanceFunction) (const_reference, const_reference);

  //@}


// -------------------------------------------------------------------
// P U B L I C    M E M B E R S
// -------------------------------------------------------------------
public:


  /** @name Constructors */
  //        ============
  //@{

  /**
   * @brief Construct a partition of clusters using a distance function.
   *
   * @param anObjVect      vector of the objects to be partitioned
   * @param aDistFunction  distance function <b>f(T*,T*)</b>
   * @param aClusterCnt    number of resulting clusters (default <b>3</b>)
   *
   * @throw qgar::QgarErrorAlgorithm
   *   if an error occurred while creating clusters
   */
  GenKMeans(const std::vector<value_type>& anObjVect,
            DistanceFunction aDistFunction,
            int aClusterCnt = 3)
    throw(qgar::QgarErrorAlgorithm);

  /**
   * @brief Construct a partition of clusters of given centers,
   *   using a distance function.
   *
   * @param anObjVect      vector of the objects to be partitioned
   * @param aDistFunction  distance function <b>f(T*,T*)</b>
   * @param aCenterVector  vector of the initial centers of the clusters
   * @param aClusterCnt    number of resulting clusters (default <b>3</b>)
   *
   * @throw qgar::QgarErrorAlgorithm
   *   if an error occurred while creating clusters
   */
  GenKMeans(const std::vector<value_type>& anObjVect,
            DistanceFunction aDistFunction,         
            const std::vector<value_type>& aCenterVector,
            int aClusterCnt = 3)
    throw(qgar::QgarErrorAlgorithm);

  //@}


  /** @name Destructor */
  //        ==========
  //@{

  /**
   * @brief Destructor.
   *
   * It is not virtual as the class is not supposed to be derived.
   */
  ~GenKMeans();

  //@}


  /** @name Access */
  //        ======
  //@{

  /**
   * @brief Get number of resulting clusters.
   */
  inline int clusterCnt() const;

  /**
   * @brief Get the vector storing the resulting cluster sizes.
   */
  inline const std::vector<int>& clusterSizes() const;

  /** 
   *@brief Get the vector storing the resulting cluster centers.
   */
  inline const std::vector<const_pointer>& clusterCenters() const;

  /**
   * @brief Get the vector storing the elements of the clusters.
   *
   * Each element of the returned vector represents a cluster.
   * Each cluster is itself represented by a vector, storing
   * pointers to the elements of the cluster.
   */
  inline const std::vector< std::vector<const_pointer> >&
  accessClusterElts() const;

  /**
   * @brief Get a copy of the vector storing the elements
   *   of the clusters.
   *
   * Each element of the returned vector represents a cluster.
   * Each cluster is itself represented by a vector, storing
   * pointers to the elements of the cluster.
   */
  inline std::vector< std::vector<const_pointer> >
  clusterElts() const;

  /**
   * @brief Get the vector storing the clusters.
   *
   * Each element of the returned vector represents a cluster.
   * Each cluster is represented by an instance of class
   * qgar::GenCluster.
   */
  const std::vector< GenCluster<value_type> >&
  accessClusters() const;

  /**
   * @brief Get a copy of the vector storing the clusters.
   *
   * Each element of the returned vector represents a cluster.
   * Each cluster is represented by an instance of class
   * qgar::GenCluster.
   */
  std::vector< GenCluster<value_type> > clusters() const;

  //@}

// -------------------------------------------------------------------
// P R O T E C T E D    M E M B E R S
// -------------------------------------------------------------------
protected:

  /** @name Representation of a cluster */
  //        ===========================
  //@{

  /**
   * @brief Number of clusters.
   */
  const int _clusterCnt;

  /**
   * @brief Vector storing the values of the clusters.
   *
   * Each element of this vector represents a cluster.
   * Each cluster is also represented by a vector, storing the pointers
   * to the elements of the cluster.
   */
  std::vector< std::vector<const_pointer> > _clusterElts;

  /**
   * @brief Vector of clusters sizes.
   */
  std::vector<int> _clusterSizes;

  /**
   * @brief Vector of cluster centers.
   */
  std::vector<const_pointer> _clusterCenters;

  /**
   * @brief Vector of objects to be partitioned.
   */
  std::vector<const_pointer> _objVect;

  /**
   * @brief Vector storing the final clusters.
   *
   * Each element of this vector represents a cluster.
   * Each cluster is represented by an instance
   * of class qgar::GenCluster.
   */
  mutable std::vector< GenCluster<value_type> > _clusters;

  /**
   * @brief The distance function.
   */
  const DistanceFunction _distance;

  //@}

// -------------------------------------------------------------------
// P R I V A T E    M E M B E R S
// -------------------------------------------------------------------
private:

  /** @name Auxiliaries */
  //        ===========
  //@{

  /**
   * @brief Initialize cluster centers.
   *
   * Use a given number of the first objects of the given list of objects.
   *
   * @exception qgar::QgarErrorAlgorithm
   */
  void PRIVATEinitCenters()  throw(qgar::QgarErrorAlgorithm);

  /**
   * @brief Distribute objects into clusters.
   */
  void PRIVATEdistributeIntoClusters();

  /**
   * @brief Compute new cluster centers.
   *
   * @param aNewCenterVector  vector of resulting cluster centers
   *
   * @exception qgar::QgarErrorAlgorithm
   */
  void PRIVATEgetCenters(std::vector<const_pointer>& aNewCenterVector)
    throw(qgar::QgarErrorAlgorithm);

  /**
   * @brief Loop on constructing clusters until getting stable centers.
   */
  void PRIVATEgetClusters();

  /**
   * @brief Construct the final clusters in <b>_clusters</b>
   *   from <b>_clustersElts</b>.
   */
  void PRIVATEconsFinalClusters();

  //@}


  /** @name Disabled */
  //        ========
  //@{

  /**
   * @brief Disabled copy constructor.
   */
  GenKMeans(const GenKMeans&);

  /**
   * @brief Disabled assignment operator.
   */
  GenKMeans& operator=(const GenKMeans&);

  //@}

// ---------------------------------------------------------------------

}; // class GenKmeans


} // namespace qgar




// IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
// IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
// I M P L E M E N T A T I O N
// IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
// IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII


#include <qgarlib/GenKMeans.TCC>

// IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
// IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII




// HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
// HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
// H  E  L  P  E  R  S
// HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
// HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH


namespace qgar
{


/** @name KMeans helper functions  */
//        =======================
//@{

/**
 * @ingroup GLOB_HELPER
 *
 * @brief Construct a partition of clusters using a distance function.
 *
 * @param anObjVect     vector of objects to be partitioned
 * @param aDistFunction distance function <b>f(const T&, const T&)</b>
 * @param aClusterCnt   number of resulting clusters (default <b>3</b>)
 *
 * @throw qgar::QgarErrorAlgorithm
 *   if an error occurred while creating clusters
 */
template <class T>
std::vector< GenCluster<T> > 
qgKMeans(const std::vector<T>& anObjVect,
         double (*aDistFunction) (const T&, const T&),
         int aClusterCnt = 3)

  throw (QgarErrorAlgorithm);


/**
 * @ingroup GLOB_HELPER
 *
 * @brief Construct a partition of clusters of given centers,
 *   using a distance function.
 *
 * @param anObjVect     vector of objects to be partitioned
 * @param aDistFunction distance function <b>f(const T&, const T&)</b>
 * @param aCenterVector vector of the initial centers of the clusters
 * @param aClusterCnt   number of resulting clusters (default <b>3</b>)
 *
 * @throw qgar::QgarErrorAlgorithm
 *   if an error occurred while creating clusters
 */
template <class T>
std::vector< GenCluster<T> >
qgKMeans(const std::vector<T>& anObjVect,
         double (*aDistFunction) (const T&, const T&),
         std::vector<T*>& aCenterVector,
         int aClusterCnt = 3)

  throw (QgarErrorAlgorithm);

//@}


} // namespace qgar 


// HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
// HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH


#endif /* __GENKMEANS_H_INCLUDED__ */