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

Джерело завдання. Завдання доповнює матеріали курсу (у вихідному архіві домашнє завдання для теми 11 відсутнє). Постановку сформульовано природно для теми — реалізація алгоритму Apriori з генерацією правил. Готового коду тут немає — це індивідуальне завдання; техніку обчислень показано на інших даних у 2method.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 за $s_{\min} = 0.5$, $c_{\min} = 0.7$ — очікувано три часті 2-набори ($\{\text{Яблуко},\text{Банан}\}$, $\{\text{Яблуко},\text{Виноград}\}$, $\{\text{Банан},\text{Виноград}\}$, усі з підтримкою $0.5$) і чотири правила з достовірністю $0.75$. Значення підйому звірте з Задачею 3 (пара «Яблуко — Виноград»: $\operatorname{lift} = 1.125$).
• Оформлення звіту — за 5report.md; перелік запитань до захисту — у 6questions.md.

Laboratory/Laboratory11/4task.md · 6.4 KB · updated 2026-08-04 23:32