A Clustering-based framework for Classifying Data Streams

Xuyang Yan, Abdollah Homaifar, Mrinmoy Sarkar, Abenezer Girma, Edward W. TunstelIJCAI 2021 · DOI

TL;DR

This paper introduces CDSC-AL, a novel clustering-based framework for classifying data streams that are constantly changing (non-stationary). It tackles the challenges of concept drift, new class emergence, and class overlap without requiring an initial labeled dataset, using an active learning strategy to efficiently acquire labels.

What Problem Does This Paper Address?

The world is awash in data streams – continuous flows of information from sources like sensors, financial markets, and social media. Traditional machine learning models struggle with these streams because the underlying patterns (concepts) can change over time (concept drift) or new patterns can emerge. This non-stationarity, along with the difficulty and cost of obtaining labels for every data point, makes classifying these streams a significant challenge. Existing methods often rely on pre-existing labeled data, struggle with overlapping classes, or require extensive parameter tuning. This paper aims to provide a robust, semi-supervised solution that can adapt to these evolving data streams efficiently and effectively.

Methods

The core of the CDSC-AL framework lies in its three main components:

  • Concept Drift and Evolution Detection through Clustering: The authors adapt a density-based stream clustering algorithm (DFPS-clustering) to identify changes. A novel cluster merge procedure is introduced to distinguish between "drifted" concepts (existing clusters that have changed) and "novel" concepts (entirely new clusters). A dynamic density threshold, based on the mean and standard deviation of historical cluster densities, is used to validate the emergence of these novel clusters.
  • Adaptation of Drifted and Novel Concepts using Active Learning: To manage the cost of labeling, CDSC-AL employs an active learning strategy. It maintains two levels of summary for the data stream: a macro-level summary (GSt) and a micro-level summary (LSt). The micro-level summary is crucial for handling class overlap by creating sub-clusters, each representing a single class. The active learning strategy uses a hybrid approach, combining "informative-based" sampling (selecting samples that are uncertain or far from existing clusters) and "representative-based" sampling (selecting samples that best represent novel concepts) to query labels from human experts.
  • Classification through Label Propagation: Once a small set of labels is acquired through active learning, a label propagation mechanism is used to classify the remaining unlabeled data in the current chunk. This is achieved by using a k-nearest-neighbor (KNN) rule, leveraging the prototypes (representative samples) from the learned cluster summaries and the newly labeled samples.

Datasets

The paper evaluates CDSC-AL on nine benchmark datasets:

  • Synthetic Datasets: Syn-1, Syn-2, Sea
  • Real-world Datasets: KDD99, Forest, GasSensor, Shuttle, MNIST, CIFAR10

These datasets vary in size, dimensionality, number of classes, and importantly, the degree of class overlap. Some datasets are specifically arranged to simulate abrupt concept drifts, while others simulate gradual drifts.

Key Insights and Ideas

  • No Initial Labels Needed: A significant advantage is the framework's ability to start learning without any pre-existing labeled data, making it practical for real-world scenarios where labeling is a bottleneck.
  • Dynamic Concept Detection: The use of a dynamic density threshold for novel cluster detection is a clever way to adapt to the changing nature of data streams, rather than relying on fixed parameters.
  • Handling Class Overlap: The introduction of sub-clusters within the micro-level summary is a key innovation for dealing with overlapping classes, a common and difficult problem in stream classification.
  • Efficient Label Acquisition: The hybrid active learning strategy strikes a good balance between exploring new concepts and refining existing ones, minimizing the number of labels required.

Key Results

CDSC-AL demonstrates strong performance across various datasets:

  • Semi-supervised Comparison: CDSC-AL consistently outperforms or performs comparably to existing semi-supervised methods like OReSSL and LNP in terms of balanced classification accuracy (BA) and macro-average F-score (Fmac). Statistical tests confirm significant improvements over LNP.
  • Supervised Comparison: Even when using only 10% of the available labels, CDSC-AL achieves the best performance on six out of nine benchmark datasets, outperforming supervised methods like Leverage Bagging, OBA, AHT, and SAMKNN. It shows statistically comparable performance to some supervised methods on the remaining datasets.
  • Robustness: The framework shows good performance even on datasets with abrupt concept drifts and high class overlap.

Limitations and Future Work

The authors acknowledge that while CDSC-AL performs well, future work could focus on:

  • Reducing Time Complexity: The current time complexity involves quadratic distance calculations for density evaluation. Further optimizations could be explored.
  • Real-world Applications: The authors plan to investigate the application of CDSC-AL to real-world problems such as text and image stream classification.

Summary updated

BibTeX
@inproceedings{yan2021clustering,
  author = {Xuyang Yan and Abdollah Homaifar and Mrinmoy Sarkar and Abenezer Girma and Edward W. Tunstel},
  title = {{A Clustering-based framework for Classifying Data Streams}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/448},
}
Figure