frequent pattern growth algorithm data mining
Podrobný návod na algoritmus častého rastu, ktorý predstavuje databázu vo forme stromu FP. Zahŕňa FP Growth Vs Apriori Porovnanie:
Aprioriho algoritmus bol podrobne vysvetlený v našom predchádzajúcom návode. V tomto tutoriále sa dozvieme o častom raste vzorov - FP Growth je metóda ťažby častých množín položiek.
bezplatný softvér na správu kostolov v plnej verzii
Ako všetci vieme, Apriori je algoritmus pre častú ťažbu vzorov, ktorý sa zameriava na generovanie množín položiek a objavovanie najbežnejšej množiny položiek. Výrazne zmenšuje veľkosť množiny položiek v databáze, Apriori má však tiež svoje vlastné nedostatky.
Prečítajte si naše Celá školiaca séria ťažby dát pre úplnú znalosť konceptu.
Čo sa dozviete:
- Nedostatky aprioriho algoritmu
- Algoritmus častého rastu vzorcov
- FP strom
- Kroky častého algoritmu
- Príklad FP-rastového algoritmu
- Výhody rastového algoritmu FP
- Nevýhody FP-rastového algoritmu
- FP Growth vs Apriori
- SVIETIŤ
- Záver
- Odporúčané čítanie
Nedostatky aprioriho algoritmu
- Používanie Apriori vyžaduje generáciu kandidátskych položiek. Ak je sada položiek v databáze obrovská, ich počet môže byť veľký.
- Apriori potrebuje viacnásobné skenovanie databázy, aby skontroloval podporu každej vygenerovanej množiny položiek, čo vedie k vysokým nákladom.
Tieto nedostatky je možné prekonať pomocou algoritmu rastu FP.
Algoritmus častého rastu vzorcov
Tento algoritmus je vylepšením metódy Apriori. Generuje sa častý vzor bez potreby generovania kandidátov. Algoritmus rastu FP predstavuje databázu vo forme stromu nazývaného častý vzorový strom alebo FP strom.
Táto stromová štruktúra zachová asociáciu medzi množinami položiek. Databáza je fragmentovaná pomocou jednej častej položky. Táto fragmentovaná časť sa nazýva „fragment fragmentu“. Analyzujú sa položky týchto fragmentovaných vzorov. Týmto spôsobom je teda porovnanie pomerne častého vyhľadávania častých položiek zmenšené.
FP strom
Frequent Pattern Tree je stromová štruktúra, ktorá je vytvorená s počiatočnými množinami položiek databázy. Účelom stromu FP je ťažiť najbežnejší vzorec. Každý uzol stromu FP predstavuje položku množiny položiek.
Koreňový uzol predstavuje hodnotu null, zatiaľ čo dolné uzly predstavujú množiny položiek. Pri vytváraní stromu sa zachováva asociácia uzlov s dolnými uzlami, ktoré sú množinami položiek, s ostatnými množinami položiek.
Kroky častého algoritmu
Metóda častého rastu vzorov nám umožňuje nájsť častý vzor bez generovania kandidátov.
Pozrime sa na kroky, ktoré boli dodržané pri získavaní častých vzorov pomocou algoritmu častého rastu vzorov:
# 1) Prvým krokom je skenovanie databázy, aby sa zistili výskyty množín položiek v databáze. Tento krok je rovnaký ako prvý krok programu Apriori. Počet 1-položiek v databáze sa nazýva počet podpôr alebo frekvencia 1-položiek.
#dva) Druhým krokom je zostrojenie stromu FP. Za týmto účelom vytvorte koreň stromu. Koreň predstavuje null.
# 3) Ďalším krokom je opätovné skenovanie databázy a preskúmanie transakcií. Preskúmajte prvú transakciu a nájdite v nej množinu položiek. Množina položiek s maximálnym počtom sa berie na vrchu, ďalšia množina položiek s nižším počtom atď. To znamená, že vetva stromu je skonštruovaná z množiny transakčných položiek v zostupnom poradí.
# 4) Preskúma sa ďalšia transakcia v databáze. Množiny položiek sú zoradené v zostupnom poradí podľa počtu. Ak je ktorákoľvek množina položiek tejto transakcie už prítomná v inej vetve (napríklad v 1. transakcii), potom by táto vetva transakcie zdieľala spoločnú predponu s koreňom.
To znamená, že spoločná množina položiek je spojená s novým uzlom inej množiny položiek v tejto transakcii.
# 5) Rovnako sa zvyšuje počet položiek v priebehu transakcií. Počet spoločných uzlov aj nových uzlov sa zvyšuje o 1, keď sa vytvárajú a prepájajú podľa transakcií.
# 6) Ďalším krokom je ťažba vytvoreného stromu FP. Z tohto dôvodu sa najskôr skúma najnižší uzol spolu s väzbami najnižších uzlov. Najnižší uzol predstavuje dĺžku kmitočtového obrazca 1. Z tohto miesta prechádzajte po ceste v strome FP. Táto cesta alebo cesty sa nazývajú podmienený základ vzorov.
najlepšie odstránenie vírusov pre Windows 10
Podmienečný základ vzorov je sub-databáza pozostávajúca z prefixových ciest v strome FP vyskytujúcich sa s najnižším uzlom (príponou).
# 7) Zostrojte podmienený strom FP, ktorý je tvorený počtom množín položiek v ceste. Množiny položiek, ktoré spĺňajú podporu prahových hodnôt, sa považujú za podmienené FP stromy.
# 8) Časté vzory sa generujú z podmieneného stromu FP.
Príklad FP-rastového algoritmu
Prahová hodnota podpory = 50%, spoľahlivosť = 60%
stôl 1
Transakcia | Zoznam položiek |
---|---|
Využitie pamäte | |
T1 | I1, I2, I3 |
T2 | I2, I3, I4 |
T3 | 14, 15 |
T4 | I1, I2, I4 |
T5 | I1, I2, I3, I5 |
T6 | I1, I2, I3, I4 |
Riešenie:
Prahová hodnota podpory = 50% => 0,5 * 6 = 3 => min_sup = 3
1. Počet každej položky
Tabuľka 2
Položka | Gróf |
---|---|
I1 | 4 |
I2 | 5 |
I3 | 4 |
14 | 4 |
I5 | dva |
2. Zoraďte zostavu položiek v zostupnom poradí.
Tabuľka 3
Položka | Gróf |
---|---|
I2 | 5 |
I1 | 4 |
I3 | 4 |
14 | 4 |
3. Zostavte strom FP
- Vzhľadom na to, že koreňový uzol je neplatný.
- Prvý sken transakcie T1: I1, I2, I3 obsahuje tri položky {I1: 1}, {I2: 1}, {I3: 1}, kde I2 je prepojená ako dieťa s rootom, I1 je prepojená s I2 a I3 je spojené s I1.
- T2: I2, I3, I4 obsahuje I2, I3 a I4, kde I2 je spojená s koreňom, I3 je spojená s I2 a I4 je spojená s I3. Ale táto vetva by zdieľala I2 uzol tak bežný, ako sa už používa v T1.
- Zvýši počet I2 o 1 a I3 je spojená ako dieťa s I2, I4 je spojená ako dieťa s I3. Počet je {I2: 2}, {I3: 1}, {I4: 1}.
- T3: I4, I5. Podobne je nová pobočka s I5 prepojená s I4, keď sa vytvára dieťa.
- T4: I1, I2, I4. Sekvencia bude I2, I1 a I4. I2 je už prepojený s koreňovým uzlom, preto sa zvýši o 1. Podobne sa zvýši I1 o 1, pretože je už prepojený s I2 v T1, teda {I2: 3}, {I1: 2}, {I4: 1}.
- T5: I1, I2, I3, I5. Sekvencia bude I2, I1, I3 a I5. Teda {I2: 4}, {I1: 3}, {I3: 2}, {I5: 1}.
- T6: I1, I2, I3, I4. Sekvencia bude I2, I1, I3 a I4. Teda {I2: 5}, {I1: 4}, {I3: 3}, {I4 1}.
4. Ťažba stromu FP je zhrnutá nižšie:
- Položka I5 s najnižším uzlom sa neberie do úvahy, pretože nemá minimálny počet podpôr, a preto je odstránená.
- Ďalším dolným uzlom je I4. I4 sa vyskytuje v 2 vetvách, {I2, I1, I3:, I41}, {I2, I3, I4: 1}. Ak teda vezmeme ako príponu I4, cesty prefixov budú {I2, I1, I3: 1}, {I2, I3: 1}. Toto vytvára podmienený základ vzoru.
- Podmienený základ vzorov sa považuje za databázu transakcií, je skonštruovaný strom FP. Bude obsahovať {I2: 2, I3: 2}, na I1 sa neprihliada, pretože nespĺňa minimálny počet podporovaných údajov.
- Táto cesta vygeneruje všetky kombinácie častých vzorov: {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
- Pre I3 by cesta prefixu bola: {I2, I1: 3}, {I2: 1}, vygeneruje sa 2-uzlový strom FP: {I2: 4, I1: 3} a vygenerujú sa časté vzory: {I2 , I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}.
- Pre I1 by cesta prefixu bola: {I2: 4} vygeneruje sa jediný uzol FP-strom: {I2: 4} a vygenerujú sa časté vzory: {I2, I1: 4}.
Položka | Podmienečný podkladový vzor | Podmienený strom FP | Generované časté vzory |
---|---|---|---|
14 | {I2, I1, I3: 1}, {I2, I3: 1} | {I2: 2, I3: 2} | {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2} |
I3 | {I2, I1: 3}, {I2: 1} | {I2: 4, I1: 3} | {I2, I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3} |
I1 | {I2: 4} | {I2: 4} | {I2, I1: 4} |
Schéma uvedená nižšie zobrazuje podmienený strom FP spojený s podmieneným uzlom I3.
Výhody rastového algoritmu FP
- Tento algoritmus potrebuje skenovať databázu iba dvakrát v porovnaní s programom Apriori, ktorý skenuje transakcie pre každú iteráciu.
- Párovanie položiek sa v tomto algoritme nevykonáva, čo ho urýchľuje.
- Databáza je uložená v kompaktnej verzii v pamäti.
- Je efektívny a škálovateľný na ťažbu dlhých aj krátkych častých vzorov.
Nevýhody FP-rastového algoritmu
- FP Tree je ťažkopádnejší a ťažšie zostaviteľný ako Apriori.
- Môže to byť drahé.
- Keď je databáza veľká, algoritmus sa nemusí zmestiť do zdieľanej pamäte.
FP Growth vs Apriori
FP rast | Apriori |
---|---|
Generovanie vzorov | |
Rast FP generuje vzor konštruovaním stromu FP | Apriori generuje vzor spárovaním položiek do singletonov, párov a trojíc. |
Generácia kandidátov | |
Neexistuje generácia kandidátov | Apriori používa generáciu kandidátov |
Proces | |
Proces je v porovnaní s Apriori rýchlejší. Doba chodu procesu sa lineárne zvyšuje s nárastom počtu množín položiek. | Proces je pomerne pomalší ako rast FP, doba chodu sa zvyšuje exponenciálne s nárastom počtu množín položiek |
Uloží sa kompaktná verzia databázy | Kombinácie kandidátov sú uložené v pamäti |
SVIETIŤ
Vyššie uvedená metóda, Apriori a FP growth, ťaží časté sady položiek pomocou horizontálneho dátového formátu. ECLAT je metóda ťažby častých množín položiek pomocou vertikálneho dátového formátu. Transformuje údaje v horizontálnom formáte údajov do vertikálneho formátu.
bezplatná ochrana brány firewall pre systém Windows 7
Napríklad,Apriori a FP použitie rastu:
Transakcia | Zoznam položiek |
---|---|
T1 | I1, I2, I3 |
T2 | I2, I3, I4 |
T3 | 14, 15 |
T4 | I1, I2, I4 |
T5 | I1, I2, I3, I5 |
T6 | I1, I2, I3, I4 |
ECLAT bude mať formát tabuľky ako:
Položka | Sada transakcií |
---|---|
I1 | {T1, T4, T5, T6} |
I2 | {T1, T2, T4, T5, T6} |
I3 | {T1, T2, T5, T6} |
14 | {T2, T3, T4, T5} |
I5 | {T3, T5} |
Táto metóda vytvorí vo vertikálnom dátovom formáte 2-položky, 3 položky, sady k. Tento proces s k sa zvyšuje o 1, kým sa nenájdu žiadne kandidátske sady položiek. Spolu s Apriori sa používajú niektoré optimalizačné techniky, ako napríklad diffset.
Táto metóda má oproti Apriori výhodu, pretože nevyžaduje skenovanie databázy s cieľom nájsť podporu k množinám položiek k + 1. Je to tak preto, lebo sada Transakcie bude obsahovať počet výskytov každej položky v transakcii (podpora). Úzke miesto nastáva, keď existuje veľa transakcií, ktoré na prieniky množín vyžadujú obrovskú pamäť a výpočtový čas.
Záver
Algoritmus Apriori sa používa na dolovanie asociačných pravidiel. Funguje na princípe, „časté musia byť aj neprázdne podmnožiny častých položiek“. Formuje kandidátov na k-položky z (k-1) položiek a skenuje databázu, aby našla časté sady položiek.
Algoritmus častého rastu vzorcov je metóda hľadania častých vzorcov bez generovania kandidátov. Konštruuje FP strom namiesto použitia stratégie generovania a testovania Apriori. Algoritmus FP Growth sa zameriava na fragmentáciu dráh položiek a ťažbu častých vzorov.
Dúfame, že tieto návody v sérii Data Mining Series obohatili vaše vedomosti o Data Mining !!
Výukový program PREV | PRVÝ výukový program
Odporúčané čítanie
- Techniky dolovania dát: Algoritmus, metódy a najlepšie nástroje na dolovanie dát
- Apriori Algorithm in Mining Data: Implementácia s príkladmi
- Príklady algoritmu rozhodovacieho stromu v dolovaní dát
- Príklady dolovania dát: Najčastejšie aplikácie dolovania dát 2021
- Ťažba dát: Proces, techniky a hlavné problémy v analýze dát
- Proces ťažby dát: zúčastnené modely, kroky procesu a výzvy
- Vzor otázky týkajúcej sa certifikácie skúšok softvéru CSTE
- Data Mining vs. Machine Learning vs. Artificial Intelligence vs. Deep Learning