Calculate Correlation/Distance Between Two Sets of Binary Vectors

Question

Given two sets of binary vectors, what are some optimal ways to calculate their correlation? For example,

Set A:

[1,1,1,0,0,0]

[1,0,1,0,1,0]

[0,0,1,1,1,1]

Set B:

[1,1,1,0,0,0]

[1,0,1,0,1,0]

[1,1,1,1,0,0]

Here Sets A and B both have two identical binary vectors ([1,1,1,0,0,0] and [1,0,1,0,1,0]), and two exclusive binary vectors ([0,0,1,1,1,1] and [1,1,1,1,0,0]).

One approach would be to create a new binary vector that represents if an item in one set (in this case a bitvector) was found in the other set. For example, we could represent the correlation from B to A as [1,1,0], as the first two items in B are distinctly found in Set A while the third is not. Although this works, it seems to oversimplify the problem.

Another approach might be, for each item in one set, find an item in the other set with the highest correlation score and place the result in a vector. If we used a hamming distance as our metric here (just as an example - I know Hamming Distance is a distance metric not a correlation metric), then we could represent the correlation from B to A as [0,0,1], as the first two items in Set B can be associated with an item in A with an optimal hamming score of 0, and the third item in Set B can be associated with an item in A with an optimal hamming score of 1.

This seems a bit better, but ironically in this example the third item in Set B is more closely correlated with the first item in Set A. This isn't necessarily a problem as the set items may be unordered, but in practice (for my purposes) it is unlikely that an element of one set will have two matches from another set, particularly if it as already been matched explicitly.

For a practical example, consider a machine that emits a set of binary patterns of equal length. Now observe another machine that also emits a set of binary patterns of the same length. The patterns are distinct, but the sets are unordered. What is the best way to calculate the correlation between the two machines, such that you can determine how identical machine B is to machine A?

I've found some great algorithms for calculating distance and correlation for binary vectors (Distance Metrics For Binary Vectors), but nothing that works on sets of binary vectors. I would like to combine these techniques into something that works on sets as well.

Any thoughts on this? Should I just go with one of the two approaches I mentioned? Also, if this question is better suited for a different stack exchange please let me know. Thanks.

Answer 1

This problem is not exactly a binary comparison problem. The binary comparison problem would be the comparison of two vectors of binary values. In term of machine learning, what you call a binary comparison correspond to the binary classification score. Here you want to compare matrices. You can continue to see a matrix as a point-by-point stuff, but you can also see it row-wise or column-wise, or globally. What should be done is a comparison of either

• point-wise comparison (it seems it's what you have done already)
• vector-wise comparison (when you calculate e.g. the cosine similarity between rows) : this ends up with a row-by-row sized matrix, that eventually leads to global score (by e.g. averaging over all cosine similarities)
• column- or row-wise comparison, by supposing statistical independence among the column and or rows (see below)
• global-wise comparison, by comparing the entire matrix structure among the different matrices

Note a few things:

• what applies to rows can apply to columns (you can do the cosine similarity of columns, why not?)
• one can construct the contingency/confusion matrix for data point-wise, simply by counting the number of times $\delta\left(A_{ij}=1\right) = \delta\left(B_{ij}=1\right)$ (true positive), $\delta\left(A_{ij}=1\right) = \delta\left(B_{ij}=0\right)$ (false negative or false positive) $\delta\left(A_{ij}=0\right) = \delta\left(B_{ij}=1\right)$ (false positive or false negative, respectively) and $\delta\left(A_{ij}=0\right) = \delta\left(B_{ij}=0\right)$ (true negative), where $\delta$ is the indicatrice function (it is counting after all)
• one can construct the contingency/confusion matrix for row-wise structure, by counting over columns e.g. $\delta\left(A_{i\cdot}=1\right)=\delta\left(B_{i\cdot}=1\right)$, ... This procedure ends up with a true positive like vector of size given by the number of rows of $A$ or $B$ (both having the same size), and $A_{i\cdot}$ is the marginal laws regarding rows
• one can construct the contingency/confusion matrix for column-wise structure, by counting over rows e.g. $\delta\left(A_{\cdot j}=1\right)=\delta\left(B_{\cdot j}=1\right)$, ... This procedure ends up with a true positive like vector of size given by the number of columns of $A$ or $B$ (both having the same size), and $A_{\cdot j}$ is the marginal laws regarding columns

A nice approach to understand all these concepts is the multi-label classification task, that naturally ends-up with the comparison of two matrices. In its simplest form the multi-label classification correspond to the comparison of two binary matrices (I mean matrices where only $0$ or $1$ appears, some multi-label classification may have higher values as well). In the classification terminology, if $A$ is the true matrix and $B$ is the predicted matrix, then the true/false positive/negative naming follows the first convention given above.

Answer 2

I ended up approaching this problem by finding the union of the two sets, the items in Set A but not Set B, and the items in Set B but not Set A. From the cardinality of these results I calculated the a, b, c metrics identified in this article and used algorithms such as Jaccard, Dice, and Sorgenfrei to calculate the correlation between the two sets.