Name
Abstract | ||
|---|---|---|
We propose an online clustering algorithm that manages the exploration/exploitation tradeoff using an adaptive weighting over batch clustering algorithms. We extend algorithms for online supervised learning, with access to expert predictors, to the unsupervised learning setting. Instead of computing prediction errors in order to re-weight the experts, the algorithm computes an approximation to the current value of the \emphk-means objective obtained by each expert. When the experts are batch clustering algorithms with \emphb-approximation guarantees with respect to the \emphk-means objective (for example, the \emphk-means++ or \emphk-means # algorithms), applied to a sliding window of the data stream, our algorithm achieves an approximation guarantee with respect to the \emphk-means objective. The form of this online clustering approximation guarantee is novel, and extends an evaluation framework proposed by Dasgupta as an analog to regret. Our algorithm tracks the best clustering algorithm on real and simulated data sets. |
Year | Venue | DocType |
|---|---|---|
2012 | ICML On-line Trading of Exploration and Exploitation | Journal |
Volume | Citations | PageRank |
22 | 3 | 0.40 |
References | Authors | |
25 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anna Choromanska | 1 | 52 | 9.48 |
| Claire Monteleoni | 2 | 327 | 24.15 |