FIELD

The disclosure relates generally to data clustering on computing systems, and more particularly, to efficiently initializing distributed clustering on large data sets.

BACKGROUND

Cluster analysis (clustering) is a well-documented machine learning (ML) problem. One of the simplest and most popular clustering algorithms is called “k-means” clustering. In short, the algorithm uses an a priori chosen number of centroids (“k”) to cluster data points. Every sample in the data set is a member of a cluster represented by the centroid closest to the sample as measured by some distance metric (e.g., the “L2” metric, generalized Pythagorean theorem). The algorithm iteratively moves centroid positions to find a state where the total sum of distances is minimal.

One of the major weaknesses of k-means clustering is the quality of clustering results being heavily dependent on the initial position of the centroids. One drawback of k-means clustering is that it requires the number of clusters k as an input parameter. The quality of k-means clustering increases as the value of the k parameter approaches the number of natural clusters in the dataset, but the optimal value of k is unknown before execution of the algorithm. A second drawback is that the quality of k-means clustering increases as the initial centroid positions approach the locations of the natural centroids of the clusters, but these locations are unknown before execution of the algorithm. The k-means++ clustering algorithm addresses this second drawback. The k-means++ algorithm attempts to initialize centroid starting positions by probabilistically leveraging points already present in the dataset instead of attempting to evenly partition the entire space or use purely random datapoints.

However, the computational power required to perform naïve k-means++ initialization on the scale of very large datasets (e.g., hundreds of millions of samples, hundreds of features each) is prohibitively large to the point of such an approach being infeasible.

Additionally, in some cases, ML systems that perform further processing on the clustered data can typically only reasonably handle clusters below a certain size. Larger clusters pose a significant hurdle due to the nonlinear scaling of the computational difficulty of ML modelling. Also, clusters that are only hundreds of samples or less in size pose a problem too, because there is not enough data in them to reliably train a ML model. Both the unfeasibly large and the unfeasibly small clusters may be natively present in a dataset and routinely manifest themselves. Conventional techniques, such as k-means++, are unable to prevent clusters of unacceptable size from forming upon initialization.

SUMMARY

In an aspect, the inventive subject matter provides a large-dataset-capable centroid initialization method that utilizes a random sampling window to increase speed of centroid initialization. In some embodiments, the initialization method is modified to leverage parallelism, configured to execution on multi-node compute clusters. Optionally, the initialization method can include a post-initialization centroid discarding and/or re-assignment that adaptively controls cluster sizes.

Systems and methods enable efficiently initializing centroids for clustering operations by (i) obtaining a set of datapoints, wherein the set of datapoints includes a plurality of datapoints; (ii) performing one or more integrity checks on the set of datapoints; (iii) spawning a plurality of threads; (iv) creating, in parallel by the plurality of threads, a random view of the set of datapoints; (v) determining, in parallel by each thread of the plurality of threads, a window of the random view of the set of datapoints for the thread, wherein each window comprises a distinct sub-space of the set of datapoints; and (vi) producing, in parallel by each thread of the plurality of threads, one centroid for the datapoints within the window of the thread by performing one iteration of a clustering algorithm, wherein each produced centroid is stored in a memory storage local to each thread.

