Online Clustering with Experts

Anna Choromanska, Claire Monteleoni
Proceedings of the Workshop on On-line Trading of Exploration and Exploitation 2, PMLR 26:1-18, 2012.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v26-choromanska12a, title = {Online Clustering with Experts}, author = {Choromanska, Anna and Monteleoni, Claire}, booktitle = {Proceedings of the Workshop on On-line Trading of Exploration and Exploitation 2}, pages = {1--18}, year = {2012}, editor = {Glowacka, Dorota and Dorard, Louis and Shawe-Taylor, John}, volume = {26}, series = {Proceedings of Machine Learning Research}, address = {Bellevue, Washington, USA}, month = {02 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v26/choromanska12a/choromanska12a.pdf}, url = {https://proceedings.mlr.press/v26/choromanska12a.html}, 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.} }
Endnote
%0 Conference Paper %T Online Clustering with Experts %A Anna Choromanska %A Claire Monteleoni %B Proceedings of the Workshop on On-line Trading of Exploration and Exploitation 2 %C Proceedings of Machine Learning Research %D 2012 %E Dorota Glowacka %E Louis Dorard %E John Shawe-Taylor %F pmlr-v26-choromanska12a %I PMLR %P 1--18 %U https://proceedings.mlr.press/v26/choromanska12a.html %V 26 %X 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.
RIS
TY - CPAPER TI - Online Clustering with Experts AU - Anna Choromanska AU - Claire Monteleoni BT - Proceedings of the Workshop on On-line Trading of Exploration and Exploitation 2 DA - 2012/05/02 ED - Dorota Glowacka ED - Louis Dorard ED - John Shawe-Taylor ID - pmlr-v26-choromanska12a PB - PMLR DP - Proceedings of Machine Learning Research VL - 26 SP - 1 EP - 18 L1 - http://proceedings.mlr.press/v26/choromanska12a/choromanska12a.pdf UR - https://proceedings.mlr.press/v26/choromanska12a.html AB - 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. ER -
APA
Choromanska, A. & Monteleoni, C.. (2012). Online Clustering with Experts. Proceedings of the Workshop on On-line Trading of Exploration and Exploitation 2, in Proceedings of Machine Learning Research 26:1-18 Available from https://proceedings.mlr.press/v26/choromanska12a.html.

Related Material