«Асоціативні правила (алгоритм Apriori)»

Національний авіаційний університет

Факультет економіки та бізнес-адміністрування

Кафедра економічної кібернетики

РОЗРАХУНКОВО ГРАФІЧНА РОБОТА

з дисципліни «Інструменти і засоби статистики, та інтелект аналізу даних»

на тему: «Асоціативні правила (алгоритм Apriori)»

Виконав:

Студент 510 групи ФЕБА

Тюрменко Владислав Владиславович

Керівник:

к.е.н., доцент

Квашук Дмитро Миколайович
Київ 2018

Асоціативні правила (алгоритм Apriori).

Алгоритм Apriori – масштабований алгоритм пошуку асоціативних правил, що базується на методах інтелектуального аналізу (Data Mining), призначений для виявлення знань у базах даних.

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

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

Асоціативне правило має вигляд: "З події А слідує подія B".

Правило AB має підтримку S (англ. support), якщо S% транзакцій з D, містять AB. Достовірність правила показує, яка ймовірність того, що з A слід B. Правило AB справедливо з достовірністю (англ. confidence) C, якщо С% транзакцій з D, що містять A, також містять B, conf (AB) = supp (AB) / supp (A).

Для застосування алгоритму Apriori необхідно провести попередню обробку даних: по-перше, привести всі дані до бінарного вигляду, по-друге, змінити структуру даних.

Кожен запис відповідає транзакції: 1 – елемент присутній в транзакції, і 0 – в іншому випадку.

Алгоритм Apriori визначає набори, які часто зустрічаються за кілька етапів. На i -му етапі визначаються всі часто зустрічаються i - елементні набори. Кожен етап складається з двох кроків:

- формування кандидатів (candidate generation),

- підрахунок підтримки кандидатів (candidate counting).

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

Потім підраховуються частоти переходів між різними діями для складання Марківського ланцюга заданого порядку. На заключному етапі отримані Марківські ланцюги кластеризуються для виявлення груп зі схожими частотами переходів.

Для прогнозування наступного дії користувача спочатку на підставі історії його дій в рамках сесії визначається група, до якої він належить з найбільшою ймовірністю. Потім визначається дія, яка виконується з найбільшою імовірністю в цій групі з урахуванням останніх дій даного користувача. Для реалізації такого аналізу можна, наприклад, використовувати алгоритм Microsoft Sequential Clustering, що входить до Microsoft Analysis Services 2012.

Структура моделі кластеризації послідовностей служби Microsoft Analysis Services.

• 
  визначення типових сесій і навігаційних шляхів користувачів сайту (аналіз послідовностей, асоціативних правил);
  
• 
  знаходження залежностей при користуванні послугами сайту (пошук асоціативних правил, кластеризація послідовностей).
  

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