CompartmentalizedBottomUpClusterer Class Reference

Collaboration diagram for CompartmentalizedBottomUpClusterer:

Public Member Functions
	CompartmentalizedBottomUpClusterer (const vector< vector< Clusterable *> > &points, BaseFloat max_merge_thresh, int32 min_clust)
BaseFloat	Cluster (vector< vector< Clusterable *> > *clusters_out, vector< vector< int32 > > *assignments_out)
	~CompartmentalizedBottomUpClusterer ()

Private Types
typedef std::priority_queue< CompBotClustElem, std::vector< CompBotClustElem >, std::greater< CompBotClustElem > >	QueueType

Private Member Functions
void	Renumber (int32 compartment)
void	InitializeAssignments ()
void	SetInitialDistances ()
	Sets up distances and queue. More...
bool	CanMerge (int32 compartment, 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...
BaseFloat	MergeClusters (int32 compartment, int32 i, int32 j)
	Merge j into i and delete j. Returns obj function change. More...
void	ReconstructQueue ()
	Reconstructs the priority queue from the distances. More...
void	SetDistance (int32 compartment, int32 i, int32 j)

Private Attributes
const vector< vector< Clusterable * > > &	points_
BaseFloat	max_merge_thresh_
int32	min_clust_
vector< vector< Clusterable * > >	clusters_
vector< vector< int32 > >	assignments_
vector< vector< BaseFloat > >	dist_vec_
int32	ncompartments_
int32	nclusters_
vector< int32 >	npoints_
QueueType	queue_

Detailed Description

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

Member Typedef Documentation

QueueType

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

private

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

Constructor & Destructor Documentation

CompartmentalizedBottomUpClusterer()

CompartmentalizedBottomUpClusterer ( const vector< vector< Clusterable *> > &  points, BaseFloat  max_merge_thresh, int32  min_clust  )

inline

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

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

      : points_(points), max_merge_thresh_(max_merge_thresh),
        min_clust_(min_clust) {
    ncompartments_ = points.size();
    nclusters_ = 0;
    npoints_.resize(ncompartments_);
    for (int32 comp = 0; comp < ncompartments_; comp++) {
      npoints_[comp] = points[comp].size();
      nclusters_ += npoints_[comp];
    }
  }

~CompartmentalizedBottomUpClusterer()

~CompartmentalizedBottomUpClusterer ( )

inline

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

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

                                        {
    for (vector< vector<Clusterable*> >::iterator itr = clusters_.begin(),
         end = clusters_.end(); itr != end; ++itr)
      DeletePointers(&(*itr));
  }

Member Function Documentation

CanMerge()

bool CanMerge ( int32  compartment, 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 584 of file cluster-utils.cc.

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

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

Cluster()

BaseFloat Cluster	(	vector< vector< Clusterable *> > *	clusters_out,
		vector< vector< int32 > > *	assignments_out
	)

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

References BottomUpClusterer::assignments_, BottomUpClusterer::CanMerge(), BottomUpClusterer::clusters_, CompBotClustElem::compartment, CompBotClustElem::dist, BottomUpClusterer::InitializeAssignments(), BottomUpClusterer::MergeClusters(), BottomUpClusterer::min_clust_, BottomUpClusterer::nclusters_, CompBotClustElem::point1, CompBotClustElem::point2, BottomUpClusterer::queue_, BottomUpClusterer::Renumber(), and BottomUpClusterer::SetInitialDistances().

Referenced by kaldi::ClusterBottomUpCompartmentalized().

                                              {
  InitializeAssignments();
  SetInitialDistances();
  BaseFloat total_obj_change = 0;

  while (nclusters_ > min_clust_ && !queue_.empty()) {
    CompBotClustElem qelem = queue_.top();
    queue_.pop();
    if (CanMerge(qelem.compartment, qelem.point1, qelem.point2, qelem.dist))
      total_obj_change += MergeClusters(qelem.compartment, qelem.point1,
                                        qelem.point2);
  }
  for (int32 comp = 0; comp < ncompartments_; comp++)
    Renumber(comp);
  if (clusters_out != NULL) clusters_out->swap(clusters_); 
  if (assignments_out != NULL) assignments_out->swap(assignments_);
  return total_obj_change;
}

InitializeAssignments()

void InitializeAssignments ( )

private

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

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

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

MergeClusters()

BaseFloat MergeClusters ( int32  compartment, int32  i, int32  j  )

private

Merge j into i and delete j. Returns obj function change.

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

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

                                                                     {
  KALDI_ASSERT(comp < ncompartments_ && i < npoints_[comp] && j < i);
  clusters_[comp][i]->Add(*(clusters_[comp][j]));
  delete clusters_[comp][j];
  clusters_[comp][j] = NULL;
  // note that we may have to follow the chain within "assignment_" to get
  // final assignments.
  assignments_[comp][j] = i;
  // objective function change.
  BaseFloat ans = -dist_vec_[comp][(i * (i - 1)) / 2 + j];
  nclusters_--;
  // Now update "distances".
  for (int32 k = 0; k < npoints_[comp]; k++) {
    if (k != i && clusters_[comp][k] != NULL) {
      if (k < i)
        SetDistance(comp, i, k);  // SetDistance requires k < i.
      else
        SetDistance(comp, k, i);
    }
  }
  // Control memory use by getting rid of orphaned queue entries every time
  // it's at least twice the maximum possible size.
  if (queue_.size() >= static_cast<size_t> (nclusters_ * nclusters_)) {
    ReconstructQueue();
  }
  return ans;
}

ReconstructQueue()

void ReconstructQueue ( )

private

Reconstructs the priority queue from the distances.

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

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

                                                          {
  // empty queue [since there is no clear()]
  {
    QueueType tmp;
    std::swap(tmp, queue_);
  }
  for (int32 comp = 0; comp < ncompartments_; comp++) {
    for (int32 i = 0; i < npoints_[comp]; i++) {
      if (clusters_[comp][i] == NULL) continue;
      for (int32 j = 0; j < i; j++) {
        if (clusters_[comp][j] == NULL) continue;
        SetDistance(comp, i, j);
      }
    }
  }
}

Renumber()

void Renumber ( int32  compartment )

private

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

References BottomUpClusterer::assignments_, BottomUpClusterer::clusters_, rnnlm::i, KALDI_ASSERT, BottomUpClusterer::nclusters_, BottomUpClusterer::npoints_, BottomUpClusterer::queue_, and kaldi::swap().

                                                            {
  // 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_);
  }

  // First find the number of surviving clusters in the compartment.
  int32 clusts_in_compartment = 0;
  for (int32 i = 0; i < npoints_[comp]; i++) {
    if (clusters_[comp][i] != NULL)
      clusts_in_compartment++;
  }
  KALDI_ASSERT(clusts_in_compartment <= nclusters_);

  // mapping from intermediate to final clusters.
  vector<uint_smaller> mapping(npoints_[comp], static_cast<uint_smaller> (-1));
  vector<Clusterable*> new_clusters(clusts_in_compartment);

  // Now copy the surviving clusters in a fresh array.
  clusts_in_compartment = 0;
  for (int32 i = 0; i < npoints_[comp]; i++) {
    if (clusters_[comp][i] != NULL) {
      new_clusters[clusts_in_compartment] = clusters_[comp][i];
      mapping[i] = clusts_in_compartment;
      clusts_in_compartment++;
    }
  }

  // Next, process the assignments.
  std::vector<int32> new_assignments(npoints_[comp]);
  for (int32 i = 0; i < npoints_[comp]; i++) {
    int32 ii = i;
    while (assignments_[comp][ii] != ii)
      ii = assignments_[comp][ii];  // follow the chain.
    // cannot assign to nonexistent cluster.
    KALDI_ASSERT(clusters_[comp][ii] != NULL);
    KALDI_ASSERT(mapping[ii] != static_cast<uint_smaller>(-1));
    new_assignments[i] = mapping[ii];
  }
  clusters_[comp].swap(new_clusters);
  assignments_[comp].swap(new_assignments);
}

SetDistance()

void SetDistance ( int32  compartment, int32  i, int32  j  )

private

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

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

                                                                       {
  KALDI_ASSERT(comp < ncompartments_ && i < npoints_[comp] && j < i);
  KALDI_ASSERT(clusters_[comp][i] != NULL && clusters_[comp][j] != NULL);
  BaseFloat dist = clusters_[comp][i]->Distance(*(clusters_[comp][j]));
  dist_vec_[comp][(i * (i - 1)) / 2 + j] = dist;
  if (dist < max_merge_thresh_) {
    queue_.push(CompBotClustElem(dist, comp, static_cast<uint_smaller>(i),
        static_cast<uint_smaller>(j)));
  }
}

SetInitialDistances()

void SetInitialDistances ( )

private

Sets up distances and queue.

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

References BottomUpClusterer::dist_vec_, rnnlm::i, rnnlm::j, BottomUpClusterer::npoints_, and BottomUpClusterer::SetDistance().

                                                             {
  dist_vec_.resize(ncompartments_);
  for (int32 comp = 0; comp < ncompartments_; comp++) {
    dist_vec_[comp].resize((npoints_[comp] * (npoints_[comp] - 1)) / 2);
    for (int32 i = 0; i < npoints_[comp]; i++)
      for (int32 j = 0; j < i; j++)
        SetDistance(comp, i, j);
  }
}

Member Data Documentation

assignments_

vector< vector<int32> > assignments_

private

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

clusters_

vector< vector<Clusterable*> > clusters_

private

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

dist_vec_

vector< vector<BaseFloat> > dist_vec_

private

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

max_merge_thresh_

BaseFloat max_merge_thresh_

private

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

min_clust_

int32 min_clust_

private

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

nclusters_

int32 nclusters_

private

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

ncompartments_

int32 ncompartments_

private

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

npoints_

vector<int32> npoints_

private

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

points_

const vector< vector<Clusterable*> >& points_

private

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

queue_

QueueType queue_

private

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

---

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

• tree/cluster-utils.cc