Leer Het Verwerken van Transactionele Datastromen met het Apriori-algoritme | Grondslagen van Associatieregels en Transactionele Analyse

Veeg om het menu te tonen

Het Apriori-algoritme is een fundamenteel hulpmiddel voor het ontdekken van frequente itemsets in transactionele data, wat essentieel is voor market basket-analyse. De kern van Apriori is het Apriori-principe, ook bekend als de downward closure-eigenschap.

Definitie

Apriori-principe - Als een itemset frequent is, moeten al zijn deelverzamelingen ook frequent zijn.

Dit inzicht vermindert drastisch het aantal te evalueren itemsets, omdat elke itemset met een infrequente deelverzameling direct kan worden uitgesloten.

Kandidaatgeneratie is de koppelingsfase van het algoritme. In elke ronde kijkt het algoritme naar de winnende frequente itemsets uit de vorige ronde en combineert deze om nieuwe, grotere groepen te vormen, de zogenaamde kandidaten. Om dit efficiënt te doen, voegt het algoritme alleen itemsets samen die bijna identiek zijn en alle items delen behalve het laatste item.

Werking: Als het algoritme ontdekt dat {Bread, Milk} en {Bread, Diapers} beide op zichzelf zeer populair zijn, combineert het deze om een geheel nieuwe kandidaat met drie items te creëren voor de volgende ronde: {Bread, Milk, Diapers}.

Direct na het genereren van nieuwe kandidaten start het algoritme de Pruning-fase om overbodige combinaties te elimineren voordat zware databaseberekeningen worden uitgevoerd. Deze stap is volledig gebaseerd op het Apriori-principe, dat stelt dat een grote itemset alleen frequent kan zijn als al zijn kleinere deelverzamelingen ook frequent zijn. Tijdens het snoeien analyseert het algoritme zorgvuldig elke nieuwe kandidaat en bekijkt de kleinere deelverzamelingen. Als zelfs één deelverzameling in de vorige ronde niet voldeed, wordt de hele kandidaat direct verwijderd.

Werking: Stel dat de kandidaat {Bread, Milk, Eggs} wordt gegenereerd. Het algoritme controleert de subcomponenten: {Bread, Milk}, {Bread, Eggs} en {Milk, Eggs}. Als uit je historische transactielogs blijkt dat {Milk, Eggs} een zeldzame combinatie is die een vorige ronde niet heeft gehaald, snoeit het algoritme {Bread, Milk, Eggs} volledig weg. Dit voorkomt verspilling van rekenkracht aan een combinatie die wiskundig gegarandeerd zal falen.

Zodra de kandidatenlijst is teruggebracht tot de meest kansrijke combinaties, gaat het algoritme over naar Identificatie van frequente itemsets. Het systeem scant de ruwe transactiedatabases om precies te tellen hoe vaak deze overgebleven kandidaatgroepen samen voorkomen in echte aankopen. Het totale aantal van elke kandidaat wordt omgezet in een percentage. Als deze score voldoet aan of hoger is dan de vooraf bepaalde minimale supportdrempel, wordt de kandidaat officieel erkend als een frequente itemset.

Definitie

Minimale supportdrempel is een door de gebruiker ingestelde grens die bepaalt wat de laagste frequentie is die een itemset moet hebben om als significant te worden beschouwd in het Apriori-algoritme. Door deze drempel in te stellen, filter je itemsets uit die te weinig voorkomen in de dataset. Een hoge drempel resulteert in minder, maar meer voorkomende itemsets, waardoor mogelijk interessante maar zeldzame combinaties worden gemist. Een te lage drempel kan leiden tot een overvloed aan itemsets, waaronder die met weinig praktische waarde. De gekozen drempel heeft direct invloed op de diepgang en focus van je analyse en moet daarom aansluiten bij de doelen en omvang van je data-analyse.

Deze volledige driestapslus herhaalt zich achtereenvolgens. Het proces gaat van enkele items naar paren, vervolgens naar groepen van drie, en breidt zich verder uit totdat er een ronde is waarin geen nieuwe frequente itemsets meer gevonden kunnen worden, waarmee het volledige netwerk van consumentenaankoopgedrag in kaart wordt gebracht.

Om deze ideeën concreet te maken, volgt hier een eenvoudig voorbeeld met een kleine dataset. Stel dat je de volgende transacties hebt:

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

Het algoritme identificeert eerst alle enkele items die vaak voorkomen, genereert vervolgens kandidaat-paren hiervan, verwijdert paren met infrequente items, en gaat zo verder om grotere frequente groepen te ontdekken, zoals {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}")

Deze Python-code toont een eenvoudige implementatie van het Apriori-algoritme voor het identificeren van frequente itemsets in transactionele data. Hieronder volgt een overzicht van elke stap:

Gegevensvoorbereiding

De transacties worden weergegeven als een lijst van lijsten, waarbij elke sublijst de samen gekochte items bevat.
Alle unieke items worden geïdentificeerd en gesorteerd.
Er wordt een one-hot encoded DataFrame aangemaakt: elke rij stelt een transactie voor en elke kolom correspondeert met een item, met True of False voor aanwezigheid of afwezigheid.

Stappen van het Apriori-algoritme

1. Identificatie van frequente 1-itemsets

Het algoritme berekent de support voor elk individueel item (het aandeel transacties waarin het item voorkomt).
Als de support van een item voldoet aan of hoger is dan de min_support-drempel (hier 0,6), wordt het als frequent beschouwd en opgenomen in de eerste lijst met frequente itemsets.

2. Generatie van kandidaten

Voor itemsets van lengte k (beginnend bij 2) genereert het algoritme nieuwe kandidaat-itemsets door frequente itemsets uit de vorige ronde te combineren die op één item na identiek zijn.
Alleen unieke combinaties worden overwogen, zodat er geen duplicaten ontstaan.

3. Pruning

Van elke nieuwe kandidaat worden de deelverzamelingen van lengte k-1 gecontroleerd.
Als een deelverzameling niet voorkomt in de lijst met frequente itemsets uit de vorige iteratie, wordt de kandidaat uitgesloten (gepruned), volgens het Apriori-principe.

4. Supporttelling

Voor elke overgebleven kandidaat telt het algoritme hoeveel transacties alle items uit de kandidaat bevatten.
De support wordt berekend en vergeleken met de drempel. Alleen kandidaten die aan de drempel voldoen, worden als frequente itemsets voor de volgende ronde behouden.

5. Iteratie

Stappen 2–4 worden herhaald, waarbij de grootte van de itemsets telkens toeneemt, totdat er geen nieuwe frequente itemsets meer worden gevonden.

Uitvoer

De uiteindelijke lijst bevat alle frequente itemsets en hun supportwaarden.
De code print elke frequente itemset en de bijbehorende support, zodat zichtbaar wordt welke combinaties van items vaak samen in de transacties voorkomen.

1. Welke van de volgende beschrijvingen geeft het beste de stap voor het genereren van kandidaten in het Apriori-algoritme weer?

2. Wat is de belangrijkste reden om kandidaat-itemsets te prunen tijdens het Apriori-algoritme?

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 1. Hoofdstuk 4

Vraag AI

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

Sectie 1. Hoofdstuk 4