1. Мета роботи
Навчитися шукати часті набори алгоритмом FP-Growth: будувати FP-дерево транзакційної бази за два проходи, утворювати умовну базу образів та умовне FP-дерево для окремого елемента й рекурсивно видобувати всі часті набори без генерації кандидатів; реалізувати FP-Growth програмою, що читає транзакції з файлу, і звірити її результат із алгоритмом Apriori.
Виконавши роботу, студент повинен уміти:
- упорядковувати елементи за частотою (-список) і відкидати нечасті ще до побудови дерева, спираючись на властивість Apriori (антимонотонність);
- будувати FP-дерево за два проходи: 1-й — частоти елементів; 2-й — вставлення транзакцій як шляхів зі спільними префіксами; заповнювати заголовну таблицю зі зв’язками між вузлами (node-links);
- утворювати умовну базу образів елемента (префіксні шляхи його вузлів із їхніми лічильниками) та умовне FP-дерево (лишивши елементи, часті вже в цій базі);
- рекурсивно видобувати часті набори знизу вгору заголовною таблицею; користуватися оптимізацією «єдиний шлях» (усі комбінації вузлів);
- правильно застосовувати поріг наново всередині кожного умовного дерева й розуміти, чому саме це відсіює несправжні набори;
- звіряти результат FP-Growth із Apriori/Eclat (мають збігатися) і порівнювати три алгоритми за генерацією кандидатів, проходами по базі та пам’яттю;
- реалізувати FP-Growth у вигляді програми, що читає транзакції з файлу CSV/тексту, і за потреби доповнити її генерацією асоціативних правил та порівнянням із Apriori.
Робота закріплює Лекцію 12 — Алгоритм FP-Growth і спирається на Лабораторну 11 (Apriori та Eclat). Уся потрібна теорія повторена в самодостатньому вигляді в методичних вказівках.