Dynamic Sparse Subspace Clustering for Evolving High-Dimensional Data Streams

Jinping Sui, Zhen Liu, Li Liu, Alexander Jung, Xiang Li

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.

Illustration of (a) static subspace clustering and (b) dynamic subspace evolution in a data stream over time.

The Challenges of Evolving Streams

Most existing algorithms struggle with two primary issues in the streaming context:

  1. 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.
  2. 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.

The two-phase framework of EDSSC, distinguishing between initial static learning and continuous online clustering.

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

Abstract

In an era of ubiquitous large-scale evolving data streams, data stream clustering (DSC) has received lots of attention because the scale of the data streams far exceeds the ability of expert human analysts. It has been observed that high-dimensional data are usually distributed in a union of low-dimensional subspaces. In this article, we propose a novel sparse representation-based DSC algorithm, called evolutionary dynamic sparse subspace clustering (EDSSC). It can cope with the time-varying nature of subspaces underlying the evolving data streams, such as subspace emergence, disappearance, and recurrence. The proposed EDSSC consists of two phases: 1) static learning and 2) online clustering. During the first phase, a data structure for storing the statistic summary of data streams, called EDSSC summary, is proposed which can better address the dilemma between the two conflicting goals: 1) saving more points for accuracy of subspace clustering (SC) and 2) discarding more points for the efficiency of DSC. By further proposing an algorithm to estimate the subspace number, the proposed EDSSC does not need to know the number of subspaces. In the second phase, a more suitable index, called the average sparsity concentration index (ASCI), is proposed, which dramatically promotes the clustering accuracy compared to the conventionally utilized SCI index. In addition, the subspace evolution detection model based on the Page-Hinkley test is proposed where the appearing, disappearing, and recurring subspaces can be detected and adapted. Extinct experiments on real-world data streams show that the EDSSC outperforms the state-of-the-art online SC approaches.
BibTeX
@article{sui2020dynamic,
  author = {Jinping Sui and Zhen Liu and Li Liu and Alexander Jung and Xiang Li},
  title = {{Dynamic Sparse Subspace Clustering for Evolving High-Dimensional Data Streams}},
  journal = {IEEE Transactions on Cybernetics},
  year = {2020},
  doi = {10.1109/tcyb.2020.3023973},
}
Figure