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

Your definition of similarity:

The criteria of clustering 2 lists into a same cluster is that "the more they overlap, the more similar they are.

makes me think about Kmeans but with cosine similarity as distance definition.

If you consider

$$ [a] = [1,0,0]\\ [b] = [0,1,0]\\ [c] = [0,0,1] $$

you can think these embeddings as three perpendicular vectors inside a $\mathbb{R}^3$ vectorial space and in particular as its base (i.e. $\widehat{i}, \widehat{j},\widehat{k}$).

In this case to measure how much two verctors overlap, it's the same of calculating the angle between them, and cosine similarity does this.

Note that cosine similarity doesn't take into account vectors magnitude, so two records like $[a,a]$ and $[a,a,a,a,a]$ ($[2,0,0]$ and $[5,0,0]$) will be considered equal (because they have same orientation in the space).