Planing to implement Mini Batch K-Means on a large scale dataset resembles to sklean.cluster.MiniBatchKMeans.

In the first step, b samples are drawn randomly from the dataset, to form a mini-batch. These are then assigned to the nearest centroid. In the second step, the centroids are updated. In contrast to k-means, this is done on a per-sample basis. For each sample in the mini-batch, the assigned centroid is updated by taking the streaming average of the sample and all previous samples assigned to that centroid.

sklean description (I might misunderstood the sklearn doc):

In terms of first step, it says that only assign newly sampled data to their closest clusters. What about the samples drew from previous rounds, shouldn't we also update them.

My understanding:

In the first step, assign these newly drawn data along with all previous samples if any to the nearest centroid.

Which would be a common implementaion for mini batch K-Means? Suppose, we do not update previous samples to their nearest clusters, will the K-Means converge?


1 Answer 1


If I understand correctly, you suggest assigning all data points to their nearest centroids, then update all centroids to be the mean of the points assigned to them. This is Lloyd's algorithm, which is the typical batch algorithm used to solved k-means. It would no longer operate on mini-batches.

  • 1
    $\begingroup$ Thanks for the answer. Not all, but assigning current batch and reassigning data from past batches since centroids get updated. $\endgroup$
    – Logan
    Commented Feb 27, 2018 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.