# Лекція 11. Пошук асоціативних правил. Алгоритми Apriori та Eclat ## Огляд У [Лекції 9](DA-L09.md) та [Лекції 10](DA-L10.md) ми розв'язували задачі **кластеризації** — це вже було **навчання без учителя** (англ. *unsupervised learning*): даним не приписано жодної цільової позначки, і метод сам шукає в них структуру. Пошук **асоціативних правил** належить до тієї самої родини, але шукає структуру **іншого типу**: не групи схожих об'єктів, а **сталі спільні появи ознак** — набори елементів, що систематично трапляються разом, і залежності «якщо є одне — імовірно, є й інше». Класичний приклад — **аналіз ринкового кошика** (англ. *market basket analysis*): за чеками супермаркету знайти, які товари купують укупі. Правило «хто бере пелюшки, часто бере й пиво» — не прогноз для конкретного покупця (як у класифікації), а **виявлена закономірність** усієї бази транзакцій. У цій лекції ми означимо асоціативне правило, уведемо чотири **міри інтересовності** (підтримка, достовірність, підйом, переконливість), навчимося відбирати **цікаві** правила й розберемо два алгоритми пошуку частих наборів — **Apriori** (горизонтальний, з відсіванням кандидатів) та **Eclat** (вертикальний, на перетинах tid-множин). > **Практичний бік.** Підтримку, достовірність і підйом ви обчислюватимете > «руками» й виконаєте **Apriori вручну**, а потім реалізуєте пошук правил > **програмою** в [Лабораторній роботі 11](../Laboratory/Laboratory11/main.md). Наскрізний приклад лекції — маленька **транзакційна база** невеликого магазину: шість чеків над п'ятьма товарами. | Транзакція | Товари (набір елементів) | |:--:|---| | $t_1$ | Хліб, Молоко, Яйця | | $t_2$ | Хліб, Масло | | $t_3$ | Хліб, Молоко, Масло, Яйця | | $t_4$ | Молоко, Масло | | $t_5$ | Хліб, Молоко, Масло | | $t_6$ | Хліб, Молоко, Яйця, Кава | Тут $N = 6$ транзакцій, а множина всіх товарів — $I = \{\text{Хліб}, \text{Молоко}, \text{Масло}, \text{Яйця}, \text{Кава}\}$. ![Транзакційна база наскрізного прикладу у вигляді бінарної матриці «чек × товар» з підтримкою кожного товару](img/l11_transactions.png) --- ## 11.1 Задача пошуку асоціативних правил > **Означення (пошук асоціативних правил).** **Пошук асоціативних правил** (англ. > *association rule mining*) — це напрям машинного навчання, присвячений > знаходженню в даних сталих залежностей у формі правил «**якщо** $A$, **то** > $B$», де $A$ і $B$ — набори елементів (подій), що часто трапляються разом. Три риси відрізняють цю задачу від класифікації ([Лекції 6](DA-L06.md)–[8](DA-L08.md)): - **Немає виділеної цільової ознаки.** Будь-який елемент може опинитися як у лівій, так і в правій частині правила; ми не передбачаємо один стовпець за іншими, а шукаємо всі помітні зв'язки одразу. - **Результат — описовий, а не прогнозний.** Правило описує **закономірність наявних даних**, а не виносить вирок про новий об'єкт. - **Зв'язок — не причинність.** «Якщо $A$, то $B$» означає лише, що поява $A$ **супроводжується** появою $B$ частіше за випадкову; це не твердження, що $A$ **спричиняє** $B$. --- ## 11.2 Сфери застосування Задача виникає всюди, де дані природно подаються як **набори одночасних подій**. - **Аналіз ринкового кошика.** Товари з одного чеку — для розкладки на полицях, рекомендацій («з цим товаром купують…») та акцій. - **Медична діагностика.** Симптоми, результати аналізів і діагнози, що стало супроводжують певне захворювання. - **Аналіз веб-сторінок.** Сторінки одного сеансу чи переходи за посиланнями — для навігації та перелінкування. - **Біоінформатика.** Гени, що спільно експресуються, чи мутації, що трапляються разом; асоціації генотипу й фенотипу. - **Кібербезпека.** Ознаки мережевих подій, що разом характеризують атаку, — для сигнатур систем виявлення вторгнень. --- ## 11.3 Транзакційна база даних > **Означення (транзакційна база).** **Транзакційна** (операційна) база даних — > це множина **транзакцій** $D = \{t_1, t_2, \dots, t_N\}$ над скінченною > множиною **елементів** (англ. *items*) $I$. Кожна транзакція $t_i \subseteq I$ > — це **набір елементів**, що трапилися разом. **Набором** (англ. *itemset*) > називають будь-яку підмножину $X \subseteq I$; набір із $k$ елементів — це > **$k$-набір**. На відміну від таблиці «об'єкт $\times$ ознаки» з попередніх лекцій, транзакції можуть мати **різну довжину** (у чеку буває один товар, а буває десять), а порядок елементів у транзакції несуттєвий. ### Два способи задання Ту саму базу можна зберігати двома рівносильними способами — і вибір між ними визначає, який алгоритм зручніший. **Горизонтальний формат** (транзакція $\to$ набір елементів) — це саме таблиця з §Огляд: рядок — транзакція, у ньому перелічено її елементи. Так дані надходять природно (чек, сеанс, історія хвороби). **Вертикальний формат** (елемент $\to$ множина транзакцій) — для кожного елемента зберігають **tid-множину** (англ. *tid-set*, від *transaction identifier*) — множину номерів транзакцій, що його містять: | Елемент | tid-множина | |---|---| | Хліб | $\{1, 2, 3, 5, 6\}$ | | Молоко | $\{1, 3, 4, 5, 6\}$ | | Масло | $\{2, 3, 4, 5\}$ | | Яйця | $\{1, 3, 6\}$ | | Кава | $\{6\}$ | Вертикальний формат зручний тим, що **підтримку набору** (скільки транзакцій його містять) можна дістати як **перетин** tid-множин його елементів — на цьому й побудовано алгоритм Eclat (§11.8). --- ## 11.4 Асоціативне правило > **Означення (асоціативне правило).** **Асоціативне правило** — це вираз > $$ X \Rightarrow Y, $$ > де $X, Y \subseteq I$ — непорожні набори елементів, що **не перетинаються** > ($X \cap Y = \varnothing$). Набір $X$ називають **умовою** (антецедентом, > англ. *antecedent*), а $Y$ — **наслідком** (консеквентом, англ. > *consequent*). Читається правило як «транзакції, що містять $X$, схильні містити й $Y$». Наприклад, $\{\text{Молоко}\} \Rightarrow \{\text{Яйця}\}$ означає «до молока часто беруть яйця». Саме собою правило нічого не варте, доки ми не виміряли, **наскільки воно надійне** й **наскільки цікаве**. Для цього слугують чотири числові міри. --- ## 11.5 Міри інтересовності ### Підтримка > **Означення (підтримка).** **Підтримка** (англ. *support*) набору $X$ — це > частка транзакцій, що містять $X$: > $$ \operatorname{supp}(X) = \frac{|\{\, t \in D : X \subseteq t \,\}|}{N}. $$ Підтримка показує, **наскільки поширений** набір. Підтримкою **правила** $X \Rightarrow Y$ називають підтримку об'єднання $\operatorname{supp}(X \cup Y)$ — частку транзакцій, де є **і** $X$, **і** $Y$. **Приклад 11.1 (підтримка наборів).** У наскрізній базі ($N = 6$): $$ \operatorname{supp}(\{\text{Хліб}\}) = \tfrac{5}{6} \approx 0.83, \qquad \operatorname{supp}(\{\text{Яйця}\}) = \tfrac{3}{6} = 0.5, \qquad \operatorname{supp}(\{\text{Кава}\}) = \tfrac{1}{6} \approx 0.17. $$ Молоко з яйцями трапляються разом у транзакціях $t_1, t_3, t_6$, тож $\operatorname{supp}(\{\text{Молоко}, \text{Яйця}\}) = \tfrac{3}{6} = 0.5$. Це ж число — підтримка правила $\{\text{Молоко}\} \Rightarrow \{\text{Яйця}\}$. ### Достовірність Підтримка симетрична й не відрізняє «якщо $A$, то $B$» від «якщо $B$, то $A$». **Напрямок** правила вимірює достовірність. > **Означення (достовірність).** **Достовірність** (англ. *confidence*) правила > $X \Rightarrow Y$ — > $$ \operatorname{conf}(X \Rightarrow Y) = \frac{\operatorname{supp}(X \cup Y)}{\operatorname{supp}(X)}. $$ Це **умовна частка**: серед транзакцій, що містять $X$, яка **частина** містить ще й $Y$. Достовірність — емпіричний аналог умовної ймовірності $P(Y \mid X)$. **Приклад 11.2 (достовірність).** Для $\{\text{Молоко}\} \Rightarrow \{\text{Яйця}\}$: $$ \operatorname{conf} = \frac{\operatorname{supp}(\{\text{Молоко}, \text{Яйця}\})}{\operatorname{supp}(\{\text{Молоко}\})} = \frac{3/6}{5/6} = \frac{3}{5} = 0.6. $$ Тобто $60\%$ покупців молока беруть і яйця. Натомість для зворотного напрямку $\{\text{Яйця}\} \Rightarrow \{\text{Молоко}\}$: $$ \operatorname{conf} = \frac{3/6}{3/6} = 1.0, $$ бо **всі** три транзакції з яйцями містять молоко. Підтримка обох правил однакова ($0.5$), а достовірність — різна: достовірність **напрямлена**. > **Типова помилка (висока достовірність без урахування поширеності наслідку).** > Достовірність $1.0$ здається ідеальною, але сама собою може ввести в оману. > Якщо наслідок $Y$ і так є майже в кожній транзакції, то $Y$ «підтвердиться» > після будь-якого $X$ — правило достовірне, але **беззмістовне**. Саме цю > ваду виправляє підйом. ### Підйом > **Означення (підйом).** **Підйом** (англ. *lift*) правила $X \Rightarrow Y$ — > це відношення його достовірності до підтримки наслідку: > $$ \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)}. $$ Підйом порівнює, **наскільки частіше** $Y$ з'являється разом з $X$, ніж якби $X$ і $Y$ були **незалежні**. Три випадки: - $\operatorname{lift} > 1$ — **позитивний** зв'язок: $X$ і $Y$ притягуються (поява $X$ підвищує шанс $Y$); - $\operatorname{lift} = 1$ — **незалежність**: $X$ нічого не каже про $Y$; - $\operatorname{lift} < 1$ — **негативний** зв'язок: $X$ і $Y$ відштовхуються. Із другої формули видно, що підйом **симетричний**: $\operatorname{lift}(X \Rightarrow Y) = \operatorname{lift}(Y \Rightarrow X)$ — на відміну від достовірності. **Приклад 11.3 (підйом).** Для $\{\text{Молоко}\} \Rightarrow \{\text{Яйця}\}$ ($\operatorname{conf} = 0.6$, $\operatorname{supp}(\{\text{Яйця}\}) = 0.5$): $$ \operatorname{lift} = \frac{0.6}{0.5} = 1.2 > 1, $$ тобто молоко підвищує шанс яєць на $20\%$ — слабкий, але позитивний зв'язок. Порівняймо з $\{\text{Хліб}\} \Rightarrow \{\text{Молоко}\}$: $$ \operatorname{conf} = \frac{4/6}{5/6} = \frac{4}{5} = 0.8, \qquad \operatorname{lift} = \frac{0.8}{5/6} = \frac{24}{25} = 0.96 < 1. $$ Достовірність висока ($0.8$), але підйом **менший за одиницю**: хліб і молоко з'являються разом навіть трохи **рідше**, ніж за незалежності, — просто обидва дуже поширені. Це саме та пастка, від якої застерігала виноска вище: висока достовірність без підйому оманлива. ### Переконливість Підйом симетричний і не бачить напрямку. Ще одна міра, **переконливість**, відновлює напрямок і зосереджується на тому, **як часто правило помиляється**. > **Означення (переконливість).** **Переконливість** (англ. *conviction*) > правила $X \Rightarrow Y$ — > $$ \operatorname{conv}(X \Rightarrow Y) = \frac{1 - \operatorname{supp}(Y)}{1 - \operatorname{conf}(X \Rightarrow Y)}. $$ Чисельник $1 - \operatorname{supp}(Y)$ — частка транзакцій **без** $Y$ узагалі; знаменник $1 - \operatorname{conf}$ — частка «порушень» правила (є $X$, немає $Y$). Отже, переконливість — відношення очікуваної частоти порушень за незалежності до фактичної. Тлумачення: - $\operatorname{conv} > 1$ — правило **змістовне**: порушень менше, ніж було б випадково (що більше, то краще); - $\operatorname{conv} = 1$ — незалежність ($X$ і $Y$ не пов'язані); - $\operatorname{conv} \to \infty$, коли $\operatorname{conf} \to 1$ — правило **ніколи не порушується**. **Приклад 11.4 (переконливість).** Для $\{\text{Молоко}\} \Rightarrow \{\text{Яйця}\}$ ($\operatorname{conf} = 0.6$, $\operatorname{supp}(\{\text{Яйця}\}) = 0.5$): $$ \operatorname{conv} = \frac{1 - 0.5}{1 - 0.6} = \frac{0.5}{0.4} = 1.25 > 1 $$ — правило змістовніше за випадкове. А для $\{\text{Яйця}\} \Rightarrow \{\text{Хліб}\}$ маємо $\operatorname{conf} = 1.0$, тож знаменник обертається на нуль і $\operatorname{conv} \to \infty$: у нашій базі це правило не має жодного винятку. Зведемо всі чотири міри для трьох правил (усі числа перевірено обчисленням): | Правило | $\operatorname{supp}$ | $\operatorname{conf}$ | $\operatorname{lift}$ | $\operatorname{conv}$ | |---|:--:|:--:|:--:|:--:| | $\{\text{Молоко}\} \Rightarrow \{\text{Яйця}\}$ | $0.5$ | $0.6$ | $1.2$ | $1.25$ | | $\{\text{Хліб}\} \Rightarrow \{\text{Молоко}\}$ | $0.67$ | $0.8$ | $0.96$ | $0.83$ | | $\{\text{Яйця}\} \Rightarrow \{\text{Хліб}\}$ | $0.5$ | $1.0$ | $1.2$ | $\infty$ | ![Перетин tid-множин Молока та Яєць із обчисленням підтримки, достовірності й підйому для правила Молоко ⇒ Яйця](img/l11_measures.png) --- ## 11.6 Відбір цікавих правил Правил, які можна виписати з бази, надзвичайно багато (для $|I|$ елементів — експоненційно). Переважна більшість — випадковий шум або тривіальності. Тому задають **два пороги** й лишають правила, що долають обидва. > **Означення (цікаве правило).** Задано **мінімальну підтримку** $s_{\min}$ і > **мінімальну достовірність** $c_{\min}$. Правило $X \Rightarrow Y$ вважають > **цікавим**, якщо > $$ \operatorname{supp}(X \cup Y) \ge s_{\min} \quad \text{і} \quad \operatorname{conf}(X \Rightarrow Y) \ge c_{\min}. $$ Поріг **підтримки** відсіює **рідкісні** набори (випадкові збіги, статистично ненадійні); поріг **достовірності** відсіює **ненадійні** напрямки. Підйом і переконливість застосовують **додатково** — уже до правил, що пройшли обидва пороги, — щоб упорядкувати їх за силою зв'язку й прибрати оманливо-достовірні (з $\operatorname{lift} \le 1$). ![Стовпчикова діаграма підйому кількох правил відносно межі lift = 1: зелені притягуються, помаранчеві відштовхуються](img/l11_lift.png) Пошук цікавих правил природно розпадається на **два кроки**: 1. **Знайти всі часті набори** — набори з $\operatorname{supp} \ge s_{\min}$. Це обчислювально важка частина; їй присвячено Apriori та Eclat. 2. **Згенерувати правила** з кожного частого набору: набір $Z$ розбивають на $X$ і $Y = Z \setminus X$ усіма способами й лишають ті, де $\operatorname{conf} \ge c_{\min}$. Цей крок дешевий, бо всі потрібні підтримки вже пораховано на кроці 1. ### Граф правил Набір відібраних правил зручно подати **графом**: вершини — елементи (або набори), орієнтоване ребро $X \to Y$ означає правило $X \Rightarrow Y$, а його товщину чи колір пов'язують із мірою (підтримкою, достовірністю, підйомом). Так стають видимими центральні товари (багато вихідних ребер), взаємні пари й ізольовані елементи. Такий **граф цікавих правил** — стандартний спосіб подати результат аналізу замовникові. ![Граф асоціативних правил наскрізної бази: вершини-товари, орієнтовані ребра, товщина й колір за підйомом](img/l11_rule_graph.png) --- ## 11.7 Алгоритм Apriori Перебирати всі $2^{|I|}$ наборів неможливо. **Apriori** різко скорочує перебір, спираючись на одну структурну властивість частоти. > **Властивість Apriori (антимонотонність).** Усі підмножини частого набору — > часті; рівносильно, **будь-яка надмножина нечастого набору — нечаста**. > > *Обґрунтування.* Якщо $X \subseteq Y$, то кожна транзакція, що містить $Y$, > містить і $X$, тож $\operatorname{supp}(X) \ge \operatorname{supp}(Y)$. > Отже, коли $\operatorname{supp}(Y) \ge s_{\min}$, то й > $\operatorname{supp}(X) \ge s_{\min}$. $\blacksquare$ Практичний наслідок: щойно набір виявився **нечастим**, усі його надмножини можна **відкинути не рахуючи** — саме це економить роботу. ### Кроки алгоритму ```text Apriori(транзакції D, мінімальна підтримка s_min): L1 <- усі 1-набори з підтримкою >= s_min # часті 1-набори k <- 2 доки L(k-1) не порожня: Ck <- apriori_gen(L(k-1)) # кандидати k-наборів для кожної транзакції t із D: # один прохід по базі для кожного кандидата c ⊆ t: лічильник[c]++ Lk <- { c ∈ Ck : лічильник[c]/N >= s_min } # часті k-набори k <- k + 1 повернути об'єднання всіх Lk apriori_gen(L(k-1)): # генерація кандидатів # з'єднання: два (k-1)-набори зі спільними першими (k-2) елементами Ck <- { p ∪ q : p,q ∈ L(k-1), різняться лише останнім елементом } # відсів: викинути кандидата, якщо якась його (k-1)-підмножина ∉ L(k-1) для кожного c ∈ Ck: якщо існує (k-1)-підмножина s ⊂ c така, що s ∉ L(k-1): викинути c повернути Ck ``` Ключова ідея — **генерація кандидатів у два підкроки**: *з'єднання* будує потенційні $k$-набори з частих $(k{-}1)$-наборів, а *відсів* заздалегідь викидає тих кандидатів, чия якась $(k{-}1)$-підмножина нечаста (за властивістю Apriori вони не можуть бути частими). Лише те, що пережило відсів, коштує проходу по базі для підрахунку підтримки. ### Приклад 11.5 (Apriori вручну) Візьмемо наскрізну базу й поріг $s_{\min} = 0.5$, тобто набір частий, коли він є принаймні у $3$ з $6$ транзакцій (лічильник $\ge 3$). **Крок 1 — часті 1-набори.** Порахуємо підтримку кожного елемента: | 1-набір | Лічильник | Підтримка | Часті? | |---|:--:|:--:|:--:| | $\{\text{Хліб}\}$ | 5 | $0.83$ | так | | $\{\text{Молоко}\}$ | 5 | $0.83$ | так | | $\{\text{Масло}\}$ | 4 | $0.67$ | так | | $\{\text{Яйця}\}$ | 3 | $0.50$ | так | | $\{\text{Кава}\}$ | 1 | $0.17$ | **ні** | Кава відпадає (і більше ніколи не з'явиться в жодному кандидаті — властивість Apriori). Лишаються чотири часті 1-набори. **Крок 2 — кандидати й часті 2-набори.** З'єднання чотирьох частих 1-наборів дає $\binom{4}{2} = 6$ кандидатів; усі їхні 1-підмножини часті, тож відсів нікого не викидає. Рахуємо підтримку: | 2-набір | Лічильник | Підтримка | Часті? | |---|:--:|:--:|:--:| | $\{\text{Хліб}, \text{Молоко}\}$ | 4 | $0.67$ | так | | $\{\text{Хліб}, \text{Масло}\}$ | 3 | $0.50$ | так | | $\{\text{Хліб}, \text{Яйця}\}$ | 3 | $0.50$ | так | | $\{\text{Молоко}, \text{Масло}\}$ | 3 | $0.50$ | так | | $\{\text{Молоко}, \text{Яйця}\}$ | 3 | $0.50$ | так | | $\{\text{Масло}, \text{Яйця}\}$ | 1 | $0.17$ | **ні** | Часті всі, крім $\{\text{Масло}, \text{Яйця}\}$ (вони разом лише в $t_3$). **Крок 3 — кандидати й часті 3-набори.** Тепер працює відсів. З'єднавши часті 2-набори, дістаємо чотири потенційні 3-набори; перевіримо їхні 2-підмножини: | Кандидат | 2-підмножини | Рішення відсіву | |---|---|---| | $\{\text{Хліб}, \text{Молоко}, \text{Масло}\}$ | усі три часті | лишити, рахувати | | $\{\text{Хліб}, \text{Молоко}, \text{Яйця}\}$ | усі три часті | лишити, рахувати | | $\{\text{Хліб}, \text{Масло}, \text{Яйця}\}$ | містить $\{\text{Масло}, \text{Яйця}\}$ — нечасту | **відсіяти** | | $\{\text{Молоко}, \text{Масло}, \text{Яйця}\}$ | містить $\{\text{Масло}, \text{Яйця}\}$ — нечасту | **відсіяти** | Два кандидати відсіяно **без підрахунку** — у цьому й економія. Рахуємо лише два, що лишилися: $$ \operatorname{supp}(\{\text{Хліб}, \text{Молоко}, \text{Масло}\}) = \tfrac{2}{6} \approx 0.33 \ (\text{нечастий}), \quad \operatorname{supp}(\{\text{Хліб}, \text{Молоко}, \text{Яйця}\}) = \tfrac{3}{6} = 0.5 \ (\text{частий}). $$ Отже, єдиний частий 3-набір — $\{\text{Хліб}, \text{Молоко}, \text{Яйця}\}$. З'єднати його нема з чим — часті 4-набори відсутні, алгоритм зупиняється. ![Ґратка наборів елементів наскрізної бази з позначенням частих, нечастих і відсіяних Apriori вузлів; штрихування — надмножини нечастого набору Масло-Яйця](img/l11_lattice.png) ![Рівнева генерація кандидатів Apriori від 1-наборів до 3-наборів із лічильниками та відсіванням за антимонотонністю](img/l11_apriori_levels.png) ### Генерація правил (Приклад 11.6) Візьмемо частий 3-набір $Z = \{\text{Хліб}, \text{Молоко}, \text{Яйця}\}$ ($\operatorname{supp} = 0.5$) і порог $c_{\min} = 0.7$. Розіб'ємо $Z$ на умову й наслідок усіма способами й порахуємо достовірність $\operatorname{conf} = \operatorname{supp}(Z) / \operatorname{supp}(X)$: | Правило $X \Rightarrow Y$ | $\operatorname{supp}(X)$ | $\operatorname{conf}$ | $\ge c_{\min}$? | $\operatorname{lift}$ | |---|:--:|:--:|:--:|:--:| | $\{\text{Хліб}, \text{Молоко}\} \Rightarrow \{\text{Яйця}\}$ | $4/6$ | $0.75$ | так | $1.5$ | | $\{\text{Хліб}, \text{Яйця}\} \Rightarrow \{\text{Молоко}\}$ | $3/6$ | $1.0$ | так | $1.2$ | | $\{\text{Молоко}, \text{Яйця}\} \Rightarrow \{\text{Хліб}\}$ | $3/6$ | $1.0$ | так | $1.2$ | | $\{\text{Яйця}\} \Rightarrow \{\text{Хліб}, \text{Молоко}\}$ | $3/6$ | $1.0$ | так | $1.5$ | | $\{\text{Хліб}\} \Rightarrow \{\text{Молоко}, \text{Яйця}\}$ | $5/6$ | $0.6$ | **ні** | $1.2$ | | $\{\text{Молоко}\} \Rightarrow \{\text{Хліб}, \text{Яйця}\}$ | $5/6$ | $0.6$ | **ні** | $1.2$ | Чотири правила проходять поріг достовірності; усі мають $\operatorname{lift} > 1$ — зв'язки справжні. Найсильніше (за підйомом $1.5$) — $\{\text{Хліб}, \text{Молоко}\} \Rightarrow \{\text{Яйця}\}$: додавши до кошика хліб і молоко, покупець у $1.5$ раза частіше бере яйця. > **Типова помилка (плутати пороги підтримки й достовірності).** Підтримку > перевіряють для **набору** (крок 1, спільна для всіх правил цього набору), а > достовірність — для **напрямку** (крок 2, різна для кожного розбиття). Занизький > $s_{\min}$ породжує лавину випадкових наборів; зависокий — втрачає рідкісні, але > цінні правила. Це компроміс, який підбирають під конкретну задачу. --- ## 11.8 Алгоритм Eclat **Apriori** працює з **горизонтальним** форматом і на кожному рівні робить окремий прохід по всій базі, щоб порахувати підтримку кандидатів. **Eclat** (*Equivalence Class Transformation*) працює з **вертикальним** форматом і уникає повторних проходів: підтримку він дістає **перетином tid-множин**. > **Ключова ідея Eclat.** Для будь-яких наборів > $$ \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-множин його частин — без > звертання до вихідних транзакцій. Eclat будує **префіксне дерево** наборів: корінь — порожній набір, кожен вузол додає до батьківського набору один елемент, а його tid-множину дістають перетином tid-множини батька з tid-множиною нового елемента. Гілки з нечастим набором **не розгалужують** (та сама властивість Apriori: надмножина нечастого — нечаста). ```text Eclat(префікс P, список пар <набір, tidset>, s_min): для кожного елемента i зі списку: вивести P ∪ i.набір з підтримкою |i.tidset| / N # частий набір нащадки <- порожній список для кожного j зі списку, що йде після i: T <- i.tidset ∩ j.tidset # перетин tid-множин якщо |T| / N >= s_min: додати < i.набір ∪ j.набір, T > до нащадки якщо нащадки не порожні: Eclat(P ∪ i.набір, нащадки, s_min) # заглиблення в дерево ``` ### Приклад 11.7 (Eclat вручну) Той самий поріг $s_{\min} = 0.5$ (лічильник $\ge 3$). Часті 1-набори з їхніми tid-множинами (Кава відпала, $|\operatorname{tid}| = 1$): $$ \operatorname{tid}(\text{Хліб}) = \{1,2,3,5,6\}, \ \operatorname{tid}(\text{Молоко}) = \{1,3,4,5,6\}, \ \operatorname{tid}(\text{Масло}) = \{2,3,4,5\}, \ \operatorname{tid}(\text{Яйця}) = \{1,3,6\}. $$ **Гілка «Хліб».** Перетинаємо tid-множину хліба з наступними: $$ \operatorname{tid}(\text{Хліб}) \cap \operatorname{tid}(\text{Молоко}) = \{1,3,5,6\} \ (|\cdot| = 4 \ge 3), $$ $$ \operatorname{tid}(\text{Хліб}) \cap \operatorname{tid}(\text{Масло}) = \{2,3,5\} \ (3), \qquad \operatorname{tid}(\text{Хліб}) \cap \operatorname{tid}(\text{Яйця}) = \{1,3,6\} \ (3). $$ Усі три 2-набори з хлібом часті. Заглиблюємось у під-гілку $\{\text{Хліб}, \text{Молоко}\}$ з tid-множиною $\{1,3,5,6\}$ і перетинаємо її з рештою під-гілок цього вузла: $$ \{1,3,5,6\} \cap \operatorname{tid}(\text{Яйця}) = \{1,3,6\} \ (3 \ge 3) \ \Rightarrow\ \{\text{Хліб}, \text{Молоко}, \text{Яйця}\} \ \text{частий}. $$ Це той самий частий 3-набір, що його знайшов Apriori, — але дістали ми його **перетином множин**, а не проходом по базі. Гілка «Масло» одразу дає $\operatorname{tid}(\text{Масло}) \cap \operatorname{tid}(\text{Яйця}) = \{3\}$ (потужність $1 < 3$) — нечастий 2-набір, який не розгалужують. ![Префіксне дерево Eclat наскрізної бази з tid-множинами у вузлах та обчисленням підтримки через їх перетин](img/l11_eclat_tree.png) > **Apriori проти Eclat.** Обидва знаходять **ті самі** часті набори; різниця — у > способі рахувати підтримку. Apriori (горизонтальний, «завширшки») робить прохід > по базі на кожному рівні — простий і ощадливий за пам'яттю. Eclat > (вертикальний, «завглибшки») зводить підрахунок до перетинів tid-множин — > швидший, коли ці множини малі, але тримає їх у пам'яті. На щільних базах > tid-множини великі, і Eclat програє за пам'яттю; на розріджених — виграє за > швидкістю. --- ## Застосування в аналітиці даних - **Рекомендаційні системи й розкладка.** Правила «з $X$ беруть $Y$» — основа підказок «з цим товаром купують…», кросселінгу, розкладки на полицях і «якорів» акцій; підйом відсіває тривіальні пари поширених товарів. - **Виявлення аномалій і атак.** У кібербезпеці правила над ознаками подій дають сигнатури; порушення сталого правила — привід для тривоги. - **Медичні та біологічні асоціації.** Спільні симптоми/діагнози чи гени, що експресуються разом; підйом і переконливість відрізняють справжній зв'язок від збігу через поширеність. - **Скорочення простору пошуку.** Властивість Apriori — загальний прийом «якщо частина не підходить, ціле теж ні» — застосовний і поза асоціативними правилами (пошук частих підграфів, послідовностей). ## Підсумок - **Пошук асоціативних правил** — навчання без учителя, що шукає сталі спільні появи у формі «якщо $X$, то $Y$»; це **зв'язок**, а не причинність. - Дані — **транзакційна база** над елементами $I$; її задають **горизонтально** (транзакція $\to$ набір) або **вертикально** (елемент $\to$ **tid-множина**). - **Асоціативне правило** $X \Rightarrow Y$ будують для наборів, що не перетинаються ($X \cap Y = \varnothing$). - **Чотири міри:** підтримка $\operatorname{supp}(X) = |\{t : X \subseteq t\}| / N$ (поширеність); достовірність $\operatorname{conf} = \operatorname{supp}(X \cup Y)/\operatorname{supp}(X)$ (надійність напрямку); підйом $\operatorname{lift} = \operatorname{conf}/\operatorname{supp}(Y)$ (сила зв'язку, симетрична; $>1$ — притягання); переконливість $\operatorname{conv} = (1 - \operatorname{supp}(Y))/(1 - \operatorname{conf})$ (частота порушень; $\to \infty$ при $\operatorname{conf} = 1$). - **Цікаві правила** долають пороги $s_{\min}$ і $c_{\min}$; підйом і переконливість упорядковують їх і прибирають оманливо-достовірні. - **Apriori** спирається на **антимонотонність** (надмножина нечастого — нечаста): будує кандидатів з'єднанням частих $(k{-}1)$-наборів, відсіває тих, у кого є нечаста підмножина, і лише решту рахує проходом по базі. У наскрізному прикладі ($s_{\min} = 0.5$) єдиний частий 3-набір — $\{\text{Хліб}, \text{Молоко}, \text{Яйця}\}$. - **Eclat** дає ті самі набори, але рахує підтримку **перетином tid-множин** у префіксному дереві завглибшки; вигідний на розріджених базах. ## Вправи ### Для розігріву 1. За наскрізною базою обчисліть $\operatorname{supp}(\{\text{Масло}\})$ і $\operatorname{supp}(\{\text{Хліб}, \text{Масло}\})$, а тоді достовірність правила $\{\text{Масло}\} \Rightarrow \{\text{Хліб}\}$. 2. Поясніть різницю між достовірністю й підйомом. Чому правило з достовірністю $0.8$ може мати підйом менший за $1$? Наведіть приклад із лекції. 3. Сформулюйте властивість Apriori двома рівносильними способами (через підмножини частого набору й через надмножини нечастого) і поясніть, як вона економить перебір. ### Стандартні 4. Для правила $\{\text{Масло}\} \Rightarrow \{\text{Молоко}\}$ обчисліть усі чотири міри (підтримку, достовірність, підйом, переконливість). Порівняйте підйом і переконливість із правилом $\{\text{Молоко}\} \Rightarrow \{\text{Яйця}\}$ з Прикладу 11.4: яке правило змістовніше? 5. Виконайте Apriori на наскрізній базі з порогом $s_{\min} = \tfrac{1}{3}$ (лічильник $\ge 2$). Які нові часті 2- і 3-набори з'являться порівняно з Прикладом 11.5? Чи стане частим $\{\text{Хліб}, \text{Молоко}, \text{Масло}\}$? 6. Побудуйте tid-множини й методом Eclat перевірте, що $\{\text{Молоко}, \text{Масло}\}$ частий за $s_{\min} = 0.5$, а $\{\text{Молоко}, \text{Масло}, \text{Яйця}\}$ — ні, не рахуючи транзакцій безпосередньо. ### Підвищеної складності 7. Доведіть симетричність підйому: $\operatorname{lift}(X \Rightarrow Y) = \operatorname{lift}(Y \Rightarrow X)$ — виходячи з формули через підтримки. Чому достовірність цієї симетрії **не** має? 8. Покажіть, що для правила з фіксованою умовою $X$ підйом і переконливість досягають максимуму одночасно з достовірністю. Що відбувається з переконливістю, коли $\operatorname{conf} \to 1$, і як це тлумачити? 9. Оцініть, скільки кандидатів довелося б порахувати «в лоб» (усі 2- і 3-набори над п'ятьма елементами) без відсіву, і скільки насправді порахував Apriori у Прикладі 11.5. У скільки разів відсів скоротив роботу на рівні 3-наборів? Запропонуйте також, як подати результат Прикладу 11.6 **графом цікавих правил**: які вершини й ребра, чим кодувати підтримку та підйом.