Лекція 11. Пошук асоціативних правил. Алгоритми Apriori та Eclat #

Огляд #

У Лекції 9 та Лекції 10 ми розв’язували задачі кластеризації — це вже було навчання без учителя (англ. unsupervised learning): даним не приписано жодної цільової позначки, і метод сам шукає в них структуру. Пошук асоціативних правил належить до тієї самої родини, але шукає структуру іншого типу: не групи схожих об’єктів, а сталі спільні появи ознак — набори елементів, що систематично трапляються разом, і залежності «якщо є одне — імовірно, є й інше».

Класичний приклад — аналіз ринкового кошика (англ. market basket analysis): за чеками супермаркету знайти, які товари купують укупі. Правило «хто бере пелюшки, часто бере й пиво» — не прогноз для конкретного покупця (як у класифікації), а виявлена закономірність усієї бази транзакцій. У цій лекції ми означимо асоціативне правило, уведемо чотири міри інтересовності (підтримка, достовірність, підйом, переконливість), навчимося відбирати цікаві правила й розберемо два алгоритми пошуку частих наборів — Apriori (горизонтальний, з відсіванням кандидатів) та Eclat (вертикальний, на перетинах tid-множин).

Практичний бік. Підтримку, достовірність і підйом ви обчислюватимете «руками» й виконаєте Apriori вручну, а потім реалізуєте пошук правил програмою в Лабораторній роботі 11.

Наскрізний приклад лекції — маленька транзакційна база невеликого магазину: шість чеків над п’ятьма товарами.

Тут $N = 6$ транзакцій, а множина всіх товарів — $I = \{\text{Хліб}, \text{Молоко}, \text{Масло}, \text{Яйця}, \text{Кава}\}$.

11.1 Задача пошуку асоціативних правил #

Означення (пошук асоціативних правил). Пошук асоціативних правил (англ. association rule mining) — це напрям машинного навчання, присвячений знаходженню в даних сталих залежностей у формі правил «якщо $A$, то $B$», де $A$ і $B$ — набори елементів (подій), що часто трапляються разом.

Три риси відрізняють цю задачу від класифікації (Лекції 6–8):

• Немає виділеної цільової ознаки. Будь-який елемент може опинитися як у лівій, так і в правій частині правила; ми не передбачаємо один стовпець за іншими, а шукаємо всі помітні зв’язки одразу.
• Результат — описовий, а не прогнозний. Правило описує закономірність наявних даних, а не виносить вирок про новий об’єкт.
• Зв’язок — не причинність. «Якщо $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-множин його елементів — на цьому й побудовано алгоритм 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$: у нашій базі це правило не має жодного винятку.

Зведемо всі чотири міри для трьох правил (усі числа перевірено обчисленням):

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$).

Пошук цікавих правил природно розпадається на два кроки:

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$, а його товщину чи колір пов’язують із мірою (підтримкою, достовірністю, підйомом). Так стають видимими центральні товари (багато вихідних ребер), взаємні пари й ізольовані елементи. Такий граф цікавих правил — стандартний спосіб подати результат аналізу замовникові.

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$

Практичний наслідок: щойно набір виявився нечастим, усі його надмножини можна відкинути не рахуючи — саме це економить роботу.

Кроки алгоритму #

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-набори. Порахуємо підтримку кожного елемента:

Кава відпадає (і більше ніколи не з’явиться в жодному кандидаті — властивість Apriori). Лишаються чотири часті 1-набори.

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

Часті всі, крім $\{\text{Масло}, \text{Яйця}\}$ (вони разом лише в $t_3$).

Крок 3 — кандидати й часті 3-набори. Тепер працює відсів. З’єднавши часті 2-набори, дістаємо чотири потенційні 3-набори; перевіримо їхні 2-підмножини:

Два кандидати відсіяно без підрахунку — у цьому й економія. Рахуємо лише два, що лишилися:

$$\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-набори відсутні, алгоритм зупиняється.

Генерація правил (Приклад 11.6) #

Візьмемо частий 3-набір $Z = \{\text{Хліб}, \text{Молоко}, \text{Яйця}\}$ ($\operatorname{supp} = 0.5$) і порог $c_{\min} = 0.7$. Розіб’ємо $Z$ на умову й наслідок усіма способами й порахуємо достовірність $\operatorname{conf} = \operatorname{supp}(Z) / \operatorname{supp}(X)$:

Чотири правила проходять поріг достовірності; усі мають $\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: надмножина нечастого — нечаста).

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-набір, який не розгалужують.

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 графом цікавих правил: які вершини й ребра, чим кодувати підтримку та підйом.

Lectures/DA-L11.md · 43.3 KB · updated 2026-08-05 09:54