# Clustering based on distance measure violating triangle inequality

Suppose I have a set of categorical data $X=\{x_1,x_2,\cdots, x_n\}$, (in my case $n =~ 10,000-50,000$) as well as a precomputed "distance" measure $g(x_i,x_j)$ (in my case I just have an array of distances). However, this measure doesn't necessarily satisfy the triangle inequality.

I want to cluster this data via some sort of k-means-like routine, but as the triangle inequality doesn't hold doing the usual procedure of iterating with a centroid of average values won't really work.

My hope was to use some sort of graphical model where each $x_i$ was a node and each $g(x_i,x_j)$ was an arrow, and do some sort of clustering based on that. However, my current literature review wasn't that fruitful. Does anyone have any insight into an algorithm that might work for this sort of analysis?

• k-means only works' for continuous data. Use (single/average/complete linkage) hierarchical clustering or DBSCAN which can work with arbitrary data and do not require triangle inequality either. – Anony-Mousse Nov 16 '15 at 7:08
• In stats.stackexchange.com/a/240567/123561 , there is an answer using a distance that violates triangle inequality (the distance used is the inverse of geographical distance), and it seems to work fine using complete linkage. I also checked with single linkage and it worked, too, although results were less interesting. I wonder if I should copy the same example as an answer here. – Pere Oct 16 '16 at 20:24