|
|5 = When we have seen all the original data points, we cluster all the intermediate medians into ''k'' final medians, using the primal dual algorithm.<ref>{{cite book | first1 = K. | last1 = Jain | first2 = V. | last2 = Vazirani | url = http://portal.acm.org/citation.cfm?id=796509 | title = Primal-dual approximation algorithms for metric facility ___location and k-median problems | journal = Proc. FOCS | pages = 2– | date = 1999 | isbn = 9780769504094 | series = Focs '99 }}</ref>
}}
== Key Challenges ==
# '''Unbounded and Continuous Data''' One of the fundamental challenges of data stream clustering is the infinite nature of data streams. Unlike traditional datasets, a data stream may never end, making it impossible to store all the data for retrospective analysis. Algorithms must therefore operate in one-pass or limited-pass modes, summarizing or discarding data after processing to maintain efficiency.
# '''Real-Time Constraints and Low Latency''' Clustering algorithms for data streams must provide results with minimal delay. Applications such as fraud detection or traffic analysis demand real-time responsiveness, meaning that incoming data must be processed as soon as it arrives. This necessitates the use of lightweight, low-complexity algorithms capable of producing immediate outputs.
# '''Memory Limitations''' With data continuously arriving at high speeds, memory resources are quickly overwhelmed if not carefully managed. Effective data stream clustering requires memory-efficient techniques, such as micro-clustering (summarizing clusters into compact representations), reservoir sampling, or data sketching, which help maintain performance without retaining the full dataset.
# '''Concept Drift''' Data streams often exhibit concept drift, where the underlying data distribution changes over time. This is common in applications such as e-commerce or environmental monitoring, where user behavior or sensor readings evolve. Clustering algorithms must be capable of adapting dynamically to such changes, typically through window-based processing or fading mechanisms that de-emphasize older data .
# '''Noise and Outliers''' Streaming data is frequently noisy and may contain anomalies, missing values, or outliers. Robust clustering methods must differentiate between genuine shifts in data patterns and transient noise, often using density-based or probabilistic approaches that can absorb minor fluctuations without destabilizing clusters.
# '''Determining the Number of Clusters''' Traditional clustering algorithms like k-means require the number of clusters (k) to be known in advance. In the streaming context, this is often unknown or variable, as new patterns may emerge and old ones disappear over time. Data stream clustering methods must either estimate k automatically or allow clusters to grow, merge, or dissolve dynamically.
# '''High Dimensionality''' Many data streams involve high-dimensional data, such as network traffic logs, IoT sensor data, or user interaction traces. In high-dimensional spaces, the notion of distance becomes less meaningful—a phenomenon known as the curse of dimensionality—making many traditional clustering techniques ineffective. Techniques such as dimensionality reduction, feature selection, or subspace clustering are often used in conjunction to mitigate this issue.
# '''Evaluation Challenges''' Measuring the effectiveness of clustering in a data stream setting is particularly difficult due to the lack of ground truth and the temporal evolution of data. Evaluation metrics must often be computed over summarized representations or fixed time windows, using internal criteria like silhouette score or external criteria when labeled data is intermittently available.
=== Other algorithms ===
| 