Úvod do dolovania asociačných pravidiel

Tento článok predstavuje základný koncept dolovania asociačných pravidiel. Vysvetlíme si princíp dolovania asociačných pravidiel, definujeme základné pojmy, ako sú podpora a konfidenčnosť, a následne budeme dolovať asociačné pravidlá pomocou dátovej množiny Market Basket Analysis z platformy Kaggle.

Čo je asociácia?

Wikipedia uvádza nasledujúcu definíciu asociácie:

akýkoľvek vzťah medzi dvoma meranými veličinami, ktorý spôsobuje, že sú štatisticky závislé, hoci nemusí ísť o kauzálny vzťah ani o koreláciu

Definície

Uvažujme množinu $\mathcal{I}=\{ i_1, i_2, ..., i_m \}$ , kde prvky tejto množiny sú literály, ktoré budeme nazývať aj položky. Ľubovoľnú podmnožinu $T$ množiny ${\mathcal{I}}$ budeme nazývať množina položiek alebo transakcia.

Príklad: Nech $\mathcal{I}= \{ \textrm{mlieko}, \textrm{maslo}, \textrm{vajcia} \}$ a $T = \{ \textrm{mlieko}, \textrm{maslo}\}$ . Potom $T$ je transakcia.

Nech $\mathcal{I}$ je množina všetkých položiek. Dvojicu $(X,Y)$ budeme nazývať asociačné pravidlo, ak $X \subseteq \mathcal{I}$ , $Y \subseteq \mathcal{I}$ a zároveň $X \cap Y = \emptyset$ . Budeme ju zapisovať ako $X \Rightarrow Y$ .

Príklad: Nech $\mathcal{I} = \{ \textrm{mlieko}, \textrm{maslo}, \textrm{vajcia}\}$ . Potom $\{ \textrm{mlieko} \} \Rightarrow \{ \textrm{maslo} \}$ je asociačné pravidlo.

Metriky

Na určenie toho, či je asociačné pravidlo zaujímavé, použijeme nasledujúce metriky:

Podpora: Podpora množiny položiek $X$ je definovaná ako podiel transakcií v databáze, v ktorých sa táto množina položiek vyskytuje.

\large \textrm{support}(X) = \frac{\text{počet transakcií obsahujúcich } X}{\text{celkový počet transakcií}}

Konfidenčnosť: Konfidenčnosť pravidla $X \Rightarrow Y$ je podiel transakcií obsahujúcich $X$ a zároveň $Y$ vzhľadom na všetky transakcie obsahujúce $X$ .

\large \textrm{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}

Algoritmy

Apriori

Tento algoritmus navrhli Agrawal a Srikanth v roku 1994¹. Svoj názov dostal podľa predpokladu, ktorý nazývame a priori princíp. Ten hovorí, že:

Každá podmnožina frekventovanej množiny položiek je tiež frekventovaná. Ekvivalentne, ak množina nie je frekventovaná, potom nie je frekventovaná ani žiadna jej nadmnožina.

Môžeme sa stretnúť aj s pojmami antimonotónnosť alebo vlastnosť uzavretosti smerom nadol.

Vďaka tejto vlastnosti možno efektívne zúžiť prehľadávaný priestor. Uvedený princíp umožňuje postupne zväčšovať veľkosť množín a tým nájsť všetky frekventované množiny.

Ako funguje?

Algoritmus vykoná niekoľko prechodov databázou. Pri prvom prechode jednoducho spočíta hodnoty podpory jednotlivých položiek. Tie, ktoré spĺňajú zadaný prah, sa považujú za frekventované jednoprvkové množiny. V $k$ -tom kroku sa na základe frekventovaných množín nájdených v $(k-1)$ -tom kroku a pomocou funkcie apriori-gen vygenerujú kandidátske $k$ -prvkové množiny. V tomto kroku potom prejdeme databázu a vypočítame podporu kandidátskych množín. Na konci prechodu sa vyberú iba tie kandidátske množiny, ktoré sú frekventované, a tie sa použijú v ďalšom kroku. Algoritmus sa vykonáva dovtedy, kým všetky kandidátske množiny z predchádzajúceho prechodu nemajú podporu menšiu ako zadaný prah.

Pseudokód

L = { frekventované 1-prvkové množiny }
for (k = 2; Lk_1 != ∅; k++) do
    Ck = apriori_gen(Lk_1)
    for all transactions t in database do
        Ct = subset(Ck, t)
        for all candidates c in Ct do
            c.count++
    Lk = { c ∈ Ck | c.count ≥ min_sup }

Funkcia apriori_gen, ktorá berie všetky $(k-1)$ -prvkové frekventované množiny a vracia kandidátske $k$ -prvkové množiny, pozostáva z dvoch krokov:

Krok JOIN: spoja sa všetky množiny, ktoré majú rovnaký $(k-2)$ -prvkový prefix.

INSERT INTO Ck
SELECT p.item1,p.item2, ... , p.itemk_1, q.itemk_1
FROM Lk_1 p, Lk_1 q
WHERE p.item1 = q.item1, ..., p.itemk_2 = q.itemk_2 , p.itemk_1 < q.itemk_1

Krok PRUNE: odstránia sa všetky množiny, ktoré majú niektorú nefrekventovanú podmnožinu.

 for all set c ∈ Ck do
     for all (k-1)_element set s, s ⊆ c do
     if s ̸∈ Lk_1 then
     remove c from Ck;

Výhody a nevýhody

Hlavnou nevýhodou tohto algoritmu je jeho výpočtová zložitosť. Spracovanie veľkého počtu kandidátskych množín je nákladné. Ak napríklad existuje $10^4$ frekventovaných jednoprvkových množín, algoritmus Apriori musí vygenerovať viac ako $10^7$ dvojprvkových množín. Navyše, na nájdenie frekventovanej množiny kardinality 100, napríklad $\{a_1, ...,a_{100}\}$ , musí algoritmus vygenerovať viac ako $2^{100} \approx 10^{30}$ kandidátov².

FP-Growth

Algoritmus navrhli v roku 2000 Han, Pei a Yin². Predstavuje významné zlepšenie oproti predchádzajúcemu algoritmu, pretože nevyžaduje generovanie kandidátskych množín, čo vedie k výraznému zvýšeniu výkonu.

Algoritmus FP-growth pozostáva z dvoch fáz:

konštrukcia FP-stromu, ktorý je kompaktnou reprezentáciou dát,
generovanie frekventovaných množín položiek pomocou FP-stromu.

Ako funguje?

Algoritmus reprezentuje databázu pomocou stromovej štruktúry nazývanej strom frekventovaných vzorov, skrátene FP-strom. Táto štruktúra umožňuje efektívne zisťovať frekvencie, resp. podporu ľubovoľnej množiny, a je navrhnutá tak, aby bola kompaktná a pri svojej konštrukcii nevyžadovala viacnásobné prechody databázou.

Logicky takýto strom nemusí obsahovať nefrekventované položky, pretože žiadna množina obsahujúca nefrekventovanú položku nemôže byť frekventovaná.

Každý uzol stromu, okrem koreňa, má nasledujúce atribúty:

item-name: zaznamenáva, ktorú položku daný uzol reprezentuje.
count: počet transakcií, ktoré obsahujú položky na ceste k danému uzlu.
node-link: odkaz na ďalšie uzly v strome s rovnakým názvom.

Na jednoduchšie vyhľadávanie a prístup k uzlom sa vytvára hlavičková tabuľka. Každý jej záznam reprezentuje jednu položku a obsahuje odkaz na uzol v strome, v ktorom sa daná položka nachádza.

Pseudokód

Každá transakcia z databázy sa mapuje na cestu v strome.

1   sort items in transaction in descending order of frequency
2   for all transactions do
3       T = root of the tree
4       for each item in transaction do
5       if T has child N AND N.name = item  then
6           T.count++;
7       else
8           N = create a new node
9           N.count = 1;
10          N.name = item;
11          T.addChild(N);
12          T.node_link = other node, that has the same name as N

Na prvom riadku sa vytvorí hlavičková tabuľka a určí sa poradie položiek v transakciách. Usporiadaním položiek sa uprednostnia častejšie položky na začiatku transakcie. Pri vkladaní do stromu sa tak častejšie položky vložia bližšie ku koreňu, čím sa zvýši pravdepodobnosť, že daná položka bude zdieľaná viacerými transakciami.

Vetva riadku 6 zodpovedá prechodu po existujúcej ceste. V tomto prípade sa jednoducho inkrementuje počítadlo príslušného uzla, čím sa šetrí čas aj pamäťové zdroje.

Vetva riadkov 8–12 rieši prípad, keď v strome neexistuje zodpovedajúci uzol, do ktorého možno vstúpiť. V takom prípade takýto uzol vytvoríme a inicializujeme ho všetkými potrebnými hodnotami.

Takto skonštruovaný strom obsahuje úplnú informáciu o databáze z hľadiska vyhľadávania frekventovaných množín. Každá transakcia teda zodpovedá jednej ceste a všetky potrebné informácie, napríklad hodnota podpory, sú uložené v strome.

Za zmienku stojí, že veľkosť stromu je ohraničená celkovým výskytom frekventovaných množín v databáze a jeho výška je ohraničená veľkosťou najväčšej frekventovanej množiny v ľubovoľnej transakcii².

Príklad FP-stromu

Výhody a nevýhody

Autori tohto algoritmu uvádzajú, že veľkosť FP-stromu je zvyčajne oveľa menšia než veľkosť databázy. Podobne je podmienený FP-strom zvyčajne oveľa menší než pôvodný strom (podmienený FP-strom je podstromom pôvodného stromu). Vďaka tomuto princípu každá nasledujúca iterácia pracuje so stále menším množstvom dát. Z hľadiska efektívnosti je preto algoritmus FP-growth výrazne efektívnejší než algoritmus Apriori.

Hoci je algoritmus FP-growth rýchlejší, jeho implementácia je v porovnaní s algoritmom Apriori zložitejšia.

[Hore]

Dátová množina

Na analýzu pomocou asociačných pravidiel sme použili dátovú množinu „The Bread Basket“, ktorá je dostupná na platforme Kaggle³. Táto dátová množina obsahuje informácie o transakciách v pekárni „The Bread Basket“ v Edinburghu v Škótsku.

Dátová množina je verejne dostupná na stiahnutie vo formáte .csv. Obsahuje 20507 záznamov, viac ako 9000 transakcií a 5 atribútov:

No: jedinečný identifikátor transakcie (číslo v rozsahu 1 až 9684).
Item: názov zakúpeného produktu, napríklad chlieb, káva alebo čaj.
DateTime: dátum a čas transakcie, napríklad 30.10.2016 9:58.
Daypart: časť dňa, v ktorej bola transakcia vykonaná, napríklad ráno.
DayType: informácia o tom, či bola transakcia vykonaná počas víkendu alebo pracovného dňa.

No.	Položky	DateTime	Daypart	DayType
1	Bread	30. 10. 2016 9:58	Morning	Weekend
2	Scandinavian	30. 10. 2016 10:05	Morning	Weekend
2	Scandinavian	30. 10. 2016 10:05	Morning	Weekend
…	…	…	…	…
9683	Coffee	04. 09. 2017 14:57	Afternoon	Weekend
9683	Pastry	04. 09. 2017 14:57	Afternoon	Weekend
9684	Smoothies	04. 09. 2017 15:04	Afternoon	Weekend

Samotná implementácia metódy Apriori prijíma dáta vo forme, v ktorej sú jednotlivé transakcie v riadkoch a položky v stĺpcoch. Hodnota 1 alebo 0 v $i$ -tom riadku a $j$ -tom stĺpci tabuľky určuje, či bola položka $j$ zakúpená v rámci transakcie $i$ .

Niektorí si môžu všimnúť, že existujú položky, ktoré boli zakúpené viackrát. Pri dolovaní túto skutočnosť ignorujeme.

V analýze zohľadňujeme aj časový aspekt. Do výslednej tabuľky pridáme štyri stĺpce: Afternoon, Evening, Morning, Night. Výsledný dátový rámec, ktorý bude slúžiť ako vstup pre metódu dolovania, je uvedený nižšie:

[Hore]

Dolovanie

Problém hľadania asociačných pravidiel možno rozdeliť na dve úlohy:

Nájsť všetky množiny položiek, ktorých podpora je väčšia než zadaný prah podpory. Množina, ktorá spĺňa túto podmienku, sa nazýva frekventovaná.
Použiť nájdené frekventované množiny na generovanie všetkých pravidiel. Pre daný problém máme priamočiary algoritmus. Pre každú frekventovanú množinu $Y$ nájdeme všetky jej neprázdne podmnožiny a pre každú takúto podmnožinu $X$ vrátime pravidlo $X \Rightarrow Y \setminus X$ ak pravidlo spĺňa podmienku minimálnej hodnoty konfidenčnosti.

Nasledujúce parametre pre asociačné pravidlá boli zvolené experimentálne:

prah podpory pravidla: $\textrm{min\_sup} = 0{,}03$ ,
prah konfidenčnosti: $\textrm{min\_conf} = 0{,}5$ .

Pre pravidlo $A \Rightarrow B$ požadujeme, aby sa $A \cup B$ vyskytovalo aspoň v $3 \%$ transakcií a aby sa $B$ vyskytovalo s pravdepodobnosťou aspoň $50 \%$ v každej transakcii obsahujúcej $A$ .

Implementácia

Z dostupných online implementácií algoritmov Apriori a FP-growth sme sa rozhodli implementovať metódu pomocou knižnice mlxtend⁴.

Príprava dát

dataset = pd.read_csv("bakery.csv")

transactions_str = dataset.groupby(['TransactionNo', 'Items', "Daypart"])['Items'].count().reset_index(name ='Count')
my_basket = transactions_str.pivot_table(index=['TransactionNo'], columns=['Items'], values='Count', aggfunc='sum').fillna(0)
daypart = transactions_str.pivot_table(index=['TransactionNo'], columns=['Daypart'], values='Count', aggfunc='sum').fillna(0)
daypart

def encode(x):
    return False if x <= 0 else True

df = my_basket.apply(lambda row: row.map(encode), axis=1)
daypart = daypart.apply(lambda row: row.map(encode), axis=1)

df = pd.concat([df, daypart], axis=1)
df

Dolovanie asociačných pravidiel

Apriori

# finding frequent itemsets
frq_items = apriori(df, min_support = 0.03, use_colnames = True)

rules = association_rules(frq_items, metric ="confidence", min_threshold = 0.5)
rules = rules.sort_values(['confidence'], ascending =[ False])

FP-Growth

# finding frequent itemsets
frq_items = fpgrowth(df, min_support = 0.03, use_colnames = True)

rules = association_rules(frq_items, metric ="confidence", min_threshold = 0.5)
rules = rules.sort_values(['confidence'], ascending =[ False])

Výsledky

Z dátovej množiny sa nám podarilo vydolovať asociačné pravidlá. Tabuľka nižšie zobrazuje niektoré z 23 pravidiel zoradených podľa konfidenčnosti.

No.	Antecedenty	Konsekventy	Podpora	Konfidenčnosť
1	Soup	Afternoon	0,032647	0,947853
2	Sandwich, Coffee	Afternoon	0,033492	0,875691
…	…	…	…	…
12	Medialuna	Coffee	0,035182	0,569231
13	Hot chocolate	Afternoon	0,033069	0,567029
14	Morning, Pastry	Coffee	0,033492	0,554196
…	…	…	…	…
18	Sandwich	Coffee	0,038246	0,532352
19	Cake	Coffee	0,054727	0,52695
…	…	…	…	…
22	Morning	Coffee	0,223244	0,514989
23	Bread	Afternoon	0,164395	0,502422

Tieto pravidlá môže analytik interpretovať napríklad takto:

pravidlá 1, 2, 13: Počas popoludňajších hodín zaznamenáva kaviareň zvýšený predaj polievok, koláčov, sendvičov a čaju. V reakcii na túto situáciu môže majiteľ kaviarne zvážiť zavedenie špeciálnych ponúk, napríklad kombináciu čaju s koláčom alebo sendvičom za zvýhodnenú cenu.
pravidlá 14, 18, 19: Káva slúži ako doplnok k viacerým jedlám. Túto silnú asociáciu môže majiteľ kaviarne využiť na podporu spoločného predaja oboch produktov, napríklad zľavou na kávu pri kúpe jedla.

[Hore]

Bibliografia

Agrawal, Rakesh and Ramakrishnan Srikant, 1994. Fast Algorithms for Mining Association Rules in Large Databases. In: Proceedings of the 20th International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers Inc., p. 487–499. ISBN 1558601538 ↩
Han, Jiawei et al, 2004. Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach. In: Data Min. Knowl. Discov.. Vol. 8, p. 53–87. doi: 10.1023/B:DAMI.0000005258.31418.83 ↩ ↩² ↩³
Kuila, Akashdeep, 2021. Bakery Sales Dataset [online]. Data in CSV. Kaggle. Dostupné na: https://www.kaggle.com/datasets/akashdeepkuila/bakery bakery. [cit. 2024. 4. 28]. ↩
Raschka, Sebastian. apriori: Frequent itemsets via the Apriori algorithm [online]. Dostupné na: https://rasbt.github.io/mlxtend/user_guide/frequent_patterns/apriori/. [cit. 2024. 4. 25]. ↩

Čo je asociácia?

Definície

Metriky

Algoritmy

Apriori

Ako funguje?

Pseudokód

Výhody a nevýhody

FP-Growth

Ako funguje?

Pseudokód

Výhody a nevýhody

Dátová množina

Dolovanie

Implementácia

Príprava dát

Dolovanie asociačných pravidiel

Výsledky

Bibliografia

Footnotes