Učení pravidla asociace - Association rule learning - Wikipedia

Učení pravidla asociace je strojové učení založené na pravidlech metoda pro objevování zajímavých vztahů mezi proměnnými ve velkých databázích. Je určen k identifikaci silných pravidel objevených v databázích pomocí určitých měr zajímavosti.^[1]

Na základě konceptu silných pravidel Rakesh Agrawal, Tomasz Imieliński a Arun Swami^[2] zavedla asociační pravidla pro zjišťování zákonitostí mezi produkty ve velkých transakčních datech zaznamenaných společností místě prodeje (POS) systémy v supermarketech. Například pravidlo ${ displaystyle { mathrm {cibule, brambory} } Rightarrow { mathrm {hamburger} }}$ zjištěné v prodejních datech supermarketu by naznačovaly, že pokud si zákazník koupí cibuli a brambory společně, pravděpodobně si také koupí hamburgerové maso. Tyto informace lze použít jako základ pro rozhodování o marketingových aktivitách, jako jsou např. Propagační akce ceny nebo umístění produktu.

Kromě výše uvedeného příkladu z analýza tržního koše asociační pravidla se dnes používají v mnoha aplikačních oblastech včetně Těžba využití webu, detekce narušení, nepřetržitá výroba, a bioinformatika. V kontrastu s sekvenční těžba, učení asociačního pravidla obvykle nezohledňuje pořadí položek v rámci transakce ani napříč transakcemi.

Definice

Podle původní definice Agrawal, Imieliński, Swami^[2] problém dolování asociačních pravidel je definován jako:

Nechat ${ displaystyle I = {i_ {1}, i_ {2}, ldots, i_ {n} }}$ být soubor ${ displaystyle n}$ volané binární atributy položky.

Nechat ${ displaystyle D = {t_ {1}, t_ {2}, ldots, t_ {m} }}$ být soubor transakcí nazývaných databáze.

Každý transakce v ${ displaystyle D}$ má jedinečné ID transakce a obsahuje podmnožinu položek v ${ displaystyle I}$.

A pravidlo je definován jako implikace formuláře:

${ displaystyle X Rightarrow Y}$, kde ${ displaystyle X, Y subseteq I}$.

In Agrawal, Imieliński, Swami^[2] A pravidlo je definován pouze mezi sadou a jednou položkou, ${ displaystyle X Rightarrow i_ {j}}$ pro ${ displaystyle i_ {j} v I}$.

Každé pravidlo se skládá ze dvou různých sad položek, známých také jako sady položek, ${ displaystyle X}$ a ${ displaystyle Y}$, kde ${ displaystyle X}$ je nazýván předchůdce nebo na levé straně (LHS) a ${ displaystyle Y}$ následný nebo pravá strana (RHS).

Pro ilustraci konceptů používáme malý příklad z domény supermarketu. Sada položek je ${ displaystyle I = { mathrm {mléko, chléb, máslo, pivo, plenky} }}$ a v tabulce je zobrazena malá databáze obsahující položky, kde v každé položce hodnota 1 znamená přítomnost položky v příslušné transakci a hodnota 0 představuje nepřítomnost položky v dané transakci.

Příkladem pravidla pro supermarket může být ${ displaystyle { mathrm {máslo, chléb} } Rightarrow { mathrm {mléko} }}$ to znamená, že pokud se kupuje máslo a chléb, kupují si zákazníci také mléko.

Poznámka: tento příklad je extrémně malý. V praktických aplikacích potřebuje pravidlo podporu několika stovek transakcí, než ho lze považovat za statisticky významné,^[3] a datové sady často obsahují tisíce nebo miliony transakcí.

Užitečné koncepty

Aby bylo možné vybrat zajímavá pravidla ze sady všech možných pravidel, používají se omezení týkající se různých měr důležitosti a zájmu. Nejznámějšími omezeními jsou minimální prahové hodnoty pro podporu a důvěru.

Nechat ${ displaystyle X, Y}$ být předměty, ${ displaystyle X Rightarrow Y}$ pravidlo přidružení a ${ displaystyle T}$ soubor transakcí dané databáze.

Podpěra, podpora

Podpora je údaj o tom, jak často se v datové sadě objevuje sada položek.

Podpora ${ displaystyle X}$ s ohledem na ${ displaystyle T}$ je definován jako podíl transakcí ${ displaystyle t}$ v datové sadě, která obsahuje sadu položek ${ displaystyle X}$.

${ displaystyle mathrm {supp} (X) = { frac {| {t v T; X subseteq t } |} {| T |}}}$

V ukázkové datové sadě sada položek ${ displaystyle X = { mathrm {pivo, plenky} }}$ má podporu ${ displaystyle 1/5 = 0,2}$ protože se vyskytuje u 20% všech transakcí (1 z 5 transakcí). Argument ${ displaystyle mathrm {supp} ()}$ je soubor předpokladů, a proto se s růstem stává restriktivnější (místo inkluzivnějšího).^[4]

Dále sada položek ${ displaystyle Y = { mathrm {mléko, chléb, máslo} }}$ má podporu ${ displaystyle 1/5 = 0,2}$ jak se také objevuje u 20% všech transakcí.

Důvěra

Důvěra je známkou toho, jak často bylo pravidlo shledáno pravdivým.

The důvěra hodnota pravidla, ${ displaystyle X Rightarrow Y}$ , s ohledem na soubor transakcí ${ displaystyle T}$, je podíl transakcí, které obsahuje ${ displaystyle X}$ který také obsahuje ${ displaystyle Y}$.

Důvěra je definována jako:

${ displaystyle mathrm {conf} (X Rightarrow Y) = mathrm {supp} (X cup Y) / mathrm {supp} (X)}$

Například pravidlo ${ displaystyle { mathrm {máslo, chléb} } Rightarrow { mathrm {mléko} }}$ má důvěru ${ displaystyle 0,2 / 0,2 = 1,0}$ v databázi, což znamená, že u 100% transakcí obsahujících máslo a chléb je pravidlo správné (100% případů, kdy si zákazník kupuje máslo a chléb, kupuje také mléko).

Všimněte si, že ${ displaystyle mathrm {supp} (X cup Y)}$ znamená podporu spojení položek v X a Y. To je poněkud matoucí, protože normálně uvažujeme z hlediska pravděpodobností Události a ne sady položek. Můžeme přepsat ${ displaystyle mathrm {supp} (X cup Y)}$ jako pravděpodobnost ${ displaystyle P (E_ {X} čepice E_ {Y})}$, kde ${ displaystyle E_ {X}}$ a ${ displaystyle E_ {Y}}$ jsou události, které transakce obsahuje sadu položek ${ displaystyle X}$ a ${ displaystyle Y}$, resp.^[5]

Důvěru lze tedy interpretovat jako odhad podmíněná pravděpodobnost ${ displaystyle P (E_ {Y} | E_ {X})}$, pravděpodobnost nalezení RHS pravidla v transakcích za podmínky, že tyto transakce obsahují také LHS.^[4][6]

Výtah

The výtah pravidla je definováno jako:

${ displaystyle mathrm {výtah} (X Rightarrow Y) = { frac { mathrm {supp} (X cup Y)} { mathrm {supp} (X) times mathrm {supp} (Y) }}}$

nebo poměr pozorované podpory k očekávané podpoře, pokud by X a Y byly nezávislý.

Například pravidlo ${ displaystyle { mathrm {mléko, chléb} } Rightarrow { mathrm {máslo} }}$ má výtah ${ displaystyle { frac {0,2} {0,4 krát 0,4}} = 1,25}$.

Pokud by pravidlo mělo výtah 1, znamenalo by to, že pravděpodobnost výskytu předchůdce a pravděpodobnost následku jsou navzájem nezávislé. Pokud jsou dvě události na sobě nezávislé, nelze vyvodit žádné pravidlo zahrnující tyto dvě události.

Pokud je výtah> 1, umožňuje nám to vědět, do jaké míry jsou tyto dva výskyty na sobě závislé, a tato pravidla jsou potenciálně užitečná pro předpovídání následků v budoucích souborech dat.

Pokud je výtah <1, znamená to, že položky se navzájem nahrazují. To znamená, že přítomnost jedné položky má negativní vliv na přítomnost jiné položky a naopak.

Hodnota výtahu spočívá v tom, že zohledňuje jak podporu pravidla, tak celkovou sadu dat.^[4]

Přesvědčení

The přesvědčení pravidla je definována jako ${ displaystyle mathrm {conv} (X Rightarrow Y) = { frac {1- mathrm {supp} (Y)} {1- mathrm {conf} (X Rightarrow Y)}}}$.^[7]

Například pravidlo ${ displaystyle { mathrm {mléko, chléb} } Rightarrow { mathrm {máslo} }}$ má přesvědčení ${ displaystyle { frac {1-0,4} {1-0,5}} = 1,2}$, a lze jej interpretovat jako poměr očekávané frekvence, ke které X dojde bez Y (tj. frekvence, kterou pravidlo vytváří nesprávnou predikci), pokud X a Y byly nezávislé, děleno pozorovanou frekvencí nesprávných předpovědí. V tomto příkladu hodnota přesvědčení 1,2 ukazuje, že pravidlo ${ displaystyle { mathrm {mléko, chléb} } Rightarrow { mathrm {máslo} }}$ by bylo nesprávné o 20% častěji (1,2krát častěji), pokud by asociace mezi X a Y byla čistě náhodná.

Alternativní měřítka zajímavosti

Kromě důvěry, další opatření zajímavost byla navržena pravidla. Některá populární opatření jsou:

• Sebedůvěra^[8]
• Kolektivní síla^[9]
• Vliv^[10]

Několik dalších opatření předkládá a srovnává Tan et al.^[11] a Hahsler.^[5] Hledání technik, které mohou modelovat to, co uživatel znal (a použití těchto modelů jako měřítka zajímavosti), je v současné době aktivním výzkumným trendem pod názvem „Subjektivní zajímavost“.

Proces

Mřížka časté sady položek, kde barva pole označuje, kolik transakcí obsahuje kombinaci položek. Pamatujte, že nižší úrovně mřížky mohou obsahovat nanejvýš minimální počet položek jejich rodičů; např. {ac} může mít maximálně ${ displaystyle min (a, c)}$ položky. Tomu se říká vlastnost uzavření dolů.^[2]

Pravidla přidružení jsou obvykle požadována k uspokojení uživatelem zadané minimální podpory a uživatelem zadané minimální důvěryhodnosti současně. Generování pravidla přidružení se obvykle dělí na dva samostatné kroky:

1. K nalezení všech se použije minimální prahová hodnota podpory časté položky v databázi.
2. Na tyto časté položky je aplikováno minimální omezení spolehlivosti, aby se vytvořila pravidla.

Zatímco druhý krok je přímočarý, první krok vyžaduje více pozornosti.

Nalezení všech častých položek v databázi je obtížné, protože zahrnuje hledání všech možných položek (kombinací položek). Sada možných položek je napájecí sada přes ${ displaystyle I}$ a má velikost ${ displaystyle 2 ^ {n} -1}$ (kromě prázdné sady, která není platnou sadou položek). I když velikost sady energie exponenciálně roste v počtu položek ${ displaystyle n}$ v ${ displaystyle I}$, efektivní vyhledávání je možné pomocí vlastnost uzavření dolů podpory^[2][12] (také zvaný anti-monotónnost^[13]) což zaručuje, že pro častou množinu položek jsou také časté všechny její podmnožiny, takže žádná neobvyklá sada položek nemůže být podmnožinou sady častých položek. Využití této vlastnosti, efektivní algoritmy (např. Apriori^[14] a Eclat^[15]) najdete všechny časté položky.

Dějiny

Koncept pravidel přidružení byl popularizován zejména díky článku Agrawal et al. Z roku 1993,^[2] která od srpna 2015 získala více než 18 000 citací podle Google Scholar, a je tak jedním z nejcitovanějších článků v oblasti Data Mining. To, co se nyní nazývá „pravidla přidružení“, je však představeno již v dokumentu z roku 1966^[16] na GUHA, obecné metodě dolování dat vyvinuté Petr Hájek et al.^[17]

Rané (kolem roku 1989) použití minimální podpory a důvěry k nalezení všech pravidel přidružení je rámec Feature Based Modeling, který našel všechna pravidla s ${ displaystyle mathrm {supp} (X)}$ a ${ displaystyle mathrm {conf} (X Rightarrow Y)}$ větší než uživatelem definovaná omezení.^[18]

Statisticky spolehlivé asociace

Jedním z omezení standardního přístupu k objevování asociací je to, že při prohledávání obrovského počtu možných asociací za účelem hledání kolekcí položek, které se zdají být přidružené, existuje velké riziko nalezení mnoha falešných asociací. Jedná se o sbírky položek, které se vyskytují s neočekávanou frekvencí v datech, ale pouze náhodou. Předpokládejme například, že uvažujeme o kolekci 10 000 položek a hledáme pravidla obsahující dvě položky na levé straně a 1 položku na pravé straně. Existuje přibližně 1 000 000 000 000 takových pravidel. Pokud použijeme statistický test nezávislosti s úrovní významnosti 0,05, znamená to, že existuje pouze 5% šance na přijetí pravidla, pokud neexistuje žádná asociace. Pokud předpokládáme, že neexistují žádné asociace, měli bychom přesto očekávat, že najdeme 50 000 000 000 pravidel. Statisticky spolehlivý objev asociace^[19][20] kontroluje toto riziko, ve většině případů snižuje riziko nálezu žádný falešné asociace na úroveň významnosti specifikovanou uživatelem.

Algoritmy

Bylo navrženo mnoho algoritmů pro generování asociačních pravidel.

Některé známé algoritmy jsou A priori, Eclat a FP-Growth, ale dělají jen polovinu práce, protože jsou to algoritmy pro těžbu častých položek. Po vygenerování pravidel z častých sad položek nalezených v databázi je třeba provést další krok.

Apriori algoritmus

A priori^[14] používá strategii pro vyhledávání na šířku k počítání podpory položek položek a používá funkci generování kandidátů, která využívá vlastnost uzavření dolů podpory.

Eclatův algoritmus

Sláva^[15] (alt. ECLAT, znamená Transformace třídy ekvivalence) je a hloubkové vyhledávání algoritmus založený na nastavené křižovatce. Je vhodný jak pro sekvenční, tak pro paralelní provedení s vlastnostmi zvyšujícími lokalitu.^[21][22]

Algoritmus růstu FP

FP znamená častý vzor.^[23]

Při prvním průchodu algoritmus spočítá výskyty položek (páry atribut-hodnota) v datové sadě transakcí a uloží tyto počty do „tabulky záhlaví“. Ve druhém průchodu vytvoří strukturu stromu FP vložením transakcí do a trie.

Položky v každé transakci je třeba před vložením seřadit podle sestupného pořadí jejich frekvence v datové sadě, aby bylo možné strom rychle zpracovat. Položky v každé transakci, které nesplňují minimální požadavek na podporu, jsou zahozeny. položky, strom FP poskytuje vysokou kompresi blízko kořene stromu.

Rekurzivní zpracování této komprimované verze hlavní datové sady rozšiřuje časté sady položek přímo, namísto generování kandidátských položek a jejich testování proti celé databázi (jako v algoritmu apriori).

Růst začíná od dolní části tabulky záhlaví, tj. U položky s nejmenší podporou vyhledáním všech seřazených transakcí, které v této položce končí. Zavolejte tuto položku ${ displaystyle I}$.

Je vytvořen nový podmíněný strom, na který se promítá původní strom FP ${ displaystyle I}$. Podpory všech uzlů v projektovaném stromu se přepočítají, přičemž každý uzel získá součet jeho podřízených počtů. Uzly (a tedy podstromy), které nesplňují minimální podporu, jsou prořezány. Rekurzivní růst končí, když nejsou podmíněny žádné jednotlivé položky ${ displaystyle I}$ splnit minimální práh podpory. Výsledné cesty od kořene k ${ displaystyle I}$ budou časté položky. Po tomto kroku pokračuje zpracování s další nejméně podporovanou položkou záhlaví původního stromu FP.

Po dokončení rekurzivního procesu budou nalezeny všechny časté sady položek a začne vytváření pravidla přidružení.^[24]

Ostatní

ASSOC

Postup ASSOC^[25] je metoda GUHA, která rychle využívá dolary pro obecná pravidla přidružení bitstrings operace. Pravidla přidružení těžená touto metodou jsou obecnější než pravidla vydaná apriori, například „položky“ mohou být spojeny jak s konjunkcí, tak s disjunkce a vztah mezi předchůdcem a následkem pravidla se neomezuje na stanovení minimální podpory a důvěry jako v apriori: lze použít libovolnou kombinaci opatření podporovaného úroku.

Hledání OPUS

OPUS je efektivní algoritmus pro zjišťování pravidel, který na rozdíl od většiny alternativ nevyžaduje monotónní ani anti-monotónní omezení, jako je minimální podpora.^[26] Zpočátku se používá k nalezení pravidel pro pevný následník^[26][27] následně byla rozšířena o vyhledání pravidel s jakoukoli položkou.^[28] Hledání OPUS je základní technologií v populárním systému zjišťování asociací Magnum Opus.

Lore

Slavným příběhem o těžbě asociačních pravidel je příběh „pivo a plenka“. Údajný průzkum chování nakupujících v supermarketech zjistil, že zákazníci (pravděpodobně mladí muži), kteří kupují plenky, mají tendenci kupovat také pivo. Tato anekdota se stala populární jako příklad toho, jak lze z každodenních dat najít neočekávaná pravidla přidružení. Názory na to, jak velká část příběhu je pravdivá, se liší.^[29] Daniel Powers říká:^[29]

V roce 1992 Thomas Blischok, manažer maloobchodní poradenské skupiny ve společnosti Teradata a jeho zaměstnanci připravili analýzu 1,2 milionu košů z asi 25 obchodů Osco Drug. Byly vyvinuty databázové dotazy k identifikaci spřízněnosti. Analýza „zjistila, že mezi 17:00 a 19:00 si spotřebitelé kupovali pivo a plenky“. Manažeři společnosti Osco NEVYUŽÍVALI vztah piva a plenek tím, že produkty na regálech přibližovali k sobě.

Jiné typy těžby asociačních pravidel

Pravidla asociace s více vztahy: Multi-Relation Association Rules (MRAR) are asociační pravidla, kde každá položka může mít několik vztahů. Tyto vztahy naznačují nepřímý vztah mezi entitami. Zvažte následující MRAR, kde první položka se skládá ze tří vztahů žít v, poblíž a vlhký: "Ti, kteří žít v místo, které je poblíž město s vlhký klimatický typ a také jsou mladší než 20 -> jejich zdravotní stav je dobrý". Taková asociační pravidla lze extrahovat z dat RDBMS nebo sémantických webových dat.^[30]

Učení kontrastní sady je forma asociativního učení. Kontrastní sada studentů používat pravidla, která se smysluplně liší v jejich distribuci napříč podmnožinami.^[31][32]

Vážené učení třídy je další forma asociativního učení, při které lze třídám přiřadit váhu, aby bylo možné zaměřit se na konkrétní problém, který se týká spotřebitele výsledků dolování dat.

Objevování vzorů vysokého řádu usnadňují zachycení (syntetických) vzorů vysokého řádu nebo asociací událostí, které jsou vlastní komplexním datům v reálném světě.^[33]

Optimální objevování vzorů K. poskytuje alternativu ke standardnímu přístupu k učení pravidel přidružení, která vyžaduje, aby se každý vzor v datech zobrazoval často.

Přibližná častá položka mining je uvolněná verze těžby Frequent Itemset, která umožňuje, aby některé položky v některých řádcích byly 0.^[34]

Zobecněná pravidla přidružení hierarchická taxonomie (pojmová hierarchie)

Kvantitativní pravidla přidružení kategorická a kvantitativní data

Pravidla pro intervalové přidružení dat např. rozdělit věk na 5letý přírůstek

Těžba sekvenčních vzorů objevuje posloupnosti, které jsou společné pro více než minsup^{[je zapotřebí objasnění ]} sekvence v databázi sekvencí, kde minsup nastavuje uživatel. Sekvence je seřazený seznam transakcí.^[35]

Shlukování podprostorů, konkrétní typ Shlukování vysoce dimenzionálních dat, je v mnoha variantách také založen na vlastnosti uzavření dolů pro konkrétní modely shlukování.^[36]

Warmr je dodáván jako součást sady pro dolování dat ACE. Umožňuje učení asociačních pravidel pro relační pravidla prvního řádu.^[37]

Viz také

• Sekvenční těžba
• Výrobní systém (počítačová věda)
• Systém klasifikace učení
• Strojové učení založené na pravidlech

Reference

Bibliografie

• Komentovaná bibliografie o pravidlech sdružení M. Hahsler