Oppiskele Yleisten Kuvioiden Puiden Rakentaminen FP-Growth-algoritmilla | Suorituskykyinen Sääntöjen Louhinta ja Skaalauksen Optimointi

Pyyhkäise näyttääksesi valikon

FP-Growthin yleiskatsaus

FP-Growth on suorituskykyinen algoritmi, joka on suunniteltu usein esiintyvien tuotejoukkojen louhintaan suurista transaktiotietoaineistoista. Toisin kuin Apriori, joka muodostaa ehdokasjoukkoja ja käy tietokannan läpi useaan kertaan, FP-Growth rakentaa tiiviin tietorakenteen nimeltä FP-puu (Frequent Pattern Tree), jonka avulla usein esiintyvät kuviot voidaan louhia ilman ehdokasjoukkojen muodostamista. Tämä tuo merkittäviä nopeus- ja muistietuja erityisesti aineistoissa, joissa on paljon usein esiintyviä kuvioita.

Puun rakenne

FP-puu tiivistää kaikki transaktiot prefiksipuun muotoon. Jokainen transaktio käsitellään järjestämällä sen tuotteet laskevan esiintymistiheyden mukaan ja lisäämällä ne puuhun siten, että jaetaan yhteiset prefiksit olemassa olevien polkujen kanssa. Juurisolmu on nollasolmu, joka toimii sisäänkäyntinä, ja jokainen puun solmu edustaa tuotetta sekä lukumäärää, kuinka moni transaktio jakaa kyseisen prefiksin siihen asti.

Solmujen linkitys

Tehokkaan louhinnan mahdollistamiseksi kaikki saman tuotteen solmut yhdistetään linkitettyyn listaan, jota kutsutaan otsikkotaulukoksi. Tämän avulla voidaan nopeasti käydä läpi kaikki tietyn tuotteen esiintymät puussa. Jokainen otsikkotaulukon merkintä osoittaa ensimmäiseen kyseisen tuotteen solmuun puussa, ja jokaisessa solmussa on linkki seuraavaan saman tuotteen solmuun.

Kuvioiden louhinta

Usein esiintyvien kuvioiden louhinta FP-puusta koostuu kahdesta päävaiheesta. Ensin puuta käydään läpi alhaalta ylöspäin seuraamalla otsikkotaulukon linkkejä kullekin tuotteelle ja kerätään kaikki prefiksipolut, jotka johtavat kyseiseen tuotteeseen. Tämän jälkeen rakennetaan ehdolliset FP-puut jokaiselle tuotteelle ja louhitaan niitä rekursiivisesti kaikkien usein esiintyvien tuotejoukkojen löytämiseksi. Tämä rekursiivinen prosessi jatkuu, kunnes uusia usein esiintyviä kuvioita ei enää löydy.

Esimerkki: FP-puun rakentaminen vaihe vaiheelta

Käydään läpi tarkka vaiheittainen rakentaminen käyttäen esimerkkitapahtumiasi ja oletetaan minimituen kynnysarvoksi 2 (eli tuotteen tulee esiintyä vähintään kahdesti, jotta se huomioidaan).

Oletetaan, että sinulla on seuraavat tapahtumat:

- Tapahtuma 1: A, B, D;
- Tapahtuma 2: B, C, E;
- Tapahtuma 3: A, B, C, E;
- Tapahtuma 4: B, E.

Vaihe 1: Tietokannan läpikäynti ja lajittelu esiintymistiheyden mukaan

Aluksi algoritmi lukee koko aineiston ja laskee, kuinka monta kertaa kukin yksittäinen tuote esiintyy. Kaikki tuotteet, jotka jäävät alle minimituen, poistetaan. Tämän jälkeen muodostetaan globaali lajittelujärjestys korkeimmasta matalimpaan esiintymistiheyteen.

Globaalit tuotemäärät:

B esiintyy 4 kertaa

E esiintyy 3 kertaa

A esiintyy 2 kertaa

C esiintyy 2 kertaa

D esiintyy 1 kerran (Poistetaan, koska se jää alle minimituen 2)

Lopullinen lajittelusääntö: Jokainen tapahtuma suodatetaan ja järjestetään nyt noudattamaan tätä laskevaa esiintymistiheysjärjestystä:

$\mathbf{B} \longrightarrow \mathbf{E} \longrightarrow \mathbf{A} \longrightarrow \mathbf{C}$

Vaihe 2: Järjestä jokainen tapahtuma uudelleen

Ennen kuin tuotteet lisätään puuhun, algoritmi kirjoittaa jokaisen tapahtuman uudelleen. Se poistaa harvinaisen tuotteen (D) ja järjestää jäljelle jäävät tuotteet uuden globaalin järjestyksen mukaisesti.

- Tapahtuma 1: A, B, D muuttuu B, A
- Tapahtuma 2: B, C, E muuttuu B, E, C
- Tapahtuma 3: A, B, C, E muuttuu B, E, A, C
- Tapahtuma 4: B, E muuttuu B, E

Vaihe 3: Polkujen lisääminen FP-puuhun

Jokainen FP-puu alkaa tyhjällä solmulla, jota kutsutaan Null Root Node -juurisolmuksi. Nyt lisätään uudelleen järjestetyt tapahtumat puuhun yksi kerrallaan, kasvattaen laskureita kun polut menevät päällekkäin ja haarautuen kun ne eroavat toisistaan.

Lisää tapahtuma 1 {B, A}: puu luo uuden haaran suoraan juuresta alas.

Lisää tapahtuma 2 {B, E, C}: algoritmi aloittaa juuresta ja tarkistaa ensimmäisen tuotteen, B. Koska B on jo juuren lapsena, polku menee päällekkäin! Algoritmi siirtyy B:hen ja kasvattaa sen laskuria arvoon 2. Seuraava tuote on E. Koska B:llä ei vielä ole lasta nimeltä E, puu haarautuu tässä ja luo uuden alahaaran E:lle, jota seuraa C.

Lisää tapahtuma 3 {B, E, A, C}: aloittaen juuresta, polku kulkee B:n kautta (laskuri kasvaa arvoon 3), sitten alas olemassa olevalle E-solmulle (laskuri kasvaa arvoon 2). Seuraava tuote on A. Koska E:llä ei ole lasta nimeltä A, puu luo uuden haaran E:n alle (A:1) -> (C:1).

Lisää tapahtuma 4 {B, E}: algoritmi kulkee suosituimman etupolun läpi ja B kasvaa arvoon 4, E kasvaa arvoon 3. Tapahtuma päättyy tähän, joten uusia solmuja ei lisätä.

(Null Root) | (B: 4) / \ (A: 1) (E: 3) / \ (C: 1) (A: 1) | (C: 1)


              12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
            
transactions = [
    ['A', 'B', 'D'],
    ['B', 'C', 'E'],
    ['A', 'B', 'C', 'E'],
    ['B', 'E']
]

# Step 1: Counting item frequency
from collections import defaultdict, Counter

item_counts = Counter()
for transaction in transactions:
    item_counts.update(transaction)

# Step 2: Removing infrequent items
min_support = 2
freq_items = {item for item, count in item_counts.items() if count >= min_support}

# Step 3: Sorting items in each transaction by frequency
def sort_transaction(transaction):
    return sorted([item for item in transaction if item in freq_items],
                  key=lambda item: (-item_counts[item], item))

sorted_transactions = [sort_transaction(t) for t in transactions]

# Step 4: Defining FP-Tree node class
class FPTreeNode:
    def __init__(self, item, count, parent):
        self.item = item
        self.count = count
        self.parent = parent
        self.children = {}
        self.link = None  # Node link for header table

# Step 5: Building the FP-Tree and header table
def build_fp_tree(transactions):
    root = FPTreeNode(None, 1, None)
    header_table = defaultdict(list)

    for transaction in transactions:
        current = root
        for item in transaction:
            if item not in current.children:
                current.children[item] = FPTreeNode(item, 1, current)
                header_table[item].append(current.children[item])
            else:
                current.children[item].count += 1
            current = current.children[item]
    # Linking nodes in header table
    for item, nodes in header_table.items():
        for i in range(len(nodes) - 1):
            nodes[i].link = nodes[i + 1]
    return root, header_table

fp_root, header_table = build_fp_tree(sorted_transactions)

# Step 6: Printing the FP-Tree
def print_tree(node, indent=0):
    if node.item is not None:
        print('  ' * indent + f"{node.item}:{node.count}")
    for child in node.children.values():
        print_tree(child, indent + 1)

print_tree(fp_root)

Tämä koodiesimerkki näyttää, kuinka FP-puu rakennetaan tapahtumalistasta Pythonilla. Tässä on yksityiskohtainen selitys jokaisesta vaiheesta:

Tuotteiden esiintymistiheyksien laskeminen:
- Koodi käyttää Counter-luokkaa (collections-moduulista) laskeakseen, kuinka monta kertaa kukin tuote esiintyy kaikissa tapahtumissa;
- Tämä auttaa tunnistamaan, mitkä tuotteet ovat riittävän yleisiä sisällytettäväksi puuhun.
Harvinaisten tuotteiden poistaminen:
- Tuotteet, jotka eivät täytä minimituen kynnystä, suodatetaan pois;
- Joukko freq_items sisältää vain tuotteet, jotka esiintyvät vähintään niin monta kertaa kuin min_support määrittää.
Tapahtumien lajittelu esiintymistiheyden mukaan:
- Jokainen tapahtuma suodatetaan niin, että vain yleiset tuotteet jäävät jäljelle;
- Tuotteet järjestetään sitten laskevaan globaaliin esiintymistiheyteen (ja aakkosjärjestykseen tasatilanteissa);
- Lajittelu maksimoi etupolkujen jakamisen FP-puussa, mikä tekee puusta kompaktimman.
FP-puun solmuluokan määrittely:
- FPTreeNode-luokka edustaa jokaista solmua puussa;
- Jokainen solmu tallentaa tuotteen nimen, laskurin, osoittimen vanhempaan, sanakirjan lapsista ja linkin seuraavaan saman tuotteen solmuun (otsikkotaulukon läpikäyntiä varten).
FP-puun ja otsikkotaulukon rakentaminen:
- build_fp_tree-funktio luo puun lisäämällä jokaisen lajitellun tapahtuman;
- Aloittaen juuresta, jokaisen tapahtuman kohdalla tarkistetaan, onko lapsisolmua olemassa—jos ei, luodaan uusi ja lisätään se otsikkotaulukkoon;
- Jos solmu on jo olemassa, sen laskuria kasvatetaan;
- Kun puu on rakennettu, koodi linkittää kaikki saman tuotteen solmut link-attribuutin avulla, mikä mahdollistaa nopean läpikäynnin otsikkotaulukon kautta.
FP-puun rakenteen tulostaminen:
- print_tree-funktio näyttää puun rakenteen tulostamalla rekursiivisesti jokaisen solmun ja sen laskurin sisennyksellä, joka havainnollistaa puun rakennetta;
- Tämä tuloste auttaa visualisoimaan, miten tapahtumat tiivistyvät jaetuille poluille FP-puussa.

1. Mikä seuraavista on FP-Growth-algoritmin keskeinen etu verrattuna Apriori-algoritmiin?

2. Mikä on FP-Puun solmun rakenne?

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 2. Luku 1

Kysy tekoälyä

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

Osio 2. Luku 1