Data stream clustering: Difference between revisions

Revision as of 01:11, 5 February 2010

Revision as of 20:17, 5 February 2010

Line 20:

STREAM is an algorithm for clustering data streams described by Guha, Mishra, Motwani and O'Callaghan <ref>S. Guha, N. Mishra, R. Motwani, L. O'Callaghan. [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.1927 Clustering Data Streams]. Proceedings of the Annual Symposium on Foundations of Computer Science, 2000</ref> 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 <math>O(n^{<sup>1+\epsilon })e</mathsup>) and space <math>\thetaθ(n^{\epsilon})<sup>ε</mathsup>) up to a factor 2<mathsup>2^{O({1/ \epsilon}e)}</mathsup>, where <math>n</math> the number of points and e<math>\epsilon < 1/2</math>''.

The first goal is to show that clustering can take place in small space (not caring about the number of passes). Small-Space<ref>S. Guha, N. Mishra, R. Motwani, L. O'Callaghan. [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.1927 Clustering Data Streams]. Proceedings of the Annual Symposium on Foundations of Computer Science, 2000</ref> 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).

[[File:Small-Space.jpg | thumb | 500x230px440x140px | centerright | Small-Space Algorithm representation]]

<blockquote>

Algorithm Small-Space(S)

1. Divide ''S'' into ''l'' disjoint pieces <math>\chi_1, \dots, \chi_l</math>.

'''Algorithm Small-Space(S)'''

2. For each ''i'', find ''O(k)'' centers in <math>\chi_i</math>, using ''k''-means. Assign

each point in <math>\chi_i</math> to its closest center.

<ol>

3. Let <math>\chi'</math> be the ''O(lk)'' centers obtained in (2),

1.<li> Divide ''S'' into ''l'' disjoint pieces ''χ<mathsub>1</sub>\chi_1, \dots..., \chi_lχ<sub>l</mathsub>''.</li>

2.<li> For each ''i'', find ''O(k)'' centers in ''χ<mathsub>\chi_ii</mathsub>'', using ''k''-means. Assign

each point in ''χ<mathsub>\chi_ii</mathsub>'' to its closest center.</li>

3.<li> Let <math>\chi'</math>'χ''' be the ''O(lk)'' centers obtained in (2),

where each center ''c'' is weighted by the number

of points assigned to it.</li>

4.<li> Cluster <math>\chi'</math>'χ''' to find ''k'' centers.</li>

</blockquoteol>

<br />

[[File:Small-Space.jpg | thumb | 500x230px | center | Small-Space Algorithm representation]]

<br />

Where, at step (2) we use a bi-criteria ''(a,b)''-[[approximation algorithm | approximation algorithm]] which outputs at most ''ak'' medians with cost at most ''b'' <math>\forall</math> optimum and at step (3) we run a c-approximation algorithm. The approximation factor of thisSmall-Space() algorithm is <math>''2c(1+2b)+2b</math>''. andWe ifcan wealso generalize it so that it recursively calls itself, <math>i</math> 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 Algorithms ===

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

* BIRCH

* COBWEB

== References ==