Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 0 down vote favorite
1
  1. Incremental clustering algorithms
  2. Online clustering algorithms
  3. Data stream clustering algorithms
  4. Single pass clustering algorithms

Are the following expressions related? Does some of them include others? What is the difference between them? What are the constraints that each one should face unlike others?

share|improve this question
This question is on topic at Stats--and I'm pretty sure it would get good answers there--but because you requested that it be migrated, we're sending it along to SO. If the SO community closes it, we would welcome it back at Stats. – whuber♦ Feb 8 '12 at 14:22

1 Answer

up vote 1 down vote accepted

When there is more than one term for essentially the same thing, it usually is because people from different communities (that talk little to each other) try to do the same thing. This probably is also the case here.

Incremental clustering and online clustering are largely the same thing IMHO. Incremental clustering may be a bit more batch oriented that online clustering.

Data stream clustering is similar, but usually makes the assumption that "old" data is of less importance. As such, it will often discard old data, and only keep "summaries" of it for clustering.

So "online" and "stream" often differ in that in the first case it is commonly expected that the result will be exactly the same as if all the data had been available in the first place; in the second case, old data is considered unavailable, and the summaries are just updated for the new data. Things such as "concept drift" come into existence here.

Now for the last one, single-pass means that you are supposed to process every element just once (and not copy it). Such algorithms obviously must be in linear time, which makes them good candidates for big data and MapReduce (if they can be somewhat divided, this is not necessarily trivial).

Single-pass doesn't necessarily mean the results will be updateable and thus usable for online or streaming operation. However they often are, as they never need to access "old" data, and the summaries they are allowed to keep usually can be kept and updated.

Single-pass are mostly interesting when you have too much data to keep or process more than once. So for "real time" applications and such. Obviously, the results will usually be worse than when you had full data available anytime.

share|improve this answer
Actually, I'm searching for clustering algorithms where all the following constraints are considered (and I think it belongs to more than one of the above mentioned categories): (1) We don't have initial representatives beforehand, and we can not extract them from the dataset using a seeding procedure since we don't have this dataset beforehand, because it's a continuously arriving and evolving data stream. (2) The data are processed (clustered) one by one (one at a time) in the order of arriving, i.e. we can not for example wait until we get a sufficient number of data and then cluster them. – shn Feb 8 '12 at 18:24
(3) and of course processing each new data should be done incrementally (we do not redo all clustering since the beginning on all previously seen data), but this doesn't mean that the old clusters are no more so important. – shn Feb 8 '12 at 18:24
Well, you can of course do online k-means, and just use the first k instances as initial mean estimations (which actually even is the original MacQueen k-means AFAIK). You will need to do some kind of bootstrapping if you want a representative based clustering. – Anony-Mousse Feb 8 '12 at 18:30
It's a k-means implementation where we have the first k instances as initial centroid, then we assign each arriving data point to a cluster and update its centroid immediately. This is not feasible because in the first constraint I've said that we have "a continuously arriving and evolving data stream", that is, if you fix the number of clusters to k and keep updating there centers, then if you have a completely new class of data that arrives (because the data stream is evolving) the fixed k centres will not be convenient (we may need new clusters). Moreover we can not know K beforehand. – shn Feb 8 '12 at 18:52
That is largely the common downside of k-means that you usually do not know the appropriate k. Depending on your task, you may however get away with a much larger k. As for an "evolving" stream, and obvious choice would be to allow the means to shift more by artificially forgetting old contribution. E.g. assuming that each mean is the mean of 100 objects, so the new object always contributes a static fraction. This way, "concept drift" is possible. If you choose k much larger, you can then run another k-means on these "rough" means only. Might give good results or not. With k-ms you never know – Anony-Mousse Feb 8 '12 at 19:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.