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

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

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

Реалізувати алгоритм **Apriori**. На вхід подається набір транзакцій (CSV/текст,
одна транзакція на рядок). Програма знаходить усі **часті набори** з підтримкою не
меншою за заданий поріг, генерує **асоціативні правила** з достовірністю не меншою
за заданий поріг і виводить їх разом із **підтримкою, достовірністю та підйомом**.

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

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

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

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

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

1. Прочитати транзакції з файлу; побудувати множину елементів $I$ і кількість
   транзакцій $N$.
2. Знайти **всі часті набори** з підтримкою $\ge s_{\min}$ алгоритмом Apriori:
   часті 1-набори $\to$ генерація кандидатів $\to$ підрахунок підтримки $\to$
   часті $k$-набори, доки з'являються нові.
3. Реалізувати **відсівання кандидатів** за властивістю Apriori (кандидат із
   нечастою $(k{-}1)$-підмножиною не рахується).
4. Вивести часті набори згруповано за розміром із їхньою підтримкою.

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

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

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

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

Додатково до середнього:

8. Обчислювати й виводити для кожного правила ще й **підйом** і
   **переконливість**; впорядкувати «цікаві» правила (з $\operatorname{lift} > 1$)
   за спаданням підйому (або переконливості).
9. Реалізувати **Eclat** (через перетин tid-множин) як **альтернативний** пошук
   частих наборів і **порівняти** його результат із Apriori (мають збігатися) —
   або, як варіант, порівняти час роботи обох на більшій базі.
10. Передбачити **перевірку коректності** вводу (порожній файл, некоректні пороги
    поза $[0,1]$, рядки без елементів) з інформативним повідомленням.

## Що здавати

- Вихідний код програми (з коротким `README`: як запустити, формат входу, як
  задають пороги).
- Приклад запуску на **тестовому** файлі. Обов'язково перевірте програму на даних
  [Задачі 2](3classroom.md) за $s_{\min} = 0.5$, $c_{\min} = 0.7$ — очікувано
  три часті 2-набори ($\{\text{Яблуко},\text{Банан}\}$, $\{\text{Яблуко},\text{Виноград}\}$,
  $\{\text{Банан},\text{Виноград}\}$, усі з підтримкою $0.5$) і чотири правила з
  достовірністю $0.75$. Значення підйому звірте з
  [Задачею 3](3classroom.md) (пара «Яблуко — Виноград»: $\operatorname{lift} = 1.125$).
- Оформлення звіту — за [5report.md](5report.md); перелік запитань до захисту — у
  [6questions.md](6questions.md).