Clustering given "distance" matrix and K in python

Question

INPUT ($D$, $K$):

I have a symmetrical "distance" matrix $D$ of size $N \times N$ which tells me how distant one object is from another. Function used for calculating the distances is not a metric (doesn't satisfy triangle inequality). The values in $D$ are from $[0,1]$ where 0 means 2 objects are identical, and 1 means they are the furthest possible.

I also know that I would like to obtain $K$ clusters.

OUTPUT:

I would like to obtain $K$ clusters, where every clustroid has a small average distance to every other guy within the same cluster. Ideally with no silly clusters with 1-2 elements.

QUESTION:

Which clustering method would you use? K-means requires feature vectors, which I don't have, Spectral Clustering assumes that the distance function is a metric. I thought of using DBSCAN, but it doesn't allow $K$ as input. I could tune the hyperparams to get the $K$ I want, but I was wondering if there is a clear better choice. $N$ can range from 5 000 to 20 000, and $K$ is smaller than 1 000, so I assume there will be no issues with CPU or MEM.

Answer 1

There are different clustering options that work well with a distance matrix and most of them accept the number of clusters as input. I list all the ones I used for my Ph.D. thesis and know they work as intended:

• Scikit-learn's Spectral clustering: You can transform your distance matrix to an affinity matrix following the logic of similarity, which is (1-distance). The closer it gets to 1, the higher the similarity (affinity) and vice-versa. For this and the other clustering methods, if you have a 1D array, you can transform it using sp.spatial.distance.squareform for input to the cluster.fit_predict method. You need to set the affinity parameter to precomputed to work. Following the documentation, you can also use precomputed_nearest_neighbors for the affinity parameter, as a distance matrix can be interpreted as a sparse graph of precomputed distances. In my experiments, this approach yielded the best results (with external CVIs over 0.9), so it is worth mentioning.

• Scikit-learn-extra's K-Medoids clustering: You need to install the scikit-learn-extra library (it is not included in the standard one) to access a method similar to K-Means that can take a distance matrix as direct input. You have to set the metric parameter as precomputed and introduce the distance matrix in the cluster.fit_predict method for the clustering to work.

• Scikit-learn's Agglomerative clustering: Similar to the previous clustering methods, you need to set the affinity parameter to precomputed and use the distance matrix for the cluster.fit_predict method. For clarification, while we are using the affinity parameter (which other clustering methods use for the affinity/similarity matrix) the API indicates it takes a distance matrix instead, so no further changes are needed.

• Hdbscan's HDBSCAN clustering: The hierarchical version of DBSCAN accepts the distance matrix by setting the metric parameter to precomputed and using it for the cluster.fit_predict method. As a side note, if you need to specify the number of clusters, you can use the flat.HDBSCAN_flat method included in the library, which is handy as default DBSCAN and HDBSCAN do not currently support specifying the clusters as parameters.

• Scikit-learn's Affinity Propagation clustering: While the API does not explicitly indicates it, you need to use an affinity (similarity) matrix instead of your distance matrix for the cluster.fit_predict method. You can follow the recommendation from Spectral Clustering method to transform it. As before, set the affinity parameter to precomputed. For clarification, it does not accept the number of clusters as input.

• Scikit-learn's OPTICS clustering: Similar to K-Medoids, set metric to precomputed and use the distance matrix as input for the cluster.fit_predict method.

Answer 2

I think PAM and Hierarchical clustering algorithms can be good when your input is a distance matrix. Take a look at this