// doc/clustering.dox
  
  
  // Copyright 2009-2011 Microsoft Corporation
  
  // See ../../COPYING for clarification regarding multiple authors
  //
  // Licensed under the Apache License, Version 2.0 (the "License");
  // you may not use this file except in compliance with the License.
  // You may obtain a copy of the License at
  
  //  http://www.apache.org/licenses/LICENSE-2.0
  
  // THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  // KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
  // WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
  // MERCHANTABLITY OR NON-INFRINGEMENT.
  // See the Apache 2 License for the specific language governing permissions and
  // limitations under the License.
  
  namespace kaldi {
  /**
    \page clustering Clustering mechanisms in Kaldi
  
    This page explains the generic clustering mechanisms and interfaces
    used in Kaldi.  See \ref clustering_group for a list of classes
    and functions involved in this.  This page does not cover phonetic 
    decision-tree clustering (see \ref tree_internals and \ref tree_externals), although
    classes and functions introduced in this page are used in lower levels
   of the phonetic clustering code.
  
    \section clustering_sec_intro The Clusterable interface
  
    The Clusterable class is a pure virtual class from which the class
    GaussClusterable inherits (GaussClusterable represents Gaussian statistics).
    In future we will add other types of clusterable object that inherit from
    Clusterable.  The reason for the Clusterable class is to allow us to use
    generic clustering algorithms.
  
    The central notion of the Clusterable interface is that of
    adding statistics together, and measuring the objective function.  The notion
    of distance between two Clusterable objects is derived from measuring the
    objective function of the two objects separately, then adding them together
    and measuring the objective function; the negative of the decrease in objective
    function gives the notion of distance.  
  
    Examples of Clusterable classes that we intend to add at some point include
    mixture-of-Gaussian statistics derived from posteriors of a fixed, shared, 
    mixture-of-Gaussians model, and also collections of counts
    of discrete observations (the objective function would be equivalent to the 
    negated entropy of the distribution, times the number of counts).
  
    An example of getting a pointer of type Clusterable* (which is actually
    of the GaussClusterable type) is as follows:
   \code
    Vector<BaseFloat> x_stats(10), x2_stats(10);
    BaseFloat count = 100.0, var_floor = 0.01;
    // initialize x_stats and x2_stats e.g. as
    // x_stats = 100 * mu_i, x2_stats = 100 * (mu_i*mu_i + sigma^2_i)
    Clusterable *cl = new GaussClusterable(x_stats, x2_stats, var_floor, count);
   \endcode
  
    \section clustering_sec_algo Clustering algorithms
    
    We have implemented a number of generic clustering algorithms.  
    These are listed in \ref clustering_group_algo.  A data-structure that
    is used heavily in these algorithms is a vector of pointers to the 
    Clusterable interface class:
    \code
     std::vector<Clusterable*> to_be_clustered;
    \endcode
    The index into the vector is the index of the "point" to be
    clustered.  
  
    \subsection clustering_sec_kmeans K-means and algorithms with similar interfaces
  
     A typical example of calling clustering code is as follows:
    \code
     std::vector<Clusterable*> to_be_clustered;
     // initialize "to_be_clustered" somehow ...
     std::vector<Clusterable*> clusters;
     int32 num_clust = 10; // requesting 10 clusters
     ClusterKMeansOptions opts; // all default.
     std::vector<int32> assignments;
     ClusterKMeans(to_be_clustered, num_clust, &clusters, &assignments, opts);
    \endcode
    After the clustering code is called, "assignments" will tell you for each
    item in "to_be_clustered", which cluster it is assigned to.  The
    ClusterKMeans() algorithm is fairly efficient even for large number of points;
    click the function name for more details.
  
    There are two more algorithms that have a similar interface to ClusterKMeans():
    namely, ClusterBottomUp() and ClusterTopDown().  Probably the more useful one
    is ClusterTopDown(), which should be more efficient than ClusterKMeans() if the
    number of clusters is large (it does a binary split, and then does a binary
    split on the leaves, and so on).  Internally it calls TreeCluster(), see below.
  
    \subsection clustering_sec_tree_cluster Tree clustering algorithm
  
    The function TreeCluster() clusters points into a binary tree (the leaves
    won't necessarily have just one point each, you can specify a maximum
    number of leaves).  This function is useful, for instance, when building 
    regression trees for adaptation.  See that function's
    documentation for a detailed explanation of its output format.  The quick
    overview is that it numbers leaf and non-leaf nodes in topological order
    with the leaves first and the root last, and outputs a vector that tells you
    for each node what its parent is.
   
  */
  
  /**
   \defgroup clustering_group Classes and functions related to clustering
      See \ref clustering for context.
  
   \defgroup clustering_group_simple Some simple functions used in clustering algorithms
      See \ref clustering for context.
   \ingroup clustering_group
  
   \defgroup clustering_group_algo Algorithms for clustering
      See \ref clustering for context.
   \ingroup clustering_group
  
  */
  }