I am self-studying some data clustering algorithms recently to solve a problem at work. Sometimes my data set is too big to perform k-means so I take a shortcut: (1) first randomly sample, without replacement, from the data set, then (2) perform k-means on the random sample, finally (3) assign the original data to the closest centroids found in step (2).

I am wondering if there is any performance guarantee, even probabilistically, about the above approach? For example, can we say something like:

(a) If we sample a fraction $f$ of the original data, then we sample all clusters with high probability (probability that depends on $f$);

(b) If we sample a fraction $f$ of the original data, then the resulting within-cluster-distances is at most a fraction $f$ of the within-cluster-distances of the original data.

It seems intuitive to me that the random sample is usually representative of my original data. So it seems okay to just perform k-means on the random sample. Of course with somewhat low probability I can get really unlucky to draw a bad sample. So I want to quantify this "low probability".

The closet theoretical result I can find is in Theorem 1 of this article (screenshot below). But the result assumes that the random sample is drawn with replacement (assumes $X_i$'s are independent). Can a similar (hopefully better) result be shown for random sample without replacement?

enter image description here

Intuitively sample without replacement should do better because the clusters that have not been sampled yet will have relatively higher probability of being drawn compared to the clusters that have been sampled. So random sample without replacement is less likely to miss a cluster with replacement. Even if no results can be shown, is my intuition making sense?

Thanks in advance for any guidance.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.