0
$\begingroup$

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.

$\endgroup$
  • $\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$ – aginensky Nov 20 '16 at 22:32
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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