SKIF: A Data Imputation Framework for Concept Drifting Data Streams

摘要

Missing data commonly occur in many applications. While many data imputation methods exist to handle the missing data problem for databases, when applied to concept drifting data streams, these methods share some common difficulties. First, due to large and continuous data volumes, we are unable to maintain all stream records to form a candidate pool for missing value estimation, as most existing methods commonly do. Second, even if we could maintain all complete stream records using a summary structure, the concept drifting problem would make some information obsolete, and thus deteriorate the imputation accuracy. Third, in data streams, it is necessary to develop a fast yet accurate algorithm to find most similar data for imputation. Fourth, due to dynamic and sophisticated data collection environments, the missing rate of most stream data may be much higher than that in databases, so the imputation method should be able to handle high missing rate in the data. To tackle these challenges, we propose a Streaming k-Nearest-Neighbors Imputation Framework (SKIF) for concept drifting data streams. To handle concept drifting and large volume problems in data streams, SKIF first summarizes historical complete records in some micro-resources (which are high-level statistical data structures), and maintains these micro-resources in a candidate pool as benchmark data. After that, SKIF employs a novel hybrid-kNN imputation procedure, which uses a hybrid similarity search mechanism, to find the most similar micro-resources from the large scale candidate pool efficiently. Experimental results demonstrate the effectiveness of the proposed SKIF framework for data stream imputation tasks.