Визначення поняття Data Mining

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

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

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

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

1. знаходження всіх наборів елементів, які задовольняють порогу minsupport. Такі набори елементів називаються тими, що часто зустрічаються;
2. генерація правил з наборів елементів, знайдених згідно п. a) з достовірністю, що задовольняє порогу minconfidence.

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

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

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

 

 

2.1 Узагальнені асоціативні правила (Generalized Association Rules)

 

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

Наприклад, якщо Покупець купив товар з групи "Безалкогольні напої", то він купить і товар з групи "Молочні продукти" або "Сік". Ці правила носять назву узагальнених асоціативних правил.

Визначення 2. Узагальненим асоціативним правилом називається  імплікація X Y, де X I, Y I і X Y= і де жоден з елементів, що входять в набір У, не є предком жодного елемента, що входить в X. Підтримка і достовірність підраховуються так само, як і у разі асоціативних правил (див. Визначення 1).

Введення додаткової інформації про угрупування елементів у  вигляді ієрархії дасть наступні переваги:

1. це допомагає встановити асоціативні правила не тільки між окремими елементами, але і між різними рівнями ієрархії (групами);
2. окремі елементи можуть мати недостатню підтримку, але в цілому група може задовольняти порогу minsupport;
3. для знаходження таких правил можна використовувати будь-який з вищеназваних алгоритмів.

Групувати елементи можна не тільки по входженню в певну товарну групу, але і по інших характеристиках, наприклад за ціною (дешево, дорого), бренду і т.д.

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

При цьому для скорочення простору пошуку асоціативних правил використовується властивість апріорності. Воно затверджує, що якщо науковий набір Z не є частим, то додавання будь – якого нового предмету А до набору Z не робить його таким. Іншими словами, якщо набір Z не є частим, то і Z + A – теж.

 

 

2.2 Властивість анти–монотонності

 

Виявлення наборів елементів, що часто зустрічаються, – операція, що вимагає багато обчислювальних ресурсів і, відповідно, часу. Примітивний підхід до рішення даної задачі – простий перебір всіх можливих наборів елементів. Це потребує O(2^|I|) операцій, де |I| – кількість елементів. Apriori використовує одну з властивостей підтримки, що свідчить: підтримка будь-якого набору елементів не може перевищувати мінімальної підтримки будь-якої з його підмножин. Наприклад, підтримка 3–елементного набору {Хліб, Масло, Молоко} буде завжди менше або рівно підтримці 2–елементних наборів {Хліб, Масло},                  {Хліб, Молоко} {Масло, Молоко}. Річ у тому, що будь-яка транзакція, що містить {Хліб, Масло, Молоко}, також повинна містити {Хліб, Масло},               {Хліб, Молоко}, {Масло, Молоко}, причому зворотне не вірно.

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

Властивості анти–монотонності можна дати і інше формулювання: із зростанням розміру набору елементів підтримка зменшується, або залишається такою ж. Зі всього, що було сказано раніше витікає, що будь–який k–елементний набір буде часто зустрічатися тоді і тільки тоді, коли всі його (k–1)–елементні підмножини будуть часто зустрічатись. Всі можливі набори елементів з I можна представити у вигляді грат, що починаються з порожньої множини, потім на 1 рівні 1–елементні набори, на 2–м – 2–елементні і т.д. На k рівні представлені k–елементні набори, пов'язані зі всіма своїми (k – 1) – елементними підмножинами.

Розглянемо малюнок, ілюструючи набір елементів I – {А, B, З, D}. Припустимо, що набір з елементів {А, B} має підтримку нижче заданого порогу і, відповідно, не є тим, що часто зустрічається. Тоді, згідно властивості анти–монотонності, всі його супермножини також не є тими, що часто зустрічаються і відкидаються. Вся ця гілка, починаючи з {А, B}, виділена фоном. Використовування цієї евристики дозволяє істотно скоротити простір пошуку.

Рисунок 2.1 – Набір елементів I  
2.3 Алгоритм Apriori

 

Для того, щоб  було можливе застосувати алгоритм, необхідно провести предобработку даних: по-перше, привести всі дані до бінарного вигляду; по-друге, змінити структуру даних[9]. Вигляд транзакційної бази даних представлен в таблиці 2.1 і таблиці 2.2.

Таблиця 2.1 – Звичайний вигляд

Номер транзакції	Назва елемента	Кількість
1001	А	2
1001	D	3
1001	E	1
1002	А	2
1002	F	1
1003	B	2
1003	A	2
1003	C	2
…	…	…

Таблиця 2.2 – Нормалізований вигляд

TID	A	B	C	D	E	F	G	H	I	K	…
1001	1	0	0	1	1	0	0	0	0	0	…
1002	1	0	0	0	0	1	0	0	0	0	…
1003	1	1	1	0	0	0	0	0	1	0	…

Кількість стовпців в таблиці рівно кількості  елементів, присутніх в безлічі  транзакцій D. Кожний запис відповідає транзакції, де у відповідному стовпці стоїть 1, якщо елемент присутній в транзакції, і 0 в осоружному випадку. Помітимо, що початковий вид таблиці може бути відмінним від приведеного в таблиці 2.1. Головне, щоб дані були перетворені до нормалізованого вигляду, інакше алгоритм не застосовний. Крім того, всі елементи повинні бути впорядкований в алфавітному порядку (якщо це числа, вони повинні бути впорядкований в числовому порядку).

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

Наступні кроки складатимуться з двох частин: генерації наборів  елементів (їх називають кандидатами) і підрахунку підтримки, що потенційно часто зустрічаються, для кандидатів[4].

Описаний вище алгоритм можна записати у вигляді наступного псевдокоду:

F₁ = {1-елементні набори, що часто зустрічаються}

для (k=2; F_k-1 <> ; k++) {

C_k = Apriorigen (F_k-1) // генерація кандидатів

для всіх транзакцій t T {

C_t = subset(C_k, t)// видалення надмірних правил

для всіх кандидатів с C_t

c.count ++

}

F_k = {с C_k | c.count >= minsupport} // відбір кандидатів

}

Результат F_k

Опишемо функцію генерації  кандидатів. На цей раз немає ніякої необхідності знов звертатися до бази даних. Для того, щоб отримати k–елементні набори, скористаємося (k–1)–елементними наборами, які були визначені на попередньому кроці і є тими, що часто зустрічаються.

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

Генерація кандидатів також  складатиметься з двох кроків.

Крок 1. Об'єднання. Кожний кандидат C_к формуватиметься шляхом

розширення набору розміру (k–1), що часто зустрічається, додаванням елемента з іншого (k–1)–елементного набору.

Приведемо алгоритм цієї функції Apriorigen у вигляді невеликого SQL –подібного запиту.

insert into C_k

select p.item₁, p.item₂ ., p.item_k-1, q.item_k-1 
From F_k-1 p, F_k-1 q 
where p.item₁= q.item₁, p.item₂ = q.item₂ ., p.item_k-2 = q.item_k-2, p.item_k-1 < q.item_k-1

Крок 2. Видалення надмірних правил. На підставі властивості анти–монотонності, слід видалити всі набори с C_k якщо хоча б одна з його (k–1) підмножин не є тим, що часто зустрічається.

  Після генерації кандидатів наступною задачею є підрахунок підтримки для кожного кандидата. Очевидно, що кількість кандидатів може бути дуже великою і потрібен ефективний спосіб підрахунку. Найтривіальніший спосіб – порівняти кожну транзакцію з кожним кандидатом. Але це далеко не краще рішення. Набагато швидше і ефективно використовувати підхід, заснований на зберіганні кандидатів в хеш–дереві. Внутрішні вузли дерева містять хеш–таблиці з покажчиками на нащадків, а листя – на кандидатів. Це дерево нам стане в нагоді для швидкого підрахунку підтримки для кандидатів.

Хеш–дерево будується кожного разу, коли формуються кандидати. Спочатку дерево складається тільки з кореня, який є листом, і не містить ніяких кандидатів – наборів. Кожного разу коли формується новий кандидат, він заноситься в корінь дерева і так до тих пір, поки кількість кандидатів в корені – листі не перевищить якогось порогу. Як тільки кількість кандидатів стає більше порогу, корінь перетвориться в хеш–таблицю, тобто стає внутрішнім вузлом, і для нього створюються нащадки – листя. І всі приклади розподіляються по вузлах – нащадкам згідно з хеш–значеннями елементів, що входять в набір, і т.п. Кожний новий кандидат хеширується на внутрішніх вузлах, поки він не досягне першого вузла–листа, де він і зберігатиметься, поки кількість наборів знову ж таки не перевищить порогу.