1 #ifndef LLOYDPROBMEDIAN_HPP
2 #define LLOYDPROBMEDIAN_HPP
9 #include "WeightedPoint.hpp"
10 #include "AdaptiveSampling.hpp"
11 #include "Weiszfeld.hpp"
12 #include "CenterOfGravity.hpp"
13 #include "KumarMedian.hpp"
14 #include "ProbabilisticPoint.hpp"
31 int kumarMedianIterations;
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);
50 template<
typename ForwardIterator,
typename OutputIterator>
55 for (ForwardIterator it = begin; it != end; ++it)
57 int dimension = (*begin)[0].getDimension();
60 std::vector<WeightedPoint> allRealizations;
62 for (
auto it = begin; it != end; ++it)
67 for (
auto wpit = pp.cbegin(); wpit != pp.cend(); ++wpit)
70 wp.setWeight(wp.getWeight() * pp.getWeight());
71 allRealizations.push_back(wp);
74 int m = allRealizations.size();
75 std::unique_ptr < std::vector < Point >> initialCenters = sampling.
computeCenterSet(allRealizations.begin(), allRealizations.end(), k, m);
77 std::vector<Point> centers(*initialCenters);
78 std::vector<size_t> centerAssignmentIndices(n, 0);
79 bool assignmentChanged =
true;
80 for (
size_t i = 0; i < maxIterations && assignmentChanged; ++i)
83 assignmentChanged =
false;
84 std::vector < std::vector < WeightedPoint >> centerAssignments(k, std::vector<WeightedPoint>());
86 for (ForwardIterator it = begin; it != end; ++it)
89 double minDist = std::numeric_limits<double>::infinity();
91 for (
size_t c = 0; c < centers.size(); ++c)
94 for (
auto wpit = pp.cbegin(); wpit != pp.cend(); ++wpit)
97 tmpDist += wp.getWeight() * metric->distance(centers[c], *wpit);
99 if (tmpDist < minDist)
105 if (centerAssignmentIndices[p] != minCenter)
107 centerAssignmentIndices[p] = minCenter;
108 assignmentChanged =
true;
110 for (
auto wpit = pp.cbegin(); wpit != pp.cend(); ++wpit)
111 centerAssignments[minCenter].push_back(*wpit);
115 for (
size_t c = 0; c < centers.size(); ++c)
117 if (centerAssignments[c].size() > 0)
119 centers[c] = centerOfGravity.
cog(centerAssignments[c].begin(), centerAssignments[c].end());
123 centers[c] = weiszfeld.
approximateOneMedian(centerAssignments[c].begin(), centerAssignments[c].end(), weiszfeldMaxIt);
127 centers[c] = kumar.
approximateOneMedianRounds(centerAssignments[c].begin(), centerAssignments[c].end(), 0.9999999999, weiszfeldMaxIt);
131 centers[c] =
Point(dimension);
135 for (
size_t i = 0; i < centers.size(); ++i)
137 *output = centers[i];