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 1 | + m/|s 2 | + (mt)/m )

où:

  • m : Nombre de caractères correspondants
    • Deux caractères de s 1 et s 2 sont considérés comme correspondant s’ils sont identiques et pas plus éloignés de [max(|s 1 |, |s 2 |) / 2] – 1 caractères l’un de l’autre.
  • |s 1 | , |s 2 | : 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 1 et s 2
  • 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 1 ) : souris
  • Chaîne 2 (s 2 ) : muette

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

sim j = 1/3 * ( m /|s 1 | + m/|s 2 | + (mt)/m )

où:

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

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

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

Dans ce cas, |s 1 | = 5 et |s 1 | = 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

Ajouter un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *