Incremental fuzzy decision tree classification method for data streams mining based on threaded binary search trees

Decision tree classification is a well-studied problem in data mining. Recently, there has been much interest in mining data streams. Domingos and Hulten have presented a one-pass algorithm. Their system, VFDT, uses Hoeffding inequality to achieve a probabilistic bound on the accuracy of the tree constructed. Gama et al. have extended VFDT in two directions. Their system VFDTc can deal with continuous data and use more powerful classification techniques at tree leaves. Peng et al. present soft discretization method to solve continuous attributes in data mining. This paper revisits this problem and implemented a system fVFDT on top of VFDT and VFDTc. It has the following four contributions: (l). It presents a threaded binary search trees (TBST) approach for efficiently handling continuous attributes. It builds a threaded binary search tree, and its processing time for values inserting is O(nlogn), while VFDT's processing time is O(n²). When a new example arrives, VFDTc need update O(logn) attribute tree nodes, but fVFDT just need update one necessary node. (2) It improves the method of getting the best split-test point of a given continuous attribute. Comparing to the method used in VFDTc, it improves from O(nlogn) to O(n) in processing time. (3) Comparing to VFDTc, fVFDT's candidate split-test number decrease from O(n) to O(logn). (4) It uses soft discretization method in data streams mining to solve the problem of noise data.