Data stream clustering
Encyclopedia
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.
, CURE
and the popular BIRCH
. For data streams, one of the first results appeared in 1980 but the model was formalized in 1998 .
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.
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 in a single pass, with time O(n1+e) and space θ(nε) up to a factor 2O(1/e), where n the number of points and e<1/2.
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 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)
k) centers obtained in (2),
where each center c is weighted by the number
of points assigned to it.
Cluster X to find k centers.
Where, if in Step 2 we run a bicriteria (a,b)-approximation algorithm
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 2c(1+2b)+2b. 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, (n/
) and so that the weighted 
k centers also fit in memory, 
k. 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:
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, 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
Streaming algorithm
In computer science, streaming algorithms are algorithms forprocessing data streams in which the input is presented as a sequence ofitems and can be examined in only a few passes...
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-medoidsK-medoids
The -medoids algorithm is a clustering algorithm related to the -means algorithm and the medoidshift algorithm. Both the -means and -medoids algorithms are partitional and both attempt to minimize squared error, the distance between points labeled to be in a cluster and a point designated as the...
, CURE
CURE data clustering algorithm
CURE is an efficient data clustering algorithm for large databases that is more robust to outliers and identifies clusters having non-spherical shapes and wide variances in size.- Drawbacks of traditional algorithms :...
and the popular BIRCH
BIRCH (data clustering)
BIRCH is an unsupervised data mining algorithm used to perform hierarchical clustering over particularly large data-sets...
. 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.
STREAM
STREAM is an algorithm for clustering data streams described by Guha, Mishra, Motwani and O'Callaghan which achieves a constant factor approximationApproximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
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 in a single pass, with time O(n1+e) and space θ(nε) up to a factor 2O(1/e), where n the number of points and e<1/2.
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 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)
- Divide S into
disjoint pieces X1,...,X
. - For each i, find O(k) centers in Xi. Assign
each point in Xi to its closest center. - Let X
k) centers obtained in (2),where each center c is weighted by the number
of points assigned to it.
Where, if in Step 2 we run a bicriteria (a,b)-approximation algorithm
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
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 2c(1+2b)+2b. 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, (n/) and so that the weighted k centers also fit in memory, k 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:
- Input the first m points; using the randomized algorithm presented in reduce these to O(k) (say 2k) points.
- Repeat the above till we have seen m2/(2k) of the original data points. We now have m intermediate medians.
- Using a local searchLocal search (optimization)In computer science, local search is a metaheuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions...
algorithm, cluster these m first-level medians into 2k second-level medians and proceed.
- In general, maintain at most m level-i medians, and, on seeing m, generate 2k level-i+ 1 medians, with the weight of a new median as the sum of the weights of the intermediate medians assigned to it.
- When we have seen all the original data points, we cluster all the intermediate medians into k final medians, using the primal dual algorithm .
Other Algorithms
Other well-known algorithms used for data stream clustering are:- BIRCHBIRCH (data clustering)BIRCH is an unsupervised data mining algorithm used to perform hierarchical clustering over particularly large data-sets...
: 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 O(N) since one pass suffices to get a good clustering (though, results can be improved by allowing several passes). - COBWEBCobweb (clustering)COBWEB is an incremental system for hierarchical conceptual clustering.COBWEB incrementally organizes observations into a classification tree. Each node in a classification tree represents a class and is labeled by a probabilistic concept that summarizes the attribute-value distributions of...
: is an incremental clustering technique that keeps a hierarchical clustering model in the form of a classification treeDecision tree learningDecision tree learning, used in statistics, data mining and machine learning, uses a decision tree as a predictive model which maps observations about an item to conclusions about the item's target value. More descriptive names for such tree models are classification trees or regression trees...
. 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 functionCategory utilityCategory utility is a measure of "category goodness" defined in and . It was intended to supersede more limited measures of category goodness such as "cue validity" and "collocation index"...
).