Content deleted Content added
| (91 intermediate revisions by 37 users not shown) | |||
Line 1:
In [[computer science]], '''data stream
== History ==
Data stream clustering has recently attracted attention for emerging applications that involve large amounts of streaming data. For clustering, [[k-means clustering
== Definition ==
The problem of data stream clustering is defined as:
'''Input:''' a sequence of
'''Output:'''
This is the streaming version of the k-median problem.
== Algorithms ==
<!-- Unlike online algorithms, algorithms for data stream clustering have only a bounded amount of memory available and they may be able to take action after a group of points arrives while online algorithms are required to take action after each point arrives. -->
STREAM is an algorithm for clustering data streams described by Guha, Mishra, Motwani and O'Callaghan
[[File:Small-Space.jpg | thumb | 440x140px | right | Small-Space Algorithm representation]]▼
'''Algorithm Small-Space(S)'''
{{ordered list
each point in ''
where each center ''c'' is weighted by the number
of points assigned to it.
}}
Where,
The problem with the Small-Space is that the number of subsets <math>\ell</math> 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 <math>\ell</math> subsets such that each subset fits in memory, (<math>n / \ell</math>) and so that the weighted <math>\ell k</math> centers also fit in memory, <math>\ell k < M</math>. But such an <math>\ell</math> may not always exist.
▲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 Small-Space() algorithm is ''2c(1+2b)+2b''. We can also generalize it so that it recursively calls itself <math>i</math> times on a successively smaller set of weighted centers.
The STREAM algorithm solves the problem of storing intermediate medians and achieves better running time and space requirements. The algorithm works as follows:<ref name=cds />
==== Other Algorithms ====▼
{{ordered list
|1 = Input the first ''m'' points; using the randomized algorithm presented in<ref name=cds /> reduce these to {{tmath|O(k)}} (say 2''k'') points.
|2 = Repeat the above till we have seen ''m''<sup>2</sup>/(2''k'') of the original data points. We now have ''m'' intermediate medians.
|3 = Using a [[Local search (optimization)|local search]] algorithm, cluster these ''m'' first-level medians into 2''k'' second-level medians and proceed.
|4 = In general, maintain at most ''m'' level-''i'' medians, and, on seeing ''m'', generate 2''k'' 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.<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>
}}
Other well-known algorithms used for data stream clustering are:
* [[BIRCH (data clustering)|BIRCH]]:<ref name="birch">{{cite journal | first1 = T. | last1 = Zhang | first2 = R. | last2 = Ramakrishnan | first3 = M. | last3 = Linvy | title = BIRCH: An efficient data clustering method for very large databases | journal = ACM SIGMOD Record |doi=10.1145/235968.233324 | date = 1996 | volume=25 | issue = 2 | pages=103–114| doi-access = free }}</ref> 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 {{tmath|O(N)}} since one pass suffices to get a good clustering (though, results can be improved by allowing several passes).
* [[Cobweb (clustering)|COBWEB]]:<ref>{{cite journal | first = D. H. | last = Fisher | title = Knowledge Acquisition Via Incremental Conceptual Clustering | journal = Machine Learning | date = 1987 | doi=10.1023/A:1022852608280 | volume=2 | issue = 2 | pages=139–172| doi-access = free }}</ref><ref>{{cite journal | first = D. H. | last = Fisher | citeseerx = 10.1.1.6.9914 | title = Iterative Optimization and Simplification of Hierarchical Clusterings | journal = Journal of AI Research | volume = 4 | date = 1996 | arxiv = cs/9604103 | bibcode = 1996cs........4103F }}</ref> is an incremental clustering technique that keeps a [[hierarchical clustering]] model in the form of a [[Decision tree learning|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| category utility function]]).
* [[C2ICM(incremental clustering)|C2ICM]]:<ref>{{cite journal | first = F. | last = Can | title = Incremental Clustering for Dynamic Information Processing | journal = ACM Transactions on Information Systems | volume = 11 | issue = 2 | date = 1993 | pages = 143–164 | doi=10.1145/130226.134466| s2cid = 1691726 | doi-access = free }}</ref> 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 (data clustering)|CluStream]]:<ref>{{cite journal |last1=Aggarwal |first1=Charu C. |last2=Yu |first2=Philip S. |last3=Han |first3=Jiawei |last4=Wang |first4=Jianyong |title=A Framework for Clustering Evolving Data Streams |journal=Proceedings 2003 VLDB Conference |date=2003 |pages=81–92 |doi=10.1016/B978-012722442-8/50016-1 |isbn=9780127224428 |s2cid=2354576 |url=http://www.vldb.org/conf/2003/papers/S04P02.pdf |ref=CluStream}}</ref> uses micro-clusters that are temporal extensions of [[BIRCH]]<ref name="birch" /> 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 ==
{{reflist}}
[[Category:Cluster analysis algorithms]]
| |||