Natural Language Processing for Fuzzy String Matching with Python

Inom datavetenskap är fuzzy strängmatchning tekniken för att hitta strängar som matchar ett mönster ungefärligt (snarare än exakt). Med ett annat ord är fuzzy strängmatchning en typ av sökning som hittar träffar även när användaren stavar fel eller bara skriver in en del av orden i sökningen. Det kallas också ungefärlig strängmatchning.

Fuzzy string search kan användas i olika tillämpningar, t.ex.:

• En stavningskontroll och rättare av stavfel och felskrivningar. Om en användare t.ex. skriver in ”Missisaga” i Google får han en lista med träffar tillsammans med ”Visar resultat för mississauga”. Det vill säga, sökfrågan returnerar resultat även om användarens inmatning innehåller ytterligare eller saknade tecken, eller andra typer av stavfel.
• En programvara kan användas för att kontrollera om det finns dubbla poster. Till exempel om en kund är listad flera gånger med olika inköp i databasen på grund av olika stavningar av namnet (dvs. Abigail Martin vs Abigail Martinez), en ny adress eller ett felaktigt inmatat telefonnummer.

Apropå dedupe är det kanske inte så lätt som det låter, särskilt inte om du har hundratusentals poster. Inte ens Expedia gör det 100 procent rätt:

Detta inlägg kommer att förklara vad fuzzy string matching är tillsammans med dess användningsområden och ge exempel med hjälp av Pythons Fuzzywuzzy-bibliotek.

Varje hotell har sin egen nomenklatur för att namnge rummen, och samma scenario gäller för resebyråer på nätet (OTA). Expedia kallar till exempel ett rum på samma hotell för ”Studio, 1 King Bed med bäddsoffa, Corner”, men Booking.com kan vara säker på att visa rummet som ”Corner King Studio”.

Det är inget fel här, men det kan leda till förvirring när vi vill jämföra rumspriserna mellan OTA:s, eller när en OTA vill försäkra sig om att en annan OTA följer avtalet om prisjämlikhet. Med andra ord, för att kunna jämföra priser måste vi se till att vi jämför äpplen med äpplen.

En av de mest konsekvent frustrerande frågorna för webbplatser och appar för prisjämförelser är att försöka ta reda på om två artiklar (eller hotellrum) är för samma sak, automatiskt.

Fuzzywuzzy är ett Pythonbibliotek som använder Levenshtein Distance för att beräkna skillnaderna mellan sekvenser i ett lättanvänt paket.

För att demonstrera skapar jag min egen datamängd, det vill säga för samma hotellfastighet tar jag en rumstyp från Expedia, låt oss säga ”Suite, 1 King Bed (Parlor)”, och sedan matchar jag den med en rumstyp på Booking.com som är ”King Parlor Suite”. Med lite erfarenhet skulle de flesta människor veta att det är samma sak. Efter denna metodik skapar jag en liten datamängd med över 100 rumstypspar som finns på Github.

Med hjälp av denna datamängd ska vi testa hur Fuzzywuzzy tänker. Med andra ord ska vi använda Fuzzywuzzy för att matcha poster mellan två datakällor.

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

Databasuppsättningen har skapats av mig själv, så den är mycket ren.

Det finns flera sätt att jämföra två strängar i Fuzzywuzzy, låt oss prova dem en efter en.

• ratio , jämför hela stränglikheten, i tur och ordning.

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

Detta säger oss att paret ”Deluxe Room, 1 King Bed” och ”Deluxe King Room” är ungefär 62% lika.

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

Paret ”Traditional Double Room, 2 Double Beds” och ”Double Room with Two Double Beds” är ungefär 69% lika.

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

Paret ”Rum med två dubbelsängar (19:e till 25:e våningen)” och ”Rum med två dubbelsängar – läge (19:e till 25:e våningen)” är ungefär 74 % lika.

Jag är besviken på dessa. Det visar sig att det naiva tillvägagångssättet är alldeles för känsligt för små skillnader i ordföljd, saknade eller extra ord och andra sådana problem.

• partial_ratio , jämför partiell stränglikhet.

Vi använder fortfarande samma datapar.

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

För min datauppsättning ger jämförelser av partiella strängar inte bättre resultat totalt sett. Låt oss fortsätta.

• token_sort_ratio , ignorerar ordföljd.

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

Bäst hittills.

• token_set_ratio , ignorerar dubblerade ord. Det liknar token sort ratio, men är lite mer flexibelt.

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 ut som om token_set_ratio passar bäst för mina data. Enligt denna upptäckt bestämde jag mig för att tillämpa token_set_ratio på hela min datamängd.