Online K-means
Online K-means Clustering (Sequential / Streaming 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.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
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.
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
- 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. link ↗
- 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. DOI: 10.1145/1772690.1772862 ↗
How to cite this page
ScholarGate. (2026, June 3). Online K-means Clustering (Sequential / Streaming K-means). ScholarGate. https://scholargate.app/en/machine-learning/online-k-means
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- DBSCANMachine learning↔ compare
- Hierarchical ClusteringMachine learning↔ compare
- K-Means ClusteringMachine learning↔ compare
- Self-Organizing MapMachine learning↔ compare