Apriori algoritmus - Apriori algorithm - Wikipedia

A priori^[1] je algoritmus pro častou těžbu sady položek a učení pravidel asociace přes relační databáze. Postupuje identifikací častých jednotlivých položek v databázi a jejich rozšířením na větší a větší sady položek, pokud se tyto sady položek v databázi vyskytují dostatečně často. K určení lze použít časté sady položek určené společností Apriori pravidla přidružení které zdůrazňují obecné trendy v EU databáze: toto má aplikace v doménách jako analýza tržního koše.

Přehled

Algoritmus Apriori navrhli Agrawal a Srikant v roce 1994. Apriori je navržen tak, aby fungoval dál databáze obsahující transakce (například sbírky položek zakoupených zákazníky nebo podrobnosti o návštěvnosti webových stránek nebo IP adresy^[2]). Jiné algoritmy jsou navrženy pro hledání pravidel přidružení v datech, která nemají žádné transakceWinepi a Minepi) nebo bez časových značek (sekvenování DNA). Každá transakce je považována za sadu položek (an sada položek). Vzhledem k prahové hodnotě ${ displaystyle C}$ , algoritmus Apriori identifikuje sady položek, které jsou alespoň podmnožinami ${ displaystyle C}$ transakce v databázi.

Apriori používá přístup "zdola nahoru", kdy se časté podmnožiny rozšiřují o jednu položku najednou (krok známý jako generace kandidátů) a skupiny kandidátů jsou testovány na základě údajů. Algoritmus se ukončí, když nebudou nalezeny žádné další úspěšné přípony.

Apriori používá vyhledávání na šířku a a Hash strom struktura pro efektivní počítání sad kandidátských položek. Generuje sady kandidátských položek délky ${ displaystyle k}$ ze sady položek délky ${ displaystyle k-1}$ . Pak to ořezává kandidáty, kteří mají řídký dílčí vzor. Podle lemmatu uzavírání dolů obsahuje sada kandidátů vše časté ${ displaystyle k}$ -délkové sady položek. Poté prohledá databázi transakcí a určí mezi kandidáty časté sady položek.

Níže je uveden pseudokód algoritmu pro databázi transakcí ${ displaystyle T}$ a prahová hodnota podpory ve výši ${ displaystyle epsilon}$ . Používá se obvyklá množinová teoretická notace, ačkoli si uvědomte, že ${ displaystyle T}$ je multiset. ${ displaystyle C_ {k}}$ je kandidát nastavený na úroveň ${ displaystyle k}$ . V každém kroku se předpokládá, že algoritmus vygeneruje sady kandidátů ze sad velkých položek předchozí úrovně s ohledem na lemma uzavření dolů. ${ displaystyle count [c]}$ přistupuje k poli datové struktury, která představuje sadu kandidátů ${ displaystyle c}$ , který se zpočátku předpokládá jako nula. Mnoho podrobností je níže vynecháno, obvykle nejdůležitější částí implementace je datová struktura používaná pro ukládání kandidátských sad a počítání jejich frekvencí.

${ displaystyle { begin {aligned} & mathrm {Apriori} (T, epsilon) & qquad L_ {1} gets { mathrm {large ~ 1-itemsets} } & qquad k dostane 2 & qquad mathrm { textbf {while}} ~ L_ {k-1} neq emptyset & qquad qquad C_ {k} gets {c = a cup {b } mid a in L_ {k-1} land b not in a, {s subseteq c mid | s | = k-1 } subseteq L_ {k-1} } & qquad qquad mathrm {{ textbf {for}} ~ transakce} ~ t v T & qquad qquad qquad D_ {t} dostane {c v C_ {k } mid c subseteq t } & qquad qquad qquad mathrm {{ textbf {for}} ~ kandidáti} ~ c v D_ {t} & qquad qquad qquad qquad { mathit {count}} [c] dostane { mathit {count}} [c] +1 & qquad qquad L_ {k} dostane {c v C_ {k} mid { mathit {count}} [c] geq epsilon } & qquad qquad k dostane k + 1 & qquad mathrm { textbf {návrat}} ~ bigcup _ {k} L_ { k} end {zarovnáno}}}$

Příklady

Příklad 1

Zvažte následující databázi, kde každý řádek je transakce a každá buňka je samostatnou položkou transakce:

alfa	beta	epsilon
alfa	beta	theta
alfa	beta	epsilon
alfa	beta	theta

Pravidla přidružení, která lze určit z této databáze, jsou následující:

100% sad s alfa obsahuje také beta
50% sad s alfa, beta má také epsilon
50% sad s alfa, beta má také theta

můžeme to také ilustrovat na různých příkladech.

Příklad 2

Předpokládejme, že velký supermarket sleduje údaje o prodeji skladovací jednotka (SKU) pro každou položku: každá položka, například „máslo“ nebo „chléb“, je označena číselným SKU. Supermarket má databázi transakcí, kde každá transakce je sada SKU, které byly zakoupeny společně.

Nechte databázi transakcí sestávat z následujících sad položek:

Položky
{1,2,3,4}
{1,2,4}
{1,2}
{2,3,4}
{2,3}
{3,4}
{2,4}

K určení častých sad položek této databáze použijeme Apriori. Za tímto účelem řekneme, že sada položek je častá, pokud se objeví v nejméně 3 transakcích databáze: hodnota 3 je práh podpory.

Prvním krokem Apriori je spočítat počet výskytů, nazývaných podpora, každé členské položky zvlášť. Při prvním skenování databáze získáme následující výsledek

Položka	Podpěra, podpora
{1}	3
{2}	6
{3}	4
{4}	5

Všechny sady položek velikosti 1 mají podporu alespoň 3, takže jsou časté.

Dalším krokem je vygenerování seznamu všech párů častých položek.

Například, pokud jde o dvojici {1,2}: první tabulka z příkladu 2 ukazuje položky 1 a 2, které se objevují společně ve třech sadách položek; proto říkáme, že položka {1,2} má podporu tří.

Položka	Podpěra, podpora
{1,2}	3
{1,3}	1
{1,4}	2
{2,3}	3
{2,4}	4
{3,4}	3

Dvojice {1,2}, {2,3}, {2,4} a {3,4} všechny splňují nebo překračují minimální podporu 3, takže jsou časté. Páry {1,3} a {1,4} nejsou. Nyní, protože {1,3} a {1,4} nejsou časté, nemůže být častá žádná větší sada, která obsahuje {1,3} nebo {1,4}. Tímto způsobem můžeme prořezávat sady: nyní vyhledáme v databázi časté trojnásobky, ale již můžeme vyloučit všechny trojice, které obsahují jeden z těchto dvou párů:

Položka	Podpěra, podpora
{2,3,4}	2

v příkladu nejsou časté trojčata. {2,3,4} je pod minimální prahovou hodnotou a ostatní trojčata byla vyloučena, protože se jednalo o super sady párů, které již byly pod prahovou hodnotou.

Zjistili jsme tedy časté sady položek v databázi a ukázali, jak se některé položky nepočítají, protože o jedné z jejich podmnožin bylo již známo, že jsou pod prahovou hodnotou.

Omezení

Apriori, i když je historicky významný, trpí řadou neefektivnosti nebo kompromisů, které způsobily další algoritmy. Generování kandidátů generuje velké množství podmnožin (Algoritmus se pokusí načíst množinu uchazečů s co největším počtem podmnožin před každým skenováním databáze). Průzkum podmnožiny zdola nahoru (v zásadě průchod šířky podmřížky podmnožiny) najde jakoukoli maximální podmnožinu S až po všem ${ displaystyle 2 ^ {| S |} -1}$ jejích správných podmnožin.

Algoritmus prohledává databázi příliš mnohokrát, což snižuje celkový výkon. Z tohoto důvodu algoritmus předpokládá, že databáze je permanentní v paměti.

Časová i prostorová složitost tohoto algoritmu je také velmi vysoká: ${ displaystyle O (2 ^ {| D |})}$ , tedy exponenciální, kde ${ displaystyle | D |}$ je vodorovná šířka (celkový počet položek) přítomný v databázi.

Pozdější algoritmy jako např Max-Miner^[3] zkuste identifikovat maximální časté sady položek bez výčtu jejich podmnožin a proveďte „skoky“ ve vyhledávacím prostoru spíše než čistě zdola nahoru.

Reference

^ Rakesh Agrawal a Ramakrishnan Srikant Rychlé algoritmy pro pravidla asociace těžby. Sborník z 20. mezinárodní konference o velmi velkých databázích, VLDB, strany 487-499, Santiago, Chile, září 1994.
^ Datová věda za shodou IP adres Publikováno deductive.com, 6. září 2018, vyvoláno 7. září 2018
^ Bayardo Jr., Roberto J. (1998). „Efektivní těžba dlouhých vzorů z databází“ (PDF). Záznam ACM SIGMOD. 27 (2).

externí odkazy

ARtool, GPL Java asociační pravidla pro těžbu aplikací s GUI, nabízející implementace více algoritmů pro objevování častých vzorů a extrakci asociačních pravidel (včetně Apriori)
SPMF nabízí Java open-source implementace Apriori a několik variant, jako jsou AprioriClose, UApriori, AprioriInverse, AprioriRare, MSApriori, AprioriTID a další efektivnější algoritmy jako FPGrowth a LCM.
Christian Borgelt poskytuje implementace C pro Apriori a mnoho dalších častá těžba vzorků algoritmy (Eclat, FPGrowth atd.). Kód je distribuován jako svobodný software pod Licence MIT.
The R balík arules obsahuje Apriori a Eclat a infrastrukturu pro reprezentaci, manipulaci a analýzu transakčních dat a vzorů.
Efektivní - Apriori je balíček Python s implementací algoritmu, jak je uvedeno v původním článku.

[apriori-1] Rakesh Agrawal a Ramakrishnan Srikant Rychlé algoritmy pro pravidla asociace těžby. Sborník z 20. mezinárodní konference o velmi velkých databázích, VLDB, strany 487-499, Santiago, Chile, září 1994.

[2] Datová věda za shodou IP adres Publikováno deductive.com, 6. září 2018, vyvoláno 7. září 2018

[3] Bayardo Jr., Roberto J. (1998). „Efektivní těžba dlouhých vzorů z databází“ (PDF). Záznam ACM SIGMOD. 27 (2).

[1]

[2]

[3]