Exploring distribution of pairwise distances before clustering I'm trying to perform clustering on a 200+ feature dataset consisting of brain measures for 200 healthy controls and 200 schizophrenia patients. However, I have the feeling the data points do not really cluster into different subsets. Since I know the diagnostic labels, I can do supervised classification, e.g., using SVMs. In that case, I get around 70% cross-validated test accuracy so there is some structure in there that allows the (nonlinear) SVM to keep the groups apart. However, clustering methods may need a better separation in order to show up. Note that I'm not trying to reproduce the diagnostic groups using clustering (I tried that just to see if the diagnostic labels match the clustering labels. In fact, they do not). I'm trying to see whether I can find clusters of subjects across diagnostic categories.
Now, since I was not really getting any results I thought I'd look at the distribution of pairwise distances in the dataset. I read somewhere that, if clusters exist, you should see some peaks and valleys in the histogram. I tried several distances measures in Scipy, like squared euclidian, cosine, city block, etc. However, these all look very much like normal distributions (some quite perfect, others a bit skewed to one side). I plotted the distribution of cosine distances for a randomly generated dataset and its shape looks exactly the same as my brain data.... So, I'm wondering, is this evidence enough to conclude there are no clusters? Is this a good way to visually explore whether there's anything of interest in the data in terms of clusters?
Any advise on this would be greatly appreciated!
 A: I have tried that.
Unfortunately, for complex data sets you will mostly be seeing uninteresting distances.
This is a histogram of pairwise distances of "interesting points" from DBpedia. This includes landmarks, but also remote locations where e.g. a space shuttle downed in the ocean. And of course the poles, they are landmarks!

Now you may be excited, and figure "there must be two clusters here!".
But that is outright wrong. All of that histogram is actually not interesting, because that is mostly distances across different continents. So yes, we do see "within continent" distances at the very very very left, and everything larger than say 1,000,000 meter is across continents.
But of course we have more than 2 continents. You cannot even derive this macroscopic structure from this histogram, unfortunately.
If you have 10 clusters, each 10% of your data set, only 10% of pairwise distances is within-cluster, and 90% is different clusters. Here, I was expecting to see hundreds of clusters; so anything of interest is in the very left bins of the histogram.
