Математична постановка задач інтелектуального аналізу — алгоритм асоціативних правил

Однією з задач DataMining є асоціація. Метою пошуку асоціативних правил (associationrule) є знаходження закономірностей між зв’язаними подіями в базах даних.

Дуже часто покупці придбавають не один товар, а декілька. В більшості випадків між цими товарами існує взаємозв'язок. Так, наприклад, покупець, що придбаває макаронні вироби, швидше за все, схоче придбати також кетчуп. Ця інформація може бути використана для розміщення товару на полицях крамниці.

Наведемо простий приклад асоціативного правила: покупець, що придбаває банку фарби, придбає пензлик для фарби з вірогідністю 50%.

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

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

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

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

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

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

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

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

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

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

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

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