# 6. Контрольні запитання

Ці запитання допомагають перевірити готовність до роботи й самоконтроль після неї.
Відповіді спираються на [методичні вказівки](2method.md) та
[Лекцію 12](../../Lectures/DA-L12.md).

## Мотивація та ідея FP-Growth

1. Які **два обмеження Apriori** долає FP-Growth? Поясніть, чому «вартість
   кандидатів» і «багаторазові проходи по базі» стають вузькими місцями на великих
   даних.
2. У чому **основна ідея** FP-Growth? Скільки проходів по базі він робить і чому
   каже, що метод шукає часті набори **без генерації кандидатів**?
3. Чи знаходять Apriori, Eclat і FP-Growth **однакові** часті набори? Що саме в них
   різне?

## FP-дерево

4. Що таке **FP-дерево**? Що зберігає кожен його вузол і що таке **заголовна
   таблиця** та **зв'язки між вузлами** (node-links)?
5. Опишіть **два проходи** побудови FP-дерева. Що роблять у 1-му проході й що — у
   2-му?
6. Навіщо елементи впорядковують **за спаданням частоти** ($F$-список) перед
   вставленням? Що станеться зі стисненням, якщо взяти довільний порядок?
7. Чому нечасті елементи відкидають **ще до** побудови дерева? На яку властивість
   (Лабораторна 11) це спирається?
8. Як перевірити правильність побудованого дерева за **сумою лічильників** вузлів
   одного елемента?

## Умовна база образів та видобуток

9. Дайте означення **умовної бази образів** елемента. Як її побудувати за
   заголовною таблицею й node-links?
10. Що таке **умовне FP-дерево** і чим воно відрізняється від умовної бази образів?
    Чому в ньому поріг $s_{\min}$ **застосовують наново**?
11. Чому видобуток ведуть **знизу вгору** заголовною таблицею (від найрідшого
    елемента)?
12. У чому полягає оптимізація «**єдиний шлях**»? Як із ланцюжка вузлів одразу
    виписати всі часті набори та їхні підтримки?
13. На прикладі поясніть, як поріг, застосований у **умовній** базі, відсіює набір,
    що здавався би частим (напр., чому не з'являється трійка з Задач
    [3classroom.md](3classroom.md)).

## Порівняння та реалізація

14. Порівняйте **Apriori, Eclat і FP-Growth** за генерацією кандидатів, кількістю
    проходів по базі та пам'яттю. Коли який вигідніший (щільні проти розріджених
    баз)?
15. Як **перевірити правильність** реалізації FP-Growth? (Порівняння з обчисленням
    «руками», **звірка з Apriori** — часті набори мають збігатися, порівняння з
    бібліотечною реалізацією.)
16. Як програма має опрацьовувати **крайні випадки** (порожній файл, транзакції
    різної довжини, поріг поза $[0,1]$, дублікати елементів у рядку)?