# 2. Методичні вказівки

Цей розділ **самодостатній**: у ньому зібрано теорію асоціативних правил, мір
інтересовності та алгоритмів Apriori і Eclat, потрібну для аудиторних задач
([3classroom.md](3classroom.md)) і домашньої програми ([4task.md](4task.md)).
Ширше цю саму теорію викладено в [Лекції 11](../../Lectures/DA-L11.md).

## 2.1 Транзакційна база та набори

**Транзакційна (операційна) база** — це множина транзакцій
$D = \{t_1, \dots, t_N\}$ над множиною **елементів** $I$; кожна транзакція
$t_i \subseteq I$ — набір елементів, що трапилися разом (чек, сеанс, історія
хвороби). **Набором** (англ. *itemset*) називають будь-яку підмножину
$X \subseteq I$; набір із $k$ елементів — **$k$-набір**.

Базу задають **горизонтально** (рядок — транзакція зі своїми елементами) або
**вертикально** (елемент $\to$ **tid-множина** — множина номерів транзакцій, що
його містять). Обидва формати рівносильні; вибір визначає зручніший алгоритм.

## 2.2 Підтримка

**Підтримка** (англ. *support*) набору $X$ — частка транзакцій, що містять $X$:

$$ \operatorname{supp}(X) = \frac{|\{\, t \in D : X \subseteq t \,\}|}{N}. $$

Підтримкою **правила** $X \Rightarrow Y$ називають підтримку об'єднання
$\operatorname{supp}(X \cup Y)$ — частку транзакцій, де є **і** $X$, **і** $Y$.
Порівнюючи з порогом, зручно тримати **лічильник** $|\{t : X \subseteq t\}|$ і
порівнювати його з $s_{\min} \cdot N$.

## 2.3 Достовірність

**Асоціативне правило** $X \Rightarrow Y$ будують для наборів, що **не
перетинаються** ($X \cap Y = \varnothing$). **Достовірність** (англ.
*confidence*) — умовна частка «серед транзакцій з $X$ — скільки містять і $Y$»:

$$ \operatorname{conf}(X \Rightarrow Y) = \frac{\operatorname{supp}(X \cup Y)}{\operatorname{supp}(X)}. $$

Це емпіричний аналог умовної ймовірності $P(Y \mid X)$. Достовірність
**напрямлена**: $\operatorname{conf}(X \Rightarrow Y) \ne \operatorname{conf}(Y \Rightarrow X)$.

## 2.4 Підйом і переконливість

Достовірність не враховує, наскільки поширений сам наслідок $Y$. Це виправляє
**підйом** (англ. *lift*):

$$ \operatorname{lift}(X \Rightarrow Y) = \frac{\operatorname{conf}(X \Rightarrow Y)}{\operatorname{supp}(Y)}
= \frac{\operatorname{supp}(X \cup Y)}{\operatorname{supp}(X)\,\operatorname{supp}(Y)}. $$

Він порівнює спільну появу $X$ і $Y$ з очікуваною за незалежності:
$\operatorname{lift} > 1$ — позитивний зв'язок (притягання), $= 1$ — незалежність,
$< 1$ — негативний. Підйом **симетричний**:
$\operatorname{lift}(X \Rightarrow Y) = \operatorname{lift}(Y \Rightarrow X)$.

**Переконливість** (англ. *conviction*) вимірює, як часто правило порушується:

$$ \operatorname{conv}(X \Rightarrow Y) = \frac{1 - \operatorname{supp}(Y)}{1 - \operatorname{conf}(X \Rightarrow Y)}. $$

$\operatorname{conv} > 1$ — правило змістовне (порушень менше, ніж випадково);
$\operatorname{conv} = 1$ — незалежність; $\operatorname{conv} \to \infty$ при
$\operatorname{conf} \to 1$ (правило без винятків).

## 2.5 Часті набори та властивість Apriori

Набір **частий**, якщо $\operatorname{supp} \ge s_{\min}$. Пошук правил — це
насамперед пошук **усіх частих наборів**; решта (генерація правил) дешева.
Ключ до ефективності — властивість антимонотонності.

> **Властивість Apriori.** Усі підмножини частого набору — часті; рівносильно,
> **будь-яка надмножина нечастого набору — нечаста**. Тому щойно набір виявився
> нечастим, усі його надмножини можна відкинути **не рахуючи**.

## 2.6 Алгоритм Apriori (горизонтальний)

Apriori будує часті набори за зростанням розміру $k$, роблячи прохід по базі на
кожному рівні:

1. **Часті 1-набори.** Порахувати підтримку кожного елемента; лишити ті, що
   $\ge s_{\min}$.
2. **Генерація кандидатів** ($k$-набори): **з'єднати** пари частих
   $(k{-}1)$-наборів, що різняться лише останнім елементом; **відсіяти** кандидата,
   якщо якась його $(k{-}1)$-підмножина нечаста.
3. **Підрахунок підтримки** кандидатів одним проходом по базі; лишити часті.
4. Повторювати кроки 2–3, доки з'являються нові часті набори.

## 2.7 Алгоритм Eclat (вертикальний)

Eclat дає **ті самі** часті набори, але рахує підтримку не проходом по базі, а
**перетином tid-множин**:

$$ \operatorname{tid}(X \cup Y) = \operatorname{tid}(X) \cap \operatorname{tid}(Y), \qquad
\operatorname{supp}(X \cup Y) = \frac{|\operatorname{tid}(X) \cap \operatorname{tid}(Y)|}{N}. $$

Він будує **префіксне дерево** завглибшки: кожен вузол додає елемент, а його
tid-множину дістає перетином tid-множини батька з tid-множиною нового елемента;
нечасті вузли не розгалужують. Eclat вигідний на **розріджених** базах (малі
tid-множини), Apriori — простіший і ощадливіший за пам'яттю.

## 2.8 Демонстраційний приклад (на інших даних, ніж у задачах)

Розгляньмо базу невеликої чайної крамниці ($N = 5$ транзакцій) над елементами
$I = \{\text{Чай}, \text{Цукор}, \text{Лимон}, \text{Мед}\}$:

| Транзакція | Елементи |
|:--:|---|
| $t_1$ | Чай, Цукор |
| $t_2$ | Чай, Цукор, Лимон |
| $t_3$ | Чай, Цукор, Мед |
| $t_4$ | Чай, Лимон |
| $t_5$ | Лимон, Мед |

**(а) Підтримка та вертикальний формат.** tid-множини елементів:
$\operatorname{tid}(\text{Чай}) = \{1,2,3,4\}$,
$\operatorname{tid}(\text{Цукор}) = \{1,2,3\}$,
$\operatorname{tid}(\text{Лимон}) = \{2,4,5\}$,
$\operatorname{tid}(\text{Мед}) = \{3,5\}$. Звідси

$$ \operatorname{supp}(\{\text{Чай}\}) = \tfrac{4}{5} = 0.8, \quad
\operatorname{supp}(\{\text{Цукор}\}) = \tfrac{3}{5} = 0.6, \quad
\operatorname{supp}(\{\text{Лимон}\}) = \tfrac{3}{5} = 0.6, \quad
\operatorname{supp}(\{\text{Мед}\}) = \tfrac{2}{5} = 0.4. $$

Підтримка пари через перетин:
$\operatorname{tid}(\text{Чай}) \cap \operatorname{tid}(\text{Цукор}) = \{1,2,3\}$,
тож $\operatorname{supp}(\{\text{Чай}, \text{Цукор}\}) = \tfrac{3}{5} = 0.6$.

![Вертикальний формат чайної крамниці та підтримка набору Чай-Цукор через перетин tid-множин](img/lab11_tidsets.png)

**(б) Міри для правила $\{\text{Чай}\} \Rightarrow \{\text{Цукор}\}$.**

$$ \operatorname{conf} = \frac{0.6}{0.8} = 0.75, \qquad
\operatorname{lift} = \frac{0.75}{0.6} = 1.25, \qquad
\operatorname{conv} = \frac{1 - 0.6}{1 - 0.75} = \frac{0.4}{0.25} = 1.6. $$

Зворотне правило $\{\text{Цукор}\} \Rightarrow \{\text{Чай}\}$ має ту саму
підтримку $0.6$, але $\operatorname{conf} = 0.6/0.6 = 1.0$ (усі покупці
цукру беруть чай), той самий підйом $1.25$ (симетричний), а
$\operatorname{conv} \to \infty$. Підйом **однаковий** для обох напрямків,
достовірність і переконливість — **ні**.

**(в) Apriori за $s_{\min} = 0.4$** (лічильник $\ge 2$). Часті 1-набори — усі
чотири. Кандидати-пари й підтримки:

| 2-набір | Лічильник | Частий? |
|---|:--:|:--:|
| $\{\text{Чай}, \text{Цукор}\}$ | 3 | так |
| $\{\text{Чай}, \text{Лимон}\}$ | 2 | так |
| $\{\text{Чай}, \text{Мед}\}$ | 1 | ні |
| $\{\text{Цукор}, \text{Лимон}\}$ | 1 | ні |
| $\{\text{Цукор}, \text{Мед}\}$ | 1 | ні |
| $\{\text{Лимон}, \text{Мед}\}$ | 1 | ні |

Часті 2-набори: $\{\text{Чай}, \text{Цукор}\}$ і $\{\text{Чай}, \text{Лимон}\}$.
Єдиний кандидат-трійка $\{\text{Чай}, \text{Цукор}, \text{Лимон}\}$ **відсівається
без підрахунку**: його підмножина $\{\text{Цукор}, \text{Лимон}\}$ нечаста
(властивість Apriori). Отже, частих 3-наборів немає.

## 2.9 Робочий контрольний список

- Спершу зафіксуйте **пороги** $s_{\min}$ і $c_{\min}$ та переведіть $s_{\min}$ у
  **лічильник** $s_{\min}\cdot N$ — так зручніше порівнювати.
- Часті набори шукайте **за зростанням розміру**; нечастий набір **відразу**
  вилучайте з подальших з'єднань (не рахуйте його надмножин).
- Достовірність рахуйте **для кожного напрямку** окремо; підтримка набору —
  спільна для всіх правил із нього.
- Підйом і переконливість застосовуйте **після** порогів — щоб упорядкувати
  правила й прибрати оманливо-достовірні ($\operatorname{lift} \le 1$).
- Для перевірки підтримки зручний **вертикальний формат**: підтримка набору —
  потужність перетину tid-множин його елементів.