Data Warehousing und Mining: DB-Support für Data Mining – 1Klemens Böhm

Kapitel 19:Datenbank-Unterstützung

für Datenanalyse

Data Warehousing und Mining: DB-Support für Data Mining – 2Klemens Böhm

Datenbank-Unterstützung für Data Mining

Unterschiedliche Ebenen:Erweiterung des Datenbank-Kerns(„Datenbank-Primitive“),Erweiterungen der Anfragesprache,unmittelbare Benutzerunterstützung.

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 3Klemens Böhm

Datenbank-Primitive für Datenanalyse und Knowledge Discovery

Welche Unterstützung sollte Datenbank-Kern für Datenanalyse bieten?Gemeint ist nicht:

Welche objekt-relationalen Erweiterungen sind denkbar/sinnvoll?Wie sollte Informationsbedürfnis in SQL formuliert sein?Welche Optimierungen bei der Queryoptimierung?

Kapitel orientiert sich an NonStop SQL/MX von Tandem/Compaq.

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 4Klemens Böhm

Auswahl der PrimitiveDatenanalyse in unterschiedlicher Weise ‚auf unterschiedlichen Ebenen‘ implementierbar (Client-seitig, Standard SQL, Stored Procedures, O-R Erweiterungen, neue Primitive etc.)

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 5Klemens Böhm

Auswahl der Primitive (1)Kriterien, wann Feature als Datenbank-Primitiv realisiert sein sollte:

1. Allgemeinheit: Unterstützung mehrerer Algorithmen und Knowledge-Discovery Arbeitsschritten? Anwendungsunabhängigkeit?

2. Kompatibilität mit relationalem Modell: Beispiel – ist das Ergebnis natürlicherweise eine Relation?

3. Integrationsgrad: Deutlich verbesserte Ausdrucksmächtigkeit und Performanz?

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 6Klemens Böhm

Auswahl der Primitive (2)Kriterien, wann Feature als Datenbank-Primitiv realisiert sein sollte (Forts.):

4. Kontrolle: Sind Anwendungsentwickler und Anbieter von Tools bereit, die Operation der Datenbank zu überlassen?

5. Ausgereiftheit und Stabilität: Sind in naher Zukunft Weiterentwicklungen dieses Features zu erwarten?

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 7Klemens Böhm

Primitive in SQL/MXTransposition.Mehrere Frequency Countsund Abzählen anderer Abhängigkeiten in einem Statement.Sampling.Unterscheidungen wurden bereits angesprochen.Sequence-Funktionen.Vergleichbar mit MDX-Funktionalität.Primitive für den physischen Entwurf.Nichts Spezielles, z. B.

Vertikale Partitionierung,Horizontale Partitionierung,kompakte Darstellung von Attributen mit kleinem Wertebereich.

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 8Klemens Böhm

Transposition (1)Beispiel: Wir wollen Tabelle mit Anzahl Vorkommen jedes Attributwerts, für alle Attribute.Mögliches Vorgehen:SELECT ACCT_STATUS, COUNT(*)FROM CUSTOMER GROUP BY ACCT_STATUS;SELECT GENDER, COUNT(*)FROM CUSTOMER GROUP BY GENDER; ...

Viele Scans(nur vermeidbar mit Multi-Query Optimierung).

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 9Klemens Böhm

Transposition (2)Alternative: Verwendung des TRANSPOSE-Operators.TRANSPOSE erzeugt aus einem Tupelmehrere mit unterschiedlichem Inhalt.Ausgangsrelation und Ergebnis von TRANSPOSE –Illustration:

ACCT_ STATUS

GENDER AGE

ok M 32 ok M 29

overdrawn F 32 ok F 59

ATTR_ ID

ATTR_ VAL

1 ok 2 M 1 ok 2 M

...

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

ACCT_STATUS → 1, GENDER → 2, …

Data Warehousing und Mining: DB-Support für Data Mining – 10Klemens Böhm

Transposition (3)Beispiel:SELECT ATTR_ID, ATTR_VAL, COUNT(*)FROM CUSTOMERTRANSPOSE(1, ACCT_STATUS),

(2, GENDER), ...AS (ATTR_ID, ATTR_VAL)

GROUP BY ATTR_ID, ATTR_VALORDER BY ATTR_ID, ATTR_VAL;

Ausgangsrelation und Ergebnis von TRANSPOSE:

ACCT_ STATUS

GENDER AGE

ok M 32 ok M 29

overdrawn F 32 ok F 59

ATTR_ ID

ATTR_ VAL

1 ok 2 M 1 ok 2 M

...

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 11Klemens Böhm

Transposition – weiteres Beispiel (1)Ausgangsrelation:

Ziel-Tabelle (nützlich z. B. für Klassifikation):

(Spalte 1 für Typ string, Spalte 2 für int;Unterscheidung durch zusätzliches Attribut.DV – Abkürzung für dependent variable,IV – independent variable)

GENDER AGE #CHILDREN STATUS M 31 0 S M 28 0 S M 61 3 M M 56 0 S

CTNUMBER IV1 IV2 DV COUNT 1 M – S 3 1 M – M 1 2 – 31 S 1 2 – 28 S 1

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 12Klemens Böhm

Transposition – weiteres Beispiel (2)Zwischenergebnis nach Transposition:

Hier noch einmal Ausgangsrelation:

CTNUMBER IV1 IV2 STATUS 1 M – S 2 – 31 S 3 – 0 S 1 M – S 2 – 28 S 3 – 0 S

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß GENDER AGE #CHILDREN STATUS M 31 0 S M 28 0 S M 61 3 M M 56 0 S

Data Warehousing und Mining: DB-Support für Data Mining – 13Klemens Böhm

Transposition – weiteres Beispiel (3)Anfrage:SELECT CTNUMBER, IV1, IV2, DV, COUNT(*)FROM MINING_DATATRANSPOSE (1, GENDER, NULL, STATUS),

(2, NULL, AGE, STATUS),(3, NULL, NUM_CHILDREN, STATUS)AS (CTNUMBER, IV1, IV2, DV)

GROUP BY CTNUMBER IV1, IV2, DVORDER BY CTNUMBER IV1, IV2, DV

Zwischenergebnis nach Transposition:CTNUMBER IV1 IV2 STATUS

1 M – S 2 – 31 S 3 – 0 S 1 M – S 2 – 28 S 3 – 0 S

...

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 14Klemens Böhm

Sampling (1)Schnelle ungefähre Resultate.Aus Performancegründen sinnvoll, Samplingin den Datenbank-Kern ‚hineinzudrücken‘.Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 15Klemens Böhm

Sampling (2)Beispiele:

SELECT ATTR_ID, ATTR_VAL, COUNT(*)FROM CUSTOMERSAMPLE RANDOM 1 PERCENTTRANSPOSE (1, ACCT_STATUS), (2, GENDER), ... AS (ATTR_ID, ATTR_VAL)GROUP BY ATTR_ID, ATTR_VALORDER BY ATTR_ID, ATTR_VAL;

SELECT * FROM CUSTOMERSAMPLE RANDOM BALANCEWHEN GENDER='M' THEN 150 PERCENTWHEN GENDER='F' THEN 100 PERCENT

END;

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 16Klemens Böhm

Sampling (3)SAMPLE-Klausel kann an unterschiedlichen Stellen der Query plaziert werden.Weitere mögliche Verfeinerungen:

Methode: Random, First-N, periodisch;Größe des Samples: Absolute oder relative Angabe.

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 17Klemens Böhm

Sequence Funktionen (1)Ähnlichkeit mit MDX-Funktionen, die Einschränkung auf bestimmte Zeit-Fenster bieten.Beispiel:SELECT ACCOUNT, HISTORY_MONTH,

MOVINGAVG(BALANCE, ROWS SINCE(THIS(ACCOUNT) <> ACCOUNT), 3)FROM CUSTOMER_ACCOUNT_HISTORYSEQUENCE BY ACCOUNT, HISTORY_MONTH;

Zugrundeliegende Relation CUSTOMER_ACCOUNT_HISTORY(ACCOUNT, HISTORY_MONTH, BALANCE)

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 18Klemens Böhm

Sequence Funktionen (2)Erläuterungen:

Zugrundeliegende Relation CUSTOMER_ACCOUNT_HISTORY(ACCOUNT, HISTORY_MONTH, BALANCE)Ergebnis:

Durchschnittsberechnung – entweder drei Monate oder weniger, wenn Account noch nicht solange existiert.

ACCOUNT HISTORY_ MONTH

AVG

Einleitung

DB-Primitive

- Einleitung

- Transpos.

- Sampling

- Sequence-F.

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 19Klemens Böhm

DiskussionBis hierhin:

Was für Kriterien dafür, daß Feature Teil des DB-Kerns sein sollte?Vorstellung entsprechender Features.Features, die zum Großteil bereits besprochenwurden. Verständnis scheint zu konvergieren.Funktionalität, die für Data Mining nützlich ist.Keine ‘unmittelbare’ Mining Funktionalität.

Im Folgenden:Mining Funktionalität (hier: Klassifizierung).Erweiterung der Anfragesprache.

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 20Klemens Böhm

Ad Hoc Queries mit Mining PrädikatenVorhersagemodell – Mining Modell für Vorhersagen, z. B. Classifier.SQL Erweiterungen für Erstellung und Anwendung von Vorhersagemodellen heute Bestandteil kommerzieller RDBMSe.Anfragen möglich, die Mining Prädikate enthalten.Beispiel:„Selektiere alle Personen, die www.ipd.uka.de letzte Woche besucht haben, und die als Fußball-interessiert einklassifiziert werden.“

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 21Klemens Böhm

Code Beispiel: MS SQL Server 2000 (1)CREATE MINING MODEL Risk_Class

// Name of Model(Customer_ID LONG KEY, // source columnGender TEXT DISCRETE, // source columnRisk TEXT DISCRETE PREDICT,

// prediction columnPurchases DOUBLE DISCRETIZED(),

// source columnAge DOUBLE DISCRETIZED, // source column)USING [Decision_Trees_101]

// Mining Algorithm

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 22Klemens Böhm

Code Beispiel: MS SQL Server 2000 (2)Erläuterungen:

Erstellung des Mining Modells in SQL,Modell muß trainiert werden (hier nicht dargestellt);funktioniert mit INSERT INTO.

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 23Klemens Böhm

Code Beispiel: MS SQL Server 2000 (3)Prediction Join:

Prediction Join von Daten und Modell liefert Vorhersage.Beispiel:SELECT D.Customer_ID, M.RiskFROM [Risk_Class] MPREDICTION JOIN(SELECT Customer_ID, Gender, Age, sum(Purchases) as SP FROM Customers D GROUP BY Customer_ID, Gender, Age) as DON M.Gender = D.Genderand M.Age = D.Ageand M.Purchases = D.SPWHERE M.Risk="low"

Alle source columns des Modells kommen in der anderen Relation vor.

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 24Klemens Böhm

Code Beispiel: MS SQL Server 2000 (4)Herkömmliche Evaluierung der Anfrage in zwei Phasen:

1. Ermittlung aller Datenobjekte mit allen relevanten ‚physischen‘ Eigenschaften.

2. Anwendung des Mining Modells auf alle Datenobjekte nacheinander.

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 25Klemens Böhm

Evaluierung von Anfragenmit Mining Prädikaten

Beispiel von vorhin:„Selektiere alle Personen, die www.ipd.uka.de letzte Woche besucht haben, und die als Fußball-interessiert einklassifiziert werden.“Fußballfans sind vielleicht nur sehr kleiner Teilder Besucher von www.ipd.uka.de.Anwendung des Mining Prädikats für den effizienten Zugriff.Ansatz: Einfacheres Prädikat herleiten; Algorithmus hierfür ist Modell-spezifisch.Upper envelope– auf diese Weise hergeleitetes Prädikat.

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 26Klemens Böhm

Upper Envelopes für Decision Trees (1)Illustration:

Anfrage: „Selektiere alle Personen, die α erfüllen,und für die Klasse 1 vorhergesagt wird.“Upper Envelope von Klasse 1 ist „((lower BP > 91) AND (age > 63) AND (overweight)) OR ((lowerBP > 91) AND (upper BP > 130))“.

Lower BP > 91

Age > 63 Upper BP > 130

Overweight? 2 1 2

1 2

yes no

yes no yes no

yes no

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 27Klemens Böhm

Upper Envelopes für Decision Trees (2)Beispiel, fortgesetzt:

Anfrage, die zur Ausführung kommt: Selektiere alle Personen, die α erfüllen,und (((lower BP > 91) and (age > 63) and (overweight)) or ((lowerBP > 91) and (upper BP > 130)))

Lower BP > 91

Age > 63 Upper BP > 130

Overweight? 2 1 2

1 2

yes no

yes no yes no

yes no

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 28Klemens Böhm

Upper Envelopes für Decision Trees (3)Für Entscheidungsbäume ist Upper Envelope exakt.

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 29Klemens Böhm

Upper Envelopes für Decision Trees (4)Beispiel, fortgesetzt:

Was geschieht mit Anfrage „Selektiere alle Personen, die β erfüllen,und für die Klasse 2 vorhergesagt wird“?Wie sieht Upper Envelope aus?

Lower BP > 91

Age > 63 Upper BP > 130

Overweight? 2 1 2

1 2

yes no

yes no yes no

yes no

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 30Klemens Böhm

Upper Envelopes – ErläuterungenAlgorithmus für Entscheidungsbäume ist einfach:Für jeden Pfad von Wurzel zu Blatt in der Klasse Bedingungen verUNDen, und resultierende Bedingungen mit ODER verknüpfen.Andere, kompliziertere Algorithmen für andere Classifier.Effektivität hängt von folgenden Faktoren ab:

Ist Upper Envelope für breite Vielfalt von Mining Modellen herleitbar? (Ja.)‚Tightness‘ der Upper Envelopes, zumindest wenn ursprüngliches Mining Prädikat selektiv ist. (Ja.)

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 31Klemens Böhm

IllustrationScreenshots Data-Mining Features MS SQL Server.Clustering und Klassifikation als Vorhersagemodelle.Wizards zur Erstellung der erweiterten SQL-Statements; GUI zur Visualisierung der Mining-Ergebnisse.

Data Warehousing und Mining: DB-Support für Data Mining – 32Klemens Böhm

Upper Envelopes – ErläuterungenAlgorithmus für Entscheidungsbäume ist einfach:Für jeden Pfad von Wurzel zu Blatt in der Klasse Bedingungen verUNDen, und resultierende Bedingungen mit ODER verknüpfen.Andere, kompliziertere Algorithmen für andere Classifier.Effektivität hängt von folgenden Faktoren ab:

Ist Upper Envelope für breite Vielfalt von Mining Modellen herleitbar? (Ja.)‚Tightness‘ der Upper Envelopes, zumindest wenn ursprüngliches Mining Prädikat selektiv ist. (Ja.)

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 33Klemens Böhm Data Warehousing und Mining: DB-Support für Data Mining – 34Klemens Böhm

Data Warehousing und Mining: DB-Support für Data Mining – 35Klemens Böhm Data Warehousing und Mining: DB-Support für Data Mining – 36Klemens Böhm

Data Warehousing und Mining: DB-Support für Data Mining – 37Klemens Böhm Data Warehousing und Mining: DB-Support für Data Mining – 38Klemens Böhm

Data Warehousing und Mining: DB-Support für Data Mining – 39Klemens Böhm z Data Warehousing und Mining: DB-Support für Data Mining – 40Klemens Böhm

Data Warehousing und Mining: DB-Support für Data Mining – 41Klemens Böhm Data Warehousing und Mining: DB-Support für Data Mining – 42Klemens Böhm

Data Warehousing und Mining: DB-Support für Data Mining – 43Klemens Böhm Data Warehousing und Mining: DB-Support für Data Mining – 44Klemens Böhm

Data Warehousing und Mining: DB-Support für Data Mining – 45Klemens Böhm Data Warehousing und Mining: DB-Support für Data Mining – 46Klemens Böhm

DiskussionData Mining ist Ablauf, bestehend aus mehreren Schritten

Data Cleaning,in Abhängigkeit vom Ergebnis Erstellung weiterer, anderer Modelle,gleichzeitige Erstellung mehrerer unterschiedlicher Modelle;explizite Kontrolle über verwendete Techniken,Optimierung des Ablaufs.

Einleitung

DB-Primitive

DB-Einbett.

Illustration

Schluß

Data Warehousing und Mining: DB-Support für Data Mining – 47Klemens Böhm

Prüfungsfragen, beispielhaft<Kriterien für die Entscheidung, ob ein Feature als Datenbank-Primitiv vorhanden sein sollte, erklären können.>Geben Sie Beispiele für Features, die sich gut als Datenbank-Primitiv eignen. Erklären Sie, warum das so ist.Was ist ein Upper Envelope in unserem Kontext?Was bedeutet die Aussage ‚Ergebnis des Clusteringkann als Vorhersagemodell dienen‘?

Data Warehousing und Mining: DB-Support für Data Mining – 48Klemens Böhm

LiteraturJohn Clear et al.: NonStop SQL/MX Primitives for Knowledge Discovery.Proceedings of the fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1999.http://doi.acm.org/10.1145/312129.312309Surajit Chaudhuri, Vivek R. Narasayya, Sunita Sarawagi: Efficient Evaluation of Querieswith Mining Predicates. ICDE 2002.http://citeseer.ist.psu.edu/chaudhuri02efficient.html