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

Question

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.

Answer 1

Usually, when it comes to NLP, dimensionality is a problem. I can think of three ways that you can try and see a clustering structure in such data set:

1. a dimensionality reduction (PCA or SVD), before clustering. This can help "throw" away the lesser important similarities

2. I'd throw in a 2d t-sne to check and see if there is some what of a clustering structure in your data. If the similarity matrix is too big, there are alternatives. Just analyse the plots carefully. If any distinguishable patterns really do rise when t-sne-ing the data, you should be able to find it through other clustering techniques.

3. Other types of clustering algorithms, maybe? I am thinking of DBSCAN or HDBSCAN (check about them, and other clustering techniques here) where there are different types of assumptions for clustering. I've also heard about bi-clustering can be a good way group data points when it comes to similarity matrices (not on NLP, but on other types of data). Sklearn has a few implementations, but I haven't tried them .