PROBI  1.0
 All Classes Functions
AdaptiveSampling.hpp
1 #ifndef ADAPTIVESAMPLING_HPP
2 #define ADAPTIVESAMPLING_HPP
3 
4 #include <algorithm>
5 #include <utility>
6 #include <memory>
7 #include <random>
8 
9 #include "Metric.hpp"
10 #include "WeightedPoint.hpp"
11 #include "Randomness.hpp"
12 
17 {
18 private:
19  Metric<Point>* metric;
20 public:
21  AdaptiveSampling(std::function<Metric<Point>*() > createMetric);
22  virtual ~AdaptiveSampling();
23 
32  template<typename ForwardIterator>
33  std::unique_ptr<std::vector<Point >> computeCenterSet(ForwardIterator begin, ForwardIterator end, size_t k, size_t n = 0);
34 };
35 
36 template<typename ForwardIterator>
37 std::unique_ptr<std::vector<Point >> AdaptiveSampling::computeCenterSet(ForwardIterator begin, ForwardIterator end, size_t k, size_t n)
38 {
39  if (n == 0)
40  for (ForwardIterator it = begin; it != end; ++it)
41  ++n;
42 
43  std::mt19937 * rand = Randomness::getMT19937();
44  std::unique_ptr < std::vector < Point >> centers (new std::vector<Point>(k));
45 
46  // Draw first center
47  std::uniform_int_distribution<> uniformFirst(0, n - 1);
48  size_t firstCenterIndex = uniformFirst(*rand);
49  ForwardIterator firstCenter = begin;
50  for (size_t i = 0; i < firstCenterIndex; ++i)
51  ++firstCenter;
52  (*centers)[0] = *firstCenter;
53 
54  // Draw remaining centers
55  std::uniform_real_distribution<> uniformReal(0, 1);
56  std::vector<double> weights(n, std::numeric_limits<double>::infinity());
57  for (size_t c = 1; c < k; ++c)
58  {
59  double sumWeights = 0;
60  // Update nearest center propterty of all points
61  {
62  ForwardIterator it = begin;
63  for (size_t p = 0; p < n; ++p)
64  {
65  double dist = metric->distance((*centers)[c - 1], *it);
66  if (dist < weights[p])
67  weights[p] = dist;
68  sumWeights += weights[p];
69  ++it;
70  }
71  }
72  // New center
73  {
74  // Draw random number / center
75  double nextCenterCumWeight = uniformReal(*rand);
76  // Determine new center
77  double nextCenterCumSearch = 0;
78  size_t nextCenterIndex = 0;
79  ForwardIterator it = begin;
80  for (size_t p = 0; p < n; ++p)
81  {
82  nextCenterIndex = p;
83  if (p > 0)
84  ++it;
85  double weight = weights[p];
86  if (nextCenterCumSearch + weight > nextCenterCumWeight)
87  break;
88  else
89  nextCenterCumSearch += weight;
90  }
91  (*centers)[c] = *it;
92  }
93  }
94 
95  return centers;
96 }
97 
98 #endif /* ADAPTIVESAMPLING_HPP */
99