Quando confrontiamo i prezzi delle camere d’albergo tra diversi siti web, dobbiamo essere sicuri di confrontare le mele con le mele
In informatica, la corrispondenza di stringhe fuzzy è la tecnica di trovare stringhe che corrispondono a un modello approssimativamente (piuttosto che esattamente). In un’altra parola, il fuzzy string matching è un tipo di ricerca che troverà le corrispondenze anche quando gli utenti scrivono male le parole o inseriscono solo parole parziali per la ricerca. È anche conosciuta come corrispondenza approssimativa delle stringhe.
La ricerca fuzzy delle stringhe può essere usata in varie applicazioni, come:
- Un correttore ortografico e un correttore di errori di battitura. Per esempio, un utente digita “Missisaga” in Google, una lista di risultati viene restituita insieme a “Mostra i risultati per mississauga”. Cioè, la query di ricerca restituisce risultati anche se l’input dell’utente contiene caratteri aggiuntivi o mancanti, o altri tipi di errori di ortografia.
- Un software può essere usato per controllare i record duplicati. Per esempio, se un cliente è elencato più volte con acquisti diversi nel database a causa di diverse ortografie del suo nome (cioè Abigail Martin contro Abigail Martinez) un nuovo indirizzo, o un numero di telefono inserito erroneamente.
Parlando di deduplicazione, potrebbe non essere così facile come sembra, in particolare se si hanno centinaia di migliaia di record. Anche Expedia non lo fa al 100%:
Questo post spiegherà cos’è il fuzzy string matching insieme ai suoi casi d’uso e darà degli esempi usando la libreria Fuzzywuzzy di Python.
Ogni hotel ha la sua nomenclatura per chiamare le sue camere, lo stesso scenario vale per le Online Travel Agency (OTA). Per esempio, una camera nello stesso hotel, Expedia chiama “Studio, 1 King Bed with Sofa bed, Corner”, Booking.com può trovare sicuro nel mostrare la camera semplicemente come un “Corner King Studio”.
Non c’è niente di sbagliato qui, ma potrebbe portare a confusione quando vogliamo confrontare il tasso di camera tra OTA, o un OTA vuole assicurarsi un altro OTA segue l’accordo di parità di tasso. In un’altra parola, per essere in grado di confrontare i prezzi, dobbiamo essere sicuri che stiamo confrontando mele con mele.
Uno dei problemi più costantemente frustranti per i siti web e le applicazioni di confronto dei prezzi è cercare di capire se due articoli (o camere d’albergo) sono per la stessa cosa, automaticamente.
Fuzzywuzzy è una libreria Python che usa la distanza di Levenshtein per calcolare le differenze tra sequenze in un pacchetto semplice da usare.
Per dimostrarlo, creo il mio set di dati, cioè, per la stessa struttura alberghiera, prendo un tipo di camera da Expedia, diciamo “Suite, 1 King Bed (Parlor)”, poi lo abbino a un tipo di camera in Booking.com che è “King Parlor Suite”. Con un po’ di esperienza, la maggior parte degli umani saprebbe che sono la stessa cosa. Seguendo questa metodologia, creo un piccolo set di dati con oltre 100 coppie di tipi di camera che si possono trovare su Github.
Utilizzando questo set di dati, stiamo per testare come Fuzzywuzzy pensa. In altre parole, stiamo usando Fuzzywuzzy per abbinare i record tra due fonti di dati.
import pandas as pddf = pd.read_csv('room_type.csv')
df.head(10)
La serie di dati è stata creata da me, quindi, è molto pulita.
Ci sono diversi modi per confrontare due stringhe in Fuzzywuzzy, proviamoli uno per uno.
-
ratio, confronta l’intera similarità delle stringhe, in ordine.
from fuzzywuzzy import fuzz
fuzz.ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')
Questo ci sta dicendo che la coppia “Deluxe Room, 1 King Bed” e “Deluxe King Room” sono circa il 62% uguali.
fuzz.ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')
La coppia “Traditional Double Room, 2 Double Beds” e “Double Room with Two Double Beds” sono circa il 69% uguali.
fuzz.ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')
La coppia “Camera, 2 letti matrimoniali (dal 19° al 25° piano)” e “Camera con due letti matrimoniali – Posizione (dal 19° al 25° piano)” sono circa il 74% uguali.
Sono deluso da questi. Si scopre che l’approccio ingenuo è troppo sensibile alle differenze minori nell’ordine delle parole, alle parole mancanti o extra, e ad altri problemi del genere.
-
partial_ratio, confronta la somiglianza parziale delle stringhe.
Stiamo ancora usando le stesse coppie di dati.
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)')
Per il mio set di dati, confrontare la stringa parziale non porta risultati migliori in generale. Continuiamo.
-
token_sort_ratio, ignora l’ordine delle parole.
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)')
Il migliore finora.
-
token_set_ratio, ignora le parole duplicate. È simile al token sort ratio, ma un po’ più flessibile.
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)')
Sembra che token_set_ratio sia il più adatto ai miei dati. In base a questa scoperta, ho deciso di applicare token_set_ratio a tutto il mio set di dati.