Vorlesung ‘Data Warehousing und Mining’ Kapitel 1: Einleitung file• Mailings an Familien mit Profil P • Cross-Selling von Produkt B an Kunden C Motivation Begriffe DW Probleme

Data Warehousing und Mining - 1Klemens Böhm

Vorlesung‘Data Warehousing und Mining’

Kapitel 1: Einleitung


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


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


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


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


“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


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.


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


Architektur:

Data Warehousing - Szenario

Source SourceSource

Warehouse

Vertrieb Personal Marketing

Motivation

Begriffe DW

Probleme

Begriffe DM

Zs.hang DW – DM

Vorlesung


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


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


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 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


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 –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


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


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 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


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


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


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


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 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


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


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



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



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



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


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


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


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


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


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


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


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


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


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


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


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


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


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


R-Baum

DatenraumDatenraum

RR--BaumBaum

WurzelWurzel

AnfrageAnfrage

Entropie

MDL

Index-strukturen

Documents

Vorlesung ‘Data Warehousing und Mining’ Kapitel 1: Einleitung file• Mailings an Familien mit Profil P • Cross-Selling von Produkt B an Kunden C Motivation Begriffe DW Probleme