Natural Language Processing for Fuzzy String Matching with Python

In der Informatik ist Fuzzy String Matching die Technik, Zeichenketten zu finden, die einem Muster annähernd (und nicht exakt) entsprechen. Mit anderen Worten: Fuzzy-String-Matching ist eine Art der Suche, die auch dann Übereinstimmungen findet, wenn Benutzer Wörter falsch schreiben oder nur Teilwörter für die Suche eingeben. Sie wird auch als ungefähre Zeichenkettensuche bezeichnet.

Die unscharfe Zeichenkettensuche kann in verschiedenen Anwendungen eingesetzt werden, wie z.B.:

• Eine Rechtschreibprüfung und Korrektur von Rechtschreibfehlern und Tippfehlern. Gibt ein Nutzer zum Beispiel „Missisaga“ in Google ein, wird eine Liste von Treffern zusammen mit „Zeige Ergebnisse für mississauga“ zurückgegeben. Das heißt, die Suchanfrage liefert auch dann Ergebnisse, wenn die Benutzereingabe zusätzliche oder fehlende Zeichen oder andere Arten von Rechtschreibfehlern enthält.
• Eine Software kann verwendet werden, um auf doppelte Einträge zu prüfen. Zum Beispiel, wenn ein Kunde aufgrund unterschiedlicher Schreibweisen seines Namens (z.B. Abigail Martin vs. Abigail Martinez), einer neuen Adresse oder einer irrtümlich eingegebenen Telefonnummer mehrfach mit verschiedenen Käufen in der Datenbank aufgeführt ist.

Als wir von Deduplizierung sprachen, war es nicht so einfach, wie es sich anhört, insbesondere wenn Sie hunderttausende von Datensätzen haben. Selbst Expedia macht es nicht zu 100% richtig:

In diesem Beitrag wird erklärt, was Fuzzy-String-Matching ist und welche Anwendungsfälle es gibt, und es werden Beispiele mit der Python-Bibliothek Fuzzywuzzy gegeben.

Jedes Hotel hat seine eigene Nomenklatur, um seine Zimmer zu benennen, dasselbe Szenario gilt für Online-Reisebüros (OTA). Zum Beispiel nennt Expedia ein Zimmer im selben Hotel „Studio, 1 King Bed with Sofa bed, Corner“, während Booking.com das Zimmer einfach als „Corner King Studio“ anzeigt.

Das ist nicht schlimm, könnte aber zu Verwirrung führen, wenn wir die Zimmerpreise zwischen OTAs vergleichen wollen, oder wenn ein OTA sicherstellen will, dass ein anderer OTA die Ratenparitätsvereinbarung einhält. Mit anderen Worten: Um Preise vergleichen zu können, müssen wir sicherstellen, dass wir Äpfel mit Äpfeln vergleichen.

Eines der frustrierendsten Probleme für Preisvergleichs-Websites und -Apps ist der Versuch, herauszufinden, ob zwei Artikel (oder Hotelzimmer) automatisch für dieselbe Sache sind.

Fuzzywuzzy ist eine Python-Bibliothek, die die Levenshtein-Distanz verwendet, um die Unterschiede zwischen Sequenzen in einem einfach zu bedienenden Paket zu berechnen.

Zur Veranschaulichung erstelle ich meinen eigenen Datensatz, d. h. für dasselbe Hotelobjekt nehme ich einen Zimmertyp von Expedia, sagen wir „Suite, 1 King Bed (Parlor)“, und vergleiche ihn dann mit einem Zimmertyp auf Booking.com, der „King Parlor Suite“ lautet. Mit ein wenig Erfahrung wissen die meisten Menschen, dass es sich um dasselbe handelt. Nach dieser Methode habe ich einen kleinen Datensatz mit über 100 Zimmertyp-Paaren erstellt, der auf Github zu finden ist.

Mit diesem Datensatz werden wir testen, wie Fuzzywuzzy denkt. Mit anderen Worten, wir verwenden Fuzzywuzzy, um Datensätze zwischen zwei Datenquellen abzugleichen.

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

Der Datensatz wurde von mir selbst erstellt, er ist also sehr sauber.

Es gibt mehrere Möglichkeiten, zwei Zeichenketten in Fuzzywuzzy zu vergleichen, probieren wir sie eine nach der anderen aus.

• ratio , vergleicht die gesamte Zeichenkettenähnlichkeit, in der Reihenfolge.

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

Dies sagt uns, dass das Paar „Deluxe Room, 1 King Bed“ und „Deluxe King Room“ zu 62% gleich sind.

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

Das Paar „Traditional Double Room, 2 Double Beds“ und „Double Room with Two Double Beds“ sind zu 69% gleich.

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

Das Paar „Zimmer, 2 Doppelbetten (19. bis 25. Etage)“ und „Zimmer mit zwei Doppelbetten – Lage (19. bis 25. Etage)“ sind zu 74 % identisch.

Ich bin enttäuscht. Es stellt sich heraus, dass der naive Ansatz viel zu empfindlich auf geringfügige Unterschiede in der Wortreihenfolge, fehlende oder zusätzliche Wörter und andere derartige Probleme reagiert.

• partial_ratio , vergleicht die Ähnlichkeit von Teilstrings.

Wir verwenden immer noch dieselben Datenpaare.

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 meinen Datensatz bringt der Vergleich von Teilstrings insgesamt keine besseren Ergebnisse. Fahren wir fort.

• token_sort_ratio , ignoriert die Wortreihenfolge.

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

Bislang das Beste.

• token_set_ratio , ignoriert doppelte Wörter. Es ist ähnlich wie das Token-Sortierverhältnis, aber etwas flexibler.

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

Sieht so aus, als ob token_set_ratio die beste Lösung für meine Daten ist. Nach dieser Entdeckung habe ich beschlossen, token_set_ratio auf meinen gesamten Datensatz anzuwenden.