# 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?

• See also (stats.stackexchange.com/questions/27323/…) for similar question. – Miroslav Sabo Oct 9 '12 at 16:41
• Welcome to the site. You don't need to add your name at the end, the program does it automatically. I also used LaTeX on your formula – Peter Flom Oct 9 '12 at 20:06
• I noticed an anonymous edit on your post: For kmeans+Hellinger dist the data are pretransformed by $\sqrt(Y_{ij}/Y_{i+})$ so when kmeans calculates euclidean distance is actually calculating Hellingers'. Have you lost your account information? (The present account is already registered.) – chl Oct 10 '12 at 18:36

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?

• Thanks a lot Anony-Mousse. I am very sorry I was not explicit! I pre-transformed my presence-absence data (as suggested by Legendre and Gallagher 2001), to overcome this problem (that kmeans only works on euclidean distance), by pre-transforming the data, when the kmeans algorithm is calculating the euclidean distance, is actually computing Hellinger's (transformation is sqrt(Yij/Yi+)) and it is very similar to Jaccard except that in some cases is able to distinguish a bit better differences in composition. Trying now DBSCAN. What about running the k means cluster over the MDS scores? – Ana Oct 9 '12 at 17:45
• Usually with k-means you will want to interpret the cluster centers. They are supposed to be representative of the cluster. If the results don't degenerate badly (check distance between means compared to object-mean distances, for example, and cluster sizes - if there are tiny clusters, something is wrong) and you can transform back the mean to a value that you can interpret - give it a try and see if it is useful for you. That is the one true objective. – Has QUIT--Anony-Mousse Oct 9 '12 at 19:07
• Hola @Anony-Mousse I tried DBSCAN using both Bsim and Hellinger distances, neither gave good results, either all sites were classed as noise or in few classes surrounded by "noise". Seeing that, now am not sure what is the appropriate approach to analyse the species patterns: some have wide distributions while others are restricted. A hierarchical clustering could be an option, except that cutting the tree at k usually renders some regions well defined (compared with empirical knowledge) while others are still too broad. Is there any valid way of picking the level at what to cut each branch? – Ana Nov 8 '12 at 1:18
• Look at the dendrogram. You do not need to perform a horizontal cut, you can cut at different levels for different areas. Getting Noise is not bad, as there may be noise in your data. This will also happen with hierarchical clustering, that you get single-element "clusters". – Has QUIT--Anony-Mousse Nov 8 '12 at 6:58
• Thanks! Is good to know that is ok to cut at different levels for different areas. So, I will cut at the levels that make more sense! – Ana Nov 8 '12 at 15:54