Stellen Sie sich vor, Sie sind in einem Kreditkartenunternehmen für die Betrugsbekämpfung zuständig. Jedes Mal, wenn für eine der ausgegebenen Karten ein Zahlungsvorgang gebucht wird (eine "Transaktion"), werden Ihnen die Daten übermittelt. Wenn Ihnen die Transaktion verdächtig erscheint, können Sie eine Detailprüfung anordnen und damit möglicherweise eine Betrugsserie im Keim ersticken. Aber die Prüfung ist teuer und aufwendig, sollte also so sparsam wie möglich angewendet werden.

Woran erkennen Sie also möglichst trennscharf eine verdächtige Transaktion? Offensichtlich können Sie nicht lange über jeden Einzelfall nachdenken, sondern benötigen eine einfache Entscheidungsvorschrift: ein "Modell" oder eine "Hypothese" im Jargon des Data Mining. Nehmen wir weiter an, es gebe weder Literatur, in der geeignete Modelle zu finden wären, noch einen Experten, den Sie fragen können. Immerhin hat Ihre Firma in den letzten zwei Jahren ihres Bestehens alle Transaktions- und Kundendaten gesammelt und bei jeder Transaktion vermerkt, ob sie sich schlussendlich als betrügerisch herausgestellt hat oder nicht.

Dann befinden Sie sich in der gleichen Situation wie ein Lernverfahren für das Data Mining. Ein solches Computerprogramm soll allgemein eine Klassifikations- oder Vorhersageaufgabe lösen. Das muss nicht eine einfache Ja-Nein-Entscheidung sein wie in unserem Fall. In manchen Fällen gibt es mehr als zwei mögliche Antworten, etwa wenn aus dem Text einer E-Mail zu erschließen ist, an welche Abteilung der Empfängerfirma sie weiterzuleiten ist. Oder die Antwort ist ein Zahlenwert wie der zukünftig zu erwartende Umsatz eines Kunden.

Das Programm erhält nun eine große Menge von Beispielen für die Lösung der Aufgabe und soll daraus ein Modell für zukünftige Fälle erzeugen. Weil man diese Entscheidungsvorschrift auch als Funktion im mathematischen Sinne ansehen kann, die zu jeder denkbaren Situations- oder Objektbeschreibung eine eindeutige Entscheidung oder Vorhersage liefert, nennt man diese Aufgabe auch "Funktionslernen aus Beispielen".

Nehmen wir der Einfachheit halber weiter an, der Datenbestand, an dem Sie lernen können, bestehe nur aus den 16 Einträgen in der Tabelle unten. Jeder dieser Datensätze enthält drei "Attribute": die Zahlungsart der betreffenden Transaktion (online oder offline), den Typ der verwendeten Karte (standard, premium oder temporär) und den Betrag, sowie die aus der Erfahrung gewonnene Klassifizierung der Transaktion (Betrug oder OK). In der Realität können solche Beispieltabellen einige hundert Attribute haben und mehrere Millionen bis Milliarden von Einträgen umfassen; darüber hinaus liegen die Daten oft nicht als einheitliche Tabelle vor, sondern sind aus mehreren Tabellen unterschiedlicher Art zusammenzutragen.

Wenn Ihnen jetzt eine Transaktion mit den Attributwerten (online, premium, 1020) vorgelegt wird, dann ist es eine nahe liegende Idee, sich am nahe Liegenden zu orientieren, das heißt an Beispielen aus der Vergangenheit, die dem neuen Fall möglichst ähnlich sind. Sie würden also die Tabelle durchgehen und bei Beispiel 12 fündig werden: Zahlungsart und Kartentyp sind gleich, und beim Betrag gibt es nur geringfügige Unterschiede. Nach diesem Vorbild würden Sie vermutlich eine Prüfung anordnen.

Aus diesem einfachen Prinzip hat sich eine Klasse von Lernverfahren entwickelt, die als "Nächste-Nachbarn-Verfahren" bezeichnet werden: Man ordne die zu betrachtenden Objekte in einen abstrakten Raum ein, derart dass ähnliche Objekte auch nahe beieinander zu liegen kommen. Zu dem zu klassifizierenden Objekt suche man in diesem abstrakten Raum den nächsten Nachbarn und verwende dessen Klassifizierung.

Für zahlenwertige Attribute ist "Nähe" beziehungsweise "Abstand" im Sinne der klassischen Geometrie zu verstehen: Man betrachtet die Zahlenwerte als Koordinaten eines Punktes in einem mehrdimensionalen Raum und berechnet den ("euklidischen") Abstand zweier Punkte nach einer Standardformel, die auf den Satz des Pythagoras zurückgeht. Für Attribute, die nicht durch Zahlen auszudrücken sind, muss man geeignete Abstandsfunktionen definieren. So könnte man festlegen, dass der Abstand zwischen identischen Werten 0 und der Abstand zwischen unterschiedlichen Werten 1 sein soll. Dann ist noch durch geeignete Wahl der Maßeinheiten jedem Attribut ein angemessenes Gewicht im Vergleich zu den anderen Attributen zuzuweisen: Ist der Unterschied zwischen einer Standard- und einer Premium-Karte ungefähr so bemerkenswert wie ein Betragsunterschied von 500 Euro?

Mehrere nächste Nachbarn sind ein besserer Ratgeber als einer. Um eine Entscheidung zu treffen, dürfen die k nächsten Nachbarn "abstimmen", wobei das Stimmgewicht jedes Nachbarn umgekehrt proportional zu seinem Abstand ist: Je weiter entfernt ein Nachbar ist, desto weniger hat er zu sagen. Es wird dann diejenige Vorhersage getroffen, die unter Berücksichtigung der Gewichte die meisten Stimmen erhalten hat; für numerische Vorhersagen verwendet man das gewichtete arithmetische Mittel. Die Anzahl k der einzubeziehenden Nachbarn ist ein vom Benutzer vorzugebender Parameter.

Mit einer geschickt definierten Abstandsfunktion sind diese k-nächste-Nachbarn-Verfahren sehr leistungsfähig. Auf diese Weise haben wir gemeinsam mit Mathias Kirsten und Tamás Horváth von der Universität Bremen ein Verfahren entwickelt, das sehr erfolgreich chemische Moleküle bestimmten Klassen zuordnet und auch Typen von mRNA-Signalstrukturen mit hoher Sicherheit erkennt.

Leider muss man bei einem k-nächste-Nachbarn-Verfahren zur Klassifikation eines neuen Objektes sämtliche Beispiele aus der Vergangenheit zur Verfügung haben. Bei Millionen oder Milliarden von Beispielen kostet das sehr viel Speicherplatz und Suchzeit. Das kann in gewissen Grenzen mit intelligenten Speicher- und Suchstrategien kompensiert werden. Ein weiterer Nachteil dieser Verfahren bleibt jedoch bestehen: Sie liefern keine kompakte Entscheidungsvorschrift, die sich ein Mensch ansehen und auch nur gedanklich nachvollziehen, geschweige denn überprüfen könnte.

In der Praxis nutzt man daher unter anderem die so genannten Entscheidungsbaumverfahren. Sie sind nicht da-rauf angewiesen, alle Beispiele dauerhaft zu speichern, sondern erzeugen aus ihnen eine kompakte Vorschrift in Form eines Entscheidungsbaumes.

Die Vorschrift ist einfach anzuwenden. Zur Klassifikation eines neuen Objektes durchläuft man den Baum von oben nach unten. Jede "Astgabel" (oval in der Abbildung) stellt eine Frage nach einem der Attribute und verweist einen je nach der Antwort auf einen von mehreren Ästen. Dem folgt man bis zur nächsten Astgabel und so weiter, bis man am Ende (in einem der "Blätter") eine Entscheidung vorfindet. Bei unserer Überprüfung würde eine Transaktion mit den Attributwerten (online, premium, 1020) nach Durchlaufen nur zweier Astgabeln (und Wahl des jeweils rechten Astes) bereits als verdächtig klassifiziert.

Wie kann man nun einen solchen Entscheidungsbaum aus Beispielen erstellen? Wir lassen ihn aus einem zarten Pflänzchen heranwachsen. Das Urbäumchen hat nur eine Astgabel, an der zwei Blätter hängen; aber wir haben die Freiheit, in die Astgabel eine beliebige Frage hinein zu schreiben, an die Äste die möglichen Antworten und an die Blätter Entscheidungen. Diese Freiheit nutzen wir so, dass dieser rudimentäre Baum, angewandt auf die Beispielmenge, möglichst wenig falsche (und entsprechend möglichst viele richtige) Entscheidungen trifft. Dazu probieren wir sämtliche Attribute durch.

In unserem Kreditkartenproblem ergibt sich: Schreiben wir das Attribut "Zahlungsart" in die Astgabel, kommen wir auf fünf falsche unter 16 Entscheidungen, wenn wir den Ast "offline" mit dem Blatt "prüfen" und den Ast "online" mit dem Blatt "nicht prüfen" versehen. Mit dem Attribut "Kartentyp" kommen wir ("prüfen" bei "Standard", "nicht prüfen" sonst) auf sieben Fehler. Das Attribut "Betrag" ist zahlenwertig; in diesem Falle ist es zweckmäßig, einen gewissen Wert festzulegen und dann dem einen Ast alle Werte zuzuweisen, die über diesem "Schwellenwert" liegen, und dem anderen Ast alle darunter. In unserem Beispiel stellt sich 650 als der geeignetste Schwellenwert heraus; aber selbst damit macht unser Bäumchen noch sieben Fehler.

Also schreiben wir "Zahlungsart" in die Astgabel, weil das die wenigsten Fehlentscheidungen ergibt. Nun darf unser Bäumchen weiter wachsen, das heißt, jedes Blatt wird durch eine Astgabel mit Ästen und Blättern ersetzt. Wieder haben wir die Freiheit, die neu herangewachsenen Teile so mit Fragen, Antworten und Entscheidungen zu versehen, dass der Baum noch treffsicherer wird, das heißt, so wenig falsche Entscheidungen trifft wie möglich. Aber die Bezeichnung der alten Astgabeln und Äste ändern wir nicht. Für die neue Astgabel an den Ast "Zahlungsart offline" stehen nur noch die Beispiele mit dem Attributwert "Zahlungsart offline" zur Debatte, und noch einmal nach der Zahlungsart zu fragen macht keinen Sinn.

In weiteren Wachstumsschüben wird nun jedes Blatt, das überhaupt noch Fehler macht, durch eine Astgabel samt Zubehör ersetzt. Am Ende trifft der Baum auf der gesamten Beispielmenge die richtige Entscheidung, es sei denn, die Beispiele selbst wären widersprüchlich: Wenn von zwei Transaktionen mit den Attributen (offline, standard, 750) die eine sauber war und die andere nicht, kann man es nicht vollständig richtig machen. Der Baum im Bild links ist nach diesem Verfahren aus unserer Beispielmenge konstruiert.

Entscheidungsbaumverfahren sind sehr schnell und in der Praxis sehr erfolgreich. Sie unterscheiden sich nicht im Grundprinzip, sondern vor allem in den Kriterien, nach denen die Fragen in die Astgabeln eingesetzt werden. Unser Kriterium war sehr einfach: Minimiere die Summe der Fehler. Wesentlich bessere Ergebnisse liefert das Kriterium des Informationsgewinns: Stelle diejenige Frage, deren Antwort am meisten Information über das Objekt preisgibt oder, was auf dasselbe hinausläuft, am wenigsten von der für eine perfekte Entscheidung noch notwendigen Information im Dunkeln lässt. Dieses Prinzip lässt sich mithilfe der klassischen Informationstheorie quantifizieren.

Nun hat unser Entscheidungsverfahren so erfolgreich gelernt, dass es, angewandt auf die Beispieldaten, keine Fehler macht – aber darauf kommt es leider gar nicht an. Das Verfahren soll nicht die Trainingsdaten perfekt beherrschen, sondern in künftigen Entscheidungssituationen möglichst wenig Fehler machen. Das kann nicht gelingen, wenn das lernende Programm in der Schule andere Bei-spiele vorgesetzt bekommt als später im echten Leben. Es ist eine Kunst für sich, das Lernmaterial so auszuwählen, dass es die zu erwartende Realität repräsentativ wiedergibt.

Aber darüber hinaus sind die besten Schüler unter den Verfahren später nicht die besten Entscheider. Wer zu viel Wert auf zufällige Einzelheiten des Trainingsmaterials legt, kann später leicht in die Irre laufen. Ein Verfahren, das tausend verschiedene Modelle zur Auswahl hat, läuft – theoretisch nachweisbar – ein höheres Risiko, bei späterer Benutzung einen hohen Fehler zu produzieren, als eines, das überhaupt nur hundert Modelle in Erwägung ziehen kann.

Allzu große Empfindsamkeit ist also von Nachteil. Daher werden die Verfahren häufig abgestumpft. Entscheidungsbäume werden im Wortsinne gestutzt: Man schneidet einige der zuletzt nachgewachsenen Äste wieder ab. Das erhöht zunächst den Fehler auf der Trainingsmenge, kann aber gleichwohl nützlich sein. Um diese Nützlichkeit einzuschätzen und damit auch herauszufinden, welche Äste man stutzen soll, greift man zu einem Trick. Man lässt den Baum nur mit etwa siebzig Prozent des Beispielmaterials lernen. Dann schaut man nach, wie gut die hier oder da gestutzten Bäume auf den restlichen dreißig Prozent des Trainingsmaterials arbeiten, und wählt schließlich den, der sich am besten geschlagen hat. Diese dreißig Prozent dienen also als Ersatz für wirklich neues Material – zu Recht, denn der Baum hat sie beim Lernen nicht gesehen.

Diese Art der Modellselektion ist wahrlich nicht sehr tiefsinnig – man versucht das beste Verfahren mit der Axt zu finden. Aber es ist höchst erfolgreich: Zwar gibt es für viele Zwecke bessere Lernverfahren, aber Entscheidungsbaumverfahren haben sich in der Praxis als ein De-facto-Standard durchgesetzt.

Vorhersagen machen Sinn für Dinge, die ihrer Natur nach einigermaßen vorhersehbar sind, wie etwa die Zahlungsfähigkeit eines Kreditnehmers oder der Umsatz einer Firma im nächsten Jahr. Gewisse Einzelereignisse vorherzusagen ist dagegen aussichtslos.

Vor einigen Jahren bekamen wir von einem Marktforschungsinstitut Daten darüber, welche Kunden in einer Reihe von Supermärkten welche Getränke in welchen Packungsgrößen, -arten und zu welchen Preisen gekauft hatten. Es wäre abwegig, aus solchen Daten vorherzusagen, welches Getränk ein einzelner Kunde kaufen wird, der soeben das Geschäft betreten hat. Dennoch können in den Daten interessante Gesetzmäßigkeiten stecken, die man gerne mit einem Data-Mining-Verfahren identifizieren möchte.

Wir ließen unser Verfahren Midos nach Gruppen von Kunden suchen, die sich beim Getränkekauf auffällig umweltfreundlich (Mehrwegflaschen) oder auffällig entgegengesetzt verhalten. Es gibt Millionen von Möglichkeiten, aus der Gesamtmenge der Kunden nach den in den Daten enthaltenen Attributen Untergruppen abzugrenzen. Nur zehn dieser Untergruppen beurteilte das Programm Midos, gestützt auf eine statistische Bewertungsfunktion, als hinreichend interessant und auffällig. Auf diese Weise stellt sich zum Beispiel heraus, dass Beamtenhaushalte, die nur einmal pro Woche einkaufen, eine auffällig hohe Mehrwegquote aufweisen. Dagegen entschieden sich weibliche Singlehaushalte auffallend selten für Mehrwegflaschen.

Wohlgemerkt: Das Kaufverhalten der weiblichen Singlehaushalte aus den Daten zu ermitteln ist keine Kunst, wenn man weiß, dass man danach fragen will – wohl aber, unter den Millionen denkbarer Untergruppen die der weiblichen Singles als interessant auszudeuten. Data Mining ist hier also eine Methode zur Erzeugung guter Vermutungen, die in einem weiteren Schritt näher untersucht werden können.

Hinter erfolgreichen Subgruppenentdeckungsverfahren wie Advanced Scout oder Midos stehen einerseits statistische Bewertungsfunktionen, andererseits ähnliche Algorithmen wie bei der strukturierten Suche nach Entscheidungsbäumen.

Eine weitere Klasse von Verfahren hat ihren Ursprung ebenfalls in der Analyse von Daten, wie sie an Supermarktkassen oder in Web-Shops entstehen (der "Warenkorbanalyse"). Diese so genannten Assoziationsregelverfahren entdecken, ob sich aus dem Kauf bestimmter Artikel mit einer gewünschten Sicherheit der Kauf bestimmter anderer Artikel schließen lässt. Ein Beispiel könnte sein: "Wer eine Fernsehzeitschrift und/oder eine Videokassette kauft, nimmt mit einer Wahrscheinlichkeit von mehr als zehn Prozent auch Erdnüsse mit." Man könnte also bei der Ladenplanung diese Artikel entsprechend platzieren.

Subgruppen-, Assoziations- und verwandte Verfahren sind nicht nur dadurch attraktiv, dass sie in Situationen, in denen vorhersagende Lernverfahren scheitern, noch Ergebnisse produzieren können, sondern sie eignen sich auch zum Einsatz bei sehr großen Datenbeständen. Da die Verfahren nicht ständig ein globales Modell optimieren müssen, können besonders effiziente Suchtechniken eingesetzt werden. Nutzt man zusätzlich Stichprobentechniken, so wird die Zeit, die man zur Entdeckung der interessantesten Subgruppen benötigt, sogar weitgehend unabhängig von der Größe des zu untersuchenden Datenbestandes.

Literaturhinweise


Unsicheres und vages Wissen. Von Christian Borgelt, Heiko Timm und Rudolf Kruse in: Handbuch der Künstlichen Intelligenz. Von G. Görz et al. (Hg.). Oldenbourg, München 2000, S. 291

Graphical Models – Methods for Data Analysis and Mining. Von Christian Borgelt und Rudolf Kruse. J. Wiley & Sons, Chichester 2002.

Bayesian Networks and Decision Graphs. Von Finn V. Jensen. Springer, New York 2001.

---

Aus: Spektrum der Wissenschaft 11 / 2002, Seite 85
© Spektrum der Wissenschaft Verlagsgesellschaft mbH