Knowledge Discovery in Databases (KDD)

Große Datenmengen wie die IDS-Textkorpora können manuell nicht gewinnbringend analysiert werden. Schon wenn man nur einzelne Belege für ein bestimmtes Phänomen heraussuchen möchte, ist man auf die Hilfe von computergestützten Abfragen angewiesen. Sollen jedoch alle Belege eines Phänomens betrachtet und systematisch ausgewertet werden, so ist man – abgesehen von sehr seltenen Phänomenen mit nur wenigen Belegen – auf Prozesse und Verfahren angewiesen, die mit ‚Knowledge Discovery in Databases’ (KDD), ‚Data-Mining’ oder ‚Maschinelles Lernen’ bezeichnet werden.

Das Ziel von KDD ist, in meist sehr großen Datenbeständen mit mathematisch-statistischen Methoden neue, bisher unbekannte fachliche Zusammenhänge zu erkennen. In der Praxis werden die Begriffe KDD und Data-Mining häufig synonym gebraucht, obwohl Data-Mining streng genommen nur den Modellierungsschritt im KDD-Prozess bezeichnet. Beim maschinellen Lernen werden auf vorhandenen Daten statistische Modelle trainiert, die anschließend zur Vorhersage (z.B. Klassifikation neuer Daten) eingesetzt werden können. Viele der eingesetzten Algorithmen können sowohl für Data-Mining als auch für maschinelles Lernen verwendet werden.

Der KDD-Prozess besteht normalerweise aus folgenden Schritten (vgl. Shearer 2000):

• Aufgabenverständnis: Ziele und grobe Vorgehensweise festlegen,
• Datenverständnis: Zusammenstellung der benötigten Datenquellen und Einarbeitung in deren Besonderheiten,
• Datenaufbereitung: Erstellung der endgültigen Datenmenge für die Modellierung (Auswahl der Fälle und Attribute, ggf. Berechnung/Umrechnung von Werten),
• Modellierung: Anwendung geeigneter Verfahren zur Datenanalyse und Modellbildung (meist gibt es mehrere passende Verfahren mit mehreren möglichen Parameterkombinationen),
• Evaluation: Auswahl des Modells, das die Aufgabenstellung am besten erfüllt,
• Einsatz: Interpretation des Modells (KDD) oder Anwendung des Modells auf neue Daten (maschinelles Lernen).

Erfahrungsgemäß werden mindestens 80% der Zeit für die ersten drei Schritte aufgewendet.

Aufgabenverständnis: Der grundlegende Schritt des KDD-Prozesses ist die Zielfestlegung: Was soll überhaupt modelliert werden und wozu dient die Modellierung? Bei der Modellierung der Fugenelemente geht es darum, den Regeln, die den Gebrauch von Fugenelementen in zweigliedrigen nominalen Komposita des Deutschen steuern, auf die Spur zu kommen. Um dies zu erreichen, muss das im Modell enthaltene Wissen explizit repräsentiert, also für den Menschen ‚lesbar’ sein, damit ein Experte es interpretieren kann. Daher bietet sich hier an, so genannte Entscheidungsbäume zu trainieren.

Datenverständnis und Datenaufbereitung: Nach der Festlegung des Ziels wird ermittelt, welche Daten zur Modellierung zur Verfügung stehen. Diese Daten müssen auf ihre Besonderheiten hin untersucht werden, um spätere Überraschungen zu minimieren. Wenn die Basisdaten für die Modellierung nicht ausreichen, müssen Daten aus weiteren Quellen integriert werden. So wurden beispielsweise zusätzlich zu den aus den Korpora gewonnenen Daten für die Fugenelementeanalyse noch Daten aus der lexikalischen Datenbank CELEX (Baayen u. a. 1995) extrahiert und hinzugefügt.

Modellierung: Bei der Modellierung berechnet ein Algorithmus aus einer Menge von Trainingsdaten ein Modell, das dann auf neue Daten angewendet werden kann, um bestimmte Werte vorherzusagen. Die Algorithmen unterscheiden sich unter anderem bezüglich der Art und Anzahl der vorhergesagten Werte, der Art der Trainingsdaten, überwachter vs. unüberwachter Methoden und der Interpretierbarkeit des Modells.

Bei überwachten Methoden (‚supervised learning’) enthalten die Trainingsdaten auch die tatsächliche Kategorie, die man für neue Daten vorhersagen können möchte. Bei der Modellierung der Fugenelemente kennen wir beispielsweise für alle aus den IDS-Korpora extrahierten zweigliedrigen Komposita das jeweilige Fugenelement, daher können wir auf diese Daten überwachte Methoden anwenden. Bei unüberwachten Methoden (‚unsupervised learning’), wie z.B. Clustering, werden die Trainingsdaten vom Lernalgorithmus in eine (meist vorgegebene Anzahl von) Kategorien eingeteilt. Diesen wird meist im Nachgang manuell eine passende Bezeichnung zugeordnet.

Wie bereits erwähnt sollte das Modell für den vorliegenden Zweck lesbar und interpretierbar sein. Beispielsweise erlauben künstliche neuronale Netze keinen Einblick in ihre durch die Modellierung erlernte Struktur und können daher nicht vom Menschen interpretiert werden. Entscheidungsbäume hingegen sind – vorausgesetzt sie sind nicht zu groß – gut les- und interpretierbar.

Evaluation: Die trainierten Modelle sollten nicht anhand der Trainingsdaten, sondern anhand separater Testdaten, die nicht zum Training verwendet wurden, evaluiert werden. Eine bewährte Methode ist die k-fache Kreuzvalidierung (‚k-fold cross validation’). Dazu werden die Trainingsdaten in k Teilmengen aufgeteilt. In k Trainings- und Testdurchläufen wird jeweils eine der k Teilmengen als Testdatensatz verwendet, und die verbleibenden k-1 Teilmengen bilden den Trainingsdatensatz. Der Durchschnitt aus den Evaluationsmaßen der k Einzeldurchläufe bildet das Gesamtmaß.

Bei nominalen Vorhersagewerten kommen meist mehrere Evaluationsmaße zum Einsatz. Dafür wird für jede vorherzusagende Klasse X in den Testdaten Folgendes gezählt:

• richtig positiv (r_p): Anzahl der Fälle, bei denen das Modell vorhersagt, dass der Fall zur Klasse X gehört, und dies auch der Realität entspricht;
• richtig negativ (r_n): Anzahl der Fälle, bei denen das Modell vorhersagt, dass der Fall nicht zur Klasse X gehört, und dies auch der Realität entspricht;
• falsch positiv (f_p): Anzahl der Fälle, bei denen das Modell vorhersagt, dass der Fall zur Klasse X gehört, aber dies nicht der Realität entspricht;
• falsch negativ (f_n): Anzahl der Fälle, bei denen das Modell vorhersagt, dass der Fall nicht zur Klasse X gehört, aber dies nicht der Realität entspricht.

In einer Konfusionsmatrix angeordnet sieht es folgendermaßen aus:

Mit diesen Werten lassen sich nun folgende Evaluationsmaße berechnen:

• Genauigkeit (‚precision’) = r_p / (r_p + f_p)
• Trefferquote (‚recall’) = r_p / (r_p + f_n)
• F-Maß = 2 * Genauigkeit * Trefferquote / (Genauigkeit + Trefferquote)

Alle drei Maße können Werte zwischen 0 und 1 annehmen – je größer, desto besser das Modell. Dabei sind Genauigkeit und Trefferquote voneinander abhängig: Die Trefferquote kann hoch, die Genauigkeit jedoch niedrig sein, wenn zwar alle Fälle der Klasse X gefunden werden, dabei jedoch auch viele Fälle der Klasse ‚nicht X’ fälschlicherweise dabei sind. Umgekehrt kann die Genauigkeit hoch, die Trefferquote jedoch niedrig sein, wenn zwar alle der Klasse X zugeordneten Fälle tatsächlich der Klasse X angehören, dabei aber viele Fälle nicht dabei sind, die eigentlich auch zu Klasse X gehören würden. So möchte man das bestmögliche Verhältnis von Genauigkeit und Trefferquote erreichen. Das F-Maß drückt dieses Verhältnis aus, indem es Genauigkeit und Trefferquote mithilfe des gewichteten harmonischen Mittels kombiniert.

Ist der Einsatzzweck die Interpretation des Modells durch einen menschlichen Experten, so ist nicht unbedingt das Modell mit den besten Evaluationsmaßen am besten dafür geeignet. Z.B. eignet sich ein kleinerer Entscheidungsbaum mit wenigen Knoten besser zur Interpretation, auch wenn er kein so gutes F-Maß aufweist wie ein Entscheidungsbaum mit vielen Knoten.

Einsatz: Je nach Ziel des KDD-Prozesses besteht der ‚Einsatz’ des Modells in seiner Interpretation durch einen menschlichen Experten und dem damit verbundenen Erkenntnisgewinn oder in der Anwendung auf neue Daten, um diese zu klassifizieren bzw. andere Vorhersagen zu treffen.