# Лабораторна робота 12. Алгоритм FP-Growth. Пошук частих наборів без генерації кандидатів

> Дванадцята лабораторна робота курсу **«Аналітика даних»**. Спершу **в
> аудиторії** ви будуєте «руками» **FP-дерево** для транзакційної бази,
> утворюєте умовну базу образів та умовне FP-дерево для окремого елемента й
> **видобуваєте** часті набори, звіряючи їх із результатом Apriori з
> [Лабораторної 11](../Laboratory11/main.md). Потім **удома** реалізуєте
> **програму** FP-Growth, що будує дерево й рекурсивно видобуває часті набори з
> файлу транзакцій. Робота закріплює [Лекцію 12](../../Lectures/DA-L12.md).

## Коротко про роботу

| | |
|---|---|
| **Тема** | Алгоритм FP-Growth; FP-дерево; умовна база образів; умовне FP-дерево; видобуток без кандидатів |
| **Передумова** | [Лекція 12. Алгоритм FP-Growth](../../Lectures/DA-L12.md); [Лабораторна 11](../Laboratory11/main.md) |
| **Аудиторна частина** | Побудова FP-дерева та видобуток частих наборів «руками» (з розв'язаннями) |
| **Домашня частина** | Програма: будує FP-дерево з файлу транзакцій і рекурсивно видобуває часті набори |
| **Оцінювання** | три рівні: базовий **60–74** / середній **75–89** / високий **90–100** |

## Зміст

| № | Частина | Файл |
|:--:|---|---|
| 1 | Мета роботи | [1purpose.md](1purpose.md) |
| 2 | Методичні вказівки (теорія + демонстраційний приклад) | [2method.md](2method.md) |
| 3 | Аудиторні задачі з розв'язаннями | [3classroom.md](3classroom.md) |
| 4 | Домашнє завдання (програма) | [4task.md](4task.md) |
| 5 | Зміст звіту | [5report.md](5report.md) |
| 6 | Контрольні запитання | [6questions.md](6questions.md) |

## Домовленості

- **Дві частини.** Аудиторні задачі ([3classroom.md](3classroom.md)) розбирають
  спільно «руками» — з них ви розумієте, *що саме* будує й обходить програма.
  Домашнє завдання ([4task.md](4task.md)) — самостійна реалізація FP-Growth у коді.
- **Той самий результат, що й Apriori.** FP-Growth знаходить **ті самі** часті
  набори, що Apriori та Eclat, але **без генерації кандидатів** і лише за **два
  проходи** по базі. Тому в аудиторній частині ми беремо базу з
  [Лабораторної 11](../Laboratory11/3classroom.md) і **звіряємо** результат —
  він має збігтися.
- **Порядок за спаданням частоти.** Елементи в кожній транзакції перед вставленням
  у дерево сортують за **$F$-списком** (спадання частоти; за рівних частот —
  сталий початковий порядок). Це обов'язкова умова стиснення й коректності.
- **Підтримка — частка, не лічильник.**
  $\operatorname{supp}(X) = \dfrac{|\{t : X \subseteq t\}|}{N}$; порівнюйте з порогом
  частку (або еквівалентний лічильник $s_{\min}\cdot N$). У звіті завжди зазначайте,
  який $s_{\min}$ узято.
- **Мова програмування — на вибір.** Стандартні бібліотеки для читання файлів
  дозволені; готові реалізації FP-Growth (напр. `mlxtend`, Spark) можна брати
  **лише для перевірки** власної.

## Підсумок

FP-Growth — третій і найпоширеніший на практиці метод пошуку частих наборів.
Замість «породити кандидатів — перевірити базою» він **стискає базу у FP-дерево**
за два проходи, а тоді видобуває часті набори прямо з дерева, зовсім **не
породжуючи кандидатів**: для кожного елемента (знизу вгору заголовною таблицею)
будує **умовну базу образів** та **умовне FP-дерево** й рекурсивно заглиблюється.
У цій роботі ви навчитеся будувати FP-дерево «руками», утворювати умовні дерева й
видобувати часті набори, а тоді автоматизуєте весь процес програмою та
**порівняєте** її результат і швидкодію з Apriori з [Лабораторної
11](../Laboratory11/main.md). Це завершальний, найпродуктивніший метод змістового
модуля про асоціативний аналіз і типовий приклад **навчання без учителя**, що
доповнює задачі кластеризації з [Лекцій 9](../../Lectures/DA-L09.md)–[10](../../Lectures/DA-L10.md).