Concept Drift Detection: Dealing With Missing Values via Fuzzy Distance Estimations

Anjin Liu, Jie Lu, Guangquan Zhang

TL;DR

This paper introduces MDL-FWF, a novel approach to concept drift detection in data streams that explicitly handles missing values. Instead of imputing missing values and then detecting drift, MDL-FWF estimates distances between observations directly, using fuzzy logic to account for uncertainty, leading to significantly improved drift detection accuracy.

What Problem Does This Paper Address?

Data streams, where observations arrive sequentially, often exhibit "concept drift" – changes in the underlying data distribution over time. Detecting this drift is crucial for maintaining the performance of machine learning models. A significant challenge in this domain is the presence of missing values in the data. While imputation methods exist to fill these gaps, the authors argue that these methods can actually increase uncertainty and introduce bias, negatively impacting drift detection. Existing drift detection methods often ignore missing values or rely on separate imputation steps, which the authors believe is suboptimal. They aim to develop a unified approach that directly addresses missing values within the drift detection framework.

Methods

The proposed solution, MDL-FWF, consists of two main components:

  • Masked Distance Learning (MDL): This novel algorithm focuses on estimating the distance between observations rather than imputing individual missing values. It works by:
  • Masking: Creating a "masked" version of observations that originally had no missing values by artificially introducing nulls.
  • Learning: Training a regression model (specifically, a gradient boosted decision tree) to predict the actual pairwise distances from these masked observations. This approach aims to preserve data variance and minimize prediction errors.
  • Error Estimation: Estimating the error of the distance predictions, which is crucial for the next step.
  • Fuzzy-Weighted Frequency (FWF): This component uses the estimated distances and their associated errors from MDL to build a more robust representation of data distribution.
  • Fuzzification: The predicted distances are treated as fuzzy numbers (e.g., Triangular Fuzzy Numbers or Gaussian Fuzzy Numbers) to represent the uncertainty introduced by missing values.
  • Membership Degree: Observations are assigned a degree of membership to histogram bins (clusters) based on these fuzzy distances.
  • Weighted Frequency: These membership degrees are used as weights to calculate the frequency of observations in each bin. This fuzzy weighting accounts for estimation errors.
  • Drift Detection: A standard Pearson's chi-square test is then applied to the fuzzy-weighted frequencies to detect concept drift.

The authors also introduce a "Top-Q cluster constraint" to manage potential overestimation of weights in certain scenarios.

Datasets

The paper evaluates MDL-FWF using a combination of synthetic and real-world datasets:

  • Synthetic Datasets: Five types of distributions (Uniform, Gaussian, Exponential, Poisson, Categorical) were used, with missing values introduced in various configurations (MCAR). These datasets were generated to evaluate both distance estimation and drift detection performance.
  • Real-World Datasets:
    • HIGGS Bosons and Background Data Set: Used to distinguish Higgs boson particles from background processes.
  • Arabic Digit Mixture Data Set: Contains audio features for pronouncing Arabic digits.
  • Insects Mixture Data Set: Features from a laser sensor to distinguish flying insects.

These real-world datasets were augmented with synthetic drifts to simulate concept drift scenarios.

Key Insights and Ideas

  • Imputation is Not Always the Answer: The paper strongly suggests that traditional imputation methods, while seemingly intuitive, can actually degrade concept drift detection performance by introducing bias and masking true data variability.
  • Focus on Distance, Not Values: Shifting the focus from imputing individual missing values to estimating the distances between observations is a key innovation. This preserves more information about the data's structure.
  • Fuzzy Logic for Uncertainty: Fuzzy set theory is a powerful tool for modeling the inherent uncertainty introduced by missing values. By fuzzifying distances and using fuzzy membership, the algorithm becomes more robust.
  • Task-Oriented Approach: The proposed method is "task-oriented" because it directly optimizes for the statistics needed for drift detection (distances) rather than trying to perfectly reconstruct the missing values themselves.

Key Results

  • Significant Improvement in Drift Detection: MDL-FWF reduced the average drift detection difference from 10.75% to 5.83% compared to the best-performing separate imputation and drift detection approach, representing a nearly 46% improvement.
  • Robustness to Missing Values: Experiments showed that MDL-FWF maintained good performance even with significant amounts of missing data, outperforming other methods that relied on imputation.
  • Distance Estimation Accuracy: The masked distance learning component demonstrated lower RMSE and MAE compared to traditional imputation methods for distance estimation.
  • Ablation Study Findings: The fuzzy-weighted frequency component was shown to be crucial for improving performance over just using masked distance learning. The "Top-Q cluster constraint" also helped manage performance in certain scenarios.
  • Real-World Performance: MDL-FWF showed promising results on real-world datasets, demonstrating its practical applicability.

Limitations and Future Work

  • Computational Complexity: The paper acknowledges that concatenating observations horizontally to create features for MDL doubles the dimensionality, potentially increasing computation costs for high-dimensional data.
  • Dimensionality Reduction: The authors suggest exploring dimensionality reduction techniques as a future direction to mitigate the computational burden.
  • Extreme Missingness: While the method handles missing values well, the paper notes that further exploration is needed for scenarios with extremely high rates of missing data.
  • Generalization of Fuzzy Distance: The paper mentions that the current fuzzy-distance estimation is "shallow" and suggests exploring more advanced distribution estimation techniques based on uncertainty.

Summary updated

Abstract

In data streams, the data distribution of arriving observations at different time points may change—a phenomenon called concept drift. While detecting concept drift is a relatively mature area of study, solutions to the uncertainty introduced by observations with missing values have only been studied in isolation. No one has yet explored whether or how these solutions might impact drift detection performance. We, however, believe that data imputation methods may actually increase uncertainty in the data rather than reducing it. We also conjecture that imputation can introduce bias into the process of estimating distribution changes during drift detection, which can make it more difficult to train a learning model. Our idea is to focus on estimating the distance between observations rather than estimating the missing values, and to define membership functions that allocate observations to histogram bins according to the estimation errors. Our solution comprises a novel masked distance learning (MDL) algorithm to reduce the cumulative errors caused by iteratively estimating each missing value in an observation and a fuzzy-weighted frequency (FWF) method for identifying discrepancies in the data distribution. The concept drift detection algorithm proposed in this article is a singular and unified algorithm that can handle missing values, but not an imputation algorithm combined with a concept drift detection algorithm. Experiments on both synthetic and real-world datasets demonstrate the advantages of this method and show its robustness in detecting drift in data with missing values. The results show that compared to the best-performing algorithm that handles imputation and drift detection separately, MDL-FWF reduced the average drift detection difference from 10.75% to 5.83%. This is a nearly 46% improvement. These findings reveal that missing values exert a profound impact on concept drift detection, but using fuzzy set theory to model observations can produce more reliable results than imputation.
BibTeX
@article{liu2021concept,
  author = {Anjin Liu and Jie Lu and Guangquan Zhang},
  title = {{Concept Drift Detection: Dealing With Missing Values via Fuzzy Distance Estimations}},
  journal = {IEEE Trans. Fuzzy Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=8WtCB4lK3x},
}
Figure