[PROPOSAL] Unsupervised Algorithm Implementation

Background

Currently, the traditional clustering algorithm KMeans has been implemented in Mars.

However, for a scientific computing library, there are few clustering algorithms implemented in Mars, and there is a lack of unsupervised clustering algorithms for optimizing large-scale data.

Mini-batch KMeans

Mini-batch KMeans is an improvement of KMeans algorithm specifically for processing large scale data.
Reference:
Sculley, David. "Web-scale k-means clustering." Proceedings of the 19th international conference on World wide web. 2010.
See https://www.eecs.tufts.edu/~dsculley/papers/fastkmeans.pdf.

implement proposal

1. Implement the main algorithm class MiniBatchKMeans. Inherit KMeans class so that I can resuse _check_param , _check_test_data and other functions.
2. Implement the function mini_batch_k_means.
3. Implement the main function _mini_batch_step separately. This function serves as the core part of each iteration of the Mini-batch KMeans algorithms.
4. The _init_centroids function in _kmeans.py has support for batch and can be reused directly.

API definition

Use the same API design as Sklearn for now, but may change later due to the need for distributed optimization.

1. n_clusters: The number of clusters to form as well as the number of centroids to generate.
2. init: {'k-means++', 'random', 'k-means||'}, Method for initialization.
3. max_iter: Maximum number of iterations over the complete dataset before stopping independently of any early stopping criterion heuristics.
4. batch_size: Size of the mini batches.
5. verbose: Verbosity mode.
6. compute_labels: Compute label assignment and inertia for the complete dataset once the minibatch optimization has converged in fit.
7. random_state: Determines random number generation for centroid initialization and random reassignment. Use an int to make the randomness deterministic.
8. tol: Control early stopping based on the relative center changes as measured by a smoothed, variance-normalized of the mean center squared position changes. This early stopping heuristics is closer to the one used for the batch variant of the algorithms but induces a slight computational and memory overhead over the inertia heuristic. To disable convergence detection based on normalized center change, set tol to 0.0 (default).
9. max_no_improvement: Control early stopping based on the consecutive number of mini batches that does not yield an improvement on the smoothed inertia. To disable convergence detection based on inertia, set max_no_improvement to None.
10. init_size: Number of samples to randomly sample for speeding up the initialization (sometimes at the expense of accuracy): the only algorithm is initialized by running a batch KMeans on a random subset of the data. This needs to be larger than n_clusters.
11. n_init: Number of random initializations that are tried. In contrast to KMeans, the algorithm is only run once, using the best of the n_init initializations as measured by inertia.
12. reassignment_ratio: Control the fraction of the maximum number of counts for a center to be reassigned. A higher value means that low count centers are more easily reassigned, which means that the model will take longer to converge, but should converge in a better clustering.

Start by reading the existing KMeans implementation, especially _kmeans.py and its _init_centroids, _check_param, and _check_test_data helpers. Use the linked Sculley paper and the sklearn API list to define MiniBatchKMeans, mini_batch_k_means, and _mini_batch_step. Done means the proposed mini-batch algorithm and listed parameters are implemented while reusing the existing KMeans pieces.