2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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)$$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jean Marie Apr 5 at 22:39
0
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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); }}$$ $\endgroup$ – greg Apr 6 at 1:10
  • $\begingroup$ I chose to use these "temporary" variables for didactic purposes. $\endgroup$ – Jean Marie Apr 6 at 8:06
  • $\begingroup$ Thank you for your constructive remarks and +1 for your update part. $\endgroup$ – Jean Marie Apr 6 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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