INTELLIGENTE DATENANALYSE IN MATLAB - cs.uni-potsdam.de · Lernen von Assoziationsregeln der Form „wenn die Attribute 1, 2, 3 die Werte a, b, c annehmen, dann haben die Attribute

INTELLIGENTE DATENANALYSE

IN MATLAB

Unüberwachtes Lernen: Clustern von Attributen

J. Han, M. Kamber: Data Mining – Concepts and

Techniques.

J. Han et. al: Mining Frequent Patterns without

Candidate Generation.

C. Zhang, S. Zhang: Association Rule Mining.

Literatur

2

Schritte der Datenanalyse:

Überblick

3

Aggregation und

Selektion von

Daten.

Integration und

Säuberung der

Daten.

Feature-

Extraktion.

Algorithmen für

das Optimieren

des Zielkriteriums

finden.

Implementieren

der Algorithmen.

Modell-Selektion

& -Anpassung.

Training &

Evaluation des

Modells auf

gegebenen Daten.

Vorhersage für

neue Daten.

Daten-

vorverarbeitungProblemlösung

Anwendung

der LösungProblemanalyse

Bestimmen von

gegeb./gesuchten

Größen.

Wahl des

Performanzmaß/

Zielkriteriums.

Modellraum und

Modellannahmen.

Clustern von Instanzen:

Finden und deterministische bzw. probabilistische Zuweisung

zu Bereichen mit vielen Datenpunkten (Cluster).

Clustern von Attributen:

Häufig zusammen auftretende (ähnliche bzw. korrelierte)

Attribute finden.

Clustern von Instanzen & Attributen (Co-Clustern):

Gleichzeitiges Clustern von Instanzen und Attributen.

Outlier Detection:

Suche nach seltenen/auffälligen Datenpunkten.

Unüberwachtes LernenArten von Modellen & Lernproblemen

4

Gegeben: Menge von n Trainingsdaten mit m

Attributen (Datenmatrix mit Spaltenvektoren xi).

Gesucht:

Numerische Attribute:

Cluster von ähnlichen, assoziierten oder redundanten Attributen analog

zu Clustern von Instanzen (transponierte Datenmatrix segmentieren).

Diskrete Attribute:

Finden von Frequent Itemsets, d.h. häufig auftretender Muster bspw.

für Kompression, Visualisierung etc.

Lernen von Assoziationsregeln der Form „wenn die Attribute 1, 2, 3 die

Werte a, b, c annehmen, dann haben die Attribute 4, 5 die Werte d, e“.

Clustern von AttributenProblemstellung

5

m nX X

m

i Xx

Warenkorbanalyse.

z.B. für Katalog-Design, Cross-/Up-Selling, Empfehlungs-

systeme, Produktanordnung in Supermärkten usw.

Analyse des Surfverhaltens von Internetnutzern.

z.B. zur Optimierung der Navigation auf einer Webseite.

Gruppierung von Dokumenten.

z.B. für Email-Batch-Erkennung, Plagiat-Erkennung.

Clustern von AttributenAnwendung

6

Gesucht sind Assoziationsregeln der Form „wenn die

Attribute pi der Menge bestimmte

Werte yi annehmen, dann haben die Attribute qj der

Menge die Werte “.

Definition: Boolesche Funktion

Definition: Assoziationsregel

Lernen von Assoziationsregeln

7

( , , )p

p

wahr x yg p y

falsch x y

x

1 1 1 1( , , ) ( , , ) ( , , ) ( , , )s s t tg p y g p y g q y g q y x x x x

1{ ,..., } {1,..., }sP p p m

1{ ,..., } {1,..., }, tQ q q m P Q jy

Beispiel Warenkorbanalyse:

Welche Produkte werden (nicht)

zusammen gekauft?

Mögliche boolesche Fragen:

Kaufte Kunde 1 Milch?

Kaufte Kunde 3 keine Eier?

Mögliche Assoziationsregeln:

Wer Milch kauft, kauft auch Müsli:

Wer Bier und Eier kauft, kauft kein Brot:

Lernen von AssoziationsregelnBeispiel

8

1( ,Milch, ja)g wahrx

( ,Milch, ja) ( ,Müsli, ja)g gx x

3( ,Eier,nein)g falschx

( ,Bier, ja) ( ,Eier, ja) ( ,Brot,nein)g g g x x x

Kunde Brot Milch Eier Bier Müsli

1 nein ja ja nein ja

2 ja ja nein ja nein

3 nein nein ja ja nein


Wertebereich der Attribute:

Binäre/boolesche, nominale oder ordinale Attribute.

Numerische Attribute: müssen zuvor diskretisiert werden.

Bedeutung der Attribute:

Verschiedene Attribute/Belegungen unterschiedlich „wichtig“.

z.B. „Wer Computer kauft, kauft auch Computer-Zubehör“ ist evtl.

informativer als „Wer einen Dell-PC kauft, kauft auch eine Maus“.

z.B. „Wer Milch kauft, kauft auch Müsli“ ist evtl. informativer als

„Wer Milch kauft, kauft kein Bier“.

Redundanz, d.h. Ähnlichkeit/Korrelation zwischen Attributen

führt zu semantisch gleichen (redundanten) Regeln.

Lernen von AssoziationsregelnDateneigenschaften

9

Es gibt exponentiell viele mögliche Assoziationsregeln.

Assoziationsregeln unterschiedlich stark durch Daten

gestützt, d.h. unterschiedlich wahrscheinlich.

Betrachten Ereignisse:

Frage: Wie wahrscheinlich ist eine Assoziationsregel

gegeben die Daten?

Aus folgt jedoch .

Lernen von AssoziationsregelnBewertung von Assoziationsregeln

10

1 1

1 1

( , , ) ( , , )

( , , ) ( , , )

s s

t t

A g p y g p y

B g q y g q y

x x

x x

A B

( | ) ( | ) 1 ( | ) ( , | )P A B P A B P A P A B X X X X

( | ) 0P A X ( | ) 1P A B X

Betrachten daher zwei Kriterien:

Rückhalt (support), d.h. wie häufig treten die Ereignisse A

und B gemeinsam ein:

Vertrauen (confidence), d.h. wie oft tritt B ein wenn A

eingetreten ist:

Assoziationsregel ist stark mit Mindest-Support smin

und Mindest-Konfidenz cmin falls:

und

Lernen von AssoziationsregelnBewertung von Assoziationsregeln

11

supp( ) ( , | )A B P A B X

conf ( ) ( | , ) ( , | ) ( | )A B P B A P A B P A X X X

minsupp( )A B s minconf ( )A B c

A B

Beispiel für smin = 40% und cmin = 60%:

Wer Milch kauft, kauft auch Müsli:

Wer Bier und Eier kauft, kauft kein Brot:

Lernen von AssoziationsregelnBeispiel (Fortsetzung)

12






supp ( ( ,Milch, ja), ( ,Müsli, ja))P g g x x2

4

conf ( ( ,Müsli, ja) | ( ,Milch, ja))P g g x x2

3

supp ( ( ,Bier, ja), ( ,Eier, ja), ( ,Brot,nein))P g g g x x x

conf ( ( ,Brot,nein) | ( ,Bier, ja), ( ,Eier, ja))P g g g x x x

1

4

1

Starke Assoziationsregel

Schwache Assoziationsregel

( ,Milch, ja) ( ,Müsli, ja)g gx x

( ,Bier, ja) ( ,Eier, ja) ( ,Brot,nein)g g g x x x

Frequent-Itemset-Suche: Finde zunächst alle Mengen

mit Mindest-Support, d.h. .

Regel-Extraktion: Für jede dieser Mengen I, bilde alle

nicht-leeren Teilmengen und prüfe ob

erfüllt ist; falls ja, ist starke Assoziationsregel.

Lernen von AssoziationsregelnLösungsansatz

13

1 1{ ( , , ), , ( , , )}h hI g p y g p y x x

1 1 min( ( , , ), , ( , , ))h hP g p y g p y sx x

D I

min

( )conf ( \ )

( )

P ID I D c

P D

\D I D

Für eine gegebene Menge

gelten folgende Aussagen:

Der Support von I ist größer oder gleich dem Mindest-

Support, d.h. .

Ereignisse wurden in den Daten häufig

gemeinsam beobachtet.

Menge I bildet ein Frequent Itemset.

Jede Teilmenge von I bildet ein Frequent Itemset.

Frequent-Itemset-Suche

14

1 1{ ( , , ), , ( , , )}h hI g p y g p y x x

1 1( , , ), , ( , , )h hg p y g p yx x

1 1 minsupp( ) ( ( , , ), , ( , , ))h hI P g p y g p y s x x

A-Priori-Eigenschaft: Jede Teilmenge eines Frequent

Itemsets ist ein Frequent Itemset.

Beispiel: Wenn Milch & Müsli oft gekauft wird, wird auch

Milch oft gekauft bzw. wird auch Müsli oft gekauft.

Folge: Frequent Itemset mit k +1 Elementen besteht aus

Vereinigung zweier k-elementiger Frequent Itemsets

(mit k – 1 gleichen Elementen).

Beginnend mit 1-elementigen Frequent Itemsets lassen sich

so beliebig große Frequent Itemsets finden (Apriori-

Algorithmus).

Frequent-Itemset-Suche

15

Algorithmus:Apriori(Datenmatrix X, Mindest-Support smin)

Setze k = 0,

DO

k = k + 1

FOR

IF THEN

FOR

IF THEN

WHILE

RETURN

Frequent-Itemset-SucheApriori-Algorithmus

16

1 {{ ( , , )}|1 , }i i iC g i y i m y Y x

Ck sind alle Kandidaten für Frequent

Itemsets der Größe k

kI C

1, k kL C

Lk sind alle Frequent Itemsets der

Größe kminsupp( )I s

{ }k kL L I

kJ L

1I J k

1 1 { }k kC C I J

1kC

1 kL L

I und J sind Frequent Itemsets der

Größe k mit k – 1 gleichen Elementen

Betrachten beispielhaft nur

„positive“ Items und smin = 50%:

Frequent-Itemset-SucheApriori-Algorithmus: Beispiel

17






( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

b g Brot ja

b g Brot nein

m g Milch ja

m g Milch nein

e g Eier ja

e g Eier nein

r g Bier ja

r g Bier nein

s g Müsli ja

s g Müsli nein

x

x

x

x

x

x

x

x

x

xEl

em

ent

are

reig

nis

se (Item

s)

Itemset Support Itemset Support Itemset Support

1C 1L 2C

{ }m

{ }m

{ }b

{ }e

{ }r

{ }s

{ }e

1 4

3 4

3 4

1 2

1 2

3 4

3 4

{ , }m e 1 2

{ }r

{ }s

1 2

1 2

{ , }m r 1 4

{ , }e r 1 4

{ , }m s 1 2

{ , }e s 1 2

{ , }r s 0

1 {{ },{ },{ },{ }}L m e r s




18






( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

b g Brot ja

b g Brot nein

m g Milch ja

m g Milch nein

e g Eier ja

e g Eier nein

r g Bier ja

r g Bier nein

s g Müsli ja

s g Müsli nein

x

x

x

x

x

x

x

x

x

xEl

em

ent

are

reig

nis

se (Item

s)

Itemset Support Itemset Support

2L 3C

Itemset Support

2C

{ , }m e 1 2

{ , }m r 1 4

{ , }e r 1 4

{ , }m s 1 2

{ , }e s 1 2

{ , }r s 0

{ , }m e 1 2

{ , }m s 1 2

{ , , }m e s 1 2

{ , }e s 1 2

1 {{ },{ },{ },{ }}L m e r s

2 {{ , },{ , },{ , }}L m e m s e s




19






( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

b g Brot ja

b g Brot nein

m g Milch ja

m g Milch nein

e g Eier ja

e g Eier nein

r g Bier ja

r g Bier nein

s g Müsli ja

s g Müsli nein

x

x

x

x

x

x

x

x

x

xEl

em

ent

are

reig

nis

se (Item

s)

Itemset Support Itemset Support

3L 4C

Itemset Support

3C

{ , , }m e s 1 2 { , , }m e s 1 2

3 {{ , , }}L m e s

1 {{ },{ },{ },{ }}L m e r s

2 {{ , },{ , },{ , }}L m e m s e s

Mengenoperationen:

Verwendung von Hashs bzw. Hash-Bäumen.

Berechnung des Supports:

Ignoriere Items die nicht Element eines Frequent Itemset der

Größe k sind bei Berechnungen für Itemsets der Größe >k.

Partitionierung der Daten:

Frequent Itemset bzgl. aller Daten muss Frequent Itemset

mindestens einer Partition sein.

Berechne Frequent Itemsets aller Partitionen und prüfe welche

davon auch Frequent Itemsets bzgl. aller Daten sind.

Frequent-Itemset-SucheApriori-Algorithmus: Implementierung

20

Vorteile:

Effektiv und relativ einfach zu implementieren.

Nachteile:

Sehr viele Kandidaten (hohe Laufzeit/Speicherverbrauch).

104 elementare Frequent Itemsets erzeugen 107 zwei-elementige

Kandidaten.

Suche nach Frequent Itemset der Größe 100 erfordert mindestens

2100 1030 Kandidaten.

Viele Iterationen über die Daten.

Frequent Itemset der Größe k erfordert k + 1 Iterationen.

Frequent-Itemset-SucheApriori-Algorithmus: Bewertung

21

Idee: Daten als Frequent-Pattern-Baum darstellen und daraus Frequent Itemsets extrahieren.

Aufbau des FP-Baums:

Speichert nur Informationen welche zum Finden von Frequent

Itemsets notwendig sind (Sufficient Statistics).

Benötigt lediglich 2 Iterationen über die Daten.

Extraktion der Frequent Itemsets:

Divide & Conquer-Ansatz, d.h. Reduktion des Suchproblems

in viele kleine Optimierungsprobleme.

Vermeidung aufwendiger Kandidaten-Generierung.

Frequent-Itemset-SucheFP-Growth-Algorithmus

22

Bestimmung aller Elementar-

ereignisse (Items) und Sortierung

nach ihrer Häufigkeit.

Entferne alle Attribute mit zu

kleinem Support.

Frequent-Itemset-SucheFP-Growth-Algorithmus: Aufbau des FP-Baums

23






( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

( , , )

b g Brot ja

b g Brot nein

m g Milch ja

m g Milch nein

e g Eier ja

e g Eier nein

r g Bier ja

r g Bier nein

s g Müsli ja

s g Müsli nein

x

x

x

x

x

x

x

x

x

xEl

em

ent

are

reig

nis

se (Item

s)

Kunde

1 1 1 1 0 1 1 0 0 0 0

2 0 1 0 1 0 0 1 1 0 1

3 1 0 1 1 0 0 1 0 1 0

4 1 1 1 0 1 1 0 0 0 0

Häufigkeit 3 3 3 2 2 2 2 1 1 1


„positive“ Items.

Konstruktion des Präfix-Baums

der Instanzen:

Frequent-Itemset-SucheFP-Growth-Algorithmus: Aufbau des FP-Baums

24

Kunde m e r s b

1 1 1 0 1 0

2 1 0 1 0 1

3 0 1 1 0 0

4 1 1 0 1 0

1

1

1

2

1

1

1

3

2

2

Nicht berücksichtigt bei

Konstruktion des FP-Baums

da zu kleiner Support

Alle Frequent Itemsets, welche gk enthalten und gk+1,…, gm

nicht enthalten, sind Teilmengen eines Pfades von der

Wurzel zu einem Knoten gk.

Idee: Rekursiv alle Frequent Itemsets extrahieren.

Frequent-Itemset-SucheFP-Growth-Algorithmus: Extraktion der Frequent Itemsets

25

1

1

1

3

2

2

3

2

3

2

Algorithmus:

Für alle Knoten (Items) gk, betrachte Teilbaum mit allen

Pfaden von der Wurzel zu einem Knoten (Item) gk.

Berechne Support der Items für diesen Teilbaum.

Falls gk ein Frequent Item ist:

Erzeuge FP-Baum mit allen Frequent Items gp (p < k) des Teilbaumes

und bestimme davon rekursiv alle Frequent Itemsets I1,…, Iz.

Rückgabe aller Frequent Itemsets .

Sonst, Rückgabe der leeren Menge.


26

1{ }, { },..., { }k k z kg I g I g

Beispiel für n = 5, smin = 40%:


27

1

1

1

4

3

3

4

4

3

3

2

2

3

3

1

1

1

1

1

2

2

2

2

2

1

2

3

2

1

2

2

Teilbaum für g6:



28

1

1

1

4

3

3

4

4

3

3

2

2

3

3

1

1

1

12

2

2

2

2

3

2

2

Teilbaum für g6:

Frequent Items des Teilbaumes



29

1

1

1

4

3

3

4

4

3

3

2

2

3

3

1

1

1

3

2

2

2

2

3

2

2

Teilbaum für g6:

FP-Baum des Teilbaumes



30

Rekursion bzgl. g6 ergibt:

2

1 2 1

3 2 3 1 3 2 1 3

5 2 5 1 5 2 1 5 3 5 2 3 5 1 3 5 2 1 3 5

{ }

{ },{ , }

{ },{ , },{ , },{ , , }

{ },{ , },{ , },{ , , },{ , },{ , , },{ , , },{ , , , }

g

g g g

g g g g g g g g

g g g g g g g g g g g g g g g g g g g g

3

2

2

2

2

3

2

2

Teilbaum für g6:

6 2 6 1 6 2 1 6 3 6 2 3 6 1 3 6 2 1 3 6{ },{ , },{ , },{ , , },{ , },{ , , },{ , , },{ , , , },...g g g g g g g g g g g g g g g g g g g g

Vorteile:

FP-Growth ist deutlich schneller als Apriori.

Keine Kandidaten-Generierung.

Iterationen über kompakte Datenstruktur (FP-Baum) statt

über alle Daten.

Nachteile:

Höherer Implementierungsaufwand.

Innerhalb der Rekursion werden viele gleiche Bäume erzeugt;

viele redundante Berechnungen.

Frequent-Itemset-SucheFP-Growth-Algorithmus: Bewertung

31

Ziel: Identifikation ähnlicher bzw. korrelierter Attribute.

Assoziationsregeln, Frequent Itemsets, Sequenzmuster.

Frequent-Itemset-Suche mit Kandidaten-Generierung (z.B. Apriori-Algorithmus):

Idee: Teilmenge eines Frequent Itemsets ist wieder ein Frequent Itemset Konstruktion großer Itemsets aus kleinen.

Frequent-Itemset-Suche ohne Kandidaten-Generierung (z.B. FP-Growth-Algorithmus):

Idee: Konstruktion eines Präfix-Baumes Finden von Frequent Itemsets durch rekursives Traversieren undRestrukturieren des Baumes.

Zusammenfassung

32

Documents

INTELLIGENTE DATENANALYSE IN MATLAB - cs.uni-potsdam.de · Lernen von Assoziationsregeln der Form „wenn die Attribute 1, 2, 3 die Werte a, b, c annehmen, dann haben die Attribute