# Given some words and their semantic similarity matrix, how best to group them?

Say, the words are road, highway, avenue, car, bus, train. Then they should be grouped as follows: street, road, highway, avenue into one group, and car, bus, train into another group. So, I wrote a code (in MATLAB) to download synonyms of each word in my dataset (which I pass in dictionary in the code below), and then evaluate the similarity between them by finding out what fraction of synonyms are in common (Jaccard similarity).

[~,b]=dictionary('access aeroway airport amenity area atm barrier bay bench boundary bridge building bus cafe car coast continue created defibrillator drinking ele embankment entrance ferry foot fountain fuel gate golf gps grave highway horse hospital house landuse layer leisure man manmade market marketplace maxheight name natural noexit oneway park parking pgs place place_of_worship playground police police_station  post post_box_or_mail power powerstation private public railway ref residential restaurant road route school shelter shop source sport toilet toilets tourism unknown vehicle vending vending_machine village wall waste water waterway worship');

S=sum(~cellfun(@isempty,b),2);

for x=1:size(b,1)
for y=1:size(b,1)
m = b(x,:);
n = b(y,:);
similarity(x,y) = numel(intersect(m(~cellfun('isempty',m)), n(~cellfun('isempty',n)))) / numel(union(m(~cellfun('isempty',m)), n(~cellfun('isempty',n))));
end
end
csvwrite('similarity.csv',similarity)


Then, I used this gentleman's way of clustering the words based on similarity (code in R):

tmp <- read.csv('similarity.csv')
View(tmp)
d <- as.dist(tmp)
mds.coor <- cmdscale(d)
plot(mds.coor[,1], mds.coor[,2], type="n", xlab="", ylab="")
text(jitter(mds.coor[,1]), jitter(mds.coor[,2]), rownames(mds.coor), cex=0.8)
abline(h=0,v=0,col="gray75")
plot(hclust(dist(1-tmp), method="single"))


But the results are not that good:

1. Most of the words are left unclustered.
2. Many of the words that do get clustered should not be in the same cluster.

In my research online, I found out about Word2Vec and WordNet. But then, there are several complaints of mis-classification by them, like this for example. Moreover, Word2Vec apparently can group opposite words together; so it is not good for what I want it to do. Besides, for my purposes, I do not want something too complicated, as this grouping is actually not the focus of my work - its to use the grouping to do something more important. I can do the grouping manually, but having an algorithm to do it is better for generalization of the approach to scale to any dataset, and hence this question.

Also, I found out that k-means does not work when run on similarity matrices. But there is another similar algorithm called k-medoid that does run on similarity matrices. So, I used it (with corrections, see the comment on 20 June), but its results are also not good:

1. When I tried with k=10, out of 85 words, 70 words are grouped in 1 cluster.
2. When plotting with only 2 clusters, many of the words overlap (hence so few points on the graph despite having 85 points actually), and all of them lie on the basis vectors instead of in the vector space (don't know what this could mean).

So, is there any advice on what I could do? Just looking for a good-enough method of grouping words; it doesn't have to be a perfect one, and it certainly doesn't have to be complicated.

• Usually, when it comes to NLP, dimensionality is a problem. I can think of two ways I can help you: – Guilherme Marthe Jun 20 '17 at 14:20
• @GuilhermeMarthe Please, I am all ears! All help is welcome :) – Kristada673 Jun 20 '17 at 14:21
• the comment I was writing was becoming rather too long for a comment. I'll post it as an answer :D – Guilherme Marthe Jun 20 '17 at 14:24