Online K-means
Also known as: sequential k-means, streaming k-means, incremental k-means, online clustering
Online K-means is a streaming variant of the classical K-means algorithm that updates cluster centroids one observation at a time — or in small mini-batches — without storing the entire dataset in memory. It is particularly suited to large-scale, real-time, or continuously arriving data where batch recomputation would be too slow or impractical.
Key highlights
- Processes data in a single pass, making it feasible for datasets that exceed available RAM.
- Naturally adapts to streaming or continuously updating data without full recomputation.
- Computationally lightweight per update: O(K·d) per point, where d is the feature dimension.
- Mini-batch variant (Sculley 2010) provides further speedups with near-identical clustering quality to batch K-means.
- Easily parallelised: mini-batches can be processed concurrently across workers.
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
When to use it
Use Online K-means when the dataset is too large to fit in memory, when data arrives as a stream and clusters must be updated continuously, or when fast approximate clustering is needed for downstream real-time applications. It is also a practical choice for very large static datasets as a scalable alternative to batch K-means. Do not use it when the number of clusters K is unknown and no elbow or silhouette analysis is feasible; when clusters are non-spherical or of very different densities (prefer DBSCAN or GMM); or when high clustering precision on a small, static dataset is needed (batch K-means converges more reliably).
Strengths & limitations
- Processes data in a single pass, making it feasible for datasets that exceed available RAM.
- Naturally adapts to streaming or continuously updating data without full recomputation.
- Computationally lightweight per update: O(K·d) per point, where d is the feature dimension.
- Mini-batch variant (Sculley 2010) provides further speedups with near-identical clustering quality to batch K-means.
- Easily parallelised: mini-batches can be processed concurrently across workers.
- Sensitive to the choice of K; requires specifying the number of clusters in advance.
- Assumes spherical, roughly equal-sized clusters; performs poorly on elongated or density-varying cluster shapes.
- Centroid estimates can be noisy early in the stream before sufficient data has been seen.
- Not invariant to feature scale — features must be standardised beforehand.
- Results depend on random initialisation; K-means++ initialisation is strongly recommended.
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
How does Online K-means differ from Mini-Batch K-means?
Online K-means processes one point at a time; Mini-Batch K-means (Sculley 2010) processes small random batches and uses a slightly modified centroid-update rule that improves convergence speed. Both are streaming variants; Mini-Batch is more commonly used in practice due to better vectorisation on modern hardware.
How do I choose K in a streaming setting?
Run batch or Mini-Batch K-means on a representative subsample of the data first, using elbow or silhouette analysis to identify K. Then fix K and deploy Online K-means on the full stream with those initialised centroids.
Does Online K-means converge to the same solution as batch K-means?
Asymptotically yes, given stationary data and a decreasing learning rate. In practice, early noise and local minima can lead to slightly different solutions, so multiple restarts (with K-means++ init) and a final evaluation step are advisable.
What if the data distribution changes over time (concept drift)?
Standard Online K-means does not handle concept drift; old observations permanently influence centroids. To cope with drift, use a windowed or decaying-weight variant that down-weights older points, or periodically re-initialise centroids on recent data.
Should I scale my features?
Yes. Online K-means uses Euclidean distance, which is dominated by high-variance features. Apply standard scaling (zero mean, unit variance) or min-max scaling before clustering, fitting the scaler only on a representative subsample to avoid storing all data.
Sources
- 1.MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1, pp. 281–297. University of California Press.
- 2.Sculley, D. (2010). Web-scale k-means clustering. In Proceedings of the 19th International Conference on World Wide Web (WWW 2010), pp. 1177–1178. ACM.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). Online K-means. ScholarGate. https://scholargate.app/machine-learning/online-k-means