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.

Thanks in advance for your help.

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.

  • $\begingroup$ 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 ? $\endgroup$
    – meh
    Commented Nov 20, 2016 at 22:32

1 Answer 1


k-means cannot use other distances.

The key component is the mean. The mean optimizes squared deviations, and points are assigned to means by least-squared-deviation, too. You cannot just use a different distance here, it will no longer converge.

Use hierarchical clustering, PAM or DBSCAN if you have other distances.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.