CluE  1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
lloydtype.h
Go to the documentation of this file.
1 #ifndef LLOYDTYPE_H
2 #define LLOYDTYPE_H
3 
4 #include "../base/algorithm.h"
5 #include "../base/inputsetter.h"
6 #include "../base/measuresetter.h"
7 #include "../base/proxygenerator.h"
8 #include "../base/dissimilaritymeasure.h"
9 #include "../base/solutionprovider.h"
10 #include "../datastructure/doublesolution.h"
11 
12 #include "../exception/invalidruntimeconfigurationexception.h"
13 
14 #include <set>
15 #include <ctime>
16 #include <vector>
17 
18 namespace CluE
19 {
20 
26 template<typename T>
27 class Lloydtype : public Algorithm, public InputSetter<T>, public MeasureSetter<T>
28 {
29 public:
34  Lloydtype(std::vector<T*> const* data = NULL, ProxyGenerator<T>* g = NULL,
35  DissimilarityMeasure<T>* m = NULL, unsigned int maxIterations = 0);
36 
41  Lloydtype(std::vector<T> const& seeds, std::vector<T*> const* data = NULL,
42  ProxyGenerator<T>* g = NULL, DissimilarityMeasure<T>* m = NULL, unsigned int maxIterations = 0);
43 
47  Lloydtype(std::vector<T*> const& seeds, std::vector<T*> const* data = NULL,
48  ProxyGenerator<T>* g = NULL, DissimilarityMeasure<T>* m = NULL, unsigned int i = 0);
49 
50  Lloydtype(const Lloydtype<T>&);
52  virtual ~Lloydtype();
53 
60  virtual DoubleSolution<T>* compute();
61 
62  virtual void setInput(std::vector<T*> const*);
63  void setSeeding(std::vector<T> const&);
64  void setSeeding(std::vector<T*> const&);
66  virtual void setMeasure(DissimilarityMeasure<T> const*);
67 
73 
74 private:
75  std::vector<T*> const* input;
76  std::vector<T> seeding;
79  unsigned int maxiterations;
80 };
81 
82 template<typename T> Lloydtype<T>::Lloydtype(std::vector<T*> const* data,
83  ProxyGenerator<T>* g, DissimilarityMeasure<T>* m, unsigned int i) : input(data),
84  generator(g==NULL?NULL:g->clone()), measure(m==NULL?NULL:m->clone()), maxiterations(i)
85 {
86 }
87 
88 template<typename T> Lloydtype<T>::Lloydtype(std::vector<T> const& seeds,
89  std::vector<T*> const* data, ProxyGenerator<T>* g, DissimilarityMeasure<T>* m,
90  unsigned int i) : seeding(seeds), input(data), generator(g==NULL?NULL:g->clone()),
91  measure(m==NULL?NULL:m->clone()), maxiterations(i)
92 {
93 }
94 
95 template<typename T> Lloydtype<T>::Lloydtype(std::vector<T*> const& seeds,
96  std::vector<T*> const* data, ProxyGenerator<T>* g, DissimilarityMeasure<T>* m,
97  unsigned int i) : input(data), generator(g==NULL?NULL:g->clone()),
98  measure(m==NULL?NULL:m->clone()), maxiterations(i)
99 {
100  this->setSeeding(seeds);
101 }
102 
103 template<typename T> Lloydtype<T>::Lloydtype(const Lloydtype<T>& rhs) :
104  Algorithm(rhs), input(rhs.input), seeding(rhs.seeding),
105  generator(rhs.generator==NULL?NULL:rhs.generator->clone()),
106  measure(rhs.measure==NULL?NULL:rhs.measure->clone()), maxiterations(rhs.maxiterations)
107 {
108 }
109 
110 template<typename T> Lloydtype<T>& Lloydtype<T>::operator=(const Lloydtype<T>& rhs)
111 {
112  Algorithm::operator=(rhs);
113  ProxyGenerator<T>* pg = rhs.generator==NULL?NULL:rhs.generator->clone();
114  DissimilarityMeasure<T>* dm = rhs.measure==NULL?NULL:rhs.measure->clone();
115  delete this->generator;
116  this->generator = pg;
117  delete this->measure;
118  this->measure = dm;
119  this->input = rhs.input;
120  this->seeding = rhs.seeding;
121  this->maxiterations = rhs.maxiterations;
122  return *this;
123 }
124 
125 template<typename T> Lloydtype<T>::~Lloydtype()
126 {
127  delete this->measure;
128  delete this->generator;
129 }
130 
132 {
133  if (this->input==NULL)
134  throw InvalidRuntimeConfigurationException(0, "Input is NULL.");
135  if (this->generator==NULL)
136  throw InvalidRuntimeConfigurationException(2, "Proxy generator is NULL.");
137  if (this->measure==NULL)
138  throw InvalidRuntimeConfigurationException(1, "Dissimilarity measure is NULL.");
139 
140  time_t start, end;
141  start = time(0);
142 
143  DoubleSolution<T>* solution = new DoubleSolution<T>();
144 
145  unsigned int k = this->seeding.size();
146  if (k==0)
147  throw InvalidRuntimeConfigurationException(3, "Empty seeding.");
148 
149  std::set<unsigned int> altered_clusters;
150  for (unsigned int i=0; i<k; i++)
151  altered_clusters.insert(i);
152 
153  std::vector<std::vector<T*> > partitionzero(k);
154  partitionzero[0] = *this->input;
155  solution->partitions.push_back(partitionzero);
156  solution->proxysets.push_back(this->seeding);
157 
158  bool in_motion;
159  unsigned int iterations = 0;
160  do
161  {
162  iterations++;
163  in_motion = false;
164 
165  // reassign all elements to the nearest of the current proxies
166  std::vector<std::vector<T*> > previous = solution->partitions[0];
167  solution->partitions[0] = std::vector<std::vector<T*> >(k);
168  // int di = 0;
169  for (unsigned int i=0; i<k; i++)
170  {
171  // cout << "i=" << i << std::endl;
172 
173  unsigned int size = previous[i].size();
174  for (unsigned int j=0; j<size; j++)
175  {
176  // cout << "(i,j)=(" << i << "," << j << ")" << std::endl;
177 
178  double min = this->measure->dissimilarity(*previous[i][j], solution->proxysets[0][i]);
179  unsigned int c = i;
180  for (unsigned int l=0;l<k;l++)
181  {
182  double d = this->measure->dissimilarity(*previous[i][j], solution->proxysets[0][l]);
183  if (d < min)
184  {
185  min = d;
186  c = l;
187  }
188  }
189 
190  if (c!=i)
191  {
192  in_motion = true;
193  altered_clusters.insert(i);
194  altered_clusters.insert(c);
195  }
196  solution->partitions[0][c].push_back(previous[i][j]);
197  //cout << ++di << ". element reassigned" << std::endl;
198  }
199  }
200 
202  for (std::set<unsigned int>::iterator iter=altered_clusters.begin(); iter!=altered_clusters.end(); ++iter)
203  if (solution->partitions[0][*iter].size()>0)
204  solution->proxysets[0][*iter] = this->generator->generate(solution->partitions[0][*iter]);
205 
206  //std::clog << "CluE::LloydTypee<T>::compute() - " << altered_clusters.size()
207  // << " altered clusters in iteration " << iterations << std::endl;
208  altered_clusters.clear();
209 
210  if (this->maxiterations>0 && iterations>=this->maxiterations)
211  {
212  in_motion = false;
213  //std::clog << "CluE::LloydTypee<T>::compute() - maximum number of iterations "
214  // << altered_clusters.size() << " is reached" << std::endl;
215  }
216 
217  } while (in_motion);
218 
219  end = time(0);
220  solution->seconds=end-start;
221  //std::clog << "CluE::LloydType<T>::compute() - finished after " << iterations << " iterations" << std::endl;
222  return solution;
223 }
224 
225 template<typename T> void Lloydtype<T>::setInput(std::vector<T*> const* data)
226 {
227  this->input = data;
228 }
229 
230 template<typename T> void Lloydtype<T>::setSeeding(std::vector<T> const& seeds)
231 {
232  this->seeding = seeds;
233 }
234 
235 template<typename T> void Lloydtype<T>::setSeeding(std::vector<T*> const& seeds)
236 {
237  this->seeding.clear();
238  unsigned int size = seeds.size();
239  for (unsigned int i=0;i<size;i++)
240  this->seeding.push_back(*seeds[i]);
241 }
242 
243 template<typename T> void Lloydtype<T>::setGenerator(ProxyGenerator<T>* g)
244 {
245  this->generator = g==NULL?NULL:g->clone();
246 }
247 
248 template<typename T> void Lloydtype<T>::setMeasure(DissimilarityMeasure<T> const* m)
249 {
250  this->measure = m==NULL?NULL:m->clone();
251 }
252 
254 {
255  return dynamic_cast<Lloydtype<T>*>(a);
256 }
257 
258 }
259 
260 #endif
Data structure for partitions and proxies.
Lloydtype(std::vector< T * > const *data=NULL, ProxyGenerator< T > *g=NULL, DissimilarityMeasure< T > *m=NULL, unsigned int maxIterations=0)
Constructor initializing input, seeding the centers and configuring the algorithm.
Definition: lloydtype.h:82
virtual void setMeasure(DissimilarityMeasure< T > const *)
Definition: lloydtype.h:248
ProxyGenerator< T > * generator
Definition: lloydtype.h:77
Lloydtype< T > & operator=(const Lloydtype< T > &)
Definition: lloydtype.h:110
virtual ProxyGenerator< T > * clone() const =0
void setGenerator(ProxyGenerator< T > *)
Definition: lloydtype.h:243
unsigned int maxiterations
Definition: lloydtype.h:79
virtual ~Lloydtype()
Definition: lloydtype.h:125
Abstract base class for mechanisms that compute a proxy or representative object for a given set of o...
virtual DissimilarityMeasure< T > * clone() const =0
virtual void setInput(std::vector< T * > const *)
Definition: lloydtype.h:225
static Lloydtype< T > * toLloydtype(Algorithm *a)
does a dynamic cast of the given Algorithm to Lloydtype
Definition: lloydtype.h:253
std::vector< T > seeding
Definition: lloydtype.h:76
Abstract base class for algorithms.
Definition: algorithm.h:17
Lloyd type algorithm.
Definition: lloydtype.h:27
std::vector< T * > const * input
Definition: lloydtype.h:75
void setSeeding(std::vector< T > const &)
Definition: lloydtype.h:230
Interface to propagate the ability to set a DissimilarityMeasure.
Definition: measuresetter.h:13
DissimilarityMeasure< T > * measure
Definition: lloydtype.h:78
std::vector< std::vector< T > > proxysets
virtual DoubleSolution< T > * compute()
Definition: lloydtype.h:131
Abstract base class for dissimilarity measurement.
Indicates that a computation entered an invalid configuration state.
std::vector< std::vector< std::vector< T * > > > partitions
Interface to propagate the ability to set input data.
Definition: inputsetter.h:13