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

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

## 2.1 Транзакційна база та часті набори (нагадування)

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

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

Зручно тримати **лічильник** $|\{t : X \subseteq t\}|$ і порівнювати його з
$s_{\min}\cdot N$. Пошук асоціативних правил зводиться до пошуку **всіх частих
наборів** (решта — генерація правил — дешева); саме цю важку частину й розв'язує
FP-Growth.

## 2.2 Навіщо FP-Growth

**Apriori** (Лабораторна 11) породжує **кандидатів** і **сканує базу на кожному
рівні** — на щільних базах кандидатів стає надто багато, а повторні проходи
дорогі. **FP-Growth** уникає обох вад:

> **Ідея FP-Growth.** Стиснути всю базу в компактне **FP-дерево** за **два
> проходи**, а тоді видобувати часті набори **прямо з дерева, не породжуючи
> кандидатів**.

## 2.3 FP-дерево та його побудова

**FP-дерево** — префіксне дерево транзакцій. Корінь — `null`; кожен інший вузол
зберігає **елемент** і **лічильник** (скільки транзакцій проходить крізь нього);
транзакція, обмежена частими елементами й упорядкована за спільним порядком, —
**шлях** від кореня. Вузли того самого елемента сполучено у список **зв'язків між
вузлами** (node-links).

Дерево будують за **два проходи**:

1. **1-й прохід — частоти й порядок.** Порахувати підтримку кожного елемента,
   **відкинути нечасті**, а решту впорядкувати **за спаданням частоти**. Цей
   упорядкований список частих елементів — **$F$-список**; за рівних частот
   зберігають сталий (початковий) порядок.
2. **2-й прохід — вставлення.** Для кожної транзакції лишити часті елементи,
   відсортувати за $F$-списком і вставити як шлях: спільний **префікс** нарощує
   лічильники наявних вузлів, розбіжний «хвіст» додає нові.

**Заголовна таблиця** зберігає для кожного частого елемента його **сумарну
частоту** й **покажчик на перший вузол**; усі вузли елемента сполучено
node-links. Найпоширеніші елементи стоять близько до кореня — звідси стиснення.

## 2.4 Умовна база образів та умовне FP-дерево

Видобуток іде **знизу вгору** заголовною таблицею (від **найрідшого** елемента).

- **Умовна база образів** (англ. *conditional pattern base*) елемента $i$ —
  множина **префіксних шляхів** усіх вузлів $i$: для кожного вузла беруть шлях від
  кореня **до нього, без самого $i$**, із лічильником **цього вузла $i$**.
- **Умовне FP-дерево** елемента $i$ — FP-дерево, побудоване з його умовної бази
  образів, у якому лишено **лише елементи, часті вже в межах цієї бази** (їхня
  сумарна частота $\ge s_{\min} N$).

## 2.5 Рекурсивний видобуток (FP-Growth)

```text
FP-Growth(Дерево, α):
  якщо Дерево — єдиний шлях P:
    для кожної непорожньої підмножини β вузлів шляху P:
       вивести  β ∪ α  з підтримкою = найменший лічильник вузлів у β
  інакше:
    для кожного елемента i заголовної таблиці (знизу вгору):
       β <- α ∪ { i }
       вивести β з підтримкою = сумарний лічильник i
       побудувати умовну базу образів i та умовне FP-дерево Дерево_i
       якщо Дерево_i не порожнє:
          FP-Growth(Дерево_i, β)
```

Спершу викликають `FP-Growth(усе_дерево, ∅)`. Гілка «**єдиний шлях**» — важлива
оптимізація: із ланцюжка одразу виписують **усі комбінації** його вузлів
(підтримка комбінації — найменший лічильник). Поріг $s_{\min}$ **застосовують
наново** в кожному умовному дереві — це відсіює несправжні набори.

## 2.6 Apriori / Eclat / FP-Growth

Усі три знаходять **той самий** набір частих наборів; різниця — у способі:

| Ознака | Apriori | Eclat | FP-Growth |
|---|---|---|---|
| Генерація кандидатів | так | немає | **немає** |
| Проходів по базі | $\sim m$ (по рівнях) | $\sim 1$ | **2** |
| Пам'ять | мала | tid-множини | FP-дерево |
| Найкращий на | малих/розріджених | розріджених | **щільних** |

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

Розгляньмо ту саму базу невеликої чайної крамниці, що й у
[Лабораторній 11](../Laboratory11/2method.md) ($N = 5$) над елементами
$I = \{\text{Чай}, \text{Цукор}, \text{Лимон}, \text{Мед}\}$ — і застосуймо до неї
FP-Growth за тим самим порогом $s_{\min} = 0.4$ (лічильник $\ge 2$):

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

**(а) 1-й прохід — $F$-список.** Частоти: Чай $4$, Цукор $3$, Лимон $3$, Мед $2$ —
усі часті ($\ge 2$). За спаданням частоти (рівні Цукор і Лимон — у початковому
порядку):

$$ \text{Чай}(4) \prec \text{Цукор}(3) \prec \text{Лимон}(3) \prec \text{Мед}(2). $$

**(б) 2-й прохід — упорядковані транзакції й дерево.**

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

Вставивши шляхи (транзакція $t_5$ починається з Лимон і дає **нову гілку** під
коренем), дістаємо:

```text
null
├─ Чай:4
│  ├─ Цукор:3
│  │  ├─ Лимон:1
│  │  └─ Мед:1
│  └─ Лимон:1
└─ Лимон:1
   └─ Мед:1
```

![FP-дерево демонстраційної бази чайної крамниці за F-списком](img/lab12_demo_tree.png)

Заголовна таблиця: Чай($4$): `Чай:4`; Цукор($3$): `Цукор:3`; Лимон($3$):
`Лимон:1 → Лимон:1 → Лимон:1`; Мед($2$): `Мед:1 → Мед:1`. Перевірка сум: Лимон
$1+1+1 = 3$, Мед $1+1 = 2$ — збігається з частотами.

**(в) Видобуток (знизу вгору: Мед, Лимон, Цукор, Чай).**

- **Мед** — $\{\text{Мед}\}:2$. Умовна база образів:
  $(\text{Чай}, \text{Цукор}):1$ і $(\text{Лимон}):1$. Частоти в базі: Чай $1$,
  Цукор $1$, Лимон $1$ — **усі $< 2$**, тож умовне дерево порожнє. Жодної частої
  пари з Мед немає.
- **Лимон** — $\{\text{Лимон}\}:3$. Умовна база: $(\text{Чай}, \text{Цукор}):1$ і
  $(\text{Чай}):1$. Частоти: Чай $2$, Цукор $1$ — Цукор відпадає. Умовне дерево —
  єдиний вузол `Чай:2`, звідки $\{\text{Чай}, \text{Лимон}\}:2$.
- **Цукор** — $\{\text{Цукор}\}:3$. Умовна база: $(\text{Чай}):3$; умовне дерево
  `Чай:3`, звідки $\{\text{Чай}, \text{Цукор}\}:3$.
- **Чай** — $\{\text{Чай}\}:4$; під коренем, умовна база порожня.

**Часті набори:** 1-набори — Чай($4$), Цукор($3$), Лимон($3$), Мед($2$); 2-набори
— $\{\text{Чай}, \text{Цукор}\}$($3$) і $\{\text{Чай}, \text{Лимон}\}$($2$); частих
наборів розміру $\ge 3$ немає. Це **точно** той самий результат, що дав Apriori на
цій базі в [Лабораторній 11 (§2.8)](../Laboratory11/2method.md) — але **без
кандидатів**.

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

- Спершу зафіксуйте **поріг** $s_{\min}$ і переведіть його в **лічильник**
  $s_{\min}\cdot N$.
- 1-й прохід: порахуйте частоти, **відкиньте нечасті**, складіть **$F$-список** (за
  спаданням частоти; рівні — у сталому порядку).
- 2-й прохід: кожну транзакцію **відсортуйте за $F$-списком** перед вставленням —
  інакше спільні префікси не зіллються.
- Перевіряйте дерево: **сума лічильників** вузлів елемента $=$ його частота.
- Видобуток ведіть **знизу вгору** заголовною таблицею; для кожного елемента —
  умовна база образів $\to$ умовне дерево $\to$ рекурсія; єдиний шлях — одразу всі
  комбінації.
- Поріг $s_{\min}$ **перевіряйте наново** в кожній умовній базі.
- Наприкінці **звірте** список частих наборів із Apriori/Eclat — вони мають
  збігтися.