Lære Konstruktion af Hyppige Mønstergrafer med FP-Growth-algoritmen | High Performance Rule Mining and Scale Optimization

Stryg for at vise menuen

FP-Growth Oversigt

FP-Growth er en højtydende algoritme designet til at finde hyppige elementmængder i store transaktionsdatasæt. I modsætning til Apriori, som genererer kandidat-elementmængder og gentagne gange gennemgår databasen, opbygger FP-Growth en kompakt datastruktur kaldet FP-Tree (Frequent Pattern Tree), der muliggør udvinding af hyppige mønstre uden kandidatgenerering. Dette resulterer i betydelige forbedringer i hastighed og hukommelsesforbrug, især for datasæt med mange hyppige mønstre.

Træstruktur

FP-Tree-strukturen komprimerer hele sættet af transaktioner i et præfiks-træformat. Hver transaktion behandles ved at sortere dens elementer i faldende rækkefølge efter hyppighed og derefter indsætte dem i træet, hvor fælles præfikser deles med eksisterende stier. Rodnoden er en null-node, der fungerer som indgangspunkt, og hver node i træet repræsenterer et element sammen med en optælling af, hvor mange transaktioner der deler det præfiks op til det punkt.

Nodeforbindelser

For at muliggøre effektiv udvinding er alle noder, der repræsenterer det samme element, forbundet via en kædeliste, hvilket danner det, der kaldes en header table. Dette gør det muligt hurtigt at gennemgå alle forekomster af et bestemt element i træet. Hver post i header table peger på den første node i træet for det pågældende element, og hver node indeholder et link til den næste node med samme elementnavn.

Udvinding af mønstre

Udvinding af hyppige mønstre fra FP-Tree involverer to hovedtrin. Først gennemgås træet nedefra og op ved at følge forbindelserne for hvert element i header table for at indsamle alle præfiksstier, der fører til det pågældende element. Derefter konstrueres betingede FP-Tree for hvert element, og disse mines rekursivt for at udtrække alle hyppige elementmængder. Denne rekursive proces fortsætter, indtil der ikke kan findes flere hyppige mønstre.

Eksempel: Trin-for-trin FP-Tree Konstruktion

Lad os gennemgå den præcise trin-for-trin konstruktion ved hjælp af dine eksempeltransaktioner, med en Minimum Support Tærskel på 2 (hvilket betyder, at varer skal optræde mindst to gange for at blive taget i betragtning).

Antag, at du har følgende transaktioner:

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

Trin 1: Scan databasen og sorter efter hyppighed

Først læser algoritmen hele datasættet for at tælle, hvor mange gange hver enkelt vare optræder. Enhver vare, der ligger under minimum support-tærsklen, fjernes. Derefter etableres en global sorteringsrækkefølge fra højeste til laveste hyppighed.

Global vareoptælling:

B optræder 4 gange

E optræder 3 gange

A optræder 2 gange

C optræder 2 gange

D optræder 1 gang (Fjernet, da det er mindre end Minimum Support på 2)

Den endelige sorteringsregel: Hver transaktion vil nu blive filtreret og omarrangeret, så de følger denne faldende hyppighedsorden:

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

Trin 2: Omarranger hver transaktion

Før indsættelse i træet omskriver algoritmen hver transaktion. Den fjerner den sjældne vare (D) og omarrangerer de resterende varer, så de matcher den nye globale sorteringsregel.

- Transaktion 1: A, B, D bliver B, A
- Transaktion 2: B, C, E bliver B, E, C
- Transaktion 3: A, B, C, E bliver B, E, A, C
- Transaktion 4: B, E bliver B, E

Trin 3: Indsæt stier i FP-Tree

Hvert FP-Tree starter med en tom pladsholder kaldet Null Root Node. Vi indsætter nu vores nyomarrangerede transaktioner i træet én ad gangen, øger tællere, når stier overlapper, og forgrener, når de adskiller sig.

Indsæt Transaktion 1 {B, A}: træet opretter en helt ny gren direkte ned fra roden.

Indsæt Transaktion 2 {B, E, C}: algoritmen starter ved roden og tjekker det første element, B. Da B allerede findes som et barn af roden, overlapper stien! Algoritmen går videre til B og øger dens tæller til 2. Næste element er E. Da B endnu ikke har et barn med navnet E, forgrener træet sig her og opretter en ny undergren for E, efterfulgt af C.

Indsæt Transaktion 3 {B, E, A, C}: startende fra roden rammer stien B (tæller øges til 3), derefter ned til den eksisterende E-node (tæller øges til 2). Næste element er A. Da E ikke har et barn med navnet A, opretter træet en ny forgrening under E for (A:1) -> (C:1).

Indsæt Transaktion 4 {B, E}: algoritmen følger den mest populære præfikssti, og B øges til 4, E øges til 3. Transaktionen slutter her, så der tilføjes ingen nye noder.

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

Dette kodeeksempel viser, hvordan man konstruerer et FP-Tree ud fra en liste af transaktioner ved hjælp af Python. Her er en detaljeret forklaring af hvert trin:

Optælling af varefrekvenser:
- Koden bruger Counter-klassen fra collections-modulet til at tælle, hvor mange gange hver vare optræder på tværs af alle transaktioner;
- Dette hjælper med at identificere, hvilke varer der er hyppige nok til at blive inkluderet i træet.
Fjernelse af sjældne varer:
- Varer, der ikke opfylder minimum support-tærsklen, filtreres fra;
- Sættet freq_items indeholder kun varer, der optræder mindst så mange gange som angivet af min_support.
Sortering af transaktioner efter hyppighed:
- Hver transaktion filtreres, så kun hyppige varer bevares;
- Varerne sorteres derefter i faldende rækkefølge efter deres globale hyppighed (og alfabetisk for at bryde lighed);
- Sortering maksimerer præfiksdeling i FP-Tree, hvilket gør træet mere kompakt.
Definition af FP-Tree nodeklasse:
- FPTreeNode-klassen repræsenterer hver node i træet;
- Hver node gemmer varenavn, tæller, en reference til sin forælder, en ordbog over sine børn og et link til næste node med samme varenavn (til header table traversal).
Opbygning af FP-Tree og header table:
- build_fp_tree-funktionen opretter træet ved at indsætte hver sorteret transaktion;
- Startende fra roden, for hver vare i en transaktion, tjekker funktionen, om et barn allerede findes—hvis ikke, oprettes det og tilføjes til header table;
- Hvis en node allerede findes, øges dens tæller;
- Efter opbygning af træet linker koden alle noder med samme varenavn via link-attributten, hvilket muliggør hurtig traversal gennem header table.
Udskrivning af FP-Tree-strukturen:
- print_tree-funktionen viser træet ved rekursivt at udskrive hver node og dens tæller med indryk for at vise træstrukturen;
- Denne output hjælper med at visualisere, hvordan transaktioner komprimeres til delte stier i FP-Tree.

1. Hvilket af følgende er en vigtig fordel ved FP-Growth i forhold til Apriori-algoritmen?

2. Hvad er strukturen af en FP-Tree-node?

Var alt klart?

Tak for dine kommentarer!

Sektion 2. Kapitel 1

Spørg AI

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Sektion 2. Kapitel 1