1 #ifndef LLOYDMEDIAN_HPP
2 #define LLOYDMEDIAN_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"
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>
54 for (ForwardIterator it = begin; it != end; ++it)
56 int dimension = begin->getDimension();
58 std::unique_ptr < std::vector < Point >> initialCenters = sampling.
computeCenterSet(begin, end, k, n);
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)
65 assignmentChanged =
false;
66 std::vector < std::vector < WeightedPoint >> centerAssignments(k, std::vector<WeightedPoint>());
68 for (ForwardIterator it = begin; it != end; ++it)
70 double minDist = std::numeric_limits<double>::infinity();
72 for (
size_t c = 0; c < centers.size(); ++c)
74 double tmpDist = metric->distance(centers[c], *it);
75 if (tmpDist < minDist)
81 if (centerAssignmentIndices[p] != minCenter)
83 centerAssignmentIndices[p] = minCenter;
84 assignmentChanged =
true;
86 centerAssignments[minCenter].push_back(*it);
90 for (
size_t c = 0; c < centers.size(); ++c)
92 if (centerAssignments[c].size() > 0)
95 centers[c] = centerOfGravity.
cog(centerAssignments[c].begin(), centerAssignments[c].end());
99 centers[c] = weiszfeld.
approximateOneMedian(centerAssignments[c].begin(), centerAssignments[c].end(), weiszfeldMaxIt);
103 centers[c] = kumar.
approximateOneMedianRounds(centerAssignments[c].begin(), centerAssignments[c].end(), 0.9999999999, weiszfeldMaxIt);
108 centers[c] =
Point(dimension);
112 for (
size_t i = 0; i < centers.size(); ++i)
114 *output = centers[i];