3. Аудиторні задачі з розв’язаннями #

Ці задачі розбирають в аудиторії «руками». Вони показують ті самі кроки, які потім автоматизує домашня програма (4task.md). Теорія й псевдокод — у методичних вказівках. Щоб побачити, що FP-Growth дає той самий результат, що й Apriori, ми беремо ту саму базу, на якій виконували Apriori у Задачі 2 Лабораторної 11, і наприкінці звіряємо часті набори. Дані задач відрізняються від демонстраційного прикладу у 2method.md.

Наскрізна база задач — транзакційна база фруктової лавки ($N = 6$), та сама, що в Задачі 2 Лабораторної 11:

Поріг усюди — $s_{\min} = 0.5$ (набір частий, коли він є принаймні у $3$ з $6$ транзакцій, лічильник $\ge 3$).

Задача 1. Побудова FP-дерева #

Знайти $F$-список, упорядковані транзакції, FP-дерево й заголовну таблицю для бази фруктової лавки за $s_{\min} = 0.5$.

Розв’язання. 1-й прохід — частоти елементів.

Апельсин відпадає ($2 < 3$). Решту впорядковуємо за спаданням частоти; за рівних частот (Яблуко й Виноград — обидва $4$) зберігаємо початковий порядок елементів. $F$-список:

$$\text{Банан}(5) \ \prec\ \text{Яблуко}(4) \ \prec\ \text{Виноград}(4).$$

2-й прохід — упорядковані транзакції (викидаємо Апельсин, сортуємо за $F$-списком):

Вставлення шляхів. $t_1$ створює Банан→Яблуко. $t_2$ подовжує його до Банан→Яблуко→Виноград. $t_3$ починається з Яблуко (не з Банан) — спільного префікса немає, з’являється нова гілка Яблуко→Виноград під коренем. $t_4$ ділить корінь-вузол Банан і додає під ним Виноград. $t_5$ лягає вздовж наявної гілки Банан→Яблуко→Виноград, нарощуючи лічильники. $t_6$ — лише Банан. Остаточне FP-дерево:

null
├─ Банан:5
│  ├─ Яблуко:3
│  │  └─ Виноград:2
│  └─ Виноград:1
└─ Яблуко:1
   └─ Виноград:1

Заголовна таблиця (частота + вузли за зв’язками):

Перевірка (сума лічильників вузлів = частота): Яблуко $3 + 1 = 4$; Виноград $2 + 1 + 1 = 4$; Банан $5$ — усе збігається з 1-м проходом.

Відповідь: $F$-список $\text{Банан}(5) \prec \text{Яблуко}(4) \prec \text{Виноград}(4)$; FP-дерево наведено вище (шість вузлів проти $2+3+2+2+3+1 = 13$ входжень частих елементів окремими шляхами — стиснення завдяки спільним префіксам).

Задача 2. Умовна база образів та умовне FP-дерево #

Для елемента Виноград (найрідший у $F$-списку — з нього починають видобуток) побудувати умовну базу образів і умовне FP-дерево.

Розв’язання. За заголовною таблицею у Винограду три вузли; для кожного беремо префіксний шлях від кореня (без самого Винограду) з лічильником цього вузла:

• Виноград:2 — під Банан→Яблуко: шлях $(\text{Банан}, \text{Яблуко})$ з лічильником $2$;
• Виноград:1 — під Банан: шлях $(\text{Банан})$ з лічильником $1$;
• Виноград:1 — під Яблуко (гілка від кореня): шлях $(\text{Яблуко})$ з лічильником $1$.

Умовна база образів Винограду:

$$(\text{Банан}, \text{Яблуко}):2, \qquad (\text{Банан}):1, \qquad (\text{Яблуко}):1.$$

Частоти в цій базі: Банан $= 2 + 1 = 3$, Яблуко $= 2 + 1 = 3$ — обидва часті ($\ge 3$), нічого не відкидаємо. Вставивши три шляхи (за порядком $\text{Банан} \prec \text{Яблуко}$), дістаємо умовне FP-дерево Винограду:

null
├─ Банан:3
│  └─ Яблуко:2
└─ Яблуко:1        (умовне дерево для Виноград)

Це дерево не є єдиним шляхом (Яблуко трапляється і під Банан, і під коренем), тож із нього часті набори видобувають рекурсивно — знизу вгору за його заголовною таблицею $[\text{Яблуко}(3), \text{Банан}(3)]$:

• Яблуко в умовному дереві Винограду: дає набір $\{\text{Яблуко}, \text{Виноград}\}$ з підтримкою $3$. Його умовна база тут — $(\text{Банан}):2$; Банан має лічильник $2 < 3$, відпадає — далі порожньо.
• Банан в умовному дереві Винограду: дає набір $\{\text{Банан}, \text{Виноград}\}$ з підтримкою $3$. Банан — під коренем, умовна база порожня.

Відповідь: умовна база образів Винограду — $(\text{Банан}, \text{Яблуко}):2,\ (\text{Банан}):1,\ (\text{Яблуко}):1$; умовне FP-дерево — гілки Банан:3→Яблуко:2 та Яблуко:1. З нього виходять часті набори $\{\text{Яблуко}, \text{Виноград}\}:3$ і $\{\text{Банан}, \text{Виноград}\}:3$. Набір $\{\text{Банан}, \text{Яблуко}, \text{Виноград}\}$ не частий: Банан всередині під-бази Яблуко має лічильник лише $2$.

Задача 3. Повний видобуток і звірка з Apriori #

Видобути всі часті набори алгоритмом FP-Growth і звірити їх із результатом Apriori із Задачі 2 Лабораторної 11 (мають збігтися).

Розв’язання. Обходимо заголовну таблицю Задачі 1 знизу вгору: Виноград, Яблуко, Банан.

• Виноград (Задача 2): $\{\text{Виноград}\}:4$, а з умовного дерева — $\{\text{Яблуко}, \text{Виноград}\}:3$ і $\{\text{Банан}, \text{Виноград}\}:3$.
• Яблуко: $\{\text{Яблуко}\}:4$. Умовна база образів — $(\text{Банан}):3$ (у Яблука два вузли: Яблуко:3 під Банан дає $(\text{Банан}):3$; Яблуко:1 під коренем дає порожній шлях). Банан частий ($3 \ge 3$), умовне дерево — єдиний вузол Банан:3, звідки $\{\text{Банан}, \text{Яблуко}\}:3$.
• Банан: $\{\text{Банан}\}:5$; найчастіший, завжди під коренем — умовна база порожня.

Усі часті набори й звірка з Apriori (Задача 2 Лабораторної 11):

Частих наборів розміру $\ge 3$ немає: єдиний кандидат-трійка $\{\text{Яблуко}, \text{Банан}, \text{Виноград}\}$ трапляється лише в $t_2, t_5$ (підтримка $2/6 \approx 0.33 < 0.5$), і FP-Growth його не породив — саме тому, що Банан відсіявся всередині умовної під-бази (Задача 2).

Відповідь: FP-Growth знаходить три часті 1-набори ($\{\text{Банан}\}, \{\text{Яблуко}\}, \{\text{Виноград}\}$) і три часті 2-набори ($\{\text{Банан}, \text{Яблуко}\}, \{\text{Банан}, \text{Виноград}\}, \{\text{Яблуко}, \text{Виноград}\}$, усі з підтримкою $0.5$); частих наборів розміру $\ge 3$ немає. Це точно той самий список, що дав Apriori у Задачі 2 Лабораторної 11 — але без генерації кандидатів і лише за два проходи по базі. З цих частих 2-наборів далі генерують правила так само, як у Задачі 2 Лабораторної 11 (з $c_{\min} = 0.7$ проходять чотири правила з достовірністю $0.75$).

Зв’язок із домашнім завданням. Саме ці кроки — порахувати частоти й скласти $F$-список, побудувати FP-дерево, для кожного елемента утворити умовну базу образів та умовне дерево й рекурсивно видобути часті набори — виконуватиме ваша програма для довільного файлу транзакцій (4task.md). База фруктової лавки — зручний тест: подайте ці шість транзакцій на вхід за $s_{\min} = 0.5$ й переконайтесь, що програма повертає ті самі три часті 1-набори та три часті 2-набори, а її результат збігається з Apriori з Лабораторної 11.

Laboratory/Laboratory12/3classroom.md · 13.1 KB · updated 2026-08-05 09:45