A New Fuzzy Decision Tree Classification Method for Mining High-Speed Data Streams Based on Binary Search Trees

摘要

Decision tree construction 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 for decision tree constructions. Their system using 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. In this paper, we revisit these problems and implemented a system sVFDT for data stream mining. We make the following contributions: 1) we present a binary search trees (BST) approach for efficiently handling continuous attributes. Its processing time for values inserting is O(nlogn), while VFDT‘s processing time is O(n 2 ). 2) We improve the method of getting the best split-test point of a given continuous attribute. Comparing to the method used in VFDTc, it decreases fromO(nlogn) to O (n) in processing time. 3) Comparing to VFDTc, sVFDT‘zs candidate split-test number decrease fromO(n) to O(logn).4)Improve the soft discretization method to increase classification accuracy in data stream mining.