Data stream clustering: Difference between revisions

Revision as of 01:52, 20 November 2017

Revision as of 02:07, 12 December 2018

Line 2:

== History ==

Data stream clustering has recently attracted attention for emerging applications that involve large amounts of streaming data. For clustering, [[k-means clustering|k-means]] is a widely used heuristic but alternate algorithms have also been developed such as [[k-medoids]], [[CURE data clustering algorithm|CURE]] and the popular{{cn|date=July 2017}} [[BIRCH (data clustering)|BIRCH]]. For data streams, one of the first results appeared in 1980<ref>{{cite journal | first1 = J. | last1 = Munro | first2 = M. | last2 = Paterson | url = http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4567985 | title = Selection and Sorting with Limited Storage | journal = Theoretical Computer Science | volume = 12 | issue = 3 | pages = 315–323 | date = 1980 | doi = 10.1016/0304-3975(80)90061-4 }}</ref> but the model was formalized in 1998.<ref>{{cite journal | first1 = M. | last1 = Henzinger | first2 = P. | last2 = Raghavan | first3 = S. | last3 = Rajagopalan | citeseerx = 10.1.1.19.9554 | title = Computing on Data Streams | journal = Digital Equipment Corporation | volume = TR-1998-011 | date = August 1998 }}</ref>

== Definition ==

Line 17:

=== STREAM ===

STREAM is an algorithm for clustering data streams described by Guha, Mishra, Motwani and O'Callaghan<ref name=cds >{{cite paper | first1 = S. | last1 = Guha | first2 = N. | last2 = Mishra | first3 = R. | last3 = Motwani | first4 = L. | last4 = O'Callaghan | citeseerx = 10.1.1.32.1927 | title = Clustering Data Streams | journal = Proceedings of the Annual Symposium on Foundations of Computer Science | pages = 359–366 | date = 2000 }}</ref> which achieves a [[approximation algorithm|constant factor approximation]] for the k-Median problem in a single pass and using small space.

{{math 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 {{tmath|e<1/2}}.}}

Line 53:

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

* [[BIRCH (data clustering)|BIRCH]]:<ref>{{cite journal | first1 = T. | last1 = Zhang | first2 = R. | last2 = Ramakrishnan | first3 = M. | last3 = Linvy | url = http://doi.acm.org/10.1145/235968.233324 |doi=10.1145/235968.233324 | title = BIRCH: An Efficient Data Clustering Method for Very Large Databases | journal = Proceedings of the ACM SIGMOD Conference on Management of Data | date = 1996 | volume=25 | issue = 2 | pages=103–114}}</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 | url = https://link.springer.com/article/10.1023%2FA%3A1022852608280 | title = Knowledge Acquisition Via Incremental Conceptual Clustering | journal = Machine Learning | date = 1987 | doi=10.1023/A:1022852608280 | volume=2 | issue = 2 | pages=139–172}}</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 }}</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 | url = http://dl.acm.org/citation.cfm?doid=130226.134466 | 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}}</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.