1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Nov 16, 2015 at 7:08
  • $\begingroup$ 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. $\endgroup$
    – Pere
    Commented Oct 16, 2016 at 20:24

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.