What to use, k-means or hierarchical clustering for presence absence data? I am currently working with a presence-absence database that is mostly zeros (~5% are ones) representing species in space (a species per site matrix). I would like to explore the spatial pattern of the species and see whether there is any "natural" grouping of the data that could be thought of as bioregions. I have been explored different clustering methods (hierarchical clustering and kmeans) using two different metrics [Hellingher distance and $Bsim=a/a+(min(b,c))$; where $a$ is the shared species between two sites and $b$ an $c$ are the unique species for each site]. 
There is also another variation doing multidimensional scaling over the distance matrix, before running the kmeans cluster. My thinking is that by reducing everything to two or three dimensions (am working with up to 600 species), this would limit the "freedom" of the centroids to move around all the dimensions as every new pixel is added. The counter argument is that it will render the solution more stable and avoid error propagation.
While it is possible to do some kind of validation of the final clusters (e.g., represent the clusters in a map and relate their borders to some topographic or any other environmental feature), I would like to know: How can I decide between  the different clustering methods and distance metrics?  What are the pros and cons in terms of mathematics or statistics?
 A: For binary data, k-means is really bad.
The problem is that it computes means, which no longer are binary, but more central to the data set than any of your observations. But how good is a cluster assignment when the cluster means are more similar to each other than the actual observations to each other or even to the "centers"? In your cluster centers, all species will then be "a little bit present"...
Note that k-means is only well defined for Euclidean distance. Don't use it with other distance functions. If they are not compatible, the algorithm may stop converging in the worst case. K-means is only proven to converge when the mean minimizes the variance, too.
There are quite a lot of distance-based clustering algorithms around (hierarchical clustering, DBSCAN, OPTICS, ...) that can work with arbitrary distance functions. So you should be able to use these with whatever distance function you have found to be useful. And there are quite a lot of set based distance functions. I believe Jaccard similarity was even created when analyzing the presence and absence of species. So why not find a distance based clustering algorithm to use with Jaccard similarity?
