9
$\begingroup$

I am aware of Cosine Similarity which measure the angle between "two" vectors. Prototype for cosine similarity would look something like this:

float cosine_similarity(vector<float> a, vector<float> b);

Are there any similarity measures that measure the similarity between "n" vectors? Prototype of this function would look something like this:

float cosine_similarity(vector<vector<float>> vectors);

PS: I am NOT looking for clustering/classification sort of a thing.

I will appreciate if someone can point out in some direction.

Thanks!

$\endgroup$
8
  • 2
    $\begingroup$ Would you like a single number to represent the similarity among all the samples in a group? What should this value signify in your case? The purity of the group? Or perhaps an average of all pairwise cosine similarities? $\endgroup$ Commented Oct 7, 2016 at 22:36
  • $\begingroup$ If you start to look at all pairwise cosine similarities, then this falls under a standard class of "linear dependence" metrics. This suggests a natural possibility could be linear dimension reduction techniques. $\endgroup$
    – GeoMatt22
    Commented Oct 8, 2016 at 2:54
  • $\begingroup$ @GeoMatt22 could you please elaborate? $\endgroup$
    – silent_dev
    Commented Oct 8, 2016 at 7:37
  • $\begingroup$ @user115202 yeah I'd like for it to be a single number but definitely more sophisticated than an average of cosine similarities. $\endgroup$
    – silent_dev
    Commented Oct 8, 2016 at 7:38
  • 3
    $\begingroup$ @user3667569 there are many variants, and the best choice will vary depending on your data and goals. However, the basic idea is do an SVD on a data matrix of your vectors. A simple example would be to use the ratio of the first singular value and the matrix norm, which is similar to an $R^2$, giving the "fraction of variance explained", a number between 0 and 1. (PageRank is similar.) $\endgroup$
    – GeoMatt22
    Commented Oct 8, 2016 at 8:30

1 Answer 1

9
$\begingroup$

The cosine similarity between two column vectors $x_1$ and $x_2$ is simply the dot product between their unit vectors $$\mathrm{CosSim}[x_1,x_2]=\frac{x_1}{\|x_1\|}\bullet\frac{x_2}{\|x_2\|}$$ and varies from -1 to +1, similar to a correlation coefficient $R$ (to which it is closely related).

There are many ways to generalize this idea to a set of $n$ vectors, but as requested in the comments, here I will expand on one possibility, related to the idea of (linear) dimensionality reduction.

First, in the $n=2$ case, we can think of $R^2\in[0,1]$ as the "fraction of the variance explained" by a linear regression. For the squared cosine similarity, a similar interpretation is possible, except the associated regression has no "intercept term" (i.e. the vectors are scaled, but not centered).

In the $n$ dimensional case, we can concatenate the vectors into a matrix $$X=\begin{bmatrix}x_1 \, \ldots \, x_n\end{bmatrix}$$ analogous to the cosine similarity case, we can consider dot products based on the scaled matrix $$Y=\begin{bmatrix}y_1 \, \ldots \, y_n\end{bmatrix}$$ assembled from the corresponding unit vectors $$y_i=\frac{x_i}{\|x_i\|}$$ In general we could then conduct varying analyses on the "correlation matrix" $Y^TY$, including dimension reduction via PCA.

The general idea here is to create a low-rank approximation to the matrix $Y$ by truncating its singular value decomposition (SVD). Mathematically, we have $$Y=USV^T=\sum_{k=1}^n\sigma_ku_kv_k^T$$ where the singular values $\sigma_1,\ldots,\sigma_n$ are non-negative and arranged in decreasing order. (For simplicity I am assuming that for $x_i\in\mathbb{R}^m$ the number of vectors is at least $n\geq m$. Otherwise the sum will have $m$ terms.) If we truncate the sum at $K<n$, then we get a "rank $K$ approximation" $\hat{Y}_K$ to the matrix $Y=\hat{Y}_n$. The truncated SVD is optimal in the sense that it minimizes the Frobenius norm of the reconstruction error $\|\hat{Y}_K-Y\|_F^2$.

The squared Frobenius norm is just the sum of the squares of all the entries of a matrix. In particular, for the scaled matrix $Y$ we will always have $$\|Y\|_F^2=n$$ For any matrix, the Frobenius norm is also equal to the sum of the squares of the singular values. In particular, for the $K$-rank approximation $\hat{Y}_K$ we have $$\|\hat{Y}_K\|_F^2=\sum_{k=1}^K\sigma_k^2$$ So we can define an "order $K$ coefficient of determination" as $$R_K^2\equiv\frac{\|\hat{Y}_K\|_F^2}{\|Y\|_F^2}\in[0,1]$$

A simple option would be to just use the first singular value, i.e. $$R_1^2\equiv\frac{\sigma_1^2}{n}$$ The maximum similarity would be for $n$ parallel vectors (i.e. scalar multiples of a single vector), giving $R_1^2=1$. The minimum similarity would be for $n$ orthogonal vectors, giving $R_1^2=\frac{1}{n}$.

A few final notes:

  • The first singular value $\sigma_1$ can be computed via an iterative method, so no detailed SVD need be computed. (Similar to PageRank; e.g. svds(Y,1) in Matlab.)
  • To get a similarity that can range over the entire [0,1] interval, you could simply normalize, i.e. $$\hat{R}_1^2\equiv\frac{\sigma_1^2-1}{n-1}$$
  • So in Matlab the similarity function could be defined via CosSimN = @(Y) (svds(Y,1)^2-1)/(size(Y,2)-1), if we assume that $Y$ is already available as input.
  • For $n=2$ the above will reduce to the absolute value of the standard cosine similarity.
$\endgroup$
6
  • $\begingroup$ thank you for your elaborate answer. Does the equation CosSimN = @(Y) (svds(Y,1)^2-1)/(size(Y,2)-1) also hold for n > 2 and possibly negative data? If not, is there a way to support negative data? $\endgroup$
    – D. Phi
    Commented Dec 10, 2020 at 13:12
  • 1
    $\begingroup$ @D.Phi sorry for the confusion. My proposed $n$-vector similarity measure $\hat{R}_1^2$ can be applied to any collection of vectors. (The only limitation is that no vector is entirely zeros, which also applies to cosine similarity.) For the special case of $n=2$, the result will just be the absolute value of the cosine similarity. So $n > 2$ and negative data are no problem. $\endgroup$
    – GeoMatt22
    Commented Dec 10, 2020 at 17:44
  • $\begingroup$ Thanks, I appreciate your answer. I implemented your code and found an error. You divide by the column count of Y instead of n (which is row count * column count). Here is the code which works for me: CosSimN = @(Y) (svds(Y,1)^2-1) / (prod(size(Y)) - 1) $\endgroup$
    – D. Phi
    Commented Dec 14, 2020 at 19:11
  • $\begingroup$ I've noticed that your proposed formula does not work well on vectors with many zeros. E.g. if Y = [[1,0,0],[1,0,0],[1,0,0]], then CosSimN(Y) = 0.25, even though it should be 1. Is there a benefit to this approach in comparison to the average of pairwise cosine similarities? $\endgroup$
    – D. Phi
    Commented Dec 14, 2020 at 19:53
  • 1
    $\begingroup$ @D.Phi as for the size: As noted in my answer, the sum of squares of singular values by definition equals the sum of squares of the matrix entries (squared Frobenius norm). If you input a $Y$ with normalized (unit-vector) columns, then the sum of squares of $Y$'s entries will be the number of columns. This is the max you can get for the square of $Y$'s first singular value. (If you do not normalize the columns first, this would not hold.) As for "What is the benefit of this approach?", as I mentioned in my initial comment to OP, this is simply one plausible approach to generalizing CosSim. $\endgroup$
    – GeoMatt22
    Commented Dec 14, 2020 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.