Une introduction à la similarité Jaro-Winkler (définition et exemple)

En statistique, la similarité Jaro-Winkler est un moyen de mesurer la similarité entre deux chaînes.

La similarité Jaro (sim _j ) entre deux chaînes est définie comme :

sim _j = 1/3 * ( m /|s ₁ | + m/|s ₂ | + (mt)/m )

où:

• m : Nombre de caractères correspondants
  • Deux caractères de s ₁ et s ₂ sont considérés comme correspondant s’ils sont identiques et pas plus éloignés de [max(|s ₁ |, |s ₂ |) / 2] – 1 caractères l’un de l’autre.
• |s ₁ | , |s ₂ | : La longueur des première et deuxième chaînes, respectivement
• t : Nombre de transpositions
  • Calculé comme le nombre de caractères correspondants (mais dans un ordre de séquence différent) divisé par 2.

La similarité Jaro-Winkler (sim _w ) est définie comme :

sim _w = sim _j + lp(1 – sim _j )

où:

• sim _j : La similarité Jaro entre deux chaînes, s ₁ et s ₂
• l : Longueur du préfixe commun en début de chaîne (max 4 caractères)
• p : Facteur d’échelle indiquant dans quelle mesure le score est ajusté à la hausse pour avoir des préfixes communs. Généralement, cela est défini comme p = 0,1 et ne doit pas dépasser p = 0,25.

La similarité Jaro-Winkler entre deux chaînes est toujours comprise entre 0 et 1 où :

• 0 indique aucune similitude entre les chaînes
• 1 indique que les chaînes correspondent exactement

Remarque : La distance Jaro-Winkler serait définie comme 1 – sim _w .

L’exemple suivant montre comment calculer la similarité Jaro-Winkler entre deux chaînes en pratique.

Exemple : calcul de la similarité Jaro-Winkler entre deux chaînes

Supposons que nous ayons les deux chaînes suivantes :

• Chaîne 1 (s ₁ ) : souris
• Chaîne 2 (s ₂ ) : muette

Tout d’abord, calculons la similarité Jaro entre ces deux chaînes :

sim _j = 1/3 * ( m /|s ₁ | + m/|s ₂ | + (mt)/m )

où:

• m : Nombre de caractères correspondants
  • Deux caractères de s ₁ et s ₂ sont considérés comme correspondant s’ils sont identiques et pas plus éloignés de [max(|s ₁ |, |s ₂ |) / 2] – 1 caractères l’un de l’autre.

Dans ce cas, [max(|s ₁ |, |s ₂ |) / 2] – 1 est calculé comme 5/2 – 1 = 1,5. Nous définirions trois lettres comme correspondant : m, u, e. Ainsi, m = 3 .

• |s ₁ | , |s ₂ | : La longueur des première et deuxième chaînes, respectivement

Dans ce cas, |s ₁ | = 5 et |s ₁ | = 4 .

• t : Nombre de transpositions
  • Calculé comme le nombre de caractères correspondants (mais dans un ordre de séquence différent) divisé par 2.

Dans ce cas, il y a trois caractères correspondants mais ils sont déjà dans le même ordre séquentiel, donc t = 0 .

Ainsi, nous calculerions la similarité de Jaro comme suit :

sim _j = 1/3 * ( 3/5 + 3/4 + (3-0)/3 ) = 0,78333.

Ensuite, calculons la similarité Jaro-Winkler (sim _w ) comme suit :

sim _w = sim _j + lp(1 – sim _j )

Dans ce cas, on calculerait :

sim _w = 0,78333 + (1)*(0,1)(1 – 0,78333) = 0,805.

La similarité Jaro-Winkler entre les deux chaînes est de 0,805 .

Puisque cette valeur est proche de 1, cela nous indique que les deux chaînes sont très similaires.

Nous pouvons confirmer que cela est correct en calculant la similarité de Jaro-Winkler entre les deux chaînes de R :

library(stringdist)

#calculate Jaro-Winkler similarity between 'mouse' and 'mute'
1 - stringdist("mouse", "mute", method = "jw", p=0.1)

[1] 0.805

Cela correspond à la valeur que nous avons calculée manuellement.

Ressources additionnelles

Les didacticiels suivants expliquent comment calculer d’autres métriques de similarité :

Une introduction à la dissemblance de Bray-Curtis
Une introduction à l’indice de similarité Jaccard