Fast Algorithm for Mining Association Rules
Oliver MüllerKünstliche Intelligenz II WS09/10 Leibniz Universität Hannover
Inhalt
Fast Algorithm for Mining Association Rules
2
Problemstellung Formalisierung Algorithmus Apriori Algorithmus AprioriTid Algorithmus AprioriHybrid Ergebnisse Zusammenfassung
Problemstellung
Fast Algorithm for Mining Association Rules
3
Verkaufs-Transaktionen aufzeichnen Mittels Barcode-Technologie Großer Datenbestand Einzelner Datensatz bestehend aus Datum,
gekaufte Artikel
Problemstellung
Fast Algorithm for Mining Association Rules
4
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.)
Problemstellung
Fast Algorithm for Mining Association Rules
5
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
Problemstellung
Fast Algorithm for Mining Association Rules
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
Fast Algorithm for Mining Association Rules
7
Menge von Items ( -Itemset)
Notation
Fast Algorithm for Mining Association Rules
8
Menge von Items ( -Itemset)
Transaktion ist eine Menge von Items mit
Notation
Fast Algorithm for Mining Association Rules
9
Menge von Items ( -Itemset)
Transaktion ist eine Menge von Items mit Menge von Transaktionen: TID = Unique Identifier für jede Transaktion
Lexikographische Sortierung
Notation
Fast Algorithm for Mining Association Rules
10
Menge von Items ( -Itemset)
Transaktion ist eine Menge von Items mit Menge von Transaktionen: TID = Unique Identifier für jede Transaktion
Lexikographische Sortierung Assoziations-Regel:
wenn gilt: und
Notation
Fast Algorithm for Mining Association Rules
11
Menge von Items ( -Itemset)
Transaktion ist eine Menge von Items mit Menge von Transaktionen: TID = Unique Identifier für jede Transaktion
Lexikographische Sortierung Assoziations-Regel:
wenn gilt: und Confidence : aller Transaktionen in die
enthalten, enthalten auch
Notation
Fast Algorithm for Mining Association Rules
12
Menge von Items ( -Itemset) Transaktion ist eine Menge von Items mit Menge von Transaktionen: TID = Unique Identifier für jede Transaktion
Lexikographische Sortierung Assoziations-Regel:
wenn gilt: und Confidence : aller Transaktionen in die
enthalten, enthalten auch Support : aller Transaktionen in
enthalten
Formale Definition des Problems
Fast Algorithm for Mining Association Rules
13
Generierung einer Liste aller Assoziations-Regeln mit und
Formale Definition des Problems
Fast Algorithm for Mining Association Rules
14
Generierung einer Liste aller Assoziations-Regeln mit und
Achtung: Probabilistische Eigenschaft der Assoziations-
Regeln beachten: nicht unbedingt eingehalten
nicht unbedingt eingehalten
Andere Algorithmen
Fast Algorithm for Mining Association Rules
15
AIS SETM
Knowledge Discovery Klassifikations Regeln Kausale Regeln Function fitting KID3
Ablauf
Fast Algorithm for Mining Association Rules
16
1. Finden von Itemsets mit SupportDiese werden groß genannt, alle anderen klein
Ablauf
Fast Algorithm for Mining Association Rules
17
1. Finden von Itemsets mit SupportDiese werden groß genannt, alle anderen klein
2. Nutze große Itemsets zur Generierung der Regeln:
Ablauf
Fast Algorithm for Mining Association Rules
18
1. Finden von Itemsets mit SupportDiese werden groß genannt, alle anderen klein
2. Nutze große Itemsets zur Generierung der Regeln:
Sei ein großes Itemset Für jedes erzeuge Regel ,
wenn
Finden großer Itemsets
Fast Algorithm for Mining Association Rules
19
Mehrere Durchläufe von
Finden großer Itemsets
Fast Algorithm for Mining Association Rules
20
Mehrere Durchläufe von 1. Durchlauf:
Zähle Support von einzelnen Items
Finden großer Itemsets
Fast Algorithm for Mining Association Rules
21
Mehrere Durchläufe von 1. Durchlauf:
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
Finden großer Itemsets
Fast Algorithm for Mining Association Rules
22
Mehrere Durchläufe von 1. Durchlauf:
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
Fast Algorithm for Mining Association Rules
23
Intuition: Jedes Subset eines großen Itemsets ist groß
Idee
Fast Algorithm for Mining Association Rules
24
Intuition: Jedes Subset eines großen Itemsets ist groß
Finde Kandidaten für große k-Itemsets durch Kombination großer (k-1)-Itemsets
Idee
Fast Algorithm for Mining Association Rules
25
Intuition: Jedes Subset eines großen Itemsets ist groß
Finde Kandidaten für große k-Itemsets durch Kombination großer (k-1)-Itemsets
Entferne alle Kandidaten, welche kleine Subsets enthalten
Algorithmus Apriori
Fast Algorithm for Mining Association Rules
26
1. Schritt: Zähle Support 1-Items
Algorithmus Apriori
Fast Algorithm for Mining Association Rules
27
1. Schritt: Zähle Support 1-Items
k-ter Schritt
Algorithmus Apriori
Fast Algorithm for Mining Association Rules
28
1. Schritt: Zähle Support 1-Items
k-ter Schritt: Erzeuge neue
Kandidaten
Algorithmus Apriori
Fast Algorithm for Mining Association Rules
29
1. Schritt: Zähle Support 1-Items
k-ter Schritt: Erzeuge neue
Kandidaten Durchsuche alle
Transaktionen Alle Kandidaten aus t Zähle den Support
hoch
Algorithmus Apriori
Fast Algorithm for Mining Association Rules
30
1. Schritt: Zähle Support 1-Items
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
Fast Algorithm for Mining Association Rules
31
1. Schritt: Zähle Support 1-Items
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
Fast Algorithm for Mining Association Rules
32
Besteht aus 2 Schritten 1. Schritt: Join (Kombination von zwei -
Itemsets)
und sind in den ersten Einträgen identisch
Algorithmus Apriori – Apriori-Gen
Fast Algorithm for Mining Association Rules
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
Algorithmus Apriori – Apriori-Gen
Fast Algorithm for Mining Association Rules
34
Beispiel:
Join:
Prune:
, da nicht in
Algorithmus Apriori - Subset
Fast Algorithm for Mining Association Rules
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
Fast Algorithm for Mining Association Rules
36
In jeder Iteration wird die gesamte Datenbank durchsucht!
Modifikation - Algorithmus AprioriTid
Fast Algorithm for Mining Association Rules
37
Durchsucht die Datenbank nur einmal
Modifikation - Algorithmus AprioriTid
Fast Algorithm for Mining Association Rules
38
Durchsucht die Datenbank nur einmal
Kandidaten werden auch hier mit apriori-gen erzeugt.
Zur Berechnung des Supports wird dann jedoch die Menge statt benutzt
Modifikation - Algorithmus AprioriTid
Fast Algorithm for Mining Association Rules
39
Durchsucht die Datenbank nur einmal
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
Fast Algorithm for Mining Association Rules
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
Fast Algorithm for Mining Association Rules
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
Fast Algorithm for Mining Association Rules
42
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) AIS und SETM erzeugen sehr viel mehr Kandidaten
Ergebnisse
Fast Algorithm for Mining Association Rules
43
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) AIS und SETM erzeugen sehr viel mehr Kandidaten
Wie vergleichen? Mit synthetisch generierten Daten (welches
Modell?) (Reale Daten)
Synthetische Daten
Fast Algorithm for Mining Association Rules
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
Fast Algorithm for Mining Association Rules
45
SETM Zeiten für T>5 sind sehr viel höher
Ergebnisse
Fast Algorithm for Mining Association Rules
46
Ergebnisse
Fast Algorithm for Mining Association Rules
47
Apriori ist bei großen Problemen besser als AprioriTid
Vergleich Apriori – AprioriTid
Fast Algorithm for Mining Association Rules
48
AprioriTid benutzt statt . Passt in den Speicher, so ist AprioriTid
schneller als Apriori.
Vergleich Apriori – AprioriTid
Fast Algorithm for Mining Association Rules
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
Fast Algorithm for Mining Association Rules
50
Verwende Apriori in den ersten Iterationen Wenn als klein genug angenommen wird,
wechsle zu AprioriTid
AprioriHybrid
Fast Algorithm for Mining Association Rules
51
Verwende Apriori in den ersten Iterationen Wenn als klein genug angenommen wird,
wechsle zu AprioriTid Verwende dazu eine Heuristik:
AprioriHybrid
Fast Algorithm for Mining Association Rules
52
Verwende Apriori in den ersten Iterationen Wenn als klein genug angenommen wird,
wechsle zu AprioriTid Verwende dazu eine Heuristik:
Umschaltung verbraucht Zeit Ist meistens immer noch besser
AprioriHybrid – Ergebnisse
Fast Algorithm for Mining Association Rules
53
AprioriHybrid ist meist noch besser als Apriori und AprioriTid
Zusammenfassung
Fast Algorithm for Mining Association Rules
54
Assoziationsregeln sind ein wichtiges Werkzeug zur Analyse von Datenbeständen
Zusammenfassung
Fast Algorithm for Mining Association Rules
55
Assoziationsregeln sind ein wichtiges Werkzeug zur Analyse von Datenbeständen
Es wurden Algorithmen vorgestellt, welche schneller und Ressourcensparender arbeiten als bisherige Ansätze
Zusammenfassung
Fast Algorithm for Mining Association Rules
56
Assoziationsregeln sind ein wichtiges Werkzeug zur Analyse von Datenbeständen
Es wurden Algorithmen vorgestellt, welche schneller und Ressourcensparender arbeiten als bisherige Ansätze
AprioriHybrid schlägt AIS und SETM dabei um Größenordnungen bei großen Datenbeständen
Zusammenfassung
Fast Algorithm for Mining Association Rules
57
Assoziationsregeln sind ein wichtiges Werkzeug zur Analyse von Datenbeständen
Es wurden Algorithmen vorgestellt, welche schneller und Ressourcensparender arbeiten als bisherige Ansätze
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)
Fast Algorithm for Mining Association Rules
58