cluster-utils.h

Go to the documentation of this file.

// tree/cluster-utils.h

// Copyright 2012   Arnab Ghoshal
// Copyright 2009-2011  Microsoft Corporation;  Saarland University

// 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.

#ifndef KALDI_TREE_CLUSTER_UTILS_H_
#define KALDI_TREE_CLUSTER_UTILS_H_

#include <vector>
#include "matrix/matrix-lib.h"
#include "itf/clusterable-itf.h"

namespace kaldi {


BaseFloat SumClusterableObjf(const std::vector<Clusterable*> &vec);

BaseFloat SumClusterableNormalizer(const std::vector<Clusterable*> &vec);

Clusterable *SumClusterable(const std::vector<Clusterable*> &vec);

void EnsureClusterableVectorNotNull(std::vector<Clusterable*> *stats);


void AddToClusters(const std::vector<Clusterable*> &stats,
                   const std::vector<int32> &assignments,
                   std::vector<Clusterable*> *clusters);


void AddToClustersOptimized(const std::vector<Clusterable*> &stats,
                            const std::vector<int32> &assignments,
                            const Clusterable &total,
                            std::vector<Clusterable*> *clusters);



// Note, in the algorithms below, it is assumed that the input "points" (which
// is std::vector<Clusterable*>) is all non-NULL.

BaseFloat ClusterBottomUp(const std::vector<Clusterable*> &points,
                          BaseFloat thresh,
                          int32 min_clust,
                          std::vector<Clusterable*> *clusters_out,
                          std::vector<int32> *assignments_out);

BaseFloat ClusterBottomUpCompartmentalized(
    const std::vector< std::vector<Clusterable*> > &points, BaseFloat thresh,
    int32 min_clust, std::vector< std::vector<Clusterable*> > *clusters_out,
    std::vector< std::vector<int32> > *assignments_out);


struct RefineClustersOptions {
  int32 num_iters;  // must be >= 0.  If zero, does nothing.
  int32 top_n;  // must be >= 2.
  RefineClustersOptions() : num_iters(100), top_n(5) {}
  RefineClustersOptions(int32 num_iters_in, int32 top_n_in)
      : num_iters(num_iters_in), top_n(top_n_in) {}
  // include Write and Read functions because this object gets written/read as
  // part of the QuestionsForKeyOptions class.
  void Write(std::ostream &os, bool binary) const;
  void Read(std::istream &is, bool binary);
};

BaseFloat RefineClusters(const std::vector<Clusterable*> &points,
                         std::vector<Clusterable*> *clusters /*non-NULL*/,
                         std::vector<int32> *assignments /*non-NULL*/,
                         RefineClustersOptions cfg = RefineClustersOptions());

struct ClusterKMeansOptions {
  RefineClustersOptions refine_cfg;
  int32 num_iters;
  int32 num_tries;  // if >1, try whole procedure >once and pick best.
  bool verbose;
  ClusterKMeansOptions()
      : refine_cfg(), num_iters(20), num_tries(2), verbose(true)  {}
};

BaseFloat ClusterKMeans(const std::vector<Clusterable*> &points,
                        int32 num_clust,  // exact number of clusters
                        std::vector<Clusterable*> *clusters_out,  // may be NULL
                        std::vector<int32> *assignments_out,  // may be NULL
                        ClusterKMeansOptions cfg = ClusterKMeansOptions());

struct TreeClusterOptions  {
  ClusterKMeansOptions kmeans_cfg;
  int32 branch_factor;
  BaseFloat thresh;  // Objf change: if >0, may be used to control number of leaves.
  TreeClusterOptions()
      : kmeans_cfg(), branch_factor(2), thresh(0) {
    kmeans_cfg.verbose = false;
  }
};

BaseFloat TreeCluster(const std::vector<Clusterable*> &points,
                      int32 max_clust,  // max number of leaf-level clusters.
                      std::vector<Clusterable*> *clusters_out,
                      std::vector<int32> *assignments_out,
                      std::vector<int32> *clust_assignments_out,
                      int32 *num_leaves_out,
                      TreeClusterOptions cfg = TreeClusterOptions());


BaseFloat ClusterTopDown(const std::vector<Clusterable*> &points,
                         int32 max_clust,  // max number of clusters.
                         std::vector<Clusterable*> *clusters_out,
                         std::vector<int32> *assignments_out,
                         TreeClusterOptions cfg = TreeClusterOptions());


}  // end namespace kaldi.

#endif  // KALDI_TREE_CLUSTER_UTILS_H_