# Sets clustering

Given a set $$S$$ of $$k$$ sets, where $$S_k$$ is a set of high-dimentional vectors $$S_k=\{v_{k_1}...v_{k_{|S_k|}}\}$$, s.t the dimension of all vectors is fixed $$|v_{k_i}|=l$$.

The vectors are outputs from an encoder and the term "similar vectors" refers to pair of vectors with cosine similarity close to one.

We wish to cluster similar sets together, I.e, find a method that given a new set of vectors will find other sets that are close to it.

The size of the sets may differ $$|S_k|\neq|S_{k'}|$$, and no vector $$v_{k_i}$$ is present in more than one set.

What methods exist to cluster sets together such that sets with vectors that are close under the inner product will be clustered together?

Currently, we compute the chamfer distance between every two sets (which is not a clustering method, rather a similarity evaluation).

Given a new set, we wish to find similar sets without the need to compute the chamfer to all sets in the dataset.

• Are the vectors all of the same dimension? What do these sets represent? What do you mean by "similar"?
– whuber
Feb 23, 2021 at 13:07
• Yes, all the vectors are of the same dimension, and vectors that are l2 close represent similar objects. Each vector is an embedding from an unsupervised neural network, where a set of vectors (s_k) represent "groups", so to speak. Feb 23, 2021 at 13:44
• Those are important considerations, so please include them in the post. But they aren't enough: to address this problem, we would also need to know what it means in your application for two sets of vectors to be "close" or "similar." It helps to know what similar vectors are, but that doesn't translate into a unique metric to compare sets.
– whuber
Feb 23, 2021 at 14:17
• I've added the clarification, as I stated, close sets have a high chamfer similarity value, I.e, for two sets, we find for each vector in one set its closest vector in the other, and sum for all vectors. Thanks:) Feb 25, 2021 at 6:41

Your question does not provide enough information to decide between different methods, so I'll just list different known ways to compute a similarity between sets of points. My answer only gives different distances you can compute, not a solution to avoid computing distance between every set of points.

## Distribution Distance

A distribution distance outputs a positive scalar $$d = D(S_1,S_2)$$ which tells you how similar two sets of points are. I will denote $$S_1 = \{{x}_1, \dots, {x}_n\}$$ the first set with $$n$$ points and $$S_2 = \{{y}_1, \dots, {y}_m\}$$ the second set with $$m$$ points (possibly $$m\neq n$$).

### MMD

The Maximum Mean Discrepancy supposes a symmetric positive definite kernel $$k(x,y)$$ which returns a similarity measure between two vectors $$x,y$$. The definition is $$\widehat{\mathrm{MMD}}^2(S_1,S_2) = \dfrac{1}{n^2}\sum_{i,j=1}^nk(x_i,x_j) + \dfrac{1}{m^2}\sum_{i,j=1}^mk(y_i,y_j) - \dfrac{2}{nm}\sum_{i,j=1}^{n,m}k(x_i,y_j)$$ Note that the classical energy distance corresponds to the MMD for the kernel $$k(x,y) = -\lVert x-y\rVert$$. You can plug any popular characteristic kernel in this formula, such as the Rational Quadratic (RQ), Radial Basis Function (RBF) kernel, Laplacian kernel, etc.

In python you can use the shogun library, or the geomloss package. You can also reimplement it yourself, it's not that complicated.

## Wasserstein

The wasserstein metric between $$S_1$$ and $$S_2$$ transforms a cost $$c(x,y)$$ on individual points into a cost between distributions (or sets of points). The exact wasserstein distance is hard to compute, but easy to compute approximations exist.

Optimal Transport (OT) losses are known to be similar to MMD-type losses as in this paper.

In python you can compute OT losses between sets of points using the geomloss package which supports GPU.

## Friedman-Rafsky Test

This is another distribution-free test. It uses Minimum Spanning Trees between points of $$S_1\cup S_2$$. For more information, see this paper. In plain english, if points of $$S_1$$ are often connected to points of $$S_2$$, the two sets are similar.

## Procrustes

If you believe the location, scale and orientation of your points is not important, try finding the optimal translation $$\mu$$ and rotation $$\mathrm{R}$$ so that the two sets are the most similar: $$S_2 \approx \mathrm{R}(S_1 + \mu) = \tilde{S}_1$$. You then use two sample tests on the transformed samples. This means that instead of computing $$D(S_1,S_2)$$ you compute $$D(\tilde{S}_1,S_2)$$.

• ArnoV, I deeply appreciate your thorough answer. Wasserstein, EMD, and chamfer are indeed great directions, but unfortunately, as we have >>100k sets, it is unfeasible for us to compute the pair-wise distance from all samples in the dataset for each new sample. We thus seek clustering approchs, which are hard to find apparently. Feb 25, 2021 at 14:01
• @ArnoV In your MMD, shouldn't the first sum be until m not n? Mar 5, 2021 at 14:28
• Yes it should, thanks for the correction ! Mar 5, 2021 at 14:45