Fast Algorithm for Mining Association Rules Oliver Müller Künstliche Intelligenz II WS09/10 Leibniz Universität Hannover

Fast Algorithm for Mining Association Rules

Oliver MüllerKünstliche Intelligenz II WS09/10 Leibniz Universität Hannover

Inhalt


2

Problemstellung Formalisierung Algorithmus Apriori Algorithmus AprioriTid Algorithmus AprioriHybrid Ergebnisse Zusammenfassung

Problemstellung


3

Verkaufs-Transaktionen aufzeichnen Mittels Barcode-Technologie Großer Datenbestand Einzelner Datensatz bestehend aus Datum,

gekaufte Artikel

Problemstellung


4


gekaufte Artikel Interesse von Firmen meist für Marketing-

Zwecke Kundenspezifische Vermarktungs-Strategien

(Cross-Marketing, Attached Mailing, Katalog Design, etc.)

Problemstellung


5


gekaufte Artikel Interesse von Firmen meist für Marketing-

Zwecke Kundenspezifische Vermarktungs-Strategien

(Cross-Marketing, Attached Mailing, Katalog Design, etc.)

Ziel: Mining von Assoziations-Regeln im Datenbestand

Problemstellung


6

Verkaufs-Transaktionen aufzeichnen Mittels Barcode-Technologie Großer Datenbestand Einzelner Datensatz bestehend aus Datum, gekaufte

Artikel Interesse von Firmen meist für Marketing-Zwecke

Kundenspezifische Vermarktungs-Strategien (Cross-Marketing, Attached Mailing, Katalog Design, etc.)

Ziel: Mining von Assoziations-Regeln im Datenbestand

Beispiel: Reifen ^ Zubehör Kfz-Dienstleistung

Zu 98% Sicherheit (Confidence)

Notation


7

Menge von Items ( -Itemset)

Notation


8


Transaktion ist eine Menge von Items mit

Notation


9


Transaktion ist eine Menge von Items mit Menge von Transaktionen: TID = Unique Identifier für jede Transaktion

Lexikographische Sortierung

Notation


10



Lexikographische Sortierung Assoziations-Regel:

wenn gilt: und

Notation


11




wenn gilt: und Confidence : aller Transaktionen in die

enthalten, enthalten auch

Notation


12

Menge von Items ( -Itemset) Transaktion ist eine Menge von Items mit Menge von Transaktionen: TID = Unique Identifier für jede Transaktion


wenn gilt: und Confidence : aller Transaktionen in die

enthalten, enthalten auch Support : aller Transaktionen in

enthalten

Formale Definition des Problems


13

Generierung einer Liste aller Assoziations-Regeln mit und

Formale Definition des Problems


14

Generierung einer Liste aller Assoziations-Regeln mit und

Achtung: Probabilistische Eigenschaft der Assoziations-

Regeln beachten: nicht unbedingt eingehalten

nicht unbedingt eingehalten

Andere Algorithmen


15

AIS SETM

Knowledge Discovery Klassifikations Regeln Kausale Regeln Function fitting KID3

Ablauf


16

1. Finden von Itemsets mit SupportDiese werden groß genannt, alle anderen klein

Ablauf


17


2. Nutze große Itemsets zur Generierung der Regeln:

Ablauf


18


2. Nutze große Itemsets zur Generierung der Regeln:

Sei ein großes Itemset Für jedes erzeuge Regel ,

wenn

Finden großer Itemsets


19

Mehrere Durchläufe von



20

Mehrere Durchläufe von 1. Durchlauf:

Zähle Support von einzelnen Items



21


Zähle Support von einzelnen Items k-ter Durchlauf:

Erzeuge neue Kandidaten aus großen Itemsets von vorherigen Durchläufen

Verwerfe Kandidaten mit zu geringem Support



22


Zähle Support von einzelnen Items k-ter Durchlauf:

Erzeuge neue Kandidaten aus großen Itemsets von vorherigen Durchläufen

Verwerfe Kandidaten mit zu geringem Support Terminiere, wenn keine großen Itemsets mehr

gefunden werden

Idee


23

Intuition: Jedes Subset eines großen Itemsets ist groß

Idee


24


Finde Kandidaten für große k-Itemsets durch Kombination großer (k-1)-Itemsets

Idee


25


Finde Kandidaten für große k-Itemsets durch Kombination großer (k-1)-Itemsets

Entferne alle Kandidaten, welche kleine Subsets enthalten

Algorithmus Apriori


26

1. Schritt: Zähle Support 1-Items

Algorithmus Apriori


27


k-ter Schritt

Algorithmus Apriori


28


k-ter Schritt: Erzeuge neue

Kandidaten

Algorithmus Apriori


29


k-ter Schritt: Erzeuge neue

Kandidaten Durchsuche alle

Transaktionen Alle Kandidaten aus t Zähle den Support

hoch

Algorithmus Apriori


30


k-ter Schritt: Erzeuge neue Kandidaten Durchsuche alle

Transaktionen Alle Kandidaten aus t Zähle den Support hoch

Übernehme nur die mit genügend

Support

Algorithmus Apriori


31


k-ter Schritt: Erzeuge neue Kandidaten Durchsuche alle

Transaktionen Alle Kandidaten aus t Zähle den Support hoch

Übernehme nur die mit genügend

Support

Algorithmus Apriori – Apriori-Gen


32

Besteht aus 2 Schritten 1. Schritt: Join (Kombination von zwei -

Itemsets)

und sind in den ersten Einträgen identisch



33

Besteht aus 2 Schritten 1. Schritt: Join (Kombination von zwei -

Itemsets)

2. Schritt: Prune

und sind in den ersten Einträgen identisch

Entferne alle Kandidaten, welche kleine Subsets enthalten



34

Beispiel:

Join:

Prune:

, da nicht in

Algorithmus Apriori - Subset


35

Benutzt Hash-Tree

Hash-Wert in i-ter Ebene berechnet sich durch i-ten Item aus c

Laufzeit O(max(k, size(t)))

Wichtig:Items lexikographisch sortiert.

Algorithmus Apriori - Problem


36

In jeder Iteration wird die gesamte Datenbank durchsucht!

Modifikation - Algorithmus AprioriTid


37

Durchsucht die Datenbank nur einmal



38


Kandidaten werden auch hier mit apriori-gen erzeugt.

Zur Berechnung des Supports wird dann jedoch die Menge statt benutzt



39


Kandidaten werden auch hier mit apriori-gen erzeugt.

Zur Berechnung des Supports wird dann jedoch die Menge statt benutzt

Einträge von haben die Form <TID, > Idee: Speichere zu jeder Transaktion eine

Liste aller potentiell großen -Itemsets entspricht dabei der Datenbank

Algorithmus AprioriTid - Beispiel


40

TID Items

100 1 3 4

200 2 3 5

300 1 2 3 5

400 2 5

TID Set-of-Itemsets

100 { {1}, {3}, {4} }

200 { {2}, {3}, {5} }

300 { {1}, {2}, {3}, {5} }

400 { {2}, {5} }

Minimum support = 2

Itemset Support

{1} 2

{2} 3

{3} 3

{5} 3

Itemset Support

{1 2} 1

{1 3} 2

{1 5} 1

{2 3} 2

{2 5} 3

{3 5} 2

TID Set-of-Itemsets

100 { {1 3} }

200 { {2 3}, {2 5}, {3 5} }

300 { {1 2}, {1 3}, {1 5}, {2 3}, {2 5}, {3 5} }

400 { {2 5} }

Itemset Support

{1 3} 2

{2 3} 2

{2 5} 3

{3 5} 2

Itemset Support

{2 3 5} 1

TID Set-of-Itemsets

200 { {2 3 5} }

300 { {2 3 5} }

Itemset Support

{2 3 5} 2

Ergebnisse


41

Vergleich von Apriori und AprioriTid mit den Algorithmen AIS (Kandidaten für große Itemsets on-the-fly

erzeugen) SETM (on-the-fly, SQL optimiert)

Ergebnisse


42


erzeugen) SETM (on-the-fly, SQL optimiert) AIS und SETM erzeugen sehr viel mehr Kandidaten

Ergebnisse


43


erzeugen) SETM (on-the-fly, SQL optimiert) AIS und SETM erzeugen sehr viel mehr Kandidaten

Wie vergleichen? Mit synthetisch generierten Daten (welches

Modell?) (Reale Daten)

Synthetische Daten


44

Gutes Modell für reales Käufer-Verhalten: Tendenz zum Kauf mehrerer Artikel gleichzeitig. Transaktionen haben eine typische Größe (Parameter

|T| ) Große Itemsets haben eine typische Größe

(Parameter |I|) Große Itemsets haben oft gemeinsame Items Nicht alle Artikel eines großen Itemsets werden

immer zusammen gekauft Weitere Parameter:

|D| Anzahl der Transaktionen N Anzahl Items (hier: N =1000) ...

Ergebnisse


45

SETM Zeiten für T>5 sind sehr viel höher

Ergebnisse


46

Ergebnisse


47

Apriori ist bei großen Problemen besser als AprioriTid

Vergleich Apriori – AprioriTid


48

AprioriTid benutzt statt . Passt in den Speicher, so ist AprioriTid

schneller als Apriori.

Vergleich Apriori – AprioriTid


49

AprioriTid benutzt statt . Passt in den Speicher, so ist AprioriTid

schneller als Apriori. Wenn zu groß wird, passt es nicht in den

Speicher und die Ladezeiten erhöhen sich sehr (Schreiben/Lesen auf Festplatte).

AprioriHybrid


50

Verwende Apriori in den ersten Iterationen Wenn als klein genug angenommen wird,

wechsle zu AprioriTid

AprioriHybrid


51


wechsle zu AprioriTid Verwende dazu eine Heuristik:

AprioriHybrid


52


wechsle zu AprioriTid Verwende dazu eine Heuristik:

Umschaltung verbraucht Zeit Ist meistens immer noch besser

AprioriHybrid – Ergebnisse


53

AprioriHybrid ist meist noch besser als Apriori und AprioriTid

Zusammenfassung


54

Assoziationsregeln sind ein wichtiges Werkzeug zur Analyse von Datenbeständen

Zusammenfassung


55


Es wurden Algorithmen vorgestellt, welche schneller und Ressourcensparender arbeiten als bisherige Ansätze

Zusammenfassung


56



AprioriHybrid schlägt AIS und SETM dabei um Größenordnungen bei großen Datenbeständen

Zusammenfassung


57



AprioriHybrid schlägt AIS und SETM dabei um Größenordnungen bei großen Datenbeständen

Aber: Was ist mit hierarchisch sortierten Daten? Beispiel: is-a-Beziehung (Spülmaschine ist ein

Küchengerät …) Regeln nicht immer sinnvoll (Rückgang #Piraten

Zunahme globale Erwärmung)


58

Documents

Fast Algorithm for Mining Association Rules Oliver Müller Künstliche Intelligenz II WS09/10 Leibniz Universität Hannover