# K-means clustering with relative distances

I am working on implementing a clustering algorithm on similar words, based on definition. For example, given a list of words: delete, remove, edit, modify, add, I would like to construct groups of similar words (i.e. [delete, remove], [edit, modify], [add])

I wrote a function using Wordnet from nltk that calculates a rough similarity given 2 verbs, but I am wondering how to use this in my clustering algorithm. From what I have read online, you need to know fixed coordinates to compute the clusters. Unfortunately, all I have is the similarity between any 2 given verbs.

compute_similarity('delete', 'remove') # output: 0.4 (strong)
compute_similarity('yawn', 'fly') # output: 0.02 (weak)


Is there any way I can use these word-to-word relationships to form clusters based on similar meaning? If possible, I would like to stick with the K-means route, as it is relatively simple to implement.

Update: I may have posted this without doing quite enough research yet. I am now leaning towards building up a 2d matrix of all of the distances between words, and feeding it into a DBSCAN clustering algorithm.

• To cluster you need a 'distance'. That is a function with 3 properties i) $d(x,x)= 0$, ii) $d(x,y) = d(y,x)$ and, most importantly $d(x,y) + d(y,z) \geq d(x,z)$. It's not clear to me that your word metric will satisfy the third criteria. Does it ?
– meh
Nov 20, 2016 at 22:32