PROBI  1.0
 All Classes Functions
LloydMedian.hpp
1 #ifndef LLOYDMEDIAN_HPP
2 #define LLOYDMEDIAN_HPP
3 
4 #include <algorithm>
5 #include <utility>
6 #include <memory>
7 
8 #include "Metric.hpp"
9 #include "WeightedPoint.hpp"
10 #include "AdaptiveSampling.hpp"
11 #include "Weiszfeld.hpp"
12 #include "CenterOfGravity.hpp"
13 #include "KumarMedian.hpp"
14 #include "KumarMedian.hpp"
15 
22 {
23 private:
24  AdaptiveSampling sampling;
25  Weiszfeld weiszfeld;
26  CenterOfGravity centerOfGravity;
27  KumarMedian kumar;
28  Metric<Point>* metric;
29 
30  int weiszfeldMaxIt;
31  int kumarMedianIterations;
32 public:
33  LloydMedian(std::function<Metric<Point>*() > createMetric, std::function<Norm<Point>*() > createNorm);
34 
44  template<typename ForwardIterator, typename OutputIterator>
45  void computeCenterSet(ForwardIterator begin, ForwardIterator end, OutputIterator output, size_t k, size_t maxIterations, size_t n = 0);
46 
47  virtual ~LloydMedian();
48 };
49 
50 template<typename ForwardIterator, typename OutputIterator>
51 void LloydMedian::computeCenterSet(ForwardIterator begin, ForwardIterator end, OutputIterator output, size_t k, size_t maxIterations, size_t n)
52 {
53  if (n == 0)
54  for (ForwardIterator it = begin; it != end; ++it)
55  ++n;
56  int dimension = begin->getDimension();
57 
58  std::unique_ptr < std::vector < Point >> initialCenters = sampling.computeCenterSet(begin, end, k, n);
59 
60  std::vector<Point> centers(*initialCenters);
61  std::vector<size_t> centerAssignmentIndices(n, 0);
62  bool assignmentChanged = true;
63  for (size_t i = 0; i < maxIterations && assignmentChanged; ++i)
64  {
65  assignmentChanged = false;
66  std::vector < std::vector < WeightedPoint >> centerAssignments(k, std::vector<WeightedPoint>());
67  size_t p = 0;
68  for (ForwardIterator it = begin; it != end; ++it)
69  {
70  double minDist = std::numeric_limits<double>::infinity();
71  size_t minCenter = 0;
72  for (size_t c = 0; c < centers.size(); ++c)
73  {
74  double tmpDist = metric->distance(centers[c], *it);
75  if (tmpDist < minDist)
76  {
77  minDist = tmpDist;
78  minCenter = c;
79  }
80  }
81  if (centerAssignmentIndices[p] != minCenter)
82  {
83  centerAssignmentIndices[p] = minCenter;
84  assignmentChanged = true;
85  }
86  centerAssignments[minCenter].push_back(*it);
87  ++p;
88  }
89 
90  for (size_t c = 0; c < centers.size(); ++c)
91  {
92  if (centerAssignments[c].size() > 0)
93  {
94 #ifdef KMEANS
95  centers[c] = centerOfGravity.cog(centerAssignments[c].begin(), centerAssignments[c].end());
96 #else
97  try
98  {
99  centers[c] = weiszfeld.approximateOneMedian(centerAssignments[c].begin(), centerAssignments[c].end(), weiszfeldMaxIt);
100  }
101  catch (Weiszfeld::IterationFailed err)
102  {
103  centers[c] = kumar.approximateOneMedianRounds(centerAssignments[c].begin(), centerAssignments[c].end(), 0.9999999999, weiszfeldMaxIt);
104  }
105 #endif
106  }
107  else
108  centers[c] = Point(dimension);
109  }
110  }
111 
112  for (size_t i = 0; i < centers.size(); ++i)
113  {
114  *output = centers[i];
115  ++output;
116  }
117 }
118 
119 #endif /* LLOYDMEDIAN_HPP */