apache/spark — pull request #2419 by derrickburns (2014-09-16 23:01:58+00:00)
Title: This commit addresses SPARK-3218, SPARK-3219, SPARK-3261, and SPARK-3424...

....

This commit introduces a general distance function (PointOps) for the KMeans clusterer. There are no public API changes. However, the behavior of the clusterer is different on some tests. Specifically, the handling of empty clusters has changed. Emply clusters are not filled with random points in this implementation. The former behavior is undesirable for a number a reasons, not the least of which is that there is no reasonable use for duplicate cluster centers. To accommodate the change in behaviour, the test cases were changed accordingly. This addresses SPARK-3261.

The PointOps trait defines the distance function. The PointOps trait is more than a simple distance function. It also defines the types of Points and Centers for the clusterer. Standard MLLIB Vectors are converted into Points and Centers. In the case of the FastEuclideanOps implementation of PointOps, the Point and Center types includes vector norm members. In other distance functions such as the Kullback-Leibler distance function, the Point and Center types include different values that speed up the distance calculation in a similar way that caching vector norms speeds up the Euclidean distance function. This addresses SPARK-3219.

This commit also splits up the clusterer into a number of components which behave (largely) like their predecessors. KMeansParallel implements the K-Means || initialization algorithm. KMeansRandom implements the K-Means Random initialization algorithm. MultiKMeans implements the general K-Means algorithm on a given distance function. Traits for the initializer (KMeansInitializer) and the general algorithm (MultiKMeansClusterer) are provided to highlight the salient interfaces.

The KMeansPlusPlus implementation was sped up by NOT recomputing distances to clusters centers that were present in previous steps. This DRAMATICALLY improves the performance of the K-Means Parallel run. This addresses SPARK-3424.

The next step is to make different distance functions available through the user-visible API. This commit does NOT do that. Rather, the purpose of this commit is to introduce an implementation of a generic K-Means clusterer that uses different distance functions.

The private K-Means constructor which was used by some test Java code was replaced with a Scala constructor that is not Java friendly. Since the constructor was not user visible, I simply changed the Java test code to use the higher level interface.

This code has been tested (albeit while packaged outside of Spark) and performance measured on data sets of millions of features each with hundreds of dimensions and on tens of thousands of clusters.