Menu

Apriori Algorithm in Mining Data: Implementácia s príkladmi

  • Hlavná
  • Iné
  • Apriori Algorithm in Mining Data: Implementácia s príkladmi

apriori algorithm data mining

Hĺbkový tutoriál o aprioriho algoritme na zistenie častých položiek v ťažbe dát. V tomto výučbe sú vysvetlené jednotlivé kroky a ako to funguje:

V tomto Séria výučbových programov pre ťažbu dát , pozreli sme sa na Algoritmus rozhodovacieho stromu v našom predchádzajúcom návode.

Existuje niekoľko metód pre dolovanie dát, ako je asociácia, korelácia, klasifikácia a klastrovanie.

Tento výukový program sa primárne zameriava na ťažbu pomocou pravidiel asociácie. Podľa pravidiel asociácie identifikujeme množinu položiek alebo atribútov, ktoré sa vyskytujú spoločne v tabuľke.

Apriori algoritmus

Čo sa dozviete:

Čo je to položka?

Sada položiek dohromady sa nazýva sada položiek. Ak má ktorákoľvek množina položiek k-položky, nazýva sa to k-položka. Sada položiek sa skladá z dvoch alebo viacerých položiek. Množina položiek, ktorá sa vyskytuje často, sa nazýva častá množina položiek. Častá ťažba množín položiek je teda technika ťažby údajov na identifikáciu položiek, ktoré sa často vyskytujú spoločne.

Napríklad , Chlieb s maslom, Laptop a antivírusový softvér atď.

Čo je častá položka?

Sada položiek sa nazýva častá, ak spĺňa minimálnu prahovú hodnotu pre podporu a spoľahlivosť. Podpora zobrazuje transakcie s položkami zakúpenými spoločne v jednej transakcii. Dôvera ukazuje transakcie, pri ktorých sú položky nakupované jeden za druhým.

Pri metóde ťažby častých položiek uvažujeme iba tie transakcie, ktoré spĺňajú požiadavky minimálnej prahovej hodnoty a spoľahlivosti. Poznatky z týchto ťažobných algoritmov ponúkajú veľa výhod, zníženie nákladov a vylepšenú konkurenčnú výhodu.

Na vyťaženie údajov je potrebný čas a objem údajov na častú ťažbu. Algoritmus častej ťažby je efektívny algoritmus na vyťaženie skrytých vzorov množín položiek v krátkom čase a s menšou spotrebou pamäte.

Častá ťažba vzorov (FPM)

Algoritmus ťažby častých vzorov je jednou z najdôležitejších techník ťažby údajov na objavenie vzťahov medzi rôznymi položkami v množine údajov. Tieto vzťahy sú znázornené vo forme asociačných pravidiel. Pomáha zistiť nezrovnalosti v údajoch.

Program FPM má mnoho aplikácií v oblasti analýzy údajov, softvérových chýb, krížového marketingu, analýzy predajných kampaní, analýzy trhových košov atď.

Časté množiny položiek objavené cez Apriori majú veľa aplikácií v úlohách dolovania dát. Úlohy ako hľadanie zaujímavých vzorov v databáze, zisťovanie postupnosti a ťažba asociačných pravidiel sú najdôležitejšie z nich.

Pravidlá asociácie sa vzťahujú na údaje o transakciách v supermarketoch, to znamená na preskúmanie správania zákazníkov z hľadiska zakúpených produktov. Pravidlá asociácie popisujú, ako často sa položky kupujú spoločne.

Asociačné pravidlá

Ťažba pravidiel združenia je definovaná ako:

„Nech I = {…} je množina binárnych atribútov„ n “, ktoré sa nazývajú položky. Nech D = {….} Je sada transakcie nazývanej databáza. Každá transakcia v D má jedinečné ID transakcie a obsahuje podmnožinu položiek v I. Pravidlo je definované ako dôsledok formy X-> Y, kde X, Y? Ja a X? Y = ?. Množina položiek X a Y sa nazýva predchádzajúca a následná z pravidla. “

Učenie pravidiel asociácie sa používa na nájdenie vzťahov medzi atribútmi vo veľkých databázach. Pravidlo asociácie, A => B, bude mať formu „pre množinu transakcií určitá hodnota položky A určuje hodnoty položky B za podmienok, pri ktorých je splnená minimálna podpora a dôvera“.

Podporu a dôveru môžeme predstaviť v nasledujúcom príklade:

Bread=> butter [support=2%, confidence-60%]

Vyššie uvedené vyhlásenie je príkladom pravidla asociácie. To znamená, že existuje 2% transakcia, ktorá kúpila chlieb s maslom spoločne, a existuje 60% zákazníkov, ktorí si kúpili chlieb rovnako ako maslo.

Podpora a dôvera pre položky A a B sú vyjadrené vzorcami:

Vzorec na podporu a dôveru pre položky A a B.

Ťažba pravidla asociácie pozostáva z 2 krokov:

  1. Nájdite všetky časté položky.
  2. Generujte pravidlá asociácie z vyššie uvedených častých položiek.

Prečo ťažba častých položiek?

Častá množina položiek alebo dolovanie vzorov sa široko používa kvôli svojim širokým aplikáciám v pravidlách asociácie dolovania, koreláciám a obmedzeniam vzorov grafov, ktoré sú založené na častých vzoroch, postupných vzoroch a mnohých ďalších úlohách dolovania údajov.

Algoritmus Apriori - Časté algoritmy vzorov

Apriori algoritmus bol prvý algoritmus, ktorý bol navrhnutý pre častú ťažbu položiek. Neskôr ho vylepšili R. Agarwal a R. Srikant a stal sa známym ako Apriori. Tento algoritmus využíva dva kroky na zníženie spojenia a spojenie. Ide o iteračný prístup k objavovaniu najbežnejších položiek.

Apriori hovorí:

Pravdepodobnosť, že položka I nebude častá, je ak:

  • P (I)
  • P (I + A)
  • Ak má množina položiek menšiu podporu ako minimálna, potom všetky jej nadmnožiny tiež klesnú pod minimálnu podporu, a preto ju možno ignorovať. Táto vlastnosť sa nazýva vlastnosť antimonotón.

Kroky nasledované v aprioriho algoritme dolovania dát sú:

  1. Pripojte sa ku kroku : Tento krok vygeneruje (K + 1) množinu položiek z množín K-položiek spojením každej položky so sebou.
  2. Orezajte krok : V tomto kroku sa skenuje počet jednotlivých položiek v databáze. Ak kandidátska položka nespĺňa minimálnu podporu, považuje sa za zriedkavú, a preto je odstránená. Tento krok sa vykonáva na zmenšenie veľkosti kandidátskych položiek.

Kroky apriori

Apriori algoritmus je postupnosť krokov, ktoré je potrebné dodržať, aby sa našiel najbežnejší súbor položiek v danej databáze. Táto technika získavania údajov sleduje iteratívne kroky spojenia a orezania, kým sa nedosiahne najbežnejšia množina položiek. V probléme je uvedený minimálny prah podpory alebo je predpokladaný používateľom.

dobrý bezplatný sťahovač mp3 pre Android

# 1) V prvej iterácii algoritmu sa každá položka berie ako kandidát 1-položiek. Algoritmus bude počítať výskyty každej položky.

#dva) Nech existuje minimálna podpora, min_sup (napr. 2). Stanoví sa množina 1 - množín položiek, ktorých výskyt vyhovuje min. Iba tí kandidáti, ktorí majú viac alebo rovnú min_sup, sú pripravení na ďalšiu iteráciu a ostatní sú orezaní.

# 3) Ďalej sa objavia časté položky s 2 položkami s min_sup. Z tohto dôvodu sa v kroku spojenia vygeneruje sada 2 položiek vytvorením skupiny 2 kombináciou položiek so sebou.

# 4) Kandidáti na 2-položkovú sadu sa orezávajú pomocou prahovej hodnoty min-sup. Teraz bude mať tabuľka 2 –položky iba s min-sup.

# 5) Ďalšia iterácia bude tvoriť 3 –položky pomocou kroku spojenia a orezania. Táto iterácia bude nasledovať po antimonotónovej vlastnosti, kde podmnožiny 3-položkových množín, to znamená 2-množinové podmnožiny každej skupiny, spadajú do min_sup. Ak sú časté všetky podmnožiny 2 položiek, potom bude nadmnožina častá, inak sa orezáva.

# 6) Ďalším krokom bude výroba 4-položkovej sady spojením 3-položky so sebou a prerezávanie, ak jej podmnožina nespĺňa kritériá min_sup. Algoritmus sa zastaví, keď sa dosiahne najbežnejšia množina položiek.

Apriori kroky

[obrázok zdroj ]

Príklad Apriori:Prahová hodnota podpory = 50%, spoľahlivosť = 60%

STÔL 1

TransakciaZoznam položiek
T1I1, I2, I3
T2I2, I3, I4
T314, 15
T4I1, I2, I4
T5I1, I2, I3, I5
T6I1, 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žkaGróf
I14
I25
I34
144
I5dva

2. Orezať krok: TABUĽKA -2 ukazuje, že položka I5 nespĺňa min_sup = 3, preto je vymazaná, iba I1, I2, I3, I4 spĺňa počet min_sup.

TABUĽKA 3

PoložkaGróf
I14
I25
I34
144

3. Pripojte sa ku kroku: Sada 2 položiek. Od STÔL 1 zisti výskyt 2-polozkovej sady.

TABUĽKA 4

PoložkaGróf
I1, I24
I1, I33
I1, I4dva
I2, I34
I2, I43
I3, I4dva

Štyri. Orezať krok: TABUĽKA -4 ukazuje, že množina položiek {I1, I4} a {I3, I4} nespĺňa min_sup, preto je odstránená.

TABUĽKA 5

PoložkaGróf
I1, I24
I1, I33
I2, I34
I2, I43

5. Pripojte sa a prerezajte krok: Sada 3 položiek. Z STÔL 1 zistiť výskyty 3-položiek. Od TABUĽKA 5 , vyhľadajte podmnožiny 2 položiek, ktoré podporujú min_sup.

Vidíme pre podmnožiny položiek {I1, I2, I3}, {I1, I2}, {I1, I3}, {I2, I3} sa vyskytujú v TABUĽKA 5 teda {I1, I2, I3} je častý.

Vidíme pre podmnožiny položiek {I1, I2, I4} podmnožiny, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} nie sú časté, pretože sa nevyskytujú v TABUĽKA 5 teda {I1, I2, I4} nie je častý, preto je vymazaný.

TABUĽKA 6

Položka
I1, I2, I3
I1, I2, I4
I1, I3, I4
I2, I3, I4

Časté sú iba {I1, I2, I3} .

6. Vytvorte pravidlá asociácie: Z častej množiny položiek objavenej vyššie môže byť asociácia:

{I1, I2} => {I3}

Dôvera = podpora {I1, I2, I3} / podpora {I1, I2} = (3/4) * 100 = 75%

{I1, I3} => {I2}

Dôvera = podpora {I1, I2, I3} / podpora {I1, I3} = (3/3) * 100 = 100%

{I2, I3} => {I1}

Dôvera = podpora {I1, I2, I3} / podpora {I2, I3} = (3/4) * 100 = 75%

{I1} => {I2, I3}

Dôvera = podpora {I1, I2, I3} / podpora {I1} = (3/4) * 100 = 75%

{I2} => {I1, I3}

Dôvera = podpora {I1, I2, I3} / podpora {I2 = (3/5) * 100 = 60%

aký je najlepší kompilátor c ++

{I3} => {I1, I2}

Dôvera = podpora {I1, I2, I3} / podpora {I3} = (3/4) * 100 = 75%

To ukazuje, že všetky vyššie uvedené pravidlá asociácie sú silné, ak je minimálna hranica spoľahlivosti 60%.

Aprioriho algoritmus: Pseudokód

C: Sada kandidátskych predmetov veľkosti k

L: Častá množina položiek veľkosti k

Psudokód

[obrázok zdroj ]

Výhody

  1. Ľahko pochopiteľný algoritmus
  2. Kroky Join a Prune sa dajú ľahko implementovať na veľkých množinách položiek vo veľkých databázach

Nevýhody

  1. Vyžaduje vysoký výpočet, ak sú sady položiek veľmi veľké a minimálna podpora je udržiavaná na veľmi nízkej úrovni.
  2. Je potrebné naskenovať celú databázu.

Metódy na zvýšenie apriori účinnosti

Na zlepšenie efektívnosti algoritmu je k dispozícii veľa metód.

  1. Technika založená na hašovaní: Táto metóda používa na generovanie množiny k-položiek a jej zodpovedajúceho počtu štruktúru založenú na hashe, ktorá sa nazýva hašovacia tabuľka. Na generovanie tabuľky používa hashovaciu funkciu.
  2. Zníženie transakcie: Táto metóda znižuje počet skenovaní transakcií v iteráciách. Transakcie, ktoré neobsahujú časté položky, sú označené alebo odstránené.
  3. Rozdelenie na oblasti: Táto metóda vyžaduje iba dve skenovania databázy na vyťaženie častých množín položiek. Hovorí sa v ňom, že aby bola akákoľvek množina položiek v databáze potenciálne častá, mala by byť častá aspoň v jednom z oddielov databázy.
  4. Vzorkovanie: Táto metóda vyberie náhodnú vzorku S z databázy D a potom vyhľadá častú množinu položiek v S. Je možné, že stratíte globálnu častú množinu položiek. To sa dá znížiť znížením min_sup.
  5. Počítanie dynamických položiek: Táto technika môže počas skenovania databázy pridávať nové kandidátske sady položiek do ľubovoľného označeného začiatočného bodu databázy.

Aplikácie aprioriho algoritmu

Niektoré polia, kde sa používa Apriori:

  1. V oblasti vzdelávania: Extrakcia asociačných pravidiel pri dolovaní dát prijatých študentov pomocou charakteristík a špecialít.
  2. V lekárskej oblasti: Napríklad Analýza databázy pacientov.
  3. V lesníctve: Analýza pravdepodobnosti a intenzity lesného požiaru s údajmi o lesnom požiari.
  4. Apriori používajú mnohé spoločnosti ako Amazon v USA Odporúčací systém a spoločnosť Google pre funkciu automatického dokončovania.

Záver

Apriori algoritmus je efektívny algoritmus, ktorý prehľadáva databázu iba raz.

Znižuje veľkosť súborov položiek v databáze a poskytuje dobrý výkon. Dolovanie dát teda pomáha spotrebiteľom a priemyselným odvetviam lepšie v rozhodovacom procese.

V našom pripravovanom výučbe sa dozviete viac o algoritme rastu častých vzorov !!

Výukový program PREV | NEXT Tutorial

Odporúčané čítanie

^