Differences

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

--- data_mining:association_rules [2013/03/30 19:53] – angelegt phreazer
+++ data_mining:association_rules [2013/03/30 23:24] – [Phase 2] phreazer
@@ Line 13: / Line 13: @@
   - FP-Tree
     - Projected Databases
+===== FP-Trees =====
+FP-Growth Algorithmus verwendet "Divide and conquer"-Strategie. Spezielle Datenstruktur sind die Frequent-Pattern Trees.
+==== Phase 1 ====
+Aufgabe: Sortieren der Frequent Items
+Ausgangspunkt: Frequent Item List L=<c:4,f:4,a:3,b:3,m:3,p:3>
+^ TID      ^ Items       ^ Sortierte häufige Items          ^
+| 1 | f,a,c,d,h,i,m,p | c,f,a,m,p |
+| 2 | a,b,c,f,l,m,o | c,f,a,b,m |
+| 3 | b,c,h,j,o | c,b |
+| 4 | b,f,k,s,p | f,b,p |
+| 5 | a,f,c,e,l,p,m,n | c,f,a,m,p |
+==== Phase 2 ====
+Aufgabe: Aufbau des FP-Tree
+Zwei Bestandteile:
+- Baumstruktur
+  - Wuzelelement mit "null" als Label
+  - Geordnete Transaktion als Pfad des Baumes
+  - Item-Prefix Subtrees bestehen aus Itemname, Häufigkeit, Node-link (Links zu nächstem Knoten, mit gleichem Itemnamen)
+- Frequent-Item-Header-Tabelle
+  - Itemname
+  - 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