Вступ до аналізу асоціативних правил (стр. 1 из 4)
Вступ до аналізу асоціативних правил
Останнім часом задачі пошуку нових знань у великих базах сирих даних стають все більш популярними та актуальними. Одним із популярних методів виявлення знань став алгоритм пошуку так званих асоціативних правил (Association Rules). Суть задачі полягає в знаходження наборів об’єктів, які зустрічаються найчастіше серед всієї множини ймовірних наборів об’єктів. Першим застосуванням такої задачі був аналіз тенденцій в поведінці покупців у супермаркетах. При цьому аналізувались дані про всі здійснені покупки, які кожен покупець кладе у свій кошик, та одержувалась інформація про те, які товари переважно купуються разом, в якій послідовності, якими категоріями покупців, в які періоди часу, тощо. Такого роду знання дозволяють ефективно планувати закупку товарів у магазин, розробляти ефективні рекламні кампанії та розкладати товар таким чином, щоб провокувати покупців на різноманітні покупки.
Наприклад, з набору товарів, які купуються в магазинах, можна виділити такі набори товарів, що переважно купуються одночасно:
- {чіпси, пиво};
- {вода, горіхи};
- {чай, печиво};
- Тощо.
Таким чином, можна зробити висновок про те, що якщо купуються чіпси чи горіхи, то, як правило, купуються, пиво чи вода, відповідно. Отже, можна розмістити ці товари поруч на прилавках, об’єднати їх в один пакет зі знижкою чи здійснити інші дії.
Задача пошуку асоціативних правил є актуальною не лише у сфері торгівлі. Наприклад, в сфері обслуговування цікавою є інформація про те, якими послугами клієнти користуються в сукупності. Для одержання цієї інформації вирішується задача аналізу даних про послуги, якими користується один клієнт протягом певного часу. Це допомагає визначити, наприклад, як найбільш вигідно сформувати пакети послуг для клієнтів.
В медицині аналізуватись можуть симптоми та хвороби пацієнтів. В цьому випадку знання про те, які поєднання хворів та симптомів зустрічаються найчастіше, дозволяють в майбутньому ставити правильні діагнози.
Визначення
Щоб дати означення асоціативного правила, будемо вважати, що існує база даних, якій містяться записи про всі здійснені покупки в супермаркеті. Кожен запис називається транзакцією і включає дані про набір товарів, куплених одним покупцем за один візит. Таку транзакцію ще називаю ринковим кошиком.
Нехай
– це вся множина товарів з супермаркету, що називаються елементами.Приклад[1]:
| Ідентифікатор | Найменування товару | Ціна |
| 0 | Шоколад | 30.00 |
| 1 | Чіпси | 12.00 |
| 2 | Кокоси | 10.00 |
| 3 | Вода | 4.00 |
| 4 | Пиво | 14.00 |
| 5 | Горіхи | 15.00 |
Тобто вся множина елементів (їх загальна кількість рівна
) 
буде: 
.Кожна транзакція
описується як: 
. Приклади транзакцій: 
Набір усіх відомих транзакцій (загальна їх кількість нехай рівна
) позначаємо як 
: 
.Нехай для нашого прикладу:
Тоді множину
можемо представити у вигляді: | № транзакції | Ідентифікатор товару | Найменування товару | Ціна |
| 0 | 1 | Чіпси | 12.00 |
| 0 | 3 | Вода | 4.00 |
| 0 | 4 | Пиво | 14.00 |
| 1 | 2 | Кокоси | 10.00 |
| 1 | 3 | Вода | 4.00 |
| 1 | 5 | Горіхи | 15.00 |
| 2 | 5 | Горіхи | 15.00 |
| 2 | 2 | Кокоси | 10.00 |
| 2 | 1 | Чіпси | 12.00 |
| 2 | 2 | Кокоси | 10.00 |
| 2 | 3 | Вода | 4.00 |
| 3 | 2 | Кокоси | 10.00 |
| 3 | 5 | Горіхи | 15.00 |
| 3 | 2 | Кокоси | 10.00 |
Множину транзакцій, в яку входить об’єкт
позначимо як: 
.Наприклад, множина транзакцій, в які входить елемент «вода»:
Деякий довільний набір елементів позначимо так:
. Набір, що складається з 
об’єктів називається -елементним набором. Приклад 2-елементного набору: 
.Множину транзакцій, в яку входить набір
, позначимо 
: 
.В даному прикладі:
.Відношення кількості транзакцій, в які входить
, до загальної кількості транзакцій називається підтримкою (support) набору та позначається 
: 
.Можна підтримку рахувати у відсотках (тоді треба помножити на 100%).
Для набору
підтримка рівна 0.5 або 50%, так як цей набір входить у дві транзакції (з номерами 1 та 2), а всього транзакцій є 4.При пошуку аналітик може вказати мінімальне значення підтримки для наборів, що його цікавлять –
.Набір називається частим, якщо значення його підтримки є більшим за вказане мінімальне значення, задане користувачем:
.Таким чином, при пошуку асоціативних правил необхідно знайти множину всіх частих наборів:
.В даному прикладі частими наборами при
є такі: 
З іншого боку, важливо не лише знайти часті набори, але виявити правила «якщо....., то...». Наприклад, в даному прикладі можна досліджувати, наскільки правдивим є правило: якщо «кокоси», то «вода». Тобто важливо не просто знати. Що ці ва елементи часто знаходяться в одному наборі, але й вміти прогнозувати, що при покупці «кокосів» ймовірно буде покупка «води» або навпаки.
Розіб’ємо наш досліджуваний наборі на два піднабори:
та 
. Наприклад, набір будемо розглядати як: 
та 
, тобто 
. Тоді асоціативним правилом можна назвати імплікацію[2]: 
, де 
. Правило має підтримку:
, 
тобто
– це відсоток зі всіх транзакцій , що містять і набір , і набір (тобто містять набір ). 
Бо, як було вже згадано вище, з чотирьох транзакцій дві містять і «Кокоси» і «Воду».