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 under the data stream model of computation 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 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 ${\displaystyle n}$  points in metric space and an integer ${\displaystyle k}$ .
Output: ${\displaystyle k}$  centers in the set of the ${\displaystyle n}$  points so as to minimize the sum of distances from data points to their closest cluster centers.

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 with time ${\displaystyle O(n^{1+\epsilon })}$  and space ${\displaystyle \theta (n^{\epsilon })}$  up to a factor ${\displaystyle 2^{O({1/\epsilon })}}$ , where ${\displaystyle n}$  the number of points and ${\displaystyle \epsilon <1/2}$ .

The first goal is to show that clustering can take place in small space (not caring about the number of passes). Small-Space^[4] is a divide-and-conquer algorithm that divides the data into pieces, clusters each one of them (using k-means) and then clusters the centers obtained (where each center is weighted by the number of points assigned to it).

Algorithm Small-Space(S)

1. Divide S into l disjoint pieces ${\displaystyle \chi _{1},\dots ,\chi _{l}}$ . 2. For each i, find O(k) centers in ${\displaystyle \chi _{i}}$ , using k-means. Assign each point in ${\displaystyle \chi _{i}}$  to its closest center. 3. Let ${\displaystyle \chi '}$  be the O(lk) centers obtained in (2), where each center c is weighted by the number of points assigned to it. 4. Cluster ${\displaystyle \chi '}$  to find k centers.

 

Small-Space Algorithm representation

The approximation factor of this algorithm is ${\displaystyle 2c(1+2b)+2b}$  and if we generalize it so that it recursively calls itself, ${\displaystyle i}$  times on a successively smaller set of weighted centers then it gives a constant factor approximation to the k-median problem, which, as expected, worsens with each successive reclustering.

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

• BIRCH
• COBWEB

References

<references>

1. J.Munro and M. Paterson. Selection and Sorting with Limited Storage. Theoretical Computer Science, pages 315-323, 1980
2. M. Henzinger, P. Raghavan, and S. Rajagopalan. Computing on Data Streams. Digital Equipment Corporation, TR-1998-011, August 1998.
3. S. Guha, N. Mishra, R. Motwani, L. O'Callaghan. Clustering Data Streams. Proceedings of the Annual Symposium on Foundations of Computer Science, 2000
4. S. Guha, N. Mishra, R. Motwani, L. O'Callaghan. Clustering Data Streams. Proceedings of the Annual Symposium on Foundations of Computer Science, 2000

Notes

http://www.cc.gatech.edu/projects/disl/Courses/cs4440/07Fall/project/proposals/Team5Proposal_final.pdf

http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5222900&isnumber=5222860&tag=1

http://www.springerlink.com/content/uc06wwfpc8wl04wf/fulltext.pdf

Requirements for Clustering Data Streams, Daniel Barbara

^[1]

1. S. Guha, A. Meyerson, N. Mishra, R. Motwani. Clustering Data Streams: Theory and Practice. IEEE Transactions on Knowledge and Data Engineering, Volume 15, Issue 3, 2003