The AgglomerativeClusterer class contains the necessary mechanisms for the actual clustering algorithm. More...

#include <agglomerative-clustering.h>

Collaboration diagram for AgglomerativeClusterer:

Public Member Functions
	AgglomerativeClusterer (const Matrix< BaseFloat > &costs, BaseFloat threshold, int32 min_clusters, int32 first_pass_max_points, BaseFloat max_cluster_fraction, std::vector< int32 > *assignments_out)

void	Cluster ()

void	ClusterSinglePass ()

void	ClusterTwoPass ()

Private Types
typedef std::pair< BaseFloat, uint32 >	QueueElement

typedef std::priority_queue< QueueElement, std::vector< QueueElement >, std::greater< QueueElement > >	QueueType

Private Member Functions
uint32	EncodePair (int32 i, int32 j)

std::pair< int32, int32 >	DecodePair (uint32 key)

void	InitializeClusters (int32 first, int32 last)

void	ComputeClusters (int32 min_clusters)

void	AddClustersToSecondPass ()

void	AssignClusters ()

void	MergeClusters (int32 i, int32 j)

Private Attributes
const Matrix< BaseFloat > &	costs_

BaseFloat	threshold_

int32	min_clusters_

int32	first_pass_max_points_

std::vector< int32 > *	assignments_

int32	num_points_

int32	max_cluster_size_

int32	count_

int32	second_pass_count_

QueueType	queue_

QueueType	second_pass_queue_

std::unordered_map< uint32, BaseFloat >	cluster_cost_map_

std::unordered_map< int32, AhcCluster * >	clusters_map_

std::set< int32 >	active_clusters_

std::unordered_map< uint32, BaseFloat >	second_pass_cluster_cost_map_

std::unordered_map< int32, AhcCluster * >	second_pass_clusters_map_

std::set< int32 >	second_pass_active_clusters_

Detailed Description

The AgglomerativeClusterer class contains the necessary mechanisms for the actual clustering algorithm.

Definition at line 55 of file agglomerative-clustering.h.

Member Typedef Documentation

◆ QueueElement

typedef std::pair<BaseFloat, uint32> QueueElement

private

Definition at line 125 of file agglomerative-clustering.h.

◆ QueueType

typedef std::priority_queue<QueueElement, std::vector<QueueElement>, std::greater<QueueElement> > QueueType

private

Definition at line 127 of file agglomerative-clustering.h.

Constructor & Destructor Documentation

◆ AgglomerativeClusterer()

AgglomerativeClusterer	(	const Matrix< BaseFloat > &	costs,
		BaseFloat	threshold,
		int32	min_clusters,
		int32	first_pass_max_points,
		BaseFloat	max_cluster_fraction,
		std::vector< int32 > *	assignments_out
	)

inline

Definition at line 57 of file agglomerative-clustering.h.

References rnnlm::i, rnnlm::j, and MatrixBase< Real >::NumRows().

       : costs_(costs), threshold_(threshold), min_clusters_(min_clusters),
         first_pass_max_points_(first_pass_max_points),
         assignments_(assignments_out) {
     num_points_ = costs.NumRows();
 
     // The max_cluster_size_ is a hard limit on the number points in a cluster.
     // This is useful for handling degenerate cases where some outlier points
     // form their own clusters and force everything else to be clustered
     // together, e.g. when min-clusters is provided instead of a threshold.
     max_cluster_size_ = ceil(num_points_ * max_cluster_fraction);
 
     // The count_, which is used for identifying clusters, is initialized to
     // num_points_ because cluster IDs 1..num_points_ are reserved for input
     // points, which are the initial set of clusters.
     count_ = num_points_;
 
     // The second_pass_count_, which is used for identifying the initial set of
     // second pass clusters and initializing count_ before the second pass, is
     // initialized to 0 and incremented whenever a new cluster is added to the
     // initial set of second pass clusters.
     second_pass_count_ = 0;
   }

Member Function Documentation

◆ AddClustersToSecondPass()

void AddClustersToSecondPass ( )

private

Definition at line 155 of file agglomerative-clustering.cc.

Referenced by AgglomerativeClusterer::ClusterTwoPass().

                                                      {
   // This method collects the results of first pass clustering for one subset,
   // i.e. adds the set of active clusters to the set of second pass active
   // clusters and computes the costs for the newly formed cluster pairs.
   std::set<int32>::iterator it1, it2;
   int32 count = second_pass_count_;
   for (it1 = active_clusters_.begin(); it1 != active_clusters_.end(); ++it1) {
     AhcCluster *clust1 = clusters_map_[*it1];
     second_pass_clusters_map_[++count] = clust1;
 
     // Compute new cluster pair costs
     for (it2 = second_pass_active_clusters_.begin();
          it2 != second_pass_active_clusters_.end(); ++it2) {
       AhcCluster *clust2 = second_pass_clusters_map_[*it2];
       uint32 new_key = EncodePair(count, *it2);
 
       BaseFloat new_cost = 0.0;
       std::vector<int32>::iterator utt_it1, utt_it2;
       for (utt_it1 = clust1->utt_ids.begin();
            utt_it1 != clust1->utt_ids.end(); ++utt_it1) {
          for (utt_it2 = clust2->utt_ids.begin();
               utt_it2 != clust2->utt_ids.end(); ++utt_it2) {
            new_cost += costs_(*utt_it1, *utt_it2);
          }
       }
 
       second_pass_cluster_cost_map_[new_key] = new_cost;
       BaseFloat norm = clust1->size * clust2->size;
       if (new_cost / norm <= threshold_)
         second_pass_queue_.push(std::make_pair(new_cost / norm, new_key));
     }
 
     // Copy cluster pair costs that were already computed in the first pass
     int32 count2 = second_pass_count_;
     for (it2 = active_clusters_.begin(); it2 != it1; ++it2) {
       uint32 key = EncodePair(*it1, *it2);
       BaseFloat cost = cluster_cost_map_[key];
       BaseFloat norm = clust1->size * (clusters_map_[*it2])->size;
       uint32 new_key = EncodePair(count, ++count2);
       second_pass_cluster_cost_map_[new_key] = cost;
       if (cost / norm <= threshold_)
         second_pass_queue_.push(std::make_pair(cost / norm, new_key));
     }
   }
   // We update second_pass_count_ and second_pass_active_clusters_ here since
   // above loop assumes they do not change while the loop is running.
   while (second_pass_count_ < count)
     second_pass_active_clusters_.insert(++second_pass_count_);
 }

◆ AssignClusters()

void AssignClusters ( )

private

Definition at line 205 of file agglomerative-clustering.cc.

References AgglomerativeClusterer::active_clusters_, AgglomerativeClusterer::assignments_, AgglomerativeClusterer::clusters_map_, AgglomerativeClusterer::num_points_, and AhcCluster::utt_ids.

Referenced by AgglomerativeClusterer::ClusterSinglePass(), and AgglomerativeClusterer::ClusterTwoPass().

                                             {
   assignments_->resize(num_points_);
   int32 label_id = 0;
   std::set<int32>::iterator it;
   // Iterate through the clusters and assign all utterances within the cluster
   // an ID label unique to the cluster. This is the final output and frees up
   // the cluster memory accordingly.
   for (it = active_clusters_.begin(); it != active_clusters_.end(); ++it) {
     ++label_id;
     AhcCluster *cluster = clusters_map_[*it];
     std::vector<int32>::iterator utt_it;
     for (utt_it = cluster->utt_ids.begin();
          utt_it != cluster->utt_ids.end(); ++utt_it)
       (*assignments_)[*utt_it] = label_id;
     delete cluster;
   }
 }

◆ Cluster()

void Cluster ( )

Definition at line 27 of file agglomerative-clustering.cc.

References AgglomerativeClusterer::ClusterSinglePass(), AgglomerativeClusterer::ClusterTwoPass(), AgglomerativeClusterer::first_pass_max_points_, and AgglomerativeClusterer::num_points_.

Referenced by kaldi::AgglomerativeCluster().

                                      {
   if (num_points_ > first_pass_max_points_)
     ClusterTwoPass();
   else
     ClusterSinglePass();
 }

◆ ClusterSinglePass()

void ClusterSinglePass ( )

Definition at line 34 of file agglomerative-clustering.cc.

References AgglomerativeClusterer::AssignClusters(), AgglomerativeClusterer::ComputeClusters(), AgglomerativeClusterer::InitializeClusters(), AgglomerativeClusterer::min_clusters_, and AgglomerativeClusterer::num_points_.

Referenced by AgglomerativeClusterer::Cluster().

                                                {
   InitializeClusters(0, num_points_);
   ComputeClusters(min_clusters_);
   AssignClusters();
 }

◆ ClusterTwoPass()

void ClusterTwoPass ( )

Definition at line 40 of file agglomerative-clustering.cc.

Referenced by AgglomerativeClusterer::Cluster().

                                             {
   // This is the first pass loop. We divide the input into equal size subsets
   // making sure each subset has at most first_pass_max_points_ points. Then, we
   // cluster the points in each subset separately until a stopping criterion is
   // reached. We set the minimum number of clusters to 10 * min_clusters_ for
   // each subset to avoid early merging of most clusters that would otherwise be
   // kept separate in single pass clustering.
   BaseFloat num_points = static_cast<BaseFloat>(num_points_);
   int32 num_subsets = ceil(num_points / first_pass_max_points_);
   int32 subset_size = ceil(num_points / num_subsets);
   for (int32 n = 0; n < num_points_; n += subset_size) {
     InitializeClusters(n, std::min(n + subset_size, num_points_));
     ComputeClusters(min_clusters_ * 10);
     AddClustersToSecondPass();
   }
 
   // We swap the contents of the first and second pass data structures so that
   // we can use the same method to do second pass clustering.
   clusters_map_.swap(second_pass_clusters_map_);
   active_clusters_.swap(second_pass_active_clusters_);
   cluster_cost_map_.swap(second_pass_cluster_cost_map_);
   queue_.swap(second_pass_queue_);
   count_ = second_pass_count_;
 
   // This is the second pass. It moves through the queue merging clusters
   // determined in the first pass until a stopping criterion is reached.
   ComputeClusters(min_clusters_);
 
   AssignClusters();
 }

◆ ComputeClusters()

void ComputeClusters ( int32 min_clusters )

private

Definition at line 109 of file agglomerative-clustering.cc.

References AgglomerativeClusterer::active_clusters_, AgglomerativeClusterer::clusters_map_, AgglomerativeClusterer::DecodePair(), rnnlm::i, rnnlm::j, AgglomerativeClusterer::max_cluster_size_, AgglomerativeClusterer::MergeClusters(), and AgglomerativeClusterer::queue_.

Referenced by AgglomerativeClusterer::ClusterSinglePass(), and AgglomerativeClusterer::ClusterTwoPass().

                                                                {
   while (active_clusters_.size() > min_clusters && !queue_.empty()) {
     std::pair<BaseFloat, uint32> pr = queue_.top();
     int32 i, j;
     std::tie(i, j) = DecodePair(pr.second);
     queue_.pop();
     // check to make sure clusters have not already been merged
     if ((active_clusters_.find(i) != active_clusters_.end()) &&
         (active_clusters_.find(j) != active_clusters_.end())) {
       if (clusters_map_[i]->size + clusters_map_[j]->size <= max_cluster_size_)
         MergeClusters(i, j);
     }
   }
 }

◆ DecodePair()

std::pair< int32, int32 > DecodePair ( uint32 key )

private

Definition at line 78 of file agglomerative-clustering.cc.

Referenced by AgglomerativeClusterer::ComputeClusters().

                                                                    {
   return std::make_pair(static_cast<int32>(key >> 16),
                         static_cast<int32>(key & 0x0000FFFFu));
 }

◆ EncodePair()

uint32 EncodePair	(	int32	i,
		int32	j
	)

private

Definition at line 71 of file agglomerative-clustering.cc.

References rnnlm::j.

Referenced by AgglomerativeClusterer::AddClustersToSecondPass(), AgglomerativeClusterer::InitializeClusters(), and AgglomerativeClusterer::MergeClusters().

                                                           {
   if (i < j)
     return (static_cast<uint32>(i) << 16) + static_cast<uint32>(j);
   else
     return (static_cast<uint32>(j) << 16) + static_cast<uint32>(i);
 }

◆ InitializeClusters()

void InitializeClusters	(	int32	first,
		int32	last
	)

private

Definition at line 83 of file agglomerative-clustering.cc.

References AgglomerativeClusterer::active_clusters_, AgglomerativeClusterer::cluster_cost_map_, AgglomerativeClusterer::clusters_map_, AgglomerativeClusterer::costs_, AgglomerativeClusterer::EncodePair(), rnnlm::i, rnnlm::j, KALDI_ASSERT, AgglomerativeClusterer::queue_, and AgglomerativeClusterer::threshold_.

Referenced by AgglomerativeClusterer::ClusterSinglePass(), and AgglomerativeClusterer::ClusterTwoPass().

                                                                        {
   KALDI_ASSERT(last > first);
   clusters_map_.clear();
   active_clusters_.clear();
   cluster_cost_map_.clear();
   queue_ = QueueType();  // priority_queue does not have a clear method
 
   for (int32 i = first; i < last; i++) {
     // create an initial cluster of size 1 for each point
     std::vector<int32> ids;
     ids.push_back(i);
     AhcCluster *c = new AhcCluster(i + 1, -1, -1, ids);
     clusters_map_[i + 1] = c;
     active_clusters_.insert(i + 1);
 
     // propagate the queue with all pairs from the cost matrix
     for (int32 j = i + 1; j < last; j++) {
       BaseFloat cost = costs_(i, j);
       uint32 key = EncodePair(i + 1, j + 1);
       cluster_cost_map_[key] = cost;
       if (cost <= threshold_)
         queue_.push(std::make_pair(cost, key));
     }
   }
 }

◆ MergeClusters()

void MergeClusters	(	int32	i,
		int32	j
	)

private

Definition at line 124 of file agglomerative-clustering.cc.

References AgglomerativeClusterer::active_clusters_, AgglomerativeClusterer::cluster_cost_map_, AgglomerativeClusterer::clusters_map_, AgglomerativeClusterer::count_, AgglomerativeClusterer::EncodePair(), rnnlm::i, AhcCluster::id, rnnlm::j, AhcCluster::parent1, AhcCluster::parent2, AgglomerativeClusterer::queue_, AhcCluster::size, AgglomerativeClusterer::threshold_, and AhcCluster::utt_ids.

Referenced by AgglomerativeClusterer::ComputeClusters().

                                                            {
   AhcCluster *clust1 = clusters_map_[i];
   AhcCluster *clust2 = clusters_map_[j];
   // For memory efficiency, the first cluster is updated to contain the new
   // merged cluster information, and the second cluster is later deleted.
   clust1->id = ++count_;
   clust1->parent1 = i;
   clust1->parent2 = j;
   clust1->size += clust2->size;
   clust1->utt_ids.insert(clust1->utt_ids.end(), clust2->utt_ids.begin(),
                          clust2->utt_ids.end());
   // Remove the merged clusters from the list of active clusters.
   active_clusters_.erase(i);
   active_clusters_.erase(j);
   // Update the queue with all the new costs involving the new cluster
   std::set<int32>::iterator it;
   for (it = active_clusters_.begin(); it != active_clusters_.end(); ++it) {
     // The new cost is the sum of the costs of the new cluster's parents
     BaseFloat new_cost = cluster_cost_map_[EncodePair(*it, i)] +
                          cluster_cost_map_[EncodePair(*it, j)];
     uint32 new_key = EncodePair(*it, count_);
     cluster_cost_map_[new_key] = new_cost;
     BaseFloat norm = clust1->size * (clusters_map_[*it])->size;
     if (new_cost / norm <= threshold_)
       queue_.push(std::make_pair(new_cost / norm, new_key));
   }
   active_clusters_.insert(count_);
   clusters_map_[count_] = clust1;
   delete clust2;
 }