Matthias Gläfke Data Mining - Seminar im Sommersemester 2007 2. Vortrag Pincer-Search 5. Juni 2007

Matthias Gläfke

Data Mining - Seminar im Sommersemester 2007

2. Vortrag

Pincer-Search

5. Juni 2007

Überblick

• Grundlagen• Maximum Frequent Set (MFS)• Bekannte Ansätze• Maximum Frequent Candidate Set

(MFCS)• Weg zum Pincer-Search-Algorithmus• Experimente mit Beispieldatenbanken

Grundlagen --> MFS --> Bekannte Ansätze --> MFCS --> Pincer-Search --> Experimente

Definitionen I• I = {i1, … , in} : Menge aller Items („alle

Waren eines Supermarkts“)Hier: I = {1, … , n}

• Itemset X: Kombination von Items („Auswahl von Waren“)

• Transaktion T: Menge von Items („Warenkorb eines Kunden“)

• Datenbank D: Menge von Transaktionen („Einkäufe in einem Zeitraum“)


Frequent Itemset• Ein Itemset X heißt frequent itemset, wenn

sup(X)≥minsup ist. Dabei ist minsup [0,1] der vom Benutzer festgelegte minimal support. Sonst: infrequent itemset

• Wichtige Überlegung:(E1) Ist X infrequent und X Y,

so ist auch Y infrequent(E2) Ist X frequent und Y X,

so ist auch Y frequent


Maximum Frequent Set• Wichtiges Ziel des Data-Mining: frequent

itemsets finden (Assoziationsregeln,…)Wegen (E2): Jedes frequent itemset ist entweder Teilmenge eines anderen frequent itemset oder hat keine Obermenge, die ein frequent itemset ist

• X heißt maximal frequent itemset, falls X ein frequent itemset ist und jede Obermenge von X kein frequent itemset ist

• maximum frequent set (MFS): Menge aller maximal frequent itemsets


Beispiel I• D = { {1,2,3,4,5}, {1,3}, {1,2}, {1,2,3,4} }• minsup = 0,5

• frequent itemsets: {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}

• MFS = { {1,2,3,4} }{1,2,3,4,5}

{1,2,3,4}

{1,2} {1,3} {1,4} {2,3}

{1}{2}{3}{4}

schwarz: frequent itemsetsblau: maximal frequent itemsetsrot: infrequent itemsets

{1,2,3}{1,2,4}{1,3,4}

{5}

{2,3,4}

{2,4} {3,4}


Beispiel II• D = { {1,2,3,5}, {1,5}, {1,2}, {1,2,3} }• minsup = 0,5

• frequent itemsets: {1}, {2}, {3}, {5}, {1,2}, {1,3}, {1,5}, {2,3}, {1,2,3}

• MFS = { {1,2,3}, {1,5} }

{1,2,3,4,5}

{1,2,3}

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

{1}{2}{3} {4} {5}

schwarz: frequent itemsetsblau: maximal frequent itemsetsrot: infrequent itemsets


Bedeutung des MFS• Anschaulich (wie gesehen): MFS bildet

Grenze zwischen frequent und infrequent itemsets

• Klar (wegen (E2)): Mit MFS hat man alle frequent itemsets (Vereinigung der Potenzmengen der Elemente)

• Um (implizit) alle frequent itemsets zu erhalten, suchen wir das MFS!


• Bottom-Up: verwendet (E1), jedes frequent itemset wird explizit untersucht, z.B. Apriori

• Top-Down: verwendet (E2), jedes infrequent itemset wird explizit untersucht

Bekannte Ansätze

{1,2,3,4}

{1,2,3} {1,2,4} {1,3,4} {2,3,4}

{1,2} {1,3} {2,3} {1,4} {2,4} {3,4}

{1} {2} {3} {4} {5}

{1,2,3,4,5}

{1,2,3,4} {1,2,3,5} {1,2,4,5} {1,3,4,5} {2,3,4,5}

{1,2,5} {1,3,5} {1,4,5} {2,3,5} {2,4,5} {3,4,5}

{1,5} {2,5} {3,5} {4,5}

{5}


Probleme• Diese Ansätze haben nur dann eine gute

Performance, wenn die Elemente des MFS sehr kurz oder sehr lang sind (Berechnen des Supports ist teuer!)

• Idee: (E1) und (E2) verwenden!{1,2,3,4,5}

{1,2,3,4} {1,3,4,5} {1,2,3,5} {1,2,4,5} {2,3,4,5}

{1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2,5} {1,3,5} {1,4,5} {2,3,5} {2,4,5} {3,4,5}

{1,2} {1,3} {1,4} {2,3} {2,4} {3,4} {1,5} {2,5} {3,5} {4,5}

{1} {2} {3} {4} {5}

schwarz: frequent itemsetsblau: maximal frequent itemsetsrot: infrequent itemsetsgrün: nicht untersuchte itemsets


Neue Menge: MFCS• Ziel: Performance verbessern (Anzahl der

Kandidaten) durch Koordination der beiden Ansätze• Dazu wird eine neue Menge eingeführt:

maximum frequent candidate set• Enthält die längsten itemsets, die noch nicht als

infrequent identifiziert wurden• Formaler:

– Potenzmengen sämtlicher Elemente enthalten keine infrequent itemsets

– Alle frequent itemsets sind in der Vereinigung der Potenzmengen sämtlicher Elemente enthalten

– Kleinstmöglich (minimale Kardinalität)


Was macht das MFCS?• In jedem Durchgang wird der support der Bottom-

up-Kandidaten und der Elemente des MFCS berechnet– Falls Element des MFCS frequent alle Untermengen sind

frequent Element kommt ins MFS– Falls Bottom-up-Kandidat infrequent MFCS aktualisieren

• Effiziente Koordidation von Bottom-up- und Top-down-Suche! n -itemset

Top-down search cango down many levels in one pass

Bottom-up search1-itemsets goes up one level in one pass

: denotes the maximal frequent itemsets


Beispiel• Zu Beginn setzt man MFCS = { {1, … , n} }• 1. Durchgang:

• Setze MFCS = { {1, … , m} }

{1} {2} {m} {m+1} {n}

{1, ... , m}

{1, ... , m, m+1, ... , n}


Aktualisierung des MFCS• Situation: Ein k-itemset Y wird als infrequent

identifiziert• Erinnerung (Def.): Dann ist Y X für ein X

MFCS• Um die Eigenschaften zu erhalten, muss MFCS

aktualisiert werden!• Idee: Sei M = {X MFCS | Y X , Y infrequent}.

– Ist X M, so streiche X aus MFCS und generiere |Y|=k neue Itemsets Xi’ = X\{yi} (i = 1, ... , k)

– Füge die Xi’ in MFCS ein, die dort keine Obermenge haben


Beispiel zu MFCS-gen• Sei MFCS = { {1,2,3,4,5,6} } sowie {1,6} und

{3,6} die neu entdeckten infrequent itemsets. • Betrachte zunächst {1,6} M =

{ {1,2,3,4,5,6} }– Setze MFCS = Ø, X’1 = {2,3,4,5,6}, X’2 = {1,2,3,4,5}– Setze MFCS = { {2,3,4,5,6}, {1,2,3,4,5} }

• Betrachte nun {3,6} M = { {2,3,4,5,6} }– Setze MFCS = { {1,2,3,4,5} }, X’1 = {2,4,5,6}, X’2 =

{2,3,4,5}– Setze MFCS = { {1,2,3,4,5}, {2,4,5,6} }

(Beachte: {2,3,4,5} {1,2,3,4,5} !)


Algorithmus MFCS-gen

Input: Old MFCS, infrequent set Sk found in pass kOutput: New MFCS1: for all itemsets s Sk2: for all itemsets m MFCS3: if s is a subset of m4: MFCS := MFCS \ m5: for all items e itemset s6: if m\{e} is not a subset of any itemset in the MFCS7: MFCS := MFCS UNION m\{e}8: return MFCS


Ein weiteres Problem• Betrachte folgendes Beispiel:

L3 = { {1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5},{1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {2,4,6}, {2,5,6}, {3,4,5}, {4,5,6} }

• Mit der Apriori-Search ist dann C4 = { {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, {2,4,5,6} }


Ein weiteres Problem• L3 = { {1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5},

{1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {2,4,6}, {2,5,6}, {3,4,5}, {4,5,6} }

• Was kann bei Pincer-Search passieren?Sei X = {1,2,3,4,5} MFCS als frequent bekannt. Dann wird X ins MFS eingefügt, und alle Untermengen von X werden nicht mehr betrachtet L3 = { {2,4,6}, {2,5,6}, {4,5,6} }

• Apriori-join liefert keine neuen Elemente!• Aber: Es müsste C4 = { {2,4,5,6} } gelten!

(Erinnerung: C4 = { {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, {2,4,5,6} })


Itemsets wiederherstellen• Wie erhält man die evtl. in Ck+1 fehlenden

Itemsets?• Vorüberlegung: Ist X Ck+1, so müssen

Teile von X sicherlich aus Itemsets aus Lk bestehen.

• Idee: Die „verloren gegangenen“ k-Itemsets werden wiederhergestellt, aber nur die, die man auch tatsächlich mit Elementen von Lk joinen kann, also solche mit dem gleichen k-1-Präfix wie ein Element aus Lk


Itemsets wiederherstellen• Sei X = {x1, … , xk, xk+1, … , xl} MFS,

Y = {y1, … , yk} Lk mit l > k und y1, … , yk-1 X, yk-1 = xj für ein j

• Setze Y’j+1 = {y1 , … , yk-1, xj+1 } Y’j+2 = {y1 , … , yk-1, xj+2 }

. . . . . .

Y’l = {y1 , … , yk-1, xl } • Diese Y’i sind sicherlich frequent!• Füge die Y’i in Lk ein und wende dann

Apriori-join an


Beispiel (Fortsetzung)• L3 = { {2,4,6}, {2,5,6}, {4,5,6} },

X = {1,2,3,4,5} MFCS sei als frequent bekannt.• Beginne mit Y = {2,4,6}

– Dann sind y1, y2 X und y2 = x4. – Setze dann Y’5 = {2,4,5}

• Sei nun Y = {2,5,6}– Dann sind y1, y2 X und y2 = x5. – Es werden keine neuen itemsets generiert

• Für Y = {4,5,6} erhält man ebenfalls keine neuen itemsets• Man erhält L3 = { {2,4,6}, {2,5,6}, {4,5,6}, {2,4,5} }• Durch Apriori-join: C4 = { {2,4,5,6} }


Algorithmus Recovery

Input: Ck+1 from Apriori-join procedure, Lk, current MFSOutput: complete candidate set Ck+11: for all itemsets l Lk2: for all itemsets m MFS 3: if the first k-1 items in l are also in m4: /* suppose m.itemj = l.itemk-1 (!!) */5: for i from j+1 to |m|6: Ck+1 := Ck+1 UNION { {l.item1, l.item2, … , l.itemk, m.itemi} }7: /* the new elements are {l.item1, l.item2, … ,l.itemk-1, l.itemk }8: join {l.item1, l.item2, … ,l.itemk-1, m.itemi } */


Weitere Kandidaten streichen• Stand: Ck+1 wurde durch Apriori-join

und Recovery bestimmt• Es können noch weitere Kandidaten

gestrichen werden:• Hat ein Kandidat keine Obermenge im

MFCS, so ist er nach Defintion des MFCS sicherlich nicht frequent


• Insgesamt ergibt sich damit der Pincer-Search-Algorithmus

Algorithmus New prune

Input: current MFCS and Ck+1 after Apriori-join and recovery procedureOutput: final candidate set Ck+11: for all itemsets c Ck+12: if c is not a subset of any itemset in the current MFCS3: delete c from Ck+1


Algorithmus Pincer-SearchInput: a database and a user-defined minimum supportOutput: MFS which contains all maximal frequent itemsets1: L0 := Ø; k := 1; C1 := { {i} | i {1,2, … , n } }2: MFCS := { {1,2, … , n} }, MFS := Ø 3: while not Ck = Ø 4: read database and count supports for Ck and MFCS5: remove frequent frequent itemsets from MFCS and add them to MFS6: Lk := { frequent itemsets in Ck} \ { subsets of MFS }7: Sk := { infrequent itemsets in Ck } 8: call the MFCS-gen algorithm if not Sk = Ø 9: call the Apriori-join procedure to generate Ck+110: if any frequent itemset in Ck is removed in line 511: call recovery procedure to recover candidates to Ck+112: call new prunce procedure to prune candidates in Ck+113: k := k+114: end-while15: return MFS


Beispiel• D = { {1,2,3,4,5}, {1,3}, {1,2}, {1,2,3,4} }, minsup = 0,5• L0 = Ø, C1 = {{1},{2},{3},{4},{5}}, MFCS = {{1,2,3,4,5}}, MFS =

Ø• k=1

– sup({1}) = 1 , sup({2}) = 0,75 , sup({3}) = 0,75 , sup({4}) = 0,5 , sup({5}) = 0,25 , sup({1,2,3,4,5}) = 0

– L1 = {{1},{2},{3},{4}} , S1 = {{5}} MFCS = {{1,2,3,4}}– C2 = {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}

• k=2– sup({1,2}) = 0,75 , sup({1,3}) = 0,75 , sup({1,4}) = 0,5 , sup({2,3}) =

0,5 , sup({2,4}) = 0,5 , sup({3,4}) = 0,5 , sup({1,2,3,4}) = 0,5 – MFCS = Ø , MFS = {{1,2,3,4}}– L2 = Ø , S2 = Ø

• Output: MFS = {{1,2,3,4}}• Pincer-Search: 2 Schritte, Bottom-up: 4 Schritte, Top-Down: 5 Schritte


Vorbemerkungen• Für die Experimente wird nicht der

(Basis-) Algorithmus von oben verwendet

• Manchmal ist der Unterhalt des MFCS zu teuer (z.B. bei viele infrequent 2-itemsets)

• Die im Folgenden benutzte angepasste Version von Pincer-Search verzichtet so lange auf das MFCS, bis der Nutzen die Kosten übersteigt!


Beobachtung• Gibt es einen Zusammenhang zwischen der

Anzahl der maximal frequent itemsets und dem minimal support?

• Klar: Verringert man den minimal support, so vergrößert sich die Gesamtzahl der Kandidaten

• Beispiel:– D = { {1,2,3,4,5}, {1,3}, {1,2}, {1,2,3,4} }– minsup = 0,5: MFS = {{1,2,3,4}}– minsup = 0,75: MFS = {{1,2},{1,3}}


Beobachtung• Es gibt also keine solche „Monotonie“

bei der Anzahl der Elemente des MFS• Folgerung:

– Für Bottom-Up-Algorithmen vergrößert sich bei verringertem minsup die Rechenzeit, die Suche nach dem MFS dauert länger.

– Bei verringertem minsup wird die Länge der Elemente des MFS i.A. größer, werden diese vom MFCS schneller erreicht (von oben). Hier sind Vorteile für Pincer-Search zu erwarten!


Verteilungen• Grundsätzlich kann man zwei Verteilungen

unterscheiden:• scattered: viele kurze

maximal frequent itemsets• concentrated: wenige lange

maximal frequent itemsets

• Im zweiten Fall sind Vorteile für Pincer-Search zu erwarten!


Scattered distributions I

sämtliche Grafiken auf den folgenden Folien wurden übernommen aus:Lin / Kedem: Pincer Search: A new algorithm for Discovering the Maximum Frequent Set, 2002


Scattered distributions II


Scattered distributions III


Concentrated distributions I


Concentrated distributions II


Concentrated distributions III


Aktienmarkt-Datenbank

Documents

Matthias Gläfke Data Mining - Seminar im Sommersemester 2007 2. Vortrag Pincer-Search 5. Juni 2007