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

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

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

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

Визначення

Приклад бази даних з 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

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

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

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

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

${\displaystyle X\Rightarrow Y}$, де ${\displaystyle X,Y\subseteq I}$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Впевненість

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

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

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

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

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

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

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

Ліфт

^[en] правила визначається так:

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

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

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

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

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

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

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

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

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

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

Процес

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

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

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

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

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

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

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

Примітки

1. Piatetsky-Shapiro, Gregory (1991), Discovery, analysis, and presentation of strong rules, in Piatetsky-Shapiro, Gregory; and Frawley, William J.; eds., Knowledge Discovery in Databases, AAAI/MIT Press, Cambridge, MA.
2. Agrawal, R.; Imieliński, T.; Swami, A. (1993). Mining association rules between sets of items in large databases. Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93. с. 207. doi:10.1145/170035.170072. ISBN .
3. Tan, Pang-Ning; Kumar, Vipin; and Srivastava, Jaideep; [Selecting the right objective measure for association analysis, https://cse.msu.edu/%7Eptan/papers/IS.pdf [ 10 серпня 2017 у Wayback Machine.]] Information Systems, 29(4):293-313, 2004
4. Michael Hahsler (2015). A Probabilistic Comparison of Commonly Used Interest Measures for Association Rules. http://michael.hahsler.net/research/association_rules/measures.html [ 2 серпня 2018 у Wayback Machine.]
5. Hahsler, Michael (2005). (PDF). Journal of Statistical Software. Архів оригіналу (PDF) за 30 квітня 2019.
6. Hipp, J.; Güntzer, U.; Nakhaeizadeh, G. (2000). Algorithms for association rule mining --- a general survey and comparison. ACM SIGKDD Explorations Newsletter. 2: 58. doi:10.1145/360402.360421.
7. Tan, Pang-Ning; Michael, Steinbach; Kumar, Vipin (2005). (PDF). Introduction to Data Mining. Addison-Wesley. ISBN . Архів оригіналу (PDF) за 19 вересня 2017. Процитовано 3 серпня 2018.
8. Pei, Jian; Han, Jiawei; and Lakshmanan, Laks V. S.; Mining frequent itemsets with convertible constraints, in Proceedings of the 17th International Conference on Data Engineering, April 2–6, 2001, Heidelberg, Germany, 2001, pages 433—442
9. Agrawal, Rakesh; and Srikant, Ramakrishnan; Fast algorithms for mining association rules in large databases [ 25 лютого 2015 у Wayback Machine.], in Bocca, Jorge B.; Jarke, Matthias; and Zaniolo, Carlo; editors, Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), Santiago, Chile, September 1994, pages 487—499
10. Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering. 12 (3): 372—390. doi:10.1109/69.846291.
11. Webb, Geoffrey I. (2007); Discovering Significant Patterns, Machine Learning 68(1), Netherlands: Springer, pp. 1-33 online access [ 3 серпня 2018 у Wayback Machine.]
12. Gionis, Aristides; ; Mielikäinen, Taneli; and Tsaparas, Panayiotis; Assessing Data Mining Results via Swap Randomization, ACM Transactions on Knowledge Discovery from Data (TKDD), Volume 1, Issue 3 (December 2007), Article No. 14