Quantifying overlap between two categorical distributions with some non-identical categories

Question

I'm looking for a way to measure the overlap (or general similarity) between two categorical distributions in which some of the categories are shared between each and some are not. For example, if the counts for the two distributions look like this:

Distribution X
Category: a b c d
Count:    5 8 2 7

Distribution Y
Category: b c d e
Count:    6 9 5 3

Is there a statistic I can use to describe how similar these two distributions are? My first thought was Bhattacharyya distance (which I'm only vaguely familiar with), but that seems to be related to continuous quantitative distributions. Otherwise, what I can find for qualitative distributions through random Googling seem to all require that the two distributions have the same exact categories (e.g., Y should have the categories a b c d instead). I'd like to not exclude non-shared categories, though, as they're meaningful in my data.

EDIT: Another possibility I've come across is cross-entropy, but I don't understand it well enough to know if this is appropriate for this sort of data as most of what I find about cross-entropy seems to involve comparing how accurate two different classifiers are when applied to some data to be classified, but I don't have any classification task that I'm doing here.

Answer 1

You are probably looking for a similarity index. There are several that you can choose.

As a note, since you mentioned this, there are two problems with using cross-entropy for this:

1. Cross-entropy is not commutative, so if $H(p,q) \neq H(q,p)$, then it is not a similarity metric.
2. All distributions being compared would be need to have the same support. i.e., you cannot have any missing categories from any distributions/rows.

Cosine Similarity

One popular one is cosine similarity, which is often used with text data, where each "distribution" is a bag of words. For example,

text1 = "row row row your boat"
text2 = "big row"

word | text1 count | text2 count
row  |           3 |           1
your |           1 |           0
boat |           1 |           0
big  |           0 |           1

Essentially, you are calculating the "angle" between two vectors here. Since they are both positive values only, the "cosine similarity" ranges from 0 to 1.

In this case, it is

$$\frac{A · B}{||A|| * ||B||}$$

Or $\frac{3*1}{\sqrt{11} * \sqrt{2}} \approx0.64$

For your data, this value is about 0.69.

Transformation

One drawback to this might be if some categories had much higher counts/values. e.g., if category a was 100 times higher in your distributions, then the similarity would be very high, even if you consider the variation of all of the categories equally important. This is also why you often remove common words like "of" and "the" from being used when analyzing text data in this manner.

You may want to transform the vectors in this case. For each value, you can transform it using a variety of functions, including $\log{1+x}$, a binary indicator of presence, or some other method. I've used a square root function in the past with some success.

You may also want to divide each category by the sum of the overall counts, but this value is usually logarithmically scaled.

See this section on the wiki page on TF-IDF for more ideas on scaling values.

I've treated this process as feature/hyperparameter selection, so usually I will try out a few different methods, and then use cross-validation to determine which feature set is more useful. e.g., if you are classifying your distributions using some algorithm, then determining the features that determine their similarity can be selected using cross-validation.

Jaccard Index

Another metric is the Jaccard index, which looks at the number of shared elements between the sets, and then divides by the size of the union of the sets. This is not particularly useful in your case, since all elements are considered a 1 or 0 depending on whether or not they are present. Written out, the formula is

$$\frac{||A \cap B||}{||A \cup B||}$$

In the case of the above example, this would be 0.25, since only one element is shared out of all 4 elements ("row"). For your data, you would have a similarity of 0.8.

If there were more elements (preferably a small number), you could also add the number of elements that don't appear in either set to both the numerator and denominator to get the simple matching coefficient.

Possible Extension with values greater than 1

You could take the minimum value of each category in the numerator, and maximum in the denominator.

$$\frac{\sum{min(A_i,B_i)}}{\sum{max(A_i,B_i)}}$$

For my example, you would get a similarity of 0.167. For your data, you would get a similarity of 0.41.

If anyone knows if this already has a name, I'd like to know it.

Other options

Most other similarity measures I know require treating the data like network data, where you have a large number of categories and "distributions"/rows of data. A lot of these are meant to work with sparser data (i.e., most categories are 0 for most distributions/rows). However, these don't really make sense outside of the context of an entire data set. The similarity will (most likely) change each time you add/remove a "distribution"/row. e.g., PathSim.