Menu

Apriori Algorithm in Data Mining: Implementation With examples

  • Hlavní
  • Jiný
  • Apriori Algorithm in Data Mining: Implementation With examples

apriori algorithm data mining

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Podrobný výukový program o apriori algoritmu pro zjištění častých položek v dolování dat. Tento výukový program vysvětluje kroky apriori a jak to funguje:

V tomhle Série výukových programů pro dolování dat , podívali jsme se na Algoritmus rozhodovacího stromu v našem předchozím tutoriálu.

Existuje několik metod pro dolování dat, jako je asociace, korelace, klasifikace a shlukování.

software pro rozpoznávání řeči je nejoblíbenější pro

Tento kurz se primárně zaměřuje na těžbu pomocí pravidel přidružení. Podle pravidel přidružení identifikujeme sadu položek nebo atributů, které se vyskytují společně v tabulce.

Apriori algoritmus

Co se naučíte:

Co je to položka?

Sada položek dohromady se nazývá sada položek. Pokud některá položka obsahuje k-položky, nazývá se to k-položky. Sada položek se skládá ze dvou nebo více položek. Sada položek, která se často vyskytuje, se nazývá sada častých položek. Proto je častá těžba položek technikou dolování dat k identifikaci položek, které se často vyskytují společně.

Například , Chléb s máslem, Laptop a antivirový software atd.

Co je to častá položka?

Sada položek se nazývá častá, pokud splňuje minimální prahovou hodnotu pro podporu a spolehlivost. Podpora zobrazuje transakce s položkami zakoupenými společně v jedné transakci. Důvěra ukazuje transakce, kde jsou položky nakupovány jeden po druhém.

U metody těžby častých položek uvažujeme pouze ty transakce, které splňují minimální prahovou podporu a požadavky na spolehlivost. Statistiky z těchto těžebních algoritmů nabízejí mnoho výhod, snížení nákladů a lepší konkurenční výhodu.

Existuje čas kompromisu při těžbě dat a objem dat pro častou těžbu. Algoritmus častého dolování je efektivní algoritmus, který umožňuje vytěžit skryté vzory skupin položek v krátké době a s menší spotřebou paměti.

Těžba častých vzorků (FPM)

Algoritmus dolování častých vzorků je jednou z nejdůležitějších technik dolování dat k objevování vztahů mezi různými položkami v datové sadě. Tyto vztahy jsou zastoupeny ve formě pravidel přidružení. Pomáhá najít nesrovnalosti v datech.

FPM má mnoho aplikací v oblasti analýzy dat, softwarových chyb, cross-marketingu, analýzy prodejních kampaní, analýzy košů na trhu atd.

Časté sady položek objevené prostřednictvím Apriori mají mnoho aplikací v úlohách dolování dat. Mezi nejdůležitější patří úkoly, jako je hledání zajímavých vzorů v databázi, zjištění posloupnosti a těžba pravidel přidružení.

Pravidla přidružení se vztahují na údaje o transakcích v supermarketech, to znamená zkoumat chování zákazníků, pokud jde o zakoupené produkty. Pravidla přidružení popisují, jak často jsou položky nakupovány společně.

Pravidla přidružení

Těžba pravidel asociace je definována jako:

„Nechť I = {…} je množina‚ n ‘binárních atributů zvaných položky. Nechť D = {….} Je sada transakce zvané databáze. Každá transakce v D má jedinečné ID transakce a obsahuje podmnožinu položek v I. Pravidlo je definováno jako implikace tvaru X-> Y, kde X, Y? Já a X? Y = ?. Množině položek X a Y se říká předchůdce a následek pravidla. “

Učení pravidel přidružení se používá k hledání vztahů mezi atributy ve velkých databázích. Pravidlo přidružení, A => B, bude mít formu „pro sadu transakcí určitá hodnota položky A určuje hodnoty položky B za podmínky, že je splněna minimální podpora a důvěra“.

Podporu a důvěru lze představit v následujícím příkladu:

Bread=> butter (support=2%, confidence-60%)

Výše uvedené prohlášení je příkladem pravidla přidružení. To znamená, že existuje 2% transakce, která koupila chléb s máslem společně, a existuje 60% zákazníků, kteří si koupili chléb i máslo.

Podpora a důvěryhodnost pro položky A a B jsou reprezentovány vzorci:

Vzorec podpory a důvěryhodnosti pro položky A a B.

Dolování asociačních pravidel se skládá ze 2 kroků:

  1. Najděte všechny časté položky.
  2. Z výše uvedených častých položek generujte pravidla přidružení.

Proč těžit časté položky?

Častá sada položek nebo dolování vzorů se široce používá kvůli jeho širokým aplikacím v pravidlech asociace těžby, korelacím a omezením vzorů grafů, které je založeno na častých vzorcích, sekvenčních vzorech a mnoha dalších úlohách dolování dat.

Algoritmus Apriori - Časté algoritmy vzorů

Apriori algoritmus byl první algoritmus, který byl navržen pro častou těžbu položek. To bylo později vylepšeno R. Agarwalem a R. Srikantem a začalo být známé jako Apriori. Tento algoritmus využívá ke snížení prostoru pro vyhledávání dva kroky „join“ a „prořezat“. Jedná se o iterativní přístup k objevování nejčastějších položek.

Apriori říká:

Pravděpodobnost, že položka I není častá, je, pokud:

  • P (I)
  • P (I + A)
  • Pokud má sada položek hodnotu menší než minimální podpora, pak všechny její nadmnožiny také klesnou pod minimální podporu, a proto ji lze ignorovat. Tato vlastnost se nazývá vlastnost Antimonotone.

Kroky následované v Aprioriho algoritmu dolování dat jsou:

  1. Připojte se ke kroku : Tento krok generuje (K + 1) sadu položek ze sad K-položek spojením každé položky s sebou.
  2. Prořezejte krok : Tento krok prohledá počet jednotlivých položek v databázi. Pokud kandidátská položka nesplňuje minimální podporu, je považována za vzácnou, a proto je odstraněna. Tento krok se provádí ke zmenšení velikosti kandidátních položek.

Kroky v dubnu

Apriori algoritmus je sled kroků, které je třeba dodržet při hledání nejčastější položky v dané databázi. Tato technika dolování dat postupuje iterativně po spojení a prořezávání, dokud není dosaženo nejčastější položky. Minimální prahová hodnota podpory je uvedena v problému nebo ji předpokládá uživatel.

# 1) V první iteraci algoritmu se každá položka považuje za kandidáta na 1 položku. Algoritmus spočítá výskyty každé položky.

#dva) Nechť existuje nějaká minimální podpora, min_sup (např. 2). Stanoví se sada 1 - položek, jejichž výskyt vyhovuje min. Pouze ti kandidáti, kteří počítají více nebo rovnu min_sup, jsou připraveni na další iteraci a ostatní jsou ořezáni.

# 3) Dále jsou objeveny časté položky se 2 položkami s min_sup. Za tímto účelem v kroku spojení je sada 2 položek vygenerována vytvořením skupiny 2 kombinací položek sama se sebou.

# 4) Kandidáti na 2 položky se prořezávají pomocí prahové hodnoty min-sup. Nyní bude mít tabulka 2 –položky pouze s min-sup.

# 5) Další iterace vytvoří 3 –položky pomocí kroku join a prořezat. Tato iterace bude následovat po antimonotonové vlastnosti, kde podmnožiny 3-položkových sad, tj. 2 –podskupinové sady každé skupiny spadají do min_sup. Pokud jsou všechny podmnožiny 2 položek velmi časté, bude nadmnožina častá, jinak se prořezává.

# 6) Dalším krokem bude vytvoření sady 4 položek spojením sady 3 položek se sebou a prořezáním, pokud její podmnožina nesplňuje kritéria min_sup. Algoritmus se zastaví, když se dosáhne nejčastější sady položek.

Apriori kroky

(obraz zdroj )

Příklad Apriori:Prahová hodnota podpory = 50%, spolehlivost = 60%

STŮL 1

TransakceSeznam položek
T1I1, I2, I3
T2I2, I3, I4
T3I4, I5
T4I1, I2, I4
T5I1, I2, I3, I5
T6I1, I2, I3, I4

Řešení:

Prahová hodnota podpory = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Počet každé položky

TABULKA-2

PoložkaPočet
I14
I25
I34
I44
I5dva

dva. Prořezat krok: TABULKA -2 ukazuje, že položka I5 nesplňuje min_sup = 3, proto je odstraněna, pouze I1, I2, I3, I4 splňuje počet min_sup.

TABULKA-3

PoložkaPočet
I14
I25
I34
I44

3. Připojte se ke kroku: Sada 2 položek. Z STŮL 1 zjistit výskyt 2-položky.

TABULKA-4

PoložkaPočet
I1, I24
I1, I33
I1, I4dva
I2, I34
I2, I43
I3, I4dva

Čtyři. Prořezat krok: TABULKA -4 ukazuje, že sada položek {I1, I4} a {I3, I4} nesplňuje min_sup, proto je smazána.

TABULKA-5

PoložkaPočet
I1, I24
I1, I33
I2, I34
I2, I43

5. Připojte se a proveďte krok: Sada 3 položek. Z STŮL 1 zjistit výskyt 3-položky. Z TABULKA-5 , zjistěte podmnožiny 2 položek, které podporují min_sup.

Vidíme pro podmnožiny položek {I1, I2, I3}, {I1, I2}, {I1, I3}, {I2, I3} se vyskytují v TABULKA-5 tedy {I1, I2, I3} je časté.

otázky týkající se kódování java při psaní kódu

Vidíme pro podmnožiny položek {I1, I2, I4}, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} není časté, protože se nevyskytuje TABULKA-5 tedy {I1, I2, I4} není časté, proto je smazáno.

TABULKA-6

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

Časté jsou pouze {I1, I2, I3} .

6. Vytvořit pravidla přidružení: Z výše uvedené časté položky objevené asociace může být:

{I1, I2} => {I3}

Důvěra = podpora {I1, I2, I3} / podpora {I1, I2} = (3/4) * 100 = 75%

{I1, I3} => {I2}

Důvěra = podpora {I1, I2, I3} / podpora {I1, I3} = (3/3) * 100 = 100%

{I2, I3} => {I1}

Důvěra = podpora {I1, I2, I3} / podpora {I2, I3} = (3/4) * 100 = 75%

{I1} => {I2, I3}

Důvěra = podpora {I1, I2, I3} / podpora {I1} = (3/4) * 100 = 75%

{I2} => {I1, I3}

Důvěra = podpora {I1, I2, I3} / podpora {I2 = (3/5) * 100 = 60%

{I3} => {I1, I2}

Důvěra = podpora {I1, I2, I3} / podpora {I3} = (3/4) * 100 = 75%

To ukazuje, že všechna výše uvedená pravidla přidružení jsou silná, pokud je minimální prahová hodnota spolehlivosti 60%.

Algoritmus Apriori: Pseudo kód

C: Sada položek pro uchazeče o velikosti k

L: Častá sada položek o velikosti k

Psudokód

(obraz zdroj )

Výhody

  1. Snadno pochopitelný algoritmus
  2. Kroky join a Prune lze snadno implementovat na velké sady položek ve velkých databázích

Nevýhody

  1. Vyžaduje vysoký výpočet, pokud jsou sady položek velmi velké a minimální podpora je udržována na velmi nízké úrovni.
  2. Je třeba naskenovat celou databázi.

Metody ke zlepšení účinnosti apriori

Existuje mnoho metod pro zlepšení efektivity algoritmu.

  1. Technika založená na hašování: Tato metoda používá strukturu založenou na hašování, která se nazývá hašovací tabulka pro generování sad k-položek a odpovídající počet. Pro generování tabulky používá hashovací funkci.
  2. Snížení transakce: Tato metoda snižuje počet skenování transakcí v iteracích. Transakce, které neobsahují časté položky, jsou označeny nebo odstraněny.
  3. Rozdělení disku: Tato metoda vyžaduje pouze dvě skenování databáze k těžbě častých sad položek. Říká, že pro každou sadu položek, která má být v databázi potenciálně častá, by měla být častá alespoň v jednom z oddílů databáze.
  4. Vzorkování: Tato metoda vybere náhodný vzorek S z databáze D a poté vyhledá častou sadu položek v S. Je možné, že ztratíte globální častou sadu položek. To lze snížit snížením min_sup.
  5. Počítání dynamických položek: Tato technika může během skenování databáze přidávat nové kandidátské sady položek do libovolného označeného počátečního bodu databáze.

Aplikace aprioriho algoritmu

Některá pole, kde se používá Apriori:

  1. V oblasti vzdělávání: Extrakce asociačních pravidel při dolování dat přijatých studentů prostřednictvím charakteristik a specialit.
  2. V lékařské oblasti: Například Analýza databáze pacienta.
  3. V lesnictví: Analýza pravděpodobnosti a intenzity lesního požáru s údaji o lesním požáru.
  4. Apriori používá mnoho společností, jako je Amazon v Doporučující systém a Google pro funkci automatického dokončování.

Závěr

Apriori algoritmus je efektivní algoritmus, který skenuje databázi pouze jednou.

Snižuje podstatně velikost položek v databázi a poskytuje dobrý výkon. Těžba dat tak pomáhá spotřebitelům a průmyslovým odvětvím lépe v rozhodovacím procesu.

Podívejte se na náš nadcházející výukový program a dozvíte se více o Algoritmu růstu častých vzorů !!

Výukový program PREV | DALŠÍ výuka

Doporučené čtení

^