DATA MINING

Steffen Thomas 96I

Allgemein:

• Suche in riesigen Datenbanken

• Finden interessanter Trends oder Muster

• diese können auch unerwartet sein

• soll zukünftige Entscheidungen

vereinfachen

Inhalt:1 Grundlagen des Data Mining

2 Finden von zusammengehörigen Daten

3 Generierung von Regeln

4 Regeln in Form von Bäumen

5 Clustering

6 Ähnlichkeitssuche über Sequenzen

7 Weitere DataMining-Aufgaben

8 Darwin

1 Grundlagen des Data Mining

• verwandt mit der Erforschenden Daten-Analyse und der KI

• Ideen dieser Gebiete auf Data Mining anwendbar

• wichtigster Unterschied: Größe der Datenmengen

• neues Kriterium:

- Algorithmen müssen skalierbar sein

- d.h. linearer Anstieg der Rechenzeit

Grundlagen

• in der Realität enthalten Daten Rauschen und Lücken

• herkömmliche Methode wie SQL-,OLAP-Queries reichen nicht aus

• der KDD-Prozess (Knowledge Discovery Process)data selection: identifizieren des Zieldatensatzes

data cleaning: Beseitigung unnötiger Information

Vereinheitlichung von Feldwerten

Erzeugen neuer Felder

data mining: Extrahieren der vorhandenen Muster (patterns)

evaluation: visuelle Ausgabe der Ergebnisse

2 Zusammengehörige Daten

• Ausgangspunkt: Probleme wie Warenkorb-Analyse

• Warenkorb ist Sammlung von Artikeln eines einzelnen

Einkaufs

• Ziel: finde Artikel, welche zusammen gekauft werden

dadurch bessere Platzierung und Werbung

möglich

• itemset: Satz unterschiedlicher Artikel

• support: Anteil eines itemsets (%)

– BSP:

itemset {pen,ink} mit support von 75%

{milk,juice} 25%

d.h. Milch und Saft werden nicht sehr häufig zusammen gekauft

• frequent itemsets: alle itemsets mit support über einer

bestimmten Schranke (minsup)

• relativ wenig, besonders bei steigender Datenmenge

Zusammengehörige Daten

2.1 Frequent Itemsets

Algorithmus:• beruht auf einer Eigenschaft von frequent itemsets• a priori Eigenschaft: jede Unterteilung eines frequent

itemsets ist ebenfalls ein frequent itemset

foreach Artikel // Level 1 prüfe ob dieser frequent itemset ist // Artikel >minsup vorhanden

k = 1repeat

foreach frequent itemset Ik mit k Artikeln // Level k+1generiere alle itemsets Ik+1 mit k+1 Artikeln

scanne alle Transaktionen einmal und prüfe obdie generierten k+1 itemsets frequent sindk = k+1

until keine neuen frequent itemsets gefunden werden

Zusammengehörige DatenFrequent Itemsets

Ein Beispiel: minsup = 70%

erste Iteration(Level 1):

gefunden werden {pen},{ink},{milk}

zweite Iteration(Level 2):

neue Kandidaten sind {pen,ink},{pen,milk},{pen,juice},{ink,milk},{ink,juice},{milk,juice}

nach dem Scannen bleiben folgende frequent itemsets übrig

{pen,ink},{pen,milk}

dritte Iteration(Level 3):

Kandidaten sind {pen,ink,milk},{pen,ink,juice},{pen,milk,juice}

keiner der Kandidaten ist frequent, sie werden verworfen

• Verbesserung der Laufzeit durch Anwendung der a priori Eigenschaft

Zusammengehörige DatenFrequent Itemsets

2.2 Iceberg Queries

• wenig Resultate, auch bei goßen Datenbasen

• Anfrage in SQL (Bsp.):

SELECT P.custid,P.item,SUM (P.qty)

FROM Purchase P

GROUP BY P.custid,P.item

HAVING SUM (P.qty) > 5

• iceberg queries nutzen die selbe bottom-up Strategie wie frequent itemsets

• ebenfalls Performance-Gewinn durch a priori Eigenschaft

Zusammengehörige Daten

3 Generierung von Regeln

• wichtige Muster in Datenbasen sind Regeln

• effektive Beschreibung der Daten

• es existieren vielfältige Formen von Regeln

• ebensoviele Algorithmen

3.1 Association Rules

• haben die Form LHS => RHS ; LHS,RHS sind itemsets BSP: {pen} => {ink}

• sprachlich: “Wenn bei einem Einkauf ein Füller gekauft wird, so ist es wahrscheinlich, dass auch gleichzeitig Tinte gekauft wird.”

• support: ist der support für ein itemset LHS RHS im BSP: support {pen,ink} = 75%

• confidence(Vertrauen): verdeutlicht die Stärke einer Regel ergibt sich aus sup(LHS) / sup(LHS RHS) im BSP: 75% der Transaktionen die {pen} enthalten

enthalten auch {ink}

Generierung von Regeln

3.2 Ein Algorithmus zum Finden von Association Rules

• Gegeben: minsup, minconf

• Ausgangspunkt sind frequent itemsets > minsup

– X ist frequent itemset mit support sX

– X wird in LHS und RHS zerlegt

– confidence von LHS => RHS ist sX/sLHS

– alle Regeln mit confidence > minconf werden akzeptiert

• der Aufwand zur Generierung von Regeln ist relativ gering

Generierung von Regeln

3.3 Association Rules und ISA Hierarchien

• itemsets können oft auch in Hierarchien auftreten

• dadurch können Beziehungen von Artikeln auf unterschiedlichem Level erkannt werden

Stationary Beverage

Pen Ink Juice Milk

• BSP: support von {ink,juice} = 50%

jetzt juice = beverage

support von {ink,beverage} = 75%

• der support eines Artikels kann nur steigen, wenn dieser Artikel durch einen Vorgänger in der Hierarchie ersetzt wird

Generierung von Regeln

3.4 Allgemeine Association Rules

• Association Rules meist im Zusammenhang mit Warenkorb-Analyse• kann aber allgemeiner aufgefasst werden• bei Sortierung nach anderen Merkmalen können Regeln gefunden

werden, die anders interpretiert werden müssen

Bsp: Sortierung nach custid

Regel: {pen} => {milk}

support = confidence = 100%

bedeutet:”Wenn ein Käufer einen Füller kauft, so kauft er wahrscheinlich auch Milch.”

• ebenso Sortierung nach Datum usw. möglich

Generierung von Regeln

• Sortierung nach Datum wird auch als kalendrische Warenkorb-Analyse bezeichnet

• ein Kalender ist dabei Gruppierung von Daten:

z.B.: jeder Sonntag im Jahr 1999

jeder Erste des Monats• durch Spezifizierung von interessanten Kalendern, können Regeln

entdeckt werden, die in der gesamten Datenbasis nicht auffallen würden u.ä.

BSP: Regel: pen => juice

allgemein: support = 50%

Kalender = jeder Erste des Monats jetzt: support = confidence = 100%

• durch die Wahl verschiedener Gruppierungsmöglichkeiten, kann man viel komplexere Regeln identifizieren

Generierung von RegelnAllgemeine Association Rules

3.5 Sequentielle Muster

• Sequenz ist eine Gruppe von Tupeln, die nach bestimmten Merkmalen geordnet ist

• macht, genau wie association rules, Aussagen über diese TupelBsp.: Sortierung nach custid und item: Sequenz von Einkäufen eines

Kunden (custid = 201 {pen,ink,milk,juice},{pen,ink,juice})

• Teilsequenz ist ebenfalls Sequenz; eine Sequenz {a1,..,am} ist in Sequenz S enthalten, wenn S eine Teilsequenz {b1,..,bm} hat

BSP: Sequenz {pen},{ink,milk},{pen,juice} ist enthalten in {pen,ink},{shirt},{juice,ink,milk},{juice,pen,milk}

• Algorithmen zur Berechnung von Sequenzen sind ähnlich denen zum Finden von frequent itemsets

Generierung von Regeln

3.6 Association Rules und Vorhersagen

• association rules werden häufig zur Vorhersage benutzt

• diese müssen aber durch weitere Analysen und Grundlagenwissen gesichert sein

BSP:

Annahme: Tinte wird durch Füller, Füller mit Bleistiften verkauft

Regel {pen} => {ink}, hat confidence(Vertrauen) von 100% (in der gegebenen Datenbasis),d.h.:

um mehr Tinte zu verkaufen, könnte man Füller billiger anbieten

aber

{pencil} => {ink}, hat ebenfalls confidence von 100%, d.h.:

billigere Bleistifte, verkaufen mehr Tinte

wäre ein falscher Schluß

Generierung von Regeln

• in Wirklichkeit, nicht so triviale Entscheidungen

• kausale Verbindung zwischen LHS und RHS notwendig

• gefundene Regeln sollten als Ausgangspunkt für weitere Analysen dienen

• Expertenwissen ist nützlich

• gefundene Regeln als alleiniger Entscheidungsgrund sind zu unsicher

Generierung von RegelnAssociation Rules und Vorhersagen

• sind Graphen, die kausale Beziehungen zwischen Variablen oder Ereignissen darstellen können

• jede Kombination von kausalen Verbindungen ist ein Model der realen Welt

BSP:

kaufe Füller kaufe Tinte

Bedarf an

Schreibinstrumenten

kaufe Bleistifte

• Zahl der Modelle ist exponential zu Zahl der Variablen

• nur einige wichtige Verbindungen sollten ausgewertet werden

3.7 Bayesische Netze

Generierung von Regeln

3.8 Classification und Regression Rules

• Bsp:

VersicherungsInfo(Alter: integer, Autotyp: string, Risiko: boolean)

es werden Regeln gesucht, die das Versicherungsrisiko bestimmen

z.B.:

“Wenn das Alter zwischen 16 und 25 ist und das Auto ein Sportwagen oder Truck, so ist ein Risiko gegeben.”

• gesuchtes Attribut heißt: dependent(abhängiges) Attribut Risiko

• bestimmende Attribute: predictor Attribute Alter, Autotyp

Generierung von Regeln

• Allgemeine Form:

P1(X1) ^ P2(X2)... ^ Pk(Xk) => Y

X1..Xk: predictor Attribute

P1..Pk: Prädikate

Y: dependent Attribut

• Form der Prädikate abhängig vom Typ der predictor Attribute:

– numerisch: Pi hat die Form li Xi hi

– kategorisiert: Pi hat die Form Xi {v1,..,vj}

• die Regel heißt:

– classification rule, wenn dependent Attribut kategorisiert ist

– regression rule, wenn dependent Attribut numerisch ist

Bsp: (16 Alter 25) ^ (Auto {Sport,Truck}) => Risiko = true

Generierung von RegelnClassification und Regression

• support:

– für eine Bedingung C ist % von Tupeln, die C wahr machen

– für Regel C1 => C2 ist support für Bedingung C1 ^ C2

• confidence:

– angenommen alle Tupeln die C1 wahrmachen

– für Regel C1 => C2, % der Tupeln, die auch C2 wahr machen

• das effiziente Finden solcher Regeln ist nichttriviales Problem

• diese Regeln werden auf vielfältigste Weise eingesetzt

Generierung von RegelnClassification und Regression

4 Regeln in Form von Bäumen

• repräsentieren classification und regression rules• der Baum ist dabei die Ausgabe der Datamining-Anfrage• Bezeichnungen:

– Entscheidungsbäume, repräsentieren classification rules– regression-Bäume, repräsentieren regression rules

Bsp: Alter Entscheidungsbaum

<= 25 >25

Auto NEIN

Kombi Sport, Truck

NEIN JA

“Wenn jemand 25 oder jünger ist und einen Kombi fährt, so hat er ein niedriges Risiko.”

4.1 Entscheidunsbäume

• stellt einen Datensatz von einer Wurzel bis zu einem Blatt dar

• jeder interne Knoten ist mit einem predictor Attribut bezeichnet

• heißt auch splitting Attribut, d.h. teilt die Daten in Zweige auf

• ausgehende Kanten werden mit Prädikaten bezeichnet

• Information über splitting Attribut und Prädikat heißt splitting criterion (Kriterium)

• jedes Blatt ist mit dem Wert des dependent Attributs bezeichnet

• eine classification Regel ergibt sich wie folgt:

der Weg von Wurzel zum Blatt über verschiedene Prädikate = LHS

der Wert des Blattes = RHS

Baumartige Regeln

• Entscheidungsbäume werden in 2 Phasen konstruiert:

– growth(Wachstums) Phase:

• ein übergroßer Baum, mit sämtlichen Daten wird erzeugt

• die Regeln dieses Baumes sind überspezialisiert

– pruning(Stutzungs) Phase :

• die finale Größe wird bestimmt

• die Regeln sind allgemeiner

Berechnung eines gestutzten Baums:

• split selection Methode:

– hat als Input die Datenbasis oder einen Teil von ihr

– erzeugt daraus ein split Kriterium

Baumartige RegelnEntscheidunsbäume

• Schema zur Erzeugung eines gestutzten Baums:

– Input: Knoten n, Partition D, split selection Methode S

– Output: Entscheidungsbaum für D, mit Wurzel in n

– BuildTree(Knoten n, Datenpartition D, split selection methode S)

• wende S auf D an, um ein splitting Kriterium zu finden

• if(gutes Kriterium gefunden)

– Erzeuge zwei Knoten n1, n2 aus n

– Teile D in D1, D2

– BuildTree(n1, D1, S)

– BuildTree(n2, D2, S)

• endif

Baumartige RegelnEntscheidunsbäume

4.2 Ein Algorithmus für Entscheidungsbäume

• obiges Schema sofort anwendbar, wenn Daten in Hauptspeicher passen

• andernfalls versagt Algorithmus

• Lösung:

– die split selection Methode untersucht jeweils einzelne Attribute

– benötigt nicht unbedingt die ganze Datenbasis

– zusammengefasste(aggregierte) Daten sind ausreichend

– wird als AVC set bezeichnet (Attribut-Value,Classlabel)

Baumartige Regeln

• Die split selection Methode benötigt AVC set für jedes predictor Attribut

Bsp:

AVC set für Knoten AlterSELECT R.Alter,R.Risiko, COUNT (*)

FROM VersicherungsInfo R

GROUP BY R.Alter, R.Risiko

AVC set für Knoten AutoSELECT R.Auto,R.Risiko, COUNT (*)

FROM VersicherungsInfo R

WHERE R.Alter <= 25

GROUP BY R.Auto, R.Risiko

• AVC group Satz aller AVCs aller Attribute am Knoten n

Baumartige RegelnEntscheidunsbäume

5 Clustering

• Ziel: Aufteilung der Daten in Gruppen, die Aussagen über Ähnlichkeit machen

• Daten einer Gruppe sind ähnlich, unterschiedlicher Gruppen unähnlich

• dies wird durch Abstandsfunktion gemessen

• die Ausgabe eines Clustering-Algorithmus besteht aus zusammen-gefassten Repräsentationen für jeden Cluster

• Cluster werden zusammengefasst durch Center C und Radius R einer Sammlung von Daten r1..rn

Bsp: KundenInfo(Alter: int, Gehalt: real)

• 2 Arten von Clustering-Algorithmen:

– partielles: unterteilt die Daten in k Gruppen (benutzerdefiniert)

– hierarchisches: generiert Sequenz von Teildaten, verschmilzt in jeder Iteration 2 dieser Teile,

bis eine Partition übrig bleibt

Clustering

60k

30k

20 40 60 Alter

Gehalt

5.1 Ein Clustering Algorithmus

• der BIRCH Algorithmus

• Annahmen:

– Zahl der Datensätze ist sehr gross

– möglichst nur ein Scan der Datenbasis

– Hauptspeicher ist limitiert

• 2 Kontrollparameter:

– Größe des Hauptspeichers, resultiert in k Speicherblöcken

– anfängliche Schranke für Radius der Cluster

• wenn klein ist, werden viele kleine Cluster berechnet, sonst wenige, relativ grosse

• ein Cluster heißt kompakt, wenn Radius <

Clustering

• der Algorithmus behält immer <= k Cluster-Zusammenfassungen (Ci,Ri) im Speicher

• er behandelt immer kompakte Cluster

• es werden sequentiell Einträge gelesen und wie folgt bearbeitet:

1. Berechne den Abstand des Eintrags r und jedes existierenden C

i ist der Index des Clusters mit kleinstem Abstand (r, Ci)

2. Berechne den neuen Radius Ri’, des i-ten Clusters

wenn Ri’ <= , weise r dem i-ten Cluster zu (neues Ci, Ri = Ri’)

sonst, erzeuge neuen Cluster mit r

• Problem: weitere Cluster passen nicht in Hauptspeicher

• Lösung: erhöhe , es werden Cluster verschmolzen

ClusteringBIRCH Algorithmus

6 Ähnlichkeitssuche über Sequenzen

• Viele Informationen in Datenbasen bestehen aus Sequenzen

• Annahme: der Benutzer gibt Query-Sequenz an, will ähnliche Sequenzen erhalten

• ist eine Art unscharfe Suche

• Daten-Sequenz X ist eine Reihe von Zahlen X = {x1,..,xk}

• k ist Länge der Sequenz

• Teilsequenz Z = {z1,..,zj} erhält man aus X durch Löschen von Zahlen an Anfang und Ende

• Abstand zweier Sequenzen = Euklidische Norm ||X-Y|| = • benutzerdefinierte Schranke • Ziel: Finden aller Sequenzen im -Abstand

• Ähnlichkeits-Anfragen können in zwei Arten unterteilt werden:

Komplett-Sequenz Matching:

Query-Sequenz und Sequenzen der Datenbasis sind gleich lang

Ziel: alle Sequenzen im -Abstand

Teilsequenz Matching:

Query-Sequenz ist kürzer als Sequenzen der Datenbasis

Ziel: Finde alle Teilsequenzen im -Abstand

Ähnlichkeitssuche

6.1 Suche ähnlicher Sequenzen

• Annahme: Komplett-Sequenz Matching

• Suche ist ein mehrdimensionales Indizierungs-Problem

• Daten- und Query-Sequenzen sind Punkte im k-dimensionalen Raum

• Anlegen eines Hyper-Rechtecks mit Seitenlänge 2* und Query-Sequenz als Zentrum

• alle Sequenzen im Rechteck werden ausgegeben

• durch Benutzung der Indizes deutliche Reduzierung von Rechenzeit und Zahl der betrachteten Daten

Ähnlichkeitssuche

7 Weitere DataMining-Aufgaben• bisher nur Suche nach Mustern• weitere wichtige Aufgaben:

Datensatz und Feature Auswahl:Suche des ‘richtigen’ Datensatzes und dazugehöriger Attribute

Sampling:

Samples reduzieren den Aufwand in übergrossen Datenbanken

Nachteil: wichtige Informationen können übersehen werden

Berechnung der Samples noch rückständig (Forschungsgebiet)

Visualisierung:

verbessert Verständniss über komplexe Datensätze

hilft interessante Muster zu erkennen

8 Darwin

• Daten Mining Tool in Oracle-Umgebung

• parallele, skalierbare Client/Server-Architektur

• beliebig grosse Datenmengen

• einfachste Point-and-Click Bedienung

• visuelle Ausgabe der Ergebnisse

Darwin

Client:

Windows 95/NT/98

Server:

Windows NT(ab 4.0)

SUN Solaris

HP-UX

• Verwendete Algorithmen:

– Neuronale Netze mit Spezialfällen– Entscheidungsbäume(classification, regression)– speicherbasiertes Beweisen– Bayesisches Lernen (ab 4.0)– erweitertes Clustering

Darwin