Indice et distance de Jaccard

Modèle:Voir homonymes L'indice et la distance de Jaccard sont deux métriques utilisées en statistiques pour comparer la similarité et la Modèle:Lien entre des échantillons. Elles sont nommées d'après le botaniste suisse Paul Jaccard.

L'indice de Jaccard peut également être désigné par le sigle IoU (de l'anglais Intersection over Union), notamment quand il est utilisé comme une métrique de performance dans une tâche de vision par ordinateur.

Description formelle

L'indice de Jaccard (ou coefficient de Jaccard, appelé « coefficient de communauté » dans la publication d'origine) 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 $A$ et $B$, l'indice est :

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

L'extension à $n$ ensembles est triviale :

$J(S_1,S_2,\dots ,S_n)=\frac{|S_1\cap S_2\cap \cdots \cap S_n|}{|S_1\cup S_2\cup \cdots \cup S_n|}$.

La distance de Jaccard mesure la dissimilarité entre les ensembles. Elle consiste simplement à soustraire l'indice de Jaccard à 1.

$J_{\delta }(A,B)=1-J(A,B)=\frac{|A\cup B|-|A\cap B|}{|A\cup B|}=\frac{|A\mathrm{\Delta }B|}{|A\cup B|}$  où $\mathrm{\Delta }$ est la différence symétrique.

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

$J_{\delta }(S_1,S_2,\dots ,S_n)=1-J(S_1,S_2,\dots ,S_n)=\frac{|S_1\cup S_2\cup \cdots \cup S_n|-|S_1\cap S_2\cap \cdots \cap S_n|}{|S_1\cup S_2\cup \cdots \cup S_n|}$.

Similarité entre des ensembles binaires

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

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

$A=(a_1,a_2,...,a_n)$ ;

$B=(b_1,b_2,...,b_n)$.

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

		A
		0	1
B	0	$M_{00}$	$M_{10}$
	1	$M_{01}$	$M_{11}$

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

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

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

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

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

L'indice de Jaccard devient :

$J=\frac{M_{11}}{M_{01}+M_{10}+M_{11}}$.

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

$J=\frac{M_{11}}{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 $n$, est généralisable pour l'étude de similarité de plusieurs ensembles binaires (en calculant $M_{00...00}$ et $M_{11..11}$ avec autant de 0 et de 1 que d'ensembles).

La distance de Jaccard devient :

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

Exemple

$A=(1,0,1,0,0,0,0)$

$B=(1,0,0,1,0,1,1)$

$M_{11}=1$

$M_{00}=2$

$M_{01}=3$

$M_{10}=1$

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

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

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

$n=7$

$M_{11}=1$

$M_{00}=2$

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

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

Voir aussi

• Similarité cosinus
• Distance de Levenshtein

Références

• Pang-Ning Tan, Michael Steinbach and Vipin Kumar, Introduction to Data Mining, 2005 Modèle:ISBN
• Tanimoto, T.T. (1957) IBM Internal Report 17th Nov. 1957.

Liens externes

• Modèle:En indice de Jaccard et diversité entre espèces
• Modèle:En Exemple de coefficient de Jaccard
• Modèle:En Introduction à la fouille de données
• Modèle:En SimMetrics, une implémentation des métriques de similarité
• Modèle:Fr Similarité et Duplicate content : L'indice de Jaccard