Post on 05-Apr-2015
transcript
Datenbanksysteme 3 Sommer 2003Data Mining - 1Worzyk
FH Anhalt
Data Mining
• Definition, Anwendungsbespiele• Data Mining Prozess• Data Mining Cup
– 2001– 2002– 2003
Datenbanksysteme 3 Sommer 2003Data Mining - 2Worzyk
FH Anhalt
Datenquellen, Datensenken und die Wüste
vorhandene
Daten
benötigte
Daten
gewünschte
Daten
Nachfrage
Datenbanksysteme 3 Sommer 2003Data Mining - 3Worzyk
FH Anhalt
DefinitionData Mining
Data Mining„ is the nontrivial extraction of
implicit, previous unknown and potentially useful information from data“
William J. Frawley Gregory Piatetsky-Shapiro,
Datenbanksysteme 3 Sommer 2003Data Mining - 4Worzyk
FH Anhalt
Leistungsmerkmale
• Hypothesenfreiheit• Automatisierte Vorhersage von
Trends, Verhalten und Mustern• Automatisierte Aufdeckung
unbekannter Strukturen• Zusatzkomponenten für
Preprocessing und Ergebnisaufbereitung
Datenbanksysteme 3 Sommer 2003Data Mining - 5Worzyk
FH Anhalt
Anwendungsbeispiele
Datenbanksysteme 3 Sommer 2003Data Mining - 6Worzyk
FH Anhalt
Anwendungsbeispiele• Astronomie • Erdwissenschaften• Marketing• Investment• Betrugserkennung• Individualisierte Werbeanzeigen• Electronic Commerce• Datenschutz
Datenbanksysteme 3 Sommer 2003Data Mining - 7Worzyk
FH Anhalt
Datenbanksysteme 3 Sommer 2003Data Mining - 8Worzyk
FH Anhalt
Ansatz
Tradi-tionell
DataMining
Hypothesenfestlegen
Methodeentwickeln
Datenbasisanalysieren
Ergebnisseverdichten
Ergebnisseinterpretieren
Anwender ComputerExperte
ComputerSystem
Statistiker Anwender
Datenbasisanalysieren
InteressanteMusterfinden
Ergebnisseinterpretieren
Anwender
Data Mining System
Datenbanksysteme 3 Sommer 2003Data Mining - 9Worzyk
FH Anhalt
DefinitionData Mining
Data Mining„in databases is the non-trivial
process of identifying valid, novel, potential useful, and ultimately understandable patterns in data“
William J. Frawley Gregory Piatetsky-Shapiro,
Datenbanksysteme 3 Sommer 2003Data Mining - 10Worzyk
FH Anhalt
Informationsbedarf abhängig von der
AufgabeGering Hoch
Hoch Hoch strukturierte,stabile Aufgaben;Buchhaltung,Produktion
Hoch strukturierte,stark veränderlicheAufgaben; SoftwareEntwicklung
Gering Schwachstrukturierte, stabileAufgaben;Bildungsbetrieb
Unstrukturierte, starkveränderlicheAufgaben;Forschung,strategische Planung
Veränderlichkeit
Strukturiertheit
Datenbanksysteme 3 Sommer 2003Data Mining - 11Worzyk
FH Anhalt
Data Mining Prozeßmodell
Preprocessing ValidierungInterpretationAnalyse
DataWarehouse
OLTPExt
Daten
Datenbanksysteme 3 Sommer 2003Data Mining - 12Worzyk
FH Anhalt
Data Mining Cup 2001Aufgabe
Ein Versandhändler von Büromaterialien sendet regelmäßig allen seinen Kunden Informationsmaterial. Außerdem führt er größere Werbeaktionen durch, in die er jedoch nur einen Teil seiner Kunden einbezieht. Nach Möglichkeit sollen nur diejenigen Kunden beworben werden, die auf die Werbeaktion mit einer Bestellung reagieren. Bisher wurden 10.000 Kunden in eine Werbeaktion einbezogen, für 18.128 weitere Kunden ist noch zu entscheiden, ob sie in künftige Aktionen einbezogen werden. http://www.dfki.de/~damit/DMC2001/index.html
Datenbanksysteme 3 Sommer 2003Data Mining - 13Worzyk
FH Anhalt
KundenwertmatrixDie durchschnittlichen Kosten und Gewinne, die aus Werbung und den Bestellungen resultieren, können folgender Matrix entnommen werden:
http://www.dfki.de/~damit/DMC2001/aufgabe_01.html
Datenbanksysteme 3 Sommer 2003Data Mining - 14Worzyk
FH Anhalt
Mögliche Auswirkungen
• Alle Kunden (18.128) angeschrieben, alle bestellen => 20 Mio Gewinn
• Alle Kunden angeschrieben, keiner bestellt => 5 Mio Verlust
• Die Hälfte angeschrieben, keiner davon bestellt, die andere Hälfte bestellt => 3.6 Mio Gewinn
• Die Hälfte angeschrieben, alle bestellen, von der anderen Hälfte bestellt keiner => 10 Mio Gewinn
Datenbanksysteme 3 Sommer 2003Data Mining - 15Worzyk
FH Anhalt
Vorhersage
Ideal: Dieser Kunde wird bestellen, jener Kunde wird nicht bestellen
Real: Dieser Kunde wird mit einer Wahrscheinlichkeit von p bestellen
=> Bei welcher Bestellwahrscheinlichkeit p soll der Kunde angeschrieben werden?
Datenbanksysteme 3 Sommer 2003Data Mining - 16Worzyk
FH Anhalt
Optimale Bestellwahrscheinlichkeit
Kunde wird einbezogenK1: p * 1.100 + (1-p)* (-265)
Kunde wird nicht einbezogenK2: p * 625 + (1-p)* (-25)
K1= K2 715 p = 240 => p = 0,33
Datenbanksysteme 3 Sommer 2003Data Mining - 17Worzyk
FH Anhalt
Gegebene Daten
Datenbanksysteme 3 Sommer 2003Data Mining - 18Worzyk
FH Anhalt
Vorgehen
Datenexploration
Behandlung fehlender Werte
Klassifikation mittels fallbasierten Schließens
Klassifikation mittels Bayes‘scherNetze
Klassifikation mittels Entscheidungsbäumen
Aggregation der Ergebnisse
Datenbanksysteme 3 Sommer 2003Data Mining - 19Worzyk
FH Anhalt
Merkmalehttp://www.data-mining-cup.de/2001/aufgabe.html
AKTIV 0/1 Zielmerkmal 0 positiv (ist aktiver Kunde) 1 negativ (ist kein aktiver Kunde)
WO Text West/Ost/Fehlend Standort des Kunden (Merkmale mit unterschiedlicher Skalierung in Abhängigkeit dieses Merkmals sind in der Beschreibung angegeben; konkret ist dies hier nur bei Kaufkraft differenziert)
Regiotyp 11,...,16 Regionaltyp 11 Kern von Ballungsgebieten 12 Rand von Ballungsgebieten 13 Kernstadt einer Region 14 Randgebiet einer Kernstadt 15 ländliche Zentren 16 Orte auf dem Land
…
Datenbanksysteme 3 Sommer 2003Data Mining - 20Worzyk
FH Anhalt
Fehlende Werte
Zur Behandlung einzelner fehlender Werte boten sich drei Wege an:
1. Datensätze, in denen einer oder mehrere Werte fehlen, werden weggelassen.
2. Die fehlenden Werte werden durch die Mittelwerte beziehungsweise die Modalwerte des jeweiligen Merkmals ersetzt.
3. Es wird ein separates Vorhersagemodell zur Rekonstruktion der fehlenden Werte entwickelt und angewandt.
Aufwand-Nutzen-Erwägungen folgend, wurde der zweite Weg beschritten: Fehlende Werte kategorischer Merkmale wurden durch den Modalwert, fehlende Werte numerischer Merkmale durch den arithmetischen Mittelwert des jeweiligen Merkmals ersetzt.
Datenbanksysteme 3 Sommer 2003Data Mining - 21Worzyk
FH Anhalt
Aufteilung
Datenbanksysteme 3 Sommer 2003Data Mining - 22Worzyk
FH Anhalt
Fallbasiertes Schließen
Fallbasiertes Schließen ist eine Methode zum Einsatz gesammelten Erfahrungswissens. Es beruht auf einer sehr einfachen Grundidee:
Beim Lösen von Problemen entstehen Lösungen, die auch auf ähnliche Probleme angewandt werden können. Jedes gelöste Problem wird zusammen mit seiner Lösung in einer Falldatenbank gespeichert.
Beim Auftreten eines neuen Problems wird die Falldatenbank nach ähnlichen Problemen durchsucht.
Die Lösungen dieser ähnlichen Probleme kann dann auf das neue, noch ungelöste Problem übertragen werden.
Datenbanksysteme 3 Sommer 2003Data Mining - 23Worzyk
FH Anhalt
Bayes‘sches Netz
Ein Bayes'sches Netz ist ein gerichteter, azyklischer Graph; jeder Knoten des Graphen ist mit einer (bedingten) Wahrscheinlichkeitsverteilung attributiert.
Die Knoten entsprechen Zufallsvariablen (Merkmalen); die Kanten des Graphen entsprechen kausalen Beziehungen zwischen den Zufallsvariablen.
Die bedingten Wahrscheinlichkeitsverteilungen quantifizieren die kausalen Beziehungen. Sowohl die Struktur als auch die Attribute Bayes'scher Netze sind aus Daten erlernbar.
Mittels geeigneter Verfahren kann über einem Bayes'schen Netz inferiert, also von bekannten Ausprägungen einiger Zufallsvariabler auf unbekannte Ausprägungen anderer Zufallsvariabler geschlossen werden.
http://www.dfki.de/~damit/DMC2001/vorgehen_07.html
Datenbanksysteme 3 Sommer 2003Data Mining - 24Worzyk
FH Anhalt
Bayes‘sches Netz
Datenbanksysteme 3 Sommer 2003Data Mining - 25Worzyk
FH Anhalt
Entscheidungsbäume
Entscheidungsbäume ordnen Objekte, die durch Mengen von Merkmalen beschrieben werden, einer Klasse zu. Alle Knoten und Kanten eines Entscheidungsbaumes sind markiert:
die Blätter des Baumes mit der Klasse, die als Ergebnis zurückgegeben wird,
die inneren Knoten mit dem Merkmal, nach dessen Ausprägung verzweigt wird, und
die Kanten mit den Ausprägungen, die das Merkmal annehmen kann, das im Anfangsknoten der Kante steht.
http://www.dfki.de/~damit/DMC2001/vorgehen_09.html
Datenbanksysteme 3 Sommer 2003Data Mining - 26Worzyk
FH Anhalt
Ergebnisse
• Fallbasiertes Schließen für große Ähnlichkeiten
• Fünf unterschiedliche Entscheidungsbäume, dann nach Anzahl der Klassifikation „aktiv“
Datenbanksysteme 3 Sommer 2003Data Mining - 27Worzyk
FH Anhalt
Ergebnisse
Datenbanksysteme 3 Sommer 2003Data Mining - 28Worzyk
FH Anhalt
Data Mining Cup 2002Aufgabe
Ein Energieversorger möchte mit zielgerichteten Kundenbindungsmaßnahmen seine Kunden halten. Dazu möchte er potenziellen Kündigern einen günstigeren Tarif (Tarif "Rabatt") anbieten. Da dieser Tarif für den Energieversorger einen geringeren Gewinn bedeutet, will er die vorraussichtlich treuen Kunden von diesem Angebot nicht infor-mieren, um nicht zu vielen von diesen Kunden den Tarif "Rabatt„ gewähren zu müssen.
Ziel des Einsatzes von Data Mining ist es hierbei, die potenziellen Kündiger von den treuen Kunden zu unterscheiden. Potenziellen Kündigern wird dann der Tarif "Rabatt" angeboten, um sie damit zu binden. Insgesamt ist es für den Energieversorger deutlich günstiger, einen potenziellen Kündiger weiterhin im Tarif "Rabatt" zu versorgen als ihn ganz zu verlieren.
http://www.dfki.de/~damit/DMC2002/index.html
Datenbanksysteme 3 Sommer 2003Data Mining - 29Worzyk
FH Anhalt
Gegebene Daten
Eigene Daten– payment_type (Art der Bezahlung) – power_consumption (letzter jährlicher Stromverbrauch in
kWh) – hhh (Anzahl Haushalte im Haus) – hgew (Anzahl Gewerbe im Haus)
Gekaufte Daten– Mikroselections-Merkmale (z.B. Kaufkraft, Straßentyp,
Bebauungstyp, Familienstand, usw.) – PKW-Indices (z.B. PKW-Dichte, PKW-Leistungsindex, PKW-
Kleinbusindex, usw.) – Psychonomics-Versicherungstypologien (z.B.
Kundentypen, usw.) – Pharmatypologien (z.B. gesunder Kraftprotz, usw.)
Datenbanksysteme 3 Sommer 2003Data Mining - 30Worzyk
FH Anhalt
Kundenwertmatrix
Kündiger Kunde
Kunde erhält Angebot
43,80 EUR 66,30 EUR
Kunde erhält keine Angebot
0,00 EUR 72,00 EUR
Datenbanksysteme 3 Sommer 2003Data Mining - 31Worzyk
FH Anhalt
Kündigerwahrscheinlichkeit
Datenbanksysteme 3 Sommer 2003Data Mining - 32Worzyk
FH Anhalt
Datensichtung• Aus Trainings- und
Klassifikationsdaten gemeinsame Datenmenge
• Für fehlende Werte Indikatorvariablen eingeführt
• Umkodierung– Modalwert, Ausreißer abschneiden
• Faktorenanalyse
Datenbanksysteme 3 Sommer 2003Data Mining - 33Worzyk
FH Anhalt
Haushalte im Haus
Datenbanksysteme 3 Sommer 2003Data Mining - 34Worzyk
FH Anhalt
Statistische Verfahren
• Clusteranalyse• Kreuztabellen• Logistische Regression in Clustern
Datenbanksysteme 3 Sommer 2003Data Mining - 35Worzyk
FH Anhalt
Test der Ergebnisse
Mit einer Stichprobe aus den Trainingsdaten wurden Entscheidungsparameter bestimmt. Damit wurden die restlichen Daten der Trainingsmenge klassifiziert und der Kundenwert berechnet. Das Verfahren wurde mit 10 unterschiedlichen Stichproben wiederholt.
Datenbanksysteme 3 Sommer 2003Data Mining - 36Worzyk
FH Anhalt
Ergebnisse
Datenbanksysteme 3 Sommer 2003Data Mining - 37Worzyk
FH Anhalt
Data Mining Cup 2003 Aufgabe
Um zumindest die durch Sichten und Löschen der Spams bei den Mitarbeitern verursachten Kosten zu minimieren, kann man Spam-Filter einsetzen. Diese können entweder bereits auf den Mail-Servern (wie etwa SpamAssassin) arbeiten oder auch in das E-Mail-Programm eines Nutzers integriert sein (ein Beispiel hierfür sind die aktuellen Versionen von Mozilla). Ziel dieser Programme ist eine möglichst gute Erkennung unerwünschter Mails, während erwünschte nicht herausgefiltert werden sollten.
Im Rahmen des Wettbewerbs sollten Verfahren des Data-Mining angewandt werden, um eine möglichst gute Klassifikation in Spams und Nicht-Spams bei den Wettbewerbsdaten zu erreichen.
http://www.dfki.de/~damit/DMC2003/index.html
Datenbanksysteme 3 Sommer 2003Data Mining - 38Worzyk
FH Anhalt
Szenario
Den Teilnehmern des Data-Mining-Cups wurden 8000 Datensätze mit Klassenzugehörigkeit zum Lernen eines Klassifikators zur Verfügung gestellt, sowie 11177 zu klassififizierende Datensätze, deren Klassenzugehörigkeit nur der Jury bekannt war.
Ziel war es, aus diesen 11177 E-Mails möglichst gut alle Spam-Mails herauszufiltern. Die letztendliche Platzierung ergab sich aus der Anzahl der zugestellten Spams (Falsch-Negative), wobei als Nebenbedingung die Anzahl der versehentlich herausgefilterten Nicht-Spams (Falsch-Positive) 1% aller Nicht-Spam-Mails nicht überschreiten durfte. Teilnehmer, die diesen Prozentsatz überschritten, wurden in der Endwertung nicht berücksichtigt.
Die Teilnehmer erhielten jedoch nicht die E-Mails selbst, sondern eine Reihe beschreibender Merkmale, wie sie der Open-Source Spam-Filter Spam Assassin verwendet.
Datenbanksysteme 3 Sommer 2003Data Mining - 39Worzyk
FH Anhalt
Datensichtung
832 MerkmaleID-Anomalie: In hohen ID‘s nur noch
Spam
Datenbanksysteme 3 Sommer 2003Data Mining - 40Worzyk
FH Anhalt
Spam Assassin
SpamAssassin prüft für jede E-Mail zunächst das Vorhandensein einer Reihe von Merkmalen. Dieser Merkmalsvektor entspricht den im Wettbewerb vorliegenden Daten. SpamAssassin ordnet jedem dieser Merkmale eine Gewichtung zu. Merkmale, die eher in Spams anzutreffen sind erhalten ein positives Gewicht, Merkmale, die eher dagegen sprechen, dass es sich um Spam handelt, ein negatives. Die genaue Höhe der Gewichte wird vom Autor des Programms mittels eines genetischen Algorithmus und einer großen Datenbank an E-Mails bestimmt, so dass sich eine möglichst gute Klassifikationsleistung mit diesen Daten ergibt.
Datenbanksysteme 3 Sommer 2003Data Mining - 41Worzyk
FH Anhalt
Verwendete VerfahrenVerfahren
Algorihmus
Klasse in Weka
Entscheidungsbaum (EB) C4.5 weka.classifiers.trees.j48.J48
Naive Bayes (NB) weka.classifiers.bayes.NaiveBa
yes
Methode der nächsten Nachbarschaft (NN)
(weka.classifiers.lazy.IBk)
Support-Vector Maschine (SVM)
SMOweka.classifiers.functions.supp
ortVector.SMO
Logistische Regression (LR) weka.classifiers.functions.Logist
ic
BoostingAdaBoos
tM1weka.classifiers.meta.AdaBoost
M1
Stacking weka.classifiers.meta.Stacking
Datenbanksysteme 3 Sommer 2003Data Mining - 42Worzyk
FH Anhalt
Support-Vektor-Maschinen
Datenbanksysteme 3 Sommer 2003Data Mining - 43Worzyk
FH Anhalt
Data Mining Cup 2004
ZeitplanSofort: Anmeldung15.4. Ausgabe der Aufgabe und der
Daten13.5. Abgabe der Ergebnisse22.6. bis 24.6. Data Mining Cup