# 3. Аудиторні задачі з розв'язаннями

Ці задачі розбирають **в аудиторії «руками»**. Вони показують ті самі обчислення,
які потім автоматизує домашня програма ([4task.md](4task.md)). Теорія й формули —
у [методичних вказівках](2method.md). Дані задач **відрізняються** від
демонстраційного прикладу у [2method.md](2method.md).

## Задача 1. Міри інтересовності на малій базі

**Дано** транзакційну базу міні-маркету ($N = 5$ транзакцій):

| Транзакція | Елементи |
|:--:|---|
| $t_1$ | Кола, Чипси |
| $t_2$ | Кола, Чипси, Пиво |
| $t_3$ | Кола, Горішки |
| $t_4$ | Чипси, Пиво, Горішки |
| $t_5$ | Кола, Чипси, Пиво, Горішки |

**Знайти:** підтримку наборів $\{\text{Кола}\}$, $\{\text{Чипси}\}$,
$\{\text{Пиво}\}$, $\{\text{Кола}, \text{Чипси}\}$, $\{\text{Чипси}, \text{Пиво}\}$;
а також достовірність, підйом і переконливість правил
$\{\text{Чипси}\} \Rightarrow \{\text{Пиво}\}$,
$\{\text{Пиво}\} \Rightarrow \{\text{Чипси}\}$ та
$\{\text{Кола}\} \Rightarrow \{\text{Чипси}\}$.

**Розв'язання.** Підрахуємо лічильники транзакцій.

- Кола — у $t_1, t_2, t_3, t_5$: лічильник $4$, $\operatorname{supp} = \tfrac{4}{5} = 0.8$.
- Чипси — у $t_1, t_2, t_4, t_5$: лічильник $4$, $\operatorname{supp} = \tfrac{4}{5} = 0.8$.
- Пиво — у $t_2, t_4, t_5$: лічильник $3$, $\operatorname{supp} = \tfrac{3}{5} = 0.6$.
- $\{\text{Кола}, \text{Чипси}\}$ — у $t_1, t_2, t_5$: $\operatorname{supp} = \tfrac{3}{5} = 0.6$.
- $\{\text{Чипси}, \text{Пиво}\}$ — у $t_2, t_4, t_5$: $\operatorname{supp} = \tfrac{3}{5} = 0.6$.

**Правило $\{\text{Чипси}\} \Rightarrow \{\text{Пиво}\}$:**

$$ \operatorname{conf} = \frac{\operatorname{supp}(\{\text{Чипси}, \text{Пиво}\})}{\operatorname{supp}(\{\text{Чипси}\})}
= \frac{0.6}{0.8} = 0.75, \qquad
\operatorname{lift} = \frac{0.75}{\operatorname{supp}(\{\text{Пиво}\})} = \frac{0.75}{0.6} = 1.25, $$
$$ \operatorname{conv} = \frac{1 - \operatorname{supp}(\{\text{Пиво}\})}{1 - \operatorname{conf}} = \frac{1 - 0.6}{1 - 0.75} = \frac{0.4}{0.25} = 1.6. $$

**Правило $\{\text{Пиво}\} \Rightarrow \{\text{Чипси}\}$** (той самий набір, інший
напрямок):

$$ \operatorname{conf} = \frac{0.6}{0.6} = 1.0, \qquad
\operatorname{lift} = \frac{1.0}{0.8} = 1.25, \qquad
\operatorname{conv} = \frac{1 - 0.8}{1 - 1.0} \to \infty. $$

Підйом обох напрямків **однаковий** ($1.25$), бо симетричний; достовірність —
різна ($0.75$ проти $1.0$): усі покупці пива беруть чипси, але не навпаки.
Переконливість напрямку «Пиво $\Rightarrow$ Чипси» нескінченна — у цій базі
правило без винятків.

**Правило $\{\text{Кола}\} \Rightarrow \{\text{Чипси}\}$:**

$$ \operatorname{conf} = \frac{\operatorname{supp}(\{\text{Кола}, \text{Чипси}\})}{\operatorname{supp}(\{\text{Кола}\})}
= \frac{0.6}{0.8} = 0.75, \qquad
\operatorname{lift} = \frac{0.75}{0.8} = 0.9375 < 1, $$
$$ \operatorname{conv} = \frac{1 - 0.8}{1 - 0.75} = \frac{0.2}{0.25} = 0.8 < 1. $$

Достовірність висока ($0.75$), але підйом **менший за одиницю**: кола й чипси
з'являються разом навіть трохи рідше, ніж за незалежності (обидва просто дуже
поширені). Це правило **оманливо-достовірне** — його відкидають за підйомом.

**Відповідь:** $\operatorname{supp}(\{\text{Кола}\}) = \operatorname{supp}(\{\text{Чипси}\}) = 0.8$,
$\operatorname{supp}(\{\text{Пиво}\}) = 0.6$,
$\operatorname{supp}(\{\text{Кола}, \text{Чипси}\}) = \operatorname{supp}(\{\text{Чипси}, \text{Пиво}\}) = 0.6$;
$\{\text{Чипси}\} \Rightarrow \{\text{Пиво}\}$: $\operatorname{conf} = 0.75$, $\operatorname{lift} = 1.25$, $\operatorname{conv} = 1.6$;
$\{\text{Пиво}\} \Rightarrow \{\text{Чипси}\}$: $\operatorname{conf} = 1.0$, $\operatorname{lift} = 1.25$, $\operatorname{conv} = \infty$;
$\{\text{Кола}\} \Rightarrow \{\text{Чипси}\}$: $\operatorname{conf} = 0.75$, $\operatorname{lift} = 0.9375$, $\operatorname{conv} = 0.8$.

## Задача 2. Apriori «руками»

**Дано** транзакційну базу фруктової лавки ($N = 6$):

| Транзакція | Елементи |
|:--:|---|
| $t_1$ | Яблуко, Банан |
| $t_2$ | Яблуко, Банан, Виноград |
| $t_3$ | Яблуко, Виноград |
| $t_4$ | Банан, Виноград |
| $t_5$ | Яблуко, Банан, Виноград, Апельсин |
| $t_6$ | Банан, Апельсин |

**Знайти** всі часті 1- та 2-набори за $s_{\min} = 0.5$ (лічильник $\ge 3$) і
згенерувати з них правила з достовірністю $\ge c_{\min} = 0.7$.

**Розв'язання. Крок 1 — часті 1-набори.**

| 1-набір | Лічильник | Підтримка | Частий? |
|---|:--:|:--:|:--:|
| $\{\text{Яблуко}\}$ | 4 | $0.67$ | так |
| $\{\text{Банан}\}$ | 5 | $0.83$ | так |
| $\{\text{Виноград}\}$ | 4 | $0.67$ | так |
| $\{\text{Апельсин}\}$ | 2 | $0.33$ | **ні** |

Апельсин відпадає (і не з'явиться в жодному кандидаті).

**Крок 2 — часті 2-набори.** З'єднання трьох частих 1-наборів дає $\binom{3}{2} = 3$
кандидати; відсів нікого не викидає (усі 1-підмножини часті). Рахуємо:

| 2-набір | Транзакції | Лічильник | Підтримка | Частий? |
|---|---|:--:|:--:|:--:|
| $\{\text{Яблуко}, \text{Банан}\}$ | $t_1, t_2, t_5$ | 3 | $0.5$ | так |
| $\{\text{Яблуко}, \text{Виноград}\}$ | $t_2, t_3, t_5$ | 3 | $0.5$ | так |
| $\{\text{Банан}, \text{Виноград}\}$ | $t_2, t_4, t_5$ | 3 | $0.5$ | так |

Усі три часті. Єдиний кандидат-трійка $\{\text{Яблуко}, \text{Банан}, \text{Виноград}\}$
(усі його пари часті, тож відсів його лишає) трапляється лише в $t_2, t_5$:
$\operatorname{supp} = \tfrac{2}{6} \approx 0.33 < 0.5$ — **нечастий**. Отже,
частих наборів розміру $\ge 3$ немає.

**Крок 3 — генерація правил** ($c_{\min} = 0.7$). З кожного частого 2-набору
виходить два правила; достовірність
$\operatorname{conf} = \operatorname{supp}(\text{пари})/\operatorname{supp}(\text{умови})$:

| Правило | $\operatorname{supp}(\text{умови})$ | $\operatorname{conf}$ | $\ge 0.7$? | $\operatorname{lift}$ |
|---|:--:|:--:|:--:|:--:|
| $\{\text{Яблуко}\} \Rightarrow \{\text{Банан}\}$ | $4/6$ | $0.75$ | так | $0.90$ |
| $\{\text{Банан}\} \Rightarrow \{\text{Яблуко}\}$ | $5/6$ | $0.60$ | **ні** | $0.90$ |
| $\{\text{Яблуко}\} \Rightarrow \{\text{Виноград}\}$ | $4/6$ | $0.75$ | так | $1.125$ |
| $\{\text{Виноград}\} \Rightarrow \{\text{Яблуко}\}$ | $4/6$ | $0.75$ | так | $1.125$ |
| $\{\text{Банан}\} \Rightarrow \{\text{Виноград}\}$ | $5/6$ | $0.60$ | **ні** | $0.90$ |
| $\{\text{Виноград}\} \Rightarrow \{\text{Банан}\}$ | $4/6$ | $0.75$ | так | $0.90$ |

Поріг достовірності проходять **чотири** правила. Правила з умовою «Банан»
($\operatorname{supp} = 5/6$) відпадають: банан надто поширений, тож частка його
співпокупців з іншим товаром мала.

**Відповідь:** часті 1-набори — $\{\text{Яблуко}\}, \{\text{Банан}\}, \{\text{Виноград}\}$;
часті 2-набори — $\{\text{Яблуко}, \text{Банан}\}, \{\text{Яблуко}, \text{Виноград}\}, \{\text{Банан}, \text{Виноград}\}$
(усі з $\operatorname{supp} = 0.5$); частих 3-наборів немає. Правила з
$\operatorname{conf} \ge 0.7$: $\{\text{Яблуко}\} \Rightarrow \{\text{Банан}\}$,
$\{\text{Яблуко}\} \Rightarrow \{\text{Виноград}\}$,
$\{\text{Виноград}\} \Rightarrow \{\text{Яблуко}\}$,
$\{\text{Виноград}\} \Rightarrow \{\text{Банан}\}$ (усі $\operatorname{conf} = 0.75$).

![Ґратка наборів фруктової лавки з відсіванням Apriori: усе з Апельсином відсіяно без підрахунку, а трійка Яблуко-Банан-Виноград нечаста](img/lab11_lattice.png)

## Задача 3. Eclat та відбір цікавих правил

**Дано** ту саму базу, що в Задачі 2. **Перевірити** результат Задачі 2
алгоритмом **Eclat** (через tid-множини) і **відібрати справді цікаві** правила
серед тих, що пройшли поріг достовірності, скориставшись підйомом і
переконливістю.

**Розв'язання. Вертикальний формат** (tid-множини):

$$ \operatorname{tid}(\text{Яблуко}) = \{1,2,3,5\}, \quad
\operatorname{tid}(\text{Банан}) = \{1,2,4,5,6\}, \quad
\operatorname{tid}(\text{Виноград}) = \{2,3,4,5\}. $$

Підтримку пар дістаємо **перетином**, не переглядаючи транзакцій:

$$ \operatorname{tid}(\text{Яблуко}) \cap \operatorname{tid}(\text{Виноград}) = \{2,3,5\} \ (|\cdot| = 3), \quad
\operatorname{tid}(\text{Яблуко}) \cap \operatorname{tid}(\text{Банан}) = \{1,2,5\} \ (3), $$
$$ \operatorname{tid}(\text{Банан}) \cap \operatorname{tid}(\text{Виноград}) = \{2,4,5\} \ (3). $$

Усі три пари мають лічильник $3$ — збіг із Задачею 2. Для трійки перетинаємо далі:

$$ \big(\operatorname{tid}(\text{Яблуко}) \cap \operatorname{tid}(\text{Виноград})\big) \cap \operatorname{tid}(\text{Банан}) = \{2,3,5\} \cap \{1,2,4,5,6\} = \{2,5\} \ (2 < 3), $$

тобто $\{\text{Яблуко}, \text{Банан}, \text{Виноград}\}$ нечастий — знову збіг.

**Відбір цікавих правил.** З чотирьох правил, що пройшли $c_{\min}$ (Задача 2),
залишаємо ті, де $\operatorname{lift} > 1$, і впорядковуємо за переконливістю:

| Правило | $\operatorname{conf}$ | $\operatorname{lift}$ | $\operatorname{conv}$ | Цікаве? |
|---|:--:|:--:|:--:|:--:|
| $\{\text{Яблуко}\} \Rightarrow \{\text{Виноград}\}$ | $0.75$ | $1.125$ | $1.33$ | так |
| $\{\text{Виноград}\} \Rightarrow \{\text{Яблуко}\}$ | $0.75$ | $1.125$ | $1.33$ | так |
| $\{\text{Яблуко}\} \Rightarrow \{\text{Банан}\}$ | $0.75$ | $0.90$ | $0.67$ | ні |
| $\{\text{Виноград}\} \Rightarrow \{\text{Банан}\}$ | $0.75$ | $0.90$ | $0.67$ | ні |

Хоча всі чотири мають однакову достовірність $0.75$, лише пара «Яблуко —
Виноград» має $\operatorname{lift} > 1$ і $\operatorname{conv} > 1$ — це справжній
позитивний зв'язок. Правила з наслідком «Банан» ($\operatorname{lift} = 0.9$) —
оманливо-достовірні через велику поширеність банана.

**Відповідь:** Eclat підтверджує часті набори Задачі 2; єдиний цікавий зв'язок —
взаємне притягання **Яблуко $\leftrightarrow$ Виноград** ($\operatorname{lift} = 1.125$,
$\operatorname{conv} = 1.33$).

![Граф правил Задачі 3: цікавий взаємний зв'язок Яблуко-Виноград (підйом 1.125) та оманливо-достовірні ребра в Банан (підйом 0.9)](img/lab11_rule_graph.png)

> **Зв'язок із домашнім завданням.** Саме ці кроки — прочитати транзакції,
> порахувати підтримку наборів, відсіяти нечасті за $s_{\min}$, згенерувати
> правила й відібрати цікаві за $c_{\min}$, підйомом і переконливістю —
> виконуватиме ваша програма для довільного файлу транзакцій ([4task.md](4task.md)).
> Задача 2 — зручний **тест**: подайте ці шість транзакцій на вхід за
> $s_{\min} = 0.5$, $c_{\min} = 0.7$ й переконайтесь, що програма повертає ті
> самі три часті 2-набори та чотири правила.