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
à propos de l'auteur
Dr. Benjamin Anderson
Il est un professeur de statistiques à la retraite devenu éducateur dévoué sur Statorials. Avec une vaste expérience et une expertise dans le domaine des statistiques, je m'engage à partager mes connaissances pour responsabiliser les étudiants grâce à Statorials. Lire plus