You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by df...@apache.org on 2013/05/10 11:20:32 UTC
svn commit: r1480954 - in /mahout/trunk: ./
core/src/main/java/org/apache/mahout/clustering/
core/src/main/java/org/apache/mahout/clustering/streaming/
core/src/main/java/org/apache/mahout/clustering/streaming/cluster/
core/src/test/java/org/apache/mah...
Author: dfilimon
Date: Fri May 10 09:20:31 2013
New Revision: 1480954
URL: http://svn.apache.org/r1480954
Log:
MAHOUT-1162: Adding BallKMeans and StreamingKMeans clustering algorithms
Additionally, besides the new algorithms there are new utility methods in
ClusteringUtils for casting between Vector types and computing various
clustering quality metrics: Dunn Index, Davies-Bouldin Index and the
Adjusted Rand Index.
Added:
mahout/trunk/core/src/main/java/org/apache/mahout/clustering/ClusteringUtils.java
mahout/trunk/core/src/main/java/org/apache/mahout/clustering/streaming/
mahout/trunk/core/src/main/java/org/apache/mahout/clustering/streaming/cluster/
mahout/trunk/core/src/main/java/org/apache/mahout/clustering/streaming/cluster/BallKMeans.java
mahout/trunk/core/src/main/java/org/apache/mahout/clustering/streaming/cluster/StreamingKMeans.java
mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/
mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/
mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/BallKMeansTest.java
mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/DataUtils.java
mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/StreamingKMeansTest.java
Modified:
mahout/trunk/CHANGELOG
Modified: mahout/trunk/CHANGELOG
URL: http://svn.apache.org/viewvc/mahout/trunk/CHANGELOG?rev=1480954&r1=1480953&r2=1480954&view=diff
==============================================================================
--- mahout/trunk/CHANGELOG (original)
+++ mahout/trunk/CHANGELOG Fri May 10 09:20:31 2013
@@ -2,6 +2,8 @@ Mahout Change Log
Release 0.8 - unreleased
+ MAHOUT-1162: Adding BallKMeans and StreamingKMeans clustering algorithms (dfilimon)
+
MAHOUT-1205: ParallelALSFactorizationJob should leverage the distributed cache (ssc)
MAHOUT-1156: Adding nearest neighbor Searchers (dfilimon)
Added: mahout/trunk/core/src/main/java/org/apache/mahout/clustering/ClusteringUtils.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/main/java/org/apache/mahout/clustering/ClusteringUtils.java?rev=1480954&view=auto
==============================================================================
--- mahout/trunk/core/src/main/java/org/apache/mahout/clustering/ClusteringUtils.java (added)
+++ mahout/trunk/core/src/main/java/org/apache/mahout/clustering/ClusteringUtils.java Fri May 10 09:20:31 2013
@@ -0,0 +1,283 @@
+package org.apache.mahout.clustering;
+
+import java.util.List;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
+import org.apache.mahout.common.distance.DistanceMeasure;
+import org.apache.mahout.common.distance.EuclideanDistanceMeasure;
+import org.apache.mahout.math.Centroid;
+import org.apache.mahout.math.DenseMatrix;
+import org.apache.mahout.math.Matrix;
+import org.apache.mahout.math.Vector;
+import org.apache.mahout.math.WeightedVector;
+import org.apache.mahout.math.neighborhood.BruteSearch;
+import org.apache.mahout.math.neighborhood.ProjectionSearch;
+import org.apache.mahout.math.neighborhood.Searcher;
+import org.apache.mahout.math.neighborhood.UpdatableSearcher;
+import org.apache.mahout.math.random.WeightedThing;
+import org.apache.mahout.math.stats.OnlineSummarizer;
+
+public class ClusteringUtils {
+ /**
+ * Computes the summaries for the distances in each cluster.
+ * @param datapoints iterable of datapoints.
+ * @param centroids iterable of Centroids.
+ * @return a list of OnlineSummarizers where the i-th element is the summarizer corresponding to the cluster whose
+ * index is i.
+ */
+ public static List<OnlineSummarizer> summarizeClusterDistances(Iterable<? extends Vector> datapoints,
+ Iterable<? extends Vector> centroids,
+ DistanceMeasure distanceMeasure) {
+ UpdatableSearcher searcher = new ProjectionSearch(distanceMeasure, 3, 1);
+ searcher.addAll(centroids);
+ List<OnlineSummarizer> summarizers = Lists.newArrayList();
+ if (searcher.size() == 0) {
+ return summarizers;
+ }
+ for (int i = 0; i < searcher.size(); ++i) {
+ summarizers.add(new OnlineSummarizer());
+ }
+ for (Vector v : datapoints) {
+ Centroid closest = (Centroid)searcher.search(v, 1).get(0).getValue();
+ OnlineSummarizer summarizer = summarizers.get(closest.getIndex());
+ summarizer.add(distanceMeasure.distance(v, closest));
+ }
+ return summarizers;
+ }
+
+ /**
+ * Adds up the distances from each point to its closest cluster and returns the sum.
+ * @param datapoints iterable of datapoints.
+ * @param centroids iterable of Centroids.
+ * @return the total cost described above.
+ */
+ public static double totalClusterCost(Iterable<? extends Vector> datapoints, Iterable<? extends Vector> centroids) {
+ DistanceMeasure distanceMeasure = new EuclideanDistanceMeasure();
+ UpdatableSearcher searcher = new ProjectionSearch(distanceMeasure, 3, 1);
+ searcher.addAll(centroids);
+ return totalClusterCost(datapoints, searcher);
+ }
+
+ /**
+ * Adds up the distances from each point to its closest cluster and returns the sum.
+ * @param datapoints iterable of datapoints.
+ * @param centroids searcher of Centroids.
+ * @return the total cost described above.
+ */
+ public static double totalClusterCost(Iterable<? extends Vector> datapoints, Searcher centroids) {
+ double totalCost = 0;
+ for (Vector vector : datapoints) {
+ Centroid closest = (Centroid) centroids.searchFirst(vector, false).getValue();
+ totalCost += closest.getWeight();
+ }
+ return totalCost;
+ }
+
+ /**
+ * Estimates the distance cutoff. In StreamingKMeans, the distance between two vectors divided
+ * by this value is used as a probability threshold when deciding whether to form a new cluster
+ * or not.
+ * Small values (comparable to the minimum distance between two points) are preferred as they
+ * guarantee with high likelihood that all but very close points are put in separate clusters
+ * initially. The clusters themselves are actually collapsed periodically when their number goes
+ * over the maximum number of clusters and the distanceCutoff is increased.
+ * So, the returned value is only an initial estimate.
+ * @param data the datapoints whose distance is to be estimated.
+ * @param distanceMeasure the distance measure used to compute the distance between two points.
+ * @return the minimum distance between the first sampleLimit points
+ * @see org.apache.mahout.clustering.streaming.cluster.StreamingKMeans#clusterInternal(Iterable, boolean)
+ */
+ public static double estimateDistanceCutoff(Iterable<? extends Vector> data,
+ DistanceMeasure distanceMeasure, int sampleLimit) {
+ Iterable<? extends Vector> limitedData = Iterables.limit(data, sampleLimit);
+ ProjectionSearch searcher = new ProjectionSearch(distanceMeasure, 3, 1);
+ searcher.add(limitedData.iterator().next());
+ double minDistance = Double.POSITIVE_INFINITY;
+ for (Vector vector : Iterables.skip(limitedData, 1)) {
+ double closest = searcher.searchFirst(vector, false).getWeight();
+ if (closest < minDistance) {
+ minDistance = closest;
+ }
+ searcher.add(vector);
+ }
+ return minDistance;
+ }
+
+ /**
+ * Computes the Davies-Bouldin Index for a given clustering.
+ * See http://en.wikipedia.org/wiki/Clustering_algorithm#Internal_evaluation
+ * @param centroids list of centroids
+ * @param distanceMeasure distance measure for inter-cluster distances
+ * @param clusterDistanceSummaries summaries of the clusters; See summarizeClusterDistances
+ * @return the Davies-Bouldin Index
+ */
+ public static double daviesBouldinIndex(List<? extends Vector> centroids, DistanceMeasure distanceMeasure,
+ List<OnlineSummarizer> clusterDistanceSummaries) {
+ Preconditions.checkArgument(centroids.size() == clusterDistanceSummaries.size(),
+ "Number of centroids and cluster summaries differ.");
+ int n = centroids.size();
+ double totalDBIndex = 0;
+ // The inner loop shouldn't be reduced for j = i + 1 to n because the computation of the Davies-Bouldin
+ // index is not really symmetric.
+ // For a given cluster i, we look for a cluster j that maximizes the ratio of the sum of average distances
+ // from points in cluster i to its center and and points in cluster j to its center to the distance between
+ // cluster i and cluster j.
+ // The maximization is the key issue, as the cluster that maximizes this ratio might be j for i but is NOT
+ // NECESSARILY i for j.
+ for (int i = 0; i < n; ++i) {
+ double averageDistanceI = clusterDistanceSummaries.get(i).getMean();
+ double maxDBIndex = 0;
+ for (int j = 0; j < n; ++j) {
+ if (i != j) {
+ double dbIndex = (averageDistanceI + clusterDistanceSummaries.get(j).getMean()) /
+ distanceMeasure.distance(centroids.get(i), centroids.get(j));
+ if (dbIndex > maxDBIndex) {
+ maxDBIndex = dbIndex;
+ }
+ }
+ }
+ totalDBIndex += maxDBIndex;
+ }
+ return totalDBIndex / n;
+ }
+
+ /**
+ * Computes the Dunn Index of a given clustering. See http://en.wikipedia.org/wiki/Dunn_index
+ * @param centroids list of centroids
+ * @param distanceMeasure distance measure to compute inter-centroid distance with
+ * @param clusterDistanceSummaries summaries of the clusters; See summarizeClusterDistances
+ * @return the Dunn Index
+ */
+ public static double dunnIndex(List<? extends Vector> centroids, DistanceMeasure distanceMeasure,
+ List<OnlineSummarizer> clusterDistanceSummaries) {
+ Preconditions.checkArgument(centroids.size() == clusterDistanceSummaries.size(),
+ "Number of centroids and cluster summaries differ.");
+ int n = centroids.size();
+ // Intra-cluster distances will come from the OnlineSummarizer, and will be the median distance (noting that
+ // the median for just one value is that value).
+ // A variety of metrics can be used for the intra-cluster distance including max distance between two points,
+ // mean distance, etc. Median distance was chosen as this is more robust to outliers and characterizes the
+ // distribution of distances (from a point to the center) better.
+ double maxIntraClusterDistance = 0;
+ for (OnlineSummarizer summarizer : clusterDistanceSummaries) {
+ if (summarizer.getCount() > 0) {
+ double intraClusterDistance;
+ if (summarizer.getCount() == 1) {
+ intraClusterDistance = summarizer.getMean();
+ } else {
+ intraClusterDistance = summarizer.getMedian();
+ }
+ if (maxIntraClusterDistance < intraClusterDistance) {
+ maxIntraClusterDistance = intraClusterDistance;
+ }
+ }
+ }
+ double minDunnIndex = Double.POSITIVE_INFINITY;
+ for (int i = 0; i < n; ++i) {
+ // Distances are symmetric, so d(i, j) = d(j, i).
+ for (int j = i + 1; j < n; ++j) {
+ double dunnIndex = distanceMeasure.distance(centroids.get(i), centroids.get(j));
+ if (minDunnIndex > dunnIndex) {
+ minDunnIndex = dunnIndex;
+ }
+ }
+ }
+ return minDunnIndex / maxIntraClusterDistance;
+ }
+
+ public static double choose2(double n) {
+ return n * (n - 1) / 2;
+ }
+
+ /**
+ * Creates a confusion matrix by searching for the closest cluster of both the row clustering and column clustering
+ * of a point and adding its weight to that cell of the matrix.
+ * It doesn't matter which clustering is the row clustering and which is the column clustering. If they're
+ * interchanged, the resulting matrix is the transpose of the original one.
+ * @param rowCentroids clustering one
+ * @param columnCentroids clustering two
+ * @param datapoints datapoints whose closest cluster we need to find
+ * @param distanceMeasure distance measure to use
+ * @return the confusion matrix
+ */
+ public static Matrix getConfusionMatrix(List<? extends Vector> rowCentroids, List<? extends Vector> columnCentroids,
+ Iterable<? extends Vector> datapoints, DistanceMeasure distanceMeasure) {
+ Searcher rowSearcher = new BruteSearch(distanceMeasure);
+ rowSearcher.addAll(rowCentroids);
+ Searcher columnSearcher = new BruteSearch(distanceMeasure);
+ columnSearcher.addAll(columnCentroids);
+
+ int numRows = rowCentroids.size();
+ int numCols = columnCentroids.size();
+ Matrix confusionMatrix = new DenseMatrix(numRows, numCols);
+
+ for (Vector vector : datapoints) {
+ WeightedThing<Vector> closestRowCentroid = rowSearcher.search(vector, 1).get(0);
+ WeightedThing<Vector> closestColumnCentroid = columnSearcher.search(vector, 1).get(0);
+ int row = ((Centroid) closestRowCentroid.getValue()).getIndex();
+ int column = ((Centroid) closestColumnCentroid.getValue()).getIndex();
+ double vectorWeight;
+ if (vector instanceof WeightedVector) {
+ vectorWeight = ((WeightedVector) vector).getWeight();
+ } else {
+ vectorWeight = 1;
+ }
+ confusionMatrix.set(row, column, confusionMatrix.get(row, column) + vectorWeight);
+ }
+
+ return confusionMatrix;
+ }
+
+ /**
+ * Computes the Adjusted Rand Index for a given confusion matrix.
+ * @param confusionMatrix confusion matrix; not to be confused with the more restrictive ConfusionMatrix class
+ * @return the Adjusted Rand Index
+ */
+ public static double getAdjustedRandIndex(Matrix confusionMatrix) {
+ int numRows = confusionMatrix.numRows();
+ int numCols = confusionMatrix.numCols();
+ double rowChoiceSum = 0;
+ double columnChoiceSum = 0;
+ double totalChoiceSum = 0;
+ double total = 0;
+ for (int i = 0; i < numRows; ++i) {
+ double rowSum = 0;
+ for (int j = 0; j < numCols; ++j) {
+ rowSum += confusionMatrix.get(i, j);
+ totalChoiceSum += choose2(confusionMatrix.get(i, j));
+ }
+ total += rowSum;
+ rowChoiceSum += choose2(rowSum);
+ }
+ for (int j = 0; j < numCols; ++j) {
+ double columnSum = 0;
+ for (int i = 0; i < numRows; ++i) {
+ columnSum += confusionMatrix.get(i, j);
+ }
+ columnChoiceSum += choose2(columnSum);
+ }
+ double rowColumnChoiceSumDivTotal = rowChoiceSum * columnChoiceSum / choose2(total);
+ return (totalChoiceSum - rowColumnChoiceSumDivTotal)
+ / ((rowChoiceSum + columnChoiceSum) / 2 - rowColumnChoiceSumDivTotal);
+ }
+
+ /**
+ * Computes the total weight of the points in the given Vector iterable.
+ * @param data iterable of points
+ * @return total weight
+ */
+ public static double totalWeight(Iterable<? extends Vector> data) {
+ double sum = 0;
+ for (Vector row : data) {
+ Preconditions.checkNotNull(row);
+ if (row instanceof WeightedVector) {
+ sum += ((WeightedVector)row).getWeight();
+ } else {
+ sum++;
+ }
+ }
+ return sum;
+ }
+}
Added: mahout/trunk/core/src/main/java/org/apache/mahout/clustering/streaming/cluster/BallKMeans.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/main/java/org/apache/mahout/clustering/streaming/cluster/BallKMeans.java?rev=1480954&view=auto
==============================================================================
--- mahout/trunk/core/src/main/java/org/apache/mahout/clustering/streaming/cluster/BallKMeans.java (added)
+++ mahout/trunk/core/src/main/java/org/apache/mahout/clustering/streaming/cluster/BallKMeans.java Fri May 10 09:20:31 2013
@@ -0,0 +1,456 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.clustering.streaming.cluster;
+
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Random;
+
+import com.google.common.base.Function;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Iterators;
+import com.google.common.collect.Lists;
+import org.apache.mahout.clustering.ClusteringUtils;
+import org.apache.mahout.common.Pair;
+import org.apache.mahout.common.RandomUtils;
+import org.apache.mahout.common.distance.DistanceMeasure;
+import org.apache.mahout.math.Centroid;
+import org.apache.mahout.math.Vector;
+import org.apache.mahout.math.WeightedVector;
+import org.apache.mahout.math.neighborhood.UpdatableSearcher;
+import org.apache.mahout.math.random.Multinomial;
+import org.apache.mahout.math.random.WeightedThing;
+
+/**
+ * Implements a ball k-means algorithm for weighted vectors with probabilistic seeding similar to k-means++.
+ * The idea is that k-means++ gives good starting clusters and ball k-means can tune up the final result very nicely
+ * in only a few passes (or even in a single iteration for well-clusterable data).
+ *
+ * A good reference for this class of algorithms is "The Effectiveness of Lloyd-Type Methods for the k-Means Problem"
+ * by Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman and Chaitanya Swamy. The code here uses the seeding strategy
+ * as described in section 4.1.1 of that paper and the ball k-means step as described in section 4.2. We support
+ * multiple iterations in contrast to the algorithm described in the paper.
+ */
+public class BallKMeans implements Iterable<Centroid> {
+ /**
+ * The searcher containing the centroids.
+ */
+ private final UpdatableSearcher centroids;
+
+ /**
+ * The number of clusters to cluster the data into.
+ */
+ private final int numClusters;
+
+ /**
+ * The maximum number of iterations of the algorithm to run waiting for the cluster assignments
+ * to stabilize. If there are no changes in cluster assignment earlier, we can finish early.
+ */
+ private final int maxNumIterations;
+
+ /**
+ * When deciding which points to include in the new centroid calculation,
+ * it's preferable to exclude outliers since it increases the rate of convergence.
+ * So, we calculate the distance from each cluster to its closest neighboring cluster. When
+ * evaluating the points assigned to a cluster, we compare the distance between the centroid to
+ * the point with the distance between the centroid and its closest centroid neighbor
+ * multiplied by this trimFraction. If the distance between the centroid and the point is
+ * greater, we consider it an outlier and we don't use it.
+ */
+ private final double trimFraction;
+
+ /**
+ * Selecting the initial centroids is the most important part of the ball k-means clustering. Poor choices, like two
+ * centroids in the same actual cluster result in a low-quality final result.
+ * k-means++ initialization yields good quality clusters, especially when using BallKMeans after StreamingKMeans as
+ * the points have weights.
+ * Simple, random selection of the points based on their weights is faster but sometimes fails to produce the
+ * desired number of clusters.
+ * This field is true if the initialization should be done with k-means++.
+ */
+ private final boolean kMeansPlusPlusInit;
+
+ /**
+ * When using trimFraction, the weight of each centroid will not be the sum of the weights of
+ * the vectors assigned to that cluster because outliers are not used to compute the updated
+ * centroid.
+ * So, the total weight is probably wrong. This can be fixed by doing another pass over the
+ * data points and adjusting the weights of each centroid. This doesn't update the coordinates
+ * of the centroids, but is useful if the weights matter.
+ */
+ private final boolean correctWeights;
+
+ /**
+ * When running multiple ball k-means passes to get the one with the smallest total cost, can compute the
+ * overall cost, using all the points for clustering, or reserve a fraction of them, testProbability in a test set.
+ * The cost is the sum of the distances between each point and its corresponding centroid.
+ * We then use this set of points to compute the total cost on. We're therefore trying to select the clustering
+ * that best describes the underlying distribution of the clusters.
+ * This field is the probability of assigning a given point to the test set. If this is 0, the cost will be computed
+ * on the entire set of points.
+ */
+ private final double testProbability;
+
+ /**
+ * Whether or not testProbability > 0, i.e., there exists a non-empty 'test' set.
+ */
+ private final boolean splitTrainTest;
+
+ /**
+ * How many k-means runs to have. If there's more than one run, we compute the cost of each clustering as described
+ * above and select the clustering that minimizes the cost.
+ * Multiple runs are a lot more useful when using the random initialization. With kmeans++, 1-2 runs are enough and
+ * more runs are not likely to help quality much.
+ */
+ private final int numRuns;
+
+ /**
+ * Random object to sample values from.
+ */
+ private final Random random;
+
+ public BallKMeans(UpdatableSearcher searcher, int numClusters, int maxNumIterations) {
+ // By default, the trimFraction is 0.9, k-means++ is used, the weights will be corrected at the end,
+ // there will be 0 points in the test set and 1 run.
+ this(searcher, numClusters, maxNumIterations, 0.9, true, true, 0.0, 1);
+ }
+
+ public BallKMeans(UpdatableSearcher searcher, int numClusters, int maxNumIterations,
+ boolean kMeansPlusPlusInit, int numRuns) {
+ // By default, the trimFraction is 0.9, k-means++ is used, the weights will be corrected at the end,
+ // there will be 10% points of in the test set.
+ this(searcher, numClusters, maxNumIterations, 0.9, kMeansPlusPlusInit, true, 0.1, numRuns);
+ }
+
+ public BallKMeans(UpdatableSearcher searcher, int numClusters, int maxNumIterations,
+ double trimFraction, boolean kMeansPlusPlusInit, boolean correctWeights,
+ double testProbability, int numRuns) {
+ Preconditions.checkArgument(searcher.size() == 0, "Searcher must be empty initially to populate with centroids");
+ Preconditions.checkArgument(numClusters > 0, "The requested number of clusters must be positive");
+ Preconditions.checkArgument(maxNumIterations > 0, "The maximum number of iterations must be positive");
+ Preconditions.checkArgument(trimFraction > 0, "The trim fraction must be positive");
+ Preconditions.checkArgument(testProbability >= 0 && testProbability < 1, "The testProbability must be in [0, 1)");
+ Preconditions.checkArgument(numRuns > 0, "There has to be at least one run");
+
+ this.centroids = searcher;
+ this.numClusters = numClusters;
+ this.maxNumIterations = maxNumIterations;
+
+ this.trimFraction = trimFraction;
+ this.kMeansPlusPlusInit = kMeansPlusPlusInit;
+ this.correctWeights = correctWeights;
+
+ this.testProbability = testProbability;
+ this.splitTrainTest = testProbability > 0;
+ this.numRuns = numRuns;
+
+ this.random = RandomUtils.getRandom();
+ }
+
+ public Pair<List<? extends WeightedVector>, List<? extends WeightedVector>> splitTrainTest(
+ List<? extends WeightedVector> datapoints) {
+ // If there will be no points assigned to the test set, return now.
+ if (testProbability == 0) {
+ return new Pair<List<? extends WeightedVector>, List<? extends WeightedVector>>(datapoints,
+ Lists.<WeightedVector>newArrayList());
+ }
+
+ int numTest = (int) (testProbability * datapoints.size());
+ Preconditions.checkArgument(numTest > 0 && numTest < datapoints.size(),
+ "Must have nonzero number of training and test vectors. Asked for %.1f %% of %d vectors for test",
+ testProbability * 100, datapoints.size());
+
+ Collections.shuffle(datapoints);
+ return new Pair<List<? extends WeightedVector>, List<? extends WeightedVector>>(
+ datapoints.subList(numTest, datapoints.size()), datapoints.subList(0, numTest));
+ }
+
+ /**
+ * Clusters the datapoints in the list doing either random seeding of the centroids or k-means++.
+ *
+ * @param datapoints the points to be clustered.
+ * @return an UpdatableSearcher with the resulting clusters.
+ */
+ public UpdatableSearcher cluster(List<? extends WeightedVector> datapoints) {
+ Pair<List<? extends WeightedVector>, List<? extends WeightedVector>> trainTestSplit = splitTrainTest(datapoints);
+ List<Vector> bestCentroids = Lists.newArrayList();
+ double cost = Double.POSITIVE_INFINITY;
+ double bestCost = Double.POSITIVE_INFINITY;
+ for (int i = 0; i < numRuns; ++i) {
+ centroids.clear();
+ if (kMeansPlusPlusInit) {
+ // Use k-means++ to set initial centroids.
+ initializeSeedsKMeansPlusPlus(trainTestSplit.getFirst());
+ } else {
+ // Randomly select the initial centroids.
+ initializeSeedsRandomly(trainTestSplit.getFirst());
+ }
+ // Do k-means iterations with trimmed mean computation (aka ball k-means).
+ if (numRuns > 1) {
+ // If the clustering is successful (there are no zero-weight centroids).
+ iterativeAssignment(trainTestSplit.getFirst());
+ // Compute the cost of the clustering and possibly save the centroids.
+ cost = ClusteringUtils.totalClusterCost(
+ splitTrainTest ? datapoints : trainTestSplit.getSecond(), centroids);
+ if (cost < bestCost) {
+ bestCost = cost;
+ bestCentroids.clear();
+ Iterables.addAll(bestCentroids, centroids);
+ }
+ } else {
+ // If there is only going to be one run, the cost doesn't need to be computed, so we just return the clustering.
+ 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;
+ }
+
+ /**
+ * Selects some of the original points randomly with probability proportional to their weights. This is much
+ * less sophisticated than the kmeans++ approach, however it is faster and coupled with
+ *
+ * The side effect of this method is to fill the centroids structure itself.
+ *
+ * @param datapoints The datapoints to select from. These datapoints should be WeightedVectors of some kind.
+ */
+ private void initializeSeedsRandomly(List<? extends WeightedVector> datapoints) {
+ Multinomial<Integer> seedSelector = new Multinomial<Integer>();
+ int numDatapoints = datapoints.size();
+ double totalWeight = 0;
+ for (WeightedVector datapoint : datapoints) {
+ totalWeight += datapoint.getWeight();
+ }
+ for (int i = 0; i < numDatapoints; ++i) {
+ seedSelector.add(i, datapoints.get(i).getWeight() / totalWeight);
+ }
+ for (int i = 0; i < numClusters; ++i) {
+ int sample = seedSelector.sample();
+ seedSelector.delete(sample);
+ Centroid centroid = new Centroid(datapoints.get(sample));
+ centroid.setIndex(i);
+ centroids.add(centroid);
+ }
+ }
+
+ /**
+ * Selects some of the original points according to the k-means++ algorithm. The basic idea is that
+ * points are selected with probability proportional to their distance from any selected point. In
+ * this version, points have weights which multiply their likelihood of being selected. This is the
+ * same as if there were as many copies of the same point as indicated by the weight.
+ *
+ * This is pretty expensive, but it vastly improves the quality and convergences of the k-means algorithm.
+ * The basic idea can be made much faster by only processing a random subset of the original points.
+ * In the context of streaming k-means, the total number of possible seeds will be about k log n so this
+ * selection will cost O(k^2 (log n)^2) which isn't much worse than the random sampling idea. At
+ * n = 10^9, the cost of this initialization will be about 10x worse than a reasonable random sampling
+ * implementation.
+ *
+ * The side effect of this method is to fill the centroids structure itself.
+ *
+ * @param datapoints The datapoints to select from. These datapoints should be WeightedVectors of some kind.
+ */
+ private void initializeSeedsKMeansPlusPlus(List<? extends WeightedVector> datapoints) {
+ Preconditions.checkArgument(datapoints.size() > 1, "Must have at least two datapoints points to cluster " +
+ "sensibly");
+ Preconditions.checkArgument(datapoints.size() >= numClusters,
+ String.format("Must have more datapoints [%d] than clusters [%d]", datapoints.size(), numClusters));
+ // Compute the centroid of all of the datapoints. This is then used to compute the squared radius of the datapoints.
+ Centroid center = new Centroid(datapoints.iterator().next());
+ for (WeightedVector row : Iterables.skip(datapoints, 1)) {
+ center.update(row);
+ }
+
+ // Given the centroid, we can compute \Delta_1^2(X), the total squared distance for the datapoints
+ // this accelerates seed selection.
+ double deltaX = 0;
+ DistanceMeasure distanceMeasure = centroids.getDistanceMeasure();
+ for (WeightedVector row : datapoints) {
+ deltaX += distanceMeasure.distance(row, center);
+ }
+
+ // Find the first seed c_1 (and conceptually the second, c_2) as might be done in the 2-means clustering so that
+ // the probability of selecting c_1 and c_2 is proportional to || c_1 - c_2 ||^2. This is done
+ // by first selecting c_1 with probability:
+ //
+ // p(c_1) = sum_{c_1} || c_1 - c_2 ||^2 \over sum_{c_1, c_2} || c_1 - c_2 ||^2
+ //
+ // This can be simplified to:
+ //
+ // p(c_1) = \Delta_1^2(X) + n || c_1 - c ||^2 / (2 n \Delta_1^2(X))
+ //
+ // where c = \sum x / n and \Delta_1^2(X) = sum || x - c ||^2
+ //
+ // All subsequent seeds c_i (including c_2) can then be selected from the remaining points with probability
+ // proportional to Pr(c_i == x_j) = min_{m < i} || c_m - x_j ||^2.
+
+ // Multinomial distribution of vector indices for the selection seeds. These correspond to
+ // the indices of the vectors in the original datapoints list.
+ Multinomial<Integer> seedSelector = new Multinomial<Integer>();
+ for (int i = 0; i < datapoints.size(); ++i) {
+ double selectionProbability =
+ deltaX + datapoints.size() * distanceMeasure.distance(datapoints.get(i), center);
+ seedSelector.add(i, selectionProbability);
+ }
+
+ int selected = random.nextInt(datapoints.size());
+ Centroid c_1 = new Centroid(datapoints.get(selected).clone());
+ c_1.setIndex(0);
+ // Construct a set of weighted things which can be used for random selection. Initial weights are
+ // set to the squared distance from c_1
+ for (int i = 0; i < datapoints.size(); ++i) {
+ WeightedVector row = datapoints.get(i);
+ final double w = distanceMeasure.distance(c_1, row) * row.getWeight();
+ seedSelector.set(i, w);
+ }
+
+ // From here, seeds are selected with probability proportional to:
+ //
+ // r_i = min_{c_j} || x_i - c_j ||^2
+ //
+ // when we only have c_1, we have already set these distances and as we select each new
+ // seed, we update the minimum distances.
+ centroids.add(c_1);
+ int clusterIndex = 1;
+ while (centroids.size() < numClusters) {
+ // Select according to weights.
+ int seedIndex = seedSelector.sample();
+ Centroid nextSeed = new Centroid(datapoints.get(seedIndex));
+ nextSeed.setIndex(clusterIndex++);
+ centroids.add(nextSeed);
+ // Don't select this one again.
+ seedSelector.delete(seedIndex);
+ // Re-weight everything according to the minimum distance to a seed.
+ for (int currSeedIndex : seedSelector) {
+ WeightedVector curr = datapoints.get(currSeedIndex);
+ double newWeight = nextSeed.getWeight() * distanceMeasure.distance(nextSeed, curr);
+ if (newWeight < seedSelector.getWeight(currSeedIndex)) {
+ seedSelector.set(currSeedIndex, newWeight);
+ }
+ }
+ }
+ }
+
+ /**
+ * Examines the datapoints and updates cluster centers to be the centroid of the nearest datapoints points. To
+ * compute a new center for cluster c_i, we average all points that are closer than d_i * trimFraction
+ * where d_i is
+ *
+ * d_i = min_j \sqrt ||c_j - c_i||^2
+ *
+ * By ignoring distant points, the centroids converge more quickly to a good approximation of the
+ * optimal k-means solution (given good starting points).
+ *
+ * @param datapoints the points to cluster.
+ */
+ private void iterativeAssignment(List<? extends WeightedVector> datapoints) {
+ DistanceMeasure distanceMeasure = centroids.getDistanceMeasure();
+ // closestClusterDistances.get(i) is the distance from the i'th cluster to its closest
+ // neighboring cluster.
+ List<Double> closestClusterDistances = Lists.newArrayListWithExpectedSize(numClusters);
+ // clusterAssignments[i] == j means that the i'th point is assigned to the j'th cluster. When
+ // these don't change, we are done.
+ // Each point is assigned to the invalid "-1" cluster initially.
+ List<Integer> clusterAssignments = Lists.newArrayList(Collections.nCopies(datapoints.size(), -1));
+
+ boolean changed = true;
+ for (int i = 0; changed && i < maxNumIterations; i++) {
+ changed = false;
+ // We compute what the distance between each cluster and its closest neighbor is to set a
+ // proportional distance threshold for points that should be involved in calculating the
+ // centroid.
+ closestClusterDistances.clear();
+ for (Vector center : centroids) {
+ // If a centroid has no points assigned to it, the clustering failed.
+ Vector closestOtherCluster = centroids.searchFirst(center, true).getValue();
+ closestClusterDistances.add(distanceMeasure.distance(center, closestOtherCluster));
+ }
+
+ // Copies the current cluster centroids to newClusters and sets their weights to 0. This is
+ // so we calculate the new centroids as we go through the datapoints.
+ List<Centroid> newCentroids = Lists.newArrayList();
+ for (Vector centroid : centroids) {
+ // need a deep copy because we will mutate these values
+ Centroid newCentroid = (Centroid)centroid.clone();
+ newCentroid.setWeight(0);
+ newCentroids.add(newCentroid);
+ }
+
+ // Pass over the datapoints computing new centroids.
+ for (int j = 0; j < datapoints.size(); ++j) {
+ WeightedVector datapoint = datapoints.get(j);
+ // Get the closest cluster this point belongs to.
+ WeightedThing<Vector> closestPair = centroids.searchFirst(datapoint, false);
+ int closestIndex = ((WeightedVector) closestPair.getValue()).getIndex();
+ double closestDistance = closestPair.getWeight();
+ // Update its cluster assignment if necessary.
+ if (closestIndex != clusterAssignments.get(j)) {
+ changed = true;
+ clusterAssignments.set(j, closestIndex);
+ }
+ // Only update if the datapoints point is near enough. What this means is that the weight
+ // of outliers is NOT taken into account and the final weights of the centroids will
+ // reflect this (it will be less or equal to the initial sum of the weights).
+ if (closestDistance < trimFraction * closestClusterDistances.get(closestIndex)) {
+ newCentroids.get(closestIndex).update(datapoint);
+ }
+ }
+ // Add the new centers back into searcher.
+ centroids.clear();
+ centroids.addAll(newCentroids);
+ }
+
+ if (correctWeights) {
+ for (Vector v : centroids) {
+ ((Centroid)v).setWeight(0);
+ }
+ for (WeightedVector datapoint : datapoints) {
+ Centroid closestCentroid = (Centroid) centroids.searchFirst(datapoint, false).getValue();
+ closestCentroid.setWeight(closestCentroid.getWeight() + datapoint.getWeight());
+ }
+ }
+ }
+
+ @Override
+ public Iterator<Centroid> iterator() {
+ return Iterators.transform(centroids.iterator(), new Function<Vector, Centroid>() {
+ @Override
+ public Centroid apply(Vector input) {
+ Preconditions.checkArgument(input instanceof Centroid, "Non-centroid in centroids " +
+ "searcher");
+ //noinspection ConstantConditions
+ return (Centroid)input;
+ }
+ });
+ }
+}
Added: mahout/trunk/core/src/main/java/org/apache/mahout/clustering/streaming/cluster/StreamingKMeans.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/main/java/org/apache/mahout/clustering/streaming/cluster/StreamingKMeans.java?rev=1480954&view=auto
==============================================================================
--- mahout/trunk/core/src/main/java/org/apache/mahout/clustering/streaming/cluster/StreamingKMeans.java (added)
+++ mahout/trunk/core/src/main/java/org/apache/mahout/clustering/streaming/cluster/StreamingKMeans.java Fri May 10 09:20:31 2013
@@ -0,0 +1,355 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.clustering.streaming.cluster;
+
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Random;
+
+import com.google.common.base.Function;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Iterators;
+import com.google.common.collect.Lists;
+import org.apache.mahout.common.RandomUtils;
+import org.apache.mahout.math.Centroid;
+import org.apache.mahout.math.Matrix;
+import org.apache.mahout.math.MatrixSlice;
+import org.apache.mahout.math.Vector;
+import org.apache.mahout.math.jet.math.Constants;
+import org.apache.mahout.math.neighborhood.UpdatableSearcher;
+import org.apache.mahout.math.random.WeightedThing;
+
+/**
+ * Implements a streaming k-means algorithm for weighted vectors.
+ * The goal clustering points one at a time, especially useful for MapReduce mappers that get inputs one at a time.
+ *
+ * A rough description of the algorithm:
+ * Suppose there are l clusters at one point and a new point p is added.
+ * The new point can either be added to one of the existing l clusters or become a new cluster. To decide:
+ * - let c be the closest cluster to point p;
+ * - let d be the distance between c and p;
+ * - if d > distanceCutoff, create a new cluster from p (p is too far away from the clusters to be part of them;
+ * distanceCutoff represents the largest distance from a point its assigned cluster's centroid);
+ * - else (d <= distanceCutoff), create a new cluster with probability d / distanceCutoff (the probability of creating
+ * a new cluster increases as d increases).
+ * There will be either l points or l + 1 points after processing a new point.
+ *
+ * As the number of clusters increases, it will go over the numClusters limit (numClusters represents a recommendation
+ * for the number of clusters that there should be at the end). To decrease the number of clusters the existing clusters
+ * are treated as data points and are re-clustered (collapsed). This tends to make the number of clusters go down.
+ * If the number of clusters is still too high, distanceCutoff is increased.
+ *
+ * For more details, see:
+ * - "Streaming k-means approximation" by N. Ailon, R. Jaiswal, C. Monteleoni
+ * http://books.nips.cc/papers/files/nips22/NIPS2009_1085.pdf
+ * - "Fast and Accurate k-means for Large Datasets" by M. Shindler, A. Wong, A. Meyerson,
+ * http://books.nips.cc/papers/files/nips24/NIPS2011_1271.pdf
+ */
+public class StreamingKMeans implements Iterable<Centroid> {
+ /**
+ * The searcher containing the centroids that resulted from the clustering of points until now. When adding a new
+ * point we either assign it to one of the existing clusters in this searcher or create a new centroid for it.
+ */
+ private final UpdatableSearcher centroids;
+
+ /**
+ * The estimated number of clusters to cluster the data in. If the actual number of clusters increases beyond this
+ * limit, the clusters will be "collapsed" (re-clustered, by treating them as data points). This doesn't happen
+ * recursively and a collapse might not necessarily make the number of actual clusters drop to less than this limit.
+ *
+ * If the goal is clustering a large data set into k clusters, numClusters SHOULD NOT BE SET to k. StreamingKMeans is
+ * useful to reduce the size of the data set by the mappers so that it can fit into memory in one reducer that runs
+ * BallKMeans.
+ *
+ * It is NOT MEANT to cluster the data into k clusters in one pass because it can't guarantee that there will in fact
+ * be k clusters in total. This is because of the dynamic nature of numClusters over the course of the runtime.
+ * To get an exact number of clusters, another clustering algorithm needs to be applied to the results.
+ */
+ private int numClusters;
+
+ /**
+ * The number of data points seen so far. This is important for re-estimating numClusters when deciding to collapse
+ * the existing clusters.
+ */
+ private int numProcessedDatapoints = 0;
+
+ /**
+ * This is the current value of the distance cutoff. Points which are much closer than this to a centroid will stick
+ * to it almost certainly. Points further than this to any centroid will form a new cluster.
+ *
+ * This increases (is multiplied by beta) when a cluster collapse did not make the number of clusters drop to below
+ * numClusters (it effectively increases the tolerance for cluster compactness discouraging the creation of new
+ * clusters). Since a collapse only happens when centroids.size() > clusterOvershoot * numClusters, the cutoff
+ * increases when the collapse didn't at least remove the slack in the number of clusters.
+ */
+ private double distanceCutoff;
+
+ /**
+ * Parameter that controls the growth of the distanceCutoff. After n increases of the
+ * distanceCutoff starting at d_0, the final value is d_0 * beta^n (distance cutoffs increase following a geometric
+ * progression with ratio beta).
+ */
+ private final double beta;
+
+ /**
+ * Multiplying clusterLogFactor with numProcessedDatapoints gets an estimate of the suggested
+ * number of clusters. This mirrors the recommended number of clusters for n points where there should be k actual
+ * clusters, k * log n. In the case of our estimate we use clusterLogFactor * log(numProcessedDataPoints).
+ *
+ * It is important to note that numClusters is NOT k. It is an estimate of k * log n.
+ */
+ private final double clusterLogFactor;
+
+ /**
+ * Centroids are collapsed when the number of clusters becomes greater than clusterOvershoot * numClusters. This
+ * effectively means having a slack in numClusters so that the actual number of centroids, centroids.size() tracks
+ * numClusters approximately. The idea is that the actual number of clusters should be at least numClusters but not
+ * much more (so that we don't end up having 1 cluster / point).
+ */
+ private final double clusterOvershoot;
+
+ /**
+ * Random object to sample values from.
+ */
+ private Random random = RandomUtils.getRandom();
+
+ /**
+ * Calls StreamingKMeans(searcher, numClusters, 1.3, 10, 2).
+ * @see StreamingKMeans#StreamingKMeans(org.apache.mahout.math.neighborhood.UpdatableSearcher, int,
+ * double, double, double, double)
+ */
+ public StreamingKMeans(UpdatableSearcher searcher, int numClusters) {
+ this(searcher, numClusters, 1.0 / numClusters, 1.3, 20, 2);
+ }
+
+ /**
+ * Calls StreamingKMeans(searcher, numClusters, distanceCutoff, 1.3, 10, 2).
+ * @see StreamingKMeans#StreamingKMeans(org.apache.mahout.math.neighborhood.UpdatableSearcher, int,
+ * double, double, double, double)
+ */
+ public StreamingKMeans(UpdatableSearcher searcher, int numClusters, double distanceCutoff) {
+ this(searcher, numClusters, distanceCutoff, 1.3, 20, 2);
+ }
+
+ /**
+ * Creates a new StreamingKMeans class given a searcher and the number of clusters to generate.
+ *
+ * @param searcher A Searcher that is used for performing nearest neighbor search. It MUST BE
+ * EMPTY initially because it will be used to keep track of the cluster
+ * centroids.
+ * @param numClusters An estimated number of clusters to generate for the data points.
+ * This can adjusted, but the actual number will depend on the data. The
+ * @param distanceCutoff The initial distance cutoff representing the value of the
+ * distance between a point and its closest centroid after which
+ * the new point will definitely be assigned to a new cluster.
+ * @param beta Ratio of geometric progression to use when increasing distanceCutoff. After n increases, distanceCutoff
+ * becomes distanceCutoff * beta^n. A smaller value increases the distanceCutoff less aggressively.
+ * @param clusterLogFactor Value multiplied with the number of points counted so far estimating the number of clusters
+ * to aim for. If the final number of clusters is known and this clustering is only for a
+ * sketch of the data, this can be the final number of clusters, k.
+ * @param clusterOvershoot Multiplicative slack factor for slowing down the collapse of the clusters.
+ */
+ public StreamingKMeans(UpdatableSearcher searcher, int numClusters,
+ double distanceCutoff, double beta, double clusterLogFactor, double clusterOvershoot) {
+ this.centroids = searcher;
+ this.numClusters = numClusters;
+ this.distanceCutoff = distanceCutoff;
+ this.beta = beta;
+ this.clusterLogFactor = clusterLogFactor;
+ this.clusterOvershoot = clusterOvershoot;
+ }
+
+ /**
+ * @return an Iterator to the Centroids contained in this clusterer.
+ */
+ @Override
+ public Iterator<Centroid> iterator() {
+ return Iterators.transform(centroids.iterator(), new Function<Vector, Centroid>() {
+ @Override
+ public Centroid apply(Vector input) {
+ return (Centroid)input;
+ }
+ });
+ }
+
+ /**
+ * Cluster the rows of a matrix, treating them as Centroids with weight 1.
+ * @param data matrix whose rows are to be clustered.
+ * @return the UpdatableSearcher containing the resulting centroids.
+ */
+ public UpdatableSearcher cluster(Matrix data) {
+ return cluster(Iterables.transform(data, new Function<MatrixSlice, Centroid>() {
+ @Override
+ public Centroid apply(MatrixSlice input) {
+ // The key in a Centroid is actually the MatrixSlice's index.
+ return Centroid.create(input.index(), input.vector());
+ }
+ }));
+ }
+
+ /**
+ * Cluster the data points in an Iterable<Centroid>.
+ * @param datapoints Iterable whose elements are to be clustered.
+ * @return the UpdatableSearcher containing the resulting centroids.
+ */
+ public UpdatableSearcher cluster(Iterable<Centroid> datapoints) {
+ return clusterInternal(datapoints, false);
+ }
+
+ /**
+ * Cluster one data point.
+ * @param datapoint to be clustered.
+ * @return the UpdatableSearcher containing the resulting centroids.
+ */
+ public UpdatableSearcher cluster(final Centroid datapoint) {
+ return cluster(new Iterable<Centroid>() {
+ @Override
+ public Iterator<Centroid> iterator() {
+ return new Iterator<Centroid>() {
+ private boolean accessed = false;
+
+ @Override
+ public boolean hasNext() {
+ return !accessed;
+ }
+
+ @Override
+ public Centroid next() {
+ accessed = true;
+ return datapoint;
+ }
+
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ };
+ }
+ });
+ }
+
+ /**
+ * @return the number of clusters computed from the points until now.
+ */
+ public int getNumClusters() {
+ return centroids.size();
+ }
+
+ /**
+ * Internal clustering method that gets called from the other wrappers.
+ * @param datapoints Iterable of data points to be clustered.
+ * @param collapseClusters whether this is an "inner" clustering and the datapoints are the previously computed
+ * centroids. Some logic is different to ensure counters are consistent but it behaves
+ * nearly the same.
+ * @return the UpdatableSearcher containing the resulting centroids.
+ */
+ private UpdatableSearcher clusterInternal(Iterable<Centroid> datapoints, boolean collapseClusters) {
+ int oldNumProcessedDataPoints = numProcessedDatapoints;
+ // We clear the centroids we have in case of cluster collapse, the old clusters are the
+ // datapoints but we need to re-cluster them.
+ if (collapseClusters) {
+ centroids.clear();
+ numProcessedDatapoints = 0;
+ }
+
+ int numCentroidsToSkip = 0;
+ if (centroids.size() == 0) {
+ // Assign the first datapoint to the first cluster.
+ // Adding a vector to a searcher would normally just reference the copy,
+ // but we could potentially mutate it and so we need to make a clone.
+ centroids.add(Iterables.get(datapoints, 0).clone());
+ numCentroidsToSkip = 1;
+ ++numProcessedDatapoints;
+ }
+
+ // To cluster, we scan the data and either add each point to the nearest group or create a new group.
+ // when we get too many groups, we need to increase the threshold and rescan our current groups
+ for (Centroid row : Iterables.skip(datapoints, numCentroidsToSkip)) {
+ // Get the closest vector and its weight as a WeightedThing<Vector>.
+ // The weight of the WeightedThing is the distance to the query and the value is a
+ // reference to one of the vectors we added to the searcher previously.
+ WeightedThing<Vector> closestPair = centroids.searchFirst(row, false);
+
+ // We get a uniformly distributed random number between 0 and 1 and compare it with the
+ // distance to the closest cluster divided by the distanceCutoff.
+ // This is so that if the closest cluster is further than distanceCutoff,
+ // closestPair.getWeight() / distanceCutoff > 1 which will trigger the creation of a new
+ // cluster anyway.
+ // However, if the ratio is less than 1, we want to create a new cluster with probability
+ // proportional to the distance to the closest cluster.
+ double sample = random.nextDouble();
+ if (sample < row.getWeight() * closestPair.getWeight() / distanceCutoff) {
+ // Add new centroid, note that the vector is copied because we may mutate it later.
+ centroids.add(row.clone());
+ } else {
+ // Merge the new point with the existing centroid. This will update the centroid's actual
+ // position.
+ // We know that all the points we inserted in the centroids searcher are (or extend)
+ // WeightedVector, so the cast will always succeed.
+ Centroid centroid = (Centroid) closestPair.getValue();
+
+ // We will update the centroid by removing it from the searcher and reinserting it to
+ // ensure consistency.
+ if (!centroids.remove(centroid, Constants.EPSILON)) {
+ throw new RuntimeException("Unable to remove centroid");
+ }
+ centroid.update(row);
+ centroids.add(centroid);
+
+ }
+ ++numProcessedDatapoints;
+
+ if (!collapseClusters && centroids.size() > clusterOvershoot * numClusters) {
+ numClusters = (int) Math.max(numClusters, clusterLogFactor * Math.log(numProcessedDatapoints));
+
+ List<Centroid> shuffled = Lists.newArrayList();
+ for (Vector vector : centroids) {
+ shuffled.add((Centroid) vector);
+ }
+ Collections.shuffle(shuffled);
+ // Re-cluster using the shuffled centroids as data points. The centroids member variable
+ // is modified directly.
+ clusterInternal(shuffled, true);
+
+ if (centroids.size() > numClusters) {
+ distanceCutoff *= beta;
+ }
+ }
+ }
+
+ if (collapseClusters) {
+ numProcessedDatapoints = oldNumProcessedDataPoints;
+ }
+ return centroids;
+ }
+
+ public void reindexCentroids() {
+ int numCentroids = 0;
+ for (Centroid centroid : this) {
+ centroid.setIndex(numCentroids++);
+ }
+ }
+
+ /**
+ * @return the distanceCutoff (an upper bound for the maximum distance within a cluster).
+ */
+ public double getDistanceCutoff() {
+ return distanceCutoff;
+ }
+}
Added: mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/BallKMeansTest.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/BallKMeansTest.java?rev=1480954&view=auto
==============================================================================
--- mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/BallKMeansTest.java (added)
+++ mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/BallKMeansTest.java Fri May 10 09:20:31 2013
@@ -0,0 +1,177 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.clustering.streaming.cluster;
+
+import java.util.List;
+
+import com.google.common.collect.Lists;
+import org.apache.mahout.clustering.ClusteringUtils;
+import org.apache.mahout.common.Pair;
+import org.apache.mahout.common.distance.EuclideanDistanceMeasure;
+import org.apache.mahout.common.distance.SquaredEuclideanDistanceMeasure;
+import org.apache.mahout.math.Centroid;
+import org.apache.mahout.math.ConstantVector;
+import org.apache.mahout.math.DenseMatrix;
+import org.apache.mahout.math.DenseVector;
+import org.apache.mahout.math.Matrix;
+import org.apache.mahout.math.SingularValueDecomposition;
+import org.apache.mahout.math.Vector;
+import org.apache.mahout.math.WeightedVector;
+import org.apache.mahout.math.function.Functions;
+import org.apache.mahout.math.function.VectorFunction;
+import org.apache.mahout.math.neighborhood.BruteSearch;
+import org.apache.mahout.math.neighborhood.Searcher;
+import org.apache.mahout.math.neighborhood.UpdatableSearcher;
+import org.apache.mahout.math.random.MultiNormal;
+import org.apache.mahout.math.random.WeightedThing;
+import org.apache.mahout.math.stats.OnlineSummarizer;
+import org.junit.Test;
+
+import static org.apache.mahout.clustering.ClusteringUtils.totalWeight;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+public class BallKMeansTest {
+ private static final int NUM_DATA_POINTS = 10000;
+ private static final int NUM_DIMENSIONS = 4;
+ private static final int NUM_ITERATIONS = 20;
+ private static final double DISTRIBUTION_RADIUS = 0.01;
+
+ private static Pair<List<Centroid>, List<Centroid>> syntheticData =
+ DataUtils.sampleMultiNormalHypercube(NUM_DIMENSIONS, NUM_DATA_POINTS, DISTRIBUTION_RADIUS);
+ private static final int K1 = 100;
+
+ @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();
+ clusterer.cluster(syntheticData.getFirst());
+ long endTime = System.currentTimeMillis();
+
+ assertEquals("Total weight not preserved", totalWeight(syntheticData.getFirst()), totalWeight(clusterer), 1e-9);
+
+ // Verify that each corner of the cube has a centroid very nearby.
+ // This is probably FALSE for large-dimensional spaces!
+ 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() * 1e6);
+
+ // Verify that the total weight of the centroids near each corner is correct.
+ 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() {
+ // Start with super clusterable data.
+ List<? extends WeightedVector> data = cubishTestData(0.01);
+
+ // Just do initialization of ball k-means. This should drop a point into each of the clusters.
+ BallKMeans r = new BallKMeans(new BruteSearch(new SquaredEuclideanDistanceMeasure()), 6, 20);
+ r.cluster(data);
+
+ // Put the centroids into a matrix.
+ Matrix x = new DenseMatrix(6, 5);
+ int row = 0;
+ for (Centroid c : r) {
+ x.viewRow(row).assign(c.viewPart(0, 5));
+ row++;
+ }
+
+ // Verify that each column looks right. Should contain zeros except for a single 6.
+ final Vector columnNorms = x.aggregateColumns(new VectorFunction() {
+ @Override
+ public double apply(Vector f) {
+ // Return the sum of three discrepancy measures.
+ return Math.abs(f.minValue()) + Math.abs(f.maxValue() - 6) + Math.abs(f.norm(1) - 6);
+ }
+ });
+ // Verify all errors are nearly zero.
+ assertEquals(0, columnNorms.norm(1) / columnNorms.size(), 0.1);
+
+ // Verify that the centroids are a permutation of the original ones.
+ 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);
+ }
+
+ private List<? extends WeightedVector> cubishTestData(double radius) {
+ List<WeightedVector> data = Lists.newArrayListWithCapacity(K1 + 5000);
+ int row = 0;
+
+ MultiNormal g = new MultiNormal(radius, new ConstantVector(0, 10));
+ for (int i = 0; i < K1; i++) {
+ data.add(new WeightedVector(g.sample(), 1, row++));
+ }
+
+ for (int i = 0; i < 5; i++) {
+ Vector m = new DenseVector(10);
+ m.set(i, i == 0 ? 6 : 6);
+ MultiNormal gx = new MultiNormal(radius, m);
+ for (int j = 0; j < 1000; j++) {
+ data.add(new WeightedVector(gx.sample(), 1, row++));
+ }
+ }
+ return data;
+ }
+}
Added: mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/DataUtils.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/DataUtils.java?rev=1480954&view=auto
==============================================================================
--- mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/DataUtils.java (added)
+++ mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/DataUtils.java Fri May 10 09:20:31 2013
@@ -0,0 +1,84 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.clustering.streaming.cluster;
+
+import java.util.List;
+
+import com.google.common.collect.Lists;
+import org.apache.mahout.common.Pair;
+import org.apache.mahout.math.Centroid;
+import org.apache.mahout.math.DenseVector;
+import org.apache.mahout.math.Vector;
+import org.apache.mahout.math.random.MultiNormal;
+
+/**
+ * A collection of miscellaneous utility functions for working with data to be clustered.
+ * Includes methods for generating synthetic data and estimating distance cutoff.
+ */
+public class DataUtils {
+ /**
+ * Samples numDatapoints vectors of numDimensions cardinality centered around the vertices of a
+ * numDimensions order hypercube. The distribution of points around these vertices is
+ * multinormal with a radius of distributionRadius.
+ * A hypercube of numDimensions has 2^numDimensions vertices. Keep this in mind when clustering
+ * the data.
+ *
+ *
+ * @param numDimensions number of dimensions of the vectors to be generated.
+ * @param numDatapoints number of data points to be generated.
+ * @param distributionRadius radius of the distribution around the hypercube vertices.
+ * @return a pair of lists, whose first element is the sampled points and whose second element
+ * is the list of hypercube vertices that are the means of each distribution.
+ */
+ public static Pair<List<Centroid>, List<Centroid>> sampleMultiNormalHypercube(
+ int numDimensions, int numDatapoints, double distributionRadius) {
+ int pow2N = 1 << numDimensions;
+ // Construct data samplers centered on the corners of a unit hypercube.
+ // Additionally, keep the means of the distributions that will be generated so we can compare
+ // these to the ideal cluster centers.
+ List<Centroid> mean = Lists.newArrayListWithCapacity(pow2N);
+ List<MultiNormal> rowSamplers = Lists.newArrayList();
+ for (int i = 0; i < pow2N; i++) {
+ Vector v = new DenseVector(numDimensions);
+ // Select each of the num
+ int pow2J = 1 << (numDimensions - 1);
+ for (int j = 0; j < numDimensions; ++j) {
+ v.set(j, 1.0 / pow2J * (i & pow2J));
+ pow2J >>= 1;
+ }
+ mean.add(new Centroid(i, v, 1));
+ rowSamplers.add(new MultiNormal(distributionRadius, v));
+ }
+
+ // Sample the requested number of data points.
+ List<Centroid> data = Lists.newArrayListWithCapacity(numDatapoints);
+ for (int i = 0; i < numDatapoints; ++i) {
+ data.add(new Centroid(i, rowSamplers.get(i % pow2N).sample(), 1));
+ }
+ return new Pair<List<Centroid>, List<Centroid>>(data, mean);
+ }
+
+ /**
+ * Calls sampleMultinormalHypercube(numDimension, numDataPoints, 0.01).
+ * @see DataUtils#sampleMultiNormalHypercube(int, int, double)
+ */
+ public static Pair<List<Centroid>, List<Centroid>> sampleMultiNormalHypercube(int numDimensions,
+ int numDatapoints) {
+ return sampleMultiNormalHypercube(numDimensions, numDatapoints, 0.01);
+ }
+}
Added: mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/StreamingKMeansTest.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/StreamingKMeansTest.java?rev=1480954&view=auto
==============================================================================
--- mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/StreamingKMeansTest.java (added)
+++ mahout/trunk/core/src/test/java/org/apache/mahout/clustering/streaming/cluster/StreamingKMeansTest.java Fri May 10 09:20:31 2013
@@ -0,0 +1,161 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.clustering.streaming.cluster;
+
+
+import java.util.Arrays;
+import java.util.List;
+
+import org.apache.mahout.clustering.ClusteringUtils;
+import org.apache.mahout.common.Pair;
+import org.apache.mahout.common.distance.EuclideanDistanceMeasure;
+import org.apache.mahout.common.distance.SquaredEuclideanDistanceMeasure;
+import org.apache.mahout.math.Centroid;
+import org.apache.mahout.math.Vector;
+import org.apache.mahout.math.neighborhood.BruteSearch;
+import org.apache.mahout.math.neighborhood.FastProjectionSearch;
+import org.apache.mahout.math.neighborhood.ProjectionSearch;
+import org.apache.mahout.math.neighborhood.Searcher;
+import org.apache.mahout.math.neighborhood.UpdatableSearcher;
+import org.apache.mahout.math.random.WeightedThing;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.runners.Parameterized.Parameters;
+
+
+@RunWith(value = Parameterized.class)
+public class StreamingKMeansTest {
+ private static final int NUM_DATA_POINTS = 1 << 16;
+ private static final int NUM_DIMENSIONS = 6;
+ private static final int NUM_PROJECTIONS = 2;
+ private static final int SEARCH_SIZE = 10;
+
+ private static final Pair<List<Centroid>, List<Centroid>> syntheticData =
+ DataUtils.sampleMultiNormalHypercube(NUM_DIMENSIONS, NUM_DATA_POINTS);
+
+ private UpdatableSearcher searcher;
+ private boolean allAtOnce;
+
+ public StreamingKMeansTest(UpdatableSearcher searcher, boolean allAtOnce) {
+ this.searcher = searcher;
+ this.allAtOnce = allAtOnce;
+ }
+
+ @Parameters
+ public static List<Object[]> generateData() {
+ return Arrays.asList(new Object[][] {
+ {new ProjectionSearch(new SquaredEuclideanDistanceMeasure(), NUM_PROJECTIONS, SEARCH_SIZE), true},
+ {new FastProjectionSearch(new SquaredEuclideanDistanceMeasure(), NUM_PROJECTIONS, SEARCH_SIZE),
+ true},
+ {new ProjectionSearch(new SquaredEuclideanDistanceMeasure(), NUM_PROJECTIONS, SEARCH_SIZE), false},
+ {new FastProjectionSearch(new SquaredEuclideanDistanceMeasure(), NUM_PROJECTIONS, SEARCH_SIZE),
+ false},
+ });
+ }
+
+ @Test
+ public void testAverageDistanceCutoff() {
+ double avgDistanceCutoff = 0;
+ double avgNumClusters = 0;
+ int numTests = 1;
+ System.out.printf("Distance cutoff for %s\n", searcher.getClass().getName());
+ for (int i = 0; i < numTests; ++i) {
+ searcher.clear();
+ int numStreamingClusters = (int)Math.log(syntheticData.getFirst().size()) * (1 <<
+ NUM_DIMENSIONS);
+ double distanceCutoff = 1e-6;
+ double estimatedCutoff = ClusteringUtils.estimateDistanceCutoff(syntheticData.getFirst(),
+ searcher.getDistanceMeasure(), 100);
+ System.out.printf("[%d] Generated synthetic data [magic] %f [estimate] %f\n", i, distanceCutoff, estimatedCutoff);
+ StreamingKMeans clusterer =
+ new StreamingKMeans(searcher, numStreamingClusters, estimatedCutoff);
+ clusterer.cluster(syntheticData.getFirst());
+ avgDistanceCutoff += clusterer.getDistanceCutoff();
+ avgNumClusters += clusterer.getNumClusters();
+ System.out.printf("[%d] %f\n", i, clusterer.getDistanceCutoff());
+ }
+ avgDistanceCutoff /= numTests;
+ avgNumClusters /= numTests;
+ System.out.printf("Final: distanceCutoff: %f estNumClusters: %f\n", avgDistanceCutoff, avgNumClusters);
+ }
+
+ @Test
+ public void testClustering() {
+ searcher.clear();
+ int numStreamingClusters = (int)Math.log(syntheticData.getFirst().size()) * (1 << NUM_DIMENSIONS);
+ System.out.printf("k log n = %d\n", numStreamingClusters);
+ double estimatedCutoff = ClusteringUtils.estimateDistanceCutoff(syntheticData.getFirst(),
+ searcher.getDistanceMeasure(), 100);
+ StreamingKMeans clusterer =
+ new StreamingKMeans(searcher, numStreamingClusters, estimatedCutoff);
+
+ long startTime = System.currentTimeMillis();
+ if (allAtOnce) {
+ clusterer.cluster(syntheticData.getFirst());
+ } else {
+ for (Centroid datapoint : syntheticData.getFirst()) {
+ clusterer.cluster(datapoint);
+ }
+ }
+ long endTime = System.currentTimeMillis();
+
+ System.out.printf("%s %s\n", searcher.getClass().getName(), searcher.getDistanceMeasure()
+ .getClass().getName());
+ System.out.printf("Total number of clusters %d\n", clusterer.getNumClusters());
+
+ System.out.printf("Weights: %f %f\n", ClusteringUtils.totalWeight(syntheticData.getFirst()),
+ ClusteringUtils.totalWeight(clusterer));
+ assertEquals("Total weight not preserved", ClusteringUtils.totalWeight(syntheticData.getFirst()),
+ ClusteringUtils.totalWeight(clusterer), 1e-9);
+
+ // and verify that each corner of the cube has a centroid very nearby
+ double maxWeight = 0;
+ for (Vector mean : syntheticData.getSecond()) {
+ WeightedThing<Vector> v = searcher.search(mean, 1).get(0);
+ maxWeight = Math.max(v.getWeight(), maxWeight);
+ }
+ assertTrue("Maximum weight too large " + maxWeight, maxWeight < 0.05);
+ 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() * 1e6);
+
+ // verify that the total weight of the centroids near each corner is correct
+ 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);
+ }
+ }
+}