The K-means algorithm does not fit in a probabilistic framework but it has some interesting convergence properties described in the following paper:

"Convergence Properties of the K-Means Algorithms" by Léon Bottou and Yoshua Bengio.

You can find a copy of this paper at:

http://papers.nips.cc/paper/989-convergence-properties-of-the-k-means-algorithms.pdf

Dear Dominique,

Thanks for the answer and the paper (which I knew) but my question is not about kmeans (which was just an example in my question).

My question is "How do I determine that a database is cluster-friendly ?"

Best Regards

Vincent

Are you looking for a relational or non-relational database? Also, do you mean clustering by storing data on a single machine and sharing access across multiple machines or a distributed database system with many machines running on the same data, split up across them?

Dear Mark,

Yes Sorry I discover that my question is ambiguous. I change 1 word

"How do I determine that a dataset is cluster-friendly?"

best regards

Stanford may have a suitable document:

http://infolab.stanford.edu/~ullman/mmds/ch7.pdf

This is not my background so I can not tell if it is of much use but it may help :-)

dear Mark,

The chapter is interesting and summarize a part of the state of the art but do not contribute to answer to my question (even if some definition are close to) - thanks !

You could re-word the question as 'how do I determine if there are clusters in my datasets'? The best way is to run a clustering algorithm and see if the results make sense! :-D

If it was data you could visualise easily, e.g. 2D data you could plot, then how would you decide yourself from looking at it? Personally I'd draw lines through the regions of low density data such that they surround the high density data. Typically we want results that make sense to us, based on the same criteria we would use if we could so this suggests a density based clustering technique.

It also depends what you mean by a cluster. To many people clusters are like clouds of data where everything in one cluster is closer to each other than to data in other clusters. This produces hyper-spheres or hyper-elliptical cluster shapes. Many techniques are avilable for these.

These techniques are somewhat limited if the groups you wish to find are different shapes, e.g. spirals, helices or other arbitrary shapes though. We humans do not limit our groups to elliptical shapes, we can group data in any kind of shape. For arbitrary shaped clusters try DBScan and it's variants or just google 'clustering arbitrary shapes'. I have a new technique of my own under development for this. The advantage of these types of techniques is that an arbitrary shape technique will find ellipses, but not vice-versa.

At a guess I expect you are trying to find a very quick technique to avoid wasting time running clustering algorithms if no clusters are present? How about this for a suggestion:

Select pairs of data dimensions.

For each, select a suitable radius, or size of square.

Scan across the data dimensions and see how many data points fall in each square. (You could even try plotting it and do this visually!)

If the number is similar in most cases then you have fairly evenly spread data and clusters will not be present. A graph will help here.

If however you have a high variation it suggests that there are regions with high and low number of samples - high numbers would be within a cluster, low between.

Not perfect, not guranteed, but a start.

(I did try this on 15D data once, plotted every possible pair. It was interesting and gave some additional insight into the data.)

Dear Richard,

At first thanks for your long answer.

My opinion based on the paragraphs of your answer :

1) Yes I can try but as you said in 5) I do not want to waist my time ;-). My question in more related if we can "imagine" criterion (may be several as in "Basu - 'Data Complexity in Pattern Recognition' (Book springer 2006)" for classification problem)  to find an idea for the answer ...

2) Visualization are not in the scope on my question, I do not work on toy problem :-) where the number of explanatory is small

3) and 4) Yes of course I think that the answer of my question may be 'algorithm dependent' , may be we have to think to a "tree of answers"

5) yes this idea could the beginning of one criterion among a set of criteria

thanks again

I found some criteria in : Jain and Deubes (1988) "Algorithm for clustering data" based on statistical test.

And for me the interesting "Hopkins" criterion in Diggle (1983) : "Statistical analysis of spatial point patterns"

Hi, I would check : (Banerjee, Amit & Davé, Rajesh N., 2004) Validating Clusters using the Hopkins Statistic.