Online Clustering with Experts

Workshop on On-line Trading of Exploration and Exploitation 2

Anna Choromanska [e-mail]

PID  :  120711

来源: CEUR

【 摘 要 】

We propose an online clustering algorithm that manages the exploration/exploitation trade off 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 reweight the experts, the algo rithm computes an approximation to the current value of the kmeans objective obtained by each expert. When the experts are batch clustering algorithms with bapproximation guarantees with respect to the kmeans objective (for example, the kmeans++ or kmeans# algorithms), applied to a sliding window of the data stream, our algorithm achieves an approximation guarantee with respect to the kmeans objective. The form of this online clustering approx imation 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.