Lære Konstruksjon av Hyppige Mønstertre med FP-Growth-algoritmen | Høyytelses Regelutvinning og Skaleringsoptimalisering

Sveip for å vise menyen

Oversikt over FP-Growth

FP-Growth er en høyytelsesalgoritme utviklet for å finne hyppige elementsett i store transaksjonsdatasett. I motsetning til Apriori, som genererer kandidatsett og gjentatte ganger skanner databasen, bygger FP-Growth en kompakt datastruktur kalt FP-Tree (Frequent Pattern Tree) som gjør det mulig å finne hyppige mønstre uten å generere kandidater. Dette gir betydelige forbedringer i hastighet og minnebruk, spesielt for datasett med mange hyppige mønstre.

Trestruktur

FP-Tree-strukturen komprimerer hele settet av transaksjoner til et prefikstre-format. Hver transaksjon behandles ved å sortere elementene i synkende rekkefølge etter frekvens, og deretter settes de inn i treet, hvor felles prefikser deles med eksisterende stier. Rotnoden er en nullnode som fungerer som inngangspunkt, og hver node i treet representerer et element sammen med en teller for hvor mange transaksjoner som deler det prefikset opp til det punktet.

Nodekobling

For å muliggjøre effektiv utvinning, er alle noder som representerer det samme elementet koblet sammen via en lenket liste, og danner det som kalles en header table. Dette gjør det mulig å raskt traversere alle forekomster av et bestemt element i treet. Hver oppføring i header table peker til den første noden i treet for det elementet, og hver node inneholder en kobling til neste node med samme elementnavn.

Mønsterutvinning

Utvinning av hyppige mønstre fra FP-Tree innebærer to hovedtrinn. Først traverserer du treet nedenfra og opp, ved å følge koblingene for hvert element i header table for å samle alle prefiksstier som leder til det elementet. Deretter konstruerer du betingede FP-Tree for hvert element og utvinner dem rekursivt for å hente ut alle hyppige elementsett. Denne rekursive prosessen fortsetter til det ikke finnes flere hyppige mønstre.

Eksempel: Steg-for-steg FP-Tree-konstruksjon

La oss gå gjennom den nøyaktige steg-for-steg-konstruksjonen ved å bruke dine eksempeltransaksjoner, med en minimumsstøtte på 2 (det vil si at varer må forekomme minst to ganger for å bli vurdert).

Anta at du har følgende transaksjoner:

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

Steg 1: Skann databasen og sorter etter frekvens

Først leser algoritmen hele datasettet for å telle hvor mange ganger hver enkelt vare forekommer. Alle varer som faller under minimumsstøtten blir fjernet. Deretter etableres en global sorteringsrekkefølge fra høyest til lavest frekvens.

Global vareantall:

B forekommer 4 ganger

E forekommer 3 ganger

A forekommer 2 ganger

C forekommer 2 ganger

D forekommer 1 gang (Fjernet fordi det er mindre enn minimumsstøtten på 2)

Den endelige sorteringsregelen: Hver transaksjon vil nå filtreres og omorganiseres for å følge denne synkende frekvensrekkefølgen:

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

Steg 2: Omorganiser hver transaksjon

Før varene settes inn i treet, skriver algoritmen om hver transaksjon. Den fjerner den sjeldne varen (D) og omorganiserer de gjenværende varene etter den nye globale sorteringsregelen.

- Transaksjon 1: A, B, D blir B, A
- Transaksjon 2: B, C, E blir B, E, C
- Transaksjon 3: A, B, C, E blir B, E, A, C
- Transaksjon 4: B, E blir B, E

Steg 3: Sett inn stier i FP-Tree

Hvert FP-Tree starter med en tom plassholder kalt Null Root Node. Vi setter nå inn våre nyomorganiserte transaksjoner i treet én etter én, øker tellere når stier overlapper og forgrener når de skiller lag.

Sett inn transaksjon 1 {B, A}: treet oppretter en helt ny gren rett ned fra roten.

Sett inn transaksjon 2 {B, E, C}: algoritmen starter ved roten og sjekker første vare, B. Siden B allerede finnes som barn av roten, overlapper stien! Algoritmen går til B og øker telleren til 2. Neste vare er E. Siden B ikke har et barn som heter E ennå, forgrener treet seg her og oppretter en ny undergren for E, etterfulgt av C.

Sett inn transaksjon 3 {B, E, A, C}: starter fra roten, følger stien til B (teller øker til 3), deretter ned til eksisterende E-node (teller øker til 2). Neste vare er A. Siden E ikke har et barn som heter A, oppretter treet en ny forgrening under E for (A:1) -> (C:1).

Sett inn transaksjon 4 {B, E}: algoritmen følger den mest populære prefiksstien og B øker til 4, E øker til 3. Transaksjonen avsluttes her, så ingen nye noder legges til.

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

Denne kodeeksempelet viser hvordan man kan konstruere et FP-Tree fra en liste med transaksjoner ved hjelp av Python. Her er en detaljert forklaring av hvert steg:

Telle varefrekvenser:
- Koden bruker Counter-klassen fra collections-modulen for å telle hvor mange ganger hver vare forekommer i alle transaksjoner;
- Dette hjelper med å identifisere hvilke varer som er hyppige nok til å inkluderes i treet.
Fjerne sjeldne varer:
- Varer som ikke oppfyller minimumsstøtten blir filtrert ut;
- Mengden freq_items inneholder kun varer som forekommer minst så mange ganger som angitt av min_support.
Sortere transaksjoner etter frekvens:
- Hver transaksjon filtreres for å beholde kun hyppige varer;
- Varene sorteres deretter i synkende rekkefølge etter global frekvens (og alfabetisk for å bryte likhet);
- Sortering maksimerer prefiksdeling i FP-Tree, noe som gjør treet mer kompakt.
Definere FP-Tree node-klasse:
- FPTreeNode-klassen representerer hver node i treet;
- Hver node lagrer varenavn, teller, peker til forelder, en ordbok over barn og en lenke til neste node med samme varenavn (for traversering av header-tabellen).
Bygge FP-Tree og header-tabell:
- build_fp_tree-funksjonen oppretter treet ved å sette inn hver sorterte transaksjon;
- Fra roten, for hver vare i en transaksjon, sjekker funksjonen om et barnenode finnes—hvis ikke, opprettes en og legges til i header-tabellen;
- Hvis en node allerede finnes, økes telleren;
- Etter at treet er bygget, lenker koden alle noder med samme varenavn via link-attributtet, slik at man kan traversere raskt via header-tabellen.
Skrive ut FP-Tree-strukturen:
- print_tree-funksjonen viser treet ved å rekursivt skrive ut hver node og dens teller med innrykk for å vise trestrukturen;
- Denne utdataen hjelper med å visualisere hvordan transaksjoner komprimeres til delte stier i FP-Tree.

1. Hva er en sentral fordel med FP-Growth sammenlignet med Apriori-algoritmen?

2. Hva er strukturen til en FP-Tree-node?

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 2. Kapittel 1

Spør AI

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

Seksjon 2. Kapittel 1