BallKMeans implements Iterable<Centroid> { public UpdatableSearcher cluster(List<? extends WeightedVector> datapoints) { Pair<List<? extends WeightedVector>, List<? extends WeightedVector>> trainTestSplit = splitTrainTest(datapoints); List<Vector> bestCentroids = new ArrayList<>(); double cost = Double.POSITIVE_INFINITY; double bestCost = Double.POSITIVE_INFINITY; for (int i = 0; i < numRuns; ++i) { centroids.clear(); if (kMeansPlusPlusInit) { initializeSeedsKMeansPlusPlus(trainTestSplit.getFirst()); } else { initializeSeedsRandomly(trainTestSplit.getFirst()); } if (numRuns > 1) { iterativeAssignment(trainTestSplit.getFirst()); cost = ClusteringUtils.totalClusterCost( splitTrainTest ? datapoints : trainTestSplit.getSecond(), centroids); if (cost < bestCost) { bestCost = cost; bestCentroids.clear(); Iterables.addAll(bestCentroids, centroids); } } else { iterativeAssignment(datapoints); return centroids; } } if (bestCost == Double.POSITIVE_INFINITY) { throw new RuntimeException("No valid clustering was found"); } if (cost != bestCost) { centroids.clear(); centroids.addAll(bestCentroids); } if (correctWeights) { for (WeightedVector testDatapoint : trainTestSplit.getSecond()) { WeightedVector closest = (WeightedVector) centroids.searchFirst(testDatapoint, false).getValue(); closest.setWeight(closest.getWeight() + testDatapoint.getWeight()); } } return centroids; } BallKMeans(UpdatableSearcher searcher, int numClusters, int maxNumIterations);  BallKMeans(UpdatableSearcher searcher, int numClusters, int maxNumIterations,
                    boolean kMeansPlusPlusInit, int numRuns);  BallKMeans(UpdatableSearcher searcher, int numClusters, int maxNumIterations,
                    double trimFraction, boolean kMeansPlusPlusInit, boolean correctWeights,
                    double testProbability, int numRuns); Pair<List<? extends WeightedVector>, List<? extends WeightedVector>> splitTrainTest(
      List<? extends WeightedVector> datapoints); UpdatableSearcher cluster(List<? extends WeightedVector> datapoints); @Override Iterator<Centroid> iterator();  }
@Test public void testClusteringMultipleRuns() { for (int i = 1; i <= 10; ++i) { BallKMeans clusterer = new BallKMeans(new BruteSearch(new SquaredEuclideanDistanceMeasure()), 1 << NUM_DIMENSIONS, NUM_ITERATIONS, true, i); clusterer.cluster(syntheticData.getFirst()); double costKMeansPlusPlus = ClusteringUtils.totalClusterCost(syntheticData.getFirst(), clusterer); clusterer = new BallKMeans(new BruteSearch(new SquaredEuclideanDistanceMeasure()), 1 << NUM_DIMENSIONS, NUM_ITERATIONS, false, i); clusterer.cluster(syntheticData.getFirst()); double costKMeansRandom = ClusteringUtils.totalClusterCost(syntheticData.getFirst(), clusterer); System.out.printf("%d runs; kmeans++: %f; random: %f\n", i, costKMeansPlusPlus, costKMeansRandom); assertTrue("kmeans++ cost should be less than random cost", costKMeansPlusPlus < costKMeansRandom); } }
@Test public void testClustering() { UpdatableSearcher searcher = new BruteSearch(new SquaredEuclideanDistanceMeasure()); BallKMeans clusterer = new BallKMeans(searcher, 1 << NUM_DIMENSIONS, NUM_ITERATIONS); long startTime = System.currentTimeMillis(); Pair<List<Centroid>, List<Centroid>> data = syntheticData; clusterer.cluster(data.getFirst()); long endTime = System.currentTimeMillis(); long hash = 0; for (Centroid centroid : data.getFirst()) { for (Vector.Element element : centroid.all()) { hash = 31 * hash + 17 * element.index() + Double.toHexString(element.get()).hashCode(); } } System.out.printf("Hash = %08x\n", hash); assertEquals("Total weight not preserved", totalWeight(syntheticData.getFirst()), totalWeight(clusterer), 1.0e-9); OnlineSummarizer summarizer = new OnlineSummarizer(); for (Vector mean : syntheticData.getSecond()) { WeightedThing<Vector> v = searcher.search(mean, 1).get(0); summarizer.add(v.getWeight()); } assertTrue(String.format("Median weight [%f] too large [>%f]", summarizer.getMedian(), DISTRIBUTION_RADIUS), summarizer.getMedian() < DISTRIBUTION_RADIUS); double clusterTime = (endTime - startTime) / 1000.0; System.out.printf("%s\n%.2f for clustering\n%.1f us per row\n\n", searcher.getClass().getName(), clusterTime, clusterTime / syntheticData.getFirst().size() * 1.0e6); double[] cornerWeights = new double[1 << NUM_DIMENSIONS]; Searcher trueFinder = new BruteSearch(new EuclideanDistanceMeasure()); for (Vector trueCluster : syntheticData.getSecond()) { trueFinder.add(trueCluster); } for (Centroid centroid : clusterer) { WeightedThing<Vector> closest = trueFinder.search(centroid, 1).get(0); cornerWeights[((Centroid)closest.getValue()).getIndex()] += centroid.getWeight(); } int expectedNumPoints = NUM_DATA_POINTS / (1 << NUM_DIMENSIONS); for (double v : cornerWeights) { System.out.printf("%f ", v); } System.out.println(); for (double v : cornerWeights) { assertEquals(expectedNumPoints, v, 0); } }
@Test public void testInitialization() { List<? extends WeightedVector> data = cubishTestData(0.01); BallKMeans r = new BallKMeans(new BruteSearch(new SquaredEuclideanDistanceMeasure()), 6, 20); r.cluster(data); Matrix x = new DenseMatrix(6, 5); int row = 0; for (Centroid c : r) { x.viewRow(row).assign(c.viewPart(0, 5)); row++; } final Vector columnNorms = x.aggregateColumns(new VectorFunction() { @Override public double apply(Vector f) { return Math.abs(f.minValue()) + Math.abs(f.maxValue() - 6) + Math.abs(f.norm(1) - 6); } }); assertEquals(0, columnNorms.norm(1) / columnNorms.size(), 0.1); SingularValueDecomposition svd = new SingularValueDecomposition(x); Vector s = svd.getS().viewDiagonal().assign(Functions.div(6)); assertEquals(5, s.getLengthSquared(), 0.05); assertEquals(5, s.norm(1), 0.05); }