Sequential clustering with an unknown number of clusters

Question

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)?

Answer 1

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

• Clustering algorithms.
• Bayesian inference. Lecture by Christopher Bishop of the PRML book
• Particle filters, also known as sequential Monte Carlo methods. Here are lectures by Simon Godsill, Arnaud Doucet & Nando de Freitas, and Arnaud Doucet of the Sequential Monte Carlo Methods in Practice book.

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