Fast Algorithm for Mining Association Rules Oliver Müller Künstliche Intelligenz II WS09/10...

Fast Algorithm for Mining Association Rules

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

Inhalt

Problemstellung Formalisierung Algorithmus Apriori Algorithmus AprioriTid Algorithmus AprioriHybrid Ergebnisse Zusammenfassung

Problemstellung

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

gekaufte Artikel

Problemstellung

gekaufte Artikel Interesse von Firmen meist für Marketing-

Zwecke Kundenspezifische Vermarktungs-Strategien

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

Problemstellung

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

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

Menge von Items ( -Itemset)

Notation

Transaktion ist eine Menge von Items mit

Notation

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

Lexikographische Sortierung

Notation

Lexikographische Sortierung Assoziations-Regel:

wenn gilt: und

Notation

wenn gilt: und Confidence : aller Transaktionen in die

enthalten, enthalten auch

Notation

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

Generierung einer Liste aller Assoziations-Regeln mit und

Formale Definition des Problems

Generierung einer Liste aller Assoziations-Regeln mit und

Achtung: Probabilistische Eigenschaft der Assoziations-

Regeln beachten: nicht unbedingt eingehalten

nicht unbedingt eingehalten

Andere Algorithmen

AIS SETM

Knowledge Discovery Klassifikations Regeln Kausale Regeln Function fitting KID3

Ablauf

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

Ablauf

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

Ablauf

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

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

Finden großer Itemsets

Mehrere Durchläufe von

Mehrere Durchläufe von 1. Durchlauf:

Zähle Support von einzelnen Items

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

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

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

1. Schritt: Zähle Support 1-Items

Algorithmus Apriori

k-ter Schritt

Algorithmus Apriori

k-ter Schritt: Erzeuge neue

Kandidaten

Algorithmus Apriori

k-ter Schritt: Erzeuge neue

Kandidaten Durchsuche alle

Transaktionen Alle Kandidaten aus t Zähle den Support

Algorithmus Apriori

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

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

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

Itemsets)

und sind in den ersten Einträgen identisch

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

Beispiel:

Prune:

, da nicht in

Algorithmus Apriori - Subset

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

In jeder Iteration wird die gesamte Datenbank durchsucht!

Modifikation - Algorithmus AprioriTid

Durchsucht die Datenbank nur einmal

Kandidaten werden auch hier mit apriori-gen erzeugt.

Zur Berechnung des Supports wird dann jedoch die Menge statt benutzt

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

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} 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

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

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

Ergebnisse

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

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

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

Ergebnisse

Apriori ist bei großen Problemen besser als AprioriTid

Vergleich Apriori – AprioriTid

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

schneller als Apriori.

Vergleich Apriori – AprioriTid

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

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

wechsle zu AprioriTid

AprioriHybrid

wechsle zu AprioriTid Verwende dazu eine Heuristik:

AprioriHybrid

wechsle zu AprioriTid Verwende dazu eine Heuristik:

Umschaltung verbraucht Zeit Ist meistens immer noch besser

AprioriHybrid – Ergebnisse

AprioriHybrid ist meist noch besser als Apriori und AprioriTid

Zusammenfassung

Assoziationsregeln sind ein wichtiges Werkzeug zur Analyse von Datenbeständen

Zusammenfassung

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

Zusammenfassung

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

Zusammenfassung

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 Oliver Müller Künstliche Intelligenz II WS09/10...

Documents

Self Organizing Tree Algorithm

Algorithm Engineering „ Priority Queues“

Creativity rules festivalprogramm

Algorithm Engineering Sommersemester 2009 Universität Bremen

AHB05 Rules Booklet v2.0 DE v4

Algorithm Engineering „Priority Queues“ Stefan Edelkamp

WS09/10 swt.tu-berlin.de/menue/studium_und_lehre/lehrveranstaltungen/eks

Description Logic Rules Markus Kroetzsch

UNIPOR WS09 CORISO · In seiner Struktur nutzt der neue UNIPOR WS09 CORISO bewährte Lösungen aus dem Brückenbau. Speziell ausgeprägte Stege in den Ziegelwänden sorgen für eine

Algorithm Selection, Scheduling and Configuration of

Ground Rules Migrants

Speicherstadt boargame rules

ALLGEMEINE HALLENREGELN GENERAL RULES

Vortrags Folien - Information Rules

Algorithm Engineering von Anfang an: Sortieren und ...mehlhorn/AlgorithmEngineering/sanders_sb.pdf · Sanders: Algorithm Engineering 1 Algorithm Engineering von Anfang an: Sortieren

Adapting Quantum Approximation Optimization Algorithm

Algorithm Engineering „ Teilmengen-Suche “

campushunter.de Hochschulmagazin München WS09

Übungen zu Rechnerarchitektur – Tomasulo’s Algorithm · 2019. 11. 15. · Informatik 12 | DAES Übungen zu Rechnerarchitektur – Tomasulo’s Algorithm – Sommersemester 2017

Fast Algorithm for Mining Association Rules* Vortrag im Rahmen des Seminars Neue Ansätze der Künstlichen Intelligenz Prof. Dr. Katharina Morik Lehrstuhl