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

Fast Algorithm for Mining Association Rules*

Vortrag im Rahmen des Seminars

Neue Ansätze der Künstlichen Intelligenz

Prof. Dr. Katharina Morik

Lehrstuhl für Künstliche Intelligenz

Mike [email protected]

28. Mai 2002

* Rakesh Agrawal, Ramakrishnan Srikant, 20th VLDB Conference Santiago, Chile

Fast Algorithmus for Mining Association Rules 28.05.2002Mike Duhm Seite 2


Gliederung des Vortrages:

1. Einleitung

2. Der APRIORI Algorithmus

3. Fazit

4. Literatur



1. Einleitung

Heranführung an den Algorithmus durch Informelle Darstellung des Problembereichs

Formalisierung

Probleme / Lösungsansätze



1. Einleitung

Informelle Darstellung des Problembereiches: Durch die weit verbreitete Barcode Technik können heute riesige

Mengen an Verkaufsdaten gesammelt und gespeichert werden, so

genannte Warenkorb-Daten.

Grosses Interesse im Marketing: Analyse auf immer wieder

kehrende Zusammenhänge (->Assoziationen) zwischen gekauften

Produkten.

Wer Brot und Butter kauft, kauft oft auch Marmelade

Bier, Pizza → Chips

Nutzung der Erkenntnisse zur Aufstellung des Warensortiments,

für Werbemaßnahmen, Katalogdesign,...



1. Einleitung

Formalisierung

I={i1, i2, ...,in} (Menge der Items -> „Warensortiment“)

D : Menge der Transaktionen T und TI (-> „Warenkörbe“)

Jede Transaktion bekommt einen eindeutigen Bezeichner TID.

Eine Assoziationsregel ist eine Implikation X=>Y, wobei X,Y I,

und XY=.



1. Einleitung

Formalisierung (Teil 2) Eine Regel X=>Y hat support s, wenn in s% der Transaktionen aus

D XY auftritt.

Einer Regel X=>Y hat confidence c, wenn c% der Transaktionen

aus D die X enthalten auch Y enthalten.



1. Einleitung

Probleme / Lösungsansätze Warenhaussortimente bestehen aus tausenden von Artikeln.

Jede Transaktionen Tist Element der Potenzmenge von I, es gibt

also potenziell in der Anzahl der Items viele verschiedene, und

darin eine riesige Menge möglicher Assoziationsregeln!

Ein Anwender hätte sehr viele Hypothesen aufzustellen.

Naives Herangehen an das Problem würde horrende Laufzeiten

verursachen



1. Einleitung

Probleme / Lösungsansätze Das hier vorgestellte Verfahren kommt ohne Hypothesen aus. Ein

Anwender muss nur Daten hineinwerfen und er erhält fertige

Assoziationsregeln.

support und confidence werden genutzt um „wirkliche Regeln“

herauszufinden.

Der Benutzer muss also minsup (minimaler support) und minconf

(minimale confidence) festlegen. Typische Werte sind: minsup = 0.01,

minconf = 0.25. Itemsets deren support ≥ minsup ist werden im

Folgenden häufig genannt.

Bottom-Up Vorgehen macht die Laufzeit handhabbar.



1. Einleitung

Algorithmisches Vorgehen

Einteilung des Problems in zwei Teilprobleme

Finden aller häufigen Itemsets

Hierfür werden wir die Algorithmen Apriori (und im Weiteren auch

AprioriTid und AprioriHybrid) behandeln

Benutzung die gefundenen häufigen Itemsets zum Generieren der

Assoziationsregeln

Hierauf gehe ich nicht weiter ein. Nur soviel:

Für alle häufigen Itemsets l und hier wiederum für alle Teilmengen a

muss die confidence der Regel (l-a)=>a berechnet und mit minconf

verglichen werden.



2. Der Apriori Algorithmus

Kapitelaufbau Finden der häufigen Itemsets

Struktur des Algorithmus

Konventionen und Notation

Der eigentliche Algorithmus

Subroutinen




Finden der häufigen Itemsets

Das Besondere des Algorithmus ist die bottom-up-Vorgehensweise:

Erst finden der einzelnen Items, welche häufig sind.

Daraus Aufbau der zweielementigen Kandidaten

Herausschmeissen der Kanditaten, die Teilmengen enthalten, welche

nicht häufig sind.

Überprüfung der Kandidaten, ob diese wiederum häufig sind an Hand

der Datenbasis.

Iteratives Vorgehen bis keine neuen häufigen Itemsets mehr

gefunden werden können.




Finden der häufigen Itemsets

Beispiel:




Struktur des Algorithmus:

Apriori

Kandidaten-

generierungÜberprüfung

auf Häufigkeit

Zusammenfüh-

rung (join)Beschneidung

(prune)




Konventionen und Notation : Items in einer Transaktion sowie innerhalb der Itemsets sind in

lexikographischer Ordnung.

Die Datenbank besteht aus Einträgen der Form <TID, item>.

Ein k-Itemset ist ein Itemset der Grösse k

Gebunden an jedes Itemset ist ein Zählerfeld, welches mit 0

initialisiert wird

Lk ist eine Menge von häufigen k-Itemsets

Ck ist eine Menge von k-Kandidaten-Itemsets




Endlich - der eigentliche Algorithmus1. L1 = {häufige 1-Itemsets};

2. for ( k=2 ; Lk-1 ≠ { } ; k++ ) do begin

3. Ck = apriori-gen( Lk-1); // neue Kandidaten werden erzeugt

4. forall Transaktionen t D do begin

5. Ct = subset(Ck,t) ; // in t enthaltene Kandidaten

6. forall Kandidaten c Ct do

7. c.count++;8. end

9. Lk = {c Ck I c.count >= minsup}

10. end

11. return: k Lk




Kandidatengenerierung mit apriori-gen

Schritt 1: join

Aus je zwei Itemsets aus Lk-1 wird ein neuer Kandidat der Größe k.

Insert into Ck

select p.item1, p.item2, …p.itemk-1,q.itemk-1

from Lk-1 p, Lk-1 q

where p.item1=q.item1,….,.itemk-2=q.itemk-2 p.itemk-1<q.itemk-1




Kandidatengenerierung mit apriori-gen

Schritt 2: prune

Kandidaten, welche nicht-häufige Subsets enthalten fallen heraus.

Hierbei werden nur (k-1)-subsets der Kandidaten betrachtet.

forall itemsets cCk do

for all (k-1) –subsets of c do

if ( sLk-1) then delete c form Ck




Die Subroutine subset

Wir speichern unsere Kandidaten aus Ck in einem hash-tree.

Jeder Knoten ist entweder hash-Tabelle – wenn er innerer Knoten

ist – oder Container sonst.

Jeder bucket einer hash-table in einem Knoten mit Tiefe d zeigt

auf Knoten mit Tiefe d+1.

Zum Speichern wird der Baum traversiert, wobei auf Tiefe d die

Hashfunktion auf das d-te Item angewendet wird.

Alle Knoten starten als Container und werden erst zu hash-

Tabellen, wenn sie „überfüllt“ werden




Die Subroutine subset (Teil 2)

Finden aller Kanditaten, die in Transaktion T vorhanden sind:

Der Baum wird von der Wurzel aus traversiert.

Wenn an einem Blatt angekommen, wird der passende Kandidat in

die Ausgabemenge geworfen

Wenn ein innerer Knoten durch Anwendung der Hashfunktion auf

Item i erreicht worden ist, wird an diesem die Hashfunktion auf

alle folgenden items der Transaktion angewendet.

Die Korrektheit folgt aus der Anwendung dieses Verfahrens auf

die Wurzel




Die Subroutine subset (Teil 3)

Beispiel:




Modifikation

Im Nachfolgenden gehe ich kurz auf folgende Modifizierten Versionen

des Algorithmus ein:

AprioriTID

AprioriHybrid




AprioriTID

Der gerade vorgestellte Algorithmus hat gegenüber anderen

Performance-Vorteile, jedoch muss nach jeder Kandidatengenerierung

die Datenbank komplett durchsucht werden.

Idee: Speichern der TID an den Kandidaten, die zugehörige Transaktion

enthält.

Vorteil:

Die support-Bestimmung kommt ohne weitere Datenbankdurchläufe

aus.

Nachteil:

Bei niedrigem k-Wert wird viel Speicherplatz benötigt!




AprioriTID

Die Kombination von Apriori und AprioriTID liefert den AprioriHybrid

Algorithmus.

Für niedrige k-Werte Nutzung von Apriori

Für hohe k-Werte Nutzung von AprioriTID

=> Stärken beider Algorithmen werden kombiniert.



3. Fazit

Pro: Die beide vorgestellten Algorithmen, insbesondere die daraus

resultierende Hybrid-Lösung arbeiten im Vergleich zu früheren

Ansätzen (AIS, SETM) mit hoher Performanz.

Aber: Was ist, wenn man das Sortiment hierarchisch betrachtet?

Es kann gezeigt werden, dass nicht nur sinnvolle Regeln geliefert

werden:

Beispiel: Betrachtung der CENSUS Datenbank 1990

Militärische Aktivität in der Vergangenheit => Kein Dienst in Vietnam

liefert confidence von 0.9



3. Fazit

Es gibt sicherlich noch einige andere Aspekte, aber

Insgesamt haben wir hier eine gut anwendbare Methode

kennengelernt, die spätestens auf den zweiten Blick auch

verständlich und handhabbar ist.



Literatur:

1. R. Agrawal, R. Srikant. Fast Algorithm for Mining Association Rules. In Proc. Of the 20th VLDB Conference Santaigo, Chile, 1994

2. Kapitel Maschinelles Lernen (und Data Mining) von K. Morik aus

G. Görz, J. Schneeberger und C.-R. Rollinger (Hrsg.) Handbuch der

KI. Oldenbourg Verlag

3. F. Berzal, I. Blanco, D. Sánchez, M.-A. Vila. A New Framework to

Assess Association Rules.



Fast Algorithm for Mining Association Rules

Vielen Dank für Eure Aufmerksamkeit :-)

Documents

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