Data stream clustering

In computer science, data stream clustering is defined as the clustering of data that arrive continuously such as telephone records, multimedia data, financial transactions etc. Data stream clustering is usually studied as a streaming algorithm and the objective is, given a sequence of points, to construct a good clustering of the stream, using a small amount of memory and time.

History

Data stream clustering has recently attracted attention for emerging applications that involve large amounts of streaming data. For clustering, k-means is a widely used heuristic but alternate algorithms have also been developed such as k-medoids, CURE and the popular^{[citation needed]} BIRCH. For data streams, one of the first results appeared in 1980^[1] but the model was formalized in 1998.^[2]

Definition

The problem of data stream clustering is defined as:

Input: a sequence of n points in metric space and an integer k.
Output: k centers in the set of the n points so as to minimize the sum of distances from data points to their closest cluster centers.

This is the streaming version of the k-median problem.

Algorithms

STREAM

STREAM is an algorithm for clustering data streams described by Guha, Mishra, Motwani and O'Callaghan^[3] which achieves a constant factor approximation for the k-Median problem in a single pass and using small space.

Theorem— STREAM can solve the k-Median problem on a data stream in a single pass, with time O(n^1+e) and space θ(n^ε) up to a factor 2^O(1/e), where n the number of points and ⁠${\displaystyle e<1/2}$⁠.

To understand STREAM, the first step is to show that clustering can take place in small space (not caring about the number of passes). Small-Space is a divide-and-conquer algorithm that divides the data, S, into ${\displaystyle \ell }$ pieces, clusters each one of them (using k-means) and then clusters the centers obtained.

Small-Space Algorithm representation

Algorithm Small-Space(S)

1. Divide S into ${\displaystyle \ell }$ disjoint pieces ${\displaystyle X_{1},\ldots ,X_{\ell }}$.
2. For each i, find ⁠${\displaystyle O(k)}$⁠ centers in X_i. Assign each point in X_i to its closest center.
3. Let X' be the ${\displaystyle O(\ell k)}$ centers obtained in (2), where each center c is weighted by the number of points assigned to it.
4. Cluster X' to find k centers.

Where, if in Step 2 we run a bicriteria ⁠${\displaystyle (a,b)}$⁠-approximation algorithm which outputs at most ak medians with cost at most b times the optimum k-Median solution and in Step 4 we run a c-approximation algorithm then the approximation factor of Small-Space() algorithm is ⁠${\displaystyle 2c(1+2b)+2b}$⁠. We can also generalize Small-Space so that it recursively calls itself i times on a successively smaller set of weighted centers and achieves a constant factor approximation to the k-median problem.

The problem with the Small-Space is that the number of subsets ${\displaystyle \ell }$ that we partition S into is limited, since it has to store in memory the intermediate medians in X. So, if M is the size of memory, we need to partition S into ${\displaystyle \ell }$ subsets such that each subset fits in memory, (${\displaystyle n/\ell }$) and so that the weighted ${\displaystyle \ell k}$ centers also fit in memory, ${\displaystyle \ell k<M}$. But such an ${\displaystyle \ell }$ may not always exist.

The STREAM algorithm solves the problem of storing intermediate medians and achieves better running time and space requirements. The algorithm works as follows:^[3]

1. Input the first m points; using the randomized algorithm presented in^[3] reduce these to ⁠${\displaystyle O(k)}$⁠ (say 2k) points.
2. Repeat the above till we have seen m²/(2k) of the original data points. We now have m intermediate medians.
3. Using a local search algorithm, cluster these m first-level medians into 2k second-level medians and proceed.
4. In general, maintain at most m level-i medians, and, on seeing m, generate 2k level-i+ 1 medians, with the weight of a new median as the sum of the weights of the intermediate medians assigned to it.
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.^[4]

Key Challenges

1. 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.
2. 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.
3. 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.
4. 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 .
5. 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.
6. 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.
7. 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.
8. 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

Other well-known algorithms used for data stream clustering are:

• BIRCH:^[5] builds a hierarchical data structure to incrementally cluster the incoming points using the available memory and minimizing the amount of I/O required. The complexity of the algorithm is ⁠${\displaystyle O(N)}$⁠ since one pass suffices to get a good clustering (though, results can be improved by allowing several passes).
• COBWEB:^[6][7] is an incremental clustering technique that keeps a hierarchical clustering model in the form of a classification tree. For each new point COBWEB descends the tree, updates the nodes along the way and looks for the best node to put the point on (using a category utility function).
• C2ICM:^[8] builds a flat partitioning clustering structure by selecting some objects as cluster seeds/initiators and a non-seed is assigned to the seed that provides the highest coverage, addition of new objects can introduce new seeds and falsify some existing old seeds, during incremental clustering new objects and the members of the falsified clusters are assigned to one of the existing new/old seeds.
• CluStream:^[9] uses micro-clusters that are temporal extensions of BIRCH^[5] cluster feature vector, so that it can decide if a micro-cluster can be newly created, merged or forgotten based in the analysis of the squared and linear sum of the current micro-clusters data-points and timestamps, and then at any point in time one can generate macro-clusters by clustering these micro-clustering using an offline clustering algorithm like K-Means, thus producing a final clustering result.

References

1. Munro, J.; Paterson, M. (1980). "Selection and Sorting with Limited Storage". Theoretical Computer Science. 12 (3): 315–323. doi:10.1016/0304-3975(80)90061-4.
2. Henzinger, M.; Raghavan, P.; Rajagopalan, S. (August 1998). "Computing on Data Streams". Digital Equipment Corporation. TR-1998-011. CiteSeerX 10.1.1.19.9554.
3. Guha, S.; Mishra, N.; Motwani, R.; O'Callaghan, L. (2000). "Clustering data streams". Proceedings 41st Annual Symposium on Foundations of Computer Science. pp. 359–366. CiteSeerX 10.1.1.32.1927. doi:10.1109/SFCS.2000.892124. ISBN 0-7695-0850-2. S2CID 2767180.
4. Jain, K.; Vazirani, V. (1999). Primal-dual approximation algorithms for metric facility location and k-median problems. Focs '99. pp. 2–. ISBN 9780769504094. {{cite book}}: |journal= ignored (help)
5. Zhang, T.; Ramakrishnan, R.; Linvy, M. (1996). "BIRCH: An efficient data clustering method for very large databases". ACM SIGMOD Record. 25 (2): 103–114. doi:10.1145/235968.233324.
6. Fisher, D. H. (1987). "Knowledge Acquisition Via Incremental Conceptual Clustering". Machine Learning. 2 (2): 139–172. doi:10.1023/A:1022852608280.
7. Fisher, D. H. (1996). "Iterative Optimization and Simplification of Hierarchical Clusterings". Journal of AI Research. 4. arXiv:cs/9604103. Bibcode:1996cs........4103F. CiteSeerX 10.1.1.6.9914.
8. Can, F. (1993). "Incremental Clustering for Dynamic Information Processing". ACM Transactions on Information Systems. 11 (2): 143–164. doi:10.1145/130226.134466. S2CID 1691726.
9. Aggarwal, Charu C.; Yu, Philip S.; Han, Jiawei; Wang, Jianyong (2003). "A Framework for Clustering Evolving Data Streams" (PDF). Proceedings 2003 VLDB Conference: 81–92. doi:10.1016/B978-012722442-8/50016-1. ISBN 9780127224428. S2CID 2354576.