Source-linked AI summary
Data Stream Clustering: A Review
Alaettin Zubaroğlu, Volkan Atalay
TL;DR
Data stream clustering must analyze rapidly arriving, evolving data without complete storage or reliable labels. The paper surveys stream-clustering concepts and recent algorithms, comparing their techniques, complexity, accuracy, and practical boundaries. It reports algorithm-specific improvements over baselines while identifying unresolved parameter, benchmark, and comparison-environment problems.
Problem
Rapidly generated streams differ from traditional data because they evolve, cannot be fully stored, and often lack labels or known class counts.
Method
The paper surveys stream-clustering concepts and seven recent algorithms, analyzing their techniques, computational complexity, accuracy, comparisons, datasets, and tools.
Results
The reviewed algorithms show reported improvements ranging from 2% to 7% over DenStream for one improved method and 13% to 40% over CluStream for adaptive streaming k-means.
Takeaways & Limitations
The review identifies unresolved needs for parameter selection, suitable benchmark data, and an experimental comparison environment for data stream clustering.
Takeaways & Limitations
The comparison is scoped to central data stream clustering on a single center, excluding edge computing.
Abstract
from arXiv · showhide
Number of connected devices is steadily increasing and these devices continuously generate data streams. Real-time processing of data streams is arousing interest despite many challenges. Clustering is one of the most suitable methods for real-time data stream processing, because it can be applied with less prior information about the data and it does not need labeled instances. However, data stream clustering differs from traditional clustering in many aspects and it has several challenging issues. Here, we provide information regarding the concepts and common characteristics of data streams, such as concept drift, data structures for data streams, time window models and outlier detection. We comprehensively review recent data stream clustering algorithms and analyze them in terms of the base clustering technique, computational complexity and clustering accuracy. A comparison of these algorithms is given along with still open problems. We indicate popular data stream repositories and datasets, stream processing tools and platforms. Open problems about data stream clustering are also discussed.
1 Introduction
Data stream clustering addresses continuously generated, potentially unbounded data when labels and class counts are unavailable. Unlike traditional clustering, it must process ordered instances quickly, retain only summaries, handle evolving data and ambiguous outliers, and is reviewed here through mechanisms, algorithms, comparisons, and open issues.
- Data streams are potentially unbounded ordered sequences whose instances often lack labels and a known class count, making unsupervised clustering suitable.
- Unlike traditional clustering, stream instances arrive once and in order, require rapid processing, and cannot generally be stored beyond a synopsis.
- Concept drift changes input properties over time, so stream clustering algorithms should detect and adapt to it for more accurate results.
- Outlier detection is difficult because a dissimilar instance may indicate a new cluster or concept drift rather than an anomaly.
- Algorithms summarize incoming data online in specialized structures, then periodically or on request perform final clustering over that synopsis.
- The review examines mechanisms, seven recent algorithms, comparative advantages and disadvantages, and stream datasets, tools, and platforms.
2 Concepts in Data Stream Clustering
The paper organizes stream-clustering concepts around drift, summaries, windows, and outliers. It describes four drift types, three window models, and several outlier-detection families with different assumptions, suitability, and computational costs.
- Concept Drift: Concept drift is an unforeseen change in stream statistics, occurring as sudden, gradual, incremental, or recurring change.
- Data Structures: Because streams cannot be fully stored, feature vectors, prototype arrays, coreset trees, and grids provide incremental summaries of incoming data.
- Time Window Models: Damped windows weight recent instances more heavily, landmark windows partition nonoverlapping intervals equally, and sliding windows replace one instance at each step.
- Outlier Detection: Nonparametric statistical, distance-based, density-based, and clustering-based methods offer alternative ways to identify stream outliers.
- Outlier Detection: Distance-based detection avoids distribution assumptions but is ineffective for high-dimensional streams, whereas density-based methods are more effective but computationally more complex.
3 Stream Clustering Algorithms
The review organizes stream-clustering algorithms by clustering technique and examines their complexity, capabilities, limitations, and evaluation results. Across the reviewed methods, performance depends on data characteristics, parameter choices, and the ability to handle drift, noise, dimensionality, and cluster shape.
- Adaptive Streaming k-Means: Adaptive streaming k-means improves silhouette quality over CluStream by 13%–40% and over DenStream by up to 280% on artificial streams with concept drift.On real traffic data, its improvement reaches 31% over one day and averages 12% over one week against a non-adaptive technique.
- FEAC-Stream: FEAC-Stream achieves similar clustering quality to competing k-estimation methods while reducing execution time by up to nearly 93%.Mean ARI values are 0.97–0.99, and intrusion-detection SS values are 0.90–0.92 across the compared methods.
- MuDi-Stream: MuDi-Stream outperforms DenStream by 10%–100% in clustering quality across streams involving concept drift and multiple densities.It supports arbitrary-shaped, multi-density clusters, but its quality depends strongly on density threshold, decay rate, and grid granularity.
- CEDAS: CEDAS remains nearly constant in processing time up to 10,000 dimensions, while CluStream and DenStream become substantially more expensive at high dimensionality.At 6,000 dimensions, CluStream consumes nearly 300 times more than CEDAS and DenStream nearly two times more.
- Improved Data Stream Clustering Algorithm: The improved data stream clustering algorithm automatically adjusts thresholds, removes the need for expert parameter knowledge, and improves clustering quality over DenStream by 2%–7%.Its evaluation uses the network intrusion detection dataset; claimed complexity advantages lack measurement results.
4 Comparison of the Algorithms
The review compares recent data stream clustering algorithms by operating mode, window model, cluster structure, outlier handling, and parameter requirements, exposing distinct capabilities and limitations.
- Common characteristics: All seven reviewed algorithms estimate the number of clusters and adapt to concept drift, while MuDi-Stream is the exception for high-dimensional data.MuDi-Stream’s grid-based outlier detection becomes slower as dimensionality increases because empty grids multiply.
- Cluster structure: Density-based algorithms generally find arbitrary-shaped clusters, while partitioning and distance-based methods are limited to hyper-spherical clusters.MuDi-Stream and I-HASTREAM adapt density thresholds per cluster, enabling multi-density clustering; DBIECM remains limited for different cluster sizes.
- Processing mode: CEDAS, Adaptive Streaming k-means, FEAC-Stream, and DBIECM are fully online, whereas MuDi-Stream, Improved Data Stream Clustering, and I-HASTREAM use online-offline processing.Online-offline methods can produce final clusters with latency because their offline phase runs periodically or on request.
- Time windows: Damped windows are most common; Adaptive Streaming k-means uses a sliding window, while DBIECM uses no time window model.
- Limitations: Adaptive Streaming k-means, FEAC-Stream, and DBIECM support only hyper-spherical clusters, while MuDi-Stream, CEDAS, and DBIECM additionally require expert input for successful parameter selection.The review also notes that MuDi-Stream, CEDAS, and DBIECM are highly sensitive to threshold values affecting cluster counts and quality.
5 Open Problems
The review identifies unresolved problems in automatically adapting stream clustering to changing cluster structure, evaluating it consistently, and benchmarking it with suitable data and environments.
- Finding k and parameter requirements: Finding a cluster count and parameters that adapt quickly to concept drift remains an open problem, especially when densities, sizes, and shapes change.Current methods require values such as k, density or distance thresholds, decay rates, and window lengths that can be sensitive to input data.
- Evaluation Criteria: No de facto evaluation criterion exists for data stream clustering, motivating metrics designed specifically for streaming results.
- Benchmark Data and Experimental Comparison Environment: Benchmarking is hindered by a lack of high-quality stream data containing concept drift, outliers, and class labels, plus the absence of a common comparison environment.The proposed environment would feed multiple algorithms identically and compare execution performance and clustering quality.
- Different Data Types: Most algorithms focus on quantitative features and Euclidean similarity, leaving categorical-data clustering comparatively underdeveloped.Existing practice commonly converts categorical features into quantitative representations before applying current algorithms.
- Performance Improvements: The study notes that increasing connected-device data requires continued performance improvement, but its review focuses on single-processor processing rather than parallel or edge execution.
6.1 Data Repositories
The review surveys public and real-time sources that can support data stream clustering, including repositories, frameworks, APIs, and live civic or social streams.
- Real-time sources: Real-time sources include Citi Bike system and trip data, Meetup RSVP responses, and National Weather Service alerts.These sources expose operational, event-response, or alert streams suitable for clustering studies.
- Repositories and frameworks: MOA is a popular open-source stream-mining framework containing suitable datasets and classes for generating artificial streams.
- Additional sources: Additional repositories and feeds include New York City Open Data, AWS Open Data, Twitter, AirNow, wind, solar-radiation, and broader public-dataset collections.
6.2 Popular Datasets
The review describes artificial and traditional datasets used for stream-clustering benchmarks, while emphasizing that many traditional datasets lack native stream ordering or timing.
- Artificial datasets: Artificial streams let researchers control noise, concept drift, cluster shapes, and densities, and MOA supplies generators for varied stream conditions.Most datasets mentioned in this section have true class labels, except the Charitable Donation Dataset.
- Traditional datasets: The Forest Cover Type dataset contains 581,012 instances, 54 features, and 7 cover types, but is stationary and lacks timestamps or exclusive ordering.
- Traditional datasets: The Network Intrusion Detection dataset contains 4,898,431 records, 41 features, and 23 connection types, including attacks and normal traffic.
- Other datasets: Charitable Donation, spam-mail, and sensor-network datasets are also identified as stream-clustering sources, with temporal or inherently streaming characteristics for the latter two.The donation dataset has 191,779 instances and 481 features.
7 Data Stream Processing Tools
The review surveys tools for data stream mining, including specialized frameworks, general data-mining environments, and R-based packages for stream analysis.
- 7 Data Stream Processing Tools: MOA is an open-source Java framework specialized for data streams, covering clustering, classification, regression, outlier and concept-drift detection, recommender systems, evaluation, and stream generation.It can serve both as a stream-processing tool and an environment for evaluating stream-mining algorithms.
- 7 Data Stream Processing Tools: RapidMiner supports stream-oriented processing through its Streams plugin within an integrated environment for data preparation, visualization, validation, and optimization.
- 7 Data Stream Processing Tools: R provides open-source statistical-computing packages for clustering, data streams, stream mining, and interfaces to MOA-based algorithms.The listed packages include stream, rstream, streamMOA, and RMOA.
8 Data Stream Processing Platforms
The review lists distributed, cloud, enterprise, and general-purpose platforms for ingesting, processing, and analyzing real-time data streams with varying scalability, latency, and fault-tolerance features.
- 8 Data Stream Processing Platforms: The surveyed platforms were developed by different organizations and include open-source, commercial, cloud-based, and distributed systems.
- 8 Data Stream Processing Platforms: Apache Storm, Spark Streaming, Samza, Kafka, and Kinesis provide distributed or scalable real-time stream processing, with features including fault tolerance, batching, messaging, and support for large data streams.Spark Streaming batches live streams for Apache Spark, while Kafka provides a high-throughput, low-latency publish-subscribe platform.
- 8 Data Stream Processing Platforms: IBM Infosphere is an enterprise stream-processing platform using time windows from minutes to hours for low-latency applications such as fraud detection and network management.It also supports stream fusion, changing data forms and types, and high availability.
- 8 Data Stream Processing Platforms: Google Cloud Stream and Microsoft Azure Stream Analytics offer managed or serverless real-time processing integrated with their respective cloud ecosystems.Azure supports multiple input streams and a declarative SQL-like language.
9 Conclusions
The paper surveys data stream clustering and its supporting ecosystem, while identifying unresolved needs for adaptive, broadly applicable, and systematically benchmarked algorithms.
- 9 Conclusions: Real-time clustering is increasingly relevant because interconnected devices generate large-scale, high-speed data streams.
- 9 Conclusions: The survey reviews recent algorithms, stream-clustering concepts, datasets, tools, platforms, algorithmic complexity, evaluations, and comparative advantages and disadvantages.
- 9 Conclusions: Open challenges include discovering and adapting the number of clusters, reducing dependence on critical parameters, handling concept drift, supporting diverse data types, and maintaining performance under memory restrictions.The paper specifically notes that many existing algorithms handle only quantitative data.
- 9 Conclusions: Future work should compare algorithms under controlled benchmarks containing concept drift, outliers, class labels, and real datasets, while exploring deep neural networks and edge computing.