Lære Behandling af transaktionsdatastrømme med Apriori-algoritmen | Grundlæggende om Associationsregler og Transaktionsanalyse

Stryg for at vise menuen

Apriori-algoritmen er et grundlæggende værktøj til at identificere hyppige varegrupper i transaktionsdata, hvilket er afgørende for market basket-analyse. Kernen i Apriori er Apriori-princippet, også kendt som downward closure-egenskaben.

Definition

Apriori-princippet – Hvis en varegruppe er hyppig, skal alle dens delmængder også være hyppige.

Denne indsigt reducerer dramatisk antallet af varegrupper, der skal evalueres, da enhver varegruppe, der indeholder en sjælden delmængde, straks kan udelukkes fra overvejelse.

Kandidatgenerering er algoritmens matchningsfase. I hver runde ser algoritmen på de vindende hyppige varegrupper fra den forrige runde og kombinerer dem for at danne nye, større grupper kaldet kandidater. For at gøre dette effektivt, sammenføjer algoritmen kun varegrupper, der næsten er identiske og deler alle deres varer undtagen den sidste.

Sådan fungerer det: Hvis algoritmen opdager, at {Bread, Milk} og {Bread, Diapers} begge er meget populære hver for sig, kombinerer den dem for at skabe en helt ny kandidat med tre varer til næste runde: {Bread, Milk, Diapers}.

Umiddelbart efter generering af nye kandidater starter algoritmen Pruning-fasen for at eliminere overflødige grupper, inden der udføres tunge databaseberegninger. Dette trin er udelukkende baseret på Apriori-princippet, som siger, at en stor varegruppe kun kan være hyppig, hvis alle dens mindre individuelle dele også er hyppige. Under pruning gennemgår algoritmen omhyggeligt hver ny kandidat og ser på dens mindre delmængder. Hvis blot én delmængde ikke klarede sig i den forrige runde, slettes hele kandidaten øjeblikkeligt.

Sådan fungerer det: Forestil dig, at kandidaten {Bread, Milk, Eggs} genereres. Algoritmen tjekker dens undergrupper: {Bread, Milk}, {Bread, Eggs} og {Milk, Eggs}. Hvis dine historiske transaktionslogs viser, at {Milk, Eggs} er en sjælden kombination, der ikke klarede sig i en tidligere runde, bliver {Bread, Milk, Eggs} fjernet helt. Dette sparer dig for at bruge computerkraft på en kombination, der matematisk set er dømt til at fejle.

Når kandidatlisten er reduceret til de mest levedygtige muligheder, går algoritmen videre til Identifikation af hyppige varegrupper. Systemet scanner dine rå transaktionsdatabaser for at tælle præcist, hvor mange gange disse resterende kandidatgrupper optræder sammen i faktiske køb. Hver kandidats samlede antal omregnes til en procentdel. Hvis denne score opfylder eller overstiger din forudbestemte Minimum Support Threshold, bliver kandidaten officielt udnævnt til en hyppig varegruppe.

Definition

Minimum Support Threshold er en brugerdefineret grænse, der bestemmer den laveste frekvens, et itemset skal have for at blive betragtet som signifikant i Apriori-algoritmen. Ved at sætte denne grænse filtrerer du itemsets fra, som forekommer for sjældent i datasættet. Hvis du vælger en høj grænse, vil det resultere i færre, mere almindelige itemsets, hvilket potentielt kan betyde, at interessante men sjældne kombinationer overses. Sættes grænsen for lavt, kan du blive overvældet af for mange itemsets, inklusive dem med ringe praktisk værdi. Den valgte grænse påvirker direkte dybden og fokus for din analyse, så den bør afspejle målene og omfanget af din dataudforskning.

Denne tretrins-loop gentages fortløbende. Den bevæger sig fra enkelte varer til par, derefter til grupper af tre og fortsætter med at udvide, indtil der køres en runde, hvor der ikke kan findes nye hyppige itemsets, hvilket kortlægger hele dit netværk af forbrugerens købsadfærd.

For at gøre disse idéer konkrete, overvej et simpelt Eksempel med et lille datasæt. Antag, at du har følgende transaktioner:

Transaction 1: {Milk, Bread};
Transaction 2: {Milk, Diaper, Beer, Bread};
Transaction 3: {Milk, Diaper, Beer, Cola};
Transaction 4: {Diaper, Beer};
Transaction 5: {Milk, Diaper, Bread, Beer}.

Algoritmen vil først identificere alle enkelte varer, der forekommer hyppigt, derefter generere kandidatpar ud fra disse, frasortere dem der indeholder sjældne varer, og fortsætte denne proces for at finde større hyppige grupper, såsom {Milk, Diaper, Beer}.


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
            
import pandas as pd
from itertools import combinations

# Example transaction dataset
transactions = [
    ['Milk', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Cola'],
    ['Diaper', 'Beer'],
    ['Milk', 'Diaper', 'Bread', 'Beer']
]

# Convert transactions to a DataFrame of one-hot encoded items
all_items = sorted(set(item for transaction in transactions for item in transaction))
df = pd.DataFrame([{item: (item in transaction) for item in all_items} for transaction in transactions])

def apriori(df, min_support=0.6):

    def get_support(itemset):
        return (df[list(itemset)].all(axis=1).sum()) / len(df)

    # Step 1: Finding frequent 1-itemsets
    frequent_itemsets = []
    current_level = []
    for item in all_items:
        support = get_support([item])
        if support >= min_support:
            current_level.append(frozenset([item]))
            frequent_itemsets.append((frozenset([item]), support))

    k = 2
    while current_level:
        # Step 2: Candidate generation
        candidates = []
        level_list = list(current_level)
        for i in range(len(level_list)):
            for j in range(i+1, len(level_list)):
                union = level_list[i] | level_list[j]
                if len(union) == k and union not in candidates:
                    # Step 3: Pruning
                    subsets = list(combinations(union, k-1))
                    if all(frozenset(subset) in current_level for subset in subsets):
                        candidates.append(union)

        # Step 4: Support counting
        next_level = []
        for candidate in candidates:
            support = get_support(candidate)
            if support >= min_support:
                next_level.append(candidate)
                frequent_itemsets.append((candidate, support))

        current_level = next_level
        k += 1

    # Format output
    return [(set(itemset), round(support, 2)) for itemset, support in frequent_itemsets]

# Running Apriori and displaying frequent itemsets
frequent_itemsets = apriori(df, min_support=0.6)
for itemset, support in frequent_itemsets:
    print(f"Frequent Itemset: {itemset}, Support: {support}")

Denne Python-kode demonstrerer en simpel implementering af Apriori-algoritmen til identifikation af hyppige itemsets i transaktionsdata. Her er, hvordan hvert trin udføres:

Dataklargøring

Transaktionerne er repræsenteret som en liste af lister, hvor hver underliste indeholder varer købt sammen.
Alle unikke varer identificeres og sorteres.
En one-hot kodet DataFrame oprettes: hver række repræsenterer en transaktion, og hver kolonne svarer til en vare, med True eller False for at angive tilstedeværelse eller fravær.

Apriori-algoritmens trin

1. Identifikation af hyppige 1-itemsets

Algoritmen beregner support for hver enkelt vare (andelen af transaktioner, der indeholder varen).
Hvis en vares support opfylder eller overstiger min_support-grænsen (her 0,6), betragtes den som hyppig og inkluderes i den første liste over hyppige itemsets.

2. Kandidatgenerering

For itemsets af længde k (startende fra 2) genererer algoritmen nye kandidat-itemsets ved at kombinere hyppige itemsets fra den forrige runde, som deler alle undtagen én vare.
Kun unikke kombinationer overvejes, hvilket sikrer, at der ikke er dubletter.

3. Beskæring

Hvert nyt kandidats delmængder af længde k-1 kontrolleres.
Hvis nogen delmængde ikke findes i listen over hyppige itemsets fra den forrige iteration, beskæres kandidaten (udelukkes) baseret på Apriori-princippet.

4. Supportoptælling

For hver tilbageværende kandidat tæller algoritmen, hvor mange transaktioner der indeholder alle varer i kandidaten.
Supporten beregnes og sammenlignes med grænsen. Kun kandidater, der opfylder grænsen, beholdes som hyppige itemsets til næste runde.

5. Iteration

Trin 2–4 gentages, idet størrelsen af itemsets øges hver gang, indtil der ikke findes nye hyppige itemsets.

Output

Den endelige liste inkluderer alle hyppige itemsets og deres supportværdier.
Koden udskriver hvert hyppigt itemset og dets support, hvilket viser, hvilke kombinationer af varer der ofte optræder sammen i transaktionerne.

1. Hvilken af følgende beskriver bedst kandidatgenereringstrinnet i Apriori-algoritmen?

2. Hvad er hovedårsagen til at beskære kandidat-itemsets under Apriori-algoritmen?

Var alt klart?

Tak for dine kommentarer!

Sektion 1. Kapitel 4

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 1. Kapitel 4