Oberseminar Datenbanken Carsten Severin Tobias Sorgatz Datamining

Oberseminar DatenbankenCarsten Severin Tobias Sorgatz

Datamining

Oberseminar Datenbanken: Datamining, Severin, Sorgatz

ÜberblickÜberblick 1. Einleitung 2. Eingaben 3. Ausgaben 4. Algorithmen 5. Glaubwürdigkeit 6. Maschinelles

Lernen in der Praxis


1.0. Beispiele1.0. Beispiele

Beispiel 1: Künstliche Befruchtung Eigenschaften definieren, die größte

Überlebenschance garantieren


1.1. Beispiele1.1. Beispiele

Beispiel 2: Vieh wird geschlachtet Gesundheit Lebenserwartung Fruchtbarkeit Gewicht


1.2. Situation1.2. Situation

Immer mehr Daten werden gespeichert Internet Preiswerte Speichermedien Mehr Anwendungen: Bilder, Filme Alle 20 Monate Verdopplung

der Daten


1.3. Lösung: Data Mining1.3. Lösung: Data Mining

Es ist eine Möglichkeit gesucht, dieDatenflut zu analysieren

Daten sollen ausgewertet werden Lösung: Data Mining


1.4.1. Datamining1.4.1. Datamining

Verarbeitung elektronisch gespeicherter Daten

Lernen: Wissen durch Studium aneignen Prozess der autom. oder halbautom.

Mustererkennung Maschinelles Lernen: Lernen

automatisieren


1.4.2. Data Mining1.4.2. Data Mining

Aneignen von Wissen Fähigkeit es zu verwenden Gezielte Suche in Datenbanken Analyse bereits vorhandener Daten Suche nach Mustern Ergebnisse ein weiteres Handeln

einbeziehen


1.5. Data Mining und Ethik1.5. Data Mining und Ethik

problematisch sind rassische und sexuelle Informationen

Undurchschaubarkeit von Daten (unvorhersehbare Auswertungen)

Viele Daten werden für neue Analysen zusammengefasst


1.6. Bias: Lernverfahren1.6. Bias: Lernverfahren

Zur Bestimmung des Lernverfahrens Sprachbias:

Ist die Beschreibung universal? Wird domänenwissen genutzt

Suchbias: bestmögliche Beschreibung finden

Bias zur Vermeidung der Überanpassung


2. Eingabe2. Eingabe

Wie werden die Daten zur Analyse eingegeben?


2.1. Eingabe der Daten2.1. Eingabe der Daten

Konzepte Instanzen Attribute


2.1.1. Konzepte2.1.1. Konzepte

Unabhängig von Art des Lernens Beschreibt was gelernt werden soll

Ausgabe des Lernverfahrens: Baum Regelmenge


2.1.2. Instanzen2.1.2. Instanzen

Jede Instanz ist ein eigenes Beispiel Zeile in einer Tabelle


2.1.3.1. Attribute2.1.3.1. Attribute

Attribut ist Spalte einer Tabelle Problem: Instanzen mit unterschiedlichen

Attributen -> Möglichst viele Attribute


2.1.3.2. Attribute2.1.3.2. Attribute

Numerische Attribute Nominale Attribute Ordinale Attribute


2.2. Beispiel2.2. Beispiel

Wie sehen einzulesende Datenmengen aus? Wie sehen Regelmengen aus?


2.2.1. Beispiel: Datensatz2.2.1. Beispiel: Datensatz


2.2.2. Beispiel: Baum2.2.2. Beispiel: Baum


2.2.3. Beispiel: Regelmenge2.2.3. Beispiel: Regelmenge


2.3. Aufbereitung 2.3. Aufbereitung

Aufbereitung der Eingabedaten Integration von verschiedenen Datenquellen Datacleaning Data Warehousing ARFF-Dateien


2.3.1. Data Warehousing2.3.1. Data Warehousing

Zusammenfassung von Datenquellen Unternehmensweite Datenbankintegration Keine Abteilungsgrenzen Aggregation von Daten


2.4. Eingabe: Fehlende Daten2.4. Eingabe: Fehlende Daten

Einträge außerhalb Gültigkeit (-1) Unterscheidung von fehlenden Daten(-1,-2) Wegen verändertes Experiment Wegen Messfehlern Wegen Verweigerung Ist Auftreten zufällig oder wichtig für

Analyse?


2.5. Eingabe: Genauigkeit2.5. Eingabe: Genauigkeit

Daten für andere Zwecke gespeichert Ungenauigkeiten plötzlich von anderer

Bedeutung Schreibfehler (sind Daten gleich?) Bewusste Manipulation


2.6. Arten des Lernens2.6. Arten des Lernens

Klassifizierendes Lernen Vorhandene Daten in Klassen fassen

Numerische Vorhersage Numerische statt diskrete Werte

Clustering Gruppieren von Instanzen


3. Ausgabe3. Ausgabe

3.1 Entscheidungstabellen

3.2 Entscheidungsbäume

3.3 Klassifikationsregeln

3.4 Assoziationsregeln

3.5 Regeln mit Ausnahmen

3.6 Bäume für numerische Vorhersage

3.7 Instanzbasierte Darstellung

3.8 Cluster


3.1 Entscheidungstabellen3.1 Entscheidungstabellen

Einfachste, elementarste Methode weniger einfach bei spezieller Auswahl von

Attributen Kompliziert: Auswahl der die Entscheidung

nicht beeinflussenden Attribute


3.2 Entscheidungsbäume3.2 Entscheidungsbäume

Ansatz: Teile und Herrsche Knoten eines Baumes bedingen

Auswertung eines Attributs Blätter stellen Klassifikationen dar


3.3 Klassifikationsregeln3.3 Klassifikationsregeln

Anwendung einer Regel verlangt Auswertung einer Menge von Attributen

Allgemein logische UND Verknüpfung der Bedingungen

Aus Baum: pro Blatt eine Regel, Auswertung jeder Regel eines Knotens auf dem Pfad von Wurzel zu Blatt


3.4 Assoziationsregeln3.4 Assoziationsregeln

Können nicht nur Klassen vorhersagen, sondern auch Attribute

Damit Vorhersage beliebiger Attributkombinationen

if temperatur =kalt then luftfeuchtigkeit = normal


3.5 Regeln mit Ausnahmen3.5 Regeln mit Ausnahmen

Vermeidung falscher Klassifikation durch Zulassen von Ausnahmen

Schaffen einer neuen Entscheidungsebene Bei Fortsetzung erhält man Baumstruktur if stimme = hoch then Frau except if eunuch then Mann


3.6 Bäume für numerische 3.6 Bäume für numerische VorhersagenVorhersagen

Auswertung eines numerischen Attributes


3.7 Instanzbasierte 3.7 Instanzbasierte DarstellungDarstellung

Auswendiglernen durch Merken von Trainingsinstanzen

Neue Instanz wird mit vorhandenen verglichen und der Klasse der ähnlichsten vorhandenen Instanz zugeordnet

BSP: Buchstabenerkennung


3.8 Cluster3.8 Cluster

Ausgabe eines Diagramms: Anzeige der in die Cluster eingeordneten Instanzen

Einfachster Fall: Zuweisung einer Clusternummer zu jeder Instanz


4. Algorithmen4. Algorithmen

4.1 Ableitung elementarer Regeln

4.2 statistische Modellierung

4.3 Teile und Herrsche

4.4 Abdeckungs- algorithmen


4.1 Ableitung elementarer 4.1 Ableitung elementarer RegelnRegeln

Baum auf einer Ebene Auswertung einer Regelmenge eines

Attributes für jedes attribut für jeden wert des attributes

zählen, wie oft jede klasse erscheint klasse mit häufigsten auftreten ermitteln regel aufstellen die diesem attributwert klasse zuordenet

fehlerrate der regeln berechnen regelmenge mit kleinsten fehler auswählen


4.2 Statistische Modellierung4.2 Statistische Modellierung

Nutzung aller Attribute Gewichtung für alle Attribute gleich Attribute werden als unabhängig

voneinander angesehen Rechnen mit Wahrscheinlichkeiten Auswertung von Hypothesen und

zugehörigen Ereignissen


4.3 Teile und Herrsche4.3 Teile und Herrsche Wahl eines Wurzelattributes Anlegen einer Verzweigung für jeden Wert Zerlegung der Beispielmenge in

Untermengen, eine für jeden Wert des Attr. Rekursive Anwendung für jede Verzweigung,

nur Instanzen die Verzweigung erreichen Alle Instanzen eines Knotens gleiche Klasse:

Konstruktion des Baumabschn. fertig


4.4 Abdeckungs-Algorithmen4.4 Abdeckungs-Algorithmen

Betrachtung einzelner Klassen nacheinander

Abdeckung aller Instanzen Auschluss klassenfremder Instanzen Ableitung einer Regel in jedem Schritt die

einige Instanzen abdeckt


5. Glaubwürdigkeit5. Glaubwürdigkeit

5.1 Trainieren und Testen 5.2 Leistungsvorhersage 5.3 Kreuzvalidierung 5.3.1 Leave one out 5.4 Vorhersage von Wahrscheinlichkeiten


5.1 Trainieren und Testen5.1 Trainieren und Testen

Bei richtiger Klassifikation: Erfolg Andernfalls : Fehler Angabe des Verhältnisses zwischen Erfolg

und Fehler: Gesamtleistung des Klassifizierers

Nicht effektiv, da mit alten Daten gearbeitet wird, Vorhersage schwer möglich


5.2 Leistungsvorhersage5.2 Leistungsvorhersage

Fehlerrate (fr) sei bestimmt (5.1) Bestimmung von Erfolgsrate (er): 1-fr Mit Mitteln der

Wahrscheinlichkeitsrechnung Bestimmung der Wahrscheinlichkeit von er.

Bei grossen Testreihen: Normalverteilung


5.35.3 KreuzvalidierungKreuzvalidierung

Aufteilung der Datenmenge in Test und Trainingsmenge, feste Partitionen (Bsp3)

Garantiert beste Mischung der Beispiele aller Klassen

Nacheinander Ausführung von: Testen einer Partition, trainieren mit den zwei

Anderen


5.3.1 Leave-one-out5.3.1 Leave-one-out N-fache Kreuzvalidierung N ist Anzahl der Instanzen in der

Datenmenge Nacheinander:

Weglassen einer Instanz Training mit restlichen Instanzen

Auswertung aller N Ergebnisse durch Mittelwertbildung


5.4 Vorhersage von 5.4 Vorhersage von WahrscheinlichkeitenWahrscheinlichkeiten

Bisheriges Ziel: hohe Erfolgsrate für Vorhersage

Nicht mehr wahr oder falsch (Vorhersage hat tatsächlichen Wert der Instanz)

Einführung beliebig vieler Abstufungen Verschiedene Gewichtung von

unterschiedlichen Vorhersageergebnissen


6. Maschinelles Lernen in der 6. Maschinelles Lernen in der PraxisPraxis

Algorithmen sind in Praxis viel komplexer Behandlung realer Probleme Schwerpunkte: numerische Attribute

Fehlerbehandlung Anwendung von Statistiken


6.1 Entscheidunsbäume6.1 Entscheidunsbäume

Erweiterung des Teile-und-herrsche Algo: Behandlung numerischer und fehlender Werte Beschneidung (wegen Überanpassung) Umwandlung der Entscheidungsäume in

Klassifikationsregeln


6.1.1 Numerische Werte6.1.1 Numerische Werte

Anpassung an nominale (boolsche) Struktur Beispiel: Temperaturabfrage

noyesyesnonoyesnoyesyesyesnoyes

858381807572717069686564


6.1.2 Fehlende Werte6.1.2 Fehlende Werte

Zerlegung der Instanz, unter Verwendung numerischer Gewichtung, und Bearbeitung mit allen Verzweigungen des Baumes

Bei Erreichen eines Blattknotens: Zusammenfügen der Entscheidungen des Blattknotens unter Verwendung der Gewichtung, die mit “durchgesickert” ist


6.1.3 Pruning6.1.3 Pruning

6.1.3.1 Postpruning:Nachträgliches Beschneiden des fertigen

Baumes („usammengehörige Attribute“

6.1.3.2 Prepruning Beschneidung während der Baumbildung (Arbeitseinsparung)


6.1.4 Von Bäumen zu Regeln6.1.4 Von Bäumen zu Regeln

Pro Blatt eine Regel Alle Auswertungen von Wurzel zum Blatt

werden UND-verknüpft Löschen von Bedingungen, die keinen, oder

schlechten, Einfluß auf Regel haben Entfernen von Regelduplikaten


6.2 Clustering6.2 Clustering

Ziel: Einteilung der Instanzen in natürliche Gruppen

Arten von Clustern: Ausschliessende Überlappende Wahrscheinlichkeitsverteilte Hierarchisch (Vererbungsebenen)


6.2.1 k-Mittelwert Clustering6.2.1 k-Mittelwert Clustering

Bildung von k Clustern in numerischen Domänen, durch Aufteilung der Instanzen in disjunkte (elementefremd) Cluster

Wahl von Zentren und Zuweisung der Instanzen zum nächstliegenden Zentrum

Mittelwertbildung aller Instanzen-neues Zentrum Wiederholung bis keine neuen Zentren entstehen


6.2.2 inkrementelles 6.2.2 inkrementelles ClusteringClustering

Hierarchische Gruppierung der Instanzen aufgrund eines „Quallitätsmasses

“(auch Kategorienützlichkeit) für Cluster Inkrementell (feinere Aufteilung Instanz für

Instanz)


6.2.3 Statistisches Clustering6.2.3 Statistisches Clustering

Mischmodell aus verschiedenen Wahrscheinlichkeitsverteilungen

Eine Verteilung pro Cluster Jede Verteilung gibt Wahrscheinlichkeit für

Clusterzugehörigkeit einer Instanz an (jede Instanz genau zu einem Cluster)


Vielen Dank für die Vielen Dank für die AufmerksamkeitAufmerksamkeit

Wir wünschen ein allseits schönes Wochenende.

Noch Fragen? (rhetorische Frage)


QuellenQuellen

Titel: Data Mining Praktische Werkzeuge und Techniken

für das maschinelles Lernen

Autoren: Ian H. Witten, Eibe Frank

Documents

Oberseminar Datenbanken Carsten Severin Tobias Sorgatz Datamining