Adaptive Leverage-Score Sketching and Sparse Random Projections for Scalable Streaming Clustering with Concept x Drift

Abstract

Clustering in high-dimensional streaming data is formidable due to concept drift, changing data distributions, and computational limitations. This work proposes an adaptive sketching method aimed to clustering these highly-dimensional data streams, which can simultaneously handle both scalability and concept drift. The framework combines leverage-score sampling, sparse random projections, adaptive rank selection, and online micro-clustering in a common incremental architecture. Updating the sketch representation benefits from an online learning process based on a reconstruction-error monitoring mechanism that dynamically adjusts the sketch representation in parallel to the changes in the underlying data distribution without the need for recomputing the entire sketch. Experimental results on three benchmark datasets (CoverType, ELEC, and Twitter) show that the proposed framework provides superior performance compared to state-of-the-art streaming clustering methods. It achieved ARI/NMI scores of 0.68/0.61 on CoverType, 0.72/0.65 on ELEC, and 0.39/0.42 on Twitter, surpassing CluStream, DenStream, StreamKM++, and LEMON. Moreover, the ablation study verifies the benefit of the proposed design, where the framework with full design achieves 0.68 in ARI, and that without adaptive rank selection shows 0.54 in ARI, suggesting that adaptive rank selection is a key for clustering performance. The detailed experiments demonstrate that the elaborated framework achieves optimal balance among clustering performance, adaptability and efficient computational cost, making it suitable for real-world applications such as IoT analytics, financial monitoring and online anomaly detection.