2. Методичні вказівки #

Цей розділ самодостатній: у ньому зібрано теорію асоціативних правил, мір інтересовності та алгоритмів Apriori і Eclat, потрібну для аудиторних задач (3classroom.md) і домашньої програми (4task.md). Ширше цю саму теорію викладено в Лекції 11.

2.1 Транзакційна база та набори #

Транзакційна (операційна) база — це множина транзакцій $D = \{t_1, \dots, t_N\}$ над множиною елементів $I$; кожна транзакція $t_i \subseteq I$ — набір елементів, що трапилися разом (чек, сеанс, історія хвороби). Набором (англ. itemset) називають будь-яку підмножину $X \subseteq I$; набір із $k$ елементів — $k$-набір.

Базу задають горизонтально (рядок — транзакція зі своїми елементами) або вертикально (елемент $\to$ tid-множина — множина номерів транзакцій, що його містять). Обидва формати рівносильні; вибір визначає зручніший алгоритм.

2.2 Підтримка #

Підтримка (англ. support) набору $X$ — частка транзакцій, що містять $X$:

$$\operatorname{supp}(X) = \frac{|\{\, t \in D : X \subseteq t \,\}|}{N}.$$

Підтримкою правила $X \Rightarrow Y$ називають підтримку об’єднання $\operatorname{supp}(X \cup Y)$ — частку транзакцій, де є і $X$, і $Y$. Порівнюючи з порогом, зручно тримати лічильник $|\{t : X \subseteq t\}|$ і порівнювати його з $s_{\min} \cdot N$.

2.3 Достовірність #

Асоціативне правило $X \Rightarrow Y$ будують для наборів, що не перетинаються ($X \cap Y = \varnothing$). Достовірність (англ. confidence) — умовна частка «серед транзакцій з $X$ — скільки містять і $Y$»:

$$\operatorname{conf}(X \Rightarrow Y) = \frac{\operatorname{supp}(X \cup Y)}{\operatorname{supp}(X)}.$$

Це емпіричний аналог умовної ймовірності $P(Y \mid X)$. Достовірність напрямлена: $\operatorname{conf}(X \Rightarrow Y) \ne \operatorname{conf}(Y \Rightarrow X)$.

2.4 Підйом і переконливість #

Достовірність не враховує, наскільки поширений сам наслідок $Y$. Це виправляє підйом (англ. lift):

$$\operatorname{lift}(X \Rightarrow Y) = \frac{\operatorname{conf}(X \Rightarrow Y)}{\operatorname{supp}(Y)} = \frac{\operatorname{supp}(X \cup Y)}{\operatorname{supp}(X)\,\operatorname{supp}(Y)}.$$

Він порівнює спільну появу $X$ і $Y$ з очікуваною за незалежності: $\operatorname{lift} > 1$ — позитивний зв’язок (притягання), $= 1$ — незалежність, $< 1$ — негативний. Підйом симетричний: $\operatorname{lift}(X \Rightarrow Y) = \operatorname{lift}(Y \Rightarrow X)$.

Переконливість (англ. conviction) вимірює, як часто правило порушується:

$$\operatorname{conv}(X \Rightarrow Y) = \frac{1 - \operatorname{supp}(Y)}{1 - \operatorname{conf}(X \Rightarrow Y)}.$$

$\operatorname{conv} > 1$ — правило змістовне (порушень менше, ніж випадково); $\operatorname{conv} = 1$ — незалежність; $\operatorname{conv} \to \infty$ при $\operatorname{conf} \to 1$ (правило без винятків).

2.5 Часті набори та властивість Apriori #

Набір частий, якщо $\operatorname{supp} \ge s_{\min}$. Пошук правил — це насамперед пошук усіх частих наборів; решта (генерація правил) дешева. Ключ до ефективності — властивість антимонотонності.

Властивість Apriori. Усі підмножини частого набору — часті; рівносильно, будь-яка надмножина нечастого набору — нечаста. Тому щойно набір виявився нечастим, усі його надмножини можна відкинути не рахуючи.

2.6 Алгоритм Apriori (горизонтальний) #

Apriori будує часті набори за зростанням розміру $k$, роблячи прохід по базі на кожному рівні:

1. Часті 1-набори. Порахувати підтримку кожного елемента; лишити ті, що $\ge s_{\min}$.
2. Генерація кандидатів ($k$-набори): з’єднати пари частих $(k{-}1)$-наборів, що різняться лише останнім елементом; відсіяти кандидата, якщо якась його $(k{-}1)$-підмножина нечаста.
3. Підрахунок підтримки кандидатів одним проходом по базі; лишити часті.
4. Повторювати кроки 2–3, доки з’являються нові часті набори.

2.7 Алгоритм Eclat (вертикальний) #

Eclat дає ті самі часті набори, але рахує підтримку не проходом по базі, а перетином tid-множин:

$$\operatorname{tid}(X \cup Y) = \operatorname{tid}(X) \cap \operatorname{tid}(Y), \qquad \operatorname{supp}(X \cup Y) = \frac{|\operatorname{tid}(X) \cap \operatorname{tid}(Y)|}{N}.$$

Він будує префіксне дерево завглибшки: кожен вузол додає елемент, а його tid-множину дістає перетином tid-множини батька з tid-множиною нового елемента; нечасті вузли не розгалужують. Eclat вигідний на розріджених базах (малі tid-множини), Apriori — простіший і ощадливіший за пам’яттю.

2.8 Демонстраційний приклад (на інших даних, ніж у задачах) #

Розгляньмо базу невеликої чайної крамниці ($N = 5$ транзакцій) над елементами $I = \{\text{Чай}, \text{Цукор}, \text{Лимон}, \text{Мед}\}$:

(а) Підтримка та вертикальний формат. tid-множини елементів: $\operatorname{tid}(\text{Чай}) = \{1,2,3,4\}$, $\operatorname{tid}(\text{Цукор}) = \{1,2,3\}$, $\operatorname{tid}(\text{Лимон}) = \{2,4,5\}$, $\operatorname{tid}(\text{Мед}) = \{3,5\}$. Звідси

$$\operatorname{supp}(\{\text{Чай}\}) = \tfrac{4}{5} = 0.8, \quad \operatorname{supp}(\{\text{Цукор}\}) = \tfrac{3}{5} = 0.6, \quad \operatorname{supp}(\{\text{Лимон}\}) = \tfrac{3}{5} = 0.6, \quad \operatorname{supp}(\{\text{Мед}\}) = \tfrac{2}{5} = 0.4.$$

Підтримка пари через перетин: $\operatorname{tid}(\text{Чай}) \cap \operatorname{tid}(\text{Цукор}) = \{1,2,3\}$, тож $\operatorname{supp}(\{\text{Чай}, \text{Цукор}\}) = \tfrac{3}{5} = 0.6$.

(б) Міри для правила $\{\text{Чай}\} \Rightarrow \{\text{Цукор}\}$.

$$\operatorname{conf} = \frac{0.6}{0.8} = 0.75, \qquad \operatorname{lift} = \frac{0.75}{0.6} = 1.25, \qquad \operatorname{conv} = \frac{1 - 0.6}{1 - 0.75} = \frac{0.4}{0.25} = 1.6.$$

Зворотне правило $\{\text{Цукор}\} \Rightarrow \{\text{Чай}\}$ має ту саму підтримку $0.6$, але $\operatorname{conf} = 0.6/0.6 = 1.0$ (усі покупці цукру беруть чай), той самий підйом $1.25$ (симетричний), а $\operatorname{conv} \to \infty$. Підйом однаковий для обох напрямків, достовірність і переконливість — ні.

(в) Apriori за $s_{\min} = 0.4$ (лічильник $\ge 2$). Часті 1-набори — усі чотири. Кандидати-пари й підтримки:

Часті 2-набори: $\{\text{Чай}, \text{Цукор}\}$ і $\{\text{Чай}, \text{Лимон}\}$. Єдиний кандидат-трійка $\{\text{Чай}, \text{Цукор}, \text{Лимон}\}$ відсівається без підрахунку: його підмножина $\{\text{Цукор}, \text{Лимон}\}$ нечаста (властивість Apriori). Отже, частих 3-наборів немає.

2.9 Робочий контрольний список #

• Спершу зафіксуйте пороги $s_{\min}$ і $c_{\min}$ та переведіть $s_{\min}$ у лічильник $s_{\min}\cdot N$ — так зручніше порівнювати.
• Часті набори шукайте за зростанням розміру; нечастий набір відразу вилучайте з подальших з’єднань (не рахуйте його надмножин).
• Достовірність рахуйте для кожного напрямку окремо; підтримка набору — спільна для всіх правил із нього.
• Підйом і переконливість застосовуйте після порогів — щоб упорядкувати правила й прибрати оманливо-достовірні ($\operatorname{lift} \le 1$).
• Для перевірки підтримки зручний вертикальний формат: підтримка набору — потужність перетину tid-множин його елементів.

Laboratory/Laboratory11/2method.md · 11.4 KB · updated 2026-08-05 09:54