CluE  1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
bruteforceclustering.h
Go to the documentation of this file.
1 #ifndef BRUTEFORCECLUSTERING_H
2 #define BRUTEFORCECLUSTERING_H
3 
4 #include <memory>
5 #include <utility>
6 
7 #include "../base/algorithm.h"
8 #include "../base/dissimilaritymeasure.h"
9 #include "../base/inputsetter.h"
10 #include "../base/measuresetter.h"
11 #include "../datastructure/proxysolution.h"
12 #include "../evaluation/kmeansevaluator.h"
13 
14 #include "../exception/invalidruntimeconfigurationexception.h"
15 #include "../exception/invalidargumentexception.h"
16 
17 namespace CluE
18 {
19 
27 template<typename T> class BruteForceClustering : public Algorithm, public InputSetter<T>, public MeasureSetter<T>
28 {
29 public:
30  BruteForceClustering(DissimilarityMeasure<T> const *measure = 0, std::vector<T*> const* input = 0, unsigned int numOfCenters = 1);
31 
37  virtual ProxySolution<T>* compute();
38 
39  virtual void setInput(std::vector<T*> const*);
40 
41  virtual void setMeasure(DissimilarityMeasure<T> const *measure);
42 
46  void setNumberOfClusters(unsigned int number);
47 
48 private:
49  std::pair<std::vector<size_t>, double> bruteCompute(std::vector<size_t> centers);
50 
52  std::unique_ptr<DissimilarityMeasure<T>> measure;
53  std::vector<T*> const *input;
54  unsigned int numClusters;
55 };
56 
57 template<typename T> BruteForceClustering<T>::BruteForceClustering(DissimilarityMeasure<T> const *measure, std::vector<T*> const* input, unsigned int numOfCenters) :
58  eval(measure),
59  measure(measure==0 ? 0 : measure->clone()),
60  input(input),
61  numClusters(numOfCenters)
62 {
63 }
64 
66 {
67  if(this->input == 0)
68  throw InvalidRuntimeConfigurationException(0, "Input is NULL.");
69  if(this->input->size() < numClusters)
70  throw InvalidRuntimeConfigurationException(2, "Input contains not enough elements.");
71  if(this->measure == 0)
72  throw InvalidRuntimeConfigurationException(1, "Dissimilarity measure is NULL.");
73 
74  std::pair<std::vector<size_t>, double> centersInd(bruteCompute(std::vector<size_t>()));
75  ProxySolution<T>* solution = new ProxySolution<T>();
76 
77  std::vector<T> centers;
78  centers.reserve(centersInd.first.size());
79  for(size_t i = 0; i < centersInd.first.size(); ++i)
80  centers.push_back(*(*input)[centersInd.first[i]]);
81  solution->proxysets.push_back(centers);
82 
83  return solution;
84 }
85 
86 template<typename T> std::pair<std::vector<size_t>, double> BruteForceClustering<T>::bruteCompute(std::vector<size_t> centers)
87 {
88  if(centers.size() == numClusters)
89  {
90  std::vector<T*> centerPointers;
91  centerPointers.reserve(centers.size());
92  for(size_t i = 0; i < centers.size(); ++i)
93  centerPointers.push_back((*input)[centers[i]]);
94  return std::pair<std::vector<size_t>, double>(centers, eval.proxycost(*input, centerPointers));
95  }
96  else
97  {
98  std::pair<std::vector<size_t>, double> min;
99  size_t lowerBound = centers.size()==0 ? 0 : centers[centers.size()-1] + 1;
100  size_t upperBound = input->size() - (numClusters-centers.size());
101  for(size_t i = lowerBound; i <= upperBound; ++i)
102  {
103  std::vector<size_t> newCenters(centers);
104  newCenters.push_back(i);
105  std::pair<std::vector<size_t>, double> tmp(bruteCompute(newCenters));
106  if(tmp.second < min.second || i == lowerBound)
107  min = tmp;
108  }
109  return min;
110  }
111 }
112 
113 template<typename T> void BruteForceClustering<T>::setNumberOfClusters(unsigned int numOfClusters)
114 {
115  this->numClusters = numOfClusters;
116 }
117 
118 template<typename T> void BruteForceClustering<T>::setInput(std::vector<T*> const* data)
119 {
120  this->input = data;
121 }
122 
123 template<typename T> void BruteForceClustering<T>::setMeasure(DissimilarityMeasure<T> const *measure)
124 {
125  if(measure == 0)
126  this->measure = 0;
127  else
128  this->measure = std::unique_ptr<DissimilarityMeasure<T>>(measure->clone());
129 }
130 
131 }
132 
133 #endif
std::pair< std::vector< size_t >, double > bruteCompute(std::vector< size_t > centers)
std::vector< std::vector< T > > proxysets
Definition: proxysolution.h:37
virtual ProxySolution< T > * compute()
void setNumberOfClusters(unsigned int number)
Sets the desired number of clusters.
std::unique_ptr< DissimilarityMeasure< T > > measure
Calculates the k-means weight.
virtual DissimilarityMeasure< T > * clone() const =0
Brute force k-median / k-means clustering.
Data structure for proxies.
Definition: proxysolution.h:19
virtual void setInput(std::vector< T * > const *)
Abstract base class for algorithms.
Definition: algorithm.h:17
virtual void setMeasure(DissimilarityMeasure< T > const *measure)
Interface to propagate the ability to set a DissimilarityMeasure.
Definition: measuresetter.h:13
std::vector< T * > const * input
BruteForceClustering(DissimilarityMeasure< T > const *measure=0, std::vector< T * > const *input=0, unsigned int numOfCenters=1)
Abstract base class for dissimilarity measurement.
Indicates that a computation entered an invalid configuration state.
Interface to propagate the ability to set input data.
Definition: inputsetter.h:13