Es ist wahrscheinlich nichts Neues für Sie, dass Daten als „modernes Gold“ betrachtet werden. Obwohl sich jeder der Bedeutung von Daten bewusst ist, gibt es immer noch viele Unternehmen, die nicht datengesteuert sind oder ihre Daten nicht nutzen können. Die Gründe dafür sind unterschiedlich, aber oft liegt es daran, dass die Daten nicht gut gespeichert, strukturiert oder sogar durchsuchbar sind, um sie nutzen zu können.
Daten können zwar gespeichert werden, aber Unternehmen speichern sie möglicherweise mehr als einmal oder aufgrund menschlicher Fehler ungenau. Dies führt natürlich zu einer schlechten Datenqualität, die Unternehmen ernsthaft schaden kann. Es wurde sogar festgestellt, dass Unternehmen durch ungenaue Daten durchschnittlich 15 Millionen US-Dollar pro Jahr verlieren.
Um datenbezogene Herausforderungen zu bewältigen, können Unternehmen auf automatisierte Lösungen zurückgreifen, die Daten aus zwei verschiedenen Datenquellen abgleichen können. Mit einer solchen Lösung lassen sich doppelte Daten und Ungenauigkeiten leicht beseitigen. An dieser Stelle kommt Fuzzy Matching ins Spiel.
Um dieses technische Konzept zu verstehen, werden wir uns die Zeit nehmen, um zu erklären, was es ist, warum es für moderne Organisationen notwendig ist und wie es implementiert werden kann.
Legen wir los!
Was ist Fuzzy Matching?
Fuzzy Matching (FM), auch bekannt als Fuzzy Logic Name Matching oder Approximate String Matching, ist eine Technik, die Benutzern hilft, eine ungefähre Übereinstimmung zwischen zwei verschiedenen Datenabschnitten oder sogar einer Textzeile zu finden und zu vergleichen. Diese Technik wird häufig durch Technologien wie künstliche Intelligenz (KI) und Machine Learning (ML) ermöglicht.
Technisch gesehen ist Fuzzy Matching ein String-Matching-Algorithmus (ein Algorithmus, der nach einer Zeichenkette innerhalb einer anderen Zeichenkette sucht) mit vorbestimmten Regeln, um doppelte Zeichenketten, Wörter oder Einträge zu finden, die einander am ehesten entsprechen. Mit Fuzzy Matching ist es zum Beispiel möglich, Namen, Wörter oder Zeichenketten zu finden, die abgekürzt, verkürzt oder falsch geschrieben sind.
Nehmen wir an, Sie wollen „Rechnungsnummer“ in einem Dokument finden, aber das Wort wurde als „Rechnungnummer“ falsch geschrieben oder als „Rechnungs-Nr.“ abgekürzt. In diesem Fall würden Sie bei der Suche nach „Rechnungsnummer“ keine exakte Übereinstimmung erhalten, was heißt, dass Sie nicht finden werden, was Sie suchen.
Mit einem Fuzzy-Matching-Algorithmus ist dies kein Problem, da der Algorithmus immer noch eine ungefähre Übereinstimmung mit dem falsch geschriebenen oder verkürzten Wort finden kann, indem er auf der Grundlage der „Editierkorrekturen“ eine Übereinstimmungsbewertung von 0-100 % liefert.
Eine Editierkorrektur ist eine Korrektur, die der FM-Algorithmus auf der Grundlage von Logik vornehmen muss, um eine bestimmte Zeichenfolge so anzupassen, dass sie mit einer anderen Zeichenfolge übereinstimmt.
Fuzzy Matching Korrekturen bearbeiten
Im Allgemeinen verwenden FM-Algorithmen die folgenden Schnittkorrekturen:
- Einfügen – Hinzufügen eines Buchstabens zur Vervollständigung des Wortes (z. B. „Rechnun“ wird zu „Rechnung“)
- Löschen – Entfernen eines Buchstabens aus einem Wort (z. B. „Rechnnung“ wird zu „Rechnung“)
- Substitution – Vertauschen eines Buchstabens, um ein Wort zu korrigieren (z. B. „Technung wird zu „Rechnung“)
- Transposition – Vertauschen von Buchstaben, um ein Wort zu korrigieren (z. B. „Rehcnung wird zu „Rechnung“)
Jeder Korrektur, die durchgeführt werden muss, wird eine „Bearbeitungsdistanz“ von 1 zugeschrieben. Die Bearbeitungsdistanzen beeinflussen die oben erwähnte Trefferquote. Wenn Sie beispielsweise eine Zeichenfolge mit 11 Zeichen haben und 2 Korrekturen vornehmen müssen, beträgt die endgültige Trefferquote 81,81 %.
Berechnung: 100%- 2 / 11= 81.81%
Neben diesen Korrekturen kann FM auch verwendet werden, um Zeichensetzungen, zusätzliche Wörter und fehlende Leerzeichen in Zeichenketten oder Texten zu korrigieren.
Um ein besseres Verständnis für die Funktionsweise von Fuzzy Matching und die Berechnung der Bearbeitungsdistanzen zu bekommen, werden im nächsten Abschnitt verschiedene Fuzzy Matching Algorithmen im Detail erläutert.
Fuzzy-Matching-Algorithmen
Fuzzy Matching fällt in die Kategorie der Methoden, für die es keinen spezifischen Algorithmus gibt, der alle Szenarien und Anwendungsfälle abdeckt. Daher werden wir einige der am häufigsten verwendeten und zuverlässigsten Fuzzy-Matching-Algorithmen für die Suche nach ungefähren Datenübereinstimmungen behandeln:
- Levenshtein-Distanz (LD)
- Hamming-Distanz (HD)
- Damerau-Levenshtein
Levenshtein-Distanz
Die Levenshtein-Distanz (LD) ist eine Fuzzy-Matching-Technik, die zwei Zeichenfolgen beim Vergleich und der Suche nach einer Übereinstimmung berücksichtigt. Je höher der Wert der Levenshtein-Distanz ist, desto weiter sind die beiden Zeichenfolgen oder „Begriffe“ von einer identischen Übereinstimmung entfernt.
Wie erhalten wir nun den Wert der Levenshtein-Distanz? Die LD zwischen den beiden Zeichenfolgen entspricht der Anzahl der Änderungen, die erforderlich sind, um eine Zeichenfolge in die andere umzuwandeln. Für die LD gelten das Einfügen, Löschen und Ersetzen eines einzelnen Zeichens als Bearbeitungsoperationen.
Nehmen wir an, Sie möchten die LD zwischen „Rechnungsnummer“ und „Rechnungs-Nr.“ messen. Der Abstand zwischen den beiden Begriffen ist „1 x u“, „2 x m“ und „1 x e“, was einem Abstand von 4 entsprechen würde. Warum? Weil Sie diese Zeichen hinzufügen müssten, um eine Übereinstimmung zu erreichen. Siehe die Beispiele unten.
Levenshtein-Abstand Beispiel
- Rechnungnummer → Rechnungsnummer (Einfügung von „s“) – Abstand: 1
- Rechnung numr → Rechnungsnummer (Einfügung von „m“ & „e“) – Abstand: 2
- Rechnung nr → Rechnungsnummer (Einfügung von „u, m, m, e“) – Abstand: 4
Hamming-Distanz
Die Hamming-Distanz (HD) unterscheidet sich nicht allzu sehr von der Levenshtein-Distanz. Die Hamming-Distanz wird häufig verwendet, um den Abstand zwischen zwei gleich langen Textabschnitten zu berechnen.
Die HD-Methode basiert auf der ASCII-Tabelle (American Standard Code for Information Interchange). Zur Berechnung des Abstandswertes verwendet der Hamming-Distanz-Algorithmus die Tabelle, um den Binärcode zu bestimmen, der jedem Buchstaben in den Zeichenketten zugeordnet ist.
Hamming-Abstand-Beispiel
Nehmen wir die folgenden Textzeichenfolgen „Number“ und „Lumber“ als Beispiel. Wenn wir versuchen, den HD zwischen den Zeichenfolgen zu bestimmen, ist der Abstand nicht 1, wie es mit dem Levenshtein-Algorithmus der Fall wäre. Stattdessen würde er 10 betragen. Das liegt daran, dass die ASCII-Tabelle einen Binärcode von (1001110) für den Buchstaben N und (1001100) für den Buchstaben L anzeigt.
Beispielrechnung:
D = N – L = 1001110 – 1001100 = 10
Damerau-Levenshtein
Das Damerau-Levenshtein-Verfahren misst auch den Abstand zwischen zwei Wörtern, indem es die erforderlichen Änderungen misst, die vorgenommen werden müssen, um ein Wort an das andere anzupassen. Diese Änderungen hängen von der Anzahl der Operationen ab, wie z. B. Einfügung, Löschung oder Ersetzung eines einzelnen Zeichens oder Transposition zweier benachbarter Zeichen.
Hier unterscheidet sich die Damerau-Levenshtein-Distanz von der regulären Levenshtein-Distanz, da sie zusätzlich zu den Einzelzeichen-Editieroperationen, auch Transpositionen berücksichtigt, um eine ungefähre Übereinstimmung zu finden (Fuzzy Match).
Damerau-Levenshtein Beispiel
Zeichenfolge 1: Rechnung
Zeichenfolge 2: Rehcnun
Operation 1: Transposition -> Vertauschen der Zeichen “h” und “c”
Operation 2: Einfügen eines “g” am Ende der Zeichenfolge 2
Da zwei Operationen erforderlich waren, um die beiden Wörter identisch zu gestalten, beträgt der Abstand 2. Vereinfacht ausgedrückt zählt jede Operation wie Einfügung, Löschung, Transposition usw. als ein Abstand von „1“. Mit der Levenshtein-Distanz müssten Sie jedoch drei Korrekturen vornehmen, was einem Abstand von 3 entspricht.
Alle oben genannten Fuzzy-Matching-Algorithmen unterscheiden sich natürlich in der Art und Weise, wie die Bearbeitungsdistanz berechnet wird. Dies ist der Grund, warum es keinen FM-Algorithmus gibt, der für alle geeignet ist. Von den drei vorgestellten Algorithmen ist die Levenshtein-Distanz jedoch der am häufigsten verwendete FM-Algorithmus in der Datenverwaltung und Datenwissenschaft.
Fuzzy Matching Anwendungsfälle
Es gibt eine Vielzahl von Möglichkeiten, FM in der Praxis einzusetzen, von denen einige in Ihrem täglichen Leben vorkommen. Sehen wir uns im Folgenden ein paar Beispiele an (die Liste ist nicht vollständig):
- Extraktion von Dokumentendaten
- Automatischer Vorschlag mit Rechtschreibprüfung
- Deduplizierung
- Genom-Sequenzierung
Extraktion von Dokumentendaten
Obwohl OCR, auch bekannt als Bild-zu-Text Extraktionstechnologie, heute fortschrittlicher ist als vor 10 oder sogar 20 Jahren, kann sie immer noch ungenaue Datenextraktionsergebnisse liefern. Da viele Unternehmen eine Vielzahl von Dokumenten in großen Mengen verarbeiten, können sie durch ungenaue Datenextraktionsergebnisse erhebliche Geldbeträge verlieren.
Zur Ergänzung der OCR-Software und zur Lösung dieses Problems kann Fuzzy Matching eingesetzt werden. In Fällen, in denen OCR beim Extrahieren bestimmter Datenfelder und Daten aus Dokumenten keine „exakte Übereinstimmung“ findet, kann Fuzzy Matching helfen, die nächstgelegene Übereinstimmung mit einer annähernden Zeichenfolgenübereinstimmung unter Verwendung der Levenshtein-Distanz zu finden.
Auf diese Weise können Unternehmen immer noch Daten aus Dokumenten extrahieren, anstatt dass die OCR-Software überhaupt keine Ergebnisse liefert, wenn keine exakte Übereinstimmung gefunden werden kann.
Automatischer Vorschlag mit Rechtschreibprüfung
Wahrscheinlich sind Sie in Ihrem Leben schon auf verschiedene Suchmaschinen gestoßen oder haben sie benutzt. Dabei ist Ihnen auch aufgefallen, dass Suchmaschinen uns manchmal, trotz falsch geschriebener Wörter oder Sätze, die Inhalte liefern, nach denen wir suchen.
Das geschieht nur, weil Suchmaschinen wie Google Fuzzy-Matching-Algorithmen verwenden. Google versteht, was Sie als Hauptanfrage eingeben wollten, und bietet Ihnen eine Option für das Suchwort an, während Sie in die Suchleiste tippen.
Zusammen mit KI oder ML hat Fuzzy Matching dazu beigetragen, Suchmaschinen wie Google und YouTube zu verbessern, um das Sucherlebnis zu verbessern.
Deduplizierung
Wie bereits erwähnt, leiden zahlreiche Unternehmen unter doppelten Daten, hauptsächlich aufgrund von Datenübertragungen, mangelnder Kontrolle oder Dateneingabefehlern. Sowohl identische Kopien eines Datensatzes (Name, Adresse, E-Mail, Telefonnummer usw.) als auch teilweise Duplikate sind in Unternehmen üblich.
Mit Fuzzy Matching können Unternehmen Daten zusammenführen, löschen oder reorganisieren, indem sie ungefähre Übereinstimmungen finden. So können Unternehmen ihre Datensätze und ihr Datenmanagement rationalisieren, was verschiedene Vorteile mit sich bringt, die später in diesem Blog erläutert werden.
Die Entduplizierung ist auch sehr nützlich, wenn Sie OCR-Modelle trainieren, um Informationen aus Dokumenten zu extrahieren. Durch das Entfernen doppelter Datenproben aus den Trainingsdatensätzen wird das Training effizienter und die Vorhersagegenauigkeit der OCR-Modelle verbessert sich erheblich.
Genomsequenzierung
Im Gesundheitswesen und in der Wissenschaft kann das Fuzzy Matching sehr hilfreich sein, insbesondere bei der Genomsequenzierung. Es ermöglicht Forschern, eine ungefähre Übereinstimmung mit einer bestimmten Genomsequenz zu finden, indem sie einen Algorithmus auf die Sequenz anwenden.
Mit dem Fuzzy-Matching-Algorithmus sind sie in der Lage, die nächstgelegene übereinstimmende Sequenz oder Sequenzmenge zu finden und anhand des Ergebnisses zu bestimmen, zu welchem Organismus die Sequenz gehört. Ein Beispiel wäre die Suche nach der nächsten Übereinstimmung mit einem bestimmten Bakterium oder Virus, um das richtige Heilmittel zu finden.
Mit anderen Worten: Fuzzy Matching kann Forschern helfen, ein Heilmittel für bestimmte Krankheiten zu finden. Interessant, oder?
Inzwischen sollte klar sein, dass die Verwendung von FM flexibel ist und in verschiedenen Anwendungsfällen eingesetzt werden kann. Was auch immer Ihr Anwendungsfall sein mag, es gibt verschiedene Vorteile, die Fuzzy Matching mit sich bringt.
Vorteile des Fuzzy Matching
Zu den häufigsten Vorteilen für Unternehmen, die Fuzzy Matching als Ansatz zur Identifizierung von Übereinstimmungen verwenden, gehören:
- Datengenauigkeit – Unternehmen können eine hohe Datenabgleichsgenauigkeit erreichen, da FM in der Lage ist, durch die Analyse der Zeichenketten und die Berechnung des „Bearbeitungs“-Abstandswertes mithilfe von Algorithmen nach ungefähren Übereinstimmungen zu suchen.
- Durchsuchbare Daten – Fuzzy Matching ermöglicht es den Nutzern, Übereinstimmungen zu finden, trotz der Abweichungen aufgrund von Fehlern wie Rechtschreibfehlern, falscher Großschreibung oder falscher Formatierung von Wörtern oder Zeichenfolgen.
- Flexibilität – Fuzzy-Logik-Algorithmen können auf vielfältige Weise helfen, selbst die komplexesten Probleme zu lösen.
- Saubere Datenbank – Fuzzy-Matching-Algorithmen können Unternehmen dabei helfen, doppelte Datensätze zu finden, um eine gesündere, sauberere und genauere Datenbank zu erhalten.
Nachteile des Fuzzy Matching
Nicht alles am Fuzzy String Matching ist perfekt. Im Gegenteil, FM weist verschiedene Einschränkungen auf, darunter:
- Falsche Verknüpfung – Obwohl Fuzzy Matching hervorragend geeignet ist, um ungefähre Übereinstimmungen zu finden, führt es manchmal zu einer hohen Anzahl von falsch positiven Ergebnissen, was zu falschen Verknüpfungen führt, insbesondere bei größeren Datenbanken.
- Erfordert Wartung – Die Algorithmen müssen ständig getestet und die Regeln aktualisiert werden, um einen genauen Zeichenkettenabgleich zu ermöglichen.
Obwohl es auch Nachteile gibt, bringt der Einsatz von Fuzzy Matching Unternehmen mehr Vorteile als Herausforderungen. Wie können Sie es also in Ihre eigenen Lösungen implementieren? Schauen wir uns das als Nächstes an!
Implementierung des Fuzzy Matching
Sie können Fuzzy-Matching-Algorithmen mit verschiedenen Programmiersprachen implementieren, darunter:
- Python – Die Fuzzywuzzy-Python-Bibliothek wendet den Levenshtein-Distanz-Ansatz an, um ein annäherndes String-Matching durchzuführen.
- Java – Es ist sehr schwierig, FM in Java zu implementieren, aber es ist über ein GitHub-Repository möglich, die Fuzzywuzzy-Bibliothek in Java zu implementieren.
- Excel – Einfache Implementierung von FM über Add-ons wie Exis Echo, Fuzzy Lookup und sogar unter Verwendung der nativen VLOOKUP-Funktion.
Natürlich ist es möglich, eigene Lösungen zu entwickeln, um ungefähre Übereinstimmungen von Zeichenfolgen zu finden, aber das kostet Zeit und erfordert viele Ressourcen. Oft ist es besser, eine Lösung zu erwerben, die Fuzzy-Matching-Algorithmen verwendet, um Ihren Anwendungsfall zu unterstützen.
Wenn Sie daran interessiert sind, wie wir bei Klippa Fuzzy Matching in unseren Lösungen einsetzen, dann lesen Sie weiter!
Wie verwendet Klippa Fuzzy Matching?
Viele OCR-Programme wie Klippa DocHorizon konzentrieren sich in erster Linie darauf, eine exakte Übereinstimmung in Datenfeldern für die Datenextraktion zu finden. Allerdings kann nicht jede OCR-Software immer exakte Übereinstimmung bei der Datenextraktion finden, was auf verschiedene Gründe wie die Verwendung von Abkürzungen, verkürzten Wörtern usw. zurückzuführen ist.
Aus diesem Grund ist es wichtig, Fuzzy Matching zu verwenden, um sicherzustellen, dass relevante Daten aus Dokumenten extrahiert werden können.
In diesem Zusammenhang verwendet Klippa die Levenshtein-Distanz, um ungefähre Übereinstimmungen zu finden und sicherzustellen, dass alle relevanten Daten extrahiert werden. Sobald die Datenextraktion abgeschlossen ist, wird die Datenausgabe im JSON-Format mit einer Übereinstimmungsbewertung bereitgestellt.
Anhand der Trefferquote können Kunden von Klippa feststellen, ob sie die Ergebnisse von einer Person überprüfen lassen müssen, um ungenaue Ergebnisse zu vermeiden.
Zusätzlich zur Datenextraktion verwendet Klippa Fuzzy Matching, um doppelte Daten aus Datensätzen für das Training von OCR-Modellen zu eliminieren. Auf diese Weise ist der Trainingsprozess effizienter und führt zu besseren Ergebnissen, da keine Zeit verschwendet wird und die Wahrscheinlichkeit von Fehlalarmen (bei der Datenextraktion und den Erkennungsergebnissen) reduziert wird.
Sind Sie daran interessiert, mit Fuzzy Matches die Datenextraktion oder das Datenmanagement in Ihrem Unternehmen zu verbessern? Vereinbaren Sie über das untenstehende Formular einen Termin für eine Demo, um zu sehen, wie unsere Lösung mit Fuzzy Matching funktioniert. Falls Sie ein Beratungsgespräch wünschen oder weitere Informationen wünschen, kontaktieren Sie einen unserer Experten.