Confidence Decision Trees via Online and Active Learning for Streaming
  (BIG) Data
  Decision tree classifiers are a widely used tool in data stream mining. The
use of confidence intervals to estimate the gain associated with each split
leads to very effective methods, like the popular Hoeffding tree algorithm.
From a statistical viewpoint, the analysis of decision tree classifiers in a
streaming setting requires knowing when enough new information has been
collected to justify splitting a leaf. Although some of the issues in the
statistical analysis of Hoeffding trees have been already clarified, a general
and rigorous study of confidence intervals for splitting criteria is missing.
We fill this gap by deriving accurate confidence intervals to estimate the
splitting gain in decision tree learning with respect to three criteria:
entropy, Gini index, and a third index proposed by Kearns and Mansour. Our
confidence intervals depend in a more detailed way on the tree parameters. We
also extend our confidence analysis to a selective sampling setting, in which
the decision tree learner adaptively decides which labels to query in the
stream. We furnish theoretical guarantee bounding the probability that the
classification is non-optimal learning the decision tree via our selective
sampling strategy. Experiments on real and synthetic data in a streaming
setting show that our trees are indeed more accurate than trees with the same
number of leaves generated by other techniques and our active learning module
permits to save labeling cost. In addition, comparing our labeling strategy
with recent methods, we show that our approach is more robust and consistent
respect all the other techniques applied to incremental decision trees.
