1. Suppose we have a classical k-means where iteratively each datapoint is assigned to its nearest center.
  2. After a certain time, suppose that we change the dataset by another similar dataset containing some additional classes, and I want to cluster it using only one pass, and allowing the number of clusters K to increase (when necessary). Actually this just a simple example to introduce my question.

My question: is there any statistical/probabilistic model or something that will allow us during the first phase to learn for example some values for each cluster, in order to predict if a new datapoint from the second phase should produce a new cluster or should be assigned to its nearest center.

Briefly, is there any useful statistics or probabilities that can be associated to each cluster in order to predict if a new datapoint is member of its nearest center or not. Maybe by using something like gaussian distribution for each cluster ... but how ...


1 Answer 1


What you might be looking for could be Recurrent Chinese Restaurant Process [1]. Of course I am assuming that your data has some temporal nature to it and that this temporal data can be divided into ordered epochs. Your use of the phrase "first phase" and "second phase" somewhat hints at different epochs (and first and second possibly hinting at time-ordering?) and hence, I believe that this paper might be applicable to you.

In case you are not looking at temporal data and simply looking to add new points to existing clusters, then you probably are interested in the basic Chinese Restaurant Process [2].

[1] http://www.cs.cmu.edu/~epxing/papers/SDM08_Ahmed.pdf
[2] http://www.gatsby.ucl.ac.uk/~ywteh/research/npbayes/dp.pdf

  • $\begingroup$ I'm doing online clustering, but not looking for temporal data. I've already read this post which is talking about Chinese Restaurant Process to do that, but I really don't see (or didn't understood) how the Chinese Restaurant Process can help me to decide whether a new data-point should be assigned to its nearest cluster or should start its own new cluster. $\endgroup$
    – shn
    Jun 8, 2012 at 12:52
  • $\begingroup$ @user995434 That is a very detailed and nice blog post! Note that Chinese Restaurant Process(CRP) is a model. If you fix its parameters, it will give you the probability of a point belonging to one of the existing cluster or forming a new cluster. But you already have clusters with you. Assuming that your clusters were formed using CRP, we need to figure out what parameter settings of CRP could have possibly generated your clusters (this is called inference). In the blog post, Concentrate on the section "Inference in dirichlet process mixture" and the papers he points to. It should help you. $\endgroup$ Jun 8, 2012 at 14:33
  • $\begingroup$ What are the requirements and prerequisites to understand the Inference in the Dirichlet Process Mixture and the paper he points to in the blog post ? Is this the same as this paper ? I'm not familiar with all this stuff: mixture models, dirichlet process ... Why is the CRP usually cited where we talk about DP, are they referring to the same thing ? $\endgroup$
    – shn
    Jun 8, 2012 at 19:47
  • 1
    $\begingroup$ @user995434 Whenever somebody talks of DP, they also give the various views of DP which includes CRP. You will see CRP being discussed in the second link. Yee Why Teh has videos on dirichlet process on videolectures.net as well. You might want to listen to them as well. $\endgroup$ Jun 15, 2012 at 11:54
  • 1
    $\begingroup$ @user995434 All of this falls under a more general umbrella called the non-parametric bayes models. I didn't want to confuse you earlier than what you might already be at the moment :-). However, since you seem to be very keen on this, you may be willing to take the longer route - mlg.eng.cam.ac.uk/porbanz/talks/npb-tutorial.html $\endgroup$ Jun 15, 2012 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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