Міністерство освіти і науки
Національний університет “Львівська політехніка”
Кафедра “Автоматизовані системи управління”
Звіт
до лабораторної роботи № 3
з дисципліни «Методи та системи штучного інтелекту»
на тему «Вступ до аналізу асоціативних правил»
Короткі теоретичні відомості
Останнім часом задачі пошуку нових знань у великих базах сирих даних стають все більш популярними та актуальними. Одним із популярних методів виявлення знань став алгоритм пошуку так званих асоціативних правил (Association Rules). Суть задачі полягає в знаходження наборів об’єктів, які зустрічаються найчастіше серед всієї множини ймовірних наборів об’єктів. Першим застосуванням такої задачі був аналіз тенденцій в поведінці покупців у супермаркетах. При цьому аналізувались дані про всі здійснені покупки, які кожен покупець кладе у свій кошик, та одержувалась інформація про те, які товари переважно купуються разом, в якій послідовності, якими категоріями покупців, в які періоди часу, тощо. Такого роду знання дозволяють ефективно планувати закупку товарів у магазин, розробляти ефективні рекламні кампанії та розкладати товар таким чином, щоб провокувати покупців на різноманітні покупки.
Наприклад, з набору товарів, які купуються в магазинах, можна виділити такі набори товарів, що переважно купуються одночасно:
{чіпси, пиво};
{вода, горіхи};
{чай, печиво};
Тощо.
Таким чином, можна зробити висновок про те, що якщо купуються чіпси чи горіхи, то, як правило, купуються, пиво чи вода, відповідно. Отже, можна розмістити ці товари поруч на прилавках, об’єднати їх в один пакет зі знижкою чи здійснити інші дії.
Задача пошуку асоціативних правил є актуальною не лише у сфері торгівлі. Наприклад, в сефрі обслуговування цікавою є інформація про те, якими послугами клієнти користуються в сукупності. Для одержання цієї інформації вирішується задача аналізу даних про послуги, якими користується один клієн протягом певного часу. Це допомагає визначити, наприклад, як найбільш вигідно сформувати пакети послуг для клієнтів.
В медицині аналізуватись можуть симптоми та хвороби пацієнтів. В цьому випадку знання про те, які поєднання хворів та симптомів зустрічаються найчастіше, дозволяють в майбутньому ставити правильні діагнози.
Визначення
Щоб дати означення асоціативного правила, будемо вважати, що існує база даних, якій містяться записи про всі здійснені покупки в супермаркеті. Кожен запис називається транзакцією і включає дані про набір товарів, куплених одним покупецем за один візит. Таку транзакцію ще називаю ринковим кошиком.
Нехай / – це вся множина товарів з супермаркету, що називаються елементами.
Приклад:
Ідентифікатор
Найменування товару
Ціна
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) набору / та позначається /:
/.
Можна підтримку рахувати у відсотках (...
