Oppiskele Transaktioaineistojen Virtojen Käsittely Apriori-algoritmilla | Assosiaatiosääntöjen ja transaktioanalyysin perusteet

Pyyhkäise näyttääksesi valikon

Apriori-algoritmi on keskeinen työkalu usein esiintyvien tuotejoukkojen löytämiseen transaktiodatan joukosta, mikä on olennaista ostoskorianalyysissä. Apriorin ytimessä on Apriori-periaate, joka tunnetaan myös laskevana sulkeumaperiaatteena.

Määritelmä

Apriori-periaate – Jos tuotejoukko on usein esiintyvä, myös kaikki sen osajoukot ovat usein esiintyviä.

Tämä oivallus vähentää merkittävästi arvioitavien tuotejoukkojen määrää, sillä kaikki tuotejoukot, jotka sisältävät harvinaisen osajoukon, voidaan välittömästi jättää huomiotta.

Ehdokkaiden muodostus on algoritmin yhdistelyvaihe. Jokaisella kierroksella algoritmi tarkastelee edellisen kierroksen usein esiintyviä tuotejoukkoja ja yhdistää niitä muodostaakseen uusia, suurempia ryhmiä, joita kutsutaan ehdokkaiksi. Tämän tehostamiseksi algoritmi yhdistää vain lähes identtisiä tuotejoukkoja, jotka jakavat kaikki tuotteensa paitsi viimeisen.

Toimintaperiaate: Jos algoritmi havaitsee, että {Bread, Milk} ja {Bread, Diapers} ovat molemmat suosittuja, se yhdistää ne muodostaakseen uuden kolmen tuotteen ehdokkaan seuraavalle kierrokselle: {Bread, Milk, Diapers}.

Heti uusien ehdokkaiden muodostamisen jälkeen algoritmi käynnistää karsintavaiheen poistaakseen turhat vaihtoehdot ennen raskaita tietokantahakuja. Tämä vaihe perustuu täysin Apriori-periaatteeseen, jonka mukaan suuri tuotejoukko voi olla usein esiintyvä vain, jos kaikki sen pienemmät osat ovat myös usein esiintyviä. Karsinnan aikana algoritmi tarkastelee huolellisesti jokaista uutta ehdokasta ja sen pienempiä osajoukkoja. Jos yksikin osajoukko ei läpäissyt edellistä kierrosta, koko ehdokas poistetaan välittömästi.

Toimintaperiaate: Kuvitellaan, että ehdokas {Bread, Milk, Eggs} muodostetaan. Algoritmi tarkistaa sen osat: {Bread, Milk}, {Bread, Eggs} ja {Milk, Eggs}. Jos historialliset transaktiotiedot osoittavat, että {Milk, Eggs} on harvinainen yhdistelmä, joka hylättiin aiemmalla kierroksella, algoritmi karsii {Bread, Milk, Eggs} kokonaan. Tämä säästää laskentatehoa yhdistelmiltä, joiden epäonnistuminen on matemaattisesti varmaa.

Kun ehdokaslista on karsittu elinkelpoisimpiin vaihtoehtoihin, algoritmi siirtyy vaiheeseen usein esiintyvien tuotejoukkojen tunnistus. Järjestelmä käy läpi raakatapahtumatietokannat ja laskee, kuinka monta kertaa nämä jäljelle jääneet ehdokkaat esiintyvät yhdessä oikeissa ostotapahtumissa. Jokaisen ehdokkaan kokonaismäärä muunnetaan prosenttiosuudeksi. Jos tämä arvo saavuttaa tai ylittää ennalta määritetyn minimitukikynnyksen, ehdokas nimetään virallisesti usein esiintyväksi tuotejoukoksi.

Määritelmä

Minimitukikynnys on käyttäjän määrittelemä raja-arvo, joka määrittää pienimmän esiintymistiheyden, jonka itemsetin on saavutettava ollakseen merkityksellinen Apriori-algoritmissa. Asettamalla tämän kynnyksen suodatat pois itemsetit, jotka esiintyvät liian harvoin aineistossa. Korkean kynnyksen valitseminen johtaa harvempiin, yleisempiin itemsetteihin, jolloin mielenkiintoiset mutta harvinaiset yhdistelmät voivat jäädä huomaamatta. Liian matala kynnys voi tuottaa liikaa itemsettejä, mukaan lukien käytännössä merkityksettömät yhdistelmät. Valitsemasi kynnys vaikuttaa suoraan analyysin syvyyteen ja painopisteeseen, joten sen tulisi heijastaa datatutkimuksen tavoitteita ja laajuutta.

Tämä koko kolmen vaiheen silmukka toistuu peräkkäin. Se etenee yksittäisistä tuotteista pareihin, sitten kolmen ryhmiin ja jatkaa laajentumista, kunnes saavutetaan kierros, jolla uusia usein esiintyviä itemsettejä ei enää löydy, kartoittaen onnistuneesti koko kuluttajien ostokäyttäytymisen verkoston.

Konkreettisen esimerkin avulla asia selkeytyy. Oletetaan, että käytössä on pieni aineisto seuraavilla transaktioilla:

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

Algoritmi tunnistaa ensin kaikki usein esiintyvät yksittäiset tuotteet, muodostaa niistä ehdokaspareja, karsii harvinaiset tuotteet sisältävät parit ja jatkaa tätä prosessia löytääkseen suurempia usein esiintyviä ryhmiä, kuten {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}")

Tämä Python-koodi havainnollistaa yksinkertaista Apriori-algoritmin toteutusta usein esiintyvien tuotejoukkojen tunnistamiseksi transaktiodatan perusteella. Näin kukin vaihe etenee:

Datan valmistelu

Transaktiot esitetään listojen listana, jossa jokainen alilista sisältää yhdessä ostetut tuotteet.
Kaikki yksilölliset tuotteet tunnistetaan ja lajitellaan.
Luodaan one-hot-koodattu DataFrame: jokainen rivi edustaa transaktiota ja jokainen sarake tuotetta, jossa True tai False ilmaisee tuotteen läsnäolon tai puuttumisen.

Apriori-algoritmin vaiheet

1. Usein esiintyvien 1-tuotejoukkojen tunnistaminen

Algoritmi laskee jokaisen yksittäisen tuotteen tuen (osuuden transaktioista, joissa tuote esiintyy).
Jos tuotteen tuki täyttää tai ylittää min_support-kynnyksen (tässä 0.6), se katsotaan usein esiintyväksi ja sisällytetään ensimmäiseen usein esiintyvien tuotejoukkojen listaan.

2. Ehdokkaiden muodostaminen

Pituuden k tuotejoukoille (alkaen arvosta 2) algoritmi muodostaa uusia ehdokasjoukkoja yhdistämällä edellisen kierroksen usein esiintyviä tuotejoukkoja, jotka jakavat kaikki muut paitsi yhden tuotteen.
Vain ainutlaatuiset yhdistelmät huomioidaan, jolloin kaksoiskappaleita ei synny.

3. Karsinta

Jokaisen uuden ehdokkaan kaikki pituuden k-1 alijoukot tarkistetaan.
Jos jokin alijoukko ei ole edellisen vaiheen usein esiintyvien joukossa, ehdokas karsitaan (poistetaan) Apriori-periaatteen mukaisesti.

4. Tuen laskenta

Jokaiselle jäljelle jäävälle ehdokkaalle lasketaan, kuinka monessa transaktiossa kaikki ehdokkaan tuotteet esiintyvät.
Tuki lasketaan ja verrataan kynnysarvoon. Vain kynnyksen täyttävät ehdokkaat säilytetään seuraavan kierroksen usein esiintyvinä tuotejoukkoina.

5. Iterointi

Vaiheet 2–4 toistetaan kasvattaen tuotejoukkojen kokoa, kunnes uusia usein esiintyviä joukkoja ei enää löydy.

Tuloste

Lopullinen lista sisältää kaikki usein esiintyvät tuotejoukot ja niiden tukiarvot.
Koodi tulostaa jokaisen usein esiintyvän tuotejoukon ja sen tuen, osoittaen mitkä tuotekombinaatiot esiintyvät yleisimmin transaktioissa.

1. Mikä seuraavista kuvaa parhaiten Apriori-algoritmin ehdokkaiden muodostusvaihetta?

2. Mikä on tärkein syy ehdokasjoukkojen karsintaan Apriori-algoritmissa?

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 1. Luku 4

Kysy tekoälyä

Kysy mitä tahansa tai kokeile jotakin ehdotetuista kysymyksistä aloittaaksesi keskustelumme

Osio 1. Luku 4