Abstract
Approximating the $k$-means clustering objective with an online learning algorithm is an open problem. We introduce a family of online clustering algorithms by extending algorithms for online supervised learning to the unsupervised setting. By treating various clustering algorithms as "experts," our framework provides the first online clustering algorithms with provable approximation guarantees relative to the optimal $k$-means cost of the entire data stream.
Introduction
Clustering is a fundamental unsupervised learning task, with the $k$-means objective being the most widely used metric for quality. However, most $k$-means algorithms are "batch" processes—they require the entire dataset upfront. In the real world, data often arrives as an endless stream (e.g., sensor data, stock prices, or news feeds), where we can only see each point once and have limited memory.
While some "streaming" clustering algorithms exist, providing provable guarantees in an online setting is notoriously difficult. Specifically, it is hard to ensure that an algorithm making local, immediate decisions will result in a clustering that is globally competitive with the best possible clustering of the whole sequence. This paper bridges the gap between the theoretical rigor of supervised "prediction with expert advice" and the practical necessity of online unsupervised clustering.
Methods: Online Clustering with Experts (OCE)
The authors propose a family of algorithms called Online Clustering with Experts (OCE). The core idea is to maintain a set of "expert" clustering algorithms and dynamically re-weight them based on their performance.
Experts as Black Boxes
The framework can use any batch clustering algorithm (like $k$-means++ or $k$-means#) as an expert. These experts are run on a sliding window of the most recent data points.
The Loss Function
In supervised learning, experts are penalized when they predict the wrong label. In OCE, the "loss" is defined as the squared distance between the current data point and the closest cluster center proposed by the expert. The authors demonstrate that the $k$-means loss function satisfies a property called $(c, \eta)$-realizability, which allows supervised regret bounds to be mathematically ported to the unsupervised setting.
Weighting Variants
The authors adapt three classic online learning strategies:
- Static-Expert: Best for stationary data where one expert is likely to be the best throughout.
- Fixed-Share: Designed for non-stationary data where the "best" expert might change over time.
- Learn-$\alpha$: An adaptive version that learns how quickly to switch between experts without needing to know the data's volatility in advance.
Experimental Evaluation
The authors evaluated their algorithms on a mix of synthetic and real-world datasets from the UCI Machine Learning Repository:
- Synthetic: A mixture of 25 well-separated Gaussians in 15-dimensional space.
- Real-world: Cloud (10D), Spambase (58D), Intrusion (38D), Forest Fires (13D), and Robot Navigation (24D). The Robot Navigation dataset is notably non-stationary, providing a rigorous test for adaptive algorithms.
Key Results
In head-to-head tests, OCE variants consistently outperformed standard online baselines like the "Doubling Algorithm" and "Online $k$-means."
The Learn-$\alpha$ variant proved to be the most practical, as it automatically tracked the best-performing Fixed-Share parameters. This makes it highly effective even when the user doesn't know the nature of the data stream.
Theoretical Guarantees
The authors provide regret bounds showing that the OCE algorithms will perform nearly as well as the best expert (or best sequence of experts) in their set. This is a strong theoretical result because the online algorithm never sees the future, yet it competes with a hindsight-optimal batch solution.
Discussion and Future Work
While the OCE framework provides strong guarantees, it depends on the window size ($W$) used by the experts. Larger windows improve performance on stationary data but increase computational costs. Future research directions include aggregating all cluster centers from all experts rather than just the closest ones and reducing computational overhead to better handle high-velocity stream environments.
In conclusion, by framing clustering as a prediction problem, this work provides a robust theoretical foundation and practical algorithms for online data analysis.
Summary updated