Leer Het Construeren van Frequente Patroonbomen met het FP-Growth-algoritme | Hoogwaardige Regelmijnbouw en Schaaloptimalisatie

Veeg om het menu te tonen

FP-Growth Overzicht

FP-Growth is een high-performance algoritme ontworpen voor het ontdekken van frequente itemsets in grote transactionele datasets. In tegenstelling tot Apriori, dat kandidaat-itemsets genereert en de database herhaaldelijk scant, bouwt FP-Growth een compacte datastructuur genaamd de FP-Tree (Frequent Pattern Tree), waarmee frequente patronen kunnen worden gevonden zonder kandidaatgeneratie. Dit resulteert in aanzienlijke verbeteringen in snelheid en geheugengebruik, vooral bij datasets met veel frequente patronen.

Boomstructuur

De FP-Tree-structuur comprimeert de volledige set transacties in een prefix-boomformaat. Elke transactie wordt verwerkt door de items te sorteren in aflopende volgorde van frequentie en deze vervolgens in de boom te plaatsen, waarbij gemeenschappelijke prefixen met bestaande paden worden gedeeld. De wortelknoop is een null-knoop die als ingangspunt dient, en elke knoop in de boom vertegenwoordigt een item samen met een telling van het aantal transacties dat die prefix tot dat punt deelt.

Knoopkoppeling

Om efficiënt te kunnen minen, worden alle knopen die hetzelfde item vertegenwoordigen met elkaar verbonden via een gekoppelde lijst, wat een header table wordt genoemd. Hiermee kan snel door alle voorkomens van een bepaald item in de boom worden genavigeerd. Elke invoer in de header table wijst naar de eerste knoop in de boom voor dat item, en elke knoop bevat een link naar de volgende knoop met dezelfde itemnaam.

Patronen minen

Het minen van frequente patronen uit de FP-Tree bestaat uit twee hoofdonderdelen. Eerst wordt de boom van onder naar boven doorlopen, waarbij de koppelingen voor elk item in de header table worden gevolgd om alle prefixpaden te verzamelen die naar dat item leiden. Vervolgens worden conditionele FP-Trees voor elk item geconstrueerd en recursief gemined om alle frequente itemsets te extraheren. Dit recursieve proces gaat door totdat er geen frequente patronen meer gevonden kunnen worden.

Voorbeeld: Stapsgewijze FP-Tree-constructie

Laten we de exacte stapsgewijze constructie doorlopen met jouw voorbeeldtransacties, uitgaande van een minimale supportdrempel van 2 (wat betekent dat items minstens twee keer moeten voorkomen om mee te tellen).

Stel dat je de volgende transacties hebt:

- Transactie 1: A, B, D;
- Transactie 2: B, C, E;
- Transactie 3: A, B, C, E;
- Transactie 4: B, E.

Stap 1: Scan de database en sorteer op frequentie

Eerst leest het algoritme de volledige dataset om te tellen hoe vaak elk individueel item voorkomt. Elk item dat onder de minimale supportdrempel valt, wordt verwijderd. Vervolgens wordt een globale sorteervolgorde vastgesteld van hoog naar laag op basis van frequentie.

Globale itemtelling:

B komt 4 keer voor

E komt 3 keer voor

A komt 2 keer voor

C komt 2 keer voor

D komt 1 keer voor (Verwijderd omdat dit minder is dan de minimale support van 2)

De uiteindelijke sorteervolgorde: Elke transactie wordt nu gefilterd en herschikt om strikt deze aflopende frequentievolgorde te volgen:

$\mathbf{B} \longrightarrow \mathbf{E} \longrightarrow \mathbf{A} \longrightarrow \mathbf{C}$

Stap 2: Herschik elke transactie

Voordat items in de boom worden geplaatst, herschrijft het algoritme elke transactie. Het verwijdert het infrequente item (D) en herschikt de overgebleven items volgens de nieuwe globale sorteervolgorde.

- Transactie 1: A, B, D wordt B, A
- Transactie 2: B, C, E wordt B, E, C
- Transactie 3: A, B, C, E wordt B, E, A, C
- Transactie 4: B, E wordt B, E

Stap 3: Voeg paden toe aan de FP-Tree

Elke FP-Tree begint met een lege aanduiding, de Null Root Node. We voegen nu onze nieuw herschikte transacties één voor één toe aan de boom, waarbij tellers worden verhoogd als paden overlappen en vertakkingen ontstaan als ze afwijken.

Voeg transactie 1 {B, A} toe: de boom maakt een geheel nieuwe tak direct vanaf de root.

Voeg transactie 2 {B, E, C} toe: het algoritme start bij de root en controleert het eerste item, B. Omdat B al als kind van de root bestaat, overlapt het pad! Het algoritme gaat naar B en verhoogt zijn teller naar 2. Het volgende item is E. Omdat B nog geen kind E heeft, splitst de boom hier en wordt een nieuwe sub-tak voor E aangemaakt, gevolgd door C.

Voeg transactie 3 {B, E, A, C} toe: beginnend bij de root, raakt het pad B (teller naar 3), vervolgens naar de bestaande E-node (teller naar 2). Het volgende item is A. Omdat E nog geen kind A heeft, maakt de boom een nieuwe splitsing onder E voor (A:1) -> (C:1).

Voeg transactie 4 {B, E} toe: het algoritme volgt het populairste prefixpad en B wordt verhoogd naar 4, E naar 3. De transactie eindigt hier, dus er worden geen nieuwe nodes toegevoegd.

(Null Root) | (B: 4) / \ (A: 1) (E: 3) / \ (C: 1) (A: 1) | (C: 1)


              12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
            
transactions = [
    ['A', 'B', 'D'],
    ['B', 'C', 'E'],
    ['A', 'B', 'C', 'E'],
    ['B', 'E']
]

# Step 1: Counting item frequency
from collections import defaultdict, Counter

item_counts = Counter()
for transaction in transactions:
    item_counts.update(transaction)

# Step 2: Removing infrequent items
min_support = 2
freq_items = {item for item, count in item_counts.items() if count >= min_support}

# Step 3: Sorting items in each transaction by frequency
def sort_transaction(transaction):
    return sorted([item for item in transaction if item in freq_items],
                  key=lambda item: (-item_counts[item], item))

sorted_transactions = [sort_transaction(t) for t in transactions]

# Step 4: Defining FP-Tree node class
class FPTreeNode:
    def __init__(self, item, count, parent):
        self.item = item
        self.count = count
        self.parent = parent
        self.children = {}
        self.link = None  # Node link for header table

# Step 5: Building the FP-Tree and header table
def build_fp_tree(transactions):
    root = FPTreeNode(None, 1, None)
    header_table = defaultdict(list)

    for transaction in transactions:
        current = root
        for item in transaction:
            if item not in current.children:
                current.children[item] = FPTreeNode(item, 1, current)
                header_table[item].append(current.children[item])
            else:
                current.children[item].count += 1
            current = current.children[item]
    # Linking nodes in header table
    for item, nodes in header_table.items():
        for i in range(len(nodes) - 1):
            nodes[i].link = nodes[i + 1]
    return root, header_table

fp_root, header_table = build_fp_tree(sorted_transactions)

# Step 6: Printing the FP-Tree
def print_tree(node, indent=0):
    if node.item is not None:
        print('  ' * indent + f"{node.item}:{node.count}")
    for child in node.children.values():
        print_tree(child, indent + 1)

print_tree(fp_root)

Dit codevoorbeeld laat zien hoe je een FP-Tree construeert uit een lijst van transacties met behulp van Python. Hier volgt een gedetailleerde uitleg van elke stap:

Frequenties van items tellen:
- De code gebruikt de Counter-klasse uit de collections-module om te tellen hoe vaak elk item voorkomt in alle transacties;
- Dit helpt om te bepalen welke items vaak genoeg voorkomen om in de boom te worden opgenomen.
Verwijderen van infrequente items:
- Items die niet voldoen aan de minimale supportdrempel worden eruit gefilterd;
- De set freq_items bevat alleen items die minstens zo vaak voorkomen als gespecificeerd door min_support.
Transacties sorteren op frequentie:
- Elke transactie wordt gefilterd zodat alleen frequente items overblijven;
- De items worden vervolgens gesorteerd in aflopende volgorde van hun globale frequentie (en alfabetisch bij gelijke frequentie);
- Sorteren maximaliseert het delen van prefixen in de FP-Tree, waardoor de boom compacter wordt.
Definiëren van de FP-Tree-nodeklasse:
- De FPTreeNode-klasse vertegenwoordigt elke node in de boom;
- Elke node slaat de itemnaam, teller, een verwijzing naar de ouder, een dictionary van kinderen en een link naar de volgende node met dezelfde itemnaam op (voor traverseren van de header-tabel).
Opbouwen van de FP-Tree en header-tabel:
- De functie build_fp_tree maakt de boom door elke gesorteerde transactie toe te voegen;
- Beginnend bij de root, wordt voor elk item in een transactie gecontroleerd of er al een kindnode bestaat—zo niet, dan wordt er een aangemaakt en toegevoegd aan de header-tabel;
- Als een node al bestaat, wordt de teller verhoogd;
- Na het bouwen van de boom worden alle nodes met dezelfde itemnaam aan elkaar gelinkt via het link-attribuut, wat snelle traversering via de header-tabel mogelijk maakt.
Weergeven van de FP-Tree-structuur:
- De functie print_tree toont de boom door elke node en zijn teller recursief af te drukken met inspringing om de boomstructuur te visualiseren;
- Deze uitvoer helpt om te zien hoe transacties worden samengeperst tot gedeelde paden binnen de FP-Tree.

1. Wat is een belangrijk voordeel van FP-Growth ten opzichte van het Apriori-algoritme?

2. Wat is de structuur van een FP-Tree-knooppunt?

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 2. Hoofdstuk 1

Vraag AI

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

Sectie 2. Hoofdstuk 1