I know someone at CSHL that is working on that problem, I can ask this person to contact you if you want.

Martin, please do. I have this exciting work on age and aging that awaits statistical testing...

I'll be glad to, just send me an Email address

See the concepts of "Joint Distance Function" in

[1] http://benisrael.net/IYIGUN-BENISRAEL-LAA-09.pdf

and "Classification Uncertainty Function" in

[2] http://benisrael.net/IYIGUN-BENISRAEL-JAN-10.pdf, Appendix B.

The reference for [1] is in its first page, the reference for [2] is:

C. Iyigun and A. B-I, Semi-Supervised Probabilistic Distance Clustering and the Uncertainty of Classification, pp. 3-20 in Advances in Data Analysis, Data Handling and Business Intelligence, A. Fink, B. Lausen, W. Seidel and A. Ultsch (Editors), Studies in Classification, Data Analysis and Knowledge Organization, Springer 2010, ISBN 978-3-642-01043-9

If you need further information, or want to discuss any of the above, write me at [email protected]

Adi: From what I managed to understand, the Classification Uncertainty Function depends on K. I can imagine it can be used to choose K (though I am worried about its homogeneous decline with K regardless of clustering optimality), but how can I compare two clustering solutions? If K is not equal, the values are not comparable, are they?

Eitan, the first concept I mentioned, the Joint Distance Function (JDF), measures the quality of clustering in the following way: It is defined for each point (up to a constant, the harmonic mean of distances to cluster centers). Sum over all data points and get the JDF of the data. It is a decreasing function of K (the number of clusters) going to zero as K = N (the number of points) for then every point is its own cluster. Cluster the data for K = 1, 2, 3, ... If there is a "correct" answer to your question (what is K?) then the JDF will have a change of slope at K (plus/minus 1), and will be flat afterwards. If there is no correct K (for example, data uniformly distributed), the JDF will look like 1/K.

The second concept I mentioned, the Classification Uncertainty Functions measures how sure you're of your solution, not its quality. Points that can go to either cluster have high uncertainty.

Adi: I think I understood the concept correctly. So, here is my experiment. I cluster a set of elements using two different data-sets. My null hypothesis is that the optimal number of clusters is the same within methodological variation. Now, if I understand correctly what you propose, I will generate a sum-JDF curve for each data-set separately. From that I will extract a (potentially different) K for each data-set (based on where the sum-JDF breaks from 1/k - I guess you can recommend how to do that?).

What I am not sure is how that solves my original problem. If I get two different optimal K values, how do I reject the null hypothesis that the difference is expected due to noise? What is the odds of getting p(|K1-K2|>=x) with two different samples of the same data?

Let me complicate the problem a little: while both data sets measure the same thing, they are two sparse matrices of different dimension. In other words, I am clustering N elements using an N x M matrix, with a different M in each sample.

It pretty much depends on your data. Basically there are two basic concepts that are used in validation coefficients: compactness and separateness of clusters. Some criterion function include both, other just one of this aspects. If you have round and compact clusters, you can minimize sum of distances to a centroid and it will work just perfectly. Of course most of datasets doesn't look like this.

In case of clusters based on density, some probabilistic model might be useful, however you should be careful about strong assumption on distribution in your data. For example BIC (Bayesian Information Criterion) could be used (G. Schwarz, “Estimating the dimension of a model,” Annals of Statistics, vol. 6, pp. 461–464, 1978)

Most of criteria include somehow the number of clusters, independent metrics is for example Cophenetic Correlation Coefficient - Sokal and Rohlf (1962). CPCC is computed from a dendrogram tree (you have to use hierarchical clustering or at least construct a dendrogram from clustering results)

There are numerous articles on this topic, for example On Clustering Validation Techniques (2001) by Halkidi http://web.itu.edu.tr/sgunduz/courses/verimaden/paper/validity_survey.pdf, Criterion Functions for Document Clustering: Experiments and Analysis (2002) by Ying Zhao , George Karypis http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.6872

Some of mine experiments proved that using just one criteria is not enough.

Eitan, for fuzzy C-means clusterization I used comparison of membership values distributions. I used it to determine whether the fragmentation was satisfactory or not. In the next article there is something about it on the page 107. http://www.researchgate.net/publication/225098928_Application_of_Fuzzy_Neural_Networks_for_the_Data_Clusterization_Problem

Article Application of Fuzzy Neural Networks for the Data Clusteriza...

Eitan, thanks, I'm traveling for the next week, "talk" to you after that.

I'm not knowledgeable clustering in biological applications, but a general comment is this: once you have determined a measure of clustering quality, then a computer scientist might be able to design a clustering algorithm that optimizes that measure, e.g. like k-Means optimizes average distance from a mean.

Thanks everyone - I found a solution to my problem. I am going to use something Zohar Yakhini's developed.

ER

Eitan, sorry for dropping out of the conversation. You mentioned a result of Zohar Yakhini that works for you - was it published? does it appear in his page

http://bioinfo.cs.technion.ac.il/people/zohar/publications.html

Thanks.

I think its a solution that was not published (yet). In the end we sent a paper using a different approach - comparing the number of statistically significant clusters.

Thanks - when it is published I would appreciate a copy. Best wishes.