In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, 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 In computer science, streaming algorithms are algorithms for processing data streams in which the input is presented as a sequence of items and can be examined in only a few passes (typically just one). In most models, these algorithms have access ...
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
''k''-means clustering is a method of vector quantization, originally from signal processing, that aims to partition ''n'' observations into ''k'' clusters in which each observation belongs to the cluster with the nearest mean (cluster centers o ...
is a widely used heuristic but alternate algorithms have also been developed such as
k-medoids
The -medoids problem is a clustering problem similar to -means. The name was coined by Leonard Kaufman and Peter J. Rousseeuw with their PAM algorithm. Both the -means and -medoids algorithms are partitional (breaking the dataset up into group ...
,
CURE
A cure is a substance or procedure that ends a medical condition, such as a medication, a surgical operation, a change in lifestyle or even a philosophical mindset that helps end a person's sufferings; or the state of being healed, or cured. The ...
and the popular
BIRCH
A birch is a thin-leaved deciduous hardwood tree of the genus ''Betula'' (), in the family Betulaceae, which also includes alders, hazels, and hornbeams. It is closely related to the beech-oak family Fagaceae. The genus ''Betula'' contains 30 ...
. For data streams, one of the first results appeared in 1980 but the model was formalized in 1998.
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
which achieves a
constant factor approximation for the k-Median problem in a single pass and using small space.
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
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...
that divides the data, ''S'', into
pieces, clusters each one of them (using ''k''-means) and then clusters the centers obtained.
Algorithm Small-Space(S)
Where, if in Step 2 we run a bicriteria -
approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...
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 . 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
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
subsets such that each subset fits in memory, (
) and so that the weighted
centers also fit in memory,
. But such an
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:
Other algorithms
Other well-known algorithms used for data stream clustering are:
*
BIRCH
A birch is a thin-leaved deciduous hardwood tree of the genus ''Betula'' (), in the family Betulaceae, which also includes alders, hazels, and hornbeams. It is closely related to the beech-oak family Fagaceae. The genus ''Betula'' contains 30 ...
:
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 since one pass suffices to get a good clustering (though, results can be improved by allowing several passes).
*
COBWEB
A spider web, spiderweb, spider's web, or cobweb (from the archaic word '' coppe'', meaning "spider") is a structure created by a spider out of proteinaceous spider silk extruded from its spinnerets, generally meant to catch its prey.
Spi ...
: is an incremental clustering technique that keeps a
hierarchical clustering
In data mining and statistics, hierarchical clustering (also called hierarchical cluster analysis or HCA) is a method of cluster analysis that seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into ...
model in the form of a
classification tree
Classification chart or classification tree is a synopsis of the classification scheme, designed to illustrate the structure of any particular field.
Overview
Classification is the process in which ideas and objects are recognized, differentia ...
. 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: 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:
uses micro-clusters that are temporal extensions of
BIRCH
A birch is a thin-leaved deciduous hardwood tree of the genus ''Betula'' (), in the family Betulaceae, which also includes alders, hazels, and hornbeams. It is closely related to the beech-oak family Fagaceae. The genus ''Betula'' contains 30 ...
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
''k''-means clustering is a method of vector quantization, originally from signal processing, that aims to partition ''n'' observations into ''k'' clusters in which each observation belongs to the cluster with the nearest mean (cluster centers o ...
, thus producing a final clustering result.
References
{{reflist
Cluster analysis algorithms