Abstract
In an era of ubiquitous large-scale evolving data streams, data stream clustering (DSC) has received significant attention as the scale of data far exceeds human analytical capacity. High-dimensional data are typically distributed across a union of low-dimensional subspaces. This paper presents Evolutionary Dynamic Sparse Subspace Clustering (EDSSC), a novel algorithm designed to handle the time-varying nature of these subspaces, including emergence, disappearance, and recurrence. EDSSC operates in two phases: static learning and online clustering. It introduces a summary data structure to balance accuracy and efficiency, an automated method for estimating subspace numbers, and the Average Sparsity Concentration Index (ASCI) to improve clustering accuracy. Furthermore, a subspace evolution detection model based on the Page-Hinkley test allows the system to adapt to dynamic changes. Experimental results on real-world data streams demonstrate that EDSSC outperforms state-of-the-art online subspace clustering approaches.
Introduction
High-dimensional data streams—ranging from video surveillance feeds to financial transaction logs—are characterized by their massive volume and evolving nature. The "Subspace Clustering" hypothesis suggests that such data points do not fill the high-dimensional space uniformly but instead lie within a union of several low-dimensional subspaces. While static subspace clustering (SC) is well-studied, applying it to streaming data introduces significant challenges: subspaces are not fixed; they emerge, vanish, and reappear over time.
The Challenges of Evolving Streams
Most existing algorithms struggle with two primary issues in the streaming context:
- Subspace Evolution: Real-world data is dynamic. A new category of data might appear (emergence), an existing one might cease (disappearance), or a previously seen category might return (recurrence). Static models fail to adapt to these structural shifts.
- Efficiency-Accuracy Trade-off: Maintaining a high-fidelity map of subspaces requires storing many data points, which is computationally expensive for high-speed streams. Conversely, discarding too much data leads to poor clustering accuracy.
The EDSSC Framework
To address these challenges, the researchers proposed the EDSSC framework, which bifurcates the clustering process into a static initialization phase and a continuous online phase.
Phase 1: Static Learning and Initialization
In the first phase, the algorithm performs an initial analysis of a data batch. Unlike many methods that require a pre-defined number of clusters, EDSSC utilizes the eigenvalues of a Laplacian matrix to automatically estimate the number of underlying subspaces.
Central to this phase is the EDSSC Summary, a specialized data structure. It employs a logarithmic retention function to decide how many representative points to keep for each subspace. This ensures that as a cluster grows, the memory footprint increases only logarithmically, effectively balancing the need for accuracy with the constraints of stream processing.
Phase 2: Online Clustering and Evolution Detection
As new data points arrive, EDSSC performs real-time assignment and structural updates:
- Average Sparsity Concentration Index (ASCI): Traditional measures like the Sparsity Concentration Index (SCI) often fail when clusters are imbalanced (i.e., one subspace has significantly more points than another). ASCI normalizes the sparsity measure by the representation length, providing a robust metric for skewed data distributions.
- Evolution Detection via Page-Hinkley (PH) Test: To detect structural changes, EDSSC monitors the outlier rate using the PH test, a statistical method for identifying change points. If a sustained influx of outliers is detected, the system identifies the birth of a new subspace. Conversely, a "fading function" identifies and retires subspaces that have become inactive over time.
Experimental Results
EDSSC was evaluated against seven public datasets, including facial image sets (AR, ExYaleB) and handwritten character sets (MNIST, USPS).
Key findings include:
- Superior Accuracy: On the ExYaleB dataset, EDSSC achieved an accuracy of 75.01%, significantly higher than the 57.14% achieved by the next best baseline, OLRSC.
- Dynamic Adaptability: In large-scale tests using the MNIST 30K stream, EDSSC successfully tracked the number of active subspaces as they emerged and disappeared in real-time, whereas competing models like SSSC or CEDAS either remained static or could only detect emergence.
- Computational Efficiency: The algorithm maintains a space complexity of $O(d \log^2(n))$, ensuring it remains viable for high-speed data environments without sacrificing the depth of its subspace analysis.
Conclusion
EDSSC represents a significant advancement in data stream clustering by treating subspaces as dynamic, living entities. By combining a memory-efficient summary structure with robust sparsity metrics and statistical change detection, it provides a comprehensive solution for tracking evolving high-dimensional data. Future work will focus on refining the model to detect gradual "drifts" in subspaces and automating parameter tuning for different data environments.
Summary updated