Textantworten (offene Nennungen) automatisch zuordnen in R nach Ähnlichkeit

Nachdem wir uns zuletzt angesehen hatten, wie man Textantworten (offene Nennungen) in R codieren kann und dazu das Paket stringr sowie ein wenig reguläre Ausdrücke verwendeten, wollen wir uns heute der spannenden Frage zuwenden: Wie kann man Einträge automatisch zuordnen, wenn es viele ähnliche, aber nicht exakt gleiche Einträge gibt?

Beispieldaten: Textantworten zu Automarken

Nehmen wir an, es gibt in unserer Befragung ein Textfeld, in das die Teilnehmer eine Automarke eintragen sollten. Wir halten es hier zu Demonstrationszwecken simpel und betrachten lediglich die Premiummarken Mercedes, BMW, Audi sowie dessen Konzernmutter Volkswagen.

Hier die 18 (fiktiven) Antworten, alphabetisch sortiert:

Audi

Audi A6 quattro

Audi Ingolstadt

Bayerische Mist-Werke

Bayerische Motoren-Werke

BMW

BMW i3

BMW München

Daimler-Benz

Folgswachen

mein lieber VW

Mercedes

Mercedes AMG

Merzedes

Volkswägelchen

Volkswagen

VW-Verräter

VW Golf

Ein typischer, für die Datenanalyse nicht direkt bequem nutzbarer Datensatz:

• Zum Teil sind nur Marken angegeben, z. T. auch Fahrzeugtypen (A6, i3, AMG, Golf)
• Marken sind meist ausgeschrieben, manchmal wurden Abkürzungen verwendet (BMW, VW)
• Es gibt unterschiedliche Schreibweisen und Verballhornungen sowie Fülltexte („… Mist-Werke“, „mein lieber …“, „…-Verräter“, „Merzedes“, das umgangssprachliche „Folgswachen“, „Volkswägelchen“.

Um das zu lösen, könnten wir wie gestern mit regulären Ausdrücken hantieren. Da müssten wir allerdings etliche Sonderfälle berücksichtigen, die bei zusätzlichen Daten sehr wahrscheinlich nicht ausreichen würden und die Behandlung neuer Sonderfälle erforderlich machen würden.

Gesucht ist eine Lösung, die eine automatisierte Zuordnung vornimmt, mit wenig Programmieraufwand, und die auch bei neuen Daten auf Anhieb greift.

Ein wenig vorbereitende Datenaufbereitung …

Bevor diese fast magische, automatisierte Lösung zum Einsatz kommt, betreiben wir noch ein klein wenig Datenaufbereitung, um es unserem Werkzeug etwas leichter zu machen:

• Abkürzungen ersetzen wir durch ausgeschriebene Markennamen. Unser späteres Werkzeug funktioniert besser mit etwas mehr Text.
• Den Sonderfall mit völlig unterschiedlichen Namen, die in der gleichen Kategorie landen sollen, ordnen wir vorab zu.

Hier der Code zur Ersetzung der Abkürzungen:

library(tidyverse)
autos <- autos %>%
    mutate(Marke = str_replace(Marke_org, "VW", "Volkswagen"),
           Marke = str_replace(Marke, "BMW", "Bayerische Motoren-Werke"))

Kurz und simpel. Und hier der Code zur Änderung von „Daimler / Daimler-Benz“ zu „Mercedes“, diesmal mit Hilfe eines regulären Ausdrucks (regular expression):

autos <- autos %>%
    mutate(Marke = str_replace(Marke, "(Daimler-Benz|Daimler)", "Mercedes"))

Der reguläre Ausdruck reagiert gleichermaßen auf den Eintrag „Daimer-Benz“ wie „Daimler“, der senkrechte Strich steht für „oder“. So müssen wir nicht zwei separate Codezeilen schreiben.

Automatische Zuordnung anhand von Text-Ähnlichkeit

Damit sind wir bereit für ein Stück „Magie“ – die automatische Zuordnung der Automarken auf Basis von Text-Ähnlichkeit. Dazu nutzen wir das R-Paket tidystringdist von Colin Fay, das auf stringdist aufbaut. Grundidee: Ähnlich wie Korrelationen in numerischen Daten können wir Texteinträge mit einer Punktzahl nach Ähnlichkeit bewerten.

Erster Schritt: Zuordnungstabelle Original-Einträge vs. Kategorien

Im ersten Schritt erstellen wir eine Zuordnungstabelle, die jeden Originaleintrag jeder möglichen Zielkategorie (hier: den vier Automarken) gegenüberstellt. Dazu nutzen wir die Funktion crossing() aus dem tidyr-Paket, die die praktische Eigenschaft besitzt, Duplikate zu entfernen. Das kann Speicherplatz und Rechenzeit sparen – bei unseren Beispieldaten spielt das keine Rolle, in realen Anwendungen kann es durchaus einen spürbaren Unterschied machen. Hier gibt es nach der Datenaufbereitung zwei identische Einträge: 2x Mercedes (1x umcodiert aus Daimler-Benz) und 2x Bayerische Motoren-Werke (1x umcodiert aus der Abkürzung).

marken <- c("Audi", "Bayerische Motoren-Werke", "Mercedes", "Volkswagen")
zuordnungstabelle <- tidyr::crossing(autos$Marke, marken) %>%
    rename(Marke = autos$Marke, Marken_Vorlage = marken)

Die Base R-Funktion expand.grid() wäre auch anwendbar, entfernt jedoch keine Duplikate.

Damit erhalten wir eine Tabelle der folgenden Art:

1	Audi	Audi
2	Audi	Bayerische Motoren-Werke
3	Audi	Mercedes
4	Audi	Volkswagen
5	Audi A6 quattro	Audi
6	Audi A6 quattro	Bayerische Motoren-Werke
7	Audi A6 quattro	Mercedes
8	Audi A6 quattro	Volkswagen
9	Audi Ingolstadt	Audi
10	Audi Ingolstadt	Bayerische Motoren-Werke

Hier nur die ersten 10 Zeilen; insgesamt sind es 64 Einträge (16 unterschiedliche Originalantworten x 4 Kategorien).

Zweiter Schritt: Ähnlichkeits-Score berechnen

Nun sind wir bereit für den spannendsten Schritt: Die Berechnung des Ähnlichkeits-Scores. Ähnlich wie bei Clusteranalysen kann man zwischen Ähnlichkeit und Distanz unterscheiden; üblicher sind Distanzmaße. Wir nehmen den Jaccard-Index und drehen ihn um (1 – jaccard), sodass wir etwas intuitiver interpretieren können: Je höher die Zahl, desto ähnlicher. Die mathematischen Details erspare ich mir; wer mehr erfahren will, wird hier fündig (R-Paket: stringdist): ?“stringdist-metrics“

Der R-Code zur Berechnung der Ähnlichkeiten ist denkbar simpel:

zuordnung <- tidy_stringdist(zuordnungstabelle, v1 = Marke, v2 = Marken_Vorlage) %>%
    mutate(score = round(1 - jaccard, 2)) %>%
    select(Marke, Marken_Vorlage, score)

Die Funktion berechnet mehrere Distanzmaße; wir wählen mit dplyr::select() nur den umgepolten Jaccard-Wert aus. Somit erhalten wir eine Tabelle dieser Art (hier nur die ersten sechs Zeilen):

ID	Original-Eintrag	Kategorie	Score
1	Audi	Audi	1
2	Audi	Bayerische Motoren-Werke	0.05
3	Audi	Mercedes	0.11
4	Audi	Volkswagen	0
5	Audi A6 quattro	Audi	0.36
6	Audi A6 quattro	Bayerische Motoren-Werke	0.27

Dritter Schritt: Höchste Ähnlichkeiten auswählen und den Originaldaten zuordnen

Nun wollen wir uns nicht manuell durch die Punktzahlen wühlen, sondern die jeweils wahrscheinlichste Kategorie auswählen und den Originaldaten zuspielen. Das geht so, im tidyverse-Stil:

# Nur wahrscheinlichste Kategorie (Marke) behalten ...
zuordnung_top <- zuordnung %>%
    group_by(Marke) %>%
    summarise(max_score = max(score)) %>%
    ungroup()

# ... und den Originaldaten zuspielen
zuordnung <- zuordnung %>%
    inner_join(zuordnung_top, by = c("Marke", "score" = "max_score"))

autos <- autos %>%
    left_join(zuordnung, by = "Marke")

Das dplyr-Paket enthält join-Funktionen, die an ähnliche SQL-Funktionalität angelehnt sind. inner_join() ordnet die Fälle zu, die in beiden Tabellen vorkommen, left_join() behält alle Fälle der erstgenannten Daten (hier: die Originaldaten). So werden alle 18 Einträge zugeordnet (mit den beiden oben beschriebenen Duplikaten).

Unsere Daten sehen jetzt so aus:

Marke_org	Marke (aufbereitet)	Marken_Vorlage	score
Audi	Audi	Audi	1
Audi A6 quattro	Audi A6 quattro	Audi	0.36
Audi Ingolstadt	Audi Ingolstadt	Volkswagen	0.35
Bayerische Mist-Werke	Bayerische Mist-Werke	Bayerische Motoren-Werke	0.88
Bayerische Motoren-Werke	Bayerische Motoren-Werke	Bayerische Motoren-Werke	1
BMW	Bayerische Motoren-Werke	Bayerische Motoren-Werke	1
BMW i3	Bayerische Motoren-Werke i3	Bayerische Motoren-Werke	0.94
BMW München	Bayerische Motoren-Werke München	Bayerische Motoren-Werke	0.94
Daimler-Benz	Mercedes	Mercedes	1
Folgswachen	Folgswachen	Volkswagen	0.62
mein lieber VW	mein lieber Volkswagen	Volkswagen	0.67
Mercedes	Mercedes	Mercedes	1
Mercedes AMG	Mercedes AMG	Mercedes	0.67
Merzedes	Merzedes	Mercedes	0.71
Volkswägelchen	Volkswägelchen	Volkswagen	0.69
Volkswagen	Volkswagen	Volkswagen	1
VW-Verräter	Volkswagen-Verräter	Volkswagen	0.71
VW Golf	Volkswagen Golf	Volkswagen	0.77

Ein schönes Ergebnis! Ohne Aufwand für die Behandlung von Sonderfällen wurden fast alle Einträge korrekt zugeordnet. Der Ähnlichkeits-Score gibt uns Hinweise, wie sicher die Zuordnung gelang. Abweichungen wie „Volkswägelchen“, „Folgswachen“ oder „Merzedes“ haben uns keine Bauchschmerzen bereitet.

Es wird jedoch deutlich, dass diese Methode auch schief gehen kann. Haben Sie die Fehlzuordnung gleich gesehen? Aus „Audi Ingolstadt“ wurde „Volkswagen“. Wir müssen also auf der Hut bleiben. Der Score ist mit 0.35 in diesem Fall recht niedrig – es empfiehlt sich ohnehin, niedrige Ähnlichkeitsscores nachzukontrollieren. Zudem wäre hier die Abhilfe leicht: Da der korrekte Markenname im Originaleintrag enthalten ist, könnten wir in der Datenaufbereitung diesen Namen extrahieren und somit den Zusatz „Ingolstadt“ mit wenig Aufwand entfernen.

Anwendungsbeispiel: Duplikate bei nicht-identischen Schreibweisen finden

Die Inspiration für diesen Beitrag stammt aus einem Blogbeitrag der RStudio Community. Dort ging es um die Frage, wie man Duplikate ermitteln kann, wenn Schreibweisen nicht exakt übereinstimmen. Dort war das Vorgehen ein wenig anders: Es gab keine vorgegebenen Kategorien wie hier (die vier Automarken), sondern jeder Eintrag wurde mit jedem anderen verglichen. Ergebnis: Eine Spalte, die jedem Eintrag den ihm Ähnlichsten gegenüberstellte. Dort wurde die Funktion tidystringdist::tidy_comb_all verwendet, um alle Kombinationsmöglichkeiten in einer Matrix abzubilden.

Gerade in größeren Datensätzen kann die Suche nach Duplikaten bei Detailunterschieden in Schreibweisen sehr mühsam sein – man denke an Adressdaten mit leicht abweichenden Namen (Maier vs. Meier) oder Zusatzangaben (Beispielstraße 3b HH vs. Beispielstraße 3b Hinterhaus). Mit der hier vorgestellten Technik kann man sich gezielt Fälle mit einer hohen Duplikat-Wahrscheinlichkeit heraussuchen lassen und diese dann ggf. manuell weiterverfolgen. So kann man viel menschliche Arbeitszeit einsparen.

Den R-Code zu diesem Thema finden Sie hier zum Download (Markdown-Format, enthält die Beispieldaten im Code).

Literatur-Empfehlung für fortgeschrittene Textanalysen („Text Mining“) mit R:

Text Mining With R: A Tidy Approach