Data Mining - Technische Universität Chemnitz · Data Mining Seite 6 3. Aufbereitung der Daten Sichtung und Behandlung fehlerbehafteten oder fehlenden Datenmaterials. Mögliche Schritte

Data Mining

Kompaktkurs an der Berufsakademie Mannheim

Sommersemster 2005

Prof. Dr. Werner Dilger

Data Mining Seite 2

Inhalt 1. Einführung .................................................................................................................................................................. 3

1.1. Wozu ist Data Mining gut?.............................................................................................................................. 4 1.2. Der Data Mining Prozess................................................................................................................................. 5 1.3. Kosten-Nutzen-Rechnung am Beispiel einer Direktmailingaktion.................................................................. 6 1.4. Übersicht über die Methoden des Data Mining ............................................................................................... 9

1.4.1. Statistische Methoden ................................................................................................................................. 9 1.4.2. Fallbasiertes Schließen ............................................................................................................................... 9 1.4.3. Entscheidungsbäume ................................................................................................................................ 10 1.4.4. Neuronale Netze ....................................................................................................................................... 10 1.4.5. Genetische Algorithmen ........................................................................................................................... 12

2. Entscheidungsbäume............................................................................................................................................... 29 2.1. Induktives Lernen .................................................................................................................................................. 29 2.2. Lernen von Entscheidungsbäumen ................................................................................................................ 29

2.2.1. Entscheidungsbäume als Performanzelemente..................................................................................... 29 2.2.2. Induktion von Entscheidungsbäumen aus Beispielen .......................................................................... 30 2.2.3. Abschätzung der Performanz des Lernalgorithmus ............................................................................. 34 2.2.4. Praktischer Gebrauch des Entscheidungsbaum-Lernens...................................................................... 35

2.3. Die Verwendung der Informationstheorie ..................................................................................................... 35 2.3.1. Das Prinzip des Informationsgewinns.................................................................................................. 36 2.3.2. Rauschen und Overfitting .................................................................................................................... 37 2.3.3. Erweiterung der Anwendbarkeit von Entscheidungsbäumen............................................................... 39

3. Lineare und Nichtlineare Entscheidungsbäume ...................................................................................................... 41 3.1. Geometrische Interpretation .......................................................................................................................... 41 3.2. Lineare Entscheidungsbäume ........................................................................................................................ 43 3.3. Nichtlineare Entscheidungsbäume................................................................................................................. 45

4. Neuronale Netze...................................................................................................................................................... 49 4.1. Gehirn und Computer .................................................................................................................................... 49

4.1.1. Struktur und Arbeitsweise des Gehirns................................................................................................ 49 4.1.2. Vergleich zwischen Gehirn und Computer .......................................................................................... 50

4.2. Neuronale Netze ............................................................................................................................................ 51 4.2.1. Grundbegriffe....................................................................................................................................... 51 4.2.2. Notationen............................................................................................................................................ 51 4.2.3. Einfache Rechenelemente .................................................................................................................... 52 4.2.4. Netzstrukturen...................................................................................................................................... 54 4.2.5. Optimale Netzstrukturen ...................................................................................................................... 55

4.3. Perzeptrone .................................................................................................................................................... 56 4.3.1. Struktur von Perzeptronen.................................................................................................................... 56 4.3.2. Repräsentationsfähigkeit von Perzeptronen ......................................................................................... 57 13.3.3. Erlernen linear separierbarer Funktionen ............................................................................................. 58

4.4. Mehrschichtige zyklenfreie Netze ................................................................................................................. 59 4.4.1. Back-Propagation-Lernen .................................................................................................................... 59 4.4.2. Eigenschaften des Back-Propagation-Lernens..................................................................................... 62

4.5. Anwendungen Neuronaler Netze................................................................................................................... 63 4.5.1. Englische Aussprache .......................................................................................................................... 63 4.5.2. Erkennen von Handschrift.................................................................................................................... 64 4.5.3. Autofahren ........................................................................................................................................... 64

5. Der prudsys DISCOVERER ................................................................................................................................... 67 5.1. Einige wichtige Begriffe................................................................................................................................ 67

5.1.1. Lern-, Evaluierungs- und Klassifikationsdatenbank ............................................................................ 67 5.1.2. Merkmalstypen..................................................................................................................................... 67 5.1.3. Fehlende Werte .................................................................................................................................... 68 5.1.4. Transformation und Normierung ......................................................................................................... 69

5.2. Gains-Chart, Lift-Chart, Segment-Fortschrittsanzeige .................................................................................. 70 5.2.1. Gains-Chart .......................................................................................................................................... 70 5.2.2. Lift-Chart ............................................................................................................................................. 71 5.2.3. Die Segment-Fortschrittsanzeige ......................................................................................................... 71

5.3. Die Baumdarstellung ..................................................................................................................................... 71

Berufsakademie Mannheim Sommersemester 2005

Data Mining Seite 3

5.4. Kostenanalyse................................................................................................................................................ 72

Literatur

Berry, M.J.A., Linoff, G. (1997), Data Mining Techniques. For Marketing, Sales, and Customer Support. John Wiley & Sons, Inc., New York.

Hand, D., Mannila, H., Smyth, P. (2001), Principles of Data Mining. MIT Press, Cambridge, Mass.

Prudential Systems Software GmbH (2001), prudsys DISCOVERER 3.0. User Guide, Chemnitz.

Russel, S., Norvig, P. (1995), Artificial Intelligence. A Modern Approach. Prentice Hall, Upper Saddle River, NJ.

Witten, I.A., Frank, E. (2000) Data Mining. Practical Machine Learning Tools and Techniques with Java Implementations. Academic Press, San Diego, CA.


Data Mining Seite 4

1. Einführung

1.1. Wozu ist Data Mining gut?

Die wichtigsten kommerziellen Einsatzgebiete des Data Mining sind die folgenden:

Direktmarketing

Direktmailing Außendienst

Kundenprofile

Erstellung von Kundenprofilen Top-Kunden-Analyse Neukundengewinnung Kündigerprävention

Handel

Warenkorbanalyse eCommerce

Finanz- und Versicherungswirtschaft

Risikoanalyse (Credit Scoring) Missbrauchsentdeckung (Fraud Detection)

Beim Einsatz von Data Mining zur Optimierung der Direktmailingaktion werden zunächst zwei vorbereitende Schritte gemacht.

Schritt 1: Profilerstellung

Es wird ein Produktprofil erstellt. Dazu werden Erfahrungen aus früheren Direktmailingaktionen zu gleichen oder ähnlichen Produkten benötigt, eine so genannte Responsedatenbank. Ist diese nicht vorhanden (z.B. bei einem ganz neuen Produkt), dann kann eine Testaktion mit einer kleinen Auflage (z.B. 5000 – 20000) repräsentativer Kunden durchgeführt werden. Bei neuen Produkten oder bei Direktmarketingaktionen in neuen Märkten wird eine solche Testaktion generell durchgeführt. Zum einen erhält man damit Informationen darüber, wie ein Produkt beim Kunden ankommt, zum anderen können die Ergebnisse des Tests als Responsedatenbank verwendet werden.

Schritt 2: Qualifizierung einer Kundendatenbank

Die gesamte Kundendatenbank wird auf Grund der Responsedatenbank in verschiedene Kunden-segmente unterteilt. Jedes Segment hat ein bestimmtes Responsepotenzial. Damit erhält jeder Kunde ebenfalls ein bestimmtes Responsepotenzial und man erhält eine Schätzung über sein Responseverhalten. Die Kundensegmente werden anschließend nach ihrem Responsepotenzial in absteigender Reihenfolge angeordnet. Es liegt in der Entscheidung des Leiters der Direkt-marketingaktion, bis zu welchem Segment er die Kunden in die Aktion einbeziehen soll. Das Responsepotenzial ermöglicht eine genaue Berechnung dafür, bis zu welchem Segment die Marketingaktion kostendeckend ist, wobei man im Interesse einer Gewinnmaximierung üblicher-weise nicht bis zu dieser Grenze geht.


Data Mining Seite 5

Die qualifizierte (segmentierte) Kundendatenbank dient nun als Eingabe für das Data Mining Verfahren. Jeder qualifizierte Datensatz beschreibt einen Kunden, der angeschrieben werden soll. Der Datensatz sollte aussagekräftige Merkmale enthalten. Typische Merkmale sind:

• personen- und haushaltsbezogene Informationen (z.B. Struktur des Haushalts, Lifestyle, Alter)

• Wohngebietscharakteristiken (z.B. Postleitzahlen, Wohngegend, soziales Umfeld) • Interessen (z.B. Auto, Reisen, Tiere, Kultur, Sport) • Informationen über Beschäftigungen (z.B. Beruf, Einkommen) • Konsumvorlieben • Immobilien • Kreditkartentypen

Eine besonders wichtige Angabe ist natürlich, ob der betreffende Kunde auf die vorausgegangene Direktmailingaktion reagiert hat oder nicht.

Die Kundensegmente in der qualifizierten Kundendatenbank können durch Beziehungen zwischen den Werten, oder genauer: bestimmter Wertebereiche, mehrerer relevanter Merkmalen beschrieben werden. Ein Beispiel für ein Segment ist:

Alle Haushalte, • die aus mehr als 5 Personen bestehen • deren Jahreseinkommen zwischen 40.000 € und 50.000 € liegt, • die zwei Autos fahren • und die ein Eigenheim besitzen.

Diese Beziehung kann man auch formal definieren, dann sieht sie z.B. so aus:

CountPerson > 5 and Income ≥ 40.000 and Income ≤ 50.000 and CountCar = 2 and houseowner = true

Die Unterteilung der Kundendatenbank in die Segmente erfolgt nicht einfach zufällig, vielmehr werden die Segmente so bestimmt, dass Responsepotenzial der in einem Segment liegenden Kunden entweder deutlich höher oder deutlich niedriger ist als das durchschnittliche Responsepotenzial aller Kunden.

1.2. Der Data Mining Prozess

Data Mining ist keine einzelne Methode, sondern ein Prozess, der in sechs Phasen verläuft und in dem verschiedene Methoden zum Einsatz kommen können. Die Grundlage des Prozesses sind die Daten in einer Datenbank. Die einzelnen Phasen sind

1. Verstehen des Geschäftsproblems

Definition der Aufgabe, vgl. dazu Abschnitt 1.1, Festlegung der Erfolgskriterien.

2. Verstehen der Daten

Überblick über alle zentral oder dezentral vorhandenen Daten, die das Geschäftsproblem betref-fen, Klärung des Zugriffs auf die Daten.


Data Mining Seite 6

3. Aufbereitung der Daten

Sichtung und Behandlung fehlerbehafteten oder fehlenden Datenmaterials. Mögliche Schritte hierfür sind Löschen von Datensätzen mit fehlenden Werten, Ersetzung nicht vorhandener Merkmalswerte, Identifizierung von Ausreißern mit Hilfe explorativer Untersuchungen, Bestim-mung einer für das Geschäftsproblem relevanten Teilmenge der Daten.

4. Modellbildung

Identifizierung eines Kunden- oder Produktsegments, das signifikant andere Eigenschaften als die Gesamtheit aller Kunden bzw. Produkte hat, z.B. durch Segmentierung der Daten mittels Data Mining.

5. Bewertung der Ergebnisse

Soll-Ist-Vergleich mit kritischer Bewertung der Resultate des Data Mining, eventuell Hinzu-nahme weiterer Daten.

6. Individuelle Lösung

Umsetzung der Data Mining Ergebnisse, d.h. Integration in die täglichen Geschäftsabläufe, eventuell Entwicklung einer individuellen Lösung in Form von Spezialsoftware.

Der Ablauf des Data Mining Prozesses ist in Abbildung 1.1 graphisch dargestellt.

Verstehen des

GeschäftsproblemsVerstehen der

Daten

Modellbildung Bewertung der Ergebnisse

Aufbereitung der Daten

Individuelle Lösung Daten-

bank

Abbildung 1.1

1.3. Kosten-Nutzen-Rechnung am Beispiel einer Direktmailingaktion

Wichtige Begriffe beim Direktmailing:

Ausstattungsdichte

Relation zwischen der Gesamtauflage eines Werbemittels, z.B. Katalog oder Mailing, und der Gesamtzahl aller potentiell zur Verfügung stehenden Haushalte einer Kundendatenbank. Die Aus-stattungsdichte beeinflusst die Kosten: Je höher die Ausstattungsdichte, desto höher die Kosten.

Responserate


Data Mining Seite 7

Anteil an Haushalten, die auf eine Mailingaktion positiv reagieren, z.B. Bestellung, Abonnement oder Ähnliches. Die Responserate beeinflusst auf den zu erwartenden Nettoumsatz und damit auf den Gewinn.

Kosten-Umsatz-Relation (KUR) Maß für den prozentualen Werbemittelanteil am Nettoumsatz, wird nach folgender Formel berech-net:

zNettoumsatnWerbekoste%100KUR ⋅

=

Bei festem Nettoumsatz ist die KUR ein Maß für den notwendigen Werbemitteleinsatz zur Erzie-lung dieses Umsatzes. Ist z.B. KUR = 10%, dann können mit 10 € Werbemittel 100 € Nettoumsatz erzielt werden.

Deckungsbeitrag (DB)

Es werden zwei Formen des Deckungsbeitrags definiert, eine ohne und eine mit Berücksichtigung der Werbekosten:

DB I = Nettoerlös – variable Kosten DB II = Nettoerlös – variable Kosten – Werbekosten

Der Zusammenhang zwischen Nettoumsatz, Deckungsbeiträgen und Ausstattungsdichte lässt sich wie in Abbildung 1.2 graphisch darstellen.

10% 20% 30% 40% 50% 60% 70% 80% 90% 100%

Nettoumsatz

Bestellwert

Werbekosten

Ausstattungsdichte

DB I

DB II

Abbildung 1.2


Data Mining Seite 8

Fragen

1. Welche vorbereitenden Schritte sind für die Optimierung des Data Mining-Einsatzes bei einer Direktmailing-Aktion erforderlich?

2. Wie werden Segmente in einer qualifizierten Kundendatenbank beschrieben und wie unterteilt man die Datenbank in Segmente?

3. Wie lassen sich die Ergebnisse einer in Segmente unterteilten Kundendatenbank in einem Gains-Chart veranschaulichen?

4. Aus welchen Schritten besteht der Data Mining-Prozess?

5. Welcher Schritt des Data Mining-Prozesses ist vermutlich der zeitaufwändigste?

6. Welches sind die wichtigsten Begriffe beim Direktmailing und wie kann man ihr Verhältnis zueinander grafisch darstellen?


Data Mining Seite 9

2. Übersicht über die Methoden des Data Mining

2.1. Statistische Methoden

Wichtige Aufgaben beim Data Mining sind die Korrelationsanalyse, die Hauptkomponentenana-lyse, die Regressionsanalyse und das Clustering. Zur Lösung dieser Aufgaben können herkömm-liche statistische Methoden, aber auch andere Verfahren, z.B. spezielle Neuronale Netze, eingesetzt werden.

Bei der Korrelationsanalyse geht es darum, Beziehungen zwischen verschiedenen Daten dadurch zu finden, dass man die Werte bestimmter Attribute in den Datensätzen vergleicht. Lässt sich bei einem signifikant großen Teil der Werte eine feste Relation, etwa Gleichheit oder ein funktionaler Zusammenhang wie x = f(y), feststellen, dann gelten die Daten als korreliert. Bei der Hauptkompo-nentenanalyse geht es darum, diejenigen Attribute von Datensätzen zu bestimmen, die die Daten-sätze charakterisieren, d.h. die die wichtigsten zur Beschreibung der Datensätze sind. In der Regel ist dies nur ein kleiner Teil der Attribute, und es ist dann möglich, sich bei weiteren Untersuchun-gen der Datensätze auf diese Attribute zu beschränken.

Die Regressionsanalyse untersucht Zeitreihendaten. Sie betrachtet die in der Vergangenheit etwa bei Reihenmessungen angefallenen Daten und versucht, aus dem zeitlichen Verlauf eines einzelnen oder mehrerer Werte den nächst folgenden Wert bzw. die nächst folgenden Werte zu prognostizie-ren. Beim Clustering wird eine Menge von Daten in Teilmengen ähnlicher Daten unterteilt. Es wird angenommen, dass die Daten durch Datensätze gleicher Struktur beschrieben sind. Dann sind sich Daten ähnlich, wenn sie in bestimmten ausgesuchten Attributen weitgehend übereinstimmende Werte haben. Clustering wird also immer relativ zu bestimmten Attributen gemacht.

2.2. Fallbasiertes Schließen

Die Idee des fallbasierten Schließens ist, Beispiele gelöster Probleme aus einem bestimmten An-wendungsbereich abzuspeichern um sie später zur Lösung neuer, aber ähnlich gearterer Probleme heranziehen zu können. Dazu müssen die Beispielprobleme zusammen mit ihrer Lösung in einem geeigneten Format dargestellt werden und in einer speziellen Datenbank, der Fallbasis, abgespei-chert werden. Ein Paar, bestehend aus Problembeschreibung und zugehöriger Lösung, heißt Fall. Liegt ein neues Problem vor, dann muss dieses zunächst in dem vorgegebenen Format dargestellt werden. Dann können die Problembeschreibungen der in der Fallbasis vorhandenen Fälle durch-sucht werden um eine zum neuen Problem möglichst ähnliche Beschreibung zu finden. Dafür benötigt man ein Ähnlichkeitsmaß für die Problembeschreibungen. Der Fall mit der ähnlichsten Problembeschreibung wird genommen und seine Lösung als mögliche Lösung des neuen Problems ausgegeben. Eine Anpassung der gefundenen Lösung an die neuen Gegebenheiten kann u.U. erforderlich sein.

Problem- und Lösungsbeschreibungen können in beliebigen Formaten definiert werden. Der einfachste und häufig vorkommende Fall ist, dass die Problembeschreibung aus einer Reihe von Parameterwerten besteht und die Lösungsbeschreibung ein einzelner Parameterwert ist. Ein Fall ist dann ein gewöhnlicher Datensatz bestehend aus den Werten einer Reihe von Attributen. Im Fall von numerischen Werten lässt sich das Ähnlichkeitsmaß als Euklidischer Abstand oder als (eventuell modifizierte) Manhattan-Distanz zwischen den Datensätzen definieren.


Data Mining Seite 10

2.3. Entscheidungsbäume

Es sei eine Menge von Datensätzen mit n Attributen gegeben. Jeder Datensatz charakterisiert ein bestimmtes Objekt und wird als Beispiel bezeichnet. Geometrisch betrachtet kann man ein Beispiel als Punkt im n-dimensionalen Raum auffassen. Jedes Attribut muss eine kleine Menge diskreter Werte als Wertebereich haben. Bei Attributen mit kontinuierlichen Wertebereichen muss eine Diskretisierung vorgenommen werden. Eines der Attribute wird als Zielattribut ausgewählt oder es wird ein neues Attribut als Zielattribut eingefügt. Das Zielattribut habe m verschiedene diskrete Werte.

Mittels eines speziellen Algorithmus wird nun ein Entscheidungsbaum konstruiert. Die Konstruk-tion verläuft in folgenden Schritten:

1. Wähle ein Attribut a (außer dem Zielattribut) aus und entferne a aus der Menge der zur Verfü-gung stehenden Attribute. a habe die Werte w1, w2, ..., wk.

2. Unterteile die Menge der vorhandenen Beispiele so in k Teilmengen, dass das Attribut a in der j-ten Teilmenge nur den Wert wj hat.

3. Führe die Schritte 1. und 2. für jede der k Teilmengen und die reduzierte Attributmenge durch.

Dieser rekursive Algorithmus stoppt, wenn alle Attribute aufgebraucht sind oder wenn die Beispiel-menge leer wird oder wenn die Beispielmenge homogen wird, d.h. wenn jedes Attribut für alle Beispiele in der Menge denselben Wert hat.

In der Regel wird von dem Algorithmus eine graphische Struktur aufgebaut, und zwar ein Baum. Die Knoten des Baums werden von den Beispielmengen gebildet, insbesondere der Wurzelknoten von der Menge aller am Anfang vorliegenden Beispiele, die Kanten von den Werten des an einem Knoten ausgesuchten Attributs. Homogene Beispielmengen bilden Blätter im Baum. Die Beschrif-tung eines Wegs von der Wurzel zu einem Blatt beschreibt, unter welchen Bedingungen, d.h. bei welchem Wert für das jeweils ausgewählte Attribut, die am Blatt stehende Menge zustande kommt. Der Entscheidungsbaum kann als Klassifikator verwendet werden, er gibt für jedes neue Beispiel an, zu welchem Blatt, also zu welcher Teilmenge, es gehört.

2.4. Neuronale Netze

Ein Neuronales Netz ist ein gerichteter Graph, dessen Knoten, genannt Einheiten, selbstständig rechnende Einheiten sind. Die Kanten verbinden die Knoten in verschiedenen typischen Formen, wodurch sich unterschiedliche Typen von Netzen ergeben. Man unterscheidet zwei Hauptklassen von Neuronalen Netzen, die Feed-forward-Netze und die rekurrenten Netze, danach, ob der zu Grunde liegende Graph zyklenfrei ist oder nicht. Häufig sind die Knoten in Teilmengen, genannt Schichten, unterteilt. Die Schichten sind geordnet, etwa als S1, S2, ..., Sn. Kanten werden bei geschichteten Netzen nur zwischen Knoten aufeinander folgender Schichten gesetzt, d.h. nur zwischen Si und Si+1 (i = 1, ..., n-1). Abbildung 1.3 zeigt ein geschichtetes Feed-forward-Netz.



Eingabeschicht Ausgabeschicht

verborgene Schichten

.

.

.

.

.

.

.

.

.

. . .

. . .

Abbildung 1.3

Die Einheiten bestehen meist aus zwei Teilen. Jeder Teil wird durch eine Funktion gebildet. Die beiden Teile, d.h. die beiden Funktionen, sind nacheinander angeordnet, so dass die Ausgabe der ersten Funktion Eingabe der zweiten ist. Die erste Funktion erhält ihre Eingaben über die Kanten, die von den vorgeschalteten Einheiten zu ihr führen, und die zweite Funktion überträgt ihre Aus-gabe über Kanten an nachgeschaltete Einheiten. Die erste Funktion ist eine Integrationsfunktion, die aus der Menge der Eingaben einen einzelnen Wert berechnet. Meist wird dazu die Addition benutzt. Die zweite Funktion, genannt Aktivierungsfunktion, ist meist eine Schwellenwertfunktion. Bei mehrschichtigen Netzen ist es insbesondere die Sigmoidfunktion wegen der einfachen Differenzier-barkeit. Die Eingänge in eine Einheit, d.h. die eingehenden Kanten, sind gewichtet. Jeder Eingang xi hat ein eigenes Gewicht wi. Eine typische Einheit ist in Abbildung 1.4 dargestellt.

+

w1

y

Integrations-funktion

Aktivierungs-funktion

w2

w3

w4

w5

x1

x2

x3

x4

x5

Abbildung 1.4

Ein Neuronales Netz kann trainiert werden, man sagt auch: es kann lernen. Die einfachste Form des Lernens ist das überwachte Lernen. Man gibt dem Netz eine Reihe von Beispielen in beliebiger Reihenfolge und wiederholt ein. Für jedes Beispiel ist bekannt, was die gewünschte Ausgabe sein soll. Stimmt die Ausgabe des Netzes für ein Beispiel mit der gewünschten überein, dann braucht nichts getan zu werden. Weichen tatsächliche und gewünschte Ausgabe voneinander ab, dann müssen die Gewichte im Netz so verändert werden, dass sich der Fehler bei der Ausgabe verringert. Dieser Prozess erfolgt im Idealfall so lange, bis alle Beispiele richtig berechnet werden. Das Netz ist nun trainiert und repräsentiert eine bestimmte Funktion. Damit ist es in der Lage, neue Beispiele zu berechnen, d.h. einen mutmaßlichen Funktionswert für diese auszugeben.



2.5. Genetische Algorithmen

Genetische Algorithmen laufen auf Populationen von Genomen ab. Ein Genom ist eine Folge von Genen. Die Gene sind die elementaren Informationseinheiten genetischer Algorithmen, im einfachs-ten Fall sind sie (kurze) Bitstrings. Die genetischen Algorithmen erzeugen in einer großen Schleife immer neue Generationen von Genomen durch Anwendung der Operationen Selektion, Kreuzung und Mutation. Dabei werden folgende Schritte durchgeführt:

1. Definiere die Genome und eine Fitnessfunktion und erzeuge eine initiale Population von Genomen.

2. Modifiziere die aktuelle Population durch Anwendung der Operationen Selektion, Kreuzung und Mutation.

3. Wiederhole Schritt 2 so lange, bis sich die Fitness der Population nicht mehr erhöht.

Das Ziel des Algorithmus ist die Fitness der Genome zu maximieren. Die Fitnessfunktion, die belie-big definiert sein kann, bewertet jedes neu entstandene Genom. Dazu muss das Genom in seinen zugehörigen Phänotyp umgewandelt werden, auf ihm operiert die Fitnessfunktion. Durch die Operation Selektion werden bei jedem Durchlauf durch die Schleife des Algorithmus eine bestimmte Anzahl von Genomen ausgesondert, sie sorgt also dafür, dass die Größe der Population konstant bleibt. Gleichzeitig werden (in der Regel) die fittesten Genome für die nächsten Operatio-nen ausgewählt. Bei der Operation Kreuzung werden zwei Genome an einer bestimmten Stelle aufgetrennt und die beiden Bruchstücke über Kreuz zu neuen Genomen kombiniert. Die Operation Mutation verändert ein oder mehrere zufällig ausgewählte Gene in einem Genom, wodurch ebenfalls ein neues Genom entsteht. Abbildung 1.5 illustriert die drei Operationen.

2.6. Assoziationsregeln

Eine Assoziationsregel ist eine einfache Wahrscheinlichkeitsaussage über das gemeinsame Vorkommen bestimmter Ereignisse oder Muster in einer Datenbasis. Sie sind besonders geeignet für dünn besetzte Transaktionsdatenmengen und für diese ist ihre Erstellung besonders effizient. Für die folgende Darstellung wird der Einfachheit halber angenommen, dass alle Variablen binäre Werte haben. Eine typische Assoziationsregel hat dann die Form

IF A = 1 AND B = 1 THEN C = 1 mit Wahrscheinlichkeit p

A, B und C sind binäre Variable und p eine bedingte Wahrscheinlichkeit für das Ereignis C = 1, wenn A = 1 und B = 1 gegeben sind, d.h. p = p(C = 1|A = 1, B = 1). Die Wahrscheinlichkeit p wird Konfidenzwert oder Genauigkeitswert der Regel genannt, die Wahrscheinlichkeit p(A = 1, B = 1, C = 1) heißt Support-Wert der Regel.

Bei der Bestimmung von Assoziationsregeln sucht man gewöhnlich nach solchen Regeln, deren Konfidenzwert größer als ein Schwellenwert pc und deren Support-Wert größer als ein Schwellen-wert ps ist. Zum Beispiel kann man nach Regeln suchen, deren Support-Wert größer als 0.05 und deren Konfidenzwert größer als 0.8 ist.

Praktische Anwendung finden die Assoziationsregeln meist in der Warenkorbanalyse. Bei dieser Data Mining Aufgabe versucht man zu bestimmen, mit welcher Wahrscheinlichkeit bestimmte Objekte zu einer Menge zusammengestellt werden, konkret: welche Waren typischerweise zusam-men gekauft werden und deshalb im selben Warenkorb zu finden sind. Die Zusammengehörigkeit bestimmter Produkte lässt sich formal mittels einer Datenmatrix mit n Zeilen (entsprechend den Warenkörben) und p Spalten (entsprechend den kaufbaren Produkten) darstellen. Die Einträge in



die Matrix sind binär. Eine solche Matrix ist typischerweise sehr groß (n in der Größenordnung von Millionen und p in der Größenordnung von Zehntausenden) und sehr dünn besetzt, weil ein Warenkorb meist nur wenige Produkte enthält. Die Assoziationsregeln finden einfache Muster in solchen Daten in effizienter Weise.

Mutation

KreuzungTrennstelle

n-te Generation (n+1)-te Generation Selektion

Abbildung 1. 5

Es gibt verschiedene Algorithmen zur Bestimmung von Assoziationsregeln. Sie lassen sich typi-scherweise nach folgenden Aspekten beschreiben:

1. Aufgabe Beschreibung der Assoziationen zwischen Variablen 2. Struktur Probabilistische Regeln 3. Score-Funktion Schwellenwerte für Konfidenzwert und Support-Wert 4. Suchmethode Systematische Suche (Breitensuche mit Pruning)



5. Datenmanagement Mehrfaches lineares Durchmustern

Die Score-Funktion ist eine einfache Boolesche Funktion. Eine Regel erhält den Wert 1, wenn ihr Support-Wert und ihr Konfidenzwert über den jeweiligen Schwellenwerten (s.o.) liegen. Das Ziel ist, alle Regeln mit dem Score-Wert 1 zu bestimmen.

Ein Problem bei der Bestimmung der Assoziationsregeln ist ihre große Zahl. Sie liegt in der Größenordnung O(p2p-1), wenn die Variablen binär sind, sie ist also exponentiell. Jedoch lässt sich die Suchzeit einschränken, wenn man eine Eigenschaft der Assoziationsregeln berücksichtigt. Es gilt nämlich, dass p(A = 1, B = 1) ≤ ps, wenn p(A = 1) ≤ ps oder p(B = 1) ≤ ps.

Diesen Sachverhalt kann man nutzen, indem man zuerst nach individuellen Ereignissen sucht (z.B. A = 1), die eine größere Wahrscheinlichkeit als ps haben. Dazu ist nur ein lineares Durchmustern der Datenbasis erforderlich. Ein Ereignis bzw. eine Menge von Ereignissen heißt häufig, wenn seine (ihre) Wahrscheinlichkeit größer als ps ist. Alle Paare von häufigen Ereignissen werden als mögliche häufige Mengen der Größe 2 betrachtet. In dieser Weise kann man immer größere häufige Mengen erzeugen. Beim Übergang von häufigen Mengen der Größe k – 1 zu Mengen der Größe k kann man alle Mengen der Größe k entfernen, die eine Teilmenge der Größe k – 1 enthalten, die ihrerseits nicht häufig auf Ebene k – 1 ist. Dieser Schritt ist möglich auf Grund der Produktregel der Wahrscheinlichkeitstheorie.

Hat man nun eine Liste möglicher häufiger Mengen der Größe k bestimmt, dann wird für diese mittels einer linearen Durchmusterung der Datenbasis ermittelt, welche davon wirklich häufig sind. Danach werden die Mengen zu Mengen der Größe k + 1 kombiniert, es findet wieder ein Pruning-Schritt statt usw. bis keine häufigen Mengen mehr gebildet werden können. Schließlich ist noch ein letzter Durchlauf durch die Datenbasis zu machen, bei dem geprüft wird, welche Kombinationen häufiger Mengen – als Regeln betrachtet – auch die Schwellenwertbedingung für den Konfidenz-wert erfüllen und diese werden als Assoziationsregeln ausgegeben.



Fragen

1. Nennen Sie einige statistische Methoden im Data Mining! Für welche Zwecke lassen sich die Methoden einsetzen?

2. Was ist das Prinzip des fallbasierten Schließens und wie wird eine Lösung für einen neuen Fall bestimmt?

3. Was benötigt ein Verfahren für die Erstellung eines Entscheidungsbaums als Voraussetzungen?

4. In welchen Schritten wird ein Entscheidungsbaum aufgebaut?

5. Wie ist ein mehrschichtiges Feed-forward-Netz aufgebaut?

6. Welche Struktur hat eine Einheit in einem Feed-forward-Netz?

7. Wie kann ein Neuronales Netz lernen?

8. Welche Operationen werden in einem Genetischen Algorithmus verwendet und in welchen Schritten läuft der Algorithmus ab?

9. Was beschreibt eine Assoziationsregel und welche Form hat sie?

10. Was ist der Support-Wert und der Konfidenzwert einer Assoziationsregel?

11. Nennen Sie typische Aspekte eines Algorithmus zur Bestimmung von Assoziationsregeln!

12. Mit welcher Methode lässt sich bei der Suche nach Assoziationsregeln in einer Datenbank ihre Zahl beschränken?

13. Wie bestimmt man aus einer häufigen Menge eine Assoziationsregel?



3. Entscheidungsbäume

3.1. Induktives Lernen

Die Konstruktion von Entscheidungsbäumen ist eine Form des Maschinellen Lernens, speziell des induktiven Lernens, noch spezieller des überwachten Lernens. Bei dieser Form des Lernens bekommt der Lerner eine Menge von Beispielen vorgelegt und soll daraus eine Funktion erlernen. Die Beispiele haben die Form von Paaren (x, f(x)). x ist die Eingabe und f(x) die Ausgabe der zu lernenden Funktion. Die reine induktive Inferenz (kurz Induktion) besteht aus der folgenden Aufgabe: Bestimme auf Grund einer Menge von Beispielen von f eine Funktion h, genannt Hypothese, die f approximiert.

Im Allgemeinen können viele Hypothesen aus Beispielen generiert werden. Wird einer Hypothese gegenüber einer anderen der Vorzug gegeben, dann heißt dies ein Bias. Weil es fast immer eine große Zahl möglicher konsistenter Hypothesen gibt, haben alle Lernalgorithmen einen irgendwie gearteten Bias.

3.2. Lernen von Entscheidungsbäumen

3.2.1. Entscheidungsbäume als Performanzelemente

Ein Entscheidungsbaum nimmt als Eingabe ein Objekt oder eine Situation, beschrieben durch eine Menge von Eigenschaften und erzeugt als Ausgabe eine Ja-/Nein-Entscheidung. Ein innerer Knoten eines Entscheidungsbaums entspricht einem Test auf den Wert einer der Eigenschaften und die nach unten von dem Knoten wegführenden Kanten sind mit den möglichen Werten der Eigenschaft markiert. Ein Blattknoten entspricht einem Booleschen Wert, der als Ergebnis ausgegeben wird, wenn das Blatt erreicht wird.

Als ein Beispiel wird das Entscheidungsproblem betrachtet, ob man in einem Restaurant auf einen freien Tisch warten soll, wenn alle Tische besetzt sind. Man möchte also eine Definition für das Zielprädikat Warten in Form eines Entscheidungsbaums lernen. Zunächst müssen die Eigen-schaften oder Attribute festgelegt werden, mit denen die Beispiele beschrieben werden. Die folgen-den Attribute werden gewählt:

1. Alternative: Gibt es in der Nähe ein geeignetes anderes Restaurant? 2. Bar: Gibt es in dem Restaurant eine komfortable Bar zum Warten? 3. Fr/Sa: Ist Freitag oder Samstag? 4. Hungrig: Bin ich hungrig? 5. Gäste: Wie viele Leute sind im Restaurant (keine, einige oder voll)? 6. Preis: In welchem Preissegment liegt das Restaurant (€, €€, €€€)? 7. Regen: Regnet es draußen? 8. Reservierung: Habe ich reserviert? 9. Typ: Um welche Art von Restaurant handelt es sich (Französisch, Italienisch, Chinesisch oder

Burger)? 10. Wartezeit: Welche voraussichtliche Wartezeit wird vom Restaurant geschätzt?

Ein Entscheidungsbaum für das Problem könnte z.B. der in Abbildung 3.1 dargestellte sein. Die Attribute Preis und Typ sind darin nicht benutzt, weil sie angesichts der Datenlage irrelevant sind. Der Baum kann in eine Menge von Implikationen (8 insgesamt) umgesetzt werden, die den Pfaden



von der Wurzel zu den mit Ja markierten Blättern entsprechen. Zum Beispiel ergibt der Pfad über die Knoten Wartezeit und Hungrig die Implikation

∀r Gäste(r, Voll) ∧ Wartezeit(r, 10-30) ∧ Hungrig(r, Nein) ⇒ Warten(r)

Gäste?

Wartezeit?Nein Ja

Alternative? Hungrig?Nein Ja

Reservierung? Fr/Sa? Alternative?Ja

Regen?Bar? NeinJa Ja Ja

Nein NeinJa Ja

Keine EinigeVoll

>60 30-60 10-300-10

Nein Nein

Nein Nein Nein

Nein Nein

Ja Ja

Ja Ja Ja

Ja Ja

Abbildung 3.1

3.2.2. Induktion von Entscheidungsbäumen aus Beispielen

Ein Beispiel wird durch die Werte der Attribute und den Wert des Zielprädikats beschrieben. Der Wert des Zielprädikats heißt Klassifikation des Beispiels. Ist der Wert wahr für ein Beispiel, so heißt dieses ein positives Beispiel, andernfalls ein negatives Beispiel. Die gesamte Menge der Beispiele heißt Trainingsmenge. Tabelle 3.1 enthält die Beispiele für das Restaurant-Beispiel.

Attribute Ziel Bei-spiele Alter-

native Bar Fr/Sa Hung-

rig Gäste Preis Regen Reser-

vierungTyp Warte-

zeit Warten

X1 Ja Nein Nein Ja Einige €€€ Nein Ja Franz 0-10 Ja X2 Ja Nein Nein Ja Voll € Nein Nein Chin 30-60 Nein X3 Nein Ja Nein Nein Einige € Nein Nein Burger 0-10 Ja X4 Ja Nein Ja Ja Voll € Nein Nein Chin 10-30 Ja X5 Ja Nein Ja Nein Voll €€€ Nein Ja Franz >60 Nein X6 Nein Ja Nein Ja Einige €€ Ja Ja Ital 0-10 Ja X7 Nein Ja Nein Nein Keine € Ja Nein Burger 0-10 Nein X8 Nein Nein Nein Ja Einige €€ Ja Ja Chin 0-10 Ja X9 Nein Ja Ja Nein Voll € Ja Nein Burger >60 Nein X10 Ja Ja Ja Ja Voll €€€ Nein Ja Ital 10-30 Nein X11 Nein Nein Nein Nein Keine € Nein Nein Chin 0-10 Nein X12 Ja Ja Ja Ja Voll € Nein Nein Burger 30-60 Ja

Tabelle 3.1

Bei der Erstellung eines Entscheidungsbaums aus Beispielen kommt es darauf an, ein Muster zu extrahieren, das eine große Zahl von Fällen in knapper Form beschreibt. Der Entscheidungsbaum muss vor allem eine knappe, aber informationsreiche Repräsentation von Fällen sein und er sollte alle Trainingsbeispiele erfassen.



Ein Entscheidungsbaum repräsentiert eine einfache Hypothese, wenn er möglichst klein ist. Das Problem, den kleinsten Entscheidungsbaum zu finden, ist nicht lösbar. Aber man kann versuchen einen möglichst kleinen zu finden. Zu diesem Zweck geht der DECISION-TREE-LEARNING-Algorith-mus so vor, dass er immer das wichtigste Attribut zuerst testet. Damit ist dasjenige Attribut gemeint, nach dem sich die Beispiele am stärksten unterscheiden. Auf diese Weise wird versucht eine korrekte Klassifikation mit einer kleinen Menge von Tests zu bekommen, wodurch die Pfade im Entscheidungsbaum kurz werden und der Baum insgesamt klein wird.

function DECISION-TREE-LEARNING(Beispiele, Attribute, Default) returns einen Baum inputs: Beispiele eine Menge von Beispielen Attribute eine Menge von Attributen Default ein Default-Wert für das Zielprädikat

if Beispiele ist leer then return Default else if alle Beispiele haben dieselbe Klassifikation then return die Klassifikation else if Attribute ist leer then return MAJORITY-VALUE(Beispiele) else best ← CHOOSE-ATTRIBUTE(Attribute, Beispiele) Baum ← ein neuer Entscheidungsbaum mit Wurzeltest best for each Wert vi von best do Beispielei ← {Elemente von Beispiele mit best = vi} subtree ← DECISION-TREE-LEARNING(Beispielei, Attribute - best, MAJORITY-VALUE(Beispiele)) füge einen Zweig zu Baum hinzu mit Marke vi und Teilbaum subtree end return Baum

Nachdem die erste Aufteilung der Testmenge durch das erste Attribut erfolgt ist, entstehen mehrere neue Entscheidungsbaum-Lernprobleme mit weniger Beispielen und einem Attribut weniger. Die Konstruktion des Entscheidungsbaums erfolgt also rekursiv. Vier Fälle sind dabei zu unterscheiden:

1. Wenn die Teilmenge einige positive und einige negative Beispiele enthält, dann wähle das beste Attribut um sie weiter zu unterteilen.

2. Wenn alle Beispiele in der Teilmenge positiv sind (bzw. alle negativ), dann ist der Zweig des Baums fertig. Man kann mit Ja (bzw. Nein) antworten.

3. Wenn die Teilmenge leer ist bedeutet dies, dass kein Beispiel mit der durch die bisher benutzten Attribute beschriebenen Eigenschaften vorliegt. Es wird ein Defaultwert zurückgegeben, der auf Grund der mehrheitlichen Klassifikation am Vorgängerknoten berechnet wird.

4. Wenn keine Attribute übrig sind aber die Teilmenge nicht leer ist und sowohl positive als auch negative Beispiel enthält, bedeutet dies, dass diese Beispiele zwar verschiedene Klassifikation haben, aber die gleichen Eigenschaften, zumindest so weit sie auf Grund der definierten Attri-bute beschreibbar sind. Dieser Fall tritt ein, wenn einige Daten falsch sind, d.h. wenn sie ver-rauscht sind, oder wenn die Attribute nicht genügend Information enthalten um die vorliegende Situation zu beschreiben oder wenn die Domäne nicht deterministisch ist. In diesem Fall trifft man eine Mehrheitsentscheidung.

Konstruiert man den Entscheidungsbaum für die Beispiele von Tabelle 3.1 nach dieser Vorschrift, dann erhält man den Entscheidungsbaum von Abbildung 3.2.



Gäste?

Nein Ja Hungrig?

Fr/Sa?

Typ?

Nein Ja

Nein

Keine EinigeVoll

Ja

Nein

Nein

Ja

Französisch BurgerChinesischItalienisch

NeinJa Ja

Abbildung 3.2

Die Diskrepanz zwischen dem Ausgangsbaum und dem Ergebnisbaum ist sicher auch der kleinen Anzahl von Beispielen zuzuschreiben. Mit mehr Beispielen dürfte der Unterschied geringer ausfal-len. Der Baum von Abbildung 3.2 ist auch keine sehr gute Hypothese, denn z.B. kommt der Fall, dass ein Restaurant voll und die Wartezeit 0 – 10 Minuten beträgt, gar nicht vor. Im Fall von Hunger sagt der Baum, dass nicht gewartet werden soll, aber wenn die Wartezeit höchstens 10 Minuten beträgt, wird man in der Regel warten. Diese Beobachtung führt zu der Frage nach der Korrektheit der Hypothese.

3.2.3. Abschätzung der Performanz des Lernalgorithmus

Die Qualität eines Lernalgorithmus kann danach eingeschätzt werden, wie gut er neue, vorher nicht betrachtete Beispiele klassifiziert. Dazu muss die Klassifikation dieser Beispiele aber vorab bekannt sein. Die Menge der Beispiele, die für diesen Zweck verwendet werden, heißt Testmenge. Diese Menge reserviert man üblicherweise von vornherein für den Test, ansonsten müsste man nach neuen Beispielen suchen und deren Klassifikation bestimmen. Im Einzelnen geht man in folgenden Schritten vor:

1. Sammle eine große Menge von Beispielen.

2. Unterteile die Menge in zwei disjunkte Teilmengen, die Trainingsmenge und die Testmenge.

3. Erzeuge mit dem Lernalgorithmus auf der Basis der Trainingsmenge eine Hypothese H.

4. Bestimme den Prozentsatz der Beispiele in der Testmenge, die durch H korrekt klassifiziert werden.

5. Wiederhole die Schritte 1. bis 4. für verschieden große und zufällig ausgewählte Trainingsmen-gen.

Durch Anwendung dieser Schritte erhält man eine Menge von Daten, auf Grund derer die durch-schnittliche Vorhersagequalität als eine Funktion der Größe der Trainingsmenge angegeben werden kann. Diese Funktion ergibt in grafischer Form dargestellt die so genannte Lernkurve des Algorith-mus auf der betrachteten Domäne. Abbildung 3.3 zeigt den ungefähren Verlauf der Lernkurve für den Algorithmus DECISION-TREE-LEARNING auf der Restaurant-Domäne.



0 20 40 60 80 100Größe der Trainingsmenge

40

50

80

70

60

90

100

Korrekt-heit auf

derTest-

mengein %

Abbildung 3.3

3.2.4. Praktischer Gebrauch des Entscheidungsbaum-Lernens

Gas-Öl-Trenner

BP brachte 1986 ein Expertensystem mit Namen GASOIL zum Einsatz. Sein Zweck war der Entwurf von Gas-Öl-Trennanlagen für Offshore-Ölplattformen. Die Trennung von Gas und Öl erfordert ein sehr großes, komplexes und teures Trennsystem, dessen Entwurf eine Anzahl von Attributen betrifft, u.a. die relativen Anteile von Gas, Öl und Wasser, die Flussrate, den Druck, die Dichte, die Viskosität und die Temperatur. GASOIL enthielt ungefähr 2500 Regeln. Der Bau eines solchen Expertensystems von Hand erfordert ungefähr 10 Personen-Jahre. Statt dessen wurde ein Entschei-dungsbaum-Lernverfahren auf eine Datenbasis von existierenden Entwürfen angewandt. Damit wurde das Expertensystem in 100 Personen-Tagen entwickelt. Es soll besser sein als menschliche Experten und viele Millionen Dollar eingespart haben.

Fliegen lernen im Flugsimulator

Sammut et al. entwickelten 1992 einen automatischen Piloten für eine Cessna. Die Beispieldaten wurden durch Beobachtung von drei erfahrenen Piloten im Flugsimulator gewonnen. Jeder der Piloten führte 30 Minuten lang einen vordefinierten Flugplan aus. Jedes Mal wenn ein Pilot eine Steueraktion durchführte indem er eine Steuervariable setzte, z.B. Schub oder Flügelklappen, wurde ein Beispiel erzeugt. Insgesamt wurden 90000 Beispiele erzeugt, jedes durch 20 Zustandsvariable beschrieben und mit der durchgeführten Aktion markiert. Aus den Beispielen wurde mit Hilfe des C4.5-Algorithmus ein Entscheidungsbaum erzeugt. Der Baum wurde in ein C-Programm umgesetzt und dieses in die Steuerschleife des Flugsimulators integriert, so dass das Programm das Flugzeug selbst fliegen konnte.

Die Ergebnisse waren überraschend. Das Programm konnte nicht nur fliegen, sondern sogar besser fliegen als die menschlichen Lehrer. Der Grund dafür ist, dass beim Lernen gelegentliche Fehler der einzelnen Menschen durch Verallgemeinerung ausgeglichen wurden. Das deutet an, dass für schwierige Aufgaben wie das Fliegen von Hubschraubern, die schwere Lasten bei starkem Wind tragen, mit den Methoden des Maschinellen Lernens Autopiloten entwickelt werden könnten. Bis jetzt gibt es solche nicht und es gibt auch nur wenige menschliche Piloten dafür.



3.3. Die Verwendung der Informationstheorie

3.3.1. Das Prinzip des Informationsgewinns

Zur Implementierung der CHOOSE-ATTRIBUTE-Funktion benötigt man ein Maß für gute und unnütze Attribute. Dieses Maß muss seinen größten Wert für perfekte Attribute und seinen kleinsten Wert für völlig wertlose Attribute haben. Ein solches Maß ist der erwartete Gehalt an Information, der von einem Attribut geliefert wird. Der Begriff Information ist dabei im Sinne der Shannonschen Informationstheorie zu verstehen. Eine Information in diesem Sinn ist eine Antwort auf eine Frage. Wenn man eine auf die Frage schon relativ gut zutreffende Vermutung hat, dann ist die Antwort weniger informativ als wenn man überhaupt nichts weiß.

In der Informationstheorie wird der Gehalt einer Information in Bits gemessen. Ein Bit Information genügt um eine Ja/Nein-Frage zu beantworten, über deren Antwort man keinerlei Vorstellung hat, wie dem Fall einer Münze. Wenn die möglichen Antworten vi auf die Frage die Wahrscheinlichkei-ten P(vi) haben, dann ist der Informationsgehalt I der tatsächlichen Antwort definiert durch

∑=

−=n

iiini vPvPvPvPI

12 )(log)())(),...,((

Dies ist der durchschnittliche Informationsgehalt der verschiedenen Antworten (die -Aus-drücke), gewichtet mit den Wahrscheinlichkeiten der Antworten.

P2log−

Beim Entscheidungsbaum-Lernen ist die zu beantwortende Frage: Was ist die korrekte Klassifika-tion für ein gegebenes Beispiel? Ein korrekter Entscheidungsbaum liefert die Antwort. Eine Schät-zung der Wahrscheinlichkeiten der möglichen Antworten vor dem Test der Attribute ist durch das Verhältnis der positiven und negativen Beispiele in der Trainingsmenge gegeben. Angenommen, die Trainingsmenge enthalte p positive und n negative Beispiele. Dann wird der Informationsgehalt einer korrekten Antwort wie folgt abgeschätzt:

npn

npn

npp

npp

npn

nppI

++−

++−=⎟⎟

⎠

⎞⎜⎜⎝

⎛++ 22 loglog,

Der Test eines einzelnen Attributs gibt im Allgemeinen nicht so viel Information, aber immerhin einen Teil davon. Das Maß an Information, das ein Attribut liefert, wird daran gemessen, wie viel Information nach dem Attributtest für eine korrekte Antwort noch benötigt wird. Jedes Attribut A unterteilt die Trainingsmenge E in die Teilmengen E1, ..., Ev, entsprechend ihren Werten für A, wobei angenommen ist, dass A v verschiedene Werte haben kann. Jede Teilmenge Ei enthält pi positive und ni negative Beispiele. Wenn man also auf dem i-ten Zweig des Baums fortfährt, benötigt man zusätzlich ))(,)(( npnnppI iiiiii ++ Bits an Information um die Frage zu beant-worten. Ein zufällig ausgewähltes Beispiel hat mit der Wahrscheinlichkeit )()( npnp ++ ii den i-ten Wert des Attributs, deshalb benötigt man im Durchschnitt nach dem Test des Attributs A

⎟⎟⎠

⎞⎜⎜⎝

⎛++

⋅++

= ∑= ii

i

ii

iv

i

ii

npn

npp

Inpnp

AstRe ,)(1

Bits an Information um das Beispiel zu klassifizieren. Der Informationsgewinn aus dem Attribut-test ist definiert durch die Differenz zwischen dem ursprünglichen Informationsbedarf und dem neuen Informationsbedarf:



)(,)( AstRenp

nnp

pIAGain −⎟⎟⎠

⎞⎜⎜⎝

⎛++

=

Die Heuristik, die in der CHOOSE-ATTRIBUTE-Funktion benutzt wird, ist das Attribut mit dem größ-ten Informationsgewinn zu wählen.

3.3.2. Rauschen und Overfitting

Wenn es bei einem Lernproblem eine große Menge möglicher Hypothesen gibt, besteht die Gefahr, dass man beim Lernen bedeutungslose Regelmäßigkeiten in den Daten entdeckt. Dieses Problem heißt Overfitting. Es ist ein sehr allgemeines Phänomen und kann in allen möglichen Lernverfah-ren vorkommen, nicht nur bei Entscheidungsbäumen.

Eine einfache Technik zur Vermeidung des Overfitting ist das Pruning. Durch das Pruning wird verhindert, dass Attribute für die Aufteilung einer Menge verwendet werden, die nicht wirklich relevant sind, selbst wenn die Beispiele an diesem Knoten nicht uniform klassifiziert sind. Die Frage ist, wie irrelevante Attribute entdeckt werden. Der Informationsgewinn bietet dafür eine Möglichkeit. Angenommen man teilt eine Menge von Beispielen mit einem irrelevanten Attribut auf. Die entstehenden Teilmengen haben dann in der Regel etwa dieselbe Verteilung von positiven und negativen Beispielen wie die ursprüngliche Menge. Dann ist der Informationsgewinn annä-hernd Null. Damit stellt sich umgekehrt die Frage, ab welchem Informationsgewinn es sich lohnt, ein Attribut zur Aufteilung der Beispielmenge zu verwenden.

Mit dieser Frage beschäftigen sich statistische Signifikanztests. Ein Signifikanztest beginnt mit der Annahme, es gebe in den vorliegenden Beispielen kein zugrunde liegendes Muster (so genannte Nullhypothese). Dann werden die Daten analysiert um festzustellen, wie weit sie vom vollständi-gen Fehlen eines Musters abweichen. Wenn der Grad der Abweichung statistisch unwahrscheinlich ist, dann besteht beträchtliche Evidenz für das Vorliegen eines signifikanten Musters in den Daten.

Im Fall der Entscheidungsbäume ist die Nullhypothese, dass das gerade betrachtete Attribut irrele-vant ist und damit der Informationsgewinn für eine unendlich große Menge von Beispielen Null. Nun muss die Wahrscheinlichkeit dafür berechnet werden, dass unter Annahme der Nullhypothese eine Beispielmenge der Größe v die beobachtete Abweichung von der erwarteten Verteilung der positiven und negativen Beispiele zeigt. Die Abweichung kann man messen, indem man die tat-sächlichen Anzahlen positiver und negativer Beispiele in jeder Teilmenge, also pi und ni, mit den erwarteten Zahlen und vergleicht, wobei man vollständige Irrelevanz voraussetzt: ip̂ n̂i

npnp

nnnpnp

pp iii

iii +

+⋅=

++

⋅= ˆˆ

Ein Maß für die Gesamtabweichung ist definiert durch

i

iiv

i i

ii

nnn

pppD

ˆ)ˆ(

ˆ)ˆ( 2

1

2 −+

−= ∑

=

Unter der Nullhypothese ist der Wert von D entsprechend der χ2-Verteilung mit v – 1 Freiheitsgra-den verteilt. Mit Hilfe von χ2-Tabellen oder statistischer Software kann dann berechnet werden mit welcher Wahrscheinlichkeit ein Attribut wirklich irrelevant ist.



Pruning hat auch Vorteile, wenn Daten verrauscht sind. Bei stark verrauschten Daten liefern Bäume mit Pruning bessere Ergebnisse als solche ohne Pruning. Bäume mit Pruning sind meist wesentlich kompakter und deshalb auch besser zu verstehen.

3.3.3. Erweiterung der Anwendbarkeit von Entscheidungsbäumen

Um den Einsatzbereich des Entscheidungsbaum-Lernens zu erweitern muss man Maßnahmen er-greifen um fehlende Daten zu ergänzen und um Attribute mit besonderen Eigenschaften verwendbar zu machen.

• Fehlende Daten In vielen Anwendungsbereichen sind nicht alle Attributwerte für jedes Beispiel bekannt. Das kann daran liegen, dass sie nicht erfasst wurden oder dass es zu aufwändig ist sie zu ermitteln. Hier sind zwei Probleme zu lösen: 1. Wie modifiziert man die Konstruktion des Entscheidungsbaums, insbesondere die Definition des Informationsgewinns, wenn bei einigen Beispielen Attributwerte fehlen? 2. Wie klassifiziert man ein neues Beispiel mit einem beste-henden Entscheidungsbaum, wenn eines der Testattribute nicht anwendbar ist?

• Attribute mit vielen Werten Ist die Zahl der Werte eines Attributs sehr hoch, dann kann der Extremfall eintreten, dass das Attribut für jedes Beispiel einen eigenen Wert hat und damit lauter einelementige Mengen entstehen. Der Informationsgewinn hätte dann für dieses Attribut den höchsten Wert. Trotzdem wäre das Attribut irrelevant oder nutzlos. Um solche Attribute zu behandeln kann man den Gain Ratio verwenden.

Ein Beispiel für ein solches extremes Attribut im Restaurant-Beispiel wäre der Name des Restaurants. Er liefert, zumindest innerhalb eines bestimmten geografischen Bereichs, lauter ein-elementige Teilmengen.

• Attribute mit kontinuierlichen Werten Manche Attribute haben kontinuierliche Werteberei-che, z.B. Attribute wie Größe oder Gewicht. Um sie für das Entscheidungsbaum-Lernen ver-wendbar zu machen diskretisiert man üblicherweise die Wertebereiche. Das wird meistens von Hand gemacht. Eine bessere Methode ist, die Attribute im Rahmen des Lernprozesses vorab zu behandeln um herauszufinden, welche Unterteilung des Wertebereichs die nützlichste Informa-tion für die Zwecke der Klassifikation liefert.



Fragen

1. Was ist beim induktiven Lernen die Eingabe und was wird gelernt?

2. Was ist bei einem Entscheidungsbaum die Ein- und die Ausgabe und womit sind die Knoten und Kanten des Baums beschriftet?

3. Was ist die Trainingsmenge für das Erzeugen eines Entscheidungsbaums?

4. Wie ist ein Beispiel für die Eingabe in einen Entscheidungsbaum aufgebaut?

5. Welche Eigenschaften sollte ein „guter“ Entscheidungsbaum haben?

6. Skizzieren Sie die Vorgehensweise des Decision-Tree-Learning-Algorithmus!

7. Was kann man tun, wenn bei der Entscheidungsbaumkonstruktion die Menge der Beispiele leer wird und was, wenn die Menge der Attribute leer wird?

8. Wie kann man die Qualität (Performanz) eines Entscheidungsbaums oder allgemein einer Hypothese abschätzen?

9. Was ist ein Maß für gute oder nützliche Attribute bei der Entscheidungsbaumkonstruktion?

10. Wie berechnet man den Informationsgehalt einer Antwort auf eine Frage?

11. Wie lässt sich der Informationsgewinn aus einem Attributtest berechnen?

12. Was ist Overfitting und wie kann man es vermeiden?

13. Wie kann man Entscheidungsbäume konstruieren, wenn die Attribute der Beispiele kontinuierliche Wertebereiche haben?


Documents

Data Mining - Technische Universität Chemnitz · Data Mining Seite 6 3. Aufbereitung der Daten Sichtung und Behandlung fehlerbehafteten oder fehlenden Datenmaterials. Mögliche Schritte