Fuzzy-Matching von strukturierten Daten

Question

habe ich einen ziemlich kleinen Korpus strukturierten Datensätze in einer Datenbank zu sitzen. Bei einem winzigen Bruchteil der Informationen in einem einzigen Datensatz enthalten sind, über ein Web-Formular eingereicht (so in der gleichen Weise aufgebaut, wie das Tabellenschema), (nennen wir es das Testprotokoll) Ich muss schnell eine Liste der Erarbeitung Datensätze, die die wahrscheinlichsten Spiele für das Testprotokoll sind, sowie eine Vertrauensschätzung dafür, wie eng die Suchbegriffe einen Datensatz entsprechen. Der primäre Zweck dieser Suche ist es, herauszufinden, ob jemand zur Eingabe eines Datensatzes versucht, die einem im Korpus Duplikat ist. Es gibt eine gute Chance, dass das Testprotokoll eine Betrogene sein wird und eine vernünftige Chance, das Testprotokoll wird kein Betrogene sein.

Die Aufzeichnungen sind etwa 12000 Bytes breit und die Gesamtzahl der Datensätze ist etwa 150.000. Es gibt 110 Spalten im Tabellenschema und 95% der Suchanfragen auf der Spitze sein wird 5% am häufigsten Spalten gesucht.

Die Daten sind Sachen wie Namen, Adressen, Telefonnummern und andere branchenspezifische Zahlen. Sowohl in dem Korpus und der Testdatensatz wird es von Hand eingegeben und wird innerhalb eines einzelnen Feldes halbstrukturierten. Das könnte dir auf den ersten Blick sagen „Gewicht die Spalten von Hand und Spiel Wort-Token in ihnen“, aber es ist nicht so einfach. Das dachte ich auch: wenn ich eine Telefonnummer bekommen dachte ich, dass eine perfekte Übereinstimmung zeigen würde. Das Problem ist, dass es nicht ein einzelnes Feld in der Form, deren Token Frequenz ändern ist nicht um Größenordnungen. Eine Telefonnummer kann 100-mal im Korpus oder 1-mal im Korpus erscheinen. Das gleiche gilt für andere Bereiche. Dies macht in der Feldebene unpraktisch Gewichtung. Ich brauche einen feinkörnigen Ansatz anständig Anpassung zu erhalten.

Mein erster Plan war, einen Hash von Hashes, Top-Level ist der Feldname zu erstellen. Dann würde ich alle Informationen aus dem Korpus für ein bestimmtes Feld auswählen, versuchen, die darin enthaltenen Daten zu bereinigen und tokenize die hygienisiert Daten, die Token auf der zweiten Ebene Hashing, mit den Token als Schlüssel und Frequenz als Wert.

würde ich die Frequenzzahl als Gewicht verwenden: Je höher die Frequenz eines Tokens im Referenzkorpus, desto weniger Gewicht lege ich auf diese Token, wenn es in dem Testsatz gefunden

.

Meine erste Frage ist für die Statistiker im Raum: Wie würde ich die Frequenz als Gewicht verwenden? Gibt es eine genaue mathematische Beziehung zwischen n, die Anzahl der Datensätze, f (t), die Frequenz, mit der ein Token t im Corpus erschien, ist die Wahrscheinlichkeit, o dass ein Datensatz ein ursprüngliche und nicht ein Duplikat, und die Wahrscheinlichkeit p, dass das Prüfprotokoll ist wirklich x ein Rekord den Test gegeben und x die gleichen t im gleichen Feld enthalten? Wie über die Beziehung für mehrere Token Matches über mehrere Felder?

Da ich aufrichtig Zweifel, dass es, ist es etwas, das mir nahe kommt, ist aber besser als ein völlig willkürlich Hack voller Magie Faktoren?

Abgesehen davon, hat bekam jemand eine Möglichkeit, dies zu tun?

Ich bin besonders scharf auf anderen Vorschläge, die nicht mit einer anderen Tabelle in der Datenbank beibehalten, wie eine Token-Frequenz-Lookup-Tabelle.

Answer 1

Sie können sich wahrscheinlich einige Ideen aus dieser anderen, aber ähnlichen SO Frage kommen: Berechnung-kontextsensitive Textkorrelation .

Mehr spezifisch für das Problem auf der Hand, hier sind ein paar Gedanken und Ideen:

Zunächst einmal, die sehr schiefe Nutzung Anerkennung (nur 6 bis 10 Attribute decken 95% des Einsatzes), können Sie / sollen dich auf den Attributen asymmetrischen Aufwand anwenden, also mehr investieren, sowohl in der Bezeichnung der Programmierzeit und in der Bezeichnung der Laufzeit-CPU Zuteilung, mit diesen wenigen Attributen für den Umgang als 100-odd zusätzliche Attribute.

Die relativ kleine Menge von Daten als Eingabe geliefert für den Abgleich möglich Duplikate in der Datenbank, die relativ kleine Gruppe von Attributen der Regel verwendet, und die scheinbar gemeinsame Semantik dieser (Telefonnummer, Adresse, Name ...) deutet auf eine Hand -crafted Lösung eher als ein vollständig basierend auf maschinelles Lernen.

Hinweis: Viele der Vorschläge, danach muß nicht auf alle Attribute angewandt werden (da weniger als ein Dutzend dieser Abdeckung nahezu alle Nutzung gibt es keinen Punkt, zumindest auf dem ersten viel mit den anderen Attributen zu investieren .

• Normalisieren der Daten
  Wenn es ihnen nicht erlaubt, die ursprünglichen Feldwerte vielleicht duplizieren die entsprechenden Spalten zu einem „norm_xxx“ coluumn zu ändern, wobei xxx der ursprüngliche Name ist.
  Was, Wie zu normalisieren mit jedem Attribute variieren; für „freien Text“ wie Daten, stellen Sie sicher, dass es keine führende oder nachfolgende Leerzeichen, nur ein Leerzeichen zwischen den Wörtern, keine Tabs und nicht druckbare Zeichen. Verwenden Sie entweder alle groß oder klein schreiben (eventhought das Original / for-Display Text eine Mischung umfassen kann, gehen Ihre Verarbeitung schneller durch einheitliche Gehäuse einnehmen kann). Insbesondere für Adressen und / oder Firmennamen, Sie gängige Begriffe zu einer Standardform (ST für STREET, ST und ST, etc.) umwandeln können (Achten Sie darauf, diese Liste zu halten für sie als auch für die Benutzer Suchkriterien angewandt werden ). Ein Teil der Normalisierung kann auch insgesamt einige Füllwörter fallen (wie etwa CO, INC, GMBH am Ende von den Firmennamen)
• Erstellen Sie ein paar berechneten Spalten
  Zum Beispiel diejenigen mit dem Text, in umgekehrter Richtung, für Attribute, die mit einem nachgestellten Platzhalter
durchsucht werden können
• Betrachten wir für einige Attribute eine Soundex-ähnliche Umwandlung verwendet wird.
• Volltextindex, individuell, alle textartige Spalte
• Erstellen Ebene (SQL) Indizes für alle 6 bis 10 viel gebrauchte Spalten

Alle oben genannten sind nur off-line Zeit die Vorbereitungen für tatsächlich durchführen Begegnungen. Nun .. der Benutzer seine / ihre Abfrage gibt ... hier sind ein paar Ideen, wie man damit umgehen

• Normalisieren der Suchkriterien, die es rechtfertigen
• Führen Sie mehrere Suchen ...
  Das ist ein bisschen schwierig; gibt es mehrere, teilweise widersprüchliche Ziele diese Suche durchzuführen. Wir wollen deutlich die Zahl der „möglicher Übereinstimmungen“ reduzieren: es effektiv unpraktisch ist eine vollständiges one-on-one zu tun mit den vom Benutzer angegebenen Kriterien aller 150.000 Datensätze zu vergleichen; ein Teil der Übereinstimmungslogik kann zum Beispiel des Bearbeitungs Abstand zwischen einem Feld eines bestimmten Datensatz der Datenbank und einem Suchwort bedeuten berechnen. Wir wollen auch, um sicherzustellen, wir sagen, den Namen des Unternehmens wegen eines Tippfehler nicht Datensätze aus der „möglichen Übereinstimmungen“ -Liste ausschließen ... Endlich haben wir die Liste der möglichen Übereinstimmungen in eine Rang Art und Weise zur Verfügung stellen möchten.
  Die Art und Weise dieser Suche durchzuführen folgt einige vordefinierte Heuristiken (I die Strategie-Entwurfsmuster funktionieren gut für die gefunden, so dass flexibilty in der Art und Weise die Suche ausgeführt werden, abhängig von den Benutzereingaben). Auf den Punkt gebracht die wir für die selektivsten Worte in den selektivsten / relevanten Attribute suchen, und auf der Grundlage der Anzahl der „Hits“ fanden wir entweder „OR“ (Union) oder „AND“ mit anderen Suchergebnissen, bis wir ein paar haben hundert Rekord.
• Berechnen Sie einen Ähnlichkeitswert zwischen jedem Attribute der „möglichen Übereinstimmungen“ Aufzeichnungen und den entsprechenden Suchkriterien. Möglicherweise einen Koeffizienten auf diesen Wert gilt (so dass mehr setzen wiegen ein Firmenname [teilweise] Spiel zu sagen, dass zu einem Stadtspiel)
• Tally der overal Ähnlichkeitswert für einen kompletten Datensatz (im Vergleich zu den vollständigen Suchkriterien)

• die Aufzeichnungen zeigen eine bestimmte Schwelle des Ähnlichkeitswert zu dem Endbenutzer übersteigt, für die Überprüfung

  Schließlich, und es kommt ein teilweise automatisierter Prozess, können Sie einige der Parameter auf einem Feedback basierend verändern durch den Endbenutzer geliefert. (Dies sehr schwierig zu tun, werde ich diese halten für einen anderen Beitrag ;-))