АД/Laboratory/Laboratory12/main
Raw

Лабораторна робота 12. Алгоритм FP-Growth. Пошук частих наборів без генерації кандидатів

Дванадцята лабораторна робота курсу «Аналітика даних». Спершу в аудиторії ви будуєте «руками» FP-дерево для транзакційної бази, утворюєте умовну базу образів та умовне FP-дерево для окремого елемента й видобуваєте часті набори, звіряючи їх із результатом Apriori з Лабораторної 11. Потім удома реалізуєте програму FP-Growth, що будує дерево й рекурсивно видобуває часті набори з файлу транзакцій. Робота закріплює Лекцію 12.

Коротко про роботу

Тема Алгоритм FP-Growth; FP-дерево; умовна база образів; умовне FP-дерево; видобуток без кандидатів
Передумова Лекція 12. Алгоритм FP-Growth; Лабораторна 11
Аудиторна частина Побудова FP-дерева та видобуток частих наборів «руками» (з розв’язаннями)
Домашня частина Програма: будує FP-дерево з файлу транзакцій і рекурсивно видобуває часті набори
Оцінювання три рівні: базовий 60–74 / середній 75–89 / високий 90–100

Зміст

№ Частина Файл
1 Мета роботи 1purpose.md
2 Методичні вказівки (теорія + демонстраційний приклад) 2method.md
3 Аудиторні задачі з розв’язаннями 3classroom.md
4 Домашнє завдання (програма) 4task.md
5 Зміст звіту 5report.md
6 Контрольні запитання 6questions.md

Домовленості

  • Дві частини. Аудиторні задачі (3classroom.md) розбирають спільно «руками» — з них ви розумієте, що саме будує й обходить програма. Домашнє завдання (4task.md) — самостійна реалізація FP-Growth у коді.
  • Той самий результат, що й Apriori. FP-Growth знаходить ті самі часті набори, що Apriori та Eclat, але без генерації кандидатів і лише за два проходи по базі. Тому в аудиторній частині ми беремо базу з Лабораторної 11 і звіряємо результат — він має збігтися.
  • Порядок за спаданням частоти. Елементи в кожній транзакції перед вставленням у дерево сортують за FF-списком (спадання частоти; за рівних частот — сталий початковий порядок). Це обов’язкова умова стиснення й коректності.
  • Підтримка — частка, не лічильник. supp⁡(X)=∣{t:X⊆t}∣N\operatorname{supp}(X) = \dfrac{|\{t : X \subseteq t\}|}{N}; порівнюйте з порогом частку (або еквівалентний лічильник smin⁡⋅Ns_{\min}\cdot N). У звіті завжди зазначайте, який smin⁡s_{\min} узято.
  • Мова програмування — на вибір. Стандартні бібліотеки для читання файлів дозволені; готові реалізації FP-Growth (напр. mlxtend, Spark) можна брати лише для перевірки власної.

Підсумок

FP-Growth — третій і найпоширеніший на практиці метод пошуку частих наборів. Замість «породити кандидатів — перевірити базою» він стискає базу у FP-дерево за два проходи, а тоді видобуває часті набори прямо з дерева, зовсім не породжуючи кандидатів: для кожного елемента (знизу вгору заголовною таблицею) будує умовну базу образів та умовне FP-дерево й рекурсивно заглиблюється. У цій роботі ви навчитеся будувати FP-дерево «руками», утворювати умовні дерева й видобувати часті набори, а тоді автоматизуєте весь процес програмою та порівняєте її результат і швидкодію з Apriori з Лабораторної 11. Це завершальний, найпродуктивніший метод змістового модуля про асоціативний аналіз і типовий приклад навчання без учителя, що доповнює задачі кластеризації з Лекцій 9–10.

Laboratory/Laboratory12/main.md · 5.8 KB · updated 2026-08-05 08:33