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 1 down vote favorite
  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 ...

share|improve this question

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
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. – shn Jun 8 '12 at 12:52
@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. – TenaliRaman Jun 8 '12 at 14:33
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 ? – shn Jun 8 '12 at 19:47
1  
@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. – TenaliRaman Jun 15 '12 at 11:54
1  
@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 – TenaliRaman Jun 15 '12 at 11:57
show 2 more comments

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.