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

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

Задача 1. Міри інтересовності на малій базі #

Дано транзакційну базу міні-маркету ($N = 5$ транзакцій):

Знайти: підтримку наборів $\{\text{Кола}\}$, $\{\text{Чипси}\}$, $\{\text{Пиво}\}$, $\{\text{Кола}, \text{Чипси}\}$, $\{\text{Чипси}, \text{Пиво}\}$; а також достовірність, підйом і переконливість правил $\{\text{Чипси}\} \Rightarrow \{\text{Пиво}\}$, $\{\text{Пиво}\} \Rightarrow \{\text{Чипси}\}$ та $\{\text{Кола}\} \Rightarrow \{\text{Чипси}\}$.

Розв’язання. Підрахуємо лічильники транзакцій.

• Кола — у $t_1, t_2, t_3, t_5$: лічильник $4$, $\operatorname{supp} = \tfrac{4}{5} = 0.8$.
• Чипси — у $t_1, t_2, t_4, t_5$: лічильник $4$, $\operatorname{supp} = \tfrac{4}{5} = 0.8$.
• Пиво — у $t_2, t_4, t_5$: лічильник $3$, $\operatorname{supp} = \tfrac{3}{5} = 0.6$.
• $\{\text{Кола}, \text{Чипси}\}$ — у $t_1, t_2, t_5$: $\operatorname{supp} = \tfrac{3}{5} = 0.6$.
• $\{\text{Чипси}, \text{Пиво}\}$ — у $t_2, t_4, t_5$: $\operatorname{supp} = \tfrac{3}{5} = 0.6$.

Правило $\{\text{Чипси}\} \Rightarrow \{\text{Пиво}\}$:

$$\operatorname{conf} = \frac{\operatorname{supp}(\{\text{Чипси}, \text{Пиво}\})}{\operatorname{supp}(\{\text{Чипси}\})} = \frac{0.6}{0.8} = 0.75, \qquad \operatorname{lift} = \frac{0.75}{\operatorname{supp}(\{\text{Пиво}\})} = \frac{0.75}{0.6} = 1.25,$$

$$\operatorname{conv} = \frac{1 - \operatorname{supp}(\{\text{Пиво}\})}{1 - \operatorname{conf}} = \frac{1 - 0.6}{1 - 0.75} = \frac{0.4}{0.25} = 1.6.$$

Правило $\{\text{Пиво}\} \Rightarrow \{\text{Чипси}\}$ (той самий набір, інший напрямок):

$$\operatorname{conf} = \frac{0.6}{0.6} = 1.0, \qquad \operatorname{lift} = \frac{1.0}{0.8} = 1.25, \qquad \operatorname{conv} = \frac{1 - 0.8}{1 - 1.0} \to \infty.$$

Підйом обох напрямків однаковий ($1.25$), бо симетричний; достовірність — різна ($0.75$ проти $1.0$): усі покупці пива беруть чипси, але не навпаки. Переконливість напрямку «Пиво $\Rightarrow$ Чипси» нескінченна — у цій базі правило без винятків.

Правило $\{\text{Кола}\} \Rightarrow \{\text{Чипси}\}$:

$$\operatorname{conf} = \frac{\operatorname{supp}(\{\text{Кола}, \text{Чипси}\})}{\operatorname{supp}(\{\text{Кола}\})} = \frac{0.6}{0.8} = 0.75, \qquad \operatorname{lift} = \frac{0.75}{0.8} = 0.9375 < 1,$$

$$\operatorname{conv} = \frac{1 - 0.8}{1 - 0.75} = \frac{0.2}{0.25} = 0.8 < 1.$$

Достовірність висока ($0.75$), але підйом менший за одиницю: кола й чипси з’являються разом навіть трохи рідше, ніж за незалежності (обидва просто дуже поширені). Це правило оманливо-достовірне — його відкидають за підйомом.

Відповідь: $\operatorname{supp}(\{\text{Кола}\}) = \operatorname{supp}(\{\text{Чипси}\}) = 0.8$, $\operatorname{supp}(\{\text{Пиво}\}) = 0.6$, $\operatorname{supp}(\{\text{Кола}, \text{Чипси}\}) = \operatorname{supp}(\{\text{Чипси}, \text{Пиво}\}) = 0.6$; $\{\text{Чипси}\} \Rightarrow \{\text{Пиво}\}$: $\operatorname{conf} = 0.75$, $\operatorname{lift} = 1.25$, $\operatorname{conv} = 1.6$; $\{\text{Пиво}\} \Rightarrow \{\text{Чипси}\}$: $\operatorname{conf} = 1.0$, $\operatorname{lift} = 1.25$, $\operatorname{conv} = \infty$; $\{\text{Кола}\} \Rightarrow \{\text{Чипси}\}$: $\operatorname{conf} = 0.75$, $\operatorname{lift} = 0.9375$, $\operatorname{conv} = 0.8$.

Задача 2. Apriori «руками» #

Дано транзакційну базу фруктової лавки ($N = 6$):

Знайти всі часті 1- та 2-набори за $s_{\min} = 0.5$ (лічильник $\ge 3$) і згенерувати з них правила з достовірністю $\ge c_{\min} = 0.7$.

Розв’язання. Крок 1 — часті 1-набори.

Апельсин відпадає (і не з’явиться в жодному кандидаті).

Крок 2 — часті 2-набори. З’єднання трьох частих 1-наборів дає $\binom{3}{2} = 3$ кандидати; відсів нікого не викидає (усі 1-підмножини часті). Рахуємо:

Усі три часті. Єдиний кандидат-трійка $\{\text{Яблуко}, \text{Банан}, \text{Виноград}\}$ (усі його пари часті, тож відсів його лишає) трапляється лише в $t_2, t_5$: $\operatorname{supp} = \tfrac{2}{6} \approx 0.33 < 0.5$ — нечастий. Отже, частих наборів розміру $\ge 3$ немає.

Крок 3 — генерація правил ($c_{\min} = 0.7$). З кожного частого 2-набору виходить два правила; достовірність $\operatorname{conf} = \operatorname{supp}(\text{пари})/\operatorname{supp}(\text{умови})$:

Поріг достовірності проходять чотири правила. Правила з умовою «Банан» ($\operatorname{supp} = 5/6$) відпадають: банан надто поширений, тож частка його співпокупців з іншим товаром мала.

Відповідь: часті 1-набори — $\{\text{Яблуко}\}, \{\text{Банан}\}, \{\text{Виноград}\}$; часті 2-набори — $\{\text{Яблуко}, \text{Банан}\}, \{\text{Яблуко}, \text{Виноград}\}, \{\text{Банан}, \text{Виноград}\}$ (усі з $\operatorname{supp} = 0.5$); частих 3-наборів немає. Правила з $\operatorname{conf} \ge 0.7$: $\{\text{Яблуко}\} \Rightarrow \{\text{Банан}\}$, $\{\text{Яблуко}\} \Rightarrow \{\text{Виноград}\}$, $\{\text{Виноград}\} \Rightarrow \{\text{Яблуко}\}$, $\{\text{Виноград}\} \Rightarrow \{\text{Банан}\}$ (усі $\operatorname{conf} = 0.75$).

Задача 3. Eclat та відбір цікавих правил #

Дано ту саму базу, що в Задачі 2. Перевірити результат Задачі 2 алгоритмом Eclat (через tid-множини) і відібрати справді цікаві правила серед тих, що пройшли поріг достовірності, скориставшись підйомом і переконливістю.

Розв’язання. Вертикальний формат (tid-множини):

$$\operatorname{tid}(\text{Яблуко}) = \{1,2,3,5\}, \quad \operatorname{tid}(\text{Банан}) = \{1,2,4,5,6\}, \quad \operatorname{tid}(\text{Виноград}) = \{2,3,4,5\}.$$

Підтримку пар дістаємо перетином, не переглядаючи транзакцій:

$$\operatorname{tid}(\text{Яблуко}) \cap \operatorname{tid}(\text{Виноград}) = \{2,3,5\} \ (|\cdot| = 3), \quad \operatorname{tid}(\text{Яблуко}) \cap \operatorname{tid}(\text{Банан}) = \{1,2,5\} \ (3),$$

$$\operatorname{tid}(\text{Банан}) \cap \operatorname{tid}(\text{Виноград}) = \{2,4,5\} \ (3).$$

Усі три пари мають лічильник $3$ — збіг із Задачею 2. Для трійки перетинаємо далі:

$$\big(\operatorname{tid}(\text{Яблуко}) \cap \operatorname{tid}(\text{Виноград})\big) \cap \operatorname{tid}(\text{Банан}) = \{2,3,5\} \cap \{1,2,4,5,6\} = \{2,5\} \ (2 < 3),$$

тобто $\{\text{Яблуко}, \text{Банан}, \text{Виноград}\}$ нечастий — знову збіг.

Відбір цікавих правил. З чотирьох правил, що пройшли $c_{\min}$ (Задача 2), залишаємо ті, де $\operatorname{lift} > 1$, і впорядковуємо за переконливістю:

Хоча всі чотири мають однакову достовірність $0.75$, лише пара «Яблуко — Виноград» має $\operatorname{lift} > 1$ і $\operatorname{conv} > 1$ — це справжній позитивний зв’язок. Правила з наслідком «Банан» ($\operatorname{lift} = 0.9$) — оманливо-достовірні через велику поширеність банана.

Відповідь: Eclat підтверджує часті набори Задачі 2; єдиний цікавий зв’язок — взаємне притягання Яблуко $\leftrightarrow$ Виноград ($\operatorname{lift} = 1.125$, $\operatorname{conv} = 1.33$).

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

Laboratory/Laboratory11/3classroom.md · 13.7 KB · updated 2026-08-05 09:55