Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionNext revisionBoth sides next revision | ||
data_mining:association_rules [2013/03/30 22:24] – [FP-Trees] phreazer | data_mining:association_rules [2013/03/30 23:24] – [Phase 2] phreazer | ||
---|---|---|---|
Line 19: | Line 19: | ||
==== Phase 1 ==== | ==== Phase 1 ==== | ||
Aufgabe: Sortieren der Frequent Items | Aufgabe: Sortieren der Frequent Items | ||
+ | |||
Ausgangspunkt: | Ausgangspunkt: | ||
Line 27: | Line 28: | ||
| 4 | b,f,k,s,p | f,b,p | | | 4 | b,f,k,s,p | f,b,p | | ||
| 5 | a, | | 5 | a, | ||
+ | |||
+ | ==== Phase 2 ==== | ||
+ | Aufgabe: Aufbau des FP-Tree | ||
+ | |||
+ | Zwei Bestandteile: | ||
+ | - Baumstruktur | ||
+ | - Wuzelelement mit " | ||
+ | - Geordnete Transaktion als Pfad des Baumes | ||
+ | - Item-Prefix Subtrees bestehen aus Itemname, Häufigkeit, | ||
+ | - 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, | ||
+ | - insert_tree([p|P], | ||
+ | |||
+ | 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 | ||
+ | |||
+ | |||
+ | |||
+ | |||