Lära Konstruera Frekventa Mönsterträd med FP-Growth-algoritmen | Högpresterande regelutvinning och skaloptimering

Svep för att visa menyn

Översikt av FP-Growth

FP-Growth är en högpresterande algoritm utformad för att identifiera frekventa itemsets i stora transaktionsdatamängder. Till skillnad från Apriori, som genererar kandidat-itemsets och upprepade gånger skannar databasen, bygger FP-Growth en kompakt datastruktur kallad FP-Tree (Frequent Pattern Tree) som möjliggör utvinning av frekventa mönster utan kandidatgenerering. Detta leder till betydande förbättringar i hastighet och minnesanvändning, särskilt för datamängder med många frekventa mönster.

Trädstruktur

FP-Tree-strukturen komprimerar hela uppsättningen transaktioner till ett prefixträd-format. Varje transaktion behandlas genom att dess objekt sorteras i fallande ordning efter frekvens och sedan infogas i trädet, där gemensamma prefix delas med befintliga vägar. Rotnoden är en null-nod som fungerar som ingångspunkt, och varje nod i trädet representerar ett objekt tillsammans med en räkning av hur många transaktioner som delar det prefixet upp till den punkten.

Nodlänkning

För att möjliggöra effektiv utvinning är alla noder som representerar samma objekt sammankopplade via en länkad lista, vilket bildar en så kallad header table. Detta gör det möjligt att snabbt traversera alla förekomster av ett visst objekt i trädet. Varje post i header table pekar på den första noden i trädet för det objektet, och varje nod innehåller en länk till nästa nod med samma objektnamn.

Mönsterutvinning

Utvinning av frekventa mönster från FP-Tree involverar två huvudsteg. Först traverserar du trädet nerifrån och upp, genom att följa länkarna för varje objekt i header table för att samla alla prefixvägar som leder till det objektet. Därefter konstrueras konditionella FP-Träd för varje objekt och dessa utvinns rekursivt för att extrahera alla frekventa itemsets. Denna rekursiva process fortsätter tills inga fler frekventa mönster kan hittas.

Exempel: Steg-för-steg FP-Tree-konstruktion

Här går vi igenom den exakta steg-för-steg-konstruktionen med dina exempeltransaktioner, med antagandet om ett minimalt stödfrekvensvärde på 2 (vilket innebär att varor måste förekomma minst två gånger för att beaktas).

Anta att du har följande transaktioner:

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

Steg 1: Skanna databasen och sortera efter frekvens

Först läser algoritmen hela datamängden för att räkna hur många gånger varje enskild vara förekommer. Alla varor som ligger under det minimala stödfrekvensvärdet tas bort. Därefter fastställs en global sorteringsordning från högsta till lägsta frekvens.

Global varuräkning:

B förekommer 4 gånger

E förekommer 3 gånger

A förekommer 2 gånger

C förekommer 2 gånger

D förekommer 1 gång (Tas bort eftersom det är mindre än minimalt stöd på 2)

Slutlig sorteringsregel: Varje transaktion kommer nu att filtreras och omarrangeras för att strikt följa denna fallande frekvensordning:

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

Steg 2: Omordna varje transaktion

Innan varorna förs in i trädet skriver algoritmen om varje transaktion. Den tar bort den sällsynta varan (D) och omarrangerar de återstående varorna enligt den nya globala sorteringsregeln.

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

Steg 3: Infoga vägar i FP-Tree

Varje FP-Tree börjar med en tom platshållare kallad Null Root Node. Vi för nu in våra nyomordnade transaktioner i trädet en i taget, ökar räknarna när vägar överlappar och förgrenar när de skiljer sig åt.

Infoga transaktion 1 {B, A}: trädet skapar en helt ny gren rakt ner från roten.

Infoga transaktion 2 {B, E, C}: algoritmen börjar vid roten och kontrollerar första varan, B. Eftersom B redan finns som barn till roten, överlappar vägen! Algoritmen går vidare till B och ökar dess räkning till 2. Nästa vara är E. Eftersom B ännu inte har ett barn som heter E, delar trädet här och skapar en ny undergren för E, följt av C.

Infoga transaktion 3 {B, E, A, C}: från roten träffar vägen B (räkning ökar till 3), går sedan ner till befintlig E-nod (räkning ökar till 2). Nästa vara är A. Eftersom E inte har ett barn som heter A, skapar trädet en ny förgrening under E för (A:1) -> (C:1).

Infoga transaktion 4 {B, E}: algoritmen följer den mest populära prefixvägen och B ökar till 4, E ökar till 3. Transaktionen slutar här, så inga nya noder läggs till.

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

Detta kodexempel visar hur man konstruerar ett FP-Tree från en lista av transaktioner med Python. Här är en detaljerad förklaring av varje steg:

Räkna varufrekvenser:
- Koden använder klassen Counter från modulen collections för att räkna hur många gånger varje vara förekommer i alla transaktioner;
- Detta hjälper till att identifiera vilka varor som är tillräckligt frekventa för att inkluderas i trädet.
Ta bort sällsynta varor:
- Varor som inte uppfyller det minimala stödfrekvensvärdet filtreras bort;
- Mängden freq_items innehåller endast varor som förekommer minst så många gånger som anges av min_support.
Sortera transaktioner efter frekvens:
- Varje transaktion filtreras för att endast behålla frekventa varor;
- Varorna sorteras sedan i fallande ordning efter deras globala frekvens (och alfabetiskt för att bryta lika);
- Sorteringen maximerar prefixdelning i FP-Tree, vilket gör trädet mer kompakt.
Definiera FP-Tree-nodklass:
- Klassen FPTreeNode representerar varje nod i trädet;
- Varje nod lagrar varunamn, räkning, en pekare till sin förälder, en ordbok över sina barn och en länk till nästa nod med samma varunamn (för traversering av header-tabellen).
Bygga FP-Tree och header-tabell:
- Funktionen build_fp_tree skapar trädet genom att infoga varje sorterad transaktion;
- Från roten, för varje vara i en transaktion, kontrollerar funktionen om ett barnnod finns—om inte, skapas en och läggs till i header-tabellen;
- Om en nod redan finns ökas dess räkning;
- Efter att trädet byggts länkar koden alla noder med samma varunamn via attributet link, vilket möjliggör snabb traversering via header-tabellen.
Skriva ut FP-Tree-strukturen:
- Funktionen print_tree visar trädet genom att rekursivt skriva ut varje nod och dess räkning med indrag för att visa trädstrukturen;
- Denna utmatning hjälper till att visualisera hur transaktioner komprimeras till delade vägar i FP-Tree.

1. Vilken av följande är en viktig fördel med FP-Growth jämfört med Apriori-algoritmen?

2. Hur ser strukturen ut för en FP-Tree-nod?

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 2. Kapitel 1

Fråga AI

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

Avsnitt 2. Kapitel 1