# Jaccard index, matrix notation

I have a matrix with rows representing events and columns representing users. The elements of the matrix are binary values indicating if a user has attended the event or not.

\begin{bmatrix}1&1&0&1&1\\1&1&0&0&1\\ 1&0&0&1&1\end{bmatrix}

I need matrix notation to compute the Jaccard distances between users.

\begin{align} J(U_1,U_2)=\frac{|U_1\cap U_2|}{|U_1\cup U_2|} \end{align}

To compute the numerator I can use the matrix operation \begin{align} A^T\times A \end{align}

Now my question is how to get the denominator of Jaccard index using the matrix notation.

Define the vectors \eqalign{ b &= A^T1 \cr p &= \exp(b) \cr } and the matrices \eqalign{ L &= \log(pp^T) \cr J &= (A^TA)\oslash(L-A^TA) \cr } Note that the log and exp functions are applied elementwise, $$\oslash$$ represents elementwise division, and $$1$$ is a vector of all ones.

The elements of the $$J$$-matrix are the Jaccard distances, i.e. $$\,\,J_{ik} = J(U_i,U_k)$$

The third column of your $$A$$-matrix is problematic since it results in $$\,J_{33}=\frac{0}{0}$$

There may be better ways of generating the $$L$$-matrix. However it is done, its elements must satisfy $$L_{ik} = b_i+b_k$$

Update

A much better way to calculate the $$L$$-matrix is $$L = b1^T + 1b^T = A^TN + N^TA$$ where $$N$$ is a matrix of all ones which has the same shape as $$A$$.

Now the $$J$$-matrix can be written as $$J=(A^TA)\oslash(A^TN + N^TA - A^TA)$$

• Being working on Jaccard index (see my recent question math.stackexchange.com/q/3173596), I just saw this rather old question and your rather recent answer. I propose a different approach. – Jean Marie Apr 5 at 22:39

There is a simpler way to compute the number of elements of all unions which is based on the De Morgan duality relationship :

$$S_i \cup S_j=(S_i^c \cap S_j^c)^c \tag{1}$$

(where $$^c$$ means "complementary set").

Let us keep the same name $$A$$ for the initial matrix.

We have first to constitute the matrix $$B$$ of complementary sets. This is simply done by replacing each entry $$A_{ij}$$ by $$1-A_{ij}$$. The corresponding matrix operation is $$B=U-A$$ where $$U$$ is a matrix of ones with the convenient size.

The second operation in (1) (taking the intersection of complementary sets) is done evidently by matrix operation $$C=B^TB$$.

Let us introduce notation $$|.|$$ for the number of elements of a set.

The generic entry $$C_{ij}$$ of $$C$$ is

$$C_{ij}=|S_i^c \cap S_j^c|$$

Thus

$$e-C_{ij}=|(S_i^c \cup S_j^c)\color{red}{^c}|\tag{2}$$

(where $$e$$ is the number of "events").

The matrix operation corresponding to (2) is $$Q=eU-C$$ where $$U$$ is again a matrix of ones with the convenient dimensions, reaching thus our objective.

Here is a Matlab program which does the work :

u=5;% number of users; ( = number of sets)
e=3;% number of events ( = number of elements)
A=[1 1 0 1 1
1 1 0 0 1
1 0 1 1 1];% data matrix (dimensions e x u)
P=A'*A; % P_{ij}=|S_i inter S_j|
B=ones(e,u)-A;
C=B'*B;
Q=e*ones(u,u)-C ; % Q_{ij}=|S_i union S_j|
Jac=P./Q, % matrix of Jaccard indices

• An equivalent shorter program might eliminate the variables (C,Q) and re-define (B), i.e. $${\mathrm{ B = A' * ones(e,u); \\ Jac = P \, ./ \, (B+B'-P); }}$$ – greg Apr 6 at 1:10
• I chose to use these "temporary" variables for didactic purposes. – Jean Marie Apr 6 at 8:06
• Thank you for your constructive remarks and +1 for your update part. – Jean Marie Apr 6 at 13:28