# 4. Домашнє завдання (написання програми)

> **Джерело завдання.** Завдання **доповнює матеріали курсу** (у вихідному архіві
> домашнє завдання для теми 12 відсутнє). Постановку сформульовано природно для
> теми — реалізація алгоритму FP-Growth. Готового коду тут **немає** — це
> індивідуальне завдання; техніку обчислень показано на інших даних у
> [2method.md](2method.md) та [3classroom.md](3classroom.md).

## Постановка

Реалізувати алгоритм **FP-Growth**: побудова **FP-дерева** й **рекурсивний
видобуток** частих наборів. На вхід — транзакції з файлу (CSV/текст, одна
транзакція на рядок). Вивести **всі часті набори** з підтримкою не меншою за
заданий поріг.

## Вхід і вихід

- **Вхід:** шлях до файлу транзакцій — по одній транзакції на рядок, елементи
  розділені комою (або пробілом). Приклад рядка: `Яблуко,Банан,Виноград`. Порядок
  елементів у рядку несуттєвий; повтори в межах транзакції ігнорують. Також на вхід
  подають **мінімальну підтримку** $s_{\min}$ (аргумент командного рядка, параметр
  або запит); для середнього рівня — ще й **мінімальну достовірність** $c_{\min}$.
- **Вихід:** щонайменше — перелік **частих наборів** із їхньою підтримкою,
  згрупований за розміром. Формат виводу (консоль/файл) — на розсуд студента;
  підтримку подавайте як частку (можна й у відсотках), числа округлюйте розумно
  (напр., 3–4 значущі цифри).

## Рівні складності

Оцінка відповідає найвищому **повністю й правильно** виконаному рівню.

### Базовий рівень — 60–74 балів

1. Прочитати транзакції з файлу; побудувати множину елементів $I$ і кількість
   транзакцій $N$.
2. **1-й прохід:** порахувати частоти елементів, відкинути нечасті
   ($< s_{\min} \cdot N$) і скласти **$F$-список** (за спаданням частоти; за рівних
   частот — сталий порядок).
3. **2-й прохід:** для кожної транзакції лишити часті елементи, відсортувати за
   $F$-списком і вставити як шлях у **FP-дерево**; вести **лічильники** у вузлах і
   **заголовну таблицю** зі зв'язками між вузлами (node-links).
4. **Видобути всі часті набори** рекурсивним FP-Growth (умовна база образів $\to$
   умовне FP-дерево $\to$ рекурсія; поріг $s_{\min}$ застосовувати наново в кожній
   умовній базі) і вивести їх згруповано за розміром із підтримкою.

### Середній рівень — 75–89 балів

Додатково до базового:

5. **Згенерувати асоціативні правила** з кожного частого набору: розбити набір $Z$
   на $X$ і $Y = Z \setminus X$ усіма способами й лишити правила з
   $\operatorname{conf} \ge c_{\min}$ (усі потрібні підтримки вже пораховано на
   етапі видобутку).
6. Для кожного правила вивести **підтримку та достовірність**.
7. Коректно опрацьовувати файл із **різною довжиною** транзакцій, зайвими
   пробілами та порожніми рядками; пороги $s_{\min}$, $c_{\min}$ задавати ззовні.

### Високий рівень — 90–100 балів

Додатково до середнього виконати **щонайменше один** із пунктів (краще — обидва):

8. **Порівняти з Apriori.** Реалізувати (або взяти свою реалізацію з
   [Лабораторної 11](../Laboratory11/4task.md)) алгоритм **Apriori** і на одній і
   тій самій базі **звірити** множини частих наборів обох алгоритмів — вони мають
   **повністю збігатися**. Додатково **виміряти й порівняти час** роботи FP-Growth
   і Apriori на дедалі більших базах (напр., випадково згенерованих транзакціях),
   побудувати таблицю або графік «час vs розмір бази» й прокоментувати, на яких
   даних (щільних/розріджених) який алгоритм швидший.
9. **Дослідити пороги.** Запустити FP-Growth на **кількох порогах** $s_{\min}$ для
   однієї бази, показати, як змінюється кількість частих наборів і розмір
   FP-дерева, і прокоментувати компроміс (низький поріг — лавина наборів; високий —
   втрата рідкісних, але цінних).
10. Передбачити **перевірку коректності** вводу (порожній файл, некоректний поріг
    поза $[0,1]$, рядки без елементів, дублікати елементів у рядку) з інформативним
    повідомленням.

## Що здавати

- Вихідний код програми (з коротким `README`: як запустити, формат входу, як
  задають пороги).
- Приклад запуску на **тестовому** файлі. Обов'язково перевірте програму на даних
  [Задачі 1–3](3classroom.md) (фруктова лавка) за $s_{\min} = 0.5$ — очікувано три
  часті 1-набори ($\{\text{Банан}\}$ з підтримкою $0.83$, $\{\text{Яблуко}\}$ і
  $\{\text{Виноград}\}$ з підтримкою $0.67$) і три часті 2-набори
  ($\{\text{Банан},\text{Яблуко}\}$, $\{\text{Банан},\text{Виноград}\}$,
  $\{\text{Яблуко},\text{Виноград}\}$, усі з підтримкою $0.5$); частих наборів
  розміру $\ge 3$ немає. Для високого рівня — звірте цей результат зі своєю
  реалізацією Apriori (мають збігтися).
- Оформлення звіту — за [5report.md](5report.md); перелік запитань до захисту — у
  [6questions.md](6questions.md).