hierarchical-clusterer.h

Go to the documentation of this file.

// Copyright 2007, Massachusetts Institute of Technology.
// The use of this code is permitted for research only. There is
// absolutely no warranty for this software.
//
// Author: John Lee (jjl@mit.edu)
//
// TODO(jjl): Allow users to pass in arbitrary Clusterer objects, not just
// hard-coded KMeansClusterer.
//

#ifndef CLUSTERING_HIERARCHICAL_CLUSTERER_H
#define CLUSTERING_HIERARCHICAL_CLUSTERER_H

#include <vector>
#include <list>
#include <iostream>
#include "clustering/clusterer.h"
#include "point_set/point-ref.h"
#include "tree/point-tree-node.h"
#include "tree/tree.cc"
#include "util/distance-computer.h"

using namespace std;

namespace libpmk {

template class Tree<PointTreeNode>;


class HierarchicalClusterer {
public:
  HierarchicalClusterer();



  const Tree<PointTreeNode>& centers() const;


  int membership(int index) const;

  int membership_size() const { return (int)membership_.size(); }


  void IdentifyMemberIDPath(int index, list<int>* out) const;


  void IdentifyMemberTreePath(int index, list<int>* out) const;


  void Cluster(int num_levels, int branch_factor,
               const vector<PointRef>& points,
               const DistanceComputer& distance_computer);


  void WriteToStream(ostream& output_stream) const;

  void WriteToFile(const char* output_filename) const;


  void ReadFromStream(istream& input_stream);

  void ReadFromFile(const char* input_filename);

  static const int MAX_ITERATIONS;

private:
  int num_levels_;
  int point_dim_;

  // RecursiveCluster() takes as input which level it's going to get
  // clusters for, as well as a list of ints. This list of ints gives
  // *indices into all_points_* to cluster (note that all_points_ itself
  // is a list of indices into the actual data).
  void RecursiveCluster(int level, const vector<int>& indices,
                        int num_levels, int branch_factor,
                        const vector<PointRef>& points,
                        const DistanceComputer& distance_computer,
                        int parent_index);

  // The cluster centers.
  Tree<PointTreeNode> centers_;

  // A vector with size equal to the number of points being clustered.
  // membership_[ii] gives the node ID of the leaf node that the <ii>th
  // point belongs to.
  vector<int> membership_;

  bool done_;
};
}  // namespace libpmk

#endif  // CLUSTERING_HIERARCHICAL_CLUSTERER_H

---