Lære Behandling av transaksjonsdatastrømmer med Apriori-algoritmen | Grunnleggende om assosiasjonsregler og transaksjonsanalyse

Sveip for å vise menyen

Apriori-algoritmen er et grunnleggende verktøy for å avdekke hyppige varegrupper i transaksjonsdata, noe som er avgjørende for market basket-analyse. Kjernen i Apriori er Apriori-prinsippet, også kjent som nedadgående lukningsegenskap.

Definisjon

Apriori-prinsippet – Hvis en varegruppe er hyppig, må alle dens delmengder også være hyppige.

Denne innsikten reduserer dramatisk antallet varegrupper som må vurderes, ettersom enhver varegruppe som inneholder en sjelden delmengde umiddelbart kan utelukkes fra videre behandling.

Kandidatgenerering er utvelgelsesfasen i algoritmen. I hver runde ser algoritmen på de hyppige varegruppene fra forrige runde og kombinerer dem for å danne nye, større grupper kalt kandidater. For å gjøre dette effektivt, slår algoritmen kun sammen varegrupper som er nesten identiske, og som deler alle varer unntatt den aller siste.

Slik fungerer det: Hvis algoritmen oppdager at {Bread, Milk} og {Bread, Diapers} begge er svært populære hver for seg, kombinerer den disse for å lage en helt ny kandidat med tre varer for neste runde: {Bread, Milk, Diapers}.

Umiddelbart etter at nye kandidater er generert, starter algoritmen beskjæringsfasen for å eliminere overflødige grupper før tunge databaseberegninger kjøres. Dette steget er helt avhengig av Apriori-prinsippet, som sier at en stor varegruppe kun kan være hyppig hvis alle dens mindre delmengder også er hyppige. Under beskjæringen analyserer algoritmen nøye hver ny kandidat og ser på dens mindre delmengder. Hvis selv én delmengde ikke bestod forrige runde, blir hele kandidaten umiddelbart fjernet.

Slik fungerer det: Tenk deg at kandidaten {Bread, Milk, Eggs} er generert. Algoritmen sjekker dens delmengder: {Bread, Milk}, {Bread, Eggs} og {Milk, Eggs}. Hvis dine historiske transaksjonslogger viser at {Milk, Eggs} er en sjelden kombinasjon som ikke bestod en tidligere runde, beskjærer algoritmen {Bread, Milk, Eggs} helt. Dette sparer deg for å bruke datakraft på en kombinasjon som matematisk sett er garantert å feile.

Når kandidatlisten er beskåret ned til de mest levedyktige alternativene, går algoritmen videre til identifisering av hyppige varegrupper. Systemet skanner de rå transaksjonsdatabasene dine for å telle nøyaktig hvor mange ganger disse gjenværende kandidatgruppene opptrer sammen i faktiske kjøp. Hver kandidats totale antall omregnes til en prosentandel. Hvis denne verdien møter eller overstiger din forhåndsbestemte minimumsstøtte-grense, blir kandidaten offisielt utnevnt til en hyppig varegruppe.

Definisjon

Minimum støttegrense er en brukerdefinert terskel som bestemmer den laveste frekvensen et varesett må ha for å anses som signifikant i Apriori-algoritmen. Ved å sette denne terskelen filtrerer du ut varesett som forekommer for sjelden i datasettet. En høy terskel vil resultere i færre, mer vanlige varesett, og kan føre til at interessante, men sjeldne kombinasjoner utelates. Setter du terskelen for lavt, kan du bli overveldet av for mange varesett, inkludert de med liten praktisk verdi. Terskelen du velger påvirker direkte dybden og fokuset i analysen, og bør derfor reflektere målene og omfanget for datautforskningen din.

Denne tretrinnsløkken gjentas fortløpende. Den går fra enkeltvarer til par, deretter til grupper på tre, og fortsetter å utvide seg til den kjører en runde hvor ingen nye hyppige varesett kan finnes, og kartlegger dermed hele forbrukernes kjøpsmønster.

For å konkretisere disse ideene, vurder et enkelt eksempel med et lite datasett. Anta at du har følgende transaksjoner:

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

Algoritmen vil først identifisere alle enkeltvarer som forekommer hyppig, deretter generere kandidatpar fra disse, fjerne de som inneholder sjeldne varer, og fortsette denne prosessen for å oppdage større hyppige grupper, 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-koden demonstrerer en enkel implementering av Apriori-algoritmen for å identifisere hyppige elementsett i transaksjonsdata. Slik utføres hvert trinn:

Datapreparering

Transaksjonene er representert som en liste av lister, der hver underliste inneholder varer kjøpt sammen.
Alle unike varer identifiseres og sorteres.
En én-hot kodet DataFrame opprettes: hver rad representerer en transaksjon, og hver kolonne tilsvarer en vare, med True eller False som indikerer tilstedeværelse eller fravær.

Apriori-algoritmens trinn

1. Identifisering av hyppige 1-elementsett

Algoritmen beregner støtten for hvert enkelt element (andelen transaksjoner som inneholder elementet).
Hvis et elements støtte oppfyller eller overstiger min_support-terskelen (her, 0.6), regnes det som hyppig og inkluderes i den første listen over hyppige elementsett.

2. Kandidatgenerering

For elementsett av lengde k (starter fra 2), genererer algoritmen nye kandidatsett ved å kombinere hyppige elementsett fra forrige runde som deler alle unntatt ett element.
Kun unike kombinasjoner vurderes, slik at duplikater unngås.

3. Beskjæring

Hvert nytt kandidats delmengder av lengde k-1 kontrolleres.
Hvis noen delmengde ikke finnes i listen over hyppige elementsett fra forrige iterasjon, fjernes kandidaten (utelates), basert på Apriori-prinsippet.

4. Støtteberegning

For hver gjenværende kandidat teller algoritmen hvor mange transaksjoner som inneholder alle elementene i kandidaten.
Støtten beregnes og sammenlignes med terskelen. Kun kandidater som oppfyller terskelen beholdes som hyppige elementsett for neste runde.

5. Iterasjon

Trinn 2–4 gjentas, med økende størrelse på elementsettene hver gang, til ingen nye hyppige elementsett finnes.

Resultat

Den endelige listen inkluderer alle hyppige elementsett og deres støtteverdier.
Koden skriver ut hvert hyppige elementsett og dets støtte, og viser hvilke kombinasjoner av varer som ofte forekommer sammen i transaksjonene.

1. Hvilket av følgende beskriver best kandidatgenereringstrinnet i Apriori-algoritmen?

2. Hva er hovedårsaken til å beskjære kandidatsett under Apriori-algoritmen?

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 1. Kapittel 4

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