Übung 13, Aufgabe 1 - itemsets

Tesla.
Neuling
Neuling
Beiträge: 4
Registriert: 10. Feb 2017 13:11

Übung 13, Aufgabe 1 - itemsets

Beitrag von Tesla. » 10. Feb 2017 13:19

Hallo,

in der Musterlösung zur Übung 13 Aufgabe 1a) steht bei der 3. und 4. Iteration des Apriori Algorithmus dass, "nur die Itemsets zusammengefügt [werden], deren erster Wert gleich ist" bzw. bei der 4. Iteration dass, "Itemsets generiert [werden], indem die ersten beiden Stellen gleich sein müssen."

Was ist hiermit genau gemeint? Wie werden die Itemsets erstellt? Ich hätte einfach wieder alle möglichen Kombinationen gemacht.
EDIT: Vielleicht auch so gefragt: welcher "Wert" muss hier gleich sein?

Danke im Voraus!

Linh
Erstie
Erstie
Beiträge: 17
Registriert: 13. Dez 2010 16:12

Re: Übung 13, Aufgabe 1 - itemsets

Beitrag von Linh » 11. Feb 2017 14:03

Ich vermute ich habe dir die Frage eben schon per Mail beantwortet. Da aber alle bestimmt an der Antwort interessiert sind, hier nochmal die Antwort für alle:

Wenn ich es richtig verstehe, geht es bei dir in der Frage um den Schritt b) im Apriori Step1 Agorithmus und wie dieser in der Musterlösung gelöst ist. Wie du beschreibst kann man korrekterweise für Schritt b) die Kombination aller \(S_{k}\) Itemsets bilden um alle \(C_{k+1}\) Itemsets bestimmen die jeweils k+1 Elemente haben. Was man aber auch machen kann um effektiver Schritt b) und c) gleichzeitig durchzuführen ist Folie 13 des Apriori Foliensatzes, der auch in der Musterlösung angewendet wird. Um diesen anzuwenden, überlegt sich erst eine Sortierung der Items, in dem Fall zum Beispiel einfach alphabetisch.

Wie diese efficient candidate generation funktioniert erkläre ich vielleicht am besten Anhand der Generierung vom \(C_{3}\) und \(C_{4}\):
Dazu verwenden wir folgende Regel von Folie 13:

\(C_{k+1} = \{<X_1, ...
X_{k-1},X_{k},X_{K+1}> | <X_1, ... X_{k-1},X_{k}>
\in S_{k}, <X_1, ... X_{k-1},X_{k+1}> \in S_{k}, X_k
< X_{k+1}\)


D.h. für die Generierung von \(C_{3}\) schauen wir uns \(S_{2}\) an. Dort mergen wir alle Itemsets für die obere Regel zutrifft. In dem Fall ist k=2, da wir \(C_{3}\) berechnen. Damit besagt die Regel, dass wir die Itemsets mergen wo der Part \(<X_{1}>\) der Regel gleich ist und sie sich in dem Rest unterscheiden, wobei \(X_k < X_{k+1}\) sein muss. Das ist der Grund wie auf der Folie 5 der Musterlösung die Aussage "deren erster Wert gleich ist zustande kommt". Wenden wir das nun in einem Beispiel an. Das Itemset <beer, chips> und <beer, dip> sind jeweils gleich im ersten Wert und chips < dip. Ergo ist der Regel nach auch <beer, chips, dip> in \(C_{3}\). Bei der Generierung von \(C_{3}\) trifft der Fall von Pruning nie ein, deswegen erkläre ich dir ihn Anhand der Generierung von \(C_{4}.\)

Für der Generierung von \(C_{4}\) machen wir aber erst mal das gleiche wie bei \(C_{3}\) und schauen dazu uns \(S_{3}\) an (also alle Itemsets auf Folie 5 ohne die Roten). Die Regel besagt nun da k=3, dass wir jeweils Itemsets mergen wo der Part \(<X_{1},X_{2}>\) der Regel gleich ist und sie sich in dem Rest unterscheiden, wobei \(X_k < X_{k+1}\) sein muss. Damit kommt die Aussage auf Folie 6 zustande. Man schaut sich nun die ersten beiden Werte im Itemset an die gleich sein müssen.

Damit würden sich folgende Itemsets für \(C_{4}\) ergeben:
<beer, chips, dip, pizza> und <chips, dip, pizza, wine>

Jetzt kommt der Pruning schritt von der efficient candidate generation. Man schaut ob alle k-subsets von den generierten k+1 Itemsets auch frequent sind. Im Fall des ersten Itemsets ist das: <chips, dip, pizza>, <beer, dip, pizza>, <beer, chips, pizza>, <beer, chips, dip>
Für den Fall des zweiten Itemset ist das: <dip, pizza, wine>, <chips, pizza, wine>, <chips, dip, wine> , <chips, dip, pizza>

Beim zweiten Itemset ist <chips, pizza, wine> nicht in \(S_{3}\) und somit nicht frequent. D.h. das zweite Itemset wird geprunt und man erhält die Lösung der Musterlösung.

Antworten

Zurück zu „Archiv“