Інтелектуальна обробка даних. ЛР №4 Асоціативні правила.

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”

“Асоціативні правила”

Методичні вказівки

до лабораторної роботи №4

з курсу “Інтелектуальна обробка даних”

для студентів напрямку

8.05010103, 7.05010103“Системне проектування”

Затверджено

на засіданні кафедри “Системи автоматизованого проектування” Протокол № 1 від 22.08.2011

Львів 2011

“Асоціативні правила”. Методичні вказівки до виконання лабораторної роботи №4 з курсу: “Інтелектуальна обробка даних” для 8.05010103, 7.05010103“Системне проектування”.

Укладачі: Керницький А.Б., др.інж, доц.

Денисюк П.Ю., канд.техн.наук, доц.

Мельник М.Р., канд.техн.наук, доц.

Відповідальний за випуск: Ткаченко С.П., канд.техн.наук, доц.

Рецензенти: Каркульовський В.І., канд.техн.наук, доц.

Яковина В.С., канд.фіз.-мат.наук, доц.

1. Мета роботи

Ознайомитися з асоціативними правилами, виконати індивідуальне завдання, зробити висновки.

2.Короткі теоретичні відомості

2.1. Введення в аналіз асоціативних правил

Останнім часом неухильно росте інтерес до методів «виявлення знань в базах даних» (knowledge discovery in databases). Значні об'єми сучасних баз даних викликали стійкий попит на нові алгоритми аналізу даних. Одним з популярних методів виявлення знань стали алгоритми пошуку асоціативних правил.

Асоціативні правила дозволяють знаходити закономірності між зв'язаними подіями. Прикладом такого правила, служить твердження, що покупець, що купує 'Хліб', придбає і 'Молоко' з вірогідністю 75%. Перший алгоритм пошуку асоціативних правил AIS був розроблений в 1993 році співробітниками дослідницького центру IBM Almaden. З цієї піонерської роботи зріс інтерес до асоціативних правил; пік дослідницьких робіт в цій області припав на середину 90-х років минулого століття, і з тих пір щороку з'являлося по декілька алгоритмів.

2.2. Асоціативні правила (association rules)

Вперше це завдання було запропоноване для пошуку асоціативних правил щоб знайти типові шаблони покупок, які здійснюються в супермаркетах, тому іноді це ще називають аналізом ринкової корзини (market basket analysis).

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

Визначення 1. Нехай I = {i1, i2, i3, in} – множина (набір) товарів, що називаються елементами. Нехай D – множина транзакцій, де кожна транзакція T – це набір елементів з I, T  I. Кожна транзакція є бінарним вектором, де t[k]=1, якщо ik елемент присутній в транзакції, інакше t[k]=0. Ми говоримо, що транзакція T містить X, деякий набір елементів з I, якщо X  T.  Асоціативним правилом називається імплікація X  Y, де X  I, Y  I и X  Y =  . Правило X  Y має підтримку s (support), якщо s% транзакцій з D, містять X  Y, supp(X  Y) = supp (X  Y). Достовірність правила показує яка вірогідність того, що з X виходить Y. Правило X  Y справедливо з достовірністю (confidence) c, транзакцій з D, що містять X, також містять Y, conf(X  Y) = supp(X  Y)/supp(X ).

Покажемо на конкретному прикладі: '75% транзакцій, що містять хліб, також містять молоко. 3% від загального числа всіх транзакцій містять обидва товари'. 75% – це достовірність (confidence) правила, 3% це підтримка (support), або 'Хліб'  'Молоко' з вірогідністю 75%.

Іншими словами, метою аналізу є встановлення наступних залежностей: якщо в транзакції зустрівся деякий набір елементів X, то на підставі цього можна зробити висновок про те, що інший набір елементів Y також же повинен з'явитися в цій транзакції. Встановлення таких залежностей дає нам можливість знаходити дуже прості і інтуїтивно зрозумілі правила.

Алгоритми пошуку асоціативних правил призначені для знаходження всіх правил X Y, причому підтримка і достовірність цих правил повинні бути вищими за деякі наперед задані пороги, що називаються відповідно мінімальною підтримкою (minsupport) і мінімальною достовірністю (minconfidence).

Завдання знаходження асоціативних правил розбивається на дві підзадачі:

Знаходження всіх наборів елементів, які задовольняють порогу minsupport. Такі набори елементів називаються такими, що часто зустрічаються.

Генерація правил з наборів елементів, що знайдені згідно п.1. з достовірністю, яка задовольняє порогу minconfidence.

Одним з перших алгоритмів, що ефективно вирішує подібний клас завдань, – це алгоритм APriori. Окрім цього алгоритму останнім часом були розроблені ряд інших алгоритмів: DHP, Partition, DIC та інші.

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

Пошук асоціативних правил не є тривіальним завданням, як може показатися на перший погляд. Одна з проблем – алгоритмічна складність при знаходженні часто зустрічаючих наборів елементів, оскільки із зростанням числа елементів в I (| I |) експоненціально зростає число потенційних наборів елементів.