You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by lu...@apache.org on 2010/10/23 21:31:19 UTC
svn commit: r1026667 - in /commons/proper/math/trunk/src:
main/java/org/apache/commons/math/exception/
main/java/org/apache/commons/math/exception/util/
main/java/org/apache/commons/math/stat/clustering/
main/resources/META-INF/localization/ site/xdoc/...
Author: luc
Date: Sat Oct 23 19:31:19 2010
New Revision: 1026667
URL: http://svn.apache.org/viewvc?rev=1026667&view=rev
Log:
Fixed k-means++ to add several strategies to deal with empty clusters that may appear during iterations
JIRA: MATH-429
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/ConvergenceException.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/MathIllegalStateException.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/util/LocalizedFormats.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/stat/clustering/KMeansPlusPlusClusterer.java
commons/proper/math/trunk/src/main/resources/META-INF/localization/LocalizedFormats_fr.properties
commons/proper/math/trunk/src/site/xdoc/changes.xml
commons/proper/math/trunk/src/test/java/org/apache/commons/math/stat/clustering/KMeansPlusPlusClustererTest.java
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/ConvergenceException.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/ConvergenceException.java?rev=1026667&r1=1026666&r2=1026667&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/ConvergenceException.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/ConvergenceException.java Sat Oct 23 19:31:19 2010
@@ -23,7 +23,7 @@ import org.apache.commons.math.exception
* Error thrown when a numerical computation can not be performed because the
* numerical result failed to converge to a finite value.
*
- * @since 3.0
+ * @since 2.2
* @version $Revision$ $Date$
*/
public class ConvergenceException extends MathIllegalStateException {
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/MathIllegalStateException.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/MathIllegalStateException.java?rev=1026667&r1=1026666&r2=1026667&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/MathIllegalStateException.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/MathIllegalStateException.java Sat Oct 23 19:31:19 2010
@@ -26,7 +26,7 @@ import org.apache.commons.math.exception
* Base class for all exceptions that signal a mismatch between the
* current state and the user's expectations.
*
- * @since 3.0
+ * @since 2.2
* @version $Revision$ $Date$
*/
public class MathIllegalStateException extends IllegalStateException {
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/util/LocalizedFormats.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/util/LocalizedFormats.java?rev=1026667&r1=1026666&r2=1026667&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/util/LocalizedFormats.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/exception/util/LocalizedFormats.java Sat Oct 23 19:31:19 2010
@@ -86,6 +86,7 @@ public enum LocalizedFormats implements
DISCRETE_CUMULATIVE_PROBABILITY_RETURNED_NAN("Discrete cumulative probability function returned NaN for argument {0}"),
DISTRIBUTION_NOT_LOADED("distribution not loaded"),
DUPLICATED_ABSCISSA("Abscissa {0} is duplicated at both indices {1} and {2}"),
+ EMPTY_CLUSTER_IN_K_MEANS("empty cluster in k-means"),
EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY("empty polynomials coefficients array"), /* keep */
EMPTY_SELECTED_COLUMN_INDEX_ARRAY("empty selected column index array"),
EMPTY_SELECTED_ROW_INDEX_ARRAY("empty selected row index array"),
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/stat/clustering/KMeansPlusPlusClusterer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/stat/clustering/KMeansPlusPlusClusterer.java?rev=1026667&r1=1026666&r2=1026667&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/stat/clustering/KMeansPlusPlusClusterer.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/stat/clustering/KMeansPlusPlusClusterer.java Sat Oct 23 19:31:19 2010
@@ -22,6 +22,10 @@ import java.util.Collection;
import java.util.List;
import java.util.Random;
+import org.apache.commons.math.exception.ConvergenceException;
+import org.apache.commons.math.exception.util.LocalizedFormats;
+import org.apache.commons.math.stat.descriptive.moment.Variance;
+
/**
* Clustering algorithm based on David Arthur and Sergei Vassilvitski k-means++ algorithm.
* @param <T> type of the points to cluster
@@ -31,14 +35,49 @@ import java.util.Random;
*/
public class KMeansPlusPlusClusterer<T extends Clusterable<T>> {
+ /** Strategies to use for replacing an empty cluster. */
+ public static enum EmptyClusterStrategy {
+
+ /** Split the cluster with largest distance variance. */
+ LARGEST_VARIANCE,
+
+ /** Split the cluster with largest number of points. */
+ LARGEST_POINTS_NUMBER,
+
+ /** Create a cluster around the point farthest from its centroid. */
+ FARTHEST_POINT,
+
+ /** Generate an error. */
+ ERROR
+
+ }
+
/** Random generator for choosing initial centers. */
private final Random random;
+ /** Selected strategy for empty clusters. */
+ private final EmptyClusterStrategy emptyStrategy;
+
/** Build a clusterer.
+ * <p>
+ * The default strategy for handling empty clusters that may appear during
+ * algorithm iterations is to split the cluster with largest distance variance.
+ * </p>
* @param random random generator to use for choosing initial centers
*/
public KMeansPlusPlusClusterer(final Random random) {
- this.random = random;
+ this(random, EmptyClusterStrategy.LARGEST_VARIANCE);
+ }
+
+ /** Build a clusterer.
+ * @param random random generator to use for choosing initial centers
+ * @param emptyStrategy strategy to use for handling empty clusters that
+ * may appear during algorithm iterations
+ * @since 2.2
+ */
+ public KMeansPlusPlusClusterer(final Random random, final EmptyClusterStrategy emptyStrategy) {
+ this.random = random;
+ this.emptyStrategy = emptyStrategy;
}
/**
@@ -62,9 +101,27 @@ public class KMeansPlusPlusClusterer<T e
boolean clusteringChanged = false;
List<Cluster<T>> newClusters = new ArrayList<Cluster<T>>();
for (final Cluster<T> cluster : clusters) {
- final T newCenter = cluster.getCenter().centroidOf(cluster.getPoints());
- if (!newCenter.equals(cluster.getCenter())) {
+ final T 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);
+ }
clusteringChanged = true;
+ } else {
+ newCenter = cluster.getCenter().centroidOf(cluster.getPoints());
+ if (!newCenter.equals(cluster.getCenter())) {
+ clusteringChanged = true;
+ }
}
newClusters.add(new Cluster<T>(newCenter));
}
@@ -141,6 +198,120 @@ public class KMeansPlusPlusClusterer<T e
}
/**
+ * Get a random point from the {@link Cluster} with the largest distance variance.
+ *
+ * @param <T> type of the points to cluster
+ * @param clusters the {@link Cluster}s to search
+ * @return a random point from the selected cluster
+ */
+ private T getPointFromLargestVarianceCluster(final Collection<Cluster<T>> clusters) {
+
+ double maxVariance = Double.NEGATIVE_INFINITY;
+ Cluster<T> selected = null;
+ for (final Cluster<T> cluster : clusters) {
+ if (!cluster.getPoints().isEmpty()) {
+
+ // compute the distance variance of the current cluster
+ final T center = cluster.getCenter();
+ final Variance stat = new Variance();
+ for (final T point : cluster.getPoints()) {
+ stat.increment(point.distanceFrom(center));
+ }
+ final double variance = stat.getResult();
+
+ // select the cluster with the largest variance
+ if (variance > maxVariance) {
+ maxVariance = variance;
+ selected = cluster;
+ }
+
+ }
+ }
+
+ // did we find at least one non-empty cluster ?
+ if (selected == null) {
+ throw new ConvergenceException(LocalizedFormats.EMPTY_CLUSTER_IN_K_MEANS);
+ }
+
+ // extract a random point from the cluster
+ final List<T> selectedPoints = selected.getPoints();
+ return selectedPoints.remove(random.nextInt(selectedPoints.size()));
+
+ }
+
+ /**
+ * Get a random point from the {@link Cluster} with the largest number of points
+ *
+ * @param <T> type of the points to cluster
+ * @param clusters the {@link Cluster}s to search
+ * @return a random point from the selected cluster
+ */
+ private T getPointFromLargestNumberCluster(final Collection<Cluster<T>> clusters) {
+
+ int maxNumber = 0;
+ Cluster<T> selected = null;
+ for (final Cluster<T> cluster : clusters) {
+
+ // get the number of points of the current cluster
+ final int number = cluster.getPoints().size();
+
+ // select the cluster with the largest number of points
+ if (number > maxNumber) {
+ maxNumber = number;
+ selected = cluster;
+ }
+
+ }
+
+ // did we find at least one non-empty cluster ?
+ if (selected == null) {
+ throw new ConvergenceException(LocalizedFormats.EMPTY_CLUSTER_IN_K_MEANS);
+ }
+
+ // extract a random point from the cluster
+ final List<T> selectedPoints = selected.getPoints();
+ return selectedPoints.remove(random.nextInt(selectedPoints.size()));
+
+ }
+
+ /**
+ * Get the point farthest to its cluster center
+ *
+ * @param <T> type of the points to cluster
+ * @param clusters the {@link Cluster}s to search
+ * @return point farthest to its cluster center
+ */
+ private T getFarthestPoint(final Collection<Cluster<T>> clusters) {
+
+ double maxDistance = Double.NEGATIVE_INFINITY;
+ Cluster<T> selectedCluster = null;
+ int selectedPoint = -1;
+ for (final Cluster<T> cluster : clusters) {
+
+ // get the farthest point
+ final T center = cluster.getCenter();
+ final List<T> points = cluster.getPoints();
+ for (int i = 0; i < points.size(); ++i) {
+ final double distance = points.get(i).distanceFrom(center);
+ if (distance > maxDistance) {
+ maxDistance = distance;
+ selectedCluster = cluster;
+ selectedPoint = i;
+ }
+ }
+
+ }
+
+ // did we find at least one non-empty cluster ?
+ if (selectedCluster == null) {
+ throw new ConvergenceException(LocalizedFormats.EMPTY_CLUSTER_IN_K_MEANS);
+ }
+
+ return selectedCluster.getPoints().remove(selectedPoint);
+
+ }
+
+ /**
* Returns the nearest {@link Cluster} to the given point
*
* @param <T> type of the points to cluster
Modified: commons/proper/math/trunk/src/main/resources/META-INF/localization/LocalizedFormats_fr.properties
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/resources/META-INF/localization/LocalizedFormats_fr.properties?rev=1026667&r1=1026666&r2=1026667&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/resources/META-INF/localization/LocalizedFormats_fr.properties (original)
+++ commons/proper/math/trunk/src/main/resources/META-INF/localization/LocalizedFormats_fr.properties Sat Oct 23 19:31:19 2010
@@ -58,6 +58,7 @@ DIMENSIONS_MISMATCH = dimensions incoh\u
DISCRETE_CUMULATIVE_PROBABILITY_RETURNED_NAN = Discr\u00e8tes fonction de probabilit\u00e9 cumulative retourn\u00e9 NaN \u00e0 l''argument de {0}
DISTRIBUTION_NOT_LOADED = aucune distribution n''a \u00e9t\u00e9 charg\u00e9e
DUPLICATED_ABSCISSA = Abscisse {0} dupliqu\u00e9e aux indices {1} et {2}
+EMPTY_CLUSTER_IN_K_MEANS = groupe vide dans l''algorithme des k-moyennes
EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY = tableau de coefficients polyn\u00f4miaux vide
EMPTY_SELECTED_COLUMN_INDEX_ARRAY = tableau des indices de colonnes s\u00e9lectionn\u00e9es vide
EMPTY_SELECTED_ROW_INDEX_ARRAY = tableau des indices de lignes s\u00e9lectionn\u00e9es vide
Modified: commons/proper/math/trunk/src/site/xdoc/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/site/xdoc/changes.xml?rev=1026667&r1=1026666&r2=1026667&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Sat Oct 23 19:31:19 2010
@@ -85,6 +85,10 @@ The <action> type attribute can be add,u
</action>
</release>
<release version="2.2" date="TBD" description="TBD">
+ <action dev="luc" type="fix" issue="MATH-429">
+ Fixed k-means++ to add several strategies to deal with empty clusters that may appear
+ during iterations
+ </action>
<action dev="luc" type="update" issue="MATH-417">
Improved Percentile performance by using a selection algorithm instead of a
complete sort, and by allowing caching data array and pivots when several
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math/stat/clustering/KMeansPlusPlusClustererTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/stat/clustering/KMeansPlusPlusClustererTest.java?rev=1026667&r1=1026666&r2=1026667&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/stat/clustering/KMeansPlusPlusClustererTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/stat/clustering/KMeansPlusPlusClustererTest.java Sat Oct 23 19:31:19 2010
@@ -24,6 +24,7 @@ import java.util.Arrays;
import java.util.List;
import java.util.Random;
+import org.junit.Assert;
import org.junit.Test;
public class KMeansPlusPlusClustererTest {
@@ -116,4 +117,53 @@ public class KMeansPlusPlusClustererTest
}
+ @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) {
+ KMeansPlusPlusClusterer<EuclideanIntegerPoint> transformer =
+ new KMeansPlusPlusClusterer<EuclideanIntegerPoint>(new Random(1746432956321l), strategy);
+ int numberOfVariables = 27;
+ // initialise testvalues
+ int position1 = 1;
+ int position2 = position1 + numberOfVariables;
+ int position3 = position2 + numberOfVariables;
+ int position4 = position3 + numberOfVariables;
+ // testvalues will be multiplied
+ int multiplier = 1000000;
+
+ EuclideanIntegerPoint[] breakingPoints = new EuclideanIntegerPoint[numberOfVariables];
+ // define the space which will break the cluster algorithm
+ for (int i = 0; i < numberOfVariables; i++) {
+ int points[] = { position1, position2, position3, position4 };
+ // multiply the values
+ for (int j = 0; j < points.length; j++) {
+ points[j] = points[j] * multiplier;
+ }
+ EuclideanIntegerPoint euclideanIntegerPoint = new EuclideanIntegerPoint(points);
+ breakingPoints[i] = euclideanIntegerPoint;
+ position1 = position1 + numberOfVariables;
+ position2 = position2 + numberOfVariables;
+ position3 = position3 + numberOfVariables;
+ position4 = position4 + numberOfVariables;
+ }
+
+ for (int n = 2; n < 27; ++n) {
+ List<Cluster<EuclideanIntegerPoint>> clusters =
+ transformer.cluster(Arrays.asList(breakingPoints), n, 100);
+ Assert.assertEquals(n, clusters.size());
+ int sum = 0;
+ for (Cluster<EuclideanIntegerPoint> cluster : clusters) {
+ sum += cluster.getPoints().size();
+ }
+ Assert.assertEquals(numberOfVariables, sum);
+ }
+ }
+
+ }
+
}