This is an old revision of the document!
Association Rules Mining
Mining Algorithmen
- Apriori
- Naiv
- Multi-Dimensionale Association Rules
- Multi-Level Association Rules
- Alternative Variante
- Level Crossing association Rules
- Optimierung
- Direct Hashing and Pruning
- Sampling
- Apriori B
- 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.