| ABSTRACT Accurate One Pass Decision Tree Construction (2008) | |||||||||||||||
Abstract | |||||||||||||||
| In mining continuous data streams, one popular paradigm is using sampling and having a one-pass algorithm with probabilistic bound on the accuracy. A key application of this approach is in decision tree construction. A disadvantage, however, of an algorithm that only achieves a probabilistic bound is that there are no guarantees from the results obtained from a particular application of the algorithm. In this paper, we present an approach for making one-pass decision tree construction more accurate. We present a new algorithm which attempts to determine, and mark as such, exact split points for nodes. This is done by creating a confidence interval near the probabilistic split point for a node, and storing and potentially reassigning samples that belong to this interval. The confidence intervals are constructed using Hoeffding inequality, and can be shrunk as additional samples are processed. We have evaluated our approach using a number of synthetic and real datasets. In summary, our results suggests that the approach can split a large fraction of the nodes exactly, with only modest memory and computational overheads. 1. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||