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

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.