1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.apache.commons.math4.legacy.ml.clustering;
19
20 import java.util.ArrayList;
21 import java.util.Arrays;
22 import java.util.Collection;
23 import java.util.List;
24
25 import org.apache.commons.rng.UniformRandomProvider;
26 import org.apache.commons.math4.legacy.exception.NumberIsTooSmallException;
27 import org.apache.commons.math4.legacy.ml.distance.DistanceMeasure;
28 import org.apache.commons.math4.legacy.stat.descriptive.moment.VectorialMean;
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60 public class ElkanKMeansPlusPlusClusterer<T extends Clusterable>
61 extends KMeansPlusPlusClusterer<T> {
62
63
64
65
66 public ElkanKMeansPlusPlusClusterer(int k) {
67 super(k);
68 }
69
70
71
72
73
74
75
76 public ElkanKMeansPlusPlusClusterer(int k,
77 int maxIterations,
78 DistanceMeasure measure,
79 UniformRandomProvider random) {
80 super(k, maxIterations, measure, random);
81 }
82
83
84
85
86
87
88
89
90
91 public ElkanKMeansPlusPlusClusterer(int k,
92 int maxIterations,
93 DistanceMeasure measure,
94 UniformRandomProvider random,
95 EmptyClusterStrategy emptyStrategy) {
96 super(k, maxIterations, measure, random, emptyStrategy);
97 }
98
99
100 @Override
101 public List<CentroidCluster<T>> cluster(final Collection<T> points) {
102 final int k = getNumberOfClusters();
103
104
105 if (points.size() < k) {
106 throw new NumberIsTooSmallException(points.size(), k, false);
107 }
108
109 final List<T> pointsList = new ArrayList<>(points);
110 final int n = points.size();
111 final int dim = pointsList.get(0).getPoint().length;
112
113
114
115 final double[] s = new double[k];
116 Arrays.fill(s, Double.MAX_VALUE);
117
118 final double[][] dcc = new double[k][k];
119
120
121 final double[] u = new double[n];
122 Arrays.fill(u, Double.MAX_VALUE);
123
124
125 final double[][] l = new double[n][k];
126
127
128 final double[][] centers = seed(pointsList);
129
130
131
132 final int[] partitions = partitionPoints(pointsList, centers, u, l);
133
134 final double[] deltas = new double[k];
135 VectorialMean[] means = new VectorialMean[k];
136 for (int it = 0, max = getMaxIterations();
137 it < max;
138 it++) {
139 int changes = 0;
140
141
142 updateIntraCentersDistances(centers, dcc, s);
143
144 for (int xi = 0; xi < n; xi++) {
145 boolean r = true;
146
147
148 if (u[xi] <= s[partitions[xi]]) {
149 continue;
150 }
151
152 for (int c = 0; c < k; c++) {
153
154 if (isSkipNext(partitions, u, l, dcc, xi, c)) {
155 continue;
156 }
157
158 final double[] x = pointsList.get(xi).getPoint();
159
160
161 if (r) {
162 u[xi] = distance(x, centers[partitions[xi]]);
163 l[xi][partitions[xi]] = u[xi];
164 r = false;
165 }
166
167 if (u[xi] > l[xi][c] || u[xi] > dcc[partitions[xi]][c]) {
168 l[xi][c] = distance(x, centers[c]);
169 if (l[xi][c] < u[xi]) {
170 partitions[xi] = c;
171 u[xi] = l[xi][c];
172 ++changes;
173 }
174 }
175 }
176 }
177
178
179 if (changes == 0 &&
180 it != 0) {
181 break;
182 }
183
184
185 Arrays.fill(means, null);
186 for (int i = 0; i < n; i++) {
187 if (means[partitions[i]] == null) {
188 means[partitions[i]] = new VectorialMean(dim);
189 }
190 means[partitions[i]].increment(pointsList.get(i).getPoint());
191 }
192
193 for (int i = 0; i < k; i++) {
194 deltas[i] = distance(centers[i], means[i].getResult());
195 centers[i] = means[i].getResult();
196 }
197
198 updateBounds(partitions, u, l, deltas);
199 }
200
201 return buildResults(pointsList, partitions, centers);
202 }
203
204
205
206
207
208
209
210
211
212
213
214
215
216 private double[][] seed(final List<T> points) {
217 final int k = getNumberOfClusters();
218 final UniformRandomProvider random = getRandomGenerator();
219
220 final double[][] result = new double[k][];
221 final int n = points.size();
222 final int pointIndex = random.nextInt(n);
223
224 final double[] minDistances = new double[n];
225
226 int idx = 0;
227 result[idx] = points.get(pointIndex).getPoint();
228
229 double sumSqDist = 0;
230
231 for (int i = 0; i < n; i++) {
232 final double d = distance(result[idx], points.get(i).getPoint());
233 minDistances[i] = d * d;
234 sumSqDist += minDistances[i];
235 }
236
237 while (++idx < k) {
238 final double p = sumSqDist * random.nextDouble();
239 int next = 0;
240 for (double cdf = 0; cdf < p; next++) {
241 cdf += minDistances[next];
242 }
243
244 result[idx] = points.get(next - 1).getPoint();
245 for (int i = 0; i < n; i++) {
246 final double d = distance(result[idx], points.get(i).getPoint());
247 sumSqDist -= minDistances[i];
248 minDistances[i] = Math.min(minDistances[i], d * d);
249 sumSqDist += minDistances[i];
250 }
251 }
252
253 return result;
254 }
255
256
257
258
259
260
261
262
263
264
265
266
267
268 private int[] partitionPoints(List<T> pointsList,
269 double[][] centers,
270 double[] u,
271 double[][] l) {
272 final int k = getNumberOfClusters();
273 final int n = pointsList.size();
274
275 final int[] assignments = new int[n];
276 Arrays.fill(assignments, -1);
277
278 for (int i = 0; i < n; i++) {
279 final double[] x = pointsList.get(i).getPoint();
280 for (int j = 0; j < k; j++) {
281 l[i][j] = distance(x, centers[j]);
282 if (u[i] > l[i][j]) {
283 u[i] = l[i][j];
284 assignments[i] = j;
285 }
286 }
287 }
288 return assignments;
289 }
290
291
292
293
294
295
296
297
298
299
300
301 private void updateIntraCentersDistances(double[][] centers,
302 double[][] dcc,
303 double[] s) {
304 final int k = getNumberOfClusters();
305 for (int i = 0; i < k; i++) {
306
307
308
309
310 for (int j = i + 1; j < k; j++) {
311 dcc[i][j] = 0.5 * distance(centers[i], centers[j]);
312 dcc[j][i] = dcc[i][j];
313 if (dcc[i][j] < s[i]) {
314 s[i] = dcc[i][j];
315 }
316 if (dcc[j][i] < s[j]) {
317 s[j] = dcc[j][i];
318 }
319 }
320 }
321 }
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342 private static boolean isSkipNext(int[] partitions,
343 double[] u,
344 double[][] l,
345 double[][] dcc,
346 int xi,
347 int c) {
348 return c == partitions[xi] ||
349 u[xi] <= l[xi][c] ||
350 u[xi] <= dcc[partitions[xi]][c];
351 }
352
353
354
355
356
357
358
359
360
361
362
363 private List<CentroidCluster<T>> buildResults(List<T> pointsList,
364 int[] partitions,
365 double[][] centers) {
366 final int k = getNumberOfClusters();
367 final List<CentroidCluster<T>> result = new ArrayList<>();
368 for (int i = 0; i < k; i++) {
369 final CentroidCluster<T> cluster = new CentroidCluster<>(new DoublePoint(centers[i]));
370 result.add(cluster);
371 }
372 for (int i = 0; i < pointsList.size(); i++) {
373 result.get(partitions[i]).addPoint(pointsList.get(i));
374 }
375 return result;
376 }
377
378
379
380
381
382
383
384
385
386
387
388 private void updateBounds(int[] partitions,
389 double[] u,
390 double[][] l,
391 double[] deltas) {
392 final int k = getNumberOfClusters();
393 for (int i = 0; i < partitions.length; i++) {
394 u[i] += deltas[partitions[i]];
395 for (int j = 0; j < k; j++) {
396 l[i][j] = Math.max(0, l[i][j] - deltas[j]);
397 }
398 }
399 }
400
401
402
403
404
405
406 private double distance(final double[] a,
407 final double[] b) {
408 return getDistanceMeasure().compute(a, b);
409 }
410 }