An Innovative Framework for Static and Dynamic Clustering Using Histogram Models and Wasserstein Distance Over Sliding Windows

Xiaotong Qian, Guénaël Cabanès, Parisa Rastin, Mohamed Alae Guidani, Ghassen Marrakchi, Marianne Clausel, Nistor GrozavuSSRN 2023 · DOI

TL;DR

This paper introduces a novel framework for clustering large datasets and data streams by representing clusters as histograms and using the Wasserstein distance for comparison. This approach offers a flexible and efficient way to handle both static and dynamic clustering tasks, outperforming existing methods in speed and maintaining competitive quality.

What Problem Does This Paper Address?

Clustering is a fundamental task in data analysis, but traditional methods struggle with large datasets and continuous data streams due to memory constraints and the need for real-time processing. Existing data stream clustering algorithms often have limitations in handling arbitrary cluster shapes, require prior knowledge of the number of clusters, or are computationally expensive. This paper addresses the challenge of efficiently clustering large, dynamic datasets by proposing a framework that leverages histogram models for cluster representation and the Wasserstein distance for robust comparison and merging of clusters across sliding windows.

Methods

The core of the proposed framework lies in representing each cluster as a set of histograms. This allows for a flexible representation of arbitrary cluster distributions without making strong assumptions. To compare these histogram-based cluster representations, the authors employ the Wasserstein distance, which is known for its robustness to outliers and its metric properties.

The framework operates on sliding windows, processing data in batches. For each window, conventional clustering algorithms are applied to detect initial clusters. These clusters are then converted into histogram models. The key innovation is the use of the Wasserstein distance to compare histograms from the current window with those from previous windows. A statistical test based on the Wasserstein distance is used to determine if clusters are similar enough to be merged. Similar clusters are then merged by computing their barycentric histogram. This process is repeated for each sliding window, allowing for efficient processing of data streams and large datasets.

The framework also incorporates random projections to reduce the dimensionality of multivariate histograms, making the computation more efficient while preserving essential distributional information.

Datasets

The authors evaluated their framework on a variety of datasets, including:

  • Artificial Datasets: Comet, Meteorite, Square, Gaussian, Moon, and Circle distributions were generated to simulate various cluster shapes and complexities.
  • Real Datasets:
    • Outdoor
    • Gassenor
    • IGBN
    • IABN
    • Rialto
    • JIAIN
    • JIRIN
    • Covtype
    • INSECT datasets (IABN, IGBN, IIAIN, IIRIN)

Key Insights and Ideas

  • Histogram Representation for Flexibility: Using histograms to model cluster distributions offers a powerful way to handle arbitrary shapes without strong distributional assumptions, a significant advantage over methods relying on Gaussian or other specific distributions.
  • Wasserstein Distance for Robust Comparison: The Wasserstein distance proves to be a robust metric for comparing histogram-based distributions, effectively handling variations and outliers, which is crucial for effective cluster merging.
  • Sliding Window Efficiency: The sliding window approach allows the framework to process large datasets and data streams incrementally, significantly reducing memory requirements and enabling real-time analysis.
  • Algorithmic Flexibility: The framework's ability to integrate with various conventional clustering algorithms (e.g., KMeans, HDBSCAN, BIRCH) makes it highly adaptable to different data characteristics and user needs.
  • Dimensionality Reduction via Random Projections: Employing random projections is an effective strategy to manage the computational cost of multivariate histograms, making the approach scalable to high-dimensional data.

Key Results

The proposed framework demonstrated strong performance across various experiments:

  • Static Clustering: The framework achieved ARI and Purity scores comparable to or even better than traditional clustering algorithms applied to the entire dataset, while significantly reducing computation time. For instance, in some cases, computation time was reduced by orders of magnitude.
  • Dynamic Clustering: The framework, particularly with KMeans and HDBSCAN integration (HistStream(KMeans) and HistStream(HDBSCAN)), showed competitive clustering quality and significantly faster execution times compared to existing stream clustering algorithms like StreamKmeans, CluStream, and DenStream. HistStream(KMeans) was noted for its competitive performance and significantly faster running time.
  • Parameter Sensitivity: The quality of clustering was found to be relatively insensitive to the number of bins and projections, suggesting robustness. However, window size had a more pronounced impact, with a trade-off between quality and computation time.

Limitations and Future Work

  • Window Size Optimization: The authors acknowledge that clustering quality can degrade with very small window sizes, and the optimal window size varies across datasets. Future work will focus on automatically determining the optimal number of samples per window to achieve the best trade-off between quality and speed.
  • Robustness to Noise: While the Wasserstein distance is robust to outliers, further research could explore more robust clustering results, especially in highly noisy environments.
  • Automatic Parameter Tuning: While the framework shows flexibility, further research could explore more automated ways to tune parameters like the number of bins and projections for optimal performance across diverse datasets.

Summary updated

BibTeX
@misc{qian2023innovative,
  author = {Xiaotong Qian and Guénaël Cabanès and Parisa Rastin and Mohamed Alae Guidani and Ghassen Marrakchi and Marianne Clausel and Nistor Grozavu},
  title = {{An Innovative Framework for Static and Dynamic Clustering Using Histogram Models and Wasserstein Distance Over Sliding Windows}},
  year = {2023},
  doi = {10.2139/ssrn.4573414},
  howpublished = {SSRN},
}
Figure