Quantify the similarity of bags of words

Question

I have two datasets that contain the most common words and their frequencies of two different articles.

e.g.:

A = [apple: 23, healthy: 15, tasty: 4]
B = [apple: 19, healthy: 21, bad: 7]

Both datasets contain similar words. I want to find a measure that will give me an idea of whether or not the two articles are talking about the same thing. In this case, they might be discussing apples and their health benefits.

I can get a simple measure like similarity = words in A and B / total number of words but is there a more formal measure, perhaps one that utilises the frequencies as weights?

Answer 1

Let me address this by describing the four maybe most common similarity metrics for bags of words and document (count) vectors in general, that is comparing collections of discrete variables.

Cosine similarity is used most frequently in general, but you should always measure first and make sure that no other similarity would produce better results for your problem, evaluating if you can use some of the more complex measures. Except for Jaccard's set similarity, you can (indeed, might want to) apply some form of TF-IDF reweighing (ff) to your document counts/vectors before using these measures. The TF weighting term might even be Okapi-BM25, and the IDF term replaced with corpus entropy, but in the end has little to do with the original question at hand (BoW similarity measures).

Note that the first measure, Jaccard similarity, suffers from a significant downside: It is the most heavily affected by length differences among documents, and does not take word frequencies into account, either. For Cosine similarity and the $\chi^2$-distance you can (or rather, should) adjust the vectors by normalizing your vectors to unit length (i.e., in addition to TF-IDF re-weighting). But even then, shorter documents will have more sparse counts (i.e., more zeros in their vectors) compared to longer documents, for obvious reasons. (One way around that sparsity difference could be to only include words above some minimum cutoff, using a dynamic cutoff value that increases with document length.)

Before we go over the measures, it should be mentioned that this discussion focuses only on symmetric measures, while asymmetric measure exist as well (particularly, the KL-divergence).

1. Jaccard similarity $J$

This is the most simplistic metric: Collect the set of all words in both documents (tweets, sentences, ...), ${A}$ and ${B}$, and measure the fraction of words the two sets have in common:

$$ J_{A,B} = \frac{|{A} \cap {B}|}{|{A} \cup {B}|} $$

This measure also works for words (and documents) by collecting sets of character (or word) $n$-grams, where $n$ typically is 1, 2, and maybe 3. Notice that Jaccard similarity has its limits, though; If the sequence of $A$ had been $(x, y, z, x, y, z, x, y, z)$ and that of $B$ were just $(x, y, z)$, their Jaccard similarity nonetheless is perfect (i.e., $1.0$), unless you use the n-gram "trick" just described.

Finally, it should be noted that the Dice coefficient $D$ is a slightly more involved version of the Jaccard similarity, but also does not take word counts into account, and it can easily be calculated from $J$ as: $D = \frac{2J}{1+J}$.

2. Cosine similarity $\alpha$

Cosine similarity is probably by far the most popular metric. Collect ordered sets of all word counts from both documents (tweets, sentences, ...), $A$ and $B$, that is, effectively, two "document vectors" $\vec{a}$ and $\vec{b}$, and measure the Cosine angle between the two vectors:

$$ \alpha_{A,B} = \frac{\vec{a} \cdot \vec{b}}{|\vec{a}||\vec{b}|} = \frac{\sum{a_i b_i}}{\sqrt{\sum{a_i^2}}\sqrt{\sum{b_i^2}}} $$

Now, because you can normalize your vectors to unit vectors (i.e., the $|\vec{z}|$ parts) before doing this calculation, you actually only need to calculate the dot product between the two vectors to calculate the similarity - which is nothing more than the sum of the products of all pairs. The dot product can be calculated particularly efficient on modern CPUs.

3. Spearman's rank correlation coefficient $\rho$

Instead of using the counts of each word, you order the words of each document by their counts and thereby assign a rank to each word, for either document, $A$ and $B$. That therefor saves you from having to length-normalize the document vectors. Let's use the Wikipedia nomenclature and call the rank generating function (that finds the rank for a given word $i$ from a (word, count) tuple list $X$, or a document vector $\vec{x}$) $rg$. Second, lets define that distance $d$ between the same word $i$ among the two documents as $d_i = rg(A, i) - rg(B, i)$. That is, $d$ the difference among the two ranks, zero if equal, and non-zero otherwise. With this, the coefficient can be calculated from whole numbers as:

$$ \rho_{A,B} = 1 - \frac{6-\sum d_i^2}{n(n^2-1)} $$

Note that this formulation has a strong requirement: All ranks must be distinct, so even for ties (if two words have the same count in the same document), you need to assign them distinct ranks; I suggest, you use alphanumeric ordering in those cases. And for words that only occur in one document, you place them in the last position(s) in the other document (again using the same alphanumeric ordering). It should be noted that by re-weighting your counts with TF-IDF before calculating this similarity, you can have far less ties among words with non-zero counts.

If you want to maintain ties (i.e., do not want to "artificially" make all ranks distinct) or if you are using cutoffs to remove some of the (word, count) tuples or selecting only the top $n$ most frequent words, however, you should be using the standard formula for $\rho$ (and define $rg$ as a function that generates the complete rank vector for all your document's alphanumerically ordered (word, count) tuples $X$ in the document vector $\vec{x}$):

$$ \rho_{A,B} = \frac{cov(rg(\vec{a}), rg(\vec{b}))}{\sigma_{rg_A} \sigma_{rg_B}} $$

Where $cov$ is the covariance among the ranks of the the two documents, and $\sigma_{rg_X}$ is the standard deviation of the (possibly cut-off) ranks $rg$ (with ties) of document $X$.

In a nutshell, you could see this approach as half-way between the Jaccard similarity and the Cosine similarity. Particularly, it is (a bit more - see next measure) robust against distributional differences between word counts among documents, while still taking overall word frequency into account. However, in most works, Cosine similarity seems to out-perform Spearman's rank correction - but you should test this, and might get good results with TF-IDF and Spearman, while, as said, this approach does not require you to do length normalization of your document vectors.

4. (Pearson's $\chi^2$ test-based) $\chi^2$ distance

So far, all our similarity measures assume the homogeneity of word frequencies, that is assuming that the variances of our word counts are equal among all documents of a collection (a "corpus"), something that is (hopefully, kind of intuitively) not the case. That is, earlier, Kilgarriff (1997) had demonstrated that the $\chi^2$ is a better fit to compare word counts than our above measures. Note that if you are following current research, for corpus comparisons today (e.g., to do feature selection), however, you probably should be using the Bootstrap test instead of $\chi^2$.

Kilgarriff's $\chi^2$ comparison can be applied just as well to documents (by assuming that there are only two "classes", your two documents, and therefore, $d.f. = 1$), and due to its robustness it might be preferable over the similarity measures shown so far. Note that this approach gives you a distance so to convert this value to a similarity, you'd have to take its inverse (i.e., the larger this distance, the smaller the document similarity). Let us define the count of all words in a document $X$ as $n_X = \sum x_i$ and total of both documents $A$ and $B$ as $n = n_A + n_B$. Then, a $\chi^2$-statistic-based distance for two documents (document vectors) can be derived from Pearson's base formula $\sum \frac{(O_i-E_i)^2}{E_i}$ as:

$$ \chi^2_{A,B} = n \left[ \sum{ \frac{a_i^2}{n_A(a_i+b_i)} } + \sum{ \frac{b_i^2}{n_B(a_i+b_i)} } \right] - n $$

However, this calculation is computationally far more costly to run, probably in itself explaining why most approaches stick to Cosine similarity, and even more so if you can verify that your classification/retrieval/clustering results don't gain from this latter distance measure. Also, as shown by the linked paper, this distance measure does not seem to out-compete Cosine similarity with TF-IDF reweighing. But note that the linked paper uses the "raw" term frequency counts to calculate this distance measure and compares that to TF-IDF re-weighted Cosine similarity. As discussed already, it usually is a good idea to first normalize the document vectors on their word counts (i.e., lengths) to get good results, i.e., transform $X / n_X$ first (and you might even try applying TF-IDF document vector re-weighting before that, too) in which case the above formula simplifies (a bit) to:

$$ \chi^2_{A,B} = 2 \left[ \sum{ \frac{a_i^2}{a_i+b_i} } + \sum{ \frac{b_i^2}{a_i+b_i} } \right] - 2 $$