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

Джерело завдання. Завдання доповнює матеріали курсу (у вихідному архіві домашнє завдання для теми 12 відсутнє). Постановку сформульовано природно для теми — реалізація алгоритму FP-Growth. Готового коду тут немає — це індивідуальне завдання; техніку обчислень показано на інших даних у 2method.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) алгоритм Apriori і на одній і тій самій базі звірити множини частих наборів обох алгоритмів — вони мають повністю збігатися. Додатково виміряти й порівняти час роботи FP-Growth і Apriori на дедалі більших базах (напр., випадково згенерованих транзакціях), побудувати таблицю або графік «час vs розмір бази» й прокоментувати, на яких даних (щільних/розріджених) який алгоритм швидший.
9. Дослідити пороги. Запустити FP-Growth на кількох порогах $s_{\min}$ для однієї бази, показати, як змінюється кількість частих наборів і розмір FP-дерева, і прокоментувати компроміс (низький поріг — лавина наборів; високий — втрата рідкісних, але цінних).
10. Передбачити перевірку коректності вводу (порожній файл, некоректний поріг поза $[0,1]$, рядки без елементів, дублікати елементів у рядку) з інформативним повідомленням.

Що здавати #

• Вихідний код програми (з коротким README: як запустити, формат входу, як задають пороги).
• Приклад запуску на тестовому файлі. Обов’язково перевірте програму на даних Задачі 1–3 (фруктова лавка) за $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; перелік запитань до захисту — у 6questions.md.

Laboratory/Laboratory12/4task.md · 7.6 KB · updated 2026-08-05 08:37