The ABACOC algorithm: A novel approach for nonparametric classification of data streams

Rocco De Rosa, Francesco Orabona, Nicolò Cesa-Bianchi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations


Stream mining poses unique challenges to machinelearning: predictive models are required to be scalable, incrementally trainable, must remain bounded in size, and benonparametric in order to achieve high accuracy even in complexand dynamic environments. Moreover, the learning system mustbe parameterless - traditional tuning methods are problematicin streaming settings - and avoid requiring prior knowledge ofthe number of distinct class labels occurring in the stream. Inthis paper, we introduce a new algorithmic approach for nonparametriclearning in data streams. Our approach addresses allabove mentioned challenges by learning a model that covers theinput space using simple local classifiers. The distribution of theseclassifiers dynamically adapts to the local (unknown) complexityof the classification problem, thus achieving a good balancebetween model complexity and predictive accuracy. By means ofan extensive empirical evaluation against standard nonparametricbaselines, we show state-of-the-art results in terms of accuracyversus model size. Our empirical analysis is complemented by atheoretical performance guarantee which does not rely on anystochastic assumption on the source generating the stream.
Original languageEnglish (US)
Title of host publicationProceedings - IEEE International Conference on Data Mining, ICDM
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Print)9781467395038
StatePublished - Jan 5 2016
Externally publishedYes


Dive into the research topics of 'The ABACOC algorithm: A novel approach for nonparametric classification of data streams'. Together they form a unique fingerprint.

Cite this