Lorsque nous comparons le prix d’une chambre d’hôtel entre différents sites Web, nous devons nous assurer que nous comparons des pommes avec des pommes
En informatique, la correspondance floue de chaînes de caractères est la technique qui consiste à trouver des chaînes de caractères qui correspondent approximativement (plutôt qu’exactement) à un modèle. En d’autres termes, la correspondance floue de chaînes de caractères est un type de recherche qui trouvera des correspondances même si les utilisateurs orthographient mal les mots ou ne saisissent que des mots partiels pour la recherche. Elle est également connue sous le nom de correspondance approximative de chaînes de caractères.
La recherche floue de chaînes de caractères peut être utilisée dans diverses applications, telles que :
- Un vérificateur d’orthographe et un correcteur d’erreurs d’orthographe, de fautes de frappe. Par exemple, un utilisateur tape « Missisaga » dans Google, une liste d’occurrences est retournée avec « Afficher les résultats pour mississauga ». C’est-à-dire que la requête de recherche renvoie des résultats même si la saisie de l’utilisateur contient des caractères supplémentaires ou manquants, ou d’autres types d’erreurs d’orthographe.
- Un logiciel peut être utilisé pour vérifier les enregistrements en double. Par exemple, si un client est répertorié plusieurs fois avec différents achats dans la base de données en raison de différentes orthographes de son nom (c’est-à-dire Abigail Martin vs Abigail Martinez) une nouvelle adresse, ou un numéro de téléphone saisi par erreur.
En parlant de déduplication, cela peut ne pas être aussi facile qu’il n’y paraît, en particulier si vous avez des centaines de milliers d’enregistrements. Même Expedia ne le fait pas à 100% :
Ce billet expliquera ce qu’est la correspondance floue de chaînes de caractères ainsi que ses cas d’utilisation et donnera des exemples en utilisant la bibliothèque Fuzzywuzzy de Python.
Chaque hôtel a sa propre nomenclature pour nommer ses chambres, le même scénario s’applique aux agences de voyages en ligne (OTA). Par exemple, une chambre dans le même hôtel, Expedia appelle « Studio, 1 King Bed with Sofa bed, Corner », Booking.com peut trouver sûr de montrer la chambre simplement comme un « Corner King Studio ».
Il n’y a rien de mal ici, mais cela pourrait conduire à une confusion lorsque nous voulons comparer le taux de la chambre entre les OTA, ou une OTA veut s’assurer qu’une autre OTA suit l’accord de parité des taux. En d’autres termes, pour pouvoir comparer le prix, nous devons nous assurer que nous comparons des pommes avec des pommes.
L’un des problèmes les plus constamment frustrants pour les sites Web et les applications de comparaison de prix est d’essayer de déterminer si deux articles (ou chambres d’hôtel) sont pour la même chose, automatiquement.
Fuzzywuzzy est une bibliothèque Python qui utilise la distance de Levenshtein pour calculer les différences entre les séquences dans un package simple à utiliser.
Pour démontrer, je crée mon propre ensemble de données, c’est-à-dire que pour la même propriété hôtelière, je prends un type de chambre d’Expedia, disons « Suite, 1 King Bed (Parlor) », puis je le fais correspondre à un type de chambre dans Booking.com qui est « King Parlor Suite ». Avec un peu d’expérience, la plupart des humains sauront qu’il s’agit de la même chose. Suivre cette méthodologie, je crée un petit ensemble de données avec plus de 100 paires de type de chambre qui peut être trouvé sur Github.
En utilisant cet ensemble de données, nous allons tester comment Fuzzywuzzy pense. En d’autres termes, nous utilisons Fuzzywuzzy pour faire correspondre des enregistrements entre deux sources de données.
import pandas as pddf = pd.read_csv('room_type.csv')
df.head(10)
L’ensemble de données a été créé par moi-même, donc, il est très propre.
Il y a plusieurs façons de comparer deux chaînes de caractères dans Fuzzywuzzy, essayons-les une par une.
-
ratio, compare la similarité de la chaîne entière, dans l’ordre.
from fuzzywuzzy import fuzz
fuzz.ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')
Ceci nous indique que la paire « Chambre de luxe, 1 grand lit » et « Chambre de luxe avec grand lit » est identique à environ 62%.
fuzz.ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')
La paire « Chambre double traditionnelle, 2 grands lits » et « Chambre double avec deux grands lits » est identique à environ 69%.
fuzz.ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')
La paire « Chambre, 2 lits doubles (19e à 25e étages) » et « Deux lits doubles – Chambre de localisation (19e à 25e étages) » sont environ 74% identiques.
Je suis déçu par ceux-ci. Il s’avère que l’approche naïve est beaucoup trop sensible aux différences mineures dans l’ordre des mots, aux mots manquants ou supplémentaires, et à d’autres problèmes de ce type.
-
partial_ratio, compare la similarité de chaîne partielle.
Nous utilisons toujours les mêmes paires de données.
fuzz.partial_ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')
fuzz.partial_ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')
fuzz.partial_ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')
Pour mon ensemble de données, la comparaison de chaîne partielle n’apporte pas de meilleurs résultats dans l’ensemble. Continuons.
-
token_sort_ratio, ignore l’ordre des mots.
fuzz.token_sort_ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')
fuzz.token_sort_ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')
fuzz.token_sort_ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')
Le meilleur jusqu’ici.
-
token_set_ratio, ignore les mots dupliqués. Il est similaire avec token sort ratio, mais un peu plus flexible.
fuzz.token_set_ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')
fuzz.token_set_ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')
fuzz.token_set_ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')
Il semble que token_set_ratio soit le mieux adapté à mes données. Selon cette découverte, j’ai décidé d’appliquer token_set_ratio à l’ensemble de mes données.