@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); } }
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 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 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); }
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(); }
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();  }