Werkzeug

CSV-Tool: Ähnliche Texte

Sebastian Meier (@seb_meier) | 06/04/2018

In den letzten Wochen haben wir uns etwas intensiver mit der Berliner Zuwendungsdatenbank beschäftigt. Dabei sind wir auf ein typisches Open Data-Problem gestoßen: Weil Namen und Adressen der Zuwendungsempfänger händisch in die Verwaltungsdatenbank eingepflegt wurden, haben sich eine ganze Menge Tippfehler und Ungenauigkeiten in die Daten eingeschlichen. Wir haben deshalb ein kleines Tool entwickelt, dass in der Lage ist, solche Ungereimtheiten zu erkennen und für mehr Ordnung in CSV-Dateien zu sorgen. Hier könnt ihr es ausprobieren.

Nehmen wir einmal an, der (fiktive) Verein „Kaninchenfreunde Karlshorst e.V.“ erhält eine finanzielle Förderung aus Landesmitteln und somit auch einen Eintrag in der Zuwendungsdatenbank. Im folgenden Jahr erhält der Verein vielleicht erneut eine Förderung. Diesmal vergisst die in der Verwaltung zuständige Person jedoch einen Punkt und trägt „Kaninchenfreunde Karlshorst e.V“ in die Datenbank ein. Aufgrund der unterschiedlichen Schreibweise würde eine Maschine davon ausgehen, dass es sich um zwei unterschiedliche Träger handelt. Da die Zuwendungsdatenbank mehrere tausend Einträge enthält, ist es mitunter recht schwierig, solche kleinen Vertipper nachträglich aufzuspüren. Hier hilft unser Tool weiter.

Ausgangsdatensatz

Füge den Inhalt einer CSV-Datei in das Textfeld ein oder ziehe die Datei von deinem Rechner direkt auf das Textfeld. Beachte, dass die erste Zeile die Spaltennamen enthalten muss. Für einen ersten Test kannst Du auch die bereits eingetragenen Beispieldaten verwenden.
In der Webversion sollten die Datensätze nicht zu groß sein (<2MB) um schnelle Ergebnisse zu erzielen.



Welches Trennzeichen wird in der Datei eingesetzt?
Dies sollte eigentlich automatisch erkannt werden.


Welche Spalte soll analysiert werden?
Bitte auswählen.

Vergleichs-Algorithmus

Welcher Algorithmus soll für den Vergleich genutzt werden?
Eine Erklärung zu den beiden Methoden findest du weiter unten auf der Seite.

Zusatzparameter für den Fingerprint-Algorithmus:
Art des Fingerprinting:

Sprache:

Sollen die Wörter einem Stemming-Prozess unterzogen werden:
Zusatzparameter für den KNN-Algorithmus:
Mindestanzahl an übereinstimmenden Zeichen (empfohlen: 6):

Maximale Abweichung in Prozent (empfohlen: 10):

Korrektur-Template

Das Tool gruppiert nun ähnlich geschriebene Wörter, die richtige Schreibweise lässt sich auswählen. Im nächsten Schritt werden dann alle Wörter einer Gruppe durch die richtige Schreibweise ersetzt. Soll ein Wort nicht zur Gruppe gehören, kann es entfernt werden.
(Abhängig von der Größe des Ausgangsdatensatzes kann es etwas dauern bis das Template angezeigt wird.)



Korrigierter Datensatz

Im folgenden Textfeld sollten nur noch die korrekten Bezeichnungen auftauchen und alle Fehler entfernt worden sein.
Je nach Größe der Datei kann das Säubern einen Augenblick in Anspruch nehmen.

Was steckt hinter dem Tool?

Zur Erkennung von Ähnlichkeiten greift unser Tool je nach Einstellungen auf die Fingerprint- oder die KNN-Methode zurück.

Fingerprint

Die grundsätzliche Idee des Fingerprinting ist es einen Text auf seine essentiellen Bestandteile zu reduzieren und dadurch einen essentiellen Fingerabdruck zu generieren. Dieser Fingerabdruck wird dann mit anderen verglichen um gleiche Text zu identifizieren.

Normales Fingerprinting

Um dies anzuwenden gibt es zwei Möglichkeiten. In der normalen Variante werden folgende Schritte angewandt:

So wird dann z.B. aus


                    'Grips'-Theater gemeinnützige Gesellschaft
                    gripstheatergemeinnuetzigegesellschaft
                

Dies bedeutet, dass alle folgenden Varianten zum selben Fingerabdruck werden:


                    'Grips'-Theater gemeinnützige Gesellschaft
                    Grips-Theater gemeinnützige Gesellschaft
                     Grips Theater gemeinnützige Gesellschaft
                    Grips Theater gemeinnützigeGesellschaft

                    gripstheatergemeinnuetzigegesellschaft
                

Dieses Verfahren ist sehr schnell, kann aber Probleme wie komplexere Tippfehler häufig nicht erkennen.

Phonetisches Fingerprinting

Beim phonetischen Fingerabdruck werden Textelemente erst in ihre phonetischen Marker übersetzt. Hierdurch können häufig kleine Schreibfehler, weil z.B. jemand nach Gehör geschrieben hat erkannt werden.

So haben folgende Schreibweisen die selben phonetischen Marker:


                    Sebastian
                    Sebästian
                    Sebastien

                    81826
                

Um die Umwandlung vorzunehmen wurden in unserem Modul zwei Bibliotheken integriert: für deutsch die cologne-Sammlung und für andere Sprachen die metaphone-Sammlung.

KNN / Neighbour

Die Nachbarschaftsmethode ist wesentlich komplexer und damit auch rechenintensiver, dafür aber auch genauer. Die Grundlage ist ein direkter Vergleich zweier Texte, bei dem die Distanz zwischen den Texten berechnet wird, genauer gesagt, die Levenshtein-Distanz. Diese beschreibt die Anzahl an Veränderungen am ersten Text (Löschen, Hinzufügen und Ersetzen von Zeichen), die notwendig sind um den anderen Text zu generieren. Um nicht jeden Text mit jedem anderen Text vergleichen zu müssen, wird vorher überprüft welche Texte überhaupt ähnliche Elemente enthalten. Hierzu wird der Text in kleine Bausteine aufgebrochen und diese werden miteinander verglichen. Umso länger die Bausteine umso schneller und umso kürzer die Bausteine umso genauer (Standardwert: 6).

Folgend ein Beispiel für die Aufteilung eines Textes in 6er Zeichenketten:


                    Technologie
                    Techno
                     echnol
                      chnolo
                       hnolog
                        nologi
                         ologie

                    Technik
                    Techni
                     echnik

                    Technische
                    Techni
                     echnis
                      chnisc
                       hnisch
                        nische

                

Im obrigen Beispiel würden Technik und Technische den gemeinsamen Baustein "Techni" haben.

Bei den Texten die eine Ähnlichkeit aufweisen, wird dann die konkrete Distanz berechnet. Hier sind ein paar Beispiele und die entsprechenden Distanzen:


                    Technik <> Technische = 4
                    Berlin <> Bern = 2
                    Senat <> Stern = 4
                

Für die Bewertung der Levenshteinschen Distanz (LD) setzen wir auf das Verhältnis zur Textlänge. Ein sehr langer Text der eine LD von 2 hat ist möglicherweise derselbe, ein Wort von nur 5 Zeichen mit einer LD von 2 ist mit einer geringeren Wahrscheinlichkeit derselbe.

Die hier eingesetzten Methoden haben wir uns nicht ausgedacht, sondern sind gängige Methoden um solche Problem zu lösen. Inspiriert wurde unser Vorgehen von den Funktionalitäten der quelloffenen Desktop-Anwendung Open Refine, die sich bestens eignet um Datensätze zu säubern.

Nutzung/Installation

Das Tool kann nicht nur hier im Browser genutzt, sondern läuft auch auf der Kommandozeile oder lässt sich in eigene Anwendungen integrieren. Entwickler*innen, die damit arbeiten wollen, können via NPM das entsprechende Node-Modul installieren. Der Quellcode ist wie immer offen und unter untenstehendem Github-Link abrufbar. Wir freuen uns über Feedback und Weiterentwicklungen!

Project on Github csv-string-optimization
Projekt auf GitHub
Sebastian Meier

Über den Autor

Sebastian Meier

Sebastian Meier ist Data Scientist bei der Technologiestiftung Berlin. Er studierte Kommunikations-, Interface-Design und promovierte im Bereich der Geoinformatik an der Uni Potsdam. Der Fokus von Sebastians Arbeit liegt auf der Analyse und Visualisierung räumlicher Daten, sowie menschzentrierter Perspektiven bei der Entwicklung von Mensch-Maschine-Schnittstellen.