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.evaluation;
19
20 import org.apache.commons.math4.legacy.ml.clustering.CentroidCluster;
21 import org.apache.commons.math4.legacy.ml.clustering.ClusterEvaluator;
22 import org.apache.commons.math4.legacy.ml.clustering.DoublePoint;
23 import org.apache.commons.math4.legacy.ml.clustering.KMeansPlusPlusClusterer;
24 import org.apache.commons.math4.legacy.ml.distance.DistanceMeasure;
25 import org.apache.commons.math4.legacy.ml.distance.EuclideanDistance;
26 import org.apache.commons.rng.UniformRandomProvider;
27 import org.apache.commons.rng.simple.RandomSource;
28 import org.junit.Assert;
29 import org.junit.Before;
30 import org.junit.Test;
31
32 import java.util.ArrayList;
33 import java.util.List;
34
35 public class CalinskiHarabaszTest {
36 private ClusterEvaluator evaluator;
37 private DistanceMeasure distanceMeasure;
38
39 @Before
40 public void setUp() {
41 evaluator = new CalinskiHarabasz();
42 distanceMeasure = new EuclideanDistance();
43 }
44
45 @Test
46 public void test_k_equals_4_is_best_for_a_4_center_points() {
47 final int dimension = 2;
48 final double[][] centers = {{-1, -1}, {0, 0}, {1, 1}, {2, 2}};
49 final UniformRandomProvider rnd = RandomSource.MT_64.create();
50 final List<DoublePoint> points = new ArrayList<>();
51
52 for (int i = 0; i < 1000; i++) {
53 double[] center = centers[i % centers.length];
54 double[] point = new double[dimension];
55 for (int j = 0; j < dimension; j++) {
56 double offset = (rnd.nextDouble() - 0.5) / 2;
57 Assert.assertTrue(offset < 0.25 && offset > -0.25);
58 point[j] = offset + center[j];
59 }
60 points.add(new DoublePoint(point));
61 }
62 double expectBestScore = 0.0;
63 double actualBestScore = 0.0;
64 for (int i = 0; i < 5; i++) {
65 final int k = i + 2;
66 KMeansPlusPlusClusterer<DoublePoint> kMeans = new KMeansPlusPlusClusterer<>(k, Integer.MAX_VALUE, distanceMeasure, rnd);
67 List<CentroidCluster<DoublePoint>> clusters = kMeans.cluster(points);
68 double score = evaluator.score(clusters);
69 if (score > expectBestScore) {
70 expectBestScore = score;
71 }
72 if (k == centers.length) {
73 actualBestScore = score;
74 }
75 }
76
77
78 Assert.assertEquals(expectBestScore, actualBestScore, 0.0);
79 }
80
81 @Test
82 public void test_compare_to_skLearn() {
83 final UniformRandomProvider rnd = RandomSource.MT_64.create();
84 final List<DoublePoint> points = new ArrayList<>();
85 for (double[] p : dataFromSkLearn) {
86 points.add(new DoublePoint(p));
87 }
88 double expectBestScore = 0.0;
89 double actualBestScore = 0.0;
90 for (int i = 0; i < 5; i++) {
91 final int k = i + 2;
92 KMeansPlusPlusClusterer<DoublePoint> kMeans = new KMeansPlusPlusClusterer<>(k, Integer.MAX_VALUE, distanceMeasure, rnd);
93 List<CentroidCluster<DoublePoint>> clusters = kMeans.cluster(points);
94 double score = evaluator.score(clusters);
95 if (score > expectBestScore) {
96 expectBestScore = score;
97 }
98
99
100 if (k <= kFromSkLearn) {
101 actualBestScore = score;
102 final double relScore = score / scoreFromSkLearn[i];
103 Assert.assertEquals(1, relScore, 2e-2);
104 }
105 }
106
107
108 Assert.assertEquals(expectBestScore, actualBestScore, 0.0);
109 }
110
111 static final int kFromSkLearn = 4;
112 static final double[] scoreFromSkLearn = {
113 622.487247165719, 597.7763150683217, 1157.7901325495295, 1136.8201767857847, 1092.708039201163
114 };
115 static final double[][] dataFromSkLearn = {
116 {1.403414, 1.148639}, {0.203959, 0.172137}, {2.132351, 1.883029}, {0.176704, -0.106040},
117 {-0.729892, -0.987217}, {2.073591, 1.891133}, {-0.632742, -0.847796}, {-0.080353, 0.388064},
118 {1.293772, 0.999236}, {-0.478476, -0.444240}, {1.154994, 0.922124}, {0.213056, 0.247446},
119 {1.246047, 1.329821}, {2.010432, 1.939522}, {-0.249074, 0.060909}, {1.960038, 1.883771},
120 {0.068528, -0.119460}, {1.035851, 0.992598}, {2.206471, 2.040334}, {2.114869, 2.186366},
121 {0.192118, 0.042242}, {0.194172, 0.230945}, {1.969581, 2.118761}, {1.211497, 0.803267},
122 {0.852534, 1.171513}, {2.032709, 2.068391}, {0.862354, 1.096274}, {-1.151345, -1.192454},
123 {2.642026, 1.905175}, {-1.009092, -1.383999}, {1.123967, 0.799541}, {2.452222, 2.079981},
124 {0.665412, 0.829890}, {2.145178, 1.991171}, {-1.186327, -1.110976}, {2.009537, 1.683832},
125 {1.900143, 2.059320}, {1.217072, 1.073173}, {-0.011930, 0.182649}, {-1.255492, -0.670092},
126 {0.221479, -0.239351}, {-0.155211, -0.129519}, {0.076976, 0.070879}, {2.340748, 1.728946},
127 {-0.785182, -1.003191}, {-0.048162, 0.054161}, {-0.590787, -1.261207}, {-0.322545, -1.678934},
128 {1.721805, 2.019360}, {-0.055982, 0.406160}, {1.786591, 2.030543}, {2.319241, 1.662943},
129 {-0.037710, 0.140065}, {1.255095, 1.042194}, {1.111086, 1.165950}, {-0.218115, -0.034970},
130 {2.187137, 1.692329}, {1.316916, 1.077612}, {0.112255, 0.047945}, {0.739778, 0.945151},
131 {-0.452803, -0.989958}, {2.105973, 2.005392}, {-1.090926, -0.892274}, {-0.016388, -0.243725},
132 {1.069622, 0.746740}, {2.071495, 1.707953}, {-0.734458, -0.700208}, {-0.793453, -1.142096},
133 {0.279182, 0.216376}, {-1.280766, -1.789708}, {-0.547815, -0.583041}, {1.320526, 1.312906},
134 {-0.881327, -0.716999}, {0.779240, 0.887246}, {1.925328, 1.547436}, {-0.024202, -0.206561},
135 {2.320019, 2.209286}, {-0.265125, 0.187406}, {-0.841028, -0.336119}, {-1.158193, -0.486245},
136 {2.107928, 2.027572}, {-0.203312, -0.058400}, {1.746752, 1.692956}, {-0.943192, -1.661465},
137 {-0.692261, -1.359602}, {1.189437, 1.239394}, {2.122793, 1.946352}, {0.808161, 1.145078},
138 {-0.214102, -0.254642}, {1.964497, 1.659230}, {0.162827, -0.203977}, {-1.197499, -1.150439},
139 {0.893478, 1.187206}, {2.268571, 1.937285}, {1.874589, 1.792590}, {2.115534, 2.148600},
140 {0.971884, 0.741704}, {-2.068844, -1.365312}, {1.923238, 2.135497}, {0.943657, 1.303986},
141 {2.059181, 1.866467}, {-1.150325, -1.369225}, {-0.090138, 0.186226}, {-0.361086, 0.086080},
142 {0.781402, 0.552706}, {1.788317, 2.180373}, {0.798725, 1.200775}, {-1.054850, -0.480968},
143 {-0.161374, 0.263608}, {1.261640, 0.869688}, {0.924957, 1.192590}, {1.094182, 1.031706},
144 {1.622207, 1.731404}, {-2.117348, -1.090460}, {1.005802, 1.040883}, {2.015137, 1.958903},
145 {-0.248881, 0.187862}, {1.890444, 2.059389}, {1.074242, 0.875771}, {2.004657, 1.895254},
146 {0.854140, 0.811218}, {-0.798992, -1.633529}, {0.311872, -0.109260}, {-0.219108, 0.480269},
147 {1.138654, 1.324903}, {-2.062293, -1.023073}, {0.141443, -0.087330}, {-0.745644, -0.303953},
148 {0.763012, 0.793850}, {0.975160, 0.969506}, {-1.262475, -1.264683}, {-0.934801, -0.516551},
149 {-1.342065, -0.999911}, {-0.113459, 0.213991}, {2.359609, 1.856216}, {0.408595, 0.377997},
150 {-0.382908, -1.360288}, {1.873100, 1.984283}, {-0.158167, 0.128779}, {1.001959, 0.842014},
151 {2.073056, 1.993139}, {-0.916489, -0.868636}, {1.350903, 1.159256}, {-0.999557, -1.115818},
152 {1.699934, 2.255168}, {-0.451647, 0.135991}, {1.761330, 2.091668}, {0.158764, -0.052111},
153 {0.948387, 0.928156}, {-1.723536, -0.864100}, {1.791458, 2.053596}, {0.765689, 1.028344},
154 {2.232360, 1.956492}, {-0.270874, -0.827692}, {0.702813, 0.784622}, {-0.205446, -0.314226},
155 {0.817023, 0.835158}, {-1.484335, -1.201362}, {1.875541, 1.974222}, {1.096270, 0.543190},
156 {-1.096272, -1.259179}, {-0.985800, -0.660712}, {0.095980, 0.012351}, {0.905097, 0.998787},
157 {2.087597, 1.879789}, {-0.146487, 0.088045}, {-1.606932, -1.196349}, {1.168532, 0.837345},
158 {2.119787, 2.128731}, {-0.115728, 0.016410}, {1.049650, 1.258826}, {-0.207201, -0.026785},
159 {-0.119676, 0.024613}, {-0.167932, -0.295941}, {-0.233100, -1.060121}, {1.379617, 1.104958},
160 {-0.097467, 0.075053}, {-1.153246, -0.956188}, {-0.159732, -0.364957}, {0.184015, 0.210984},
161 {-1.446427, -1.005153}, {1.970006, 2.084909}, {1.443284, 1.450596}, {1.133778, 1.024311},
162 {2.236527, 2.063874}, {0.167056, -0.170384}, {0.108058, 0.061813}, {-0.630086, -0.981357},
163 {-1.262581, -1.022503}, {0.993000, 1.033955}, {1.939089, 2.116008}, {0.888129, 1.150939},
164 {-1.033035, -0.017927}, {-1.067896, -0.033157}, {2.082978, 2.321452}, {0.975302, 0.964340},
165 {-1.199290, -1.836711}, {-1.199961, -0.825432}, {0.084522, 0.199842}, {0.129213, 0.052383}
166 };
167 }