KMeansPlusPlusClusterer extends Clusterer<T> { @Override public List<CentroidCluster<T>> cluster(final Collection<T> points) throws MathIllegalArgumentException, ConvergenceException { MathUtils.checkNotNull(points); if (points.size() < k) { throw new NumberIsTooSmallException(points.size(), k, false); } List<CentroidCluster<T>> clusters = chooseInitialCenters(points); int[] assignments = new int[points.size()]; assignPointsToClusters(clusters, points, assignments); final int max = (maxIterations < 0) ? Integer.MAX_VALUE : maxIterations; for (int count = 0; count < max; count++) { boolean emptyCluster = false; List<CentroidCluster<T>> newClusters = new ArrayList<CentroidCluster<T>>(); for (final CentroidCluster<T> cluster : clusters) { final Clusterable newCenter; if (cluster.getPoints().isEmpty()) { switch (emptyStrategy) { case LARGEST_VARIANCE : newCenter = getPointFromLargestVarianceCluster(clusters); break; case LARGEST_POINTS_NUMBER : newCenter = getPointFromLargestNumberCluster(clusters); break; case FARTHEST_POINT : newCenter = getFarthestPoint(clusters); break; default : throw new ConvergenceException(LocalizedFormats.EMPTY_CLUSTER_IN_K_MEANS); } emptyCluster = true; } else { newCenter = centroidOf(cluster.getPoints(), cluster.getCenter().getPoint().length); } newClusters.add(new CentroidCluster<T>(newCenter)); } int changes = assignPointsToClusters(newClusters, points, assignments); clusters = newClusters; if (changes == 0 && !emptyCluster) { return clusters; } } return clusters; } KMeansPlusPlusClusterer(final int k);  KMeansPlusPlusClusterer(final int k, final int maxIterations);  KMeansPlusPlusClusterer(final int k, final int maxIterations, final DistanceMeasure measure);  KMeansPlusPlusClusterer(final int k, final int maxIterations,
                                   final DistanceMeasure measure,
                                   final RandomGenerator random);  KMeansPlusPlusClusterer(final int k, final int maxIterations,
                                   final DistanceMeasure measure,
                                   final RandomGenerator random,
                                   final EmptyClusterStrategy emptyStrategy); int getK(); int getMaxIterations(); RandomGenerator getRandomGenerator(); EmptyClusterStrategy getEmptyClusterStrategy(); @Override List<CentroidCluster<T>> cluster(final Collection<T> points);  }
@Test public void testPerformClusterAnalysisDegenerate() { KMeansPlusPlusClusterer<DoublePoint> transformer = new KMeansPlusPlusClusterer<DoublePoint>(1, 1); DoublePoint[] points = new DoublePoint[] { new DoublePoint(new int[] { 1959, 325100 }), new DoublePoint(new int[] { 1960, 373200 }), }; List<? extends Cluster<DoublePoint>> clusters = transformer.cluster(Arrays.asList(points)); Assert.assertEquals(1, clusters.size()); Assert.assertEquals(2, (clusters.get(0).getPoints().size())); DoublePoint pt1 = new DoublePoint(new int[] { 1959, 325100 }); DoublePoint pt2 = new DoublePoint(new int[] { 1960, 373200 }); Assert.assertTrue(clusters.get(0).getPoints().contains(pt1)); Assert.assertTrue(clusters.get(0).getPoints().contains(pt2)); }
@Test public void testCertainSpace() { KMeansPlusPlusClusterer.EmptyClusterStrategy[] strategies = { KMeansPlusPlusClusterer.EmptyClusterStrategy.LARGEST_VARIANCE, KMeansPlusPlusClusterer.EmptyClusterStrategy.LARGEST_POINTS_NUMBER, KMeansPlusPlusClusterer.EmptyClusterStrategy.FARTHEST_POINT }; for (KMeansPlusPlusClusterer.EmptyClusterStrategy strategy : strategies) { int numberOfVariables = 27; int position1 = 1; int position2 = position1 + numberOfVariables; int position3 = position2 + numberOfVariables; int position4 = position3 + numberOfVariables; int multiplier = 1000000; DoublePoint[] breakingPoints = new DoublePoint[numberOfVariables]; for (int i = 0; i < numberOfVariables; i++) { int points[] = { position1, position2, position3, position4 }; for (int j = 0; j < points.length; j++) { points[j] *= multiplier; } DoublePoint DoublePoint = new DoublePoint(points); breakingPoints[i] = DoublePoint; position1 += numberOfVariables; position2 += numberOfVariables; position3 += numberOfVariables; position4 += numberOfVariables; } for (int n = 2; n < 27; ++n) { KMeansPlusPlusClusterer<DoublePoint> transformer = new KMeansPlusPlusClusterer<DoublePoint>(n, 100, new EuclideanDistance(), random, strategy); List<? extends Cluster<DoublePoint>> clusters = transformer.cluster(Arrays.asList(breakingPoints)); Assert.assertEquals(n, clusters.size()); int sum = 0; for (Cluster<DoublePoint> cluster : clusters) { sum += cluster.getPoints().size(); } Assert.assertEquals(numberOfVariables, sum); } } }
@Test public void testSmallDistances() { int[] repeatedArray = { 0 }; int[] uniqueArray = { 1 }; DoublePoint repeatedPoint = new DoublePoint(repeatedArray); DoublePoint uniquePoint = new DoublePoint(uniqueArray); Collection<DoublePoint> points = new ArrayList<DoublePoint>(); final int NUM_REPEATED_POINTS = 10 * 1000; for (int i = 0; i < NUM_REPEATED_POINTS; ++i) { points.add(repeatedPoint); } points.add(uniquePoint); final long RANDOM_SEED = 0; final int NUM_CLUSTERS = 2; final int NUM_ITERATIONS = 0; random.setSeed(RANDOM_SEED); KMeansPlusPlusClusterer<DoublePoint> clusterer = new KMeansPlusPlusClusterer<DoublePoint>(NUM_CLUSTERS, NUM_ITERATIONS, new CloseDistance(), random); List<CentroidCluster<DoublePoint>> clusters = clusterer.cluster(points); boolean uniquePointIsCenter = false; for (CentroidCluster<DoublePoint> cluster : clusters) { if (cluster.getCenter().equals(uniquePoint)) { uniquePointIsCenter = true; } } Assert.assertTrue(uniquePointIsCenter); }
@Test(expected=NumberIsTooSmallException.class) public void testPerformClusterAnalysisToManyClusters() { KMeansPlusPlusClusterer<DoublePoint> transformer = new KMeansPlusPlusClusterer<DoublePoint>(3, 1, new EuclideanDistance(), random); DoublePoint[] points = new DoublePoint[] { new DoublePoint(new int[] { 1959, 325100 }), new DoublePoint(new int[] { 1960, 373200 }) }; transformer.cluster(Arrays.asList(points)); }