TreeClusterer Class Reference

Collaboration diagram for TreeClusterer:

Classes
struct	Node

Public Member Functions
	TreeClusterer (const std::vector< Clusterable *> &points, int32 max_clust, TreeClusterOptions cfg)
BaseFloat	Cluster (std::vector< Clusterable *> *clusters_out, std::vector< int32 > *assignments_out, std::vector< int32 > *clust_assignments_out, int32 *num_leaves_out)
	~TreeClusterer ()

Private Member Functions
void	CreateOutput (std::vector< Clusterable *> *clusters_out, std::vector< int32 > *assignments_out, std::vector< int32 > *clust_assignments_out, int32 *num_leaves_out)
int32	NonleafOutputIndex (int32 index)
void	CreateAssignmentsOutput (std::vector< int32 > *assignments_out)
void	CreateClustAssignmentsOutput (std::vector< int32 > *clust_assignments_out)
void	CreateClustersOutput (std::vector< Clusterable *> *clusters_out)
void	DoSplit (Node *node)
void	FindBestSplit (Node *node)
void	Init ()

Private Attributes
std::vector< Node * >	leaf_nodes_
std::vector< Node * >	nonleaf_nodes_
const std::vector< Clusterable * > &	points_
int32	max_clust_
BaseFloat	ans_
std::priority_queue< std::pair< BaseFloat, Node * > >	queue_
TreeClusterOptions	cfg_

Detailed Description

Definition at line 1032 of file cluster-utils.cc.

Constructor & Destructor Documentation

TreeClusterer()

TreeClusterer ( const std::vector< Clusterable *> &  points, int32  max_clust, TreeClusterOptions  cfg  )

inline

Definition at line 1034 of file cluster-utils.cc.

References KALDI_ASSERT.

                                       :
      points_(points), max_clust_(max_clust), ans_(0.0), cfg_(cfg)
  {
    KALDI_ASSERT(cfg_.branch_factor > 1);
    Init();
  }

~TreeClusterer()

~TreeClusterer ( )

inline

Definition at line 1057 of file cluster-utils.cc.

References kaldi::DeletePointers().

                   {
    for (int32 leaf = 0; leaf < static_cast<int32>(leaf_nodes_.size());leaf++) {
      delete leaf_nodes_[leaf]->node_total;
      DeletePointers(&(leaf_nodes_[leaf]->leaf.clusters));
      delete leaf_nodes_[leaf];
    }
    for (int32 nonleaf = 0; nonleaf < static_cast<int32>(nonleaf_nodes_.size()); nonleaf++) {
      delete nonleaf_nodes_[nonleaf]->node_total;
      delete nonleaf_nodes_[nonleaf];
    }
  }

Member Function Documentation

Cluster()

BaseFloat Cluster ( std::vector< Clusterable *> *  clusters_out, std::vector< int32 > *  assignments_out, std::vector< int32 > *  clust_assignments_out, int32 *  num_leaves_out  )

inline

Definition at line 1042 of file cluster-utils.cc.

References BottomUpClusterer::ans_, and BottomUpClusterer::queue_.

Referenced by kaldi::TreeCluster().

                                           {
    while (static_cast<int32>(leaf_nodes_.size()) < max_clust_ && !queue_.empty()) {
      std::pair<BaseFloat, Node*> pr = queue_.top();
      queue_.pop();
      ans_ += pr.first;
      DoSplit(pr.second);
    }
    CreateOutput(clusters_out, assignments_out, clust_assignments_out,
                 num_leaves_out);
    return ans_;
  }

CreateAssignmentsOutput()

void CreateAssignmentsOutput ( std::vector< int32 > *  assignments_out )

inlineprivate

Definition at line 1106 of file cluster-utils.cc.

References rnnlm::i, KALDI_ASSERT, and BottomUpClusterer::points_.

                                                                  {
    assignments_out->clear();
    assignments_out->resize(points_.size(), (int32)(-1));  // fill with -1.
    for (int32 leaf = 0; leaf < static_cast<int32>(leaf_nodes_.size()); leaf++) {
      std::vector<int32> &indices = leaf_nodes_[leaf]->leaf.point_indices;
      for (int32 i = 0; i < static_cast<int32>(indices.size()); i++) {
        KALDI_ASSERT(static_cast<size_t>(indices[i]) < points_.size());
        KALDI_ASSERT((*assignments_out)[indices[i]] == (int32)(-1));  // check we're not assigning twice.
        (*assignments_out)[indices[i]] = leaf;
      }
    }
#ifdef KALDI_PARANOID
    for (size_t i = 0;i<assignments_out->size();i++) KALDI_ASSERT((*assignments_out)[i] != (int32)(-1));
#endif
  }

CreateClustAssignmentsOutput()

void CreateClustAssignmentsOutput ( std::vector< int32 > *  clust_assignments_out )

inlineprivate

Definition at line 1121 of file cluster-utils.cc.

References KALDI_ASSERT.

                                                                             {
    clust_assignments_out->resize(leaf_nodes_.size() + nonleaf_nodes_.size());
    for (int32 leaf = 0; leaf < static_cast<int32>(leaf_nodes_.size()); leaf++) {
      int32 parent_index;
      if (leaf_nodes_[leaf]->parent == NULL) {  // tree with only one node.
        KALDI_ASSERT(leaf_nodes_.size() == 1&&nonleaf_nodes_.size() == 0 && leaf == 0);
        parent_index = 0;
      } else {
        if (leaf_nodes_[leaf]->parent->is_leaf) parent_index = leaf_nodes_[leaf]->parent->index;
        else parent_index = NonleafOutputIndex(leaf_nodes_[leaf]->parent->index);
      }
      (*clust_assignments_out)[leaf] = parent_index;
    }
    for (int32 nonleaf = 0; nonleaf < static_cast<int32>(nonleaf_nodes_.size()); nonleaf++) {
      int32 index = NonleafOutputIndex(nonleaf);
      int32 parent_index;
      if (nonleaf_nodes_[nonleaf]->parent == NULL) parent_index = index;  // top node.  make it own parent.
      else {
        KALDI_ASSERT(! nonleaf_nodes_[nonleaf]->parent->is_leaf);  // parent is nonleaf since child is nonleaf.
        parent_index = NonleafOutputIndex(nonleaf_nodes_[nonleaf]->parent->index);
      }
      (*clust_assignments_out)[index] = parent_index;
    }
  }

CreateClustersOutput()

void CreateClustersOutput ( std::vector< Clusterable *> *  clusters_out )

inlineprivate

Definition at line 1145 of file cluster-utils.cc.

                                                                   {
    clusters_out->resize(leaf_nodes_.size() + nonleaf_nodes_.size());
    for (int32 leaf = 0; leaf < static_cast<int32>(leaf_nodes_.size()); leaf++) {
      (*clusters_out)[leaf] = leaf_nodes_[leaf]->node_total;
      leaf_nodes_[leaf]->node_total = NULL;  // suppress delete.
    }
    for (int32 nonleaf = 0; nonleaf < static_cast<int32>(nonleaf_nodes_.size()); nonleaf++) {
      int32 index = NonleafOutputIndex(nonleaf);
      (*clusters_out)[index] = nonleaf_nodes_[nonleaf]->node_total;
      nonleaf_nodes_[nonleaf]->node_total = NULL;  // suppress delete.
    }
  }

CreateOutput()

void CreateOutput ( std::vector< Clusterable *> *  clusters_out, std::vector< int32 > *  assignments_out, std::vector< int32 > *  clust_assignments_out, int32 *  num_leaves_out  )

inlineprivate

Definition at line 1088 of file cluster-utils.cc.

                                           {
   if (num_leaves_out) *num_leaves_out = leaf_nodes_.size();
    if (assignments_out)
      CreateAssignmentsOutput(assignments_out);
    if (clust_assignments_out)
      CreateClustAssignmentsOutput(clust_assignments_out);
    if (clusters_out)
      CreateClustersOutput(clusters_out);
  }

DoSplit()

void DoSplit ( Node *  node )

inlineprivate

Definition at line 1157 of file cluster-utils.cc.

References TreeClusterer::Node::assignments, TreeClusterer::Node::best_split, TreeClusterer::Node::children, TreeClusterer::Node::clusters, rnnlm::i, TreeClusterer::Node::index, TreeClusterer::Node::is_leaf, KALDI_ASSERT, TreeClusterer::Node::leaf, TreeClusterer::Node::node_total, TreeClusterer::Node::parent, TreeClusterer::Node::point_indices, and TreeClusterer::Node::points.

                           {
    KALDI_ASSERT(node->is_leaf && node->leaf.best_split > cfg_.thresh*0.999);  // 0.999 is to avoid potential floating-point weirdness under compiler optimizations.
    KALDI_ASSERT(node->children.size() == 0);
    node->children.resize(cfg_.branch_factor);
    for (int32 i = 0;i < cfg_.branch_factor;i++) {
      Node *child = new Node;
      node->children[i] = child;
      child->is_leaf = true;
      child->parent = node;
      child->node_total = node->leaf.clusters[i];
      if (i == 0) {
        child->index = node->index;  // assign node's own index in leaf_nodes_ to 1st child.
        leaf_nodes_[child->index] = child;
      } else {
        child->index = leaf_nodes_.size();  // generate new indices for other children.
        leaf_nodes_.push_back(child);
      }
    }

    KALDI_ASSERT(node->leaf.assignments.size() == node->leaf.points.size());
    KALDI_ASSERT(node->leaf.point_indices.size() == node->leaf.points.size());
    for (int32 i = 0; i < static_cast<int32>(node->leaf.points.size()); i++) {
      int32 child_index = node->leaf.assignments[i];
      KALDI_ASSERT(child_index < static_cast<int32>(cfg_.branch_factor));
      node->children[child_index]->leaf.points.push_back(node->leaf.points[i]);
      node->children[child_index]->leaf.point_indices.push_back(node->leaf.point_indices[i]);
    }
    node->leaf.points.clear();
    node->leaf.point_indices.clear();
    node->leaf.clusters.clear();  // already assigned pointers to children.
    node->leaf.assignments.clear();
    node->is_leaf = false;
    node->index = nonleaf_nodes_.size();  // new index at end of nonleaf_nodes_.
    nonleaf_nodes_.push_back(node);
    for (int32 i = 0;i < static_cast<int32>(cfg_.branch_factor);i++)
      FindBestSplit(node->children[i]);
  }

FindBestSplit()

void FindBestSplit ( Node *  node )

inlineprivate

Definition at line 1194 of file cluster-utils.cc.

References TreeClusterer::Node::assignments, TreeClusterer::Node::best_split, kaldi::ClusterKMeans(), TreeClusterer::Node::clusters, TreeClusterer::Node::is_leaf, KALDI_ASSERT, KALDI_WARN, TreeClusterer::Node::leaf, TreeClusterer::Node::points, and BottomUpClusterer::queue_.

                                 {
    // takes a leaf node that has just been set up, and does ClusterKMeans with k = cfg_branch_factor.
    KALDI_ASSERT(node->is_leaf);
    if (node->leaf.points.size() == 0) {
      KALDI_WARN << "Warning: tree clustering: leaf with no data";
      node->leaf.best_split = 0; return;
    }
    if (node->leaf.points.size()<=1) { node->leaf.best_split = 0; return; }
    else {
      // use kmeans.
      BaseFloat impr = ClusterKMeans(node->leaf.points,
                                     cfg_.branch_factor,
                                     &node->leaf.clusters,
                                     &node->leaf.assignments,
                                     cfg_.kmeans_cfg);
      node->leaf.best_split = impr;
      if (impr > cfg_.thresh)
        queue_.push(std::make_pair(impr, node));
    }
  }

Init()

void Init ( )

inlineprivate

Definition at line 1214 of file cluster-utils.cc.

References rnnlm::i, TreeClusterer::Node::index, TreeClusterer::Node::is_leaf, TreeClusterer::Node::leaf, TreeClusterer::Node::node_total, TreeClusterer::Node::parent, TreeClusterer::Node::point_indices, TreeClusterer::Node::points, BottomUpClusterer::points_, and kaldi::SumClusterable().

              {  // Initializes top node.
    Node *top_node = new Node;
    top_node->index = leaf_nodes_.size();  // == 0 currently.
    top_node->parent = NULL;  // no parent since root of tree.
    top_node->is_leaf = true;
    leaf_nodes_.push_back(top_node);
    top_node->leaf.points = points_;
    top_node->node_total = SumClusterable(points_);
    top_node->leaf.point_indices.resize(points_.size());
    for (size_t i = 0;i<points_.size();i++) top_node->leaf.point_indices[i] = i;
    FindBestSplit(top_node);  // this should always be called when new node is created.
  }

NonleafOutputIndex()

int32 NonleafOutputIndex ( int32  index )

inlineprivate

Definition at line 1103 of file cluster-utils.cc.

                                        {
    return leaf_nodes_.size() + nonleaf_nodes_.size() - 1 - index;
  }

Member Data Documentation

ans_

BaseFloat ans_

private

Definition at line 1232 of file cluster-utils.cc.

cfg_

TreeClusterOptions cfg_

private

Definition at line 1236 of file cluster-utils.cc.

leaf_nodes_

std::vector<Node*> leaf_nodes_

private

Definition at line 1227 of file cluster-utils.cc.

max_clust_

int32 max_clust_

private

Definition at line 1231 of file cluster-utils.cc.

nonleaf_nodes_

std::vector<Node*> nonleaf_nodes_

private

Definition at line 1228 of file cluster-utils.cc.

points_

const std::vector<Clusterable*>& points_

private

Definition at line 1230 of file cluster-utils.cc.

queue_

std::priority_queue<std::pair<BaseFloat, Node*> > queue_

private

Definition at line 1234 of file cluster-utils.cc.

---

The documentation for this class was generated from the following file:

• tree/cluster-utils.cc