data_mining:association_rules

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
data_mining:association_rules [2013/03/30 22:24] – [FP-Trees] phreazerdata_mining:association_rules [2014/02/11 21:49] (current) – external edit 127.0.0.1
Line 19: Line 19:
 ==== Phase 1 ==== ==== Phase 1 ====
 Aufgabe: Sortieren der Frequent Items Aufgabe: Sortieren der Frequent Items
 +
 Ausgangspunkt: Frequent Item List L=<c:4,f:4,a:3,b:3,m:3,p:3> Ausgangspunkt: Frequent Item List L=<c:4,f:4,a:3,b:3,m:3,p:3>
  
Line 27: Line 28:
 | 4 | b,f,k,s,p | f,b,p | | 4 | b,f,k,s,p | f,b,p |
 | 5 | a,f,c,e,l,p,m,n | c,f,a,m,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
 +
 +
 +<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>
 +
 +
 +
  
  • data_mining/association_rules.1364678692.txt.gz
  • Last modified: 2014/02/11 21:47
  • (external edit)