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

Ці задачі розбирають **в аудиторії «руками»**. Вони показують ті самі кроки, які
потім автоматизує домашня програма ([4task.md](4task.md)). Теорія й псевдокод — у
[методичних вказівках](2method.md). Щоб побачити, що FP-Growth дає **той самий**
результат, що й Apriori, ми беремо **ту саму базу**, на якій виконували Apriori у
[Задачі 2 Лабораторної 11](../Laboratory11/3classroom.md), і наприкінці звіряємо
часті набори. Дані задач **відрізняються** від демонстраційного прикладу у
[2method.md](2method.md).

**Наскрізна база задач** — транзакційна база фруктової лавки ($N = 6$), та сама, що
в Задачі 2 Лабораторної 11:

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

Поріг усюди — $s_{\min} = 0.5$ (набір частий, коли він є принаймні у $3$ з $6$
транзакцій, лічильник $\ge 3$).

## Задача 1. Побудова FP-дерева

**Знайти** $F$-список, упорядковані транзакції, **FP-дерево** й **заголовну
таблицю** для бази фруктової лавки за $s_{\min} = 0.5$.

**Розв'язання. 1-й прохід — частоти елементів.**

| Елемент | Транзакції | Лічильник | Частий? |
|---|---|:--:|:--:|
| Яблуко | $t_1, t_2, t_3, t_5$ | 4 | так |
| Банан | $t_1, t_2, t_4, t_5, t_6$ | 5 | так |
| Виноград | $t_2, t_3, t_4, t_5$ | 4 | так |
| Апельсин | $t_5, t_6$ | 2 | **ні** |

Апельсин відпадає ($2 < 3$). Решту впорядковуємо за спаданням частоти; за
**рівних** частот (Яблуко й Виноград — обидва $4$) зберігаємо початковий порядок
елементів. **$F$-список:**

$$ \text{Банан}(5) \ \prec\ \text{Яблуко}(4) \ \prec\ \text{Виноград}(4). $$

**2-й прохід — упорядковані транзакції** (викидаємо Апельсин, сортуємо за
$F$-списком):

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

**Вставлення шляхів.** $t_1$ створює `Банан→Яблуко`. $t_2$ подовжує його до
`Банан→Яблуко→Виноград`. $t_3$ починається з **Яблуко** (не з Банан) — спільного
префікса немає, з'являється **нова гілка** `Яблуко→Виноград` під коренем. $t_4$
ділить корінь-вузол Банан і додає під ним `Виноград`. $t_5$ лягає вздовж наявної
гілки `Банан→Яблуко→Виноград`, нарощуючи лічильники. $t_6$ — лише Банан. Остаточне
**FP-дерево**:

```text
null
├─ Банан:5
│  ├─ Яблуко:3
│  │  └─ Виноград:2
│  └─ Виноград:1
└─ Яблуко:1
   └─ Виноград:1
```

![FP-дерево бази фруктової лавки: вузли «елемент: лічильник» від кореня null](img/lab12_fptree.png)

**Заголовна таблиця** (частота + вузли за зв'язками):

| Елемент | Частота | Вузли дерева (за зв'язками) |
|---|:--:|---|
| Банан | 5 | Банан:5 |
| Яблуко | 4 | Яблуко:3 → Яблуко:1 |
| Виноград | 4 | Виноград:2 → Виноград:1 → Виноград:1 |

**Перевірка** (сума лічильників вузлів = частота): Яблуко $3 + 1 = 4$; Виноград
$2 + 1 + 1 = 4$; Банан $5$ — усе збігається з 1-м проходом.

**Відповідь:** $F$-список $\text{Банан}(5) \prec \text{Яблуко}(4) \prec \text{Виноград}(4)$;
FP-дерево наведено вище (шість вузлів проти $2+3+2+2+3+1 = 13$ входжень частих
елементів окремими шляхами — стиснення завдяки спільним префіксам).

## Задача 2. Умовна база образів та умовне FP-дерево

**Для елемента Виноград** (найрідший у $F$-списку — з нього починають видобуток)
побудувати **умовну базу образів** і **умовне FP-дерево**.

**Розв'язання.** За заголовною таблицею у Винограду **три** вузли; для кожного
беремо префіксний шлях від кореня (без самого Винограду) з лічильником цього
вузла:

- Виноград:2 — під `Банан→Яблуко`: шлях $(\text{Банан}, \text{Яблуко})$ з
  лічильником $2$;
- Виноград:1 — під `Банан`: шлях $(\text{Банан})$ з лічильником $1$;
- Виноград:1 — під `Яблуко` (гілка від кореня): шлях $(\text{Яблуко})$ з
  лічильником $1$.

**Умовна база образів Винограду:**

$$ (\text{Банан}, \text{Яблуко}):2, \qquad (\text{Банан}):1, \qquad (\text{Яблуко}):1. $$

**Частоти в цій базі:** Банан $= 2 + 1 = 3$, Яблуко $= 2 + 1 = 3$ — обидва часті
($\ge 3$), нічого не відкидаємо. Вставивши три шляхи (за порядком
$\text{Банан} \prec \text{Яблуко}$), дістаємо **умовне FP-дерево Винограду**:

```text
null
├─ Банан:3
│  └─ Яблуко:2
└─ Яблуко:1        (умовне дерево для Виноград)
```

![Умовна база образів та умовне FP-дерево елемента Виноград — розгалужене дерево](img/lab12_conditional.png)

Це дерево **не є** єдиним шляхом (Яблуко трапляється і під Банан, і під коренем),
тож із нього часті набори видобувають **рекурсивно** — знизу вгору за його
заголовною таблицею $[\text{Яблуко}(3), \text{Банан}(3)]$:

- **Яблуко** в умовному дереві Винограду: дає набір
  $\{\text{Яблуко}, \text{Виноград}\}$ з підтримкою $3$. Його умовна база тут —
  $(\text{Банан}):2$; Банан має лічильник $2 < 3$, відпадає — далі порожньо.
- **Банан** в умовному дереві Винограду: дає набір
  $\{\text{Банан}, \text{Виноград}\}$ з підтримкою $3$. Банан — під коренем, умовна
  база порожня.

**Відповідь:** умовна база образів Винограду —
$(\text{Банан}, \text{Яблуко}):2,\ (\text{Банан}):1,\ (\text{Яблуко}):1$; умовне
FP-дерево — гілки `Банан:3→Яблуко:2` та `Яблуко:1`. З нього виходять часті набори
$\{\text{Яблуко}, \text{Виноград}\}:3$ і $\{\text{Банан}, \text{Виноград}\}:3$.
Набір $\{\text{Банан}, \text{Яблуко}, \text{Виноград}\}$ **не** частий: Банан
всередині під-бази Яблуко має лічильник лише $2$.

## Задача 3. Повний видобуток і звірка з Apriori

**Видобути всі часті набори** алгоритмом FP-Growth і **звірити** їх із результатом
Apriori із [Задачі 2 Лабораторної 11](../Laboratory11/3classroom.md) (мають
збігтися).

**Розв'язання.** Обходимо заголовну таблицю Задачі 1 **знизу вгору**: Виноград,
Яблуко, Банан.

- **Виноград** (Задача 2): $\{\text{Виноград}\}:4$, а з умовного дерева —
  $\{\text{Яблуко}, \text{Виноград}\}:3$ і $\{\text{Банан}, \text{Виноград}\}:3$.
- **Яблуко**: $\{\text{Яблуко}\}:4$. Умовна база образів — $(\text{Банан}):3$
  (у Яблука два вузли: `Яблуко:3` під Банан дає $(\text{Банан}):3$; `Яблуко:1` під
  коренем дає порожній шлях). Банан частий ($3 \ge 3$), умовне дерево — єдиний
  вузол `Банан:3`, звідки $\{\text{Банан}, \text{Яблуко}\}:3$.
- **Банан**: $\{\text{Банан}\}:5$; найчастіший, завжди під коренем — умовна база
  порожня.

**Усі часті набори** й **звірка з Apriori** (Задача 2 Лабораторної 11):

| Частий набір | Лічильник | Підтримка | Звідки у FP-Growth | Apriori (Л11) |
|---|:--:|:--:|---|:--:|
| $\{\text{Банан}\}$ | 5 | $0.83$ | заголовна таблиця | так |
| $\{\text{Яблуко}\}$ | 4 | $0.67$ | заголовна таблиця | так |
| $\{\text{Виноград}\}$ | 4 | $0.67$ | заголовна таблиця | так |
| $\{\text{Банан}, \text{Яблуко}\}$ | 3 | $0.5$ | умовне дерево Яблуко | так |
| $\{\text{Банан}, \text{Виноград}\}$ | 3 | $0.5$ | умовне дерево Виноград | так |
| $\{\text{Яблуко}, \text{Виноград}\}$ | 3 | $0.5$ | умовне дерево Виноград | так |

Частих наборів розміру $\ge 3$ немає: єдиний кандидат-трійка
$\{\text{Яблуко}, \text{Банан}, \text{Виноград}\}$ трапляється лише в $t_2, t_5$
(підтримка $2/6 \approx 0.33 < 0.5$), і FP-Growth його **не** породив — саме тому,
що Банан відсіявся всередині умовної під-бази (Задача 2).

**Відповідь:** FP-Growth знаходить три часті 1-набори
($\{\text{Банан}\}, \{\text{Яблуко}\}, \{\text{Виноград}\}$) і три часті 2-набори
($\{\text{Банан}, \text{Яблуко}\}, \{\text{Банан}, \text{Виноград}\}, \{\text{Яблуко}, \text{Виноград}\}$,
усі з підтримкою $0.5$); частих наборів розміру $\ge 3$ немає. Це **точно** той
самий список, що дав Apriori у Задачі 2 Лабораторної 11 — але **без генерації
кандидатів** і лише за **два проходи** по базі. З цих частих 2-наборів далі
генерують правила так само, як у Задачі 2 Лабораторної 11 (з
$c_{\min} = 0.7$ проходять чотири правила з достовірністю $0.75$).

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