Clustering method for frequency embeddings

Question

I have, for example, the following lists of words that I want to cluster. The lists could have different lengths, and the vocabulary is $W = \{a,b,c\}$. The criteria of clustering 2 lists into a same cluster is that "the more they overlap, the more similar they are."

Index	List	Embedding
1	$[a,a,b,c]$	$[2,1,1]$
2	$[b,b,c]$	$[0,2,1]$
3	$[a,b,c,c,c]$	$[1,1,3]$
4	$[a,a,a]$	$[3,0,0]$

I have seen some problems with the classic clustering method (e.g. Kmeans) using the Euclidean distance is that $[a], [b],$ and $[c]$ (having the embeddings $[1,0,0], [0,1,0],$ and $[0,0,1]$) could be clustered into a same cluster even though there are non-overlapped events in the lists. And also Kmeans is not a good clustering method when the embedding is integer and could consist a lot of 0.

Which distance and which clustering method should I use for this clustering problem? Or should I use some different embeddings here?

Answer 1

You might want to change your distance metric.

Cosine distance for example, will penalize words with different "dominant" events more then words with slightly different amount of the same events.

The choice of your distance metrics may also impact the choice of your clustering algorithm. Typically, Kmeans is meant to be used with euclidean distance. You can see a bunch of other algorithms here.

Normalizing your embedding vectors would have a similar effect to using cosine distance while allowing you to use Kmeans with euclidean distance.