CluE  1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
birch.h
Go to the documentation of this file.
1 #ifndef BIRCH_H
2 #define BIRCH_H
3 
4 #include <lemon/list_graph.h>
5 
6 #include "../base/streamingalgorithm.h"
7 #include "../base/inputsetter.h"
8 #include "../base/dissimilaritymeasure.h"
9 #include "../base/solutionprovider.h"
10 #include "../base/partitionprovider.h"
11 #include "../datastructure/partitionsolution.h"
12 #include "../clustering/cftree.h"
13 #include "../clustering/birchconfig.h"
14 
15 namespace CluE
16 {
17 
28 template<typename T> class Birch : public StreamingAlgorithm<T>
29 {
30 public:
31  Birch(BirchConfig<T> const * config);
32 
33  virtual PartitionSolution<T>* compute();
34  virtual Birch<T>& operator<<(T const & element);
35 
36 private:
38 
39  BirchConfig<T> const * config;
42 
46  class ThreshFuncRedirector : public CFTree<T>::ThresholdCalculator
47  {
48  public:
49  ThreshFuncRedirector(BirchConfig<T> const * config) : config(config) { }
50 
51  virtual double operator()(double t)
52  {
53  return config->calcNewThreshold(t);
54  }
55 
56  private:
58  };
59 };
60 
61 template<typename T> Birch<T>::Birch(BirchConfig<T> const * config) :
62  config(config),
63  tfr(config),
64  cft(config->euclidianProvider, config->clusterDistanceMeasure, config->thresholdAttribute, &tfr,
65  config->innerBranching, config->leafBranching, config->threshold, config->maxSize)
66 {
67 }
68 
69 template<typename T> PartitionSolution<T>* Birch<T>::compute()
70 {
71  //Phase 2
72 
73  //Phase 3
74  std::vector<CFEntry<T> > entries = cft.leafEntries();
75  std::vector<CFEntry<T>*> entriesPointer;
76  for(typename std::vector<CFEntry<T> >::iterator it = entries.begin(); it != entries.end(); ++it)
77  entriesPointer.push_back(&(*it));
78  Algorithm* alg3 = config->phase3(&entriesPointer);
79 
80  SolutionProvider* alg3sol = alg3->compute();
81  PartitionProvider<CFEntry<T> >* alg3part = dynamic_cast<PartitionProvider<CFEntry<T> >*>(alg3sol);
82  std::vector<std::vector<CFEntry<T>*> > partitions = alg3part->clustering(0);
83 
84  std::vector<T*> features;
85  for(typename std::vector<std::vector<CFEntry<T>*> >::iterator it1 = partitions.begin(); it1 != partitions.end(); ++it1)
86  {
87  CFEntry<T>* cog = new CFEntry<T>(0, config->euclidianProvider->nullVector(), 0);
88  for(typename std::vector<CFEntry<T>*>::iterator it2 = it1->begin(); it2 != it1->end(); ++it2)
89  *cog += **it2;
90  features.push_back(new T((1/cog->number) * cog->LS));
91  }
92 
93  //Phase 4
94  Algorithm* alg4 = config->phase4(&features);
95 
96  SolutionProvider* alg4sol = alg4->compute();
97  PartitionProvider<T>* alg4part = dynamic_cast<PartitionProvider<T >*>(alg4sol);
98 
99  //Prepare result
100  std::vector<std::vector<std::vector<T*> > > solvec;
101  unsigned int max = alg4part->number_of_solutions();
102  for(unsigned int i = 0; i < max; i++)
103  solvec.push_back(alg4part->clustering(i));
105  sol->partitions = solvec;
106 
107  //Clean up
108  for(typename std::vector<T*>::iterator it = features.begin(); it != features.end(); ++it)
109  delete *it;
110  delete alg3;
111  delete alg4;
112  delete alg3sol;
113  delete alg4sol;
114 
115  return sol;
116 }
117 
118 template<typename T> Birch<T>& Birch<T>::operator<<(T const & element)
119 {
120  cft.insert(element);
121 }
122 
123 }
124 
125 #endif
std::vector< std::vector< std::vector< T * > > > partitions
BIRCH configuration class.
Definition: birchconfig.h:16
BirchConfig< T > const * config
Definition: birch.h:57
virtual double operator()(double t)
Definition: birch.h:51
ThreshFuncRedirector tfr
Definition: birch.h:40
BIRCH clustering algorithm.
Definition: birch.h:28
CFTree< T > cft
Definition: birch.h:41
T LS
Linear sum.
Definition: cfentry.h:32
size_t number
Number of points contained in the feature.
Definition: cfentry.h:27
virtual double calcNewThreshold(double oldThreshold) const =0
Returns the new threshold for rebuilding the clustering feature tree.
virtual PartitionSolution< T > * compute()
Runs the algorithm and returns the computed solution.
Definition: birch.h:69
Birch(BirchConfig< T > const *config)
Definition: birch.h:61
BirchConfig< T > const * config
Definition: birch.h:37
ThreshFuncRedirector(BirchConfig< T > const *config)
Definition: birch.h:49
virtual std::vector< std::vector< T * > > clustering(unsigned int solutionIndex) const =0
Returns the specified clustering as a vector of vector of pointers to the elements.
virtual SolutionProvider * compute()=0
Runs the algorithm and returns the computed solution.
Abstract base class for algorithms.
Definition: algorithm.h:17
virtual Birch< T > & operator<<(T const &element)
Streaming operator.
Definition: birch.h:118
Abstract base class to access results of partition based clustering algorithms.
virtual unsigned int number_of_solutions() const =0
returns the number of available solutions
Abstract base class for streaming algorithms.
Clustering feature tree entry.
Definition: cfentry.h:22
Clustering feature tree.
Definition: cftree.h:34
Abstract base class for algorithm solutions.
Data structure for partitions.
Wraps around a BirchConfig object to provide threshold calculation.
Definition: birch.h:46