Class Specific Fuzzy Decision Trees for Mining High Speed Data Streams

Abstract

In recent years, classification learning for data streams has become an important and active research topic. A major challenge posed by data streams is that their underlying concepts can change over time, which requires current classifiers to be revised accordingly and timely. To detect concept change, a common method is to observe the online classification accuracy. If accuracy drops below some threshold value, a concept change is deemed to have taken place. An implicit assumption behind this methodology is that any drop in accuracy can be interpreted as a symptom of concept change. Unfortunately however, this assumption is often violated in the real world where data streams carry noise and missing values that can also introduce a significant reduction in classification accuracy. To compound this problem, traditional noise cleansing methods are not applicable to data streams. These methods normally need to scan data multiple times whereas learning in data streams can only afford one-pass scan because of data's high speed and huge volume. To solve these problems, this paper proposes a novel classification algorithm, Class Specific Fuzzy Decision Trees (CSFDT), which utilizes fuzzy logic to classify data streams. The base classifier of CSFDT is a binary fuzzy decision tree. Whenever the problem of concern contains q classes (q > 2), CSFDT learns one binary classifier for each class to distinguish instances of this class from instances of the remaining (q − 1) classes. The CSFDT's advantages are three folds. First, it offers an adaptive structure to effectively and efficiently handle concept change. Second, it is robust to noise. Third, it deals with missing values in an elegant way. As a result, accuracy drop can be safely attributed to concept change. Extensive evaluations are conducted to compare CSFDT with representative existing data stream classification algorithms on a large variety of data. Experimental results suggest that CSFDT provides a significant benefit to data stream classification in real-world scenarios where concept changes, noise and missing values coexist.