Навчання асоціативних правил

Частина з циклу
Машинне навчання та добування даних
Парадигми Кероване навчання Некероване навчання Інтерактивне навчання Пакетне навчання Метанавчання Напівкероване навчання Самокероване навчання Навчання з підкріпленням Навчання на основі правил Квантове машинне навчання
Задачі Класифікація Породжувальна модель Регресія Кластерування Знижування розмірності Оцінювання густини Виявляння аномалій Очищування даних АвтоМН Асоціативні правила Семантичний аналіз Структурове передбачування Конструювання ознак Навчання ознак Навчання ранжуванню Виведення граматик Навчання онтологій Мультимодальне навчання
Кероване навчання (класифікація • регресія) Ансамблі Випадковий ліс Бутстрепова агрегація Підсилювання Градієнтне підсилювання AdaBoost Дерева рішень MARS CART Доречно-векторна машина k-сусідів Лінійна регресія Логістична регресія Лінійний розділювальний аналіз Наївний баєсів класифікатор Перцептрон Підмайстрове навчання Опорно-векторна машина Штучні нейронні мережі
Кластерування BIRCH CURE Ієрархічне k-середніх Нечітке Очікування-максимізація DBSCAN OPTICS Спектральне Зсув середнього
Знижування розмірності Факторний аналіз Метод незалежних компонент Канонічна кореляція Дискримінантний аналіз Метод головних компонент Власний узагальнений розклад Розклад невід'ємних матриць t-розподілене вкладення стохастичної близькості Навчання розріджених словників
Структурове передбачування Графові моделі Баєсова мережа Прихована марковська модель Умовне випадкове поле
Виявляння аномалій RANSAC k-НС Коефіцієнт локального відхилення Відстань Кука Ізоляційний ліс
Штучна нейронна мережа Автокодувальник Когнітивні обчислення Глибоке навчання DeepDream Нейронна мережа прямого поширення Рекурентна нейронна мережа ДКЧП ВРВ МВС Резервуарне обчислення Обмежена машина Больцмана ГЗМ Дифузійна модель Самоорганізаційна карта Згорткова нейронна мережа U-Net Трансформер Зоровий Спайкова нейронна мережа Мемтранзистор Електрохімічна ПДД (ECRAM)
Навчання з підкріпленням Q-навчання SARSA Метод часових різниць Багатоагентне навчання з підкріпленням Гра проти себе
Навчання з людьми Активне навчання (машинне навчання) Краудсорсинг Людина-в-циклі
Діагностування моделей Крива спроможності навчатися
Математичні засади Ядрові машини Компроміс зсуву та дисперсії Ймовірнісно приблизно коректне навчання Мінімізація емпіричного ризику Оккамове навчання Регуляризація LASSO Тихонова Еластично-сіткова Статистичне навчання Теорія Вапника — Червоненкіса Теорія обчислювального навчання
Місця машинного навчання ECML PKDD NeurIPS ICML ICLR IJCAI ML JMLR
Пов'язані статті Глосарій штучного інтелекту Список наборів даних для досліджень з машинного навчання Перелік понять машинного навчання

Навчання асоціативних правил — метод машинного навчання на основі правилах для знаходження цікавих відношень між змінними у великих базах даних. Метою є ідентифікація сильних правил, які виявляються в базах даних з використанням деяких вимірів цікавості.

Ґрунтуючись на концепції сильних правил, Ракеш Агравал, Томаш Імієлінський та Арун Свамі запровадили асоціативні правила для виявлення закономірностей між продажами продуктів, які фіксуються через торгові точки (англ. point-of-sale, POS) у супермаркетах і всі ці транзакції зберігаються у величезній базі даних. Наприклад, правило $\{{\text{цибуля, картопля}}\}\Rightarrow \{{\text{смажена картопля}}\}$, що містяться в даних про продажі супермаркету, вказує на те, що якщо споживач купує цибулю та картоплю разом, то, ймовірно, також буде придбано олію для смаження картопельки з цибулею. Така інформація може бути використана як підґрунтя для прийняття рішень щодо маркетингової діяльності, наприклад, рекламних цін або вибору місць для розташування товарів.

Окрім вищезгаданого прикладу з аналізу ринкових кошиків, асоціативні правила застосовуються сьогодні у багатьох областях, включаючи Web mining, виявлення вторгнень, безперервне виробництво та біоінформатику. На відміну від пошуку шаблону послідовності виведення послідовності, навчання асоціативних правил, як правило, не враховує порядок елементів у межах транзакції чи транзакцій.

Визначення

Приклад бази даних з 5 продажами та 5 предметами

ID операції	молоко	хліб	масло	пиво	підгузники
1	1	1	0	0	0
2	0	0	1	0	0
3	0	0	0	1	1
4	1	1	1	0	0
5	0	1	0	0	0

Відповідно до визначення запропонованого Агравалем, Імієлінські, Свамі задача пошуку асоціативного правила визначається так: Нехай $I=\{i_{1},i_{2},\ldots ,i_{n}\}$ — множина $n$ двійкових атрибутів, яка називається предмети.

Нехай $D=\{t_{1},t_{2},\ldots ,t_{m}\}$ — множина операцій або транзакцій, яка називається база даних.

Кожна транзакція в $D$ має унікальний номер — ID і містить підмножину предметів $I$.

Правило визначається як імплікація форми:

$X\Rightarrow Y$, де $X,Y\subseteq I$.

Аграваль, Імієлінські та Свамі визначали правило тільки між множиною і окремими предметами, $X\Rightarrow i_{j}$ для $i_{j}\in I$.

Кожне правило складається з двох різних множин предметів, також відомих як набори предметів $X$ та $Y$, де $X$ називається попередником (англ. antecedent) або лівостороннім, а $Y$ наступний (англ. consequent) або правостороннім.

Для пояснення концепції, розглянемо приклад пов'язаний з супермаркетом. Множина предметів $I=\{{\text{молоко, хліб, масло, пиво, підгузники}}\}$ і в таблиці зображена невелика база даних, що містить предмети, де в кожному рядку значення 1 означає наявність елемента у відповідній транзакції, а значення 0 — відсутність елемента в цій транзакції.

Приклад правила для супермаркету може бути $\{{\text{масло, хліб}}\}\Rightarrow \{{\text{молоко}}\}$, а це означає, що, якщо купили масло та хліб, то також придбають молоко.

Варто зауважити, що цей приклад дуже маленький. Для застосувань на практиці, правило повинно виконуватись для декількох сотень транзакцій, перш ніж його можна буде вважати статистично значущим, а набори даних часто містять тисячі або мільйони транзакцій.

Корисні концепції

Для відбору цікавих правил з множини усіх можливих правил, накладають обмеження на різні способи вимірювання значущості та інтересу. Найбільш відомими обмеженнями є мінімальні пороги затребуваності та довіри.

Нехай $X$ буде набором предметів, $X\Rightarrow Y$ — асоціативне правило і $T$ — множина транзакцій.

Більше вимірювань представлені і порівняні Таном та іншими, як і Гахслером. Пошук методів, які можуть моделювати те, що користувач знає (і використання цих моделей як заходи цікавість), наразі активно досліджується під назвою «суб'єктивна зацікавленість» (англ. Subjective Interestingness).

Затребуваність

Затребуваність (англ. Support) вказує наскільки часто набір предметів з'являється у наборі даних.

Затребуваність $X$ відносно $T$ визначається як частка транзакцій $t$ у наборі даних, які містять підмножиною $X$.

$\mathrm {supp} (X)={\frac {|\{t\in T;X\subseteq t\}|}{|T|}}$

У наведеному вище прикладі, набір предметів $X=\{{\text{пиво, підгузники}}\}$ має затребуваність $1/5=0.2$, бо зустрічається у 20 % всіх транзакцій (1 з 5 транзакцій). Аргументом $\mathrm {supp} ()$ є сукупність передумов, і, таким чином, при збільшенні кількості предметів стає більш жорсткою умовою.

Впевненість

Впевненість (англ. Confidence) вказує на те, як часто виконується правило.

Значення впевненості у правилі $X\Rightarrow Y$ відносно множини транзакцій $T$ є часткою транзакцій, які містять $X$, який також містить $Y$.

Впевненість визначається так:

$\mathrm {conf} (X\Rightarrow Y)=\mathrm {supp} (X\cup Y)/\mathrm {supp} (X)$

Наприклад, правило $\{{\text{масло, хліб}}\}\Rightarrow \{{\text{молоко}}\}$ має впевненість $0.2/0.2=1.0$ у базі, що означає, що для 100 % операцій, які містять масло та хліб, правило істинне (у 100 % випадків споживач, який купив масло та хліб, так само купив і молоко).

Зауважимо, що $\mathrm {supp} (X\cup Y)$ означає затребуваність об'єднання предметів з X та Y. Це може трохи заплутати, оскільки ми зазвичай думаємо про ймовірність подій, а не про набори предметів. Ми можемо переписати $\mathrm {supp} (X\cup Y)$ як імовірність $P(E_{X}\cap E_{Y})$, де $E_{X}$ та $E_{Y}$ — це події, в яких транзакція містить набори $X$ та $Y$, відповідно.

Таким чином, довіру можна інтерпретувати як оцінку умовної ймовірності $P(E_{Y}|E_{X})$, ймовірності знайти наступника у транзакції, якщо вона містить попередника.

Ліфт

Ліфт правила визначається так:

$\mathrm {lift} (X\Rightarrow Y)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)\times \mathrm {supp} (Y)}}$

або співвідношення спостережуваної затребуваності до очікуваного, якщо б Х та Y були незалежними.^{[джерело?]}

Наприклад, правило $\{{\text{молоко, хліб}}\}\Rightarrow \{{\text{масло}}\}$ має ліфт ${\frac {0.2}{0.4\times 0.4}}=1.25$.

Якщо правило має ліфт 1, це означає, що ймовірності появи попередника та наступника є незалежними одна від одної. Коли дві події є незалежними одна від одної, то й не можна вивести правила за участю цих двох подій.

Якщо ліфт > 1, це вказує на те, наскільки ці дві ситуації залежать одна від одної, і робить ці правила потенційно корисними для прогнозування таких послідовностей у майбутніх наборах даних.

Якщо ліфт < 1, це вказує на те, що предмети замінюють один одного. Це означає, що наявність одного товару негативно впливає на наявність іншого товару, і навпаки.

Значення ліфта полягає в тому, що він враховує як впевненість, так і весь набір даних.

Переконливість

Переконливість (англ. Conviction) правила визначається як $\mathrm {conv} (X\Rightarrow Y)={\frac {1-\mathrm {supp} (Y)}{1-\mathrm {conf} (X\Rightarrow Y)}}$.

Наприклад, правило $\{{\text{молоко, хліб}}\}\Rightarrow \{{\text{масло}}\}$ має переконливість ${\frac {1-0.4}{1-0.5}}=1.2$, що може бути інтерпретовано як відношення очікуваної частоти того, що X трапляється без Y (тобто частота того, що правило робить неправильне передбачення), якщо Х та Y незалежні, поділене на частоту спостережень невірних передбачень. У цьому прикладі значення переконливості 1.2 показує, що правило $\{{\text{молоко, хліб}}\}\Rightarrow \{{\text{масло}}\}$ буде правильним на 20 % частіше (у 1,2 рази частіше), якби зв'язок між X та Y був чисто випадковим.

Процес

Ґратка частот наборів предметів, в якій колір прямокутника вказує на те, скільки транзакцій містять предмети. Зазначимо, що нижчі рівні ґратки можуть містити не більше мінімальної кількості предметів своїх батьків; наприклад, {ac} може містити щонайбільше $min(a,c)$. Це називається «властивістю спадного змикання».

Асоціативні правила повинні відповідати мінімальній затребуваності та мінімальній впевненості, які визначаються користувачем одночасно. Утворення асоціативних правил, зазвичай, поділяється на два окремих кроки:

1. Порогове значення мінімальної затребуваності використовується для знаходження всіх частот предметів у базі даних.
2. Обмеження на мінімальну впевненість застосовується до частот наборів предметів для утворення правил.

Хоча другий крок є простим, перший крок потребує більшої уваги.

Пошук усіх частот наборів предметів у базі даних складний, оскільки він включає в себе пошук усіх можливих наборів, тобто усіх комбінацій предметів. Множина можливих комбінацій є булеаном $I$ та за розміром буде $2^{n}-1$ (за винятком порожнього набору, який не є набором предметів). Хоча кількість підмножин експоненціально зростає залежно від кількості предметів $n$ в $I$, ефективний пошук можливий за допомогою властивості спадного змикання (англ. downward-closure) значущості (також називається анти-монотонністю), що гарантує, що для частих наборів предметів всі його підмножини також є частими, і тому не рідкісні набори предметів можуть бути підмножиною частих наборів предметів. Використовуючи цю властивість, ефективні алгоритми (наприклад, Apriori та Eclat) можуть знаходити всі часті набори предметів.

Статистично обгрунтовані асоціації

Одним з обмежень стандартного підходу до виявлення асоціацій є те, що, перебираючи величезну кількість можливих асоціацій для пошуку колекцій предметів, які можуть бути пов'язані, існує великий ризик виявлення багатьох фальшивих асоціацій. Це набори предметів, що збігаються випадково. Наприклад, припустимо, ми розглядаємо колекцію з 10000 предметів і шукаємо правила, що містять два предмети в лівій частині та 1 предмет у правій частині. Існує приблизно 1 000 000 000 000 таких правил. Якщо ми застосуємо статистичну перевірку для незалежності з рівнем значущості 0.05, це означає, що шанс прийняти правило, якщо немає асоціації, є лише 5%. Якщо ми вважатимемо, що немає об'єднань, ми все ж повинні розраховувати на пошук 50 000 000 000 правил. Виявлення статистично обґрунтованої асоціації контролює цей ризик, і в більшості випадків зменшую ризик виявлення будь-яких хибних асоціацій відповідно до визначеного користувачем рівня значущості.