Вступ до пошуку асоціативних правил

Ця стаття знайомить з основною ідеєю пошуку асоціативних правил. Ми розглянемо базові принципи пошуку асоціативних правил, визначимо ключові поняття, зокрема підтримку та довіру, а також виконаємо пошук асоціативних правил на наборі даних Market Basket Analysis з платформи Kaggle.

Що таке асоціація?

Wikipedia подає таке визначення асоціації:

будь-який зв’язок між двома вимірюваними величинами, який робить їх статистично залежними, але не обов’язково причинно-наслідково пов’язаними або корельованими

Визначення

Розглянемо множину $\mathcal{I}=\{ i_1, i_2, ..., i_m \}$ , елементи якої є літералами; надалі ми також називатимемо їх елементами. Довільну підмножину $T$ множини ${\mathcal{I}}$ називатимемо набором елементів або транзакцією.

Приклад: Нехай $\mathcal{I}= \{ \textrm{молоко}, \textrm{масло}, \textrm{яйця} \}$ і $T = \{ \textrm{молоко}, \textrm{масло}\}$ . Тоді $T$ є транзакцією.

Нехай $\mathcal{I}$ — множина всіх елементів. Пару $(X,Y)$ називатимемо асоціативним правилом, якщо $X \subseteq \mathcal{I}$ , $Y \subseteq \mathcal{I}$ , а також $X \cap Y = \emptyset$ . Позначатимемо її як $X \Rightarrow Y$ .

Приклад: Нехай $\mathcal{I} = \{ \textrm{молоко}, \textrm{масло}, \textrm{яйця}\}$ . Тоді $\{ \textrm{молоко} \} \Rightarrow \{ \textrm{масло} \}$ є асоціативним правилом.

Метрики

Щоб визначити, чи є асоціативне правило цікавим, використаємо такі метрики:

Підтримка: Підтримка набору елементів $X$ визначається як частка транзакцій у базі даних, у яких цей набір елементів трапляється.

\large \textrm{support}(X) = \frac{\text{кількість транзакцій, що містять } X}{\text{загальна кількість транзакцій}}

Довіра: Довіра правила $X \Rightarrow Y$ — це частка транзакцій, які містять $X$ і водночас $Y$ , серед усіх транзакцій, що містять $X$ .

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

Алгоритми

Apriori

Цей алгоритм був запропонований Агравалом і Срікантом у 1994 році¹. Свою назву він отримав завдяки припущенню, яке називають апріорним принципом. Він стверджує, що:

Кожна підмножина частого набору елементів також є частою. Еквівалентно, якщо набір не є частим, то жодна його надмножина також не є частою.

Також можна зустріти терміни антимонотонність або властивість замкненості вниз.

Завдяки цій властивості можна ефективно звузити простір пошуку. Зазначений принцип дозволяє поступово збільшувати розмір наборів і таким чином знаходити всі часті набори.

Як він працює?

Алгоритм виконує кілька проходів по базі даних. Перший прохід просто підраховує значення підтримки для кожного елемента. Ті елементи, що досягають заданого порога, вважаються частими одноелементними наборами. На $k$ -му кроці на основі частих наборів, знайдених на $(k-1)$ -му кроці, та за допомогою функції apriori-gen генеруються кандидатні $k$ -елементні набори. Після цього ми проходимо по базі даних і обчислюємо підтримку кандидатних наборів. Наприкінці проходу вибираються лише ті кандидатні набори, які є частими, і саме вони використовуються на наступному кроці. Алгоритм виконується доти, доки всі кандидатні набори з попереднього переходу не матимуть підтримку, меншу за заданий поріг.

Псевдокод

L = { часті 1-елементні набори }
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 }

Функція apriori_gen, яка отримує всі $(k-1)$ -елементні часті набори й повертає кандидатні $k$ -елементні набори, складається з двох кроків:

Крок JOIN: об’єднуються всі набори, що мають однаковий $(k-2)$ -елементний префікс.

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

Крок PRUNE: видаляються всі набори, що мають принаймні одну нечасту підмножину.

 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;

Переваги та недоліки

Головним недоліком цього алгоритму є його обчислювальна складність. Обробка великої кількості кандидатних наборів є дорогою. Наприклад, якщо існує $10^4$ частих одноелементних наборів, Apriori має згенерувати понад $10^7$ двоелементних наборів. Крім того, щоб знайти деякий частий набір потужності 100, наприклад $\{a_1, ...,a_{100}\}$ , алгоритму потрібно згенерувати понад $2^{100} \approx 10^{30}$ кандидатів².

FP-Growth

Алгоритм був запропонований у 2000 році Ханом, Пеєм і Їнем². Він є суттєвим покращенням порівняно з попереднім алгоритмом, оскільки не потребує генерування кандидатних наборів, що приводить до значного підвищення продуктивності.

Алгоритм FP-growth складається з двох фаз:

побудова FP-дерева, яке є компактним представленням даних,
генерування частих наборів елементів за допомогою FP-дерева.

Як він працює?

Алгоритм представляє базу даних за допомогою деревоподібної структури, яка називається деревом частих шаблонів, скорочено FP-деревом. Ця структура дозволяє ефективно запитувати частоти, тобто підтримку, довільного набору, і розроблена так, щоб бути компактною та не вимагати багаторазових проходів по базі даних під час побудови.

Логічно, таке дерево не повинно містити нечастих елементів, оскільки будь-який набір, що містить нечастий елемент, не може бути частим.

Кожен вузол дерева, крім кореня, має такі атрибути:

item-name: записує, який елемент представляє цей вузол.
count: кількість транзакцій, що містять елементи на шляху до цього вузла.
node-link: посилання на інші вузли дерева з тією самою назвою.

Для спрощення пошуку й доступу до вузлів створюється заголовкова таблиця. Кожен її запис представляє один елемент і містить посилання на вузол у дереві, де цей елемент розташований.

Псевдокод

Кожна транзакція з бази даних відображається на шлях у дереві.

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

На першому рядку створюється заголовкова таблиця та визначається порядок елементів у транзакціях. Завдяки впорядкуванню елементів часті елементи опиняються на початку транзакції, а під час вставлення в дерево вони розміщуються ближче до кореня. Це збільшує ймовірність того, що відповідний елемент буде спільним для кількох транзакцій.

Гілка рядка 6 відповідає проходженню вже наявним шляхом. У цьому випадку лічильник відповідного вузла просто інкрементується, що заощаджує час і ресурси.

Гілка рядків 8–12 розглядає випадок, коли в дереві немає відповідного вузла, до якого можна перейти. У такому разі ми створюємо такий вузол і ініціалізуємо його всіма необхідними значеннями.

Побудоване таким чином дерево містить повну інформацію про базу даних з погляду пошуку частих наборів. Тобто кожна транзакція відповідає одному шляху, а вся необхідна інформація, зокрема значення підтримки, зберігається в дереві.

Варто зазначити, що розмір дерева обмежений загальною кількістю входжень частих наборів у базі даних, а його висота обмежена розміром найбільшого частого набору в будь-якій транзакції².

Приклад FP-дерева

Переваги та недоліки

Автори цього алгоритму зазначають, що розмір FP-дерева зазвичай значно менший за розмір бази даних. Так само умовне FP-дерево зазвичай значно менше за початкове дерево (умовне FP-дерево є піддеревом початкового дерева). Завдяки цьому принципу кожна наступна ітерація працює з дедалі меншим обсягом даних. Отже, з погляду ефективності алгоритм FP-growth є значно ефективнішим порівняно з алгоритмом Apriori.

Хоча алгоритм FP-growth є швидшим, його реалізація складніша порівняно з алгоритмом Apriori.

[Вгору]

Набір даних

Для аналізу за допомогою асоціативних правил ми використали набір даних „The Bread Basket“, доступний на платформі Kaggle³. Цей набір даних містить інформацію про транзакції в пекарні „The Bread Basket“ в Единбурзі, Шотландія.

Набір даних є публічно доступним для завантаження у форматі .csv. Він містить 20507 записів, понад 9000 транзакцій і 5 атрибутів:

No: унікальний ідентифікатор транзакції (число в діапазоні від 1 до 9684).
Item: назва придбаного продукту, наприклад хліб, кава або чай.
DateTime: дата й час транзакції, наприклад 30.10.2016 9:58.
Daypart: частина дня, коли була здійснена транзакція, наприклад ранок.
DayType: вказує, чи була транзакція здійснена у вихідний або робочий день.

No.	Елементи	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

Фактична реалізація методу Apriori приймає дані у формі, де окремі транзакції розміщені в рядках, а елементи — у стовпцях. Значення 1 або 0 в $i$ -му рядку та $j$ -му стовпці таблиці визначає, чи був елемент $j$ придбаний у транзакції $i$ .

Дехто може помітити, що існують елементи, які були придбані кілька разів. Під час пошуку правил ми ігноруємо цей факт.

В аналізі ми також враховуємо часовий аспект. До підсумкової таблиці додаємо чотири стовпці: Afternoon, Evening, Morning, Night. Підсумковий датафрейм, який буде вхідними даними для методу пошуку, наведено нижче:

[Вгору]

Пошук правил

Проблему пошуку асоціативних правил можна поділити на два завдання:

Знайти всі набори елементів, підтримка яких більша за заданий поріг підтримки. Набір, що задовольняє цю умову, називається частим.
Використати знайдені часті набори для генерування всіх правил. Для цієї задачі маємо прямий алгоритм. Для кожного частого набору $Y$ знаходимо всі його непорожні підмножини, і для кожної такої підмножини $X$ повертаємо правило $X \Rightarrow Y \setminus X$ якщо це правило задовольняє умову мінімального значення довіри.

Наступні параметри для асоціативних правил були обрані експериментально:

поріг підтримки правила: $\textrm{min\_sup} = 0{,}03$ ,
поріг довіри: $\textrm{min\_conf} = 0{,}5$ .

Для правила $A \Rightarrow B$ вимагаємо, щоб $A \cup B$ траплялося щонайменше в $3 \%$ транзакцій, а $B$ траплялося з імовірністю щонайменше $50 \%$ у кожній транзакції, що містить $A$ .

Реалізація

Із доступних онлайн-реалізацій алгоритмів Apriori та FP-growth ми вирішили реалізувати метод за допомогою бібліотеки mlxtend⁴.

Підготовка даних

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

Пошук асоціативних правил

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])

Результати

Нам вдалося видобути асоціативні правила з набору даних. У таблиці нижче наведено деякі з 23 правил, відсортованих за довірою.

No.	Антецеденти	Консеквенти	Підтримка	Довіра
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

Аналітик може інтерпретувати ці правила так:

правила 1, 2, 13: У післяобідні години в кав’ярні спостерігається підвищений продаж супів, тістечок, сендвічів і чаю. У відповідь на це власник кав’ярні може розглянути запровадження спеціальних пропозицій, наприклад поєднання чаю з тістечком або сендвічем за зниженою ціною.
правила 14, 18, 19: Кава є супутнім продуктом до різних страв. Цю сильну асоціацію власник кав’ярні може використати для стимулювання спільного продажу обох продуктів, наприклад запропонувавши знижку на каву при купівлі страви.

[Вгору]

Бібліографія

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. Available at: https://www.kaggle.com/datasets/akashdeepkuila/bakery bakery. [cit. 2024. 4. 28]. ↩
Raschka, Sebastian. apriori: Frequent itemsets via the Apriori algorithm [online]. Available at: https://rasbt.github.io/mlxtend/user_guide/frequent_patterns/apriori/. [cit. 2024. 4. 25]. ↩

Що таке асоціація?

Визначення

Метрики

Алгоритми

Apriori

Як він працює?

Псевдокод

Переваги та недоліки

FP-Growth

Як він працює?

Псевдокод

Переваги та недоліки

Набір даних

Пошук правил

Реалізація

Підготовка даних

Пошук асоціативних правил

Результати

Бібліографія

Footnotes