Algoritem rasti pogostega vzorca (FP) pri rudarjenju podatkov

frequent pattern growth algorithm data mining

Podrobna vadnica o pogostnem algoritmu rasti vzorca, ki predstavlja bazo podatkov v obliki FP drevo. Vključuje primerjavo FP Growth Vs Apriori:

Apriori algoritem je bilo podrobno razloženo v naši prejšnji vadnici. V tej vadnici bomo izvedeli več o pogosti rasti vzorca - FP Growth je način pridobivanja pogostih naborov predmetov.

kako bi preizkusil pisalo

Kot vsi vemo, je Apriori algoritem za pogosto rudarjenje vzorcev, ki se osredotoča na ustvarjanje naborov predmetov in odkrivanje najpogostejših naborov elementov. Močno zmanjša velikost nabora elementov v zbirki podatkov, vendar ima Apriori tudi svoje pomanjkljivosti.

Preberite našo Celotna serija usposabljanja za rudarjenje podatkov za popolno poznavanje koncepta.

Kaj se boste naučili:

• Pomanjkljivosti Apriorijevega algoritma
• Algoritem pogoste rasti vzorca
• Drevo FP
• Pogosti koraki algoritma vzorca
• Primer algoritma rasti FP
• Prednosti algoritma rasti FP
• Slabosti algoritma rasti FP
• Rast FP vs Apriori
• ECLAT
• Zaključek
• Priporočeno branje

Pomanjkljivosti Apriorijevega algoritma

1. Za uporabo Apriorija je potrebna generacija nabora kandidatov. Število teh naborov je lahko veliko, če je nabor elementov v zbirki podatkov ogromen.
2. Apriori potrebuje več pregledov baze podatkov, da preveri podporo vsakemu ustvarjenemu naboru elementov, kar vodi do visokih stroškov.

Te pomanjkljivosti je mogoče odpraviti z uporabo algoritma rasti FP.

Algoritem pogoste rasti vzorca

Ta algoritem je izboljšava metode Apriori. Ustvari se pogost vzorec, ne da bi bilo treba generirati kandidate. Algoritem rasti FP predstavlja bazo podatkov v obliki drevesa, imenovanega pogosto drevo vzorcev ali drevo FP.

Ta drevesna struktura bo ohranila povezavo med nabori elementov. Baza podatkov je razdrobljena z enim pogostim elementom. Ta razdrobljeni del se imenuje 'fragment vzorca'. Analizirajo se sklopi teh razdrobljenih vzorcev. Tako se pri tej metodi iskanje pogostih naborov predmetov sorazmerno zmanjša.

Drevo FP

Drevo pogostih vzorcev je drevesni strukturi, ki je narejena z začetnimi nabori elementov baze podatkov. Namen drevesa FP je izkopati najpogostejši vzorec. Vsako vozlišče drevesa FP predstavlja element nabora elementov.

Koreninsko vozlišče predstavlja nič, spodnja vozlišča pa nabore elementov. Povezovanje vozlišč z nižjimi vozlišči, ki so nabori elementov, se ohrani med oblikovanjem drevesa.

Pogosti koraki algoritma vzorca

Metoda pogoste rasti vzorca nam omogoča, da poiščemo pogost vzorec brez generacije kandidatov.

Oglejmo si korake, ki so sledili za pridobivanje pogostega vzorca z uporabo algoritma pogoste rasti vzorcev:

# 1) Prvi korak je skeniranje baze podatkov, da bi našli pojavitve naborov elementov v bazi podatkov. Ta korak je enak prvemu koraku Apriorija. Število naborov 1 v bazi se imenuje število podpor ali pogostost nabora 1.

#two) Drugi korak je izdelava drevesa FP. Za to ustvarite koren drevesa. Koren predstavlja nič.

# 3) Naslednji korak je ponovno skeniranje baze podatkov in pregled transakcij. Preučite prvo transakcijo in v njej poiščite nabor izdelkov. Nabor elementov z največjim številom se vzame na vrh, naslednji niz z manjšim številom itd. To pomeni, da je veja drevesa izdelana z nabori postavk transakcij v padajočem vrstnem redu štetja.

# 4) Preuči se naslednja transakcija v zbirki podatkov. Nabori predmetov so razvrščeni po padajočem štetju. Če je kateri koli nabor elementov te transakcije že prisoten v drugi veji (na primer v 1. transakciji), bo ta veja transakcije delila skupno predpono s korenom.

To pomeni, da je skupni nabor elementov povezan z novim vozliščem drugega nabora elementov v tej transakciji.

# 5) Prav tako se število naborov elementov poveča, ko se pojavi pri transakcijah. Skupno vozlišče in število novih vozlišč se povečata za 1, ko sta ustvarjena in povezana glede na transakcije.

vprašanja in odgovori za intervju z ado.net za izkušene

# 6) Naslednji korak je miniranje ustvarjenega drevesa FP. Za to se najprej pregleda najnižje vozlišče skupaj s povezavami najnižjih vozlišč. Najnižje vozlišče predstavlja dolžino frekvenčnega vzorca 1. Od tega prehodite pot v drevesu FP. Ta pot ali poti se imenujejo pogojna osnova vzorca.

Pogojna osnova vzorca je podbaza podatkov, sestavljena iz poti predpone v drevesu FP, ki se pojavljajo z najnižjim vozliščem (pripona).

# 7) Sestavite pogojno drevo FP, ki ga tvori število naborov elementov na poti. Nabori elementov, ki izpolnjujejo prag podpore, so obravnavani v pogojnem drevesu FP.

# 8) Pogosti vzorci se ustvarijo iz pogojnega drevesa FP.

Primer algoritma rasti FP

Prag podpore = 50%, zaupanje = 60%

Preglednica 1

Rešitev:

Prag podpore = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Štetje vsakega predmeta

Preglednica 2

2. Razvrstite nabor predmetov v padajočem vrstnem redu.

Preglednica 3

3. Zgradite drevo FP

1. Glede na nulo korenskega vozlišča.
2. Prvo skeniranje transakcije T1: I1, I2, I3 vsebuje tri elemente {I1: 1}, {I2: 1}, {I3: 1}, kjer je I2 kot podrejen povezan s korenom, I1 je povezan z I2 in I3 je povezan z I1.
3. T2: I2, I3, I4 vsebuje I2, I3 in I4, kjer je I2 povezan s korenom, I3 je povezan z I2 in I4 je povezan z I3. Toda ta veja bi si delila vozlišče I2 tako pogosto, kot se že uporablja v T1.
4. Povečajte število I2 za 1 in I3 je kot otrok povezan z I2, I4 je kot otrok povezan z I3. Štetje je {I2: 2}, {I3: 1}, {I4: 1}.
5. T3: I4, I5. Podobno je nova veja z I5 povezana z I4, ko je ustvarjen otrok.
6. T4: I1, I2, I4. Zaporedje bo I2, I1 in I4. I2 je že povezan s korenskim vozliščem, zato se bo povečal za 1. Podobno se bo I1 povečal za 1, saj je v T1 že povezan z I2, torej {I2: 3}, {I1: 2}, {I4: 1}.
7. T5: I1, I2, I3, I5. Zaporedje bo I2, I1, I3 in I5. Tako {I2: 4}, {I1: 3}, {I3: 2}, {I5: 1}.
8. T6: I1, I2, I3, I4. Zaporedje bo I2, I1, I3 in I4. Tako {I2: 5}, {I1: 4}, {I3: 3}, {I4 1}.

4. Rudarstvo FP-drevesa je povzeto spodaj:

1. Element najnižjega vozlišča I5 se ne upošteva, ker nima najmanjšega števila podpore, zato je izbrisan.
2. Naslednje spodnje vozlišče je I4. I4 se pojavlja v dveh vejah, {I2, I1, I3:, I41}, {I2, I3, I4: 1}. Torej, če upoštevamo I4 kot pripono, bodo poti predpone {I2, I1, I3: 1}, {I2, I3: 1}. To tvori pogojno osnovo vzorca.
3. Pogojna osnova vzorca se šteje za bazo podatkov o transakcijah, izdelano je FP-drevo. Ta bo vseboval {I2: 2, I3: 2}, I1 se ne upošteva, saj ne ustreza številu najmanjših podpor.
4. Ta pot bo ustvarila vse kombinacije pogostih vzorcev: {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
5. Za I3 bi bila pot predpone: {I2, I1: 3}, {I2: 1}, to bo ustvarilo FP-drevo z dvema vozliščema: {I2: 4, I1: 3} in generirani bodo pogosti vzorci: {I2 , I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}.
6. Za I1 bi bila pot predpone: {I2: 4} to bo ustvarilo eno vozlišče FP-drevo: {I2: 4} in pogosti vzorci bodo ustvarjeni: {I2, I1: 4}.

Spodnji diagram prikazuje pogojno drevo FP, povezano s pogojnim vozliščem I3.

zakaj je c ++ boljši od jave

Prednosti algoritma rasti FP

1. Ta algoritem mora zbirko podatkov skenirati le dvakrat v primerjavi z Apriori, ki skenira transakcije za vsako ponovitev.
2. Seznanjanje elementov v tem algoritmu ni izvedeno in je to hitrejše.
3. Baza podatkov je shranjena v kompaktni različici v pomnilniku.
4. Je učinkovit in razširljiv za rudarjenje tako dolgih kot kratkih pogostih vzorcev.

Slabosti algoritma rasti FP

1. FP Tree je bolj okorno in ga je težko graditi kot Apriori.
2. Morda je drago.
3. Če je baza podatkov velika, algoritem morda ne bo v skupnem pomnilniku.

Rast FP vs Apriori

ECLAT

Zgornja metoda, rast Apriori in FP, pogosto zbira predmete z uporabo vodoravne oblike podatkov. ECLAT je metoda rudarjenja pogostih naborov predmetov z uporabo vertikalne oblike podatkov. Podatke v vodoravni obliki podatkov bo spremenil v navpično obliko.

Na primer,Uporaba Apriori in FP za rast:

ECLAT bo imel tabelo v obliki:

Ta metoda bo oblikovala nabore 2, 3 nabore in k naborov elementov v navpični obliki podatkov. Ta postopek s k se poveča za 1, dokler ni mogoče najti nabora kandidatov. Skupaj z Apriori se uporabljajo nekatere tehnike optimizacije, kot je difset.

Ta metoda ima prednost pred Apriori, saj ne zahteva skeniranja baze podatkov, da bi našli podporo za k + 1 nabore elementov. To je zato, ker bo nabor transakcij vseboval število pojavitev vsakega elementa v transakciji (podpora). Ozko grlo pride, ko je veliko transakcij, ki potrebujejo ogromen pomnilnik in računski čas za sekanje množic.

Zaključek

Apriorijev algoritem se uporablja za pravila združevanja rudarjev. Deluje po načelu, 'pogoste morajo biti tudi neprazne podnabore pogostih naborov'. Iz naborov elementov (k-1) oblikuje kandidate za k-itemset in pregleda zbirko podatkov, da bi našel pogoste nabore elementov.

Algoritem pogoste rasti vzorca je metoda iskanja pogostih vzorcev brez generiranja kandidatov. Zgradi drevo FP, namesto da bi uporabil strategijo ustvarjanja in preizkušanja Apriorija. Poudarek algoritma FP Growth je na fragmentiranju poti elementov in pridobivanju pogostih vzorcev.

Upamo, da so te vadnice iz serije Data Mining obogatile vaše znanje o Data Mining !!

PREV Vadnica | PRVA Vadnica

Priporočeno branje

• Tehnike rudarjenja podatkov: algoritem, metode in najboljša orodja za rudarjenje podatkov
• Apriorijev algoritem v rudarjenju podatkov: izvedba s primeri
• Primeri algoritma drevesa odločanja v rudarjenju podatkov
• Primeri rudarjenja podatkov: najpogostejše uporabe podatkovnega rudarjenja 2021
• Podatkovno rudarjenje: postopek, tehnike in glavna vprašanja pri analizi podatkov
• Proces rudarjenja podatkov: vključeni modeli, koraki in izzivi
• Vzorec vprašanja za preverjanje izpita za preizkušanje programske opreme CSTE
• Data Mining Vs Machine Learning Vs Umetna inteligenca Vs Poglobljeno učenje