Lära Bearbetning av transaktionsdatastreams med Apriori-algoritmen | Grunderna i Associationsregler och Transaktionsanalys

Svep för att visa menyn

Apriori-algoritmen är ett grundläggande verktyg för att identifiera frekventa varukorgar i transaktionsdata, vilket är avgörande för market basket-analys. Kärnan i Apriori är Apriori-principen, även känd som egenskapen om nedåtgående slutenhet.

Definition

Apriori-principen – Om en varukorg är frekvent måste alla dess delmängder också vara frekventa.

Denna insikt minskar dramatiskt antalet varukorgar som behöver utvärderas, eftersom alla varukorgar som innehåller en ovanlig delmängd omedelbart kan uteslutas från vidare analys.

Kandidatgenerering är algoritmens matchningsfas. I varje omgång granskar algoritmen de vinnande frekventa varukorgarna från föregående omgång och kombinerar dem för att skapa nya, större grupper kallade kandidater. För att göra detta effektivt slår algoritmen endast ihop varukorgar som är nästan identiska och delar alla sina varor utom den allra sista.

Så fungerar det: Om algoritmen upptäcker att {Bread, Milk} och {Bread, Diapers} båda är mycket populära var för sig, kombinerar den dessa för att skapa en helt ny kandidat med tre varor för nästa omgång: {Bread, Milk, Diapers}.

Omedelbart efter att nya kandidater har genererats påbörjar algoritmen pruning-fasen för att eliminera onödiga alternativ innan några tunga databasberäkningar utförs. Detta steg bygger helt på Apriori-principen, som säger att en stor varukorg endast kan vara frekvent om alla dess mindre delmängder också är frekventa. Under pruning dissekerar algoritmen noggrant varje ny kandidat och granskar dess mindre delmängder. Om ens en enda delmängd inte klarade sig i föregående omgång tas hela kandidaten bort direkt.

Så fungerar det: Föreställ dig att kandidaten {Bread, Milk, Eggs} genereras. Algoritmen kontrollerar dess delmängder: {Bread, Milk}, {Bread, Eggs} och {Milk, Eggs}. Om dina historiska transaktionsloggar visar att {Milk, Eggs} är en ovanlig kombination som misslyckades i en tidigare omgång, så tas {Bread, Milk, Eggs} bort helt. Detta sparar beräkningskraft på en kombination som matematiskt sett är dömd att misslyckas.

När kandidatlistan har reducerats till de mest lovande alternativen går algoritmen vidare till identifiering av frekventa varukorgar. Systemet skannar dina råa transaktionsdatabaser för att räkna exakt hur många gånger dessa återstående kandidatgrupper förekommer tillsammans i verkliga köp. Varje kandidats totala antal omvandlas till en procentandel. Om denna siffra uppnår eller överstiger din förutbestämda minsta stödnivå blir kandidaten officiellt en frekvent varukorg.

Definition

Minsta stödnivå är en användardefinierad gräns som bestämmer den lägsta frekvens ett itemset måste ha för att anses vara signifikant i Apriori-algoritmen. Genom att ställa in denna tröskel filtrerar du bort itemsets som förekommer för sällan i datamängden. Ett högt tröskelvärde resulterar i färre, mer vanliga itemsets, vilket kan innebära att intressanta men ovanliga kombinationer missas. Om tröskeln är för låg kan du överväldigas av för många itemsets, inklusive sådana med begränsat praktiskt värde. Den tröskel du väljer påverkar direkt analysens djup och fokus, så den bör spegla målen och omfattningen av din dataanalys.

Denna trestegsslinga upprepas i följd. Den går från enskilda varor till par, sedan till grupper om tre, och fortsätter att expandera tills en omgång körs där inga nya frekventa itemsets kan hittas, vilket framgångsrikt kartlägger hela nätverket av konsumenters köpbeteende.

För att konkretisera dessa idéer, överväg ett enkelt Exempel med en liten datamängd. Anta att du har följande transaktioner:

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

Algoritmen skulle först identifiera alla enskilda varor som förekommer frekvent, sedan generera kandidatpar från dessa, gallra bort de som innehåller sällsynta varor och fortsätta denna process för att upptäcka större frekventa 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}")

Denna Python-kod visar en enkel implementering av Apriori-algoritmen för att identifiera frekventa itemsets i transaktionsdata. Så här utförs varje steg:

Databeredning

Transaktionerna representeras som en lista av listor, där varje underlista innehåller varor som köpts tillsammans.
Alla unika varor identifieras och sorteras.
En one-hot-kodad DataFrame skapas: varje rad representerar en transaktion och varje kolumn motsvarar en vara, med True eller False som indikerar närvaro eller frånvaro.

Steg i Apriori-algoritmen

1. Identifiering av frekventa 1-itemsets

Algoritmen beräknar stödet för varje enskild vara (andelen transaktioner som innehåller varan).
Om en varas stöd uppfyller eller överstiger tröskelvärdet för min_support (här 0,6) anses den vara frekvent och inkluderas i den första listan över frekventa itemsets.

2. Kandidatgenerering

För itemsets av längd k (med början från 2) genererar algoritmen nya kandidat-itemsets genom att kombinera frekventa itemsets från föregående omgång som delar alla utom en vara.
Endast unika kombinationer beaktas, vilket säkerställer att inga dubbletter uppstår.

3. Pruning

Varje ny kandidats delmängder av längd k-1 kontrolleras.
Om någon delmängd inte finns i listan över frekventa itemsets från föregående iteration, tas kandidaten bort (utesluts), baserat på Apriori-principen.

4. Stödräkning

För varje återstående kandidat räknar algoritmen hur många transaktioner som innehåller alla varor i kandidaten.
Stödet beräknas och jämförs med tröskelvärdet. Endast kandidater som uppfyller tröskelvärdet behålls som frekventa itemsets för nästa omgång.

5. Iteration

Steg 2–4 upprepas, med ökande storlek på itemsets varje gång, tills inga nya frekventa itemsets hittas.

Utdata

Den slutliga listan inkluderar alla frekventa itemsets och deras stödvärden.
Koden skriver ut varje frekvent itemset och dess stöd, vilket visar vilka kombinationer av varor som ofta förekommer tillsammans i transaktionerna.

1. Vilket av följande beskriver bäst steget för kandidatgenerering i Apriori-algoritmen?

2. Vad är den främsta anledningen till att pruna kandidat-itemsets under Apriori-algoritmen?

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 1. Kapitel 4

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