Collaboration diagram for BottomUpClusterer:

Public Member Functions
	BottomUpClusterer (const std::vector< Clusterable > &points, BaseFloat max_merge_thresh, int32 min_clust, std::vector< Clusterable > clusters_out, std::vector< int32 > assignments_out)

BaseFloat	Cluster ()

	~BottomUpClusterer ()

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

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

Private Member Functions
void	Renumber ()

void	InitializeAssignments ()

void	SetInitialDistances ()
	Sets up distances and queue. More...

bool	CanMerge (int32 i, int32 j, BaseFloat dist)
	CanMerge returns true if i and j are existing clusters, and the distance (negated objf-change) "dist" is accurate (i.e. More...

void	MergeClusters (int32 i, int32 j)
	Merge j into i and delete j. More...

void	ReconstructQueue ()
	Reconstructs the priority queue from the distances. More...

void	SetDistance (int32 i, int32 j)

BaseFloat &	Distance (int32 i, int32 j)

Private Attributes
BaseFloat	ans_

const std::vector< Clusterable * > &	points_

BaseFloat	max_merge_thresh_

int32	min_clust_

std::vector< Clusterable * > *	clusters_

std::vector< int32 > *	assignments_

std::vector< Clusterable * >	tmp_clusters_

std::vector< int32 >	tmp_assignments_

std::vector< BaseFloat >	dist_vec_

int32	nclusters_

int32	npoints_

QueueType	queue_

Detailed Description

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

Member Typedef Documentation

◆ QueueElement

typedef std::pair<BaseFloat, std::pair<uint_smaller, uint_smaller> > QueueElement

private

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

◆ QueueType

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

private

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

Constructor & Destructor Documentation

◆ BottomUpClusterer()

BottomUpClusterer	(	const std::vector< Clusterable *> &	points,
		BaseFloat	max_merge_thresh,
		int32	min_clust,
		std::vector< Clusterable >	clusters_out,
		std::vector< int32 > *	assignments_out
	)

inline

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

References BottomUpClusterer::Cluster(), BottomUpClusterer::dist_vec_, BottomUpClusterer::nclusters_, and BottomUpClusterer::npoints_.

       : ans_(0.0), points_(points), max_merge_thresh_(max_merge_thresh),
         min_clust_(min_clust), clusters_(clusters_out != NULL? clusters_out
             : &tmp_clusters_), assignments_(assignments_out != NULL ?
                 assignments_out : &tmp_assignments_) {
     nclusters_ = npoints_ = points.size();
     dist_vec_.resize((npoints_ * (npoints_ - 1)) / 2);
   }

◆ ~BottomUpClusterer()

~BottomUpClusterer ( )

inline

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

References BottomUpClusterer::CanMerge(), kaldi::DeletePointers(), rnnlm::i, BottomUpClusterer::InitializeAssignments(), rnnlm::j, BottomUpClusterer::MergeClusters(), BottomUpClusterer::ReconstructQueue(), BottomUpClusterer::Renumber(), BottomUpClusterer::SetDistance(), BottomUpClusterer::SetInitialDistances(), and BottomUpClusterer::tmp_clusters_.

209 { DeletePointers(&tmp_clusters_); }

kaldi::DeletePointers

void DeletePointers(std::vector< A *> *v)

Deletes any non-NULL pointers in the vector v, and sets the corresponding entries of v to NULL...

Definition: stl-utils.h:184

kaldi::BottomUpClusterer::tmp_clusters_

std::vector< Clusterable * > tmp_clusters_

Definition: cluster-utils.cc:236

Member Function Documentation

◆ CanMerge()

bool CanMerge	(	int32	i,
		int32	j,
		BaseFloat	dist
	)

private

CanMerge returns true if i and j are existing clusters, and the distance (negated objf-change) "dist" is accurate (i.e.

not outdated).

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

References BottomUpClusterer::clusters_, BottomUpClusterer::dist_vec_, rnnlm::j, KALDI_ASSERT, and BottomUpClusterer::npoints_.

Referenced by BottomUpClusterer::Cluster(), CompartmentalizedBottomUpClusterer::Cluster(), BottomUpClusterer::~BottomUpClusterer(), and CompartmentalizedBottomUpClusterer::~CompartmentalizedBottomUpClusterer().

                                                                  {
   KALDI_ASSERT(i != j && i < npoints_ && j < npoints_);
   if ((*clusters_)[i] == NULL || (*clusters_)[j] == NULL)
     return false;
   BaseFloat cached_dist = dist_vec_[(i * (i - 1)) / 2 + j];
   return (std::fabs(cached_dist - dist) <= 1.0e-05 * std::fabs(dist));
 }

◆ Cluster()

BaseFloat Cluster ( )

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

References BottomUpClusterer::ans_, BottomUpClusterer::CanMerge(), rnnlm::i, BottomUpClusterer::InitializeAssignments(), rnnlm::j, KALDI_VLOG, BottomUpClusterer::MergeClusters(), BottomUpClusterer::min_clust_, BottomUpClusterer::nclusters_, BottomUpClusterer::queue_, BottomUpClusterer::Renumber(), and BottomUpClusterer::SetInitialDistances().

Referenced by BottomUpClusterer::BottomUpClusterer(), kaldi::ClusterBottomUp(), and CompartmentalizedBottomUpClusterer::CompartmentalizedBottomUpClusterer().

                                      {
   KALDI_VLOG(2) << "Initializing cluster assignments.";
   InitializeAssignments();
   KALDI_VLOG(2) << "Setting initial distances.";
   SetInitialDistances();
 
   KALDI_VLOG(2) << "Clustering...";
   while (nclusters_ > min_clust_ && !queue_.empty()) {
     std::pair<BaseFloat, std::pair<uint_smaller, uint_smaller> > pr = queue_.top();
     BaseFloat dist = pr.first;
     int32 i = (int32) pr.second.first, j = (int32) pr.second.second;
     queue_.pop();
     if (CanMerge(i, j, dist)) MergeClusters(i, j);
   }
   KALDI_VLOG(2) << "Renumbering clusters to contiguous numbers.";
   Renumber();
   return ans_;
 }

◆ Distance()

BaseFloat& Distance	(	int32	i,
		int32	j
	)

inlineprivate

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

References BottomUpClusterer::dist_vec_, rnnlm::j, KALDI_ASSERT, and BottomUpClusterer::npoints_.

                                         {
     KALDI_ASSERT(i < npoints_ && j < i);
     return dist_vec_[(i * (i - 1)) / 2 + j];
   }

◆ InitializeAssignments()

void InitializeAssignments ( )

private

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

References BottomUpClusterer::assignments_, BottomUpClusterer::clusters_, rnnlm::i, BottomUpClusterer::npoints_, and BottomUpClusterer::points_.

Referenced by BottomUpClusterer::Cluster(), CompartmentalizedBottomUpClusterer::Cluster(), BottomUpClusterer::~BottomUpClusterer(), and CompartmentalizedBottomUpClusterer::~CompartmentalizedBottomUpClusterer().

                                               {
   clusters_->resize(npoints_);
   assignments_->resize(npoints_);
   for (int32 i = 0; i < npoints_; i++) {  // initialize as 1-1 mapping.
     (*clusters_)[i] = points_[i]->Copy();
     (*assignments_)[i] = i;
   }
 }

◆ MergeClusters()

void MergeClusters	(	int32	i,
		int32	j
	)

private

Merge j into i and delete j.

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

References BottomUpClusterer::ans_, BottomUpClusterer::clusters_, BottomUpClusterer::dist_vec_, rnnlm::i, rnnlm::j, KALDI_ASSERT, BottomUpClusterer::nclusters_, BottomUpClusterer::npoints_, and BottomUpClusterer::SetDistance().

Referenced by BottomUpClusterer::Cluster(), CompartmentalizedBottomUpClusterer::Cluster(), BottomUpClusterer::~BottomUpClusterer(), and CompartmentalizedBottomUpClusterer::~CompartmentalizedBottomUpClusterer().

                                                       {
   KALDI_ASSERT(i != j && i < npoints_ && j < npoints_);
   (*clusters_)[i]->Add(*((*clusters_)[j]));
   delete (*clusters_)[j];
   (*clusters_)[j] = NULL;
   // note that we may have to follow the chain within "assignment_" to get
   // final assignments.
   (*assignments_)[j] = i;
   // subtract negated objective function change, i.e. add objective function
   // change.
   ans_ -= dist_vec_[(i * (i - 1)) / 2 + j];
   nclusters_--;
   // Now update "distances".
   for (int32 k = 0; k < npoints_; k++) {
     if (k != i && (*clusters_)[k] != NULL) {
       if (k < i)
         SetDistance(i, k);  // SetDistance requires k < i.
       else
         SetDistance(k, i);
     }
   }
 }

◆ ReconstructQueue()

void ReconstructQueue ( )

private

Reconstructs the priority queue from the distances.

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

References BottomUpClusterer::clusters_, BottomUpClusterer::dist_vec_, rnnlm::i, rnnlm::j, BottomUpClusterer::max_merge_thresh_, BottomUpClusterer::npoints_, BottomUpClusterer::queue_, and kaldi::swap().

Referenced by CompartmentalizedBottomUpClusterer::MergeClusters(), BottomUpClusterer::SetDistance(), BottomUpClusterer::~BottomUpClusterer(), and CompartmentalizedBottomUpClusterer::~CompartmentalizedBottomUpClusterer().

                                          {
   // empty queue [since there is no clear()]
   {
     QueueType tmp;
     std::swap(tmp, queue_);
   }
   for (int32 i = 0; i < npoints_; i++) {
     if ((*clusters_)[i] != NULL) {
       for (int32 j = 0; j < i; j++) {
         if ((*clusters_)[j] != NULL) {
           BaseFloat dist = dist_vec_[(i * (i - 1)) / 2 + j];
           if (dist <= max_merge_thresh_) {
             queue_.push(std::make_pair(dist, std::make_pair(
                 static_cast<uint_smaller>(i), static_cast<uint_smaller>(j))));
           }
         }
       }
     }
   }
 }

◆ Renumber()

void Renumber ( )

private

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

References BottomUpClusterer::assignments_, BottomUpClusterer::clusters_, BottomUpClusterer::dist_vec_, rnnlm::i, KALDI_ASSERT, KALDI_VLOG, BottomUpClusterer::nclusters_, and BottomUpClusterer::npoints_.

Referenced by BottomUpClusterer::Cluster(), CompartmentalizedBottomUpClusterer::Cluster(), BottomUpClusterer::~BottomUpClusterer(), and CompartmentalizedBottomUpClusterer::~CompartmentalizedBottomUpClusterer().

                                  {
   KALDI_VLOG(2) << "Freeing up distance vector.";
   {
     vector<BaseFloat> tmp;
     tmp.swap(dist_vec_);
   }
 
 // Commented the following out since it was causing the process to take up too
 // much memory with larger models. While the swap() method of STL types swaps 
 // the data pointers, std::swap() creates a temporary copy. -Arnab
 //  KALDI_VLOG(2) << "Freeing up the queue";
 //   // first free up memory by getting rid of queue.  this is a special trick
 //   // to force STL to free memory.
 //  {
 //    QueueType tmp;
 //    std::swap(tmp, queue_);
 //  }
 
   // called after clustering, renumbers to make clusters contiguously
   // numbered. also processes assignments_ to remove chains of references.
   KALDI_VLOG(2) << "Creating new copy of non-NULL clusters.";
   std::vector<uint_smaller> mapping(npoints_, static_cast<uint_smaller> (-1));  // mapping from intermediate to final clusters.
   std::vector<Clusterable*> new_clusters(nclusters_);
   int32 clust = 0;
   for (int32 i = 0; i < npoints_; i++) {
     if ((*clusters_)[i] != NULL) {
       KALDI_ASSERT(clust < nclusters_);
       new_clusters[clust] = (*clusters_)[i];
       mapping[i] = clust;
       clust++;
     }
   }
   KALDI_ASSERT(clust == nclusters_);
 
   KALDI_VLOG(2) << "Creating new copy of assignments.";
   std::vector<int32> new_assignments(npoints_);
   for (int32 i = 0; i < npoints_; i++) {  // now reprocess assignments_.
     int32 ii = i;
     while ((*assignments_)[ii] != ii)
       ii = (*assignments_)[ii];  // follow the chain.
     KALDI_ASSERT((*clusters_)[ii] != NULL);  // cannot have assignment to nonexistent cluster.
     KALDI_ASSERT(mapping[ii] != static_cast<uint_smaller>(-1));
     new_assignments[i] = mapping[ii];
   }
   clusters_->swap(new_clusters);
   assignments_->swap(new_assignments);
 }

◆ SetDistance()

void SetDistance	(	int32	i,
		int32	j
	)

private

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

References BottomUpClusterer::clusters_, BottomUpClusterer::dist_vec_, rnnlm::i, rnnlm::j, KALDI_ASSERT, BottomUpClusterer::max_merge_thresh_, BottomUpClusterer::npoints_, BottomUpClusterer::queue_, and BottomUpClusterer::ReconstructQueue().

Referenced by BottomUpClusterer::MergeClusters(), CompartmentalizedBottomUpClusterer::MergeClusters(), CompartmentalizedBottomUpClusterer::ReconstructQueue(), CompartmentalizedBottomUpClusterer::SetInitialDistances(), BottomUpClusterer::~BottomUpClusterer(), and CompartmentalizedBottomUpClusterer::~CompartmentalizedBottomUpClusterer().

                                                     {
   KALDI_ASSERT(i < npoints_ && j < i && (*clusters_)[i] != NULL
          && (*clusters_)[j] != NULL);
   BaseFloat dist = (*clusters_)[i]->Distance(*((*clusters_)[j]));
   dist_vec_[(i * (i - 1)) / 2 + j] = dist;  // set the distance in the array.
   if (dist < max_merge_thresh_) {
     queue_.push(std::make_pair(dist, std::make_pair(static_cast<uint_smaller>(i),
         static_cast<uint_smaller>(j))));
   }
   // every time it's at least twice the maximum possible size.
   if (queue_.size() >= static_cast<size_t> (npoints_ * npoints_)) {
     // Control memory use by getting rid of orphaned queue entries
     ReconstructQueue();
   }
 }

◆ SetInitialDistances()

void SetInitialDistances ( )

private

Sets up distances and queue.

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

References BottomUpClusterer::clusters_, BottomUpClusterer::dist_vec_, rnnlm::i, rnnlm::j, BottomUpClusterer::max_merge_thresh_, BottomUpClusterer::npoints_, and BottomUpClusterer::queue_.

Referenced by BottomUpClusterer::Cluster(), CompartmentalizedBottomUpClusterer::Cluster(), BottomUpClusterer::~BottomUpClusterer(), and CompartmentalizedBottomUpClusterer::~CompartmentalizedBottomUpClusterer().

                                             {
   for (int32 i = 0; i < npoints_; i++) {
     for (int32 j = 0; j < i; j++) {
       BaseFloat dist = (*clusters_)[i]->Distance(*((*clusters_)[j]));
       dist_vec_[(i * (i - 1)) / 2 + j] = dist;
       if (dist <= max_merge_thresh_)
         queue_.push(std::make_pair(dist, std::make_pair(static_cast<uint_smaller>(i),
             static_cast<uint_smaller>(j))));
     }
   }
 }

Member Data Documentation

◆ ans_

BaseFloat ans_

private

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

Referenced by BottomUpClusterer::Cluster(), TreeClusterer::Cluster(), BottomUpClusterer::MergeClusters(), RefineClusterer::ProcessPoint(), RefineClusterer::Refine(), and RefineClusterer::RefineClusterer().

◆ assignments_

std::vector<int32>* assignments_

private

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

Referenced by CompartmentalizedBottomUpClusterer::Cluster(), BottomUpClusterer::InitializeAssignments(), CompartmentalizedBottomUpClusterer::InitializeAssignments(), CompartmentalizedBottomUpClusterer::MergeClusters(), RefineClusterer::MovePoint(), BottomUpClusterer::Renumber(), and CompartmentalizedBottomUpClusterer::Renumber().

◆ clusters_

std::vector<Clusterable*>* clusters_

private

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

Referenced by BottomUpClusterer::CanMerge(), CompartmentalizedBottomUpClusterer::CanMerge(), CompartmentalizedBottomUpClusterer::Cluster(), BottomUpClusterer::InitializeAssignments(), CompartmentalizedBottomUpClusterer::InitializeAssignments(), BottomUpClusterer::MergeClusters(), CompartmentalizedBottomUpClusterer::MergeClusters(), BottomUpClusterer::ReconstructQueue(), CompartmentalizedBottomUpClusterer::ReconstructQueue(), RefineClusterer::RefineClusterer(), BottomUpClusterer::Renumber(), CompartmentalizedBottomUpClusterer::Renumber(), BottomUpClusterer::SetDistance(), CompartmentalizedBottomUpClusterer::SetDistance(), BottomUpClusterer::SetInitialDistances(), and CompartmentalizedBottomUpClusterer::~CompartmentalizedBottomUpClusterer().

◆ dist_vec_

std::vector<BaseFloat> dist_vec_

private

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

Referenced by BottomUpClusterer::BottomUpClusterer(), BottomUpClusterer::CanMerge(), CompartmentalizedBottomUpClusterer::CanMerge(), BottomUpClusterer::Distance(), BottomUpClusterer::MergeClusters(), CompartmentalizedBottomUpClusterer::MergeClusters(), BottomUpClusterer::ReconstructQueue(), BottomUpClusterer::Renumber(), BottomUpClusterer::SetDistance(), CompartmentalizedBottomUpClusterer::SetDistance(), BottomUpClusterer::SetInitialDistances(), and CompartmentalizedBottomUpClusterer::SetInitialDistances().

◆ max_merge_thresh_

BaseFloat max_merge_thresh_

private

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

Referenced by BottomUpClusterer::ReconstructQueue(), BottomUpClusterer::SetDistance(), CompartmentalizedBottomUpClusterer::SetDistance(), and BottomUpClusterer::SetInitialDistances().

◆ min_clust_

int32 min_clust_

private

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

Referenced by BottomUpClusterer::Cluster(), and CompartmentalizedBottomUpClusterer::Cluster().

◆ nclusters_

int32 nclusters_

private

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

Referenced by BottomUpClusterer::BottomUpClusterer(), BottomUpClusterer::Cluster(), CompartmentalizedBottomUpClusterer::Cluster(), CompartmentalizedBottomUpClusterer::CompartmentalizedBottomUpClusterer(), BottomUpClusterer::MergeClusters(), CompartmentalizedBottomUpClusterer::MergeClusters(), BottomUpClusterer::Renumber(), and CompartmentalizedBottomUpClusterer::Renumber().

◆ npoints_

int32 npoints_

private

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

◆ points_

const std::vector<Clusterable*>& points_

private

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

Referenced by TreeClusterer::CreateAssignmentsOutput(), TreeClusterer::Init(), BottomUpClusterer::InitializeAssignments(), CompartmentalizedBottomUpClusterer::InitializeAssignments(), RefineClusterer::InitPoint(), RefineClusterer::MovePoint(), RefineClusterer::RefineClusterer(), and RefineClusterer::UpdateInfo().

◆ queue_

QueueType queue_

private

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

Referenced by BottomUpClusterer::Cluster(), CompartmentalizedBottomUpClusterer::Cluster(), TreeClusterer::Cluster(), TreeClusterer::FindBestSplit(), CompartmentalizedBottomUpClusterer::MergeClusters(), BottomUpClusterer::ReconstructQueue(), CompartmentalizedBottomUpClusterer::ReconstructQueue(), CompartmentalizedBottomUpClusterer::Renumber(), BottomUpClusterer::SetDistance(), CompartmentalizedBottomUpClusterer::SetDistance(), and BottomUpClusterer::SetInitialDistances().

◆ tmp_assignments_

std::vector<int32> tmp_assignments_

private

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

◆ tmp_clusters_

std::vector<Clusterable*> tmp_clusters_

private

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

Referenced by BottomUpClusterer::~BottomUpClusterer().

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

tree/cluster-utils.cc

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ QueueElement

◆ QueueType

Constructor & Destructor Documentation

◆ BottomUpClusterer()

◆ ~BottomUpClusterer()

Member Function Documentation

◆ CanMerge()

◆ Cluster()

◆ Distance()

◆ InitializeAssignments()

◆ MergeClusters()

◆ ReconstructQueue()

◆ Renumber()

◆ SetDistance()

◆ SetInitialDistances()

Member Data Documentation

◆ ans_

◆ assignments_

◆ clusters_

◆ dist_vec_

◆ max_merge_thresh_

◆ min_clust_

◆ nclusters_

◆ npoints_

◆ points_

◆ queue_

◆ tmp_assignments_

◆ tmp_clusters_