Інтелектуальний аналіз даних (стр. 3 из 9)
Розглянемо малюнок, ілюструючи набір елементів 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].
Описаний вище алгоритм можна записати у вигляді наступного псевдокоду:
F1 = {1-елементні набори, що часто зустрічаються}
для (k=2; Fk-1 <>
; k++) {Ck = Apriorigen (Fk-1) // генерація кандидатів
для всіх транзакцій t
T {Ct = subset(Ck, t)// видалення надмірних правил
для всіх кандидатів с
Ctc.count ++
}
Fk = {с
Ck | c.count >= minsupport} // відбір кандидатів}
Результат
FkОпишемо функцію генерації кандидатів. На цей раз немає ніякої необхідності знов звертатися до бази даних. Для того, щоб отримати k–елементні набори, скористаємося (k–1)–елементними наборами, які були визначені на попередньому кроці і є тими, що часто зустрічаються.
Пригадаємо, що наш початковий набір зберігається у впорядкованому вигляді.
Генерація кандидатів також складатиметься з двох кроків.
Крок 1. Об'єднання. Кожний кандидат Cк формуватиметься шляхом
розширення набору розміру (k–1), що часто зустрічається, додаванням елемента з іншого (k–1)–елементного набору.
Приведемо алгоритм цієї функції Apriorigen у вигляді невеликого SQL –подібного запиту.
insert into Ck
select p.item1, p.item2 ., p.itemk-1, q.itemk-1
From Fk-1 p, Fk-1 q
where p.item1= q.item1, p.item2 = q.item2 ., p.itemk-2 = q.itemk-2, p.itemk-1 < q.itemk-1
Крок 2. Видалення надмірних правил. На підставі властивості анти–монотонності, слід видалити всі набори с
Ck якщо хоча б одна з його (k–1) підмножин не є тим, що часто зустрічається.Після генерації кандидатів наступною задачею є підрахунок підтримки для кожного кандидата. Очевидно, що кількість кандидатів може бути дуже великою і потрібен ефективний спосіб підрахунку. Найтривіальніший спосіб – порівняти кожну транзакцію з кожним кандидатом. Але це далеко не краще рішення. Набагато швидше і ефективно використовувати підхід, заснований на зберіганні кандидатів в хеш–дереві. Внутрішні вузли дерева містять хеш–таблиці з покажчиками на нащадків, а листя – на кандидатів. Це дерево нам стане в нагоді для швидкого підрахунку підтримки для кандидатів.
Хеш–дерево будується кожного разу, коли формуються кандидати. Спочатку дерево складається тільки з кореня, який є листом, і не містить ніяких кандидатів – наборів. Кожного разу коли формується новий кандидат, він заноситься в корінь дерева і так до тих пір, поки кількість кандидатів в корені – листі не перевищить якогось порогу. Як тільки кількість кандидатів стає більше порогу, корінь перетвориться в хеш–таблицю, тобто стає внутрішнім вузлом, і для нього створюються нащадки – листя. І всі приклади розподіляються по вузлах – нащадкам згідно з хеш–значеннями елементів, що входять в набір, і т.п. Кожний новий кандидат хеширується на внутрішніх вузлах, поки він не досягне першого вузла–листа, де він і зберігатиметься, поки кількість наборів знову ж таки не перевищить порогу.
Хеш–дерево з кандидатами–наборами побудовано, зараз, використовуючи хеш–дерево, легко підрахувати підтримку для кожного кандидата. Для цього потрібно "пропустити" кожну транзакцію через дерево і збільшити лічильники для тих кандидатів, чиї елементи також містяться і в транзакції, тобто Ck
Ti = Ck. На кореневому рівні хеш–функція застосовується до кожного елемента з транзакції. Далі, на другому рівні, хеш–функція застосовується до других елементів і т.д. На k–рівні хеширується k–елемент. І так до тих пір, поки не досягнемо листа. Якщо кандидат, що зберігається в листі, є підмножиною даної транзакції, тоді збільшуємо лічильник підтримки цього кандидата на одиницю.Після того, як кожна транзакція з початкового набору даних "пропущена" через дерево, можна перевірити чи задовольняють значення підтримки кандидатів мінімальному порогу. Кандидати, для яких ця умова виконується, переносяться в розряд часто зустрічаємих. Крім того, слід запам'ятати і підтримку набору, вона нам стане в нагоді при витяганні правил. Ці ж дії застосовуються для знаходження (k+1)–елементних наборів і т.д.
Після того, як знайдені всі часто зустрічаємі набори елементів можна приступити безпосередньо до генерації правил.
Витягання правил – менш трудомістка задача. По–перше, для підрахунку достовірності правила достатньо знати підтримку самого набору і множини, що лежить в умові правила. Наприклад, є набір {А, B, С}, що часто зустрічається, і потрібно підрахувати достовірність для правила AB
С. Підтримка самого набору нам відома, але і його множина {А, B}, що лежить в умові правила, також часто зустрічається через властивість анти–монотонності, і значить, його підтримка нам відома. Тоді ми легко зможемо підрахувати достовірність. Це позбавляє нас від небажаного перегляду бази транзакцій, який був б потрібен в тому випадку, якщо б це підтримка була невідома.Щоб витягнути правило із часто зустрічає мого набору F, слід знайти всі його не порожні підмножини. І для кожної підмножини s ми зможемо сформулювати правило s
(F – s), якщо достовірність правила conf(s (F – s)) = supp(F)/supp(s) не менше порогу minconf.Помітимо, що чисельник залишається постійним. Тоді достовірність має мінімальне значення, якщо знаменник має максимальне значення, а це відбувається у тому випадку, коли в умові правила є набір, що складається з одного елемента. Все супермножина даної множини має меншу або рівну підтримку і, відповідно, більше значення достовірності. Ця властивість може бути використана при витяганні правил. Якщо ми почнемо витягувати правила, розглядаючи спочатку тільки один елемент в умові правила, і це правило має необхідну підтримку, тоді всі правила, де в умові стоїть супермножина цього елемента, також мають значення достовірності вище заданого порогу. Наприклад, якщо правило А
BCDE задовольняє мінімальному порогу достовірності minconf, тоді AB CDE також задовольняє. Для того, щоб витягнути всі правила використовується рекурсивна процедура. Важливе зауваження: будь-яке правило, складене з набору, що часто зустрічається, повинне містити всі елементи набору. Наприклад, якщо набір складається з елементів {А, B, С}, то правило А B не повинне розглядатися.