# 1. Мета роботи

**Навчитися шукати часті набори алгоритмом FP-Growth: будувати FP-дерево
транзакційної бази за два проходи, утворювати умовну базу образів та умовне
FP-дерево для окремого елемента й рекурсивно видобувати всі часті набори без
генерації кандидатів; реалізувати FP-Growth програмою, що читає транзакції з файлу,
і звірити її результат із алгоритмом Apriori.**

Виконавши роботу, студент повинен уміти:

- **упорядковувати елементи за частотою** ($F$-список) і відкидати нечасті ще до
  побудови дерева, спираючись на властивість Apriori (антимонотонність);
- **будувати FP-дерево** за два проходи: 1-й — частоти елементів; 2-й — вставлення
  транзакцій як шляхів зі спільними префіксами; заповнювати **заголовну таблицю**
  зі зв'язками між вузлами (node-links);
- **утворювати умовну базу образів** елемента (префіксні шляхи його вузлів із
  їхніми лічильниками) та **умовне FP-дерево** (лишивши елементи, часті вже в цій
  базі);
- **рекурсивно видобувати часті набори** знизу вгору заголовною таблицею;
  користуватися оптимізацією «єдиний шлях» (усі комбінації вузлів);
- **правильно застосовувати поріг $s_{\min}$ наново** всередині кожного умовного
  дерева й розуміти, чому саме це відсіює несправжні набори;
- **звіряти** результат FP-Growth із Apriori/Eclat (мають збігатися) і **порівнювати**
  три алгоритми за генерацією кандидатів, проходами по базі та пам'яттю;
- **реалізувати** FP-Growth у вигляді програми, що читає транзакції з файлу
  CSV/тексту, і за потреби доповнити її генерацією асоціативних правил та
  порівнянням із Apriori.

Робота закріплює [Лекцію 12 — Алгоритм FP-Growth](../../Lectures/DA-L12.md) і
спирається на [Лабораторну 11](../Laboratory11/main.md) (Apriori та Eclat). Уся
потрібна теорія повторена в самодостатньому вигляді в
[методичних вказівках](2method.md).