Debian Codegraph @

src/SZ3/tools/mdz/include/KmeansUtil.hpp

raw
1 //
2 // Created by Kai Zhao on 12/9/19.
3 //
4
5 #ifndef _SZ_KMEANS_UTIL
6 #define _SZ_KMEANS_UTIL
7
8 #include <algorithm>
9 #include <functional>
10 #include <numeric>
11 #include <unordered_map>
12 #include <random>
13 #include <vector>
14 #include <unordered_set>
15 #include <SZ3/utils/Timer.hpp>
16 #include <SZ3/def.hpp>
17
18
19 namespace SZ {
20
21 /*
22 * Internal implementation of the SMAWK algorithm.
23 */
24 template<typename T>
25 void _smawk(
26 const std::vector<size_t> &rows,
27 const std::vector<size_t> &cols,
28 const std::function<T(size_t, size_t)> &lookup,
29 std::vector<size_t> *result) {
30 // Recursion base case
31 if (rows.size() == 0) return;
32
33 // ********************************
34 // * REDUCE
35 // ********************************
36
37 std::vector<size_t> _cols; // Stack of surviving columns
38 for (size_t col : cols) {
39 while (true) {
40 if (_cols.size() == 0) break;
41 size_t row = rows[_cols.size() - 1];
42 if (lookup(row, col) >= lookup(row, _cols.back()))
43 break;
44 _cols.pop_back();
45 }
46 if (_cols.size() < rows.size())
47 _cols.push_back(col);
48 }
49
50 // Call recursively on odd-indexed rows
51 std::vector<size_t> odd_rows;
52 for (size_t i = 1; i < rows.size(); i += 2) {
53 odd_rows.push_back(rows[i]);
54 }
55 _smawk(odd_rows, _cols, lookup, result);
56
57 std::unordered_map<size_t, size_t> col_idx_lookup;
58 for (size_t idx = 0; idx < _cols.size(); ++idx) {
59 col_idx_lookup[_cols[idx]] = idx;
60 }
61
62 // ********************************
63 // * INTERPOLATE
64 // ********************************
65
66 // Fill-in even-indexed rows
67 size_t start = 0;
68 for (size_t r = 0; r < rows.size(); r += 2) {
69 size_t row = rows[r];
70 size_t stop = _cols.size() - 1;
71 if (r < rows.size() - 1)
72 stop = col_idx_lookup[(*result)[rows[r + 1]]];
73 size_t argmin = _cols[start];
74 T min = lookup(row, argmin);
75 for (size_t c = start + 1; c <= stop; ++c) {
76 T value = lookup(row, _cols[c]);
77 if (c == start || value < min) {
78 argmin = _cols[c];
79 min = value;
80 }
81 }
82 (*result)[row] = argmin;
83 start = stop;
84 }
85 }
86
87 /*
88 * Interface for the SMAWK algorithm, for finding the minimum value in each row
89 * of an implicitly-defined totally monotone matrix.
90 */
91 template<typename T>
92 std::vector<size_t> smawk(
93 const size_t num_rows,
94 const size_t num_cols,
95 const std::function<T(size_t, size_t)> &lookup) {
96 std::vector<size_t> result;
97 result.resize(num_rows);
98 std::vector<size_t> rows(num_rows);
99 iota(begin(rows), end(rows), 0);
100 std::vector<size_t> cols(num_cols);
101 iota(begin(cols), end(cols), 0);
102 _smawk<T>(rows, cols, lookup, &result);
103 return result;
104 }
105
106 /*
107 * Calculates cluster costs in O(1) using prefix sum arrays.
108 */
109 template<class DT>
110 class CostCalculator {
111 std::vector<double> cumsum;
112 std::vector<double> cumsum2;
113
114 public:
115 CostCalculator(const std::vector<DT> &vec, size_t n) {
116 cumsum.push_back(0.0);
117 cumsum2.push_back(0.0);
118 for (size_t i = 0; i < n; ++i) {
119 double x = vec[i];
120 cumsum.push_back(x + cumsum[i]);
121 cumsum2.push_back(x * x + cumsum2[i]);
122 }
123 }
124
125 double calc(size_t i, size_t j) {
126 if (j < i) return 0.0;
127 double mu = (cumsum[j + 1] - cumsum[i]) / (j - i + 1);
128 double result = cumsum2[j + 1] - cumsum2[i];
129 result += (j - i + 1) * (mu * mu);
130 result -= (2 * mu) * (cumsum[j + 1] - cumsum[i]);
131 return result;
132 }
133 };
134
135 template<typename T>
136 class Matrix {
137 std::vector<T> data;
138 size_t num_rows;
139 size_t num_cols;
140
141 public:
142 Matrix(size_t num_rows, size_t num_cols) {
143 this->num_rows = num_rows;
144 this->num_cols = num_cols;
145 data.resize(num_rows * num_cols);
146 }
147
148 inline T get(size_t i, size_t j) {
149 return data[i * num_cols + j];
150 }
151
152 inline void set(size_t i, size_t j, T value) {
153 data[i * num_cols + j] = value;
154 }
155 };
156
157 template<class DT>
158 void cluster(
159 DT *array,
160 size_t n,
161 int &k,
162 size_t *clusters,
163 DT *centroids) {
164 // ***************************************************
165 // * Sort input array and save info for de-sorting
166 // ***************************************************
167
168 std::vector<size_t> sort_idxs(n);
169 iota(sort_idxs.begin(), sort_idxs.end(), 0);
170 sort(
171 sort_idxs.begin(),
172 sort_idxs.end(),
173 [&array](size_t a, size_t b) { return array[a] < array[b]; });
174 // vector<size_t> undo_sort_lookup(n);
175 std::vector<DT> sorted_array(n);
176 for (size_t i = 0; i < n; ++i) {
177 sorted_array[i] = array[sort_idxs[i]];
178 // undo_sort_lookup[sort_idxs[i]] = i;
179 }
180
181 // ***************************************************
182 // * Set D and T using dynamic programming algorithm
183 // ***************************************************
184
185 // Algorithm as presented in section 2.2 of (Gronlund et al., 2017).
186
187 CostCalculator<DT> cost_calculator(sorted_array, n);
188 Matrix<DT> D(k, n);
189 Matrix<size_t> T(k, n);
190
191 for (size_t i = 0; i < n; ++i) {
192 D.set(0, i, cost_calculator.calc(0, i));
193 T.set(0, i, 0);
194 }
195
196 double ratio_avg = 0;
197 bool findk = false;
198 size_t bestk = 0;
199 for (size_t k_ = 1; k_ < k; ++k_) {
200 auto C = [&D, &k_, &cost_calculator](size_t i, size_t j) -> DT {
201 size_t col = i < j - 1 ? i : j - 1;
202 return D.get(k_ - 1, col) + cost_calculator.calc(j, i);
203 };
204 std::vector<size_t> row_argmins = smawk<DT>(n, n, C);
205 for (size_t i = 0; i < row_argmins.size(); ++i) {
206 size_t argmin = row_argmins[i];
207 DT min = C(i, argmin);
208 D.set(k_, i, min);
209 T.set(k_, i, argmin);
210 }
211 float ratio = D.get(k_ - 1, n - 1) / D.get(k_, n - 1);
212 ratio_avg = (ratio_avg * (k_ - 1) + ratio) / (k_);
213 // std::cout << k_ + 1 << " , " << D.get(k_, n - 1) << " , " << ratio << " , " << ratio_avg << std::endl;
214 if (ratio / ratio_avg > 1.5) {
215 bestk = k_ + 1;
216 findk = true;
217 } else {
218 if (findk) {
219 break;
220 }
221 }
222 }
223
224 if (!findk) {
225 return;
226 }
227 k = bestk;
228 std::cout << "# groups = " << k << std::endl;
229
230 // ***************************************************
231 // * Extract cluster assignments by backtracking
232 // ***************************************************
233
234 // Note: This step requires O(kn) memory usage due to saving the entire
235 // T matrix. However, it can be modified so that the memory usage is O(n).
236 // D and T would not need to be retained in full (D already doesn't need
237 // to be fully retained, although it currently is).
238 // Details are in section 3 of (Grønlund et al., 2017).
239
240 // vector<DT> sorted_clusters(n);
241
242 size_t t = n;
243 size_t k_ = k - 1;
244 size_t n_ = n - 1;
245 // The do/while loop was used in place of:
246 // for (k_ = k - 1; k_ >= 0; --k_)
247 // to avoid wraparound of an unsigned type.
248 do {
249 size_t t_ = t;
250 t = T.get(k_, n_);
251 DT centroid = 0.0;
252 for (size_t i = t; i < t_; ++i) {
253 // sorted_clusters[i] = k_;
254 centroid += (sorted_array[i] - centroid) / (i - t + 1);
255 }
256 centroids[k_] = centroid;
257 k_ -= 1;
258 n_ = t - 1;
259 } while (t > 0);
260
261 // ***************************************************
262 // * Order cluster assignments to match de-sorted
263 // * ordering
264 // ***************************************************
265
266 // for (size_t i = 0; i < n; ++i) {
267 // clusters[i] = sorted_clusters[undo_sort_lookup[i]];
268 // }
269 }
270
271 template<class T>
272 int f(T data, double start_position, double offset) {
273 return round((data - start_position) / offset);
274 }
275
276 template<class T>
277 int f1(T data, T *boundary, int n, double start_position, double offset) {
278 return round((data - start_position) / offset);
279 }
280
281 template<class T>
282 int f2(T data, T *boundary, int n, double start_position, double offset) {
283 int low = 0, high = n; // numElems is the size of the array i.e arr.size()
284 while (low != high) {
285 int mid = (low + high) / 2; // Or a fancy way to avoid int overflow
286 if (boundary[mid] <= data) {
287 low = mid + 1;
288 } else {
289 high = mid;
290 }
291 }
292 return high;
293 }
294
295 template<class T>
296 int f3(T data, T *boundary, int n, double start_position, double offset) {
297 for (int i = 1; i < n; i++) {
298 if (boundary[i] > data) {
299 return i - 1;
300 }
301 }
302 return n - 1;
303 }
304
305
306 template<class T>
307 void get_cluster(T *data, size_t num, float &level_start, float &level_offset, int &level_num,
308 size_t sample_num) {
309 T max = *std::max_element(data, data + num);
310 T min = *std::min_element(data, data + num);
311 SZ::Timer timer;
312 timer.start();
313 std::vector<T> sample;
314 if (num == sample_num) {
315 sample = std::vector<T>(data, data + num);
316 } else {
317 sample.reserve(sample_num);
318 std::random_device rd; //Will be used to obtain a seed for the random number engine
319 std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
320 // std::uniform_int_distribution<> dis(0, 2 * sample_rate);
321 size_t input_idx = 0;
322 // for (int i = 0; i < num / sample_rate; i++) {
323 // input_idx = (input_idx + dis(gen)) % num;
324 // std::cout << input_idx << " ";
325 // sample[i] = input[input_idx];
326 // }
327 // std::cout << std::endl;
328 std::uniform_int_distribution<> dis2(0, num);
329 std::unordered_set<size_t> sampledkeys;
330 printf("total_num=%lu, sample_num=%lu\n", num, sample_num);
331 for (size_t i = 0; i < sample_num; i++) {
332 do {
333 input_idx = dis2(gen);
334 } while (sampledkeys.find(input_idx) != sampledkeys.end());
335 // std::cout << input_idx << " ";
336 sample[i] = data[input_idx];
337 }
338 // std::cout << std::endl;
339
340 // std::sample(input.begin(), input.end(),
341 // sample.begin(),
342 // num / sample_rate,
343 // std::mt19937{std::random_device{}()});
344 }
345
346 timer.stop("random sample");
347 // sample = input;
348 std::vector<size_t> idx(num);
349
350 timer.start();
351 int k = 150;
352 std::vector<float> cents(k);
353 cluster(sample.data(), sample_num, k, idx.data(), cents.data());
354 // cluster(input.get(), num, 16, idx.data(), cents.data());
355 timer.stop("kmeans1d");
356 if (k == 150) {
357 std::cout << "No clusters are found." << std::endl;
358 level_num = 0;
359 return;
360 // exit(0);
361 }
362
363 // std::cout << "centers : ";
364 // for (size_t i = 0; i < k; i++) {
365 // std::cout << cents[i] << " ";
366 // }
367 // std::cout << std::endl;
368
369 // std::cout << "center diff : ";
370 // for (size_t i = 1; i < k; i++) {
371 // std::cout << cents[i] - cents[i - 1] << " ";
372 // }
373 // std::cout << std::endl;
374
375 // std::vector<float> boundary(k);
376 // boundary[0] = std::numeric_limits<float>::min();
377 // for (size_t i = 1; i < k; i++) {
378 // boundary[i] = (cents[i - 1] + cents[i]) / 2;
379 // }
380
381 level_offset = (cents[k - 1] - cents[0]) / (k - 1);
382 level_start = cents[0];
383 for (size_t i = 1; i < k; i++) {
384 level_start += cents[i] - i * level_offset;
385 }
386 level_start /= k;
387 level_num = f(max, level_start, level_offset) + 1;
388 }
389 }
390
391 #endif