Infos - Startseite - Hochschule Wismarcleve/vorl/dmining14/fdm8bwM.pdf · 1 Einführung Wissensextraktion 1.3 Ablauf einer Datenanalyse Folie 1-20 (25) 1.3.4 Datentransformation Datentransformation

Wissensextraktion

Prof. Dr. Jürgen Cleve / Prof. Dr. Uwe Lämmel

Hochschule Wismar

26. Januar 2015

InfosLehrveranstaltungen 2 V + 2 Ü, geteilt:

I Prof. Lämmel: NNI Prof. Cleve: Klassische Verfahren

Prüfung Projekt und MP 30min

Skript, Folien, Übungen etc. in Stud.IP: Wissensextraktion

Skript und Folien CopyShop

Literatur Cleve/Lämmel: Data Mining, Oldenbourg 2014http://www.wi.hs-wismar.de/dm-buchs. auch Skript und Stud.IP

KNIME http://www.knime.org/ KNIME Desktop

Modul DM in ILIAS, etliche Zusatzinfos (Videos, Tests)

Weitere Infos unter Stud.IP

Inhaltsverzeichnis

Einführung

Data Mining – Grundlagen

Anwendungsklassen

Wissensrepräsentation

Methoden und Verfahren

Datenvorbereitung

Bewertung

1 Einführung Wissensextraktion

26. Januar 2015

Inhaltsverzeichnis

Einführung


Anwendungsklassen



Datenvorbereitung

Bewertung


26. Januar 2015

Inhaltsverzeichnis – Kapitel 1

EinführungData Mining und Business IntelligenceAuswertung von MassendatenAblauf einer Datenanalyse


Folie 1-1 (6)

Einführung

Data you don’t need is never lost.Ander’s first negative Principle of Computers

Was ist Data Mining?


1.1 Data Mining und Business Intelligence Folie 1-2 (7)

Business Intelligence

I Business Intelligence (BI) ist ein relativ neuer Begriff.

I Effektiver/effizienter Umgang mit dem Unternehmenswissen fürdas Überleben wichtig



Business Intelligence

I Nach und nach: Reihe von Techniken, Programmen etc. fürUnternehmenswissen

I Heute: Business Intelligence – Zusammenfassung dieserTechniken und Architekturen für eine effizienteVerwaltung/Analyse des Unternehmenswissens

I Aufgaben von BI: Wissensgewinnung, -verwaltung und-verarbeitung.

I Querbezüge zuI InformationsmanagementI Datenbanken/Data WarehouseI Künstliche IntelligenzI Data Mining (inkl. OLAP, Statistik)



Business Intelligence – Definition

I Verschiedene Definitionen des Begriffs Business Intelligence.

I Business Intelligence im engeren/weiteren/weiten Sinn.




Business Intelligence im engeren Sinn:I Kernapplikationen, die eine Entscheidungsfindung direkt

unterstützen.I Online Analytical Processing (OLAP)I die Management Information Systems (MIS)I Executive Information Systems (EIS)I . . .




Etwas weiterer BI-Begriff:I alle Analyse-orientierten Anwendungen

I Data MiningI ReportingI Analytisches Customer Relationship ManagementI . . .




BI im weiten Verständnis:I Alle Anwendungen, die im Entscheidungsprozess benutzt

werden.I PräsentationssystemeI Datenspeicherung und -verwaltungI . . .




Abbildung Business Intelligence [Kemper et al.]



Business Intelligence – Data Mining

I Schwerpunkt dieser Vorlesung: Wissensextraktion / DataMining

I . . . nur kleiner Ausschnitt aus dem BI-Spektrum


1.2 Auswertung von Massendaten Folie 1-10 (15)

Was fangen wir mit den Unmengen von Daten an?

Industrielle Prozessdaten

Umsatzdaten

Genom-Daten

Bilder

Textinformationen



Motivation

I weltweit stetig steigende DatenflutI grobe Schätzungen: Verdoppelung alle 20 Monate

I Daten über den initialen Zweck hinaus benutzen

I Data Mining = Datenschürfen

I Suche nach Mustern oder auffälligen Häufungen

I Suche nach Beurteilungskriterien für vorgegebene Ziele

I Ausführbar zu Zeiten schwacher Computerauslastung (z.B.nachts)



Stories of success

I Erzeugen eines Entscheidungsbaums (generiert aus altenKreditdaten) als Entscheidungshilfe für die Bewertung derKreditwürdigkeit eines Kunden

I Generierung von Mustern von typischen Reisenden, um denVerkauf von Billigflügen oder -urlauben zu managen

I Windeln und Bier: Analyse des Kaufverhaltens ergibt, dassderjenige, der Windeln kauft, sehr häufig auch Bier kauft, abernicht umgekehrt.

I Analyse der Gene bei Diabetes-Kranken, um typische Gene zuerkennen



Vorhersage von Klausurnoten

<= 6 > 6

<= 6 > 6 <= 6 > 6

<= 1 > 1 <= 8 > 8

Grammatik

Logik TM

5 (17.0/1.0) Grundlagen 3 (2.0) Logik

5 (2.0) 4 (6.0/1.0) 3 (2.0/1.0) 2 (2.0)

Abb. 1: Entscheidungsbaum für die TI-Klausur 2013/14


1.3 Ablauf einer Datenanalyse Folie 1-14 (19)

Ablauf einer Datenanalyse

Folgende Phasen unterscheidet man beim Data Mining:

Selektion Auswahl der geeigneten Datenmengen

Datenvorverarbeitung Skalierung, Ausreißer . . .

Transformation Umwandlung in adäquate Datenformate

Data Mining eigentliches Suchen nach Mustern etc.

Interpretation / Evaluation Interpretation der Ergebnisse undAuswertung



Ablauf einer Datenanalyse

Datenselektion

Datenvorverarbeitung

Datentransformation

Data Mining

Interpretation

Evaluation &

Daten

bereinigte Daten

und

Muster

Information

Daten

Zieldaten

bereinigte

transformierte

Regeln

......

Wissen

Abb. 2: Ablauf eines Data-Mining-Prozesses [Fayyad et al.]



1.3.1 CRISP Data-Mining-Modell

CRISP Data-Mining-Modell

Das CRISP-DM-Modell wurde durch NCR, Daimler-Benz, ISL, OHRAentwickelt.Cross Industry Standard Process for Data Mining(http://www.crisp-dm.org/).Man geht von einem Lebenszyklus in 6 Etappen aus:

1. Verstehen der Aufgabe

2. Verständnis der Daten

3. Datenvorbereitung

4. Data Mining (Modellbildung)

5. Evaluation

6. Einsatz im & Konsequenzen für Unternehmen



1.3.1 CRISP Data-Mining-Modell

CRISP Data-Mining-Modell

Data

Understanding

Data

Understanding

Business

Deployment

Data

Preparation

Modelling

Evaluation

Abb. 3: CRISP-Modell



1.3.2 Datenselektion

Datenselektion

I Welche Daten sind verfügbar?

I Zusammenführen von Daten aus unterschiedlichen Quellen

I interne / externe Daten



1.3.3 Datenvorverarbeitung

Datenvorverarbeitung

I Qualität des Zieldatenbestands untersuchen und

I durch Einsatz geeigneter Verfahren verbessern

I Fehlerhafte Daten

I Fehlende Daten

I Ausreißer



1.3.4 Datentransformation

Datentransformation

I Analyserelevanten Zieldatenbestand in ein solchesDatenbankschema transformieren,

I das von dem verwendeten Data-Mining-System verarbeitetwerden kann

I Attribute transformieren

I Dimensionsreduktion



1.3.5 Data Mining

Data Mining

I Verfahrensauswahl (z.B. Clusteranalyse)

I Konfiguration des Verfahrens



1.3.6 Evaluation und Interpretation

Evaluation und Interpretation

I Bewertung der ResultateI Anforderungen:

I GültigkeitI NeuartigkeitI NützlichkeitI Verständlichkeit

2 Data Mining – Grundlagen Wissensextraktion

26. Januar 2015

Inhaltsverzeichnis

Einführung


Anwendungsklassen



Datenvorbereitung

Bewertung


26. Januar 2015


Data Mining – GrundlagenBegriffeZwei BeispieleInterdisziplinaritätDatentypenAbstands- und ÄhnlichkeitsmaßeWeitere Grundbegriffe


Folie 2-1 (30)


If you file it, you’ll know where it is but you’ll never need it. If you don’tfile it, you’ll need it but never know where it is.

Tillis’s Organizational Principle


2.1 Begriffe Folie 2-2 (31)

Daten

Definition 2.1 (Daten)

Ansammlungen von Zeichen mit der dazugehörigen Syntax werdenDaten genannt.

Daten→ Plural des lateinischen Datum, ein Informationselement.

I unstrukturierte Daten (Bild, Text)

I semistrukturierte Daten (WWW-Seiten)

I strukturierte Daten (Datenbanken)



Information

Definition 2.2 (Information)

Werden Daten mit einer Bedeutung gekoppelt, handelt es sich umInformationen.

Information→ zweckbestimmte Interpretation von Daten durch denMenschen



Wissen

Definition 2.3 (Wissen)

Eine Information in Verbindung mit der Fähigkeit, diese zu benutzen,wird als Wissen bezeichnet.

Information, die man anzuwenden weiß→Wissen



Data Mining

Definition 2.4 (Data Mining)

Beim Data Mining (Datenschürfen) handelt es sich um die Extraktionvon Wissen aus Daten.

Data Mining ist die nichttriviale und automatische Suche nach Wissenin Massendaten. Man unterscheidet:

I Data Mining i.e.S. (strukturierte Daten)

I Web Mining (semistrukturierte Daten)

I Text Mining (unstrukturierte Daten)


2.2 Zwei Beispiele Folie 2-6 (35)

Beispiele

In Warenhäusern werden an den Kassen die verkauften Warenelektronisch erfasst. Diese Daten werden in Datenbanken abgelegt,wodurch riesige Datenbestände über Verkaufsumsätze zur Verfügungstehen.Mit Hilfe von Data-Mining-Verfahren können nun verschiedeneAnalysen auf diesen Daten durchgeführt werden:

I Welche Waren werden häufig gemeinsam mit anderen gekauft?

I Wann werden welche Waren in welchen Mengen gekauft?


2.2 Zwei Beispiele Folie 2-7 (36)

Beispiele

Benutzen dieser Informationen, um effizient bestimmte Aufgabenlösen zu können.

I Erkennen von Kundengruppen

I Zuschneiden von Werbeprospekten auf diese Kundengruppen

I gezieltes Versenden von Werbeprospekten an konkreteZielgruppen


2.3 Interdisziplinarität Folie 2-8 (37)

Interdisziplinarität

Es gibt eine ganze Reihe von Bezügen des Data Mining zu anderenDisziplinen. Data Mining ist höchst interdisziplinär.

I Datenbanken

I Data Warehouses

I Wissensbasierte Systeme

I Maschinelles Lernen

I Statistik

I Visualisierung


2.3 Interdisziplinarität Folie 2-9 (38)

Interdisziplinarität

Mining

Mathem

atik

Data

Intelligenz

Künstliche

Statistik

Datenbanken

Visualisierung

Computergraphik

Abb. 4: Interdisziplinarität


2.4 Datentypen Folie 2-10 (39)

Datentypen

Man unterscheidet folgende wichtige Datentypen:

nominal Nominale Daten unterliegen keinerlei Rangfolge. Siekönnen lediglich nach dem Kriterium gleich bzw. nichtgleich sortiert werden.

ordinal Ordinale Daten haben zumindest eine Ordnungsrelation(wie <).

metrisch Metrische Daten besitzen alle Ordnungsmerkmale derreellen Zahlen. Man kann mit ihnen rechnen.

Verfeinerungen möglich:

I Intervalle (Geburtsjahr)

I Verhältniszahlen (Gewicht, Größe)

Gute Beispiele in [Dorian Pyle, S. 67].



Datentypen

nominal ordinal metrischFarbe Schulnote FlächeBeruf Schuhgröße GeschwindigkeitFamilienstand Erdbebenstärke KörpergrößeStaatsangehörigkeit Altersgruppe Kinderzahl

Tabelle 1: Beispiel Datentypen



Umwandlung von ordinalen in metrische Daten

Betrachten ein Attribut mit den Ausprägungen klein, mittelgroß, groß,sehr groß .Umwandlung in metrisches Attribut:

I klein→ 0

I mittelgroß→ 0,3

I groß→ 0,7

I sehr groß→ 1

Achtung: Willkürliche Wahl der Zahlen beeinflusst den Abstandzwischen den Werten und eventuell das Resultat.


2.5 Abstands- und Ähnlichkeitsmaße Folie 2-13 (42)

Abstands- und Ähnlichkeitsmaße

I dist(v ,w): Abstand zweier Datensätze

I simil(v ,w): Ähnlichkeit zweier Datensätze

Zur Bestimmung der Ähnlichkeit wird meist der Abstandherangezogen:

simil(v ,w) = f (dist(v ,w))



Eigenschaften von Distanzfunktionen

Eine Abstandsfunktion (auch Distanzfunktion genannt) solltefolgende Eigenschaften erfüllen:

I dist(x ,x) = 0

I dist(x ,y) = dist(y ,x)

I dist(x ,y)≤ dist(x ,z)+dist(z,y)



Distanzfunktionen

Folgende typische Distanzfunktionen gibt es:

I Hamming-Distanz: distH(v ,w) = counti(vi 6= wi)

I Euklidische Distanz: distE(v ,w) =√

∑i(vi −wi)2

I Manhattandistanz: distS(v ,w) = ∑i(|vi −wi |)

I Maximumdistanz: distMax(v ,w) = maxi(|vi −wi |)

I . . .

Minkowski-Distanz: distMinkowski(v ,w) = p√

∑i|vi −wi |p



Distanzfunktionen

6 8 10

2

4

6

8

10

2 4

distH = 2, distE ≈ 8.9, distMan = 12, distMax = 8

Abb. 5: Beispiel Distanzen



Aufgaben

Aufgabe 2.1 (Distanz)

Wenn man die Schritte des Königs auf einem Schachbrett als Distanzwählt, welchem Distanzbegriff entspricht das? Und welchem Begriffentspricht die Anzahl der Felder, die der Turm passieren müsste?


Berechnen Sie die Distanz zwischen den Punkten (0,1,2), (1,5,3) und(4,-2,3). Verwenden Sie dabei alle 4 aufgeführten Distanzfunktionen.



Aufgaben


Suchen Sie weitere Abstandsmaße.

Aufgabe 2.4 (Datentypen)

Welchen Typ von Daten haben wir bei den Postleitzahlen: nominal,ordinal, metrisch?


2.6 Weitere Grundbegriffe Folie 2-19 (48)

Weitere Grundbegriffe

I Lernen aus gegebenen Beispielen: Instanzenmenge E .

I Lernen auf einer Teilmenge von E : Trainingsmenge T ⊂ E

I Validieren auf einer anderen Teilmenge von E (meist E \T ):Validierungsmenge


2.6 Weitere Grundbegriffe Folie 2-20 (49)

Lern-Strategien

I Nicht-überwachtes Lernen: Die zu entdeckenden Muster sindunbekannt.

I Überwachtes Lernen: Es werden Beispiele vorgegeben, z.B.Beispiele für Nadel- oder Laubbäume.

3 Anwendungsklassen Wissensextraktion

26. Januar 2015

Inhaltsverzeichnis

Einführung


Anwendungsklassen



Datenvorbereitung

Bewertung


26. Januar 2015


AnwendungsklassenKlassifikationClusteringNumerische VorhersageAssoziationsanalyseText MiningWeb Mining


Folie 3-1 (52)

Anwendungsklassen

All great discoveries are made by mistake.Young’s Law

I Klassifikation

I Clustering

I Numerische Vorhersage

I Assoziation

I Text Mining

I Web Mining


3.1 Klassifikation Folie 3-2 (53)

Klassifikation

Ziel der Klassifikation ist die Einteilung eines Gegenstandsbereichs(z.B. Kunden) in Klassen (normale / sehr gute Kreditwürdigkeit).



Klassifikation

Trainingsproben ⇒ Klassifikations-algorithmus

Name Alter Ein- Kredit-

kommen würd. ⇓Adam ≤ 30 niedrig normalBeate ≤ 30 niedrig sehr gut Klassifikations-Clemens 31. . . 40 hoch sehr gut regeln (z.B.)Diana > 40 mittel normal WENN Alter = 31. . . 40 UNDEgon > 40 mittel normal Einkommen = hoch DANNFrank 31. . . 40 hoch sehr gut Kreditwürdigkeit = sehr gut. . . . . . . . . . . .

Abb. 6: Klassifikation – Lernphase



Klassifikation

TestprobenName Alter Ein- Kredit- Bewertung

kommen würdigkeit durch RegelnGerda 31. . . 40 hoch sehr gut sehr gutHanno 31. . . 40 hoch normal sehr gutInge > 40 hoch sehr gut . . .. . . . . . . . . . . . . . .

Abb. 7: Klassifikation – Testphase



Klassifikation

Neue DatenName Alter Ein- Kredit- Bewertung

kommen würdigkeit durch RegelnJochen 31. . . 40 hoch ?? sehr gutKarl . . . . . . . . . . . .. . . . . . . . . . . . . . .

Abb. 8: Klassifikation – Anwendungsphase



Klassifikation

Beispiel 3.1 (Klassifikation)

I Vorhersage, ob ein bestimmter Kunde auf eine Werbeaktionreagieren wird

I Zeichenerkennung (Kfz-Kennzeichen, Adressen etc.)

I Vorhersage von Erdbebenwahrscheinlichkeiten

Einige Verfahren:I Induktion von EntscheidungsbäumenI Induktion von KlassifikationsregelnI Neuronale Feedforward NetzeI Bayes-Verfahren


3.2 Clustering Folie 3-7 (58)

Clustering

Ziel der Clusteranalyse ist es, eine gegebene InstanzenmengeE (E ⊆ X) in verschiedene Teilmengen (Cluster) zu zerlegen. DieIndividuen innerhalb eines Clusters sollen dabei möglichst ähnlichsein, wohingegen Individuen verschiedener Cluster möglichstunähnlich sein sollen.



Clustering

GegebenI X Instanzenraum

I E ⊆ X Instanzenmenge

I dist : X ×X →ℜ+ Abstandsfunktion

I quality : 22X →ℜ Qualitätsfunktion

GesuchtI Clustermenge C = {C1, . . . ,Ck}, wobei:

I Ci ⊆ EI quality(C)→maxI Ci ∩Cj =� (optional)I C1∪ . . .∪Ck = E (optional)



Clustering

Abb. 9: Schlechtes und gutes Clustering



Clustering

Beispiel 3.2 (Clustern)

I Finden homogener Kundengruppen zur gezieltenAngebotsgestaltung

I OCR: Finden von Buchstabengruppen, die ähnliche Bilder haben,um spezialisierte Klassifikatoren zu entwickeln

Einige Verfahren:I k-Means-AlgorithmusI Selbstorganisierende Neuronale Netze (z.B. Kohonen Map,

Growing Neural Gas)


3.3 Numerische Vorhersage Folie 3-11 (62)

Numerische Vorhersage

Gegeben:I X Menge möglicher Instanzenbeschreibungen

I Y Menge möglicher Zielwerte

I E Menge von Beispielen (x ,y) ∈ X ×Y , wobei y = f (x)

Gesucht:I Funktion y ′ = h(x), so dass error(h, f )→min.


3.3 Numerische Vorhersage Folie 3-12 (63)

Numerische Vorhersage

Beispiel 3.3 (Numerische Vorhersage)

I Vorhersage von Verkaufszahlen zur Lageroptimierung

I Vorhersage von Aktienkursen

I Zeitreihenanalyse

Einige Verfahren:I Lineare RegressionI RegressionsbäumeI Neuronale Netze (Feed forward)


3.4 Assoziationsanalyse Folie 3-13 (64)

Assoziationsanalyse

Assoziation beschäftigt sich mit der Erkennung und Quantifizierungvon Zusammenhängen und Abhängigkeiten von Attributen.

I unabhängig von der eigentlichen Klassifikation

I Suche nach Zusammenhängen zwischen den Attributen

Beispiel 3.4 (Assoziationsanalyse)

Ein Versandhaus erkennt:

I Wer A kauft, kauft häufig auch B.

Also: Anpassung des Angebotsverhaltens


3.4 Assoziationsanalyse Folie 3-14 (65)

Einordnung in das Data Mining

I Identifikation von Regelmäßigkeiten, Herausarbeiten von Regeln

I Vorhersage des „Verhaltens“ neuer DatensätzenI Anwendungsgebiete:

I Risikoabschätzung im Kreditwesen, VersicherungsbrancheI Spielanalyse gegnerischer FußballmannschaftenI . . .

Einige Verfahren:I A-Priori-VerfahrenI ART-Netze


3.5 Text Mining Folie 3-15 (66)

Text Mining

Text Mining beschäftigt sich mit der Analyse von Textdokumenten.Texte sind im Gegensatz zu Datenbanken und Web-Seitenunstrukturiert.


3.6 Web Mining Folie 3-16 (67)

Web Mining

Web Content Mining

Web Usage Mining



Web Mining

Web Mining

Web Content Mining Web Usage Mining

Web Log MiningIntegrated

Web Usage Mining

Abb. 10: Web Mining



Web Log Mining

I Internet bedeutende Plattform für die Abwicklung geschäftlicherProzesse

I Wichtig: Gute Web-Präsenz

I Web Log Mining: Analyse des Nutzer-Verhaltens, umRückschlüsse für Optimierung der Web-Präsenz zu ziehen.

4 Wissensrepräsentation Wissensextraktion

26. Januar 2015

Inhaltsverzeichnis

Einführung


Anwendungsklassen



Datenvorbereitung

Bewertung


26. Januar 2015


WissensrepräsentationEntscheidungstabellenEntscheidungsbäumeKlassifikationsregelnAssoziationsregelnInstanzenbasierte DarstellungCluster


Folie 4-1 (72)


Quality is inversely proportional to the time left for completion of theproject.

Wright’s first law of quality.

1. Entscheidungstabellen

2. Entscheidungsbäume

3. Klassifikationsregeln

4. Assoziationsregeln

5. Instanzenbasierte Darstellung

6. Cluster


4.1 Entscheidungstabellen Folie 4-2 (73)

Entscheidungstabellen

Eine Entscheidungstabelle ist die tabellarische Auflistung möglicherBedingungen (Eingaben) und des gewünschten Ergebnisses(Ausgabe), das jeder Bedingung entspricht.


4.1 Entscheidungstabellen Folie 4-3 (74)

EntscheidungstabellenBeispiel 4.1 (Entscheidungstabelle)

In Tabelle 2 ist eine Entscheidungstabelle für das Golfspiel gegeben.

outlook temperature humidity windy playsunny hot high false nosunny hot high true nosunny mild high false nosunny mild normal true yessunny cool normal false yesovercast hot high false yesovercast hot normal false yesovercast mild high true yesovercast cool normal true yesrainy mild high false yesrainy mild normal false yesrainy mild high true norainy cool normal false yesrainy cool normal true no

Tabelle 2: Entscheidungstabelle für Golf-Spiel


4.2 Entscheidungsbäume Folie 4-4 (75)

Entscheidungsbäume

Repräsentationsform, bei der die Ergebnisse einer Bedingungverzweigt dargestellt werden. Diese Verzweigungen können wiederumandere Verzweigungen generieren.

I graphisch aufbereitete Darstellung

I Entscheidungen einfach nachvollziehbar



EntscheidungsbäumeBeispiel 4.2 (Golfspiel)

In Abbildung 11 ist ein möglicher Entscheidungsbaum für dasGolf-Beispiel angegeben.

overcast

normalhigh

sunny rainy

false true

outlook

humidity

yesno yes no

yes windy

Abb. 11: Entscheidungsbaum Golf-Spiel



Entscheidungsbäume

Abb. 12: WEKA-Entscheidungsbaum Golf-Spiel


4.3 Klassifikationsregeln Folie 4-7 (78)

Klassifikationsregeln

Die Einteilung in Klassen wird mittels Regeln dargestellt.

I UND-verknüpfte Auswertung der Attribute

I ODER-Verknüpfung mehrerer Regeln

Beispiel 4.3 (Golfspiel)

IF outlook = sunny AND humidity = high THEN play = no

IF outlook = rainy AND windy = true THEN play = no

IF outlook = overcast THEN play = yes

IF humidity = normal THEN play = yes

IF none of the above THEN play = yes


4.4 Assoziationsregeln Folie 4-8 (79)

Assoziationsregeln

I Suche nach Zusammenhängen zwischen den Attributen

I unabhängig von der eigentlichen Klassifikation



Warenkorbanalyse

Warenkorbanalyse: In einem Supermarkt werden an der Kasse dieWarenkörbe aller Kunden erfasst.

I Wenn Waschpulver gekauft wird, wird i. allg. auch Weichspülergekauft:IF waschpulver THEN weichspüler

I Wenn Fisch gekauft wird, wird i. allg. kein Fleisch gekauft:IF fisch THEN ¬ fleisch

I Wenn Sekt gekauft wird, werden i. allg. auch Pralinen gekauft:IF sekt THEN pralinen



Golfspiel

Beispiel 4.4 (Golfspiel)

Man kann Assoziationsregeln auch folgendermaßen darstellen.

IF temperature = cool

THEN humidity = normal

IF humidity = normal AND windy = false

THEN play = yes

IF outlook = sunny AND play = no

THEN humidity = high

IF windy = false AND play = no

THEN outlook = sunny AND humidity = high



4.4.1 Einfache Assoziationsregeln

Einfache Assoziationsregeln

I Mengen von Items I

I Menge von Aktionen T

I Assoziationsregel: Implikation mit Angaben über die Häufigkeitihres Auftretens in T

I Prämisse A, Konsequenz B sind Konjunktionen von Elementenaus I (Itemsets), z.B.A = {I1, I2, I3} und B = {I7}

I A∩B ≡ /0I Form der Regel: A→ B




Einfache Assoziationsregeln

Die Regel{bier, chips}→ {tvzeitung}

ist also als abkürzende Schreibweise für die Regel

IF bier=yes AND . . . THEN . . .

zu verstehen.




Support und Konfidenz

Support: relative Häufigkeit eines Itemsets in der Menge der Aktionen

supp(A→ B) = P(A∪B)

Konfidenz: relative Häufigkeit einer Regel in der Menge der Aktionen

conf(A→ B) =supp(A→ B)

supp(A)




Support und Konfidenz

Beispiel 4.5 (Support und Konfidenz)

Wie hoch sind Support und Konfidenz der Regel

IF temperature = cool THEN humidity = normal

supp(temperature = cool → humidity = normal) = P(A∪B) =4

14

supp(temperature = cool) = P(A) =4

14

conf(A→ B) =supp(A→ B)

supp(A)=

414414

= 1

Die Regel ist also absolut sicher, sie hat einen Support von 27 .



4.4.2 Schwellwerte

Schwellwerte

I Bei großen Datenbanken: sehr viele Regeln (103,104, . . .)möglich,

I . . . auch seltene Regeln und Regeln mit geringer Konfidenz

Lösung:I Einführung von Schwellwerten: suppmin, confmin

I Festlegung durch Analysten

Nicht jede unsinnige Regel ist damit zu verhindern:{Person lebt}→ {Person atmet}



4.4.2 Schwellwerte

AssoziationsregelnBeispiel 4.6 (Assoziationsregeln)

In Abb. 13 sind die WEKA-apriori-Assoziationsregeln dargestellt.

Minimum support: 0.15 Minimum metric <confidence>: 0.9Best rules found:1. humidity=normal windy=FALSE 4 ==> play=yes 4 conf:12. temp=cool 4 ==> humidity=normal 4 conf:13. outlook=overcast 4 ==> play=yes 4 conf:14. temp=cool play=yes 3 ==> humidity=normal 3 conf:15. outlook=rainy windy=FALSE 3 ==> play=yes 3 conf:16. outlook=rainy play=yes 3 ==> windy=FALSE 3 conf:17. outlook=sunny humidity=high 3 ==> play=no 3 conf:18. outlook=sunny play=no 3 ==> humidity=high 3 conf:19. temp=cool windy=FALSE 2 ==> humidity=normal play=yes 2 conf:1

10. temp=cool humidity=normal windy=FALSE 2 ==> play=yes 2 conf:1

Abb. 13: Assoziationsregeln für Golf-Spiel



4.4.3 Arten von Assoziationsregeln

Arten von Assoziationsregeln

I hierarchische Assoziationsregeln (Taxonomien)

I temporale Assoziationsregeln (Sequenzanalyse)

I quantitative Assoziationsregeln

I unscharfe Assoziationsregeln

Wozu weitere Arten?I Verbessern der Aussagekraft von Regeln

I Genauere Vorhersagen (Zahlen, Ausprägungen)

I Anpassen an Problemgebiet




Hierarchische Assoziationsregeln

Idee:I Gruppierung von Items und Itemsets

I Generalisierung (vergleichbar Vererbung in OO)

Beispiel 4.7 (Hierarchische Assoziationsregeln)

Messer, Gabel → BesteckDoppelpass, Flanke → Angriff

Ergebnis:I Reduktion der Anzahl der Regeln

I Erhöhung der Support-Werte

I Algorithmus: Einfügen der Oberbegriffe als Items




Quantitative Assoziationsregeln

Idee:I Aufnahme konkreter Attributausprägungen (Zahlen,

Zeichenketten)

I Vorhersage von Einkommen, Kinderzahl, . . .

Vorgehen:

1. Einteilung des Wertebereichs in Intervalle (Klassifizierung).

2. Für jedes Intervall wird ein neuer Begriff geschaffen.

3. Die originalen Begriffe werden durch die neuen ersetzt.




Quantitative AssoziationsregelnBeispiel 4.8 (Quantitative Assoziationsregeln)

Alter Anzahl Kinder Einkommen23 0 200028 1 250034 0 450045 2 350065 5 4000

Neue Klassifizierung:

I Alter: [0,29], [30,49], [50,∞)

I Kinder: [0,1], [2,∞)

I Einkommen: [0,2999], [3000,∞)

(Alter ∈ [0,29],Einkommen ∈ [0,2999])→ (Kinder = 0/1)




Unscharfe Assoziationsregeln

Problem:I starre Intervallgrenzen der quantitativen Regeln

I Ausreißer, Messfehler (Physik, Messdaten)

Lösung:I sprachliche Begriffe statt fester Intervallgrenzen,

z.B.: jung, alt, früh, spät

I Zuordnung zu Gruppen nach Fuzzy-Logik-Methoden




Unscharfe Assoziationsregeln

Beispiel 4.9 (Unscharfe Assoziationsregeln)

Ein Call-Center plant, Daten der eingehenden Anrufe zu speichern,(u.a.):

I Zeitpunkt, an dem der Anruf angenommen wurde.

Ziel: Sortierung der Anrufe nachTageszeiten

I z.B.: Nacht, Morgen, Nachmittag und Abend.

I Das Intervall Nacht endet um 6 Uhr, ihm folgt das IntervallMorgen. Der Morgen endet um 12 Uhr und geht in denNachmittag über usw.

Überschneidungen durch Fuzzy-Modelle darstellbar.




Temporale Assoziationsregeln

Idee:I Erfassung zeitlich abhängiger Aktionen

I Beispiel: hoher Bierkonsum am Freitag→ hoher Konsum vonKopfschmerztabletten am Samstag

Umsetzung:I Temporale Datenbanken

I Regeln als Schnappschüsse aktueller Zusammenhänge

I Beobachtung der Veränderungen der Zusammenhänge

Anwendung: Logfile-Analyse


4.5 Instanzenbasierte Darstellung Folie 4-24 (95)

Instanzenbasierte Darstellung

Bei der instanzenbasierten Darstellung werden – ähnlich wie beimAuswendiglernen – einfach alle Individuen gespeichert, z.B. in einerrelationalen Datenbank.


4.6 Cluster Folie 4-25 (96)

Cluster

Wird eine Grundgesamtheit in Teilmengen zerlegt, deren Individuenzueinander ähnlicher als zu den Individuen der anderen Teilmengensind, bezeichnet man diese Teilmengen als Cluster.



Cluster

BedingungenI Individuen innerhalb eines Clusters zueinander ähnlich

I Individuen unterschiedlicher Clusters zueinander unähnlich

DarstellungI Instanzenbasiert

I Cluster-Zentrum (Codebook-Vector): Centroid oder Medoid

I über Wahrscheinlichkeitsverteilungen



Cluster

x Centroid

Medoid

Abb. 14: Centroid und Medoid



Cluster

k-Means======Number of iterations: 4Within cluster sum of squared errors: 26.0Cluster centroids:Cluster 0 Mean/Mode: sunny mild high FALSE yes

Std Devs: N/A N/A N/A N/A N/ACluster 1 Mean/Mode: overcast cool normal TRUE yes

Std Devs: N/A N/A N/A N/A N/AClustered Instances0 10 ( 71%) 1 4 ( 29%)

Abb. 15: Cluster für das Wetter-Beispiel

5 Methoden und Verfahren Wissensextraktion

26. Januar 2015

Inhaltsverzeichnis

Einführung


Anwendungsklassen



Datenvorbereitung

Bewertung


26. Januar 2015


Methoden und VerfahrenInstanzenbasiertes LernenEntscheidungsbaumlernenVerfahren zur AssoziationsanalyseLineare RegressionÜberwachte und selbstorganisierende unüberwachte neuronaleNetzeVerfahren zur ClusterbildungNaive Bayes


Folie 5-1 (102)


A carelessly planned project takes three times longer to complete thanexpected; a carefully planned project takes only twice as long.

Golub’s Second Law of Computerdom


Folie 5-2 (103)

Hinweis

Bei den studentischen Projekten (unter meiner Homepage) findet maneine Reihe von Verfahren erläutert. Benutzen Sie ebenso denILIAS-Modul Data Mining.


Folie 5-3 (104)

Verfahren – Übersicht

Klassifikation

Assoziation

Clustering

Numer.

Vorhersage

Text

Mining

Web

Mining

Instanzenbasiertes Lernen xk Nearest Neighbour x (x) (x)

Entscheidungsbaumlernen x (x)a priori x x x

Lineare Regression xÜberwachte Neuronale Netze x x x

Selbstorganisierende Neuronale Netze (x) xk-means x

Naive Bayes x x

Tabelle 3: Data-Mining-Verfahren und Anwendungsklassen


5.1 Instanzenbasiertes Lernen Folie 5-4 (105)

Instanzenbasiertes Lernen

I einfachstes Verfahren

I Speicherung aller bekannten Individuen

I Suche des ähnlichsten Individuums

I Dessen Klasse wird vorhergesagt.



5.1.1 k Nearest Neighbour

k Nearest Neighbour

x

y

Abb. 16: Beispiel k Nearest Neighbour



5.1.1 k Nearest Neighbour

k Nearest Neighbour

I instanzenbasiertes Verfahren

I Lernschritt: Beispielobjekte nur gespeichert

I Klassifikationsschritt: Unbekannte Objekte werden überÄhnlichkeit zu gespeicherten Beispielen klassifiziert.

I Komplexität des Verfahrens nur durch den Klassifikationsschritt



5.1.2 Der kNN-Algorithmus

Der kNN-Algorithmus

Der Lernschritt beim kNN-Lernen ist sehr einfach.

I Sei f (x) die zu erlernende Funktion.

I Für jedes Trainingsbeispiel (x , f (x)) speichere das Beispiel ineiner Liste Trainingsbeispiele.




kNN – Diskrete Funktion

I V := {v1,v2, ...,vm} eine endliche Menge (Zielattributwerte)

I zu erlernende Funktion: f : ℜn→ V

I zu klassifizierendes Beispiel: y

Für alle xi in der Menge Trainingsbeispiele berechne die Ähnlichkeit zuy . Wähle diejenigen k Beispiele x1,x2, . . . ,xk aus, die zu y amähnlichsten sind.

klasse(y) := maxv∈V

k

∑p=1

δ(v , f (xp)) mit δ(a,b) :={

1, falls a=b0, sonst




kNN

Beispiel 5.1 (kNN)

Nr Alter verheiratet Eigenheim Akademiker Einkommen1 alt ja ja ja hoch2 alt ja nein nein gering3 mittel nein nein nein gering4 mittel ja ja ja hoch5 jung nein nein nein gering6 jung ja nein nein mittel7 jung ja ja ja mittel8 alt nein ja nein hoch

Einkommen für jung/verheiratet/ohne Eigenheim/Akademiker. k=2.




kNN

Beispiel 5.1 cont.

Nr Alter verheiratet Eigenheim Akademiker Abstandneu jung ja nein ja1 alt ja ja ja 22 alt ja nein nein 23 mittel nein nein nein 34 mittel ja ja ja 25 jung nein nein nein 26 jung ja nein nein 17 jung ja ja ja 18 alt nein ja nein 4

Datensätze 6 und 7: Gehaltsgruppe mittel.




kNN – Reellwertige Funktion

I analog diskreter Fall

I Zurückgegeben wird der Mittelwert


f’(y) :=

k∑

p=1f (xp)

k



5.1.3 Ein verfeinerter Algorithmus

kNN – Ein verfeinerter Algorithmus

I Schwäche von kNN: alle k Beispiele sind gleichgewichtet

I geringer (euklidischer) Abstand = hohe Ähnlichkeit

I also: Gewichte einführen

I Shepard’s method




Diskrete Funktionen

I als Gewicht: das Inverse des Quadrats der Distanz

Sei wieder V := {v1,v2, ...,vm} die Menge aller Werte, die dasZielattribut annehmen kann. Für alle xi in der MengeTrainingsbeispiele berechne die Ähnlichkeit zu y . Wähle diejenigen kBeispiele x1,x2, . . . ,xk aus, die zu y am ähnlichsten sind.

klasse(y) :=

f (xi) falls y = xi für ein i

maxv∈V

k∑

p=1wp×δ(v , f (xp)) sonst

mit δ(a,b) :={

1, falls a=b0, sonst

und wp :=1

dist(y ,xp)2 .




Reellwertige Funktionen


f’(y) :=

f (xi) falls y = xi für ein ik∑

p=1wp×f (xp)

k∑

p=1wp

sonst

mit wp :=1

dist(y ,xp)2 .



5.1.4 Anmerkungen

Anmerkungen

I Für k � 1 arbeitet der kNN-Algorithmus i. allg. auch beiverrauschten Trainingsdaten sehr gut.

I Im Gegensatz beispielsweise zum Entscheidungsbaum werdenalle Attribute in die Berechnung einbezogen.

I Die Auswahl der Trainingsdaten verdient einige Beachtung. So istz.B. von Bedeutung, dass die Trainingsvektoren denLösungsraum möglichst gleichmäßig aufspannen.



5.1.4 Anmerkungen

Aufgabe 5.1 (kNN)

Klassifizieren Sie folgende Datensätze mittels kNN.Alt. Fr/Sa Hung. Gäste Reserv. Typ Zeit Wartenja nein ja einige nein Franz. 30-60ja ja ja voll ja Chin. 10-30

nein nein nein keine nein Burger 0-10

I Alternative: Gibt es ein geeignetes anderes Restaurant? (ja/nein)I Fr/Sa: Ist Freitag oder Samstag? (ja/nein)I Hungrig: Bin ich hungrig? (ja/nein)I Gäste: Wieviele Leute sind im Restaurant? (keine/einige/voll)I Reservierung: Habe ich reserviert? (ja/nein)I Typ: Um welche Art von Restaurant handelt es sich?I Wartezeit: Welche Wartezeit wird vom Restaurant geschätzt?I Warten (Zielattribut): Warte ich, wenn alle Tische besetzt sind?



5.1.4 Anmerkungen

Aufgabe 5.1 cont.

Alt. Fr/Sa Hung. Gäste Reserv. Typ Zeit Wartenja nein ja einige ja Franz. 0-10 jaja nein ja voll nein Chin. 30-60 nein

nein nein nein einige nein Burger 0-10 jaja ja ja voll nein Chin. 10-30 jaja ja nein voll ja Franz. >60 nein

nein nein ja einige ja Ital. 0-10 janein nein nein keine nein Burger 0-10 neinnein nein ja einige ja Chin. 0-10 janein ja nein voll nein Burger >60 neinja ja ja voll ja Ital. 10-30 nein

nein nein nein keine nein Chin. 0-10 neinja ja ja voll nein Burger 30-60 ja

Tabelle 4: Restaurant-Beispiel


5.2 Entscheidungsbaumlernen Folie 5-18 (119)

5.2.1 Erzeugen eines Entscheidungsbaums

Entscheidungsbaumlernen – Algorithmus

I Gegeben: Beispielmenge E und Attributmenge A

Auswählen eines Attributs a ∈ AErzeugen der mit a markierten BaumwurzelFür jede Ausprägung ω ∈ ωa (ωa = Ausprägungsmenge von a)

1. Erzeugen einer mit ω markierten Kante

2. Generieren der Beispiel-Menge Eω ⊂ E : ∀e ∈ Eω : ωa(e) = ω3. I Wenn Eω = /0: Beenden der Kante mit NIL

I Sonst:Wenn alle Beispiele e ∈ Eω in derselben Klasse k sind: Kante mitBlatt k abschließen Sonst:

3.1 Erzeugen eines Entscheidungsbaums aus AttributmengeA′ = A\{a} und Beispielmenge Eω

3.2 Einhängen dieses Baums am Kantenende




Entscheidungsbaumlernen – Golfspiel

Tag outlook temperature humidity windy play1 sunny hot high false no2 sunny hot high true no3 overcast hot high false yes4 rainy mild high false yes5 rainy cool normal false yes6 rainy cool normal true no7 overcast cool normal true yes8 sunny mild high false no9 sunny cool normal false yes10 rainy mild normal false yes11 sunny mild normal true yes12 overcast mild high true yes13 overcast hot normal false yes14 rainy mild high true no

Tabelle 5: Daten Golfspiel




Entscheidungsbaumlernen – Golfspiel

outlook

sunny overcast rainy

windy

normal

humidity

high false true

Wurzelattribut (a)

Ausprägungen

von outlook

1,2,8,9,11

3,7,12,13

yes

yesno yes no

4,5,6,10,14

E = alle Daten

sunny= DatensätzeE

rainy= DatensätzeE

Abb. 17: Entscheidungsbaum Golf-Spiel



5.2.2 Auswahl eines Attributs

Auswahl eines Attributs

manuell (durch Benutzer)

zufällig

berechnet



5.2.2 Auswahl eines Attributs

Automatische Attributwahl

Beispiel 5.2 (Automatische Attributwahl)

I Attribut mit lokal bester Klassifikationsleistung

I probeweise Teilung an allen Attributen

I Vorhersage der Mehrheitsklasse

I Auswahl des Attributs mit der geringsten Fehlerrate errora

error(ωa) =falschalle

errora = ∑i(|Aωai ||A| ∗error(ωai)) → min.



5.2.3 Metrische Attribute

Metrische Attribute

Für jede Ausprägung (d.h. jede vorkommende Zahl) eine eigeneKante ? → Unsinnig !!Lösung:

Gruppierung Zusammenfassung zu Intervallen

Schwellwerte nur 2 Kanten (kleiner / größer Schwellwert)



5.2.4 Der ID3-Algorithmus zur Erzeugung eines Entscheidungsbaums

ID3-Algorithmus zur Entscheidungsbaumgenerierung

Nr. Zielattr. frühere Kredit- Verschul- Sicher- Ein-Risiko würdigkeit dung heiten kommen

1 hoch schlecht hoch keine 0 bis 152 hoch unbekannt hoch keine 15 bis 353 mittel unbekannt niedrig keine 15 bis 354 hoch unbekannt niedrig keine 0 bis 155 niedrig unbekannt niedrig keine über 356 niedrig unbekannt niedrig angemessen über 357 hoch schlecht niedrig keine 0 bis 158 mittel schlecht niedrig angemessen über 359 niedrig gut niedrig keine über 3510 niedrig gut hoch angemessen über 3511 hoch gut hoch keine 0 bis 1512 mittel gut hoch keine 15 bis 3513 niedrig gut hoch keine über 3514 hoch schlecht hoch keine 15 bis 35

Tabelle 6: Kreditrisiko





Abb. 18: Entscheidungsbaum





Abb. 19: Entscheidungsbaum 2





Welcher Baum ist für die Klassifikation der unbekannten Datensätzeoptimal? Der ID3-Algorithmus unterstellt, dass dies der einfachsteBaum ist.





FUNCTION induce_tree(Beispielmenge Ex, Attribute Attr)IF alle Eintraege aus Ex gehoeren zur gleichen Klasse

THEN RETURN Blattknoten mit Beschriftung dieser KlasseELSE

Waehle ein Attribut A aus Attr;Setze A als Wurzel fuer den aktuellen Baum;Loesche A aus Attr;FOREACH Wert AV von AErstelle Kante im Baum mit Kantenbeschriftung AV;Seien Ex_AV alle Elemente von Beispielmenge Ex,

die als Wert fuer A gerade AV haben;Ergebnis der Kante AV := induce_tree(Ex_AV,Attr);

END FOREACH;END IF;

END.

Abb. 20: Algorithmus Entscheidungsbaum




Auswahl eines geeigneten Attributs ?

I Grundlage: Informationstheorie

I Wahl des Attributs, das den größten Informationsgewinn liefert.

Der Informationsgehalt eines Attributs B wird gemessen als:

I(B) =k

∑i=1−p(bi)× log2(p(bi))

I Dabei stellen die bi die möglichen Werte des Attributs B dar.

I p ist die Wahrscheinlichkeit (besser: relative Häufigkeit) für dasEintreffen von bi .




Informationsgehalt der Kredit-Tabelle

I p(Risiko hoch) = 614

I p(Risiko mittel) = 314

I p(Risiko niedrig) = 514

Folglich ist I(Risiko) =

I(Tabelle)=− 614× log2(

614

)− 314× log2(

314

)− 514× log2(

514

)= 1,531




ID 3 und maximaler InformationsgewinnMan wählt das Attribut mit dem maximalen Informationsgewinn.

unbekannt schlecht gut

I(Tabelle) Alle Datensätze

Kreditwürdigkeit ?

Teiltabelle 2Teiltabelle 1 Teiltabelle 3

Kreditwürdigkeit = gut

Kreditwürdigkeit = schlechtKreditwürdigkeit = unbekannt

G(Kreditwürdigkeit)

Abb. 21: Informationsgewinn

Informationsgewinn = I(Tabelle)−G(Kreditwürdigkeit)




ID 3 und Informationsgewinn

I Beispielmenge E (die komplette DB) gegeben.

I Wählt man ein Attribut B mit n Ausprägungen aus, so wird E in nTeilmengen (Teildatenbanken) zerlegt: {E1, . . . ,En}.

I Mit B als Wurzel des Baums ist die zur Fertigstellung des Baumsvoraussichtlich erforderliche Informationsmenge:

G(B) =n

∑j=1

|Ej ||E | I(Ej)

G (gain) ist die gewichtete Summe der Einzelinformationen.Der Gewinn an Information wird dann berechnet als:

gewinn(B) = I(E)−G(B)

Es gilt, gewinn zu maximieren. Dazu geht man alle Attribute durchund wählt jenes aus, das den maximalen Gewinn liefert.




ID 3 und InformationsgewinnI Wählen zunächst Kreditwürdigkeit als Attribut.

I Kreditwürdigkeit hat 3 Ausprägungen: unbekannt, schlecht, gut.I Für jeden Wert zählen wir, wie oft welches Risiko vorkommt:

Wert hohes Risiko mittleres Risiko niedriges Risikounbekannt 2 1 2schlecht 3 1 0

gut 1 1 3

I(Kreditw_unbek) =−25 × log2(

25)− 1

5 × log2(15)− 2

5 × log2(25) = 1,52

I(Kreditw_schlecht) =−34 × log2(

34)− 1

4 × log2(14) = 0,81

I(Kreditw_gut) =−15 × log2(

15)− 1

5 × log2(15)− 3

5 × log2(35) = 1,37

G(Kreditwürdigkeit) =n∑

j=1

|Ej ||E | I(Ej) =

514 ×1,52+ 4

14 ×0,81+ 514 ×1,37 = 1,265




ID 3 und Gain-Berechnung

(14)

hoch = 1xmittel = 1xniedrig = 3x

hoch = 6x

mittel = 3x

niedrig = 5x

hoch = 2xmittel = 1xniedrig = 2x niedrig = 0x

mittel = 1xhoch = 3x

unbekannt

5x

schlecht

4x

gut 5x

I(Tabelle) = 1,531 Gesamte Tabelle

Kreditwürdigkeit ?

Teiltabelle 2Teiltabelle 1 Teiltabelle 3

... = gut... = schlechtKreditwürdigkeit = unbekannt

1,52

I =

0,81

I = I =

1,37

G(Kreditwürdigkeit) = 5/14 * 1,52 + 4/14 * 0,81 + 5/14 * 1,37

Abb. 22: Gain-Berechnung




ID 3 – Beispiel

I gewinn(kreditwuerdigkeit) = 1,531−1,265 = 0,266

I gewinn(einkommen) = 1,531−0,564 = 0,967

I gewinn(verschuldung) = 1,531−1,468 = 0,063

I gewinn(sicherheiten) = 1,531−1,325 = 0,206

Man wählt nun einkommen als obersten Knoten, da der Gewinn dortam größten ist, und setzt das Verfahren für jeden Teilbaum rekursivfort.




Fortsetzung für Zweig einkommen=15-35

I nur noch die Datensätze, wo einkommen=15-35 gilt

I Spalte für Einkommen eigentlich nun unnötig

Nr. Zielattr. frühere Kredit- Verschul- Sicher- Ein-Risiko würdigkeit dung heiten kommen

2 hoch unbekannt hoch keine 15 bis 353 mittel unbekannt niedrig keine 15 bis 3512 mittel gut hoch keine 15 bis 3514 hoch schlecht hoch keine 15 bis 35

Tabelle 7: Kreditrisiko




Informationsgehalt der reduzierten Kredit-Tabelle

I p(Risiko hoch) = 24

I p(Risiko mittel) = 24

I p(Risiko niedrig) = 04

Folglich ist I(Risiko) =

I(Tabelle2) =−24× log2(

24)− 2

4× log2(

24)− 0

4× log2(

04) = 1




Attribut mit maximalem Informationsgewinn

Nun wählt man wieder das Attribut aus, das den maximalenInformationsgewinn erzielt.

I gewinn(kreditwuerdigkeit) = 1−0,5 = 0,5

I gewinn(verschuldung) = 1−0,6887 = 0,3113

I gewinn(sicherheiten) = 1−1 = 0

Man wählt folglich kreditwuerdigkeit als nächsten Knoten, da derGewinn dort am größten ist.




Der Gini-Index

Der Gini-Index ist das Äquivalent zum Informationsgehalt einerTabelle bezüglich eines Zielattributs B:

gini(B) = 1−k

∑i=1

p(bi)2

I Dabei stellen die bi die möglichen Werte des Attributs B dar.

I p ist die Wahrscheinlichkeit (besser: relative Häufigkeit) für dasEintreffen von bi .

Analog zum Gain definiert man dann

GINI(B) =n

∑j=1

|Ej ||E | gini(Ej)



5.2.5 C4.5-Algorithmus

C4.5-Algorithmus

I Wesentlicher Nachteil des ID3-Algorithmus: kann nicht mitnumerischen Attributen umgehen

I C4.5 (Nachfolger von ID3) kann dies.

I Numerische Attribute in Intervalle unterteilt→ ordinale Attribute

I Betrachten Attribut A mit n Ausprägungen A1, . . . ,An

I Für jedes i: Bilden Intervalle [a|a≤ Ai ] und [a|a > Ai ]

I 2 Intervalle: neue (ordinale) Ausprägungen des Attributs A

I Wählen die Intervallbildung, die den größten Gewinn liefert.




ISplit

Bemerkung 5.1 (ISplit)

Der ID3-Algorithmus hat einen weiteren Nachteil: Die Sortierung derAttribute favorisiert Attribute mit vielen verschiedenen Ausprägungen.Deshalb normalisiert C4.5 den Informationsgewinn. Sei:

ISplit(B) =−n

∑j=1

|Ej ||E | × log2(

|Ej ||E | )

Der Gewinn an Information wird dann normalisiert:

gewinn’(B) =gewinn(B)ISplit(B)




ISplit

Beispiel 5.3 (ISplit)

Betrachten Ausschnitt aus einer Kino-Besuch-Datenbank.

Preis 8 5 5 9 8 8 4 5 8 8 9 8Kino besucht j n j j n j j n n j j n

Variante 1:

I 4/5⇒ billig: 4Ausprägungen

I 8/9⇒ teuer: 8Ausprägungen

Variante 2:

I 4⇒ billig: 1 Ausprägung

I 5⇒ moderat: 3 Ausprägungen

I 8⇒ teuer: 6 Ausprägungen

I 9⇒ sehr teuer: 2 Ausprägungen




ISplit

Beispiel 5.3 cont.

Gain:

I Variante 1: 0,97

I Variante 2: 0,73

Damit wird der Gewinn bei Variante 2 größer sein.Typischer Effekt: Attribute mit vielen Ausprägungen bevorzugt.Deshalb: Dividieren Informationsgewinn durch den ISplit:

I ISplit Variante 1: 0,92

I ISplit Variante 2: 1,73

Größerer ISplit reduziert den Gewinn für Variante 2 stärker.



5.2.6 Probleme

Probleme

I I. allg. großes Problem: Entscheidungsbaum kann ALLETrainingsdaten korrekt klassifizieren,

I . . . aber auf den Testdaten nicht gut funktionieren.

I Entscheidungsbaum hat Trainingsdaten auswendig gelernt.

I Effekt wird Overfitting genannt.I Verkürzen der Bäume nötig:

I Keine weiteren Unterbäume, wenn eine bestimmte Anzahl vonTrainingsdaten unterschritten wird.

I Ersetzen bereits generierter Unterbäume durch ein Blatt.



5.2.6 Probleme

ACHTUNG !!

Entscheidungsbaum wird Trainingsdaten häufig nicht zu 100% korrektvorhersagen, durch:

I das Reduzieren der Tiefe des Baums (s.o.) oder

I widersprüchliche Daten.



5.2.7 Ergänzungen

Ergänzungen

I ID3 – Top down induction of decision trees (TDIDT).

I Es wird univariater Baum erzeugt. (An jedem Knoten wird exaktein Attribut abgefragt.)

I Es gibt auch Verfahren, die multivariate Entscheidungsbäumegenerieren.

I Jetzt können in einem Knoten mehrere Attribute benutzt werden.I Z.B. als Linearkombination von Attributen: Gewicht + 2 * Größe <

70.I Schnitte im Merkmalsraum linear, aber nicht mehr achsenparallel.I Auch nichtlineare Ausdrücke abfragbar: Gewicht / (Größe*Größe)

< 25.I Nun sind die Schnitte im Merkmalsraum beliebig kurvig.

I Vorteil: meist genauer und kleiner.

I Nachteil: schwieriger zu bauen und auch schwerer lesbar



5.2.8 Aufgaben

Aufgaben

Aufgabe 5.2 (Golfspiel)

Bestimmen Sie aus den folgenden Daten einen Entscheidungsbaumfür das Attribut ‘Play?’, welches angibt, ob unter den gegebenenWitterungsbedingungen Golf gespielt wird. Wählen Sie bei gleicherGüte zweier Attribute das in der Tabelle weiter links stehende. Wiegehen Sie mit den numerischen Werten um?



5.2.8 Aufgaben

GolfbeispielAufgabe 5.2 cont.

Outlook Temp (◦F) Humidity (%) Windy? Play?sunny 85 85 false nosunny 80 90 true no

overcast 83 78 false yesrain 70 96 false yesrain 68 80 false yesrain 65 70 true no

overcast 64 65 true yessunny 72 95 false nosunny 69 70 false yesrain 75 80 false yes

sunny 75 70 true yesovercast 72 90 true yesovercast 81 75 false yes

rain 71 80 true no

Tabelle 8: Daten Golfspiel



5.2.8 Aufgaben

RestaurantbeispielAufgabe 5.3 (Restaurant)

Tabelle mit diesen Attributen:

I Alternative: Gibt es in der Nähe ein anderes Restaurant? (ja/nein)

I Fr/Sa: Ist Freitag oder Samstag? (ja/nein)

I Hungrig: Bin ich hungrig? (ja/nein)

I Gäste: Wieviele Leute sind im Restaurant? (keine/einige/voll)

I Reservierung: Habe ich reserviert? (ja/nein)

I Typ: Um welche Art von Restaurant handelt es sich?(Franz./Chin./Ital./Burger)

I Wartezeit: Welche voraussichtliche Wartezeit wird vomRestaurant geschätzt? (0-10/10-30/30-60/>60)

I Warten (Zielattribut): Warte ich, wenn alle Tische besetzt sind?(ja/nein)



5.2.8 Aufgaben

Restaurantbeispiel

Aufgabe 5.3 cont.

Generieren Sie einen Entscheidungsbaum und klassifizieren Sienachfolgende Datensätze.

Alt. Fr/Sa Hung. Gäste Reserv. Typ Zeit Wartenja nein ja einige nein Franz. 30-60ja ja ja voll ja Chin. 10-30




5.2.8 Aufgaben

RestaurantbeispielAufgabe 5.3 cont.





Tabelle 9: Daten Restaurantbeispiel


5.3 Verfahren zur Assoziationsanalyse Folie 5-52 (153)

Verfahren zur Assoziationsanalyse

Wir wenden uns nun der Aufgabe zu, Assoziationsregeln zu finden.Der Standard-Algorithmus ist der A-Priori-Algorithmus.



5.3.1 Der A-Priori-Algorithmus

Der A-Priori-Algorithmus

Der A-Priori-AlgorithmusI gehört zu den wichtigsten iterativen Verfahren

I Grundlage AIS-Algorithmus 1993

Ziel:I Finden von Frequent Itemsets

I Itemsets, deren Support über suppmin




Vorgehensweise

Der A-Priori-Algorithmus wird in zwei Schritten vollzogen:

1. Finden von Frequent Itemsets (Kandidaten) mit ausreichendemSupport

2. Erzeugen von Assoziationsregeln aus allen Frequent Itemsets




Generierung der Kandidaten

Diese Phase läuft in zwei Teilschritten ab:

I Join-Phase

I Pruning-Phase




Join- und Pruning-Phase

Join-Phase:I Erzeugen von Frequent Itemsets der Länge k mit k > 2

I paarweises Verbinden aller (k−1)-langen Sets, die sich in einemElement unterscheiden

I Ergebnis: k -elementige Menge, in der zwei Teilmengen FrequentItemsets sind

Pruning-Phase:I Zerlegen der Frequent Itemsets in Teilmengen

I Test, ob alle diese Teilmengen Frequent Itemsets sind(Monotonieeigenschaft)

I Algorithmus endet, wenn keine Frequent Itemsets mehr gefundenwerden




A Priori – Beispiel

Beispiel 5.4 (A priori)

Betrachten Kinobesuche. Wer geht gern mit wem ?

Kinobesuch-ID Kinobesucherk1 Anne, Claudia, Ernstk2 Anne, Ernst, Gudrunk3 Anne, Claudia, Ernst, Franz, Gudrunk4 Anne, Claudia, Horstk5 Bernd, Claudia, Ernst, Franz, Gudrunk6 Bernd, Claudia, Ernst, Gudrun, Horst





Beispiel 5.4 cont.

Wir fordern als minimalen Support: 50%.

Anne 4 66%Bernd 2 33%Claudia 5 83%

Ernst 5 83%Franz 2 33%Gudrun 4 66%Horst 2 33%

Bernd, Franz und Horst erfüllen nicht den minimalen Support.





Beispiel 5.4 cont.

Nun bilden wir 2er FIS:

Anne, Claudia 50% (1)Anne, Ernst 50% (2)Anne, Gudrun 33% (3)Claudia, Ernst 66% (4)Claudia, Gudrun 50% (5)Ernst, Gudrun 66% (6)

Einer dieser 6 Kandidaten erfüllt den Support nicht.





Beispiel 5.4 cont.

3er Kandidaten:

1+4 Anne, Claudia, Ernst ?%1+5 Anne, Claudia, Gudrun ?%2+6 Anne, Ernst, Gudrun ?%4+5 Claudia, Ernst, Gudrun ?%

Die beiden mittleren Kandidaten können KEINE FIS sein, daAnne/Gudrun kein 2er FIS ist (Monotonie).Unser Kandidat ACE erfüllt den Support nicht, CEG erfüllt mit 50%den geforderten Support.Vierer-Kandidaten kann es nicht geben, da wir nur ein 3er FIS haben.




A Priori – Erzeugen der Regeln

I Finden von Regeln der Form A→ (X \A) mit A⊂ X und A 6= /0I Beispiel: X = {a,b,c,d}, (a,b)→ (c,d)

I Regel muss minimaler Konfidenz entsprechen.




A Priori – Vor-/Nachteile

Vorteil Es handelt sich um Mengenoperationen, also: einfacheOperationen.

Nachteil bei großen Datenmengen schlechtes Laufzeitverhalten




A Priori


Betrachten einzigen 3er Kandidaten: {Claudia, Ernst, Gudrun}.Berechnen Konfidenz nur für eine Regelvariante:

Claudia, Ernst→ Gudrun

conf(A→ B) = P(B|A) = supp(A∪B)supp(A)

Also:

conf(Claudia, Ernst→ Gudrun) =5066

= 0,75




A Priori


Seien folgende Frequent Itemsets der Länge 3 bereits berechnet:

{a,b,c},{a,b,d},{a,c,d},{a,c,e},{b,c,d}

Daraus lassen sich folgende 4er-Kandidaten erzeugen (Join):

{a,b,c,d} (1+2) {a,c,d ,e} (3+4) {a,b,c,e} (1+4)

Pruning: {a,c,d ,e} und {a,b,c,e} fallen weg,denn {c,d ,e} bzw. {b,c,e} sind keine 3-Frequent-Itemsets.



5.3.2 Modifikationen des A-Priori-Algorithmus

Modifikationen des A-Priori-Algorithmus

Hierarchische Assoziationsregeln

I neue Begriffe einfach als Items aufnehmen

I Support eines Oberbegriffs = Support des Itemsets seinerKomponenten

Quantitative Assoziationsregeln→ Intervalle als Items.




Erzeugung von temporalen Assoziationsregeln

5 Phasen:

1. Sortierphase: Kundensequenzen

2. Generierungsphase: Hier werden die häufigen Itemmengengesucht.

3. Transformationsphase: Die Sequenzen werden durch die in ihnenenthaltenen häufigen Itemmengen ersetzt.

4. Sequenzphase: Mit Hilfe der häufigen Itemmengen werden diegewünschten Sequenzen ermittelt. Der Ablauf ist wie beimapriori-Algorithmus.

5. Maximalphase: Aus der Menge der generierten Itemmengenwerden die maximalen Sequenzen ermittelt.




Aufgaben

Aufgabe 5.4 (Frequent Itemsets)Seien diese Einkäufe gegeben:

ID gekaufte Artikelt1 Brot, Saft, Cola, Biert2 Saft, Cola, Weint3 Brot, Saft, Wassert4 Cola, Bier, Saftt5 Brot, Saft, Cola, Bier, Weint6 Wasser

Ergänzen Sie zunächst für diegegebenen Assoziationsregelnfolgende Tabelle:

Regel Support KonfidenzSaft→ ColaCola→ SaftCola→ BierBier→ Cola

Finden Sie dann alle Frequent Itemsets mit einem minimalen Supportvon 0,4.


5.4 Lineare Regression Folie 5-68 (169)

Lineare Regression

Eine Regressionsfunktion beschreibt den Trend bzw. dendurchschnittlichen Zusammenhang zwischen metrischen Attributen.

error = ∑(yi − yi)2→min



Lineare Regression

Gegeben:I Attributraum X , Zielwertraum Y

I Beispielmenge E = X ×Y

Gesucht:I Zusammenhang y = f (a,x), wobei a = [a0, . . . ,an−1] =

Parametersatz der Funktion im n-dimensionalen Raum

Lösungsansatz:I error = ∑(yi − yi)

2→min.



Lineare Regression

Abb. 23: Beispiel Regression



Aufgaben

Aufgabe 5.5 (Ausfuhränderung)

Berechnen Sie aus den nachfolgend gegebenen Daten diedurchschnittliche jährliche Änderung der Ausfuhr der BRD für diePeriode 1980/81. Folgende Entwicklung der Ausfuhr der BRD (jeweilsgegenüber dem Vorjahr) wurde beobachtet:

Periode 19.. 73/74 74/75 75/76 76/77 77/78 78/79 79/80Ausfuhränderung +29 % -4 % +16 % +7 % +4 % +10 % +11 %


5.5 Überwachte und selbstorganisierende unüberwachte neuronale Netze Folie 5-72 (173)

Überwachte und unüberwachte neuronale Netze

Neuronale Netze werden im Data Mining sehr häufig eingesetzt. Fürtiefergehende Informationen sei hier auf die Vorlesungsreihe„Neuronale Netze“ sowie die einschlägige Literatur verwiesen.


5.6 Verfahren zur Clusterbildung Folie 5-73 (174)

Verfahren zur Clusterbildung

Wir befassen uns nun mit Verfahren, die Objekte zu geeignetenMengen (Clustern) zusammenfassen.



5.6.1 Partitionierendes Clustering

Partitionierendes Clustering

I Beliebige Anfangspartitionierung→ k ClusterI Darstellung durch z.B. Medoid bzw. CentroidI Iterative Neuzuordnung der Objekte zu Clustern

I Neuberechnung des CentroidsI Neuzordnung jedes Objekts zum nächstgelegenem Centroid

I Ende, falls kein Objekt einem anderen Cluster zugeordnet wird

Partitionierende Clusterverfahren teilen die Eingabedaten indisjunkte Cluster ein, so dass gilt:

I Jeder Cluster besteht aus mindestens einem Objekt.

I Jedes Objekt ist höchstens in einem Cluster enthalten.




Algorithmus

1. Erzeuge (zufällig) k Anfangscluster Ci . Alle Objekte x aus denEingabedaten werden (zufällig) einem der Cluster zugeordnet.

2. Bestimme die Mittelpunkte x1, x2, . . . , xk der Cluster.

3. Für alle x aus den Eingabedaten: Weise x demjenigen Cluster Ci

zu, von dessen Mittelpunkt xi es am wenigsten entfernt ist.

4. Gehe zu 2, falls mindestens ein x einem anderen Clusterzugewiesen wurde.




k-Means

Initiale Cluster Centroide berechnen

X

X

X

neue CentroideNeuordnung und

X

X

X

x

x

x

neue CentroideNeuordnung und

X

X

X

Neuordnung undneue Centroide

X

X

X

Abb. 24: Clustering mit k-Means




k-Means

Vorteile von k-MeansI Anzahl der Iterationen vergleichsweise klein.I Einfache Implementierung, deswegen ist es ein

populäres Clusteringverfahren.

Nachteile von k-MeansI Anfällig bzgl. Rauschen und Ausreißern, da alle

Objekte in die Berechnung des Centroideneingehen.

I Gute initiale Cluster sind oft schwer zu bestimmen.I Ergebnis und Laufzeit sind abhängig von der

initialen Zerlegung.




k-Means – Beispiel

0 1 2 3 4 5 6 7 8 90

1

2

3

4

5

6

7

8

9

Daten

Abb. 25: k-Means – Ausgangssituation

Ziel: 3 Cluster. Startcluster (1, 5), (2, 6), (3, 6). Euklidische Distanz.





0 1 2 3 4 5 6 7 8 90

1

2

3

4

5

6

7

8

9

NEUDatenALT

0 1 2 3 4 5 6 7 8 90

1

2

3

4

5

6

7

8

9

NEUDatenALT

Abb. 26: k-Means – 1./2. Schritt





0 1 2 3 4 5 6 7 8 90

1

2

3

4

5

6

7

8

9

NEUDatenALT

0 1 2 3 4 5 6 7 8 90

1

2

3

4

5

6

7

8

9

NEUDatenALT






0 1 2 3 4 5 6 7 8 90

1

2

3

4

5

6

7

8

9

NEUDatenALT

0 1 2 3 4 5 6 7 8 90

1

2

3

4

5

6

7

8

9

NEUDatenALT





k-Medoid

I nicht mit Centroid, sondern MedoidI Wiederholtes Tauschen eines Medoids mit einem Nichtmedoid,

wobei sich die Qualität des Clusterns verbessern muss.

I Sofortige Neuordnung

I Variante 1: Partitioning Around Medoids (PAM) (relativvollständige Suche)

I Variante 2: Clustering Large Applications based onRANdomized Search (CLARANS) (stark eingeschränkte Suche)




Aufgaben

Aufgabe 5.6 (k-Means)

Gegeben seien die folgenden (zweidimensionalen) Datensätze:

x 3 6 8 1 2 2 6 6 7 7 8 8y 5 2 3 5 4 6 1 8 3 6 1 7

Bilden Sie mittels k-Means 3 Cluster. Als Anfangszentren verwendenSie die ersten drei Datentupel.

Aufgabe 5.7 (k-Means)

Erläutern Sie, wie man bei dem k-Means-Verfahren den Centroidberechnet.



5.6.2 Hierarchisches Clustering

Hierarchisches Clustering

I Ziel: Aufbau einer Hierarchie von Clustern

I Verschmelzen von Clustern mit minimaler Distanz (größterÄhnlichkeit)

I Darstellung: Baumstruktur (Dendrogramm)

Ein Dendrogramm ist ein Baum, dessen Knoten jeweils einen Clusterrepräsentieren und der folgende Eigenschaften besitzt:

I Die Wurzel repräsentiert die gesamte Datenmenge.

I Ein innerer Knoten repräsentiert die Vereinigung aller Objekte,die in den darunterliegenden Teilbäumen enthalten sind.

I Die Blätter repräsentieren einzelne Objekte.





Abb. 29: Hierarchisches Clustering





Man unterscheidet zwei Verfahren:

Agglomeratives Clustering

Divisives Clustering




Agglomeratives Clustering

I Beginn: Jedes Objekt ist ein eigener Cluster.

I Verschmelzen von jeweils 2 ähnlichsten Clustern zu einem.

I usw. bis nur noch ein Cluster (alle Objekte) vorhanden




Divisives Clustering

I Beginn: Alle Objekte bilden ein Cluster.

I Teilen des / der Cluster in jeweils 2 oder mehrere Teil-Cluster

I usw. bis jedes Objekt ein eigener Cluster ist




Hierarchisches Clustern

Nachteil beider Techniken einmal gebildete Cluster (früheVerschmelzungs- oder Aufteilungsentscheidungen)können nicht wieder aufgelöst werden



5.6.3 Erwartungsmaximierung

Erwartungsmaximierung

I Objekte werden nicht bestimmten Clustern eindeutig zugeordnet

I Objekte können zu mehreren Clustern gehören

I jeweils mit einer bestimmten WahrscheinlichkeitI Kombination von k Gaußverteilungen





Man beginnt also mit k zufällig gewählten Gauß-Verteilungen. Nunberechnet man die Wahrscheinlichkeiten, mit denen

I ein Punkt x (Objekt) aus einer

I der k Gaußverteilungen Ci(i = 1, . . . ,k) entstanden ist.

P(x |Ci) =1√

(2π)k |∑Ci|×e−

12 (x−µCi )

T (∑Ci)−1(x−µCi )

Dabei ist:

I k die Anzahl der ClusterI ∑Ci

die Kovarianzmatrix für die Punkte im Cluster Ci

I µCi der Vektor des Mittelpunkts des Clusters i





Jetzt berechnet man die Gesamt-Wahrscheinlichkeitsdichte für x :

P(x) =k

∑i=1

Wi ×P(x |Ci)

I Wi . . . Anzahl der Objekte im Cluster Ci an Gesamtzahl (relativeHäufigkeit)





Die Wahrscheinlichkeit, mit der ein bestimmtes Objekt x zu einemCluster Ci gehört, ist (Satz von Bayes):

P(Ci |x) = Wi ×P(x |Ci)

P(x)

Gesamt-Wahrscheinlichkeitsdichte :

E = ∑x∈D

log(P(x))

E soll maximiert werden.




Iterativer Algorithmus

1. Initiale Belegung der Parameter

2. Berechne P(xi),P(xj |Ci) und P(Ci |xj)

3. Berechne neue Mittelpunkte der k Cluster

4. Gehe zu 2.

Ende, falls E nicht weiter verbessert werden kann.



5.6.4 Dichtebasiertes Clustering

Dichtebasiertes Clustering

I Cluster als Menge von Objekten, die in einer bestimmten Dichtezueinander stehen

I getrennt durch Regionen geringerer Dichte


5.7 Naive Bayes Folie 5-96 (197)

Naive Bayes

I Ziel: Vorhersage der wahrscheinlichsten Klasse

I Es findet kein Training eines Modells statt.

I Die Vorhersage wird direkt aus den Trainingsdaten berechnet.

I Grundannahme: Alle Attribute sind voneinander unabhängig.



5.7.1 Bayessche Formel

Bedingte Wahrscheinlichkeit

Sei Y ein Ereignis mit P(Y )> 0. Dann heißt

P(X |Y ) =P(X ∧Y )

P(Y )

bedingte Wahrscheinlichkeit von X unter der Bedingung Y . FallsP(Y ) = 0, so ist die bedingte Wahrscheinlichkeit nicht definiert.



5.7.1 Bayessche Formel

Die Bayessche FormelStellt man die Formel für die bedingte Wahrscheinlichkeit um, so erhältman:

P(X ∧Y ) = P(Y )∗P(X |Y )

Betrachtet man die bedingte Wahrscheinlichkeit von Y bezüglich X , soergibt sich analog:

P(Y ∧X) = P(X)∗P(Y |X)

Da das logische Und kommutativ ist, gilt:

P(Y )∗P(X |Y ) = P(X)∗P(Y |X)

Somit erhält man die Bayessche Formel:

P(X |Y ) =P(Y |X)∗P(X)

P(Y )



5.7.2 Berechnungsgrundlagen

Naive Bayes – Berechnungsgrundlagen

Sei A = {a1, . . . ,an} eine Menge von Attributwerten, z.B.{sunny ,hot}. Wir möchten berechnen, ob (nicht) gespielt wird(yes/no), wenn es sunny und hot ist.Mit der Bayesschen Formel erhalten wir:

P(yes|[sunny ,hot]) =P([sunny ,hot]|yes)∗P(yes)

P([sunny ,hot])

Analog berechnen wir

P(no|[sunny ,hot]) =P([sunny ,hot]|no)∗P(no)

P([sunny ,hot])

Wir sagen dann yes vorher, wenn P(yes|[sunny ,hot]) größer alsP(no|[sunny ,hot]) ist, sonst no.





In beiden Formeln im Nenner der gleiche Term: P([sunny ,hot]).Da wir nur bezüglich der Größe vergleichen, können wir diesenweglassen.Wir reden deshalb nicht mehr von P, sondern von Likelihood L.

L(yes|[sunny ,hot]) = P([sunny ,hot]|yes)∗P(yes)L(no|[sunny ,hot]) = P([sunny ,hot]|no)∗P(no)

Der Naive-Bayes-Algorithmus geht von der Unabhängigkeit derAttribute aus und ersetzt:

P([sunny ,hot]|yes) = P(sunny |yes)∗P(hot|yes)





Nun nochmal in der Übersicht:

Relative Häufigkeit h[a,k ] des Attributs a in der Klasse k

Likelihood L[k ](A) =n∏i=1

h[ai ,k ] ×h[k ]

Wahrscheinlichkeit P[kj ](A) =L[kj ](A)

∑i

L[ki ](A)

Vorhersage km : Pm(A) = maxj(P[kj ](A))



5.7.3 Beispiel Wetterdaten

Beispiel Wetterdaten

Tag outlook temperature humidity windy play1 sunny hot high false no2 sunny hot high true no3 overcast hot high false yes4 rainy mild high false yes5 rainy cool normal false yes6 rainy cool normal true no7 overcast cool normal true yes8 sunny mild high false no9 sunny cool normal false yes10 rainy mild normal false yes11 sunny mild normal true yes12 overcast mild high true yes13 overcast hot normal false yes14 rainy mild high true no

Tabelle 10: Wetter-Daten



5.7.3 Beispiel Wetterdaten

Beispiel Wetterdaten

Wird an einem Tag mit folgenden Eigenschaften gespielt?

outlook = sunnytemperature = hothumidity = normal

windy = true



5.7.4 Naive-Bayes-Algorithmus

Naive Bayes Algorithmus

Schritt 1: Ermittlung der relativen Häufigkeiten

h[sunny ,yes] =29

weil

I es 9 Tage gibt, an denen gespielt wurde (play=yes), und

I an 2 dieser Tage outlook=sunny war.





playyes no

sunny 2/9 3/5outlook overcast 4/9 0/5

rainy 3/9 2/5hot 2/9 2/5

temperature mild 4/9 2/5cool 3/9 1/5high 3/9 4/5humiditynormal 6/9 1/5true 3/9 3/5windyfalse 6/9 2/5





Schritt 2: Berechnung der Likelihoods

L[yes](sunny ,hot,normal, true)=h[sunny ,yes]*h[hot,yes]*h[normal,yes]*h[true,yes]*h[yes]= 2/9 * 2/9 * 6/9 * 3/9 * 9/14≈ 0,007055

L[no](sunny ,hot,normal, true)= h[sunny ,no] * h[hot,no] * h[normal,no] * h[true,no] * h[no]= 3/5 * 2/5 * 1/5 * 3/5 * 5/14≈ 0,010286





Schritt 3: Berechnung der Wahrscheinlichkeiten (wir kürzensunny,hot,normal,true mit A ab).

P[yes](A)=L[yes](A)/(L[yes](A)+ L[no](A) )=0,007055/(0,007055+0,010286)≈ 0,406835

P[no](A) = L[no](A) /(L[yes](A)+ L[no](A) )=0,010286/(0,007055+0,010286)≈ 0,593165

Schritt 4: Vorhersage

(P[yes](A) = 40,68%)< (P[no](A) = 59,31%) ⇒ NO



5.7.5 Aufgaben

AufgabenAufgabe 5.8 (Naive Bayes)

I Alternative: Gibt es in der Nähe ein geeignetes anderesRestaurant? (ja/nein)

I Fr/Sa: Ist Freitag oder Samstag? (ja/nein)

I Hungrig: Bin ich hungrig? (ja/nein)

I Gäste: Wieviele Leute sind im Restaurant? (keine/einige/voll)

I Reservierung: Habe ich reserviert? (ja/nein)

I Typ: Um welche Art von Restaurant handelt es sich?(Franz./Chin./Ital./Burger)

I Wartezeit: Welche voraussichtliche Wartezeit wird vomRestaurant geschätzt? (0-10/10-30/30-60/>60)

I Warten (Zielattribut): Warte ich, wenn alle Tische besetzt sind?(ja/nein)



5.7.5 Aufgaben

Aufgaben

Aufgabe 5.8 cont.

Berechnen Sie mit Naive Bayes, ob wir in folgenden Fällen wartenoder nicht.

Alt. Fr/Sa Hung. Gäste Reserv. Typ Zeit Wartenja nein ja einige nein Franz. 30-60ja ja ja voll ja Chin. 10-30




5.7.5 Aufgaben

AufgabenAufgabe 5.8 cont.





Tabelle 11: Restaurant-Daten



5.7.5 Aufgaben

Aufgaben

Aufgabe 5.9 (Naive Bayes)

Seien folgende Datensätze gegeben (a=angest, s=selbst, v=verh,l=ledig, M=Miete, E=Eigentum)

Beruf a a a a s s s sFam.st. v l v v l l v vKinder j n n j j n j n

Wohnung M E M E E M E E

Wo lebt ein lediger Angestellter mit Kindern?

6 Datenvorbereitung Wissensextraktion

26. Januar 2015

Inhaltsverzeichnis

Einführung


Anwendungsklassen



Datenvorbereitung

Bewertung


26. Januar 2015


DatenvorbereitungMotivationArten der DatenvorbereitungDatenvorbereitung – Beispiel


Folie 6-1 (215)

Datenvorbereitung

Experience is something you don’t get until just after you need it.Olivier’s Law

Unter Vorbereitung fassen wir die 3 ersten Teilprozesse desKDD-Prozesses zusammen.


6.1 Motivation Folie 6-2 (216)

Motivation

Daten müssen i.allg. vorbereitet werden.

I Wertebereiche und AusreißerI Fehlende, ungenaue, falsche, widersprüchliche Werte

Auch Nicht-Wissen kann Information sein!I Bedeutung der DatenI Enthält das falsche / fehlende Datum eine Info (bewusste

Nichtantwort)?I Welchen Einfluss hat der fehlende Wert auf das Resultat?



Motivation

I DimensionsreduktionI Viele Attribute→ hochdimensionale ProblemeI Visuelle Wahrnehmungsfähigkeit des Menschen beschränktI Hohe Dimension→ hohe Rechenzeit

Reduktion der hohen Dimension durch:I Ausblenden einiger AttributeI Zusammenfassung von abhängigen Komponenten

I Datentransformation, Skalierung etc.



Datenvorbereitung und DM

I Datenvorbereitung spielt wichtige RolleI für LaufzeitverhaltenI für Qualität der Resultate

I etwa 80% des Gesamtaufwands



Garbage in – garbage out

I Analyseverfahren versagen auf schlechten Daten.

I Deshalb ist die Datenvorbereitung für den Erfolg wichtig.

I GIGO: Garbage in, garbage out.


6.2 Arten der Datenvorbereitung Folie 6-6 (220)

Arten der Datenvorbereitung

Folgende Klassen der Vorbereitung unterscheidet man:

Datenselektion und -integration Daten auswählen undzusammenfügen

Datensäuberung Daten werden bereinigt.

Datenreduktion Daten werden reduziert, z.B. bezüglich derDimension.

Datentransformation Daten werden umgewandelt, um so adäquateDarstellungsformen (in Abhängigkeit vom jeweiligenVerfahren) für die Daten zu bekommen.



6.2.1 Datenselektion und -integration

Datenselektion und -integration

Motivation: Gewünscht ist eine filialübergreifende Datenanalyse.

I Jede Filiale hat unter Umständen ihre eigene Datenbank.

I Es ist eine unterschiedliche Semantik und Syntax der Attributemöglich.

Die Datenintegration fügt Daten mehrerer Datensätzeunterschiedlicher Quellen (verschiedene Datenbanken) zusammen.Ergebnis sollte ein schlüssiger Datensatz sein.



6.2.1 Datenselektion und -integration

Probleme

Entitätenidentifikationsproblem Welche Merkmale besitzen dieselbeSemantik?

Redundanzen z.B. Name/name

Widersprüche z.B. unterschiedliche Adressen für die gleiche Person

Datenwertkonflikte z.B. Entfernung in Meilen und Kilometern



6.2.2 Datensäuberung

Datensäuberung

I Fehlende Daten

I Verrauschte Daten

I Falsche Daten

I Inkonsistente Daten




Fehlende Daten

I Attribut ignorieren

I Fehlende Werte manuell einfügen

I Globale Konstante zum Ausfüllen des fehlenden Werts (z.B.:unbekannt, minus unendlich)

I Durchschnittswert aller Einträge derselben Klasse

I Wahrscheinlichsten Wert eintragen (anhand statistischerMethoden ermitteln)

I Datensatz als fehlerhaft kennzeichnen und vonWeiterverarbeitung ausnehmen




Fehlende Daten

Achtung:I Einfügen von Werten⇒ Veränderung des Datenbestands

I Qualität der Daten evtl. verändert.

I Semantik der Daten kann dadurch verfälscht werden.

I Ignorieren/Weglassen verfälscht die Daten bezüglich derWahrscheinlichkeitsverteilung der Attributwerte.

I Ziel, dass jegliche Veränderung unseres Datenbestandsinformationsneutral sein sollte, verletzt.

I Allerdings haben wir bei fehlenden Daten keine Alternative.




Verrauschte Daten

I Klasseneinteilung (binning): Man gruppiert die Daten und ersetztsie durch Mittelwerte oder Grenzwerte.

I Verbundbildung (clustering): Hier werden die Ausreißer durchVerbundbildung erkannt.

I Kombinierte Maschine/Mensch-Untersuchung (combinedcomputer and human inspection):

I Computer erstellt Liste (anscheinend) befremdlicher Werte.I Mensch filtert die Ausreißer aufgrund von Erfahrungswerten

heraus.

I Regression: Man beschreibt die Daten als mathematischeFunktion. Dann ersetzt man die realen Datenwerte durch dieberechneten Funktionswerte der gefundenen Funktion.




Inkonsistente und falsche Daten

Beispiel 6.1 (Inkonsistente Daten)

Seien die folgenden Tabellen gegeben:

KundendatenKu-Nr. Name Ort1 Meier Wismar2 Schulze Schwerin3 Lehmann Rostock

BestellungenBestell-Nr. Ku-Nr.1 23 12 14 4

In der Bestellungen-Tabelle wird auf den Kunden 4 verwiesen, den esaber gar nicht gibt.




Inkonsistente und falsche Daten

Folgende Korrekturen sind möglich:

I Zuhilfenahme anderer Datensätze

I Künstliches Anlegen eines fehlenden Schlüsselattributs

I Falls nicht möglich: betreffenden Datensatz löschen oder alsfehlerhaft markieren.




Fehlerhafte, unzulässige Werte

Beispiel 6.2 (Fehlerhafte, unzulässige Werte)

I Verletzter Wertebereich: Wenn auf einstellige natürliche Zahlenbeschränkt, dann dürfen keine Zahlen x < 0 oder x > 9auftauchen.

I Verletzte Plausibilitätsbeziehungen: Sonst umsatzschwacherKunde hat plötzlich sehr hohen Jahresumsatz.



6.2.3 Datenreduktion

Datenreduktion

Problem: Datensätze sehr umfangreichStrategien: Folgende Techniken können angewendet werden.

1. Aggregation

2. Dimensionsreduktion

3. Datenkompression

4. Numerische Datenreduktion




Aggregation

Unter Aggregation (auch Verdichtung) versteht man dasZusammenfassen von Fakten zu einem Fakt oder das Generalisierender Daten. So kann man z.B. Daten durch ihre Mittelwerte ersetzenoder Teilwerte zu einer Gesamtsumme zusammenfassen.




Dimensionsreduktion

Bei der Dimensionsreduktion werden irrelevante Daten (Attribute)vernachlässigt und relevante Daten einbezogen.

I Schrittweise Vorwärtsauswahl: Gute Attribute werden schrittweisein die Zielmenge eingegliedert.

I Schrittweise Rückwärtseliminierung: Ausgehend von derGesamtmenge werden schlechte Attribute schrittweise eliminiert.

I Kombination aus beiden




Datenkompression

Die Daten werden entweder transformiert oder kodiert, um eineReduktion der Datenmenge und damit eine Reduktion der Komplexitätdes Data Mining zu erhalten.




Numerische Datenreduktion1. mit Hilfe von Stichproben

Zufällige Stichprobe zufällige AuswahlRepräsentative Stichprobe zufällige, aber repräsentative

AuswahlGeschichtete Stichprobe zufällige Auswahl, wichtige Attribute

haben WertInkrementelle Stichproben schrittweise VerfeinerungAverage Sampling Daten teilen und separat analysieren, dann

Resultate mittelnSelektive Stichprobe Stichprobe gezieltWindowing inkrementell, Erweiterung um falsch bewertete

DatensätzeClustergestützte Stichprobe Cluster von ähnlichen Daten, davon

jeweils einer

2. Lineare Regression




Datentransformation

Anpassung:

1. von unterschiedlichen Datenstrukturen

2. der Datentypen

3. von Konvertierungen oder Kodierungen

4. von Zeichenketten

5. von Datumsangaben

6. von Maßeinheiten und Skalierungen

Weitere Transformationen können in Betracht kommen:

1. Kombination oder Separierung von Attributen

2. ggf. Berechnung abgeleiteter Werte

3. Datenaggregation

4. Datenglättung




Anpassung unterschiedlicher Datenstrukturen

Innerhalb der Datenbank kann es Attribute mit nicht kompatiblenDatenstrukturen geben. Diese müssen gegebenenfalls angepasstwerden.




Anpassung der Datentypen

Betrachtet man die 2 als Datum, so stellt sich die Frage:

I Ist diese 2 vom Datentyp Char oder Integer?

I Sollte eine Umwandlung stattfinden?




Anpassung von Konvertierungen oder Kodierungen

Datenquelle und Zielmenge benutzen evtl. unterschiedlicheKodierungen.Z.B. Binärkodierung: aus Attributen mit einer bestimmten AnzahlMerkmalsausprägungen⇒ Menge binärer Attribute.Diskretisierung wird angewendet, um den Wertebereich vonquantitativen Attributausprägungen in endlich vielen Teilmengenzusammenzufassen.




Anpassung von Zeichenketten

Kann das Data-Mining-Programm mit Umlauten, Groß- undKleinschreibung sowie Leerzeichen in den Datensätzen umgehen,oder sollte hier eine Umwandlung erfolgen?




Anpassung von Datumsangaben

Datumsangaben sind oft unterschiedlich kodiert. Es können auchDaten aus unterschiedlichen Zeitzonen vorhanden sein.




Anpassung von Maßeinheiten und Skalierungen

I nationale Standards bei Maßeinheiten→ Anpassungenerforderlich.

I Inch; Zentimeter; Yard; Meter.I Normalisierung: Transformation aller Merkmalsausprägungen

auf die Werte einer stetigen, numerischen Skala (z.B. [0,1]):xneu =

x−min(xi)max(xi)−min(xi)

I Zunächst den Minimalwert subtrahieren (Minimum wird 0)I Alle Werte durch den ermittelten Maximalwert dividieren

I Alternativ: statistischer Mittelwert und Standardabweichung derAttributwerteSubtrahieren den Mittelwert von jedem Wert, anschließend dasErgebnis durch die Standardabweichung dividieren.




Kombination oder Separierung von Attributen

I Evtl. nötig: verschiedene Attribute zu einem neuenzusammenzufügen

I Tag; Monat; Jahr→ Datum.




Berechnung abgeleiteter Werte

I Berechnen abgeleiteter Werte→ ganz neue Attribute

I Einnahmen - Ausgaben→ Gewinn.




Datenaggregation

I Oft: Daten verfügbar in einer zu feinen Aggregationsebene.

I Bspl.: Einwohnerzahl von Berlin gesucht, aber nurEinwohnerzahlen der einzelnen Stadtteile verfügbar




Datenglättung

Die Hauptidee der Datenglättung (s. auch verrauschte Daten) ist, dassjeder (numerische) Wert aus der gegebenen Datenmenge durch dieGleichung

Wert(i) = Mittelwert(i)+Rauschen

dargestellt werden kann, wobei i der i-ten Instanz entspricht.Ziel: Reduzierte WertemengeMan kennt vier Techniken, mit denen Daten geglättet werden können:

I Eingruppierung (binning)

I Clustering

I kombinierte menschliche und maschinelle Kontrolle

I Regression




Fazit

Datentransformation dient dazu, Daten zwischen verschiedenenFormen zu transformieren. Es können auch bestehende Attribute inneue Attribute aufgeteilt oder Daten zwischen verschiedenen Ebenenaggregiert werden, um eine geänderte Sicht auf die Daten zu erhalten.


6.3 Datenvorbereitung – Beispiel Folie 6-33 (247)

Datenvorbereitung – BeispielPers.nr.

Wohn-ort

Ge-schlecht

Alter Jahres-gehalt

Betriebs-zugehörigkeit

Position Bildungs-abschluss

1 23966 m 45 32 10 arb Lehre2 23966 w 57 35000 25 verw Bachelor3 23966 m 52 40 5 manager Master4 23966 m 28 27 6 arb Lehre5 23966 male 57 45 25 manager Master6 23966 fem 26 27 96 arb Lehre7 23966 m 39 39 4 manager Master8 23966 m 38 32 3 arb Lehre9 23966 m 42 31 15 arb ohne10 23966 w 37 30 10 verw Abi11 23966 m 45 32 8 arb12 23966 m 37 513 23966 w 35 30 15 verw Abi

Tabelle 12: Ausgangsdaten



Datenvorbereitung – Beispiel

Was fällt uns als erstes auf?

I Das Attribut Wohnort enthält keine nützliche Information.

I Das Geschlecht ist mal als m/w angegeben, mal als male/fem.

I Beim Jahresgehalt ist in Datensatz 2 wohl das Gehalt nicht inTausend angegeben, sondern absolut.

I Im Datensatz 12 fehlen etliche Werte. Diesen sollten wir folglichweglassen.

I Im Datensatz 6 steht bei Betriebszugehörigkeit eine 96. 2Interpretationen: 96=1996 oder Monate. Wir entscheiden uns fürdie Monate.

I In Datensatz 11 fehlt der Bildungsabschluss. Das können wir z.B.korrigieren, indem wir dort den häufigsten Wert einsetzen, der fürdie gleiche Position (arb) vorkommt: Lehre.



Bereinigte Daten

Pers.nr.

Ge-schlecht

Alter Jahres-gehalt



1 m 45 32 10 arb Lehre2 w 57 35 25 verw Bachelor3 m 52 40 5 manager Master4 m 28 27 6 arb Lehre5 m 57 45 25 manager Master6 w 26 27 8 arb Lehre7 m 39 39 4 manager Master8 m 38 32 3 arb Lehre9 m 42 31 15 arb ohne10 w 37 30 10 verw Abi11 m 45 32 8 arb Lehre13 w 35 30 15 verw Abi

Tabelle 13: Bereinigung der Daten



Ziel der Analyse ?

I . . . zunächst Cluster

I Personalnummer hat keine Information.

I Für das Clustern sind metrische Werte günstig.

I Also nominale Attribute einfach durch Integer-Werte kodieren.




Ge-schlecht

Alter Jahres-gehalt



0 45 32 10 0 11 57 35 25 1 30 52 40 5 2 40 28 27 6 0 10 57 45 25 2 41 26 27 8 0 10 39 39 4 2 40 38 32 3 0 10 42 31 15 0 01 37 30 10 1 20 45 32 8 0 11 35 30 15 1 2

Tabelle 14: Codierung Variante 1



Datenvorbereitung – Beispiel – 3 Cluster

Abb. 30: Clusterversuch 1



Datenvorbereitung – Beispiel normalisiert

I Alter ist dominant.

I Grund: Abstandsmaß.

I Lösung: Normalisieren aller Daten auf das Intervall [0,1].



Datenvorbereitung – Beispiel normalisiert

Ge-schlecht

Alter Jahres-gehalt



0 0,61 0,28 0,32 0 0,251 1 0,44 1 0,5 0,750 0,84 0,72 0,09 1 10 0,06 0 0,14 0 0,250 1 1 1 1 11 0 0 0,23 0 0,250 0,42 0,67 0,05 1 10 0,39 0,28 0 0 0,250 0,52 0,22 0,55 0 01 0,35 0,17 0,32 0,5 0,50 0,61 0,28 0,23 0 0,251 0,29 0,17 0,55 0,5 0,5




Datenvorbereitung – Beispiel - normalisiert

Abb. 31: Clusterversuch 2 – Alter



Datenvorbereitung – BeispielGute Cluster !!

Abb. 32: Clusterversuch 2 – Bildungsabschluss




Nun als Ziel: Klassifikation.Brauchen nominale/ordinale Attribute.Wandeln metrische Attribute in ordinale / nominale um.




Ge-schlecht

Alter Jahres-gehalt



m alt gering kurz arb Lehrew alt viel lang verw Bachelorm alt viel kurz manager Masterm jung gering kurz arb Lehrem alt viel lang manager Masterw jung gering kurz arb Lehrem jung viel kurz manager Masterm jung gering kurz arb Lehrem alt gering lang arb ohnew jung gering kurz verw Abim alt gering kurz arb Lehrew jung gering lang verw Abi




Beispiel – Entscheidungsbaum

Abb. 33: Entscheidungsbaum mit ID3

7 Bewertung Wissensextraktion

26. Januar 2015

Inhaltsverzeichnis

Einführung


Anwendungsklassen



Datenvorbereitung

Bewertung


26. Januar 2015


BewertungInteressantheitsmaßeGütemaße und FehlerkostenTrainings- und TestmengenBewertung von Clustern


Folie 7-1 (262)

Bewertung

Negative expectations yield negative results. Positive expectationsyield negative results.

Nonreciprocal Laws of expectations.

1. Das Prinzip der minimalen Beschreibungslängen

2. Interessantheitsmaße

3. Fehlerraten und Fehlerkosten

4. Trainings- und Testmengen


Folie 7-2 (263)

Prinzip der minimalen Beschreibungslängen

Die Beschreibungslänge ist definiert als:

I Speicherplatz zur Beschreibung einer Theorie plus

I Speicherplatz zur Beschreibung der Fehler der Theorie

Dieses Konzept geht auf William of Ockham, geboren in Ockham (inSurrey, England) ca. 1285 zurück, der postulierte, dass ein Modelldesto besser sei, je einfacher es sei (Occam’s razor).


7.1 Interessantheitsmaße Folie 7-3 (264)

Interessantheitsmaße

Spezielle Aspekte der Bewertung von AssoziationsregelnNotwendigkeit:

I (zu) viele Regeln

I keine automatische Filterung möglich (Problembezogenheit)

Idee: Interessantheitsmaße der deskriptiven Statistik übernehmen



Interpretation und Evaluierung von Regeln

I signifikante Merkmale der Regeln: beispielsweise Konfidenz undSupport

I Filtern von Regeln auf der Basis dieser Merkmale

I grafische Darstellungen von Regeln

I Basis der Bewertung von Regeln: Interessantheitsmaße



7.1.1 Support

Support

Der Support einer Regel A→ B ist definiert durch:

supp(A→ B) = P(A∪B).

Wir berechnen also die relative Häufigkeit, in wievielen Datensätzenunserer Datenmenge sowohl A als auch B vorkommt.



7.1.1 Support

Support

Support: Flächeninhalt der schraffierten Fläche, geteilt durch dieFläche der gesamten Menge.

Abb. 34: Support der Assoziationsregel A→ B

Problem:I Auch seltene Items können interessant sein.



7.1.2 Konfidenz

Konfidenz

conf(A→ B) = P(B|A) = supp(A→ B)supp(A)

Konfidenz: Verhältnis der schraffierten Fläche und der gestricheltschraffierten Fläche.

Abb. 35: Konfidenz der Assoziationsregel A→ B



7.1.2 Konfidenz

Konfidenz

Probleme:I Triviale Zusammenhänge

I Regeln mit geringer statistischer Korrelation erreichen manchmalhohe Konfidenz.



7.1.2 Konfidenz

Completeness

Weiteres Interessantheitsmaß : Vollständigkeit (completeness).

completeness(A→ B) = P(A∪B|B)

Abb. 36: Completeness der Assoziationsregel A→ B



7.1.2 Konfidenz

Interessantheitsmaße

Beispiel 7.1 (Interessantheismaße für Assoziationsregeln)

Seien folgende Werte gegeben: P(A) = 0,50, P(B) = 0,40,P(A∪B) = 0,35.Es ergeben sich folgende Werte:

supp(A→ B) = P(A∪B) = 0,35

conf(A→ B) = P(B|A) = supp(A→ B)supp(A)

=0,350,50

= 70%

completeness(A→ B) = P(A∪B|B) = supp(A→ B)supp(B)

=0,350,40

=78

Konfidenz der Regel ist nicht sonderlich gut, allerdings hoheCompleteness.



7.1.3 Gain-Funktion

Gain-Funktion

Unangenehme Effekte mit Support/Konfidenz:

I Regel scheitert am Support, obwohl hohe Konfidenz

I Verzicht auf Support würde Regeln mit geringem Support, aberhoher Konfidenz erlauben.

Also: Mix aus Support und Konfidenz, der obige Effekte verhindert.



7.1.3 Gain-Funktion

Gain-Funktion

gain(A→ B) = supp(A→ B)−θ× supp(A).

I Reduktion des Supports einer Regel

I gain = 0: In jedem 1θ -ten Fall, in dem A vorkommt, kommt auch B

vor

I gain > 0: starker Zusammenhang, gain < 0: schwacherZusammenhang



7.1.3 Gain-Funktion

Gain-Funktion

Bemerkung 7.1 (Gain)

Woher kommt der gain? Je geringer der Support von A, desto höhersoll die Konfidenz der Regel sein:

conf(A→ B)≥ minconf

supp(A)+θ

Wir erlauben θ zwischen 0 und 1. Mit conf(A→ B) = supp(A→B)supp(A)

können wir die Ungleichung mit supp(A) multiplizieren und erhalten:

supp(A→ B)≥minconf + supp(A)×θ

supp(A→ B)−θ× supp(A)≥minconf



7.1.4 p-s-Funktion

Kriterien für Interessantheitsmaße

Kriterien für Interessantheitsmaße für Assoziationsregeln (RI):

1. RI(A→ B) = 0 genau dann, wenn supp(A→ B) = P(A)×P(B)ist. Das Interessantheitsmaß sollte 0 sein, wenn A und Bstatistisch unabhängig sind.

2. RI sollte mit supp(A→ B) monoton wachsen.

3. RI sollte mit P(A) und P(B) monoton fallen.

Konfidenz erfüllt nur die Bedingung 2!



7.1.4 p-s-Funktion

p-s-Funktion

ps(A→ B) = supp(A→ B)− supp(A)× supp(B)

I wie Gain-Funktion mit θ = supp(B)

I ps > 0: positiver, ps < 0: negativer statistischerZusammenhang



7.1.5 Lift

Lift

lift(A→ B) =supp(A→ B)

supp(A)× supp(B)=

conf(A→ B)supp(B)

I Wahrscheinlichkeit der Regel im Verhältnis zu ihrem Auftreten

I Außergewöhnlichkeit der Regel


7.2 Gütemaße und Fehlerkosten Folie 7-17 (278)

7.2.1 Fehlerraten

Fehlerraten

Fehlerrate bei Klassifikationen

Fehlerrate =Fehler

Alle

Fehlerrate bei numerischer Vorhersage

Fehlerrate =∑i(Realwerti −Vorhersagewerti)

2

∑i

Realwert2i

ErfolgsrateErfolgsrate = 1−Fehlerrate



7.2.2 Weitere Gütemaße für Klassifikatoren

Weitere Gütemaße für Klassifikatoren

Man unterscheidet 4 Fälle:

TP (richtig positiv) Ein guter Kunde wird als guter erkannt.

TN (richtig negativ) Ein nicht guter Kunde wird als nicht guter erkannt.

FP (falsch positiv) Ein nicht guter Kunde wird als guter erkannt.

FN (falsch negativ) Ein guter Kunde wird als nicht guter erkannt.

Darauf aufbauend definiert man eine Reihe von abgeleitetenKenngrößen.





Korrekte Klassifikationen T=TP+TN

Falsche Klassifikationen F=FP+FN

Relevanz R=TP+FN (Anzahl der guten Kunden)

Irrelevanz I=FP+TN (Anzahl der nicht guten Kunden)

Positivität P=TP+FP (Anzahl der als gut klassifizierten Kunden)

Negativität N=TN+FN (Anzahl der als nicht gut klassifiziertenKunden)

Korrektheitsrate T/n (Anteil der korrekt klassifizierten Kunden)

Inkorrektheitsrate F/n (Anteil der nicht korrekt klassifizierten Kunden)





Richtig-positiv-Rate TPR=TP/R (Wie oft wurde ein guter Kunde auchals solcher klassifiziert.) (Sensitivität, Trefferquote,Recall)

Richtig-negativ-Rate TNR=TN/I (Wie oft wurde ein nicht guter Kundeauch als solcher klassifiziert.)

Falsch-positiv-Rate FPR=FP/I (Wie oft wurde ein nicht guter Kundeals guter klassifiziert.)

Falsch-negativ-Rate FNR=FN/R (Wie oft wurde ein guter Kunde alsnicht guter klassifiziert.)





Positiver Vorhersagewert, Genauigkeit, Präzision TP/P (Wie oft ist einals gut vorhergesagter Kunde ein guter Kunde?)

Negativer Vorhersagewert TN/N (Wie oft ist ein als nicht gutvorhergesagter Kunde ein nicht guter Kunde?)

Negative Falschklassifikationsrate FN/N (Wie oft ist ein als nicht gutvorhergesagter Kunde ein guter Kunde?)

Positive Falschklassifikationsrate FP/P (Wie oft ist ein als gutvorhergesagter Kunde ein nicht guter Kunde?)



7.2.3 Fehlerkosten

Fehlerkosten

I Klassifikator wirkt sich auf Gewinn bzw. Verlust einer Firma aus.I Kredit für Bankkunde bewilligt,

I . . . den dieser nicht zurückzahlt, entstehen zusätzliche Kosten.I . . . den dieser zurückzahlt, entsteht Gewinn.

I Kredit für Bankkunde nicht bewilligt,I . . . den dieser zurückgezahlt hätte, entsteht Verlust in Zinshöhe.I . . . den dieser nicht zurückgezahlt hätte, wurde Verlust verhindert.

I Fehler ist also nicht gleich Fehler,korrekte Vorhersage nicht gleich korrekte Vorhersage.

I Folglich: gewichtete Fehlerrate



7.2.3 Fehlerkosten

Kostenmatrix

Vorhersage0 1

0 10 -201 -30 20

Wird ein Datensatz des Typs 0 mit 1 vorhergesagt, so kostet uns das20, eine korrekte Vorhersage für 0 bringt uns 10.; Gewichtete Fehlerberechnung


7.3 Trainings- und Testmengen Folie 7-24 (285)

Trainings- und Testmengen

I Lernen allein auf der gegebenen Menge nicht ausreichend.

I Verfahren würde gegebene Beispiele auswendig lernen.

I Also: separate Testmenge erforderlich

Wie teilt man Beispielmenge auf in:

I Trainingsmenge

I Testmenge



7.3.1 Holdout

Holdout

Beim Holdout wird die Instanzenmenge in zwei Teilmengen zerlegt,wobei die eine zum Trainieren und die andere zum Testen verwendetwird.

Train∪Test = Instance



7.3.2 Stratifikation

Stratifikation

zufälliges Holdout evtl. Problem, dass Testdaten und TrainingsdatenBeispiele völlig unterschiedlicher Klassen enthalten

Stratifikation versucht Teilung so, dass sowohl in der Trainings- alsauch in der Testmenge die Häufigkeitsverteilung h derKlassen K in der gesamten Instanzenmenge abgebildetwird.

∀k ∈ K : hInstancek = hTrain

k = hTestk



7.3.3 Kreuzvalidierung

Kreuzvalidierung

I Aufteilung der Datenmenge stratifiziert in V gleich großeTeilmengen

I Auswahl EINER dieser Untermengen als Testmenge

I Training mit den anderen Untermengen

I Test mit zurückbehaltener Testmenge

I Wiederholung mit jeder anderen Teilmenge als Testmenge

I Fehlerrate des Verfahrens: Mittelwert der jeweiligen Fehlerraten

Fehlerrate =

V∑

i=1Fehlerratei

V



7.3.4 Leave-one-out

Leave-one-out

Das Leave-one-out-Verfahren ist im wesentlichen identisch mit derKreuzvalidierung. Hierbei wird jedoch die N-elementigeInstanzenmenge in genau N Teilmengen zerlegt.

Fehlerrate =

|Instance|∑

i=1Fehlerratei

|Instance|


7.4 Bewertung von Clustern Folie 7-29 (290)

Bewertung von Clustern

Ansatz 1:G1 =

k

∑i=1

∑x∈Ci

dist(x ,mi)2

Güte1 =1

k∑

i=1∑

x∈Ci

dist(x ,mi)2

Ansatz 2: Güte2 = ∑1≤i≤j≤k

dist(mj ,mi)2

Man kann die Ansätze kombinieren, indem man beide Gütemaßemultipliziert:

Güte = Güte1×Güte2

8 Literatur Wissensextraktion

Folie 8-30 (291)

Literatur

Jürgen Cleve, Uwe Lämmel.Data Mining.Oldenbourg, 2014.

Usama M. Fayyad, Gregory Piatetsky-Shapiro, Padhraic Smyth,Ramasamy Uthurusamy.Advances in Knowledge Discovery and Data Mining.MIT Press, 1996.

Hans-Georg Kemper and Walid Mehanna and Carsten Unger.Business Intelligence.Vieweg, 2006.

Dorian Pyle.Data Preparation for Data Mining.Morgan Kaufmann, 1999.

Documents

Infos - Startseite - Hochschule Wismarcleve/vorl/dmining14/fdm8bwM.pdf · 1 Einführung Wissensextraktion 1.3 Ablauf einer Datenanalyse Folie 1-20 (25) 1.3.4 Datentransformation Datentransformation