You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by er...@apache.org on 2020/03/22 15:11:04 UTC

[commons-math] 01/12: MATH-1509: Implement the MiniBatchKMeansClusterer.

This is an automated email from the ASF dual-hosted git repository.

erans pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-math.git

commit da455397c2e355fedac2e813ea14a50b6a21a4c3
Author: CT <ch...@qq.com>
AuthorDate: Sun Mar 22 12:07:54 2020 +0800

    MATH-1509: Implement the MiniBatchKMeansClusterer.
---
 .../ml/clustering/MiniBatchKMeansClusterer.java    | 276 +++++++++++++++++++++
 .../clustering/MiniBatchKMeansClustererTest.java   | 181 ++++++++++++++
 2 files changed, 457 insertions(+)

diff --git a/src/main/java/org/apache/commons/math4/ml/clustering/MiniBatchKMeansClusterer.java b/src/main/java/org/apache/commons/math4/ml/clustering/MiniBatchKMeansClusterer.java
new file mode 100644
index 0000000..a6c2947
--- /dev/null
+++ b/src/main/java/org/apache/commons/math4/ml/clustering/MiniBatchKMeansClusterer.java
@@ -0,0 +1,276 @@
+/*
+ * 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.commons.math4.ml.clustering;
+
+import org.apache.commons.math4.exception.ConvergenceException;
+import org.apache.commons.math4.exception.MathIllegalArgumentException;
+import org.apache.commons.math4.exception.NumberIsTooSmallException;
+import org.apache.commons.math4.ml.distance.DistanceMeasure;
+import org.apache.commons.math4.util.MathUtils;
+import org.apache.commons.math4.util.Pair;
+import org.apache.commons.rng.UniformRandomProvider;
+import org.apache.commons.rng.sampling.ListSampler;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
+/**
+ * A very fast clustering algorithm base on KMeans(Refer to Python sklearn.cluster.MiniBatchKMeans)
+ * Use a partial points in initialize cluster centers, and mini batch in iterations.
+ * It finish in few seconds when clustering millions of data, and has few differences between KMeans.
+ * See https://www.eecs.tufts.edu/~dsculley/papers/fastkmeans.pdf
+ *
+ * @param <T> Type of the points to cluster
+ */
+public class MiniBatchKMeansClusterer<T extends Clusterable> extends KMeansPlusPlusClusterer<T> {
+
+    /**
+     * Batch data size in iteration.
+     */
+    private final int batchSize;
+    /**
+     * Iteration count of initialize the centers.
+     */
+    private final int initIterations;
+    /**
+     * Data size of batch to initialize the centers, default 3*k
+     */
+    private final int initBatchSize;
+    /**
+     * Max iterate times when no improvement on step iterations.
+     */
+    private final int maxNoImprovementTimes;
+
+
+    /**
+     * Build a clusterer.
+     *
+     * @param k                     the number of clusters to split the data into
+     * @param maxIterations         the maximum number of iterations to run the algorithm for all the points,
+     *                              for mini batch actual iterations <= maxIterations * points.size() / batchSize
+     *                              If negative, no maximum will be used.
+     * @param batchSize             the mini batch size for training iterations.
+     * @param initIterations        the iterations to find out the best clusters centers with mini batch.
+     * @param initBatchSize         the mini batch size to initial the clusters centers,
+     *                              batchSize * 3 is suitable for most case.
+     * @param maxNoImprovementTimes the max iterations times when the square distance has no improvement,
+     *                              10 is suitable for most case.
+     * @param measure               the distance measure to use, EuclideanDistance is recommended.
+     * @param random                random generator to use for choosing initial centers
+     *                              may appear during algorithm iterations
+     */
+    public MiniBatchKMeansClusterer(final int k, final int maxIterations, final int batchSize, final int initIterations,
+                                    final int initBatchSize, final int maxNoImprovementTimes,
+                                    final DistanceMeasure measure, final UniformRandomProvider random,
+                                    final EmptyClusterStrategy emptyStrategy) {
+        super(k, maxIterations, measure, random, emptyStrategy);
+        if (batchSize < 1) throw new NumberIsTooSmallException(batchSize, 1, true);
+        else this.batchSize = batchSize;
+        if (initIterations < 1) throw new NumberIsTooSmallException(initIterations, 1, true);
+        else this.initIterations = initIterations;
+        if (initBatchSize < 1) throw new NumberIsTooSmallException(initBatchSize, 1, true);
+        else this.initBatchSize = initBatchSize;
+        if (maxNoImprovementTimes < 1) throw new NumberIsTooSmallException(maxNoImprovementTimes, 1, true);
+        else this.maxNoImprovementTimes = maxNoImprovementTimes;
+    }
+
+    /**
+     * Runs the MiniBatch K-means clustering algorithm.
+     *
+     * @param points the points to cluster
+     * @return a list of clusters containing the points
+     * @throws MathIllegalArgumentException if the data points are null or the number
+     *                                      of clusters is larger than the number of data points
+     */
+    @Override
+    public List<CentroidCluster<T>> cluster(final Collection<T> points) throws MathIllegalArgumentException, ConvergenceException {
+        // sanity checks
+        MathUtils.checkNotNull(points);
+
+        // number of clusters has to be smaller or equal the number of data points
+        if (points.size() < getK()) {
+            throw new NumberIsTooSmallException(points.size(), getK(), false);
+        }
+
+        final int pointSize = points.size();
+        final int batchCount = pointSize / batchSize + ((pointSize % batchSize > 0) ? 1 : 0);
+        final int max = this.getMaxIterations() < 0 ? Integer.MAX_VALUE : (this.getMaxIterations() * batchCount);
+        List<CentroidCluster<T>> clusters = initialCenters(points);
+        // Loop execute the mini batch steps until reach the max loop times, or cannot improvement anymore.
+        final MiniBatchImprovementEvaluator evaluator = new MiniBatchImprovementEvaluator();
+        for (int i = 0; i < max; i++) {
+            //Clear points in clusters
+            clearClustersPoints(clusters);
+            //Random sampling a mini batch of points.
+            final List<T> batchPoints = randomMiniBatch(points, batchSize);
+            // Processing the mini batch training step
+            final Pair<Double, List<CentroidCluster<T>>> pair = step(batchPoints, clusters);
+            final double squareDistance = pair.getFirst();
+            clusters = pair.getSecond();
+            // Evaluate the training can finished early.
+            if (evaluator.convergence(squareDistance, pointSize)) break;
+        }
+
+        //Add every mini batch points to their nearest cluster.
+        clearClustersPoints(clusters);
+        for (final T point : points) {
+            addToNearestCentroidCluster(point, clusters);
+        }
+        return clusters;
+    }
+
+    /**
+     * clear clustered points
+     *
+     * @param clusters The clusters to clear
+     */
+    private void clearClustersPoints(final List<CentroidCluster<T>> clusters) {
+        for (CentroidCluster<T> cluster : clusters) {
+            cluster.getPoints().clear();
+        }
+    }
+
+    /**
+     * Mini batch iteration step
+     *
+     * @param batchPoints The mini batch points.
+     * @param clusters    The cluster centers.
+     * @return Square distance of all the batch points to the nearest center, and newly clusters.
+     */
+    private Pair<Double, List<CentroidCluster<T>>> step(
+            final List<T> batchPoints,
+            final List<CentroidCluster<T>> clusters) {
+        //Add every mini batch points to their nearest cluster.
+        for (final T point : batchPoints) {
+            addToNearestCentroidCluster(point, clusters);
+        }
+        final List<CentroidCluster<T>> newClusters = adjustClustersCenters(clusters);
+        // Add every mini batch points to their nearest cluster again.
+        double squareDistance = 0.0;
+        for (T point : batchPoints) {
+            final double d = addToNearestCentroidCluster(point, newClusters);
+            squareDistance += d * d;
+        }
+        return new Pair<>(squareDistance, newClusters);
+    }
+
+    /**
+     * Get a mini batch of points
+     *
+     * @param points    all the points
+     * @param batchSize the mini batch size
+     * @return mini batch of all the points
+     */
+    private List<T> randomMiniBatch(final Collection<T> points, final int batchSize) {
+        final ArrayList<T> list = new ArrayList<>(points);
+        ListSampler.shuffle(getRandomGenerator(), list);
+        return list.subList(0, batchSize);
+    }
+
+    /**
+     * Initial cluster centers with multiply iterations, find out the best.
+     *
+     * @param points Points use to initial the cluster centers.
+     * @return Clusters with center
+     */
+    private List<CentroidCluster<T>> initialCenters(final Collection<T> points) {
+        final List<T> validPoints = initBatchSize < points.size() ?
+                randomMiniBatch(points, initBatchSize) : new ArrayList<>(points);
+        double nearestSquareDistance = Double.POSITIVE_INFINITY;
+        List<CentroidCluster<T>> bestCenters = null;
+        for (int i = 0; i < initIterations; i++) {
+            final List<T> initialPoints = (initBatchSize < points.size()) ?
+                    randomMiniBatch(points, initBatchSize) : new ArrayList<>(points);
+            final List<CentroidCluster<T>> clusters = getCentroidInitializer().selectCentroids(initialPoints, getK());
+            final Pair<Double, List<CentroidCluster<T>>> pair = step(validPoints, clusters);
+            final double squareDistance = pair.getFirst();
+            final List<CentroidCluster<T>> newClusters = pair.getSecond();
+            //Find out a best centers that has the nearest total square distance.
+            if (squareDistance < nearestSquareDistance) {
+                nearestSquareDistance = squareDistance;
+                bestCenters = newClusters;
+            }
+        }
+        return bestCenters;
+    }
+
+    /**
+     * Add a point to the cluster which the closest center belong to
+     * and return the distance between point and the closest center.
+     *
+     * @param point    The point to add.
+     * @param clusters The clusters to add to.
+     * @return The distance between point and the closest center.
+     */
+    private double addToNearestCentroidCluster(final T point, final List<CentroidCluster<T>> clusters) {
+        double minDistance = Double.POSITIVE_INFINITY;
+        CentroidCluster<T> closestCentroidCluster = null;
+        // Iterate clusters and find out closest cluster to the point
+        for (CentroidCluster<T> centroidCluster : clusters) {
+            final double distance = distance(point, centroidCluster.getCenter());
+            if (distance < minDistance) {
+                minDistance = distance;
+                closestCentroidCluster = centroidCluster;
+            }
+        }
+        assert closestCentroidCluster != null;
+        closestCentroidCluster.addPoint(point);
+        return minDistance;
+    }
+
+    /**
+     * The Evaluator to evaluate whether the iteration should finish where square has no improvement for appointed times.
+     */
+    class MiniBatchImprovementEvaluator {
+        private Double ewaInertia = null;
+        private double ewaInertiaMin = Double.POSITIVE_INFINITY;
+        private int noImprovementTimes = 0;
+
+        /**
+         * Evaluate whether the iteration should finish where square has no improvement for appointed times
+         *
+         * @param squareDistance the total square distance of the mini batch points to their nearest center.
+         * @param pointSize      size of the the data points.
+         * @return true if no improvement for appointed times, otherwise false
+         */
+        public boolean convergence(final double squareDistance, final int pointSize) {
+            final double batchInertia = squareDistance / batchSize;
+            if (ewaInertia == null) {
+                ewaInertia = batchInertia;
+            } else {
+                // Refer to sklearn, pointSize+1 maybe intent to avoid the div/0 error,
+                // but java double does not have a div/0 error
+                double alpha = batchSize * 2.0 / (pointSize + 1);
+                alpha = Math.min(alpha, 1.0);
+                ewaInertia = ewaInertia * (1 - alpha) + batchInertia * alpha;
+            }
+
+            // Improved
+            if (ewaInertia < ewaInertiaMin) {
+                noImprovementTimes = 0;
+                ewaInertiaMin = ewaInertia;
+            } else {
+                // No improvement
+                noImprovementTimes++;
+            }
+            // Has no improvement continuous for many times
+            return noImprovementTimes >= maxNoImprovementTimes;
+        }
+    }
+}
diff --git a/src/test/java/org/apache/commons/math4/ml/clustering/MiniBatchKMeansClustererTest.java b/src/test/java/org/apache/commons/math4/ml/clustering/MiniBatchKMeansClustererTest.java
new file mode 100644
index 0000000..167f338
--- /dev/null
+++ b/src/test/java/org/apache/commons/math4/ml/clustering/MiniBatchKMeansClustererTest.java
@@ -0,0 +1,181 @@
+/*
+ * 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.commons.math4.ml.clustering;
+
+import org.apache.commons.math4.exception.NumberIsTooSmallException;
+import org.apache.commons.math4.ml.clustering.evaluation.CalinskiHarabasz;
+import org.apache.commons.math4.ml.distance.DistanceMeasure;
+import org.apache.commons.math4.ml.distance.EuclideanDistance;
+import org.apache.commons.rng.simple.RandomSource;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
+public class MiniBatchKMeansClustererTest {
+    /**
+     * Assert the illegal parameter throws proper Exceptions.
+     */
+    @Test
+    public void testConstructorParameterChecks() {
+        expectNumberIsTooSmallException(() -> new MiniBatchKMeansClusterer<>(1, -1, -1, 3, 300, 10, null, null, null));
+        expectNumberIsTooSmallException(() -> new MiniBatchKMeansClusterer<>(1, -1, 100, -2, 300, 10, null, null, null));
+        expectNumberIsTooSmallException(() -> new MiniBatchKMeansClusterer<>(1, -1, 100, 3, -300, 10, null, null, null));
+        expectNumberIsTooSmallException(() -> new MiniBatchKMeansClusterer<>(1, -1, 100, 3, 300, -10, null, null, null));
+    }
+
+    /**
+     * Expects block throws NumberIsTooSmallException.
+     * @param block the block need to run.
+     */
+    private void expectNumberIsTooSmallException(Runnable block) {
+        assertException(block, NumberIsTooSmallException.class);
+    }
+
+    /**
+     * Compare the result to KMeansPlusPlusClusterer
+     */
+    @Test
+    public void testCompareToKMeans() {
+        //Generate 4 cluster
+        int randomSeed = 0;
+        List<DoublePoint> data = generateCircles(randomSeed);
+        KMeansPlusPlusClusterer<DoublePoint> kMeans = new KMeansPlusPlusClusterer<>(4, -1, DEFAULT_MEASURE,
+                RandomSource.create(RandomSource.MT_64, randomSeed));
+        MiniBatchKMeansClusterer<DoublePoint> miniBatchKMeans = new MiniBatchKMeansClusterer<>(4, -1, 100, 3, 300, 10,
+                DEFAULT_MEASURE, RandomSource.create(RandomSource.MT_64, randomSeed), KMeansPlusPlusClusterer.EmptyClusterStrategy.LARGEST_VARIANCE);
+        // Test 100 times between KMeansPlusPlusClusterer and MiniBatchKMeansClusterer
+        for (int i = 0; i < 100; i++) {
+            List<CentroidCluster<DoublePoint>> kMeansClusters = kMeans.cluster(data);
+            List<CentroidCluster<DoublePoint>> miniBatchKMeansClusters = miniBatchKMeans.cluster(data);
+            // Assert cluster result has proper clusters count.
+            Assert.assertEquals(4, kMeansClusters.size());
+            Assert.assertEquals(kMeansClusters.size(), miniBatchKMeansClusters.size());
+            int totalDiffCount = 0;
+            for (CentroidCluster<DoublePoint> kMeanCluster : kMeansClusters) {
+                // Find out most similar cluster between two clusters, and summary the points count variances.
+                CentroidCluster<DoublePoint> miniBatchCluster = predict(miniBatchKMeansClusters, kMeanCluster.getCenter());
+                totalDiffCount += Math.abs(kMeanCluster.getPoints().size() - miniBatchCluster.getPoints().size());
+            }
+            // Statistic points different ratio.
+            double diffPointsRatio = totalDiffCount * 1.0 / data.size();
+            // Evaluator score different ratio by "CalinskiHarabasz" algorithm.
+            ClusterEvaluator clusterEvaluator = new CalinskiHarabasz();
+            double kMeansScore = clusterEvaluator.score(kMeansClusters);
+            double miniBatchKMeansScore = clusterEvaluator.score(miniBatchKMeansClusters);
+            double scoreDiffRatio = (kMeansScore - miniBatchKMeansScore) /
+                    kMeansScore;
+            // MiniBatchKMeansClusterer has few score differences between KMeansClusterer(less then 10%).
+            Assert.assertTrue(String.format("Different score ratio %f%%!, diff points ratio: %f%%", scoreDiffRatio * 100, diffPointsRatio * 100),
+                    scoreDiffRatio < 0.1);
+        }
+    }
+
+    /**
+     * Generate points around 4 circles.
+     * @param randomSeed Random seed
+     * @return Generated points.
+     */
+    private List<DoublePoint> generateCircles(int randomSeed) {
+        List<DoublePoint> data = new ArrayList<>();
+        Random random = new Random(randomSeed);
+        data.addAll(generateCircle(250, new double[]{-1.0, -1.0}, 1.0, random));
+        data.addAll(generateCircle(260, new double[]{0.0, 0.0}, 0.7, random));
+        data.addAll(generateCircle(270, new double[]{1.0, 1.0}, 0.7, random));
+        data.addAll(generateCircle(280, new double[]{2.0, 2.0}, 0.7, random));
+        return data;
+    }
+
+    /**
+     * Generate points as circles.
+     * @param count total points count.
+     * @param center circle center point.
+     * @param radius the circle radius points around.
+     * @param random the Random source.
+     * @return Generated points.
+     */
+    List<DoublePoint> generateCircle(int count, double[] center, double radius, Random random) {
+        double x0 = center[0];
+        double y0 = center[1];
+        ArrayList<DoublePoint> list = new ArrayList<>(count);
+        for (int i = 0; i < count; i++) {
+            double ao = random.nextDouble() * 720 - 360;
+            double r = random.nextDouble() * radius * 2 - radius;
+            double x1 = x0 + r * Math.cos(ao * Math.PI / 180);
+            double y1 = y0 + r * Math.sin(ao * Math.PI / 180);
+            list.add(new DoublePoint(new double[]{x1, y1}));
+        }
+        return list;
+    }
+
+    /**
+     * Assert there should be a exception.
+     *
+     * @param block          The code block need to assert.
+     * @param exceptionClass A exception class.
+     */
+    public static void assertException(Runnable block, Class<? extends Throwable> exceptionClass) {
+        try {
+            block.run();
+            Assert.fail(String.format("Expects %s", exceptionClass.getSimpleName()));
+        } catch (Throwable e) {
+            if (!exceptionClass.isInstance(e)) throw e;
+        }
+    }
+
+    /**
+     * Use EuclideanDistance as default DistanceMeasure
+     */
+    public static final DistanceMeasure DEFAULT_MEASURE = new EuclideanDistance();
+
+    /**
+     * Predict which cluster is best for the point
+     *
+     * @param clusters cluster to predict into
+     * @param point    point to predict
+     * @param measure  distance measurer
+     * @param <T>      type of cluster point
+     * @return the cluster which has nearest center to the point
+     */
+    public static <T extends Clusterable> CentroidCluster<T> predict(List<CentroidCluster<T>> clusters, Clusterable point, DistanceMeasure measure) {
+        double minDistance = Double.POSITIVE_INFINITY;
+        CentroidCluster<T> nearestCluster = null;
+        for (CentroidCluster<T> cluster : clusters) {
+            double distance = measure.compute(point.getPoint(), cluster.getCenter().getPoint());
+            if (distance < minDistance) {
+                minDistance = distance;
+                nearestCluster = cluster;
+            }
+        }
+        return nearestCluster;
+    }
+
+    /**
+     * Predict which cluster is best for the point
+     *
+     * @param clusters cluster to predict into
+     * @param point    point to predict
+     * @param <T>      type of cluster point
+     * @return the cluster which has nearest center to the point
+     */
+    public static <T extends Clusterable> CentroidCluster<T> predict(List<CentroidCluster<T>> clusters, Clusterable point) {
+        return predict(clusters, point, DEFAULT_MEASURE);
+    }
+}