Data Warehousing und Mining - 1Klemens Böhm
Vorlesung‘Data Warehousing und Mining’
Kapitel 1: Einleitung
Data Warehousing und Mining - 2Klemens Böhm
Gliederung dieses Kapitels
Motivation für Datenanalyse (und Thema der Vorlesung),Begriffsbildung Data Warehousing,Probleme im Bereich Data Warehousing,Begriffsbildung und Aufzeigen der Probleme im Bereich Data Mining,Zusammenhang Data Warehousing – Data Mining,voraussichtliche Gliederung der Vorlesung.
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 3Klemens Böhm
Gegenwärtige Situation (1)Unternehmen und andere Organisationen haben in der jüngeren Vergangenheit große Datenmengen angehäuft.Genauer: Unterschiedliche Datenbestände in den einzelnen Abteilungen/Unterorganisationen, die die jeweilige Teilaktivität reflektieren; oft hohes Maß an Heterogenität.Daten beschreiben alle Aspekte/alle Aktivitäten der Organisation, da die Verwendung von IT in allen Teilorganisationen stattfindet.
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 4Klemens Böhm
Gegenwärtige Situation (2)Wissen, das in den Daten enthalten/verborgen ist, ist nicht offensichtlich.
Zuviele Attribute, wenn man Gesamtheit der Daten betrachtet.Niemand hat den Überblick über alle Datenbestände.Personelle Zuständigkeiten wechseln, alte Daten werden z.T. ‚uninterpretierbar‘bzw. werden durch ‚Neuinterpretation‘des Schemas verfälscht.
Thema dieser Vorlesung: Wie kommt man in solch einem Szenario mit vertretbarem Aufwand zu verwertbarem Wissen?We are drowning in information, but starving for knowledge! (John Naisbett)
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 5Klemens Böhm
Gegenwärtige Situation (3)Weitere Aspekte, warum Datenanalyse gerade jetzt
sinnvolles und wichtiges Thema ist:Tools für das auto-matisierte Anhäufenvon Daten,Wettbewerbsdruck,billige, aber leistungs-fähige Computer,weit entwickelte theoretische/mathematische Grundlagen
Machine Learning und Logik,Statistik,Datenbank-Systeme.
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 6Klemens Böhm
“The Value Chain”, oder‘Was genau ist Datenanalyse?’
DatenDaten• Kundendaten• Daten aus den Filialen• Demographische Daten• Geographische Daten
InformationInformation• X lebt in Z• S ist Y Jahre alt• X und S sind umgezogen• W hat Geld in Z
WissenWissen• Anzahl Y des Produkts A wird in Gebiet Z verwendet• Kunden der Klasse Y verwenden x% von C in Zeitraum D
EntscheidungEntscheidung• Sonderangebot für Produkt Ain Gebiet Z.• Mailings an Familien mit Profil P• Cross-Selling von Produkt B an Kunden C
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
(Modell von Gianottiund Pedreschi)
Inspektion
Aggregation(zielgerichtet)
Interpretation
Data Warehousing und Mining - 7Klemens Böhm
Auswahl und Preprocessing
Data Mining
Interpretationund Evaluierung
Konsolidierungder Daten
Wissen
p(x)=0.02
Warehouse
Quellen
Muster & Modelle
AufbereiteteDaten
KonsolidierteDaten
Wissensextraktion als Prozeß
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Die ersten drei Phasen sind Bestandteil der Vorlesung.Letzte Phase nicht, da anwendungsspezifisch.
Data Warehousing und Mining - 8Klemens Böhm
Grundsätzliche Problemeund Lösungsansätze
Grundsätzliche Probleme, die Wissensextraktionsprozeß bewältigen muß, sehr abstrakt formuliert:
Identifizierung der relevanten Daten,Repräsentation der Daten,Suche nach geeignetem Modell,
Ansätze:Top-down:Experte hat Hypothese bereits im Kopf,Experte weiß genau, was für eine Analysedurchzuführen ist – Data Warehousing Tools sind hierfür geeignet. (Vorangegangenes Bildbeschreibt den Sachverhalt nicht ganz.)Bottom-up:Herleitung aus den Daten – Mining.
Die Realität liegt zwischen diesen beiden Extremen.
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 9Klemens Böhm
Architektur:
Data Warehousing - Szenario
Source SourceSource
Warehouse
Vertrieb Personal Marketing
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 10Klemens Böhm
Was ist ein Data Warehouse?Repository, das Daten aus unterschiedlichen, meist heterogenen Quellen enthält, Daten sind meist ‘verdichtet’ bzw. aggregiert,Data Warehouse enthält mehrere materialisierteSichten auf den Original-Datenbestand,man strebt an, daß diese Sichten möglichst aktuell sind,Data Warehouse unterstützt üblicherweisemultidimensionales Datenmodellmit entsprechenden Operationen.
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 11Klemens Böhm
Definition von Sichten in SQL –Beispiel (1)
Zugrundeliegende Relation: MGA(Mitarbeiter, Gehalt, Abteilung)
create view MG asselect Mitarbeiter, Gehalt from MGA where Gehalt > 20
View dann im Prinzip verwendbar wie ‚normale‘ Relation, z. B.:select * from MG where Gehalt < 40
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 12Klemens Böhm
Definition von Sichten in SQL –Beispiel (2)
Mitarbeiter Gehalt AbteilungKlemens 60 IPD Erik 30 DKE Holger 15 DKE Gunter 80 DB
MGA
Mitarbeiter GehaltKlemens 60 Erik 30 Gunter 80
MGA
create view MG asselect Mitarbeiter, Gehalt from MGA where Gehalt > 20
select * from MG where Gehalt < 40
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 13Klemens Böhm
Data CubeMarke
Bundesland
DatumHessen
Bayern
Saarland
BMW
Audi
Opel
07.01. 08.01.
52
95
Dimensions:Marke, Datum, Bundesland
Measure: AnzahlMotivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
z.T. intuitiver bezüglich Darstellung und Operationen
Data Warehousing und Mining - 14Klemens Böhm
OLTP vs. OLAPOLTP (‘online transaction processing’): Transaktionsorientierte Datenzugriffe, typischerweise Erfassen von Datenund Lesezugriffe auf diesen.“Tagesgeschäft bedienen”
OLAP (‘on-line analytical processing’): Konsolidierung, Viewing und Analyseder Daten gemäß mehrerer Dimensionen.“Entscheidungen unterstützen”
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 15Klemens Böhm
Data Warehousing –was sind die Probleme?
Welche Datenwerden im Data Warehouse materialisiert?Wie werden Datenim Warehouse aktuell gehalten?Wie sind die Datenim Data Warehouse organisiert?Welche Funktionalität ermöglichenData Warehouses, in Produktenund in Prototypen?
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 16Klemens Böhm
Was ist Data Mining?Menge von Techniken zum Finden typischer Muster im Datenbestand.Genauer gesagt, geht es insbesondereum interessante Muster in großen Datenbeständen,(interessant = 1. für den Benutzer neu, 2. in bezug auf andere Muster, die gefunden werden),Muster haben je nach Problem unterschiedliche Struktur, z.B. Association Rules, Clustering.‘Information Mining’ anstatt‘Data Mining’.
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 17Klemens Böhm
Was genau leistet Data Mining?Es existieren schon relativ lange
vielfältige statistischeVerfahren etc. Probleme, die betrachtet werden, sind die folgenden bzw. Kombination:‘Alle’ Muster, in tendenziellemGegensatz zu Statistik-Tests für konkrete Hypothesen. Effiziente Algorithmen,z.T. mit ungefährenErgebnissen,große Datenbestände, Hauptspeicher ist i.a. nichtausreichend,komplexere Muster,bessere Benutzer-Kontrolle,was ist sinnvoll ausBenutzersicht?
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 18Klemens Böhm
Data Mining vs. StatistikGemäß Jerome Friedman:
sehr große Datenbestände,Probleme vs. Werkzeuge,empirische Validierung,Ideen anstelle von mathematischen Verfahren.
Motivation
Termin-ology DW
Problems
Termin-ology DM
Relationship DW – DM
Lecture
Data Warehousing und Mining - 19Klemens Böhm
Wichtige Data Mining-Problemstellungen
Die wichtigen Problemstellungen sind recht einfach:Finden von Association Rules,Teilproblem: Finden von Frequent Itemsets,zahlreiche Verfeinerungen, z.B.
Quantitative Association Rules,Zeitreihenanalyse,
Clustering,Classification.
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 20Klemens Böhm
Market Basket Analysis –Association Rules
Zusammenhänge zwischen Waren, die Kunden relativ oft in ihren Einkaufswagen legen.
Kunde1Kunde2 Kunde3
Milch, Ei, Zucker, Brot
Milch, Ei, Fleisch, Brot Ei, Zucker
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 21Klemens Böhm
ClusteringIdentifizieren von Gruppen von Items,die nahe beieinanderliegen;Beispiel: Kundengruppen.
Bier
Wein0
xxx
x xx
xxx
x xx
xxx
x xx
xxxx
xxx xxxxxx
x
x
x
x
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 22Klemens Böhm
ClassificationZiel: Item hat mehrere Attribute, man will anhand der Werte von n Attributenden (n+1)-ten vorhersagen.Grundlage für Voraussage: Menge von Tupeln (Trainingsmenge), für die alle n+1 Werte bekannt sind.Beispiel:
Attribute 1, …, n: Alter, Einkommen, Beruf, …Attribut n+1: KreditwürdigkeitInformation, die i.d.R. erst später bekannt wird.
Ein mögliches Vorgehen: Entscheidungsbaum aufbauen.
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 23Klemens Böhm
Data Warehousing vs. Data Mining Data Warehousing Data Mining Bedeutung des Begriffs
eher Infrastruktur (es gibt aber auch ausgefeilte Algorithmen für die Wartung des Data Warehouses)
eher Algorithmen
Schwierigkeit eher einfache Operationen, und Implementierung in einer gegebenen Infrastruktur ist i.d.R. relativ naheliegend
relativ einfache Problemstellungen, aber es werden z.T. recht ausgefeilte Lösungen vorgeschlagen.
Schärfe des Begriffs
relativ klar umrissener Begriff Gebiet der Informatik, das mit anderen Gebieten ‚konkurriert’, z.B. Machine Learning, Statistik, neuronale Netze, und Abgrenzung ist manchmal schwierig.
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 24Klemens Böhm
Anwendungsgebiete und ChancenMarketing: Segmentierung, Customer Targeting,Finanzbereich: Portfolio Management, Identifizierung von Investitionsmöglichkeiten, Banken und Versicherungen: Kredit- und Versicherungswürdigkeit,Security: Fraud Detection,Wissenschaft und Medizin: Entdecken von Hypothesen, Vorhersagen, Diagnostik,Industrie: Prozeßmodellierung, Qualitätskontrolle, Resource Allocation,Engineering: Simulation und Analyse, Mustererkennung, Signalverarbeitung,Internet: Effektivere Suchmaschinen, Web-Marketing.
D.h. (1) alle Lebensbereiche, (2) auch solche, mit denenman Geld verdienen kann.
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 25Klemens Böhm
Voraussichtliche Gliederung der Vorlesung (1)
EinleitungMotivation, Indices und SichtenSchnelles Einfügen in Indexstrukturen, Adaptionen materialisierter Sichten,Data Warehousing – ArchitekturaspekteOLAP vs. OLTP, Referenzarchitektur,Vom relationalen zum multidimensionalen ModellAttribute vs. Dimensionen, Data Cube, Operationen auf dem Data Cube,Datenqualität Data Cleansing, Äquivalenz, Sorted-Neighborhood Methode, Active Learning,Physischer EntwurfBitmap Indices, Small Materialized Aggregates, Prefix Sum Arrays, Materialisierungsalternativen für den Data Cube,
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 26Klemens Böhm
Voraussichtliche Gliederung der Vorlesung (2)
Deklarativer Zugriff auf den Data Cube (MDX)Basiskonstrukte; Slicing und Filtering; Weiterführende Konstrukte: Abgeleitete Members, hierarchisches Navigieren,Berechnung und Maintenance des Data CubesAusnutzung der Abhängigkeiten zwischen Sichten für effiziente Berechnung, Zwei-Phasen Modell für Updates, Dimension Updates,Komprimierung des Data Cubes, approximative ErgebnisseJoin Synopsen, Wavelet-basierte Komprimierung,Exploration des Data Cubes
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 27Klemens Böhm
Voraussichtliche Gliederung der Vorlesung (3)
Association RulesFrequent Itemsets vs. Association Rules, Support und Confidence, Apriori, Sampling, FP-Trees,‚Erweiterte‘ Association RulesMulti-Level Association Rules, Querysprachen für Data Mining,Quantitative ZusammenhängeQuantitative Association Rules, Optimized Association Rules,Weitere Mining-Probleme und LösungenInteressantheit, Korrelation, Strongly Collective Itemsets, Skyline Operator,
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 28Klemens Böhm
Voraussichtliche Gliederung der Vorlesung (4)
ClassificationProblemstellung und Begriffsbildung, Entscheidungsbäume als ein mögliches Verfahren, Optimierungen für große Datenbestände,ClusteringÜbersicht über die Verfahren, Hierarchisches Clustering, Clustering in hochdimensionalen Merkmalsräumen,Outlier DetectionÜbersicht über die Verfahren, Outlier Detection in hochdimensionalen Merkmalsräumen,Zeitreihenanalyse, ForecastingData Mining und Privatheit
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 29Klemens Böhm
AcknowledgementsFolien dieser Vorlesung stammen z.T.
aus folgenden Quellen:Fosca Gianotti, Dino Pedreschi, CNR, Pisa, Italien(insbesondere Abbildungen zu Data Mining),Vorträge der Teilnehmer der Seminare‘Data Warehousing und Mining’ an der ETH Zürichim WS 1998/99 und 1999/2000(‘durch die Bank’ Folien sowohl zu Warehousing als auch zu Mining).
Motivation
Begriffe DW
Probleme
Begriffe DM
Zs.hang DW – DM
Vorlesung
Data Warehousing und Mining - 30Klemens Böhm
EntropieEntropie einer Menge gibt an, wie zufällig die Daten in einer Menge verteilt sind (bzw. wie zufällig die Ausprägung eines Attributs in einer Menge von Objekten ist), auch Maß für die Unordnung.
Definition:
pj – relative Häufigkeit der Klasse j in S.Entropie ist minimal, wenn p1=1; maximal, wenn pi=pj.
∑ ⋅−=j
jj ppSE log)(
Entropie
MDL
Index-strukturen
Data Warehousing und Mining - 31Klemens Böhm
Modelle und StatementsModell: M, Statement: xBeispiel 1:
M – irgendeine konkrete Wettervorhersage,x = “Heute scheint die Sonne, kein Regen.”
Beispiel 2:M – Classifier für Kreditwürdigkeit,x = “Klemens ist kreditwürdig.”, “Gunter ist nichtkreditwürdig.”, “Klaus ist nicht kreditwürdig.”, usw.
Entropie
MDL
Index-strukturen
Data Warehousing und Mining - 32Klemens Böhm
Beziehung zwischenModell und Statement
Beispiel :x = “Heute scheint die Sonne, kein Regen.”M – irgendeine konkrete Wettervorhersage,
Wenn x mit M übereinstimmt, kann man Kodierungvon x kurz halten (“Wetter wie vorhergesagt”).Ansonsten muß man mehr sagen.Bei schlechten Wettervorhersagenmuß man i.a. mehr sagen, wenn man das aktuelle Wetter in Abhängigkeitvon der Vorhersage beschreiben will. Gibt es allgemeinen Zusammenhangzwischen Länge des Statements und dem Modell?
Entropie
MDL
Index-strukturen
Data Warehousing und Mining - 33Klemens Böhm
Theorem zum CodierungsaufwandInformationstheoretisches Theorem (Shannon).Sei x eine Aussage. Sei M ein Modell. Wieviele Bits sind ausreichend, um x in M zu codieren? D.h. um x in Abhängigkeit von M zu formulieren?Gemäß Theorem sind es –log Pr[x|M] Bits.(Pr[x|M] – Wahrscheinlichkeit, daß x eintritt, gegeben Modell M.) (log1=0, log0=-∞)Beispiel:
x=“Heute scheint die Sonne, kein Regen.”– tatsächliches Wetter –M=irgendeine konkrete Wettervorhersage.
Entropie
MDL
Index-strukturen
Data Warehousing und Mining - 34Klemens Böhm
Minimum Description Length (1)
Welche Form der Wettervorhersage ist adäquat?Wie kodieren wir ‚Glatteis-Warnung‘?
‚Glatteis-Bit‘,Freitext-Feld enthält Glatteis-Information.
Was ist besser? Wetter in Stockholm,Wetter in Kairo.
Entropie
MDL
Index-strukturen
Data Warehousing und Mining - 35Klemens Böhm
Minimum Description Length (2)
Wir wollen mehrere Aussagen machen. Zwei grundsätzliche Alternativen:1.Ausgefeiltes Modell,
Aussagen kann man dann kurz halten.2.Primitives Modell,
Aussagen tendenziell umständlicher.Was ist besser? Minimum Description Length (MDL) Prinzip: Länge der Beschreibung des Modellsplus Länge der Beschreibung der Aussagensollte minimal sein.
Entropie
MDL
Index-strukturen
Data Warehousing und Mining - 36Klemens Böhm
Index – Illustration (1)Erläuterung:
Seitenweise Anordnung der Daten.Daten müssen im Hauptspeicher vorliegen, damit Selektion etc. durchgeführt werden kann.Seiten – Einheiten des Zugriffs.Laden einer Seite in den Hauptspeicher ist teuer, Zugriffslücke.
Entropie
MDL
Index-strukturen
Data Warehousing und Mining - 37Klemens Böhm
Index – Illustration (2)Student(name, age, gpa, major); t(Student) = 16.Non-clustered primary B+-tree für Attribut gpa.
Lam, 22, 2.8, MEMary, 24, 3, ECEKathy, 18, 3.8, LSKane, 19, 3.8, MEBob, 21, 3.7, CS
Chang, 18, 2.5, CS Vera, 17, 3.9, EELouis, 32, 4, LS
Martha, 29, 3.8, CS
James, 24, 3.1, ME
Pat, 19, 2.8, EE
Chris, 22, 3.9, CSTom, 20, 3.2, EE
Leila, 20, 3.5, LS Shideh, 16, 4, CS
(3.9, (4,2))(4, (4,3))
(3.9, (4,1))
(4, (4,4))
(3.7, (1, 3))(3.8, (3,2))(3.8, (3,3))(3.8, (3,4))
(2.3, (2, 3))(2.5, (1,2))(2.8, (1,4))
(3.1, (2,2))(3.2, (1,1)
(2.8, (3,1))
(3, (2,1))
(3.5, (2,4))
3.6
Chad, 28, 2.3, LS
Entropie
MDL
Index-strukturen
Data Warehousing und Mining - 38Klemens Böhm
Index – ErläuterungenIndex für mehrere Attribute möglich.Index für (gpa, name) nicht dasselbe wie für (name, gpa).Man kann Index nachträglich anlegen;man kann Index wieder löschen, ohne die Daten selbst zu löschen.Index ist Bestandteil der physischen Ebene. Index-Definition ist Bestandteil des internen Schemas.
Entropie
MDL
Index-strukturen
Data Warehousing und Mining - 39Klemens Böhm
Räumliche Indexstrukturen –Motivation
DatenraumDatenraum
Motivation: Grüne Punkte: Bars, die Ihr bevorzugtes Bier ausschenken.Punkte enthalten in Relation Bar(X, Y, Name).Stern: Dein Standort.Welche Bar ist am nächsten?
Offensichtliche Lösung:Relation scannen, Abstand jedes Tupelsberechnen.
Entropie
MDL
Index-strukturen
Data Warehousing und Mining - 40Klemens Böhm
kDB-Baum
NN-Distanz, NN-Sphäre,Einsparung: Nur ein paar Rechtecke inspizieren.
x
y (6, --)
(--, 6) (--, 4)
(4, --) (3, --)
(--, 2)
(x, y)
600
6
4 AnfrageAnfrage
DatenraumDatenraumkDBkDB--BaumBaum
Tiefe des Baums nur abhängig von Anzahl
der Datenobjekte. Entropie
MDL
Index-strukturen
Data Warehousing und Mining - 41Klemens Böhm
kDB-Baum
1. [(6, --)]; ∞2. [(--, 4), (--, 6)]; ∞3. [ , , (--, 6)]; ∞
x
y (6, --)
(--, 6) (--, 4)
(4, --) (3, --)
(--, 2)
(x, y)
600
6
4 AnfrageAnfrage
DatenraumDatenraumkDBkDB--BaumBaum
1. [ , (--, 6)]; 22. [(--, 6)]; 1.53. Ende Algorithmus. k-NN
Entropie
MDL
Index-strukturen
Data Warehousing und Mining - 42Klemens Böhm
R-Baum
DatenraumDatenraum
RR--BaumBaum
WurzelWurzel
AnfrageAnfrage
Entropie
MDL
Index-strukturen