Indice et distance de Jaccard

Summarize Timeline Fact Check

L'indice de Jaccard (ou coefficient de Jaccard, appelé « coefficient de communauté » dans la publication d'origine^[2]) est le rapport entre le cardinal (la taille) de l'intersection des ensembles considérés et le cardinal de l'union des ensembles. Il permet d'évaluer la similarité entre les ensembles. Soit deux ensembles ${\displaystyle A}$ et ${\displaystyle B}$, l'indice est :

${\displaystyle J(A,B)={\frac {|A\cap B|}{|A\cup B|}}}$.

La distance de Jaccard mesure la dissimilarité entre les ensembles. Elle consiste simplement à soustraire l'indice de Jaccard à 1 :${\displaystyle J_{\delta }(A,B)=1-J(A,B)={{|A\cup B|-|A\cap B|} \over |A\cup B|}={{|A\,\Delta \,B|} \over |A\cup B|}}$  où ${\displaystyle \Delta }$ est la différence symétrique.

Summarize Timeline Fact Check

L'extension à ${\displaystyle n}$ ensembles de l'indice de Jaccard s'étend comme suit :

${\displaystyle J(S_{1},S_{2},\dotsc ,S_{n})={\frac {|S_{1}\cap S_{2}\cap \dotsb \cap S_{n}|}{|S_{1}\cup S_{2}\cup \dotsb \cup S_{n}|}}}$.

De la même manière que pour l'indice, la généralisation de la distance de Jaccard devient :

${\displaystyle J_{\delta }(S_{1},S_{2},\dotsc ,S_{n})=1-J(S_{1},S_{2},\dotsc ,S_{n})={\frac {|S_{1}\cup S_{2}\cup \dotsb \cup S_{n}|-|S_{1}\cap S_{2}\cap \dotsb \cap S_{n}|}{|S_{1}\cup S_{2}\cup \dotsb \cup S_{n}|}}}$.

Summarize Timeline Top Qs Fact Check

L'indice de Jaccard est utile pour étudier la similarité entre des objets constitués d'attributs binaires.

Soit deux séquences ${\displaystyle A}$ et ${\displaystyle B}$, chacune avec ${\displaystyle n}$ attributs binaires. Chaque attribut peut être à 0 ou 1. On a ainsi :

${\displaystyle A=(a_{1},a_{2},...,a_{n})~}$ ;

${\displaystyle B=(b_{1},b_{2},...,b_{n})~}$.

On définit plusieurs quantités qui caractérisent les deux ensembles :

${\displaystyle M_{11}~}$ représente le nombre d'attributs qui valent 1 dans A et 1 dans B ;

${\displaystyle M_{01}~}$ représente le nombre d'attributs qui valent 0 dans A et 1 dans B ;

${\displaystyle M_{10}~}$ représente le nombre d'attributs qui valent 1 dans A et 0 dans B ;

${\displaystyle M_{00}~}$ représente le nombre d'attributs qui valent 0 dans A et 0 dans B.

Chaque paire d'attributs doit nécessairement appartenir à l'une des quatre catégories, de telle sorte que :

${\displaystyle M_{11}+M_{01}+M_{10}+M_{00}=n~}$.

L'indice de Jaccard devient :

${\displaystyle J={M_{11} \over M_{01}+M_{10}+M_{11}}~}$.

En utilisant ces deux dernières expressions, on obtient :

${\displaystyle J={M_{11} \over n-M_{00}}~}$.

Il suffit donc de ne calculer que les nombres d'attributs :

• valant 1 dans tous les ensembles ;
• valant 0 dans tous les ensembles.

La dernière écriture de cette formule, faisant intervenir ${\displaystyle n}$, est généralisable pour l'étude de similarité de plusieurs ensembles binaires (en calculant ${\displaystyle M_{00...00}}$ et ${\displaystyle M_{11..11}}$ avec autant de 0 et de 1 que d'ensembles).

La distance de Jaccard devient :

${\displaystyle J_{\delta }={M_{01}+M_{10} \over M_{01}+M_{10}+M_{11}}}$.

Exemple

${\displaystyle A=(1,0,1,0,0,0,0)~}$

${\displaystyle B=(1,0,0,1,0,1,1)~}$

${\displaystyle M_{11}=1~}$

${\displaystyle M_{00}=2~}$

${\displaystyle M_{01}=3~}$

${\displaystyle M_{10}=1~}$

${\displaystyle J={\frac {1}{3+1+1}}=0,2}$

${\displaystyle J_{\delta }={\frac {3+1}{3+1+1}}=0,8=1-J}$

En utilisant l'écriture de la formule faisant intervenir ${\displaystyle n}$ (plus rapide) :

${\displaystyle n=7~}$

${\displaystyle M_{11}=1~}$

${\displaystyle M_{00}=2~}$

${\displaystyle J={\frac {1}{7-2}}=0,2}$

${\displaystyle J_{\delta }=1-J=1-{\frac {1}{7-2}}=0,8}$

• Similarité cosinus
• Distance de Levenshtein