Differences

This shows you the differences between two versions of the page.

--- data_mining:association_rules [2013/03/30 22:34] – [Phase 1] phreazer
+++ data_mining:association_rules [2013/03/30 23:39] – [Phase 3] phreazer
@@ Line 41: / Line 41: @@
   - Head of node-link: Ein Zeiger auf den ersten Knoten mit dem Itemnamen
   - Optional ein Support Count eines Items.
+=== FP-Tree Erzeugung ===
+Input: DB und Minimum Support Grenzwert.
+Output: FP-tree, das Häufigkeitsmuster der DB
+Phase 1 (siehe oben): Einmaliges Scannen der DB. Sammeln der Menge der frequent Items F und Support jedes frequent Items. Sortieren von F dem Support nach absteigend, als Liste der Frequent Items FList.
+Phase 2: Wurzelknoten eines FP-Tree T erzeugen und für jede Transaktion in der DB folgendes durchführen:
+  - Erstelle sortierte Frequent-Item-Liste[p|P] für die Transaktion, rufe insert_tree([p|P],T) auf.
+  - insert_tree([p|P],T): Wenn T ein Kind N hat, sodass N.itemname=p.itemname, dann inkrementiere den Count um 1, sonst erstelle einen neuen Knoten N, mit Initialcount 1, dessen Parent mit T verbunden ist und dessen Nodelink mit den Knoten mit den gleichen Itemnamen durch die Nodelink-Struktur verbunden sind. Wenn P nichtleer ist, rufe (P, N) rekursiv auf
+Es werden 2 Scans benötigt: Scan 1 sammelt und sortiert die Menge der Frequent Items, Scan 2 erstellt FP-Tree.
+==== Phase 3 ====
+Aufgabe: Extrahieren des Frequent Itemsets aus FP-Tree (FP-Growth Algorithmus)
+Input: DB in Form eines FP-Trees und Minimumsupport Grenzwert.
+Output: Vollständige Menge der Fequent Patterns
+<code>
+Procedure FP-growth(Tree, a) {
+(01) Wenn Baum einen einzelnen Prefixpfad enthält, dann mine diesen Pfad {
+  (02) P sei der einzelne Prefixpfadteil des Baumes;
+  (03) Q sei der vielpfadige Teil mit dem oberen Verzweigungsknoten, der durch eine null-Wurzel ersetzt wurde;
+  (04) Für jede Kombination (bezeichnet als ß) der Knoten im Pfad p:
+  (05) Erzeuge Muster ß ∪ a mit Support = minimum support der Knoten in ß;
+  (06) Frequent Patternset P sei die Menge der so erzeugten Patterns;
+}
+(07) sonst sei Q ein Baum;
+(08) Für jedes Item ai in Q { // Mining multipath FP-tree
+  (09) Erzeuge Pattern ß = ai ∪ a mit support = ai.support;
+  (10) construct ß’s conditional pattern-base and then ß’s conditional FP-tree Tree ß;
+  (11) if Tree ß ≠ Ø then
+    (12) call FP-growth(Tree ß , ß);
+  (13) let freq pattern set(Q) be the set of patterns so generated;
+}
+(14) return(freq pattern set(P) ∪ freq pattern set(Q) ∪ (freq pattern set(P) × freq pattern set(Q)))
+}
+</code>