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 <iostream>
#include "clustering/clusterer.h"
#include "point_set/point-ref.h"
#include "point_set/point-set-list.h"
#include "point_set/mutable-point-set-list.h"
#include "util/sparse-vector.h"
#include "util/distance-computer.h"

using namespace std;

namespace libpmk {

class HierarchicalClusterer {
 public:
   HierarchicalClusterer();



   const PointSetList& GetClusterCenters() const;


   const vector<LargeIndex>& GetMemberships() const;

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

   pair<int, int> GetChildRange(int level, int index) const;


   int GetParentIndex(int level, int index) const;

   

   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:
   // 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);


   MutablePointSetList centers_;

   // Has the same structure as centers_, except the features are
   // 3-dim.  They tell you the index of the parent, and the start and
   // end indices of its children in the next level. -1 if N/A, like
   // if it has no children or if it has no parent.
   MutablePointSetList tree_indices_;

   // A vector of size num_levels. For each level, this tells you
   // how many centers are in that group. We need this beecause centers_
   // is sparsely done, meaning if there are clusters with 0 points,
   // they simply don't show up in centers_.
   vector<LargeIndex> memberships_;


   bool done_;
};
}  // namespace libpmk

#endif  // CLUSTERING_HIERARCHICAL_CLUSTERER_H

---