Natural Language Processing for Fuzzy String Matching with Python

I datalogi er fuzzy string matching en teknik til at finde strenge, der svarer til et mønster tilnærmelsesvis (snarere end nøjagtigt). Med et andet ord er fuzzy string matching en type søgning, der finder overensstemmelser, selv når brugerne staver ord forkert eller kun indtaster en del af ordene til søgningen. Det er også kendt som tilnærmelsesvis strengmatchning.

Fuzzy string search kan bruges i forskellige applikationer, f.eks.:

• En stavekontrol og stavefejl-, slåfejlskorrektor. Hvis en bruger f.eks. indtaster “Missisaga” i Google, får han en liste over hits tilbage sammen med “Viser resultater for mississauga”. Det vil sige, at søgeforespørgslen returnerer resultater, selv om brugerens indtastning indeholder yderligere eller manglende tegn eller andre typer stavefejl.
• En software kan bruges til at kontrollere for dobbeltposter. For eksempel, hvis en kunde er opført flere gange med forskellige køb i databasen på grund af forskellige stavemåder af deres navn (f.eks. Abigail Martin vs. Abigail Martinez), en ny adresse eller et forkert indtastet telefonnummer.

At tale om dedupe, er det måske ikke så nemt, som det lyder, især hvis du har hundredtusindvis af poster. Selv Expedia gør det ikke 100 % rigtigt:

Dette indlæg vil forklare, hvad fuzzy string matching er sammen med dets anvendelsestilfælde og give eksempler ved hjælp af Pythons Fuzzywuzzy-bibliotek.

Hvert hotel har sin egen nomenklatur til at navngive sine værelser, og det samme scenarie gælder for online-rejsebureauer (OTA). Hvis Expedia f.eks. kalder et værelse på samme hotel for “Studio, 1 King Bed with Sofa bed, Corner”, kan Booking.com finde det sikkert at vise værelset som “Corner King Studio”.

Der er ikke noget galt her, men det kan føre til forvirring, når vi ønsker at sammenligne værelsespriser mellem OTA’er, eller når en OTA ønsker at sikre sig, at en anden OTA følger aftalen om prisparitet. Med andre ord, for at kunne sammenligne priser skal vi sikre os, at vi sammenligner æbler med æbler.

Et af de mest konsekvent frustrerende problemer for websteder og apps til prissammenligning er at forsøge at finde ud af, om to varer (eller hotelværelser) er for den samme ting, automatisk.

Fuzzywuzzy er et Python-bibliotek, der bruger Levenshtein Distance til at beregne forskellene mellem sekvenser i en brugervenlig pakke.

For at demonstrere, opretter jeg mit eget datasæt, dvs. for den samme hotelejendom tager jeg en værelsestype fra Expedia, lad os sige “Suite, 1 King Bed (Parlor)”, og så matcher jeg den med en værelsestype i Booking.com, som er “King Parlor Suite”. Med en smule erfaring vil de fleste mennesker vide, at det er det samme. Efter denne metode opretter jeg et lille datasæt med over 100 par af værelsestyper, som kan findes på Github.

Med dette datasæt skal vi teste, hvordan Fuzzywuzzy tænker. Med andre ord bruger vi Fuzzywuzzy til at matche records mellem to datakilder.

import pandas as pddf = pd.read_csv('room_type.csv')
df.head(10)

Datasættet er oprettet af mig selv, så, det er meget rent.

Der er flere måder at sammenligne to strenge i Fuzzywuzzy, lad os prøve dem en efter en.

• ratio , sammenligner hele strengens lighed, i rækkefølge.

from fuzzywuzzy import fuzz
fuzz.ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')

Dette fortæller os, at parret “Deluxe Room, 1 King Bed” og “Deluxe King Room” er ca. 62 % ens.

fuzz.ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')

Parret “Traditional Double Room, 2 Double Beds” og “Double Room with Two Double Beds” er ca. 69 % ens.

fuzz.ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')

Parret “Værelse med 2 dobbeltsenge (19. til 25. etage)” og “Værelse med to dobbeltsenge – beliggenhed (19. til 25. etage)” er ca. 74 % ens.

Jeg er skuffet over disse. Det viser sig, at den naive tilgang er alt for følsom over for mindre forskelle i ordrækkefølge, manglende eller ekstra ord og andre sådanne problemer.

• partial_ratio , sammenligner delvis strenglighed.

Vi bruger stadig de samme datapairer.

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)')

For mit datasæt giver sammenligning af delvis streng samlet set ikke bedre resultater. Lad os fortsætte.

• token_sort_ratio , ignorerer ordstilling.

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)')

Bedst indtil videre.

• token_set_ratio , ignorerer duplikerede ord. Det svarer til token sort ratio, men er lidt mere fleksibelt.

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)')

Det ser ud til, at token_set_ratio passer bedst til mine data. I henhold til denne opdagelse besluttede jeg at anvende token_set_ratio på hele mit datasæt.