Table of Contents

Association Rules Mining

Mining Algorithmen

  1. Apriori
    1. Naiv
    2. Multi-Dimensionale Association Rules
    3. Multi-Level Association Rules
      1. Alternative Variante
    4. Level Crossing association Rules
    5. Optimierung
      1. Direct Hashing and Pruning
      2. Sampling
      3. Apriori B
  2. FP-Tree
    1. 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

  1. Wuzelelement mit “null” als Label
  2. Geordnete Transaktion als Pfad des Baumes
  3. Item-Prefix Subtrees bestehen aus Itemname, Häufigkeit, Node-link (Links zu nächstem Knoten, mit gleichem Itemnamen)

- Frequent-Item-Header-Tabelle

  1. Itemname
  2. Head of node-link: Ein Zeiger auf den ersten Knoten mit dem Itemnamen
  3. 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:

  1. Erstelle sortierte Frequent-Item-Liste[p|P] für die Transaktion, rufe insert_tree([p|P],T) auf.
  2. 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

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)))
}