Confidence decision trees via online and active learning for streaming data

Decision tree classiers are a widely used tool in data stream mining. The use of condence intervals to estimate the gain associated with each split leads to very eective methods, like the popular Hoeding tree algorithm. From a statistical viewpoint, the analysis of decision tree classiers 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 Hoeding trees have been already claried, a general and rigorous study of condence intervals for splitting criteria is missing. We ll this gap by deriving accurate condence 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. We also extend our condence analysis to a selective sampling setting, in which the decision tree learner adaptively decides which labels to query in the stream. We provide theoretical guarantees bounding the probability that the decision tree learned via our selective sampling strategy classies suboptimally the next example in the stream. 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 state-of- the-art techniques. In addition to that, our active learning module empirically uses fewer labels without signicantly hurting the performance.