4
$\begingroup$

Is there any clustering algorithms that:

  • does not assume the number of clusters to be known, and
  • processes the data in only one pass by considering it as a continuously arriving data stream (and we do not know the data set size beforehand)?
$\endgroup$
  • $\begingroup$ SPSS's Two-Step Clustering procedure may fit the bill. It's hard to tell what you mean by "considering it as a continuous data stream" (is this something other than treating variables as continuous?) or "do not know the dataset size beforehand" (I'm not being smart-alecky: how can an algorithm know?). $\endgroup$ – rolando2 Apr 17 '12 at 22:22
  • $\begingroup$ @rolando2 when I said "considering it as a continuous data stream" I mean that we don't have the dataset beforehand, the data comes one by one and are processed on by one (i.e. a data stream). When I said "do not know the dataset size beforehand" I meant that the size of the dataset is unknown, data arrives continuously, we can don't know beforehand how many data our stream contains ... $\endgroup$ – shn Apr 17 '12 at 22:29
  • 3
    $\begingroup$ The magic words are "sequential" or "online" clustering. This paper looks promising. $\endgroup$ – Emre Apr 17 '12 at 23:46
  • $\begingroup$ (+1) a very interesting question $\endgroup$ – steffen Apr 18 '12 at 12:37
  • $\begingroup$ @Emre I'm not familiar with Bayes methods and so on; what are the prerequisites to understand this paper ? Any lectures to propose ? $\endgroup$ – shn Apr 18 '12 at 13:14
5
$\begingroup$

In statistics, the study of streaming data is called sequential analysis. Machine learning has the closely related concept of online learning, the difference being an emphasis on model fitting (regression), rather than hypothesis testing. From the abstract:

A potential clustering with a specified number of clusters is represented by an association hypothesis. Whenever a new report arrives, a posterior distribution over all hypotheses is iteratively calculated from a prior distribution, an update model and a likelihood function. The update model is based on an association probability for clusters given the probability of false detection and a derived probability of an unobserved target. The likelihood of each hypothesis is derived from a cost value of associating the current report with its corresponding cluster according to the hypothesis. A set of hypotheses is maintained by Monte Carlo sampling. In this case, the state-space, i.e., the space of all hypotheses, is discrete with a linearly growing dimensionality over time. To lower the complexity further, hypotheses are combined if their clusters are close to each other in the observation space. Finally, for each time-step, the posterior distribution is projected into a distribution over the number of clusters.

To understand the suggested paper (Sequential clustering with particle filtering: Estimating the number of clusters from data), you will need to familiarize yourself with

There might be easier ad hoc solutions but these are useful tools so I recommend learning them anyway.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I've got the PRML book; which parts of the book are about Bayesian inference ? $\endgroup$ – shn Apr 20 '12 at 11:16
  • $\begingroup$ Bayes theorem is introduced in 1.2, Bayesian linear regression in 3.3, graphical models (which are also Bayesian) in chapter 8, and sequential models (including particle filters in 13.3.4) in chapter 13. $\endgroup$ – Emre Apr 20 '12 at 17:04
  • $\begingroup$ Do I also need "bayesian linear regression" and "graphical models" for the original problem that I stated and for the paper you proposed ? Or is "Bayes theorem" + "particle filters" sufficient to understand it ? $\endgroup$ – shn Apr 21 '12 at 23:47
  • $\begingroup$ Skip graphical models for now but read the chapters on linear models and sequential data. $\endgroup$ – Emre Apr 22 '12 at 7:03
  • $\begingroup$ can you please check my edited post at stats.stackexchange.com/questions/27946/… I've made an implementation of a simple example just to understand, but I still don't see clearly how this can be applied in the context I'm interested in, i.e. online/sequential clustering, like in the paper that you point me to: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.2931 $\endgroup$ – shn May 10 '12 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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