Презентация на тему: Поняття асоціативного правила 1

Поняття асоціативного правила 1
Основн і характеристики асоціативних правил (АП) 2
Значущість асоціативних правил 3
Алгоритм – Apriori 4
Приклад роботи алгоритму Apriori 5
Приклад роботи алгоритму Apriori (2) 6
Приклад роботи алгоритму Apriori (3) 7
Приклад роботи алгоритму Apriori (4) 8
Послідовні шаблони 9
Постановка задачі пошуку послідовних шаблонів 10
Задача пошуку послідовних шаблонів 11
Пошук послідовних шаблонів (1) 12
Пошук послідовних шаблонів (2) 13
Алгоритм AprioriAll (1) 14
Алгоритм AprioriAll (2 ) 15
Схема алгоритму AprioriAll 16
1/16
Средняя оценка: 4.9/5 (всего оценок: 7)
Код скопирован в буфер обмена
Скачать (154 Кб)
1

Первый слайд презентации: Поняття асоціативного правила 1

Однією з задач Data Mining є д ослідження зв’язків між подіями, що відбуваються сумісно, і виявлення правил (асоціацій), для їх кількісного опису. Асоціативні правила часто використовують, наприклад, у таких задачах: - виявлення наборів товарів, які часто (або ніколи) купуються разом; - визначення клієнтів, якім подобаються нововведення у їх обслуговування; визначення профілю відвідувача web-ресурсу і т. ін. Базовим поняттям теорії асоціативних правил є транзакція – множина подій, що відбуваються сумісно. Наприклад, купівельна транзакція є набором (items) товарів, куплених покупцем за один візит. Такі транзакції можуть фіксуватись касовими апаратами і зберігатись у базі даних. Визначення 1. Нехай I={i1, i2, …, ij,…in} є набором елементів (наприклад, товарів): I={шоколад, чіпси, кокоси, вода, пиво, горіхи }. Нехай D – множина транзакцій D ={ Т1, Т2,…, Тr,…, Тm}, де кожна транзакція T є набором елементів з I, Т І,Т= {i j | ij  I }. Кожна транзакція подається бінарним вектором, де t[k]=1, якщо елемент i k присутній в транзакції, інакше t[k]=0. К ажуть, що транзакція T містить деякий набір елементів X з I, якщо X  T. Асоціативним правилом називається імплікація X  Y, де X  I, Y  I, X  Y = Ø, що читається як: «З Х випливає Y». Тобто асоціативне правило формулюється у вигляді: «Якщо умова, то наслідок»

Изображение слайда
2

Слайд 2: Основн і характеристики асоціативних правил (АП) 2

Підтримка (support) правила X  Y є значенням S, яка співпадає з кількістю транзакцій з D, що містять як умову X, так і наслідок Y: S( X  Y )=P ( X  Y )= кількість транзакцій, що містять X і Y / сума транзакцій Достовірність правила С є мірою його точності, і є відношенням кількості транзакцій з умовою і наслідком, до кількості транзакцій лише з умовою: C( X  Y ) = P(Y|X)=P ( X  Y )/P(X) = транзакцій з X і Y / транзакцій лише з Х. Приклад: нехай 75% транзакцій, що містять хліб, також містять молоко. 3% від загальної кількості всіх транзакцій містять обидва товари. Тоді достовірність правила складе C=0,75, а його підтримка S=0,03. Тобто, 3% покупців купили хліб і молоко, а 75% з тих хто купив хліб, купив і молоко. Задача виявлення АП розбивається на дві підзадачі: 1. Виявлення всіх наборів елементів, які задовольняють порогу minsupport (MS), і називаються такими, що часто зустрічаються ( large itemset ). 2. Генерація правил з наборів елементів, знайдених згідно п.1. з достовірністю, що задовольняє порогу minconfidence ( М C). Порогові значення мають обмежити кількість знайдених правил. За великої підтримки алгоритми знаходять очевидні правила. За низької – генерують надто багато правил. Але більшість цікавих правил знаходиться саме при низькому значенні порогу підтримки. Хоча надто низьке значення підтримки веде до генерації статистично необгрунтованих правил. Пошук АП є не тривіальною задачею, оскільки зі зростанням потужності множини I експоненціально зростає кількість потенційних наборів елементів

Изображение слайда
3

Слайд 3: Значущість асоціативних правил 3

Левередж (значущість) – різниця між підтримкою правила в цілому і добутком підтримки окремо умови і наслідку: Т ( X  Y )=S( X  Y ) - S( X )S( Y ). У загальному випадку, чим більшим є значення левериджу, тим більш значущим є правило Приклад : нехай Х є у 70 транзакціях зі 100, а Y– у 80, і у 50 транзакціях зі 100 вони є разом. Маємо S X S Y -S XY =0,56-0,5=0,06. Отже, АП не є цікавим, товари випадково зустрічаються в одній транзакції внаслідок своєї популярності. Приклад: якщо у 100 ДТП взяли участь 70 автомобілів ВАЗ, це не означає закономірності «Якщо аварія, то ВАЗ», якщо ВАЗ складає 80% усіх авто. Ліфт (цікавість) - відношення частоти появи умови в транзакціях, які містять також і наслідок, до частоти появи наслідку в цілому: L( X  Y )=C( X  Y )/S( Y ). При L> 1 умова частіше є у транзакціях, що містять наслідок, ніж у інших,при L =1 - зв’язок Х і Y відсутній, при L< 1 - він від’ємний. Ліфт не завжди є вдалою мірою значущості правила, оскільки збільшення кількості покупців призводить до зростання зв’язку між умовою і наслідком. Іноді ліфт, що подає міру корисності АП називають покращенням (improvement), і обчислюють як відношення спостережуваної частоти до відокремлених частот умови і наслідку: І ( X  Y )=S( X  Y )/S( X )S( Y ). Покращення (ліфт) показує чи є правило кориснішим за випадкове угадування. Значення І(XY)>1 свідчить, що краще скористатись правилом, ніж здійснювати випадковий вибір. Такі міри, як ліфт і леверидж, використовують для подальшого обмеження набору АП встановленням порогу значущості нижче за який АП відкидаються.

Изображение слайда
4

Слайд 4: Алгоритм – Apriori 4

При пошуку АП треба розглянути усі можливі комбінації умов і наслідків, а потім відкинути асоціації, які не задовольняють заданим обмеженням. Але кількість АП зі зростанням кількості елементів зростає експоненційно. При k транзакц іях і бінарних АП (одноелементні умова і наслідок), треба здійснити аналіз k 2k-1 асоціацій. Тобто, для вибірки зі 100 продуктів, кількість утворюваних ними асоціацій складе 100х2 99 > 6,4х10 31. Алгоритм Apriori зменшує кількість генерованих АП за рахунок аналізу лише тих асоціацій, які зустрічаються найбільш часто. Части м набором (frequent itemset) називаєть предметний набір з підтримкою більшою за заданий поріг, або рівною йому. Цей поріг називається мінімальною підтримкою. Методика пошуку асоціативних правил з використанням частих наборів складається з двох кроків: - пошук частих наборів; - генерація на основі знайдених частих наборів АП, що задовольняють умовам мінімальної підтримки і достовірності. Для зменшення розмірності простору пошуку АП алгоритм Apriori використовує властивість антімонотонності, яка полягає у тому, що якщо предметний набір Z не є частим, то додавання деякого нового предмету А до набору Z не зробить його більш частішим. Тобто, якщо Z не є частим набором, то й набір Z  А також не буде частим

Изображение слайда
5

Слайд 5: Приклад роботи алгоритму Apriori 5

Розглянемо множину з 14 транзакцій, що містять елементи з предметного набору потужністю 7. Подамо базу даних транзакцій у нормалізованому вигляді, де на перетину рядку транзакції і стовпця предмету ставиться 1, якщо предмет присутній у транзакції, і 0 – в іншому випадку: Частота появи кожного предмету визначається сумою одиничок у стовпці. Набори, які зустрічаються у D більше ніж f=4 рази вважатимемо частими. Знайдемо спочатку однопредметні набори. Оскільки всі суми у стовпцях є не меншими за 4, усі предмети є частими однопредметними наборами. Далі визначимо множину 2-х предметних наборів, після чого скоротимо отриману множину з урахуванням властивості антімонотонності. Предметні набори, що залишаться, формують множину 3-х предметних наборів F2 і т.д.

Изображение слайда
6

Слайд 6: Приклад роботи алгоритму Apriori (2) 6

Оскільки f=4, до множини F2 увійдуть лише 7 наборів: Згенеруємо множину 3-х предметних наборів зв’язуванням F2 самої з собою. Набори є зв’язуваними, якщо їх перші k-1 предметів однакові (предмети мають розташовуватися в алфавітному порядку!). Наприклад, набори {спаржа, квасоля} і {спаржа, кабачки}, для яких k=2, повинні мати для зв’язування (k-1)-й спільний перший елемент (k-1=1), яким і є спаржа. Результатом зв’язування є: {спаржа, квасоля}+{спаржа, кабачки} = {спаржа, квасоля, кабачки}. Аналогічно отримуємо інші 3-х предметні набори: {спаржа, квасоля, кабачки};{квасоля, кукурудза,кабачки}; {квасоля,кабачки,помідори};{квасоля,кукурудза,помідори} Для перевірки антімонотонності кожного з отриманих наборів утворимо і перевіримо піднабори розмірністю k-1 (двохпредметні). Якщо будь-який з цих піднаборів не є частим, то і набор не може бути частим і він вилучається з подальшого розгляду. Наприклад, для набору {спаржа, квасоля,кабачки} треба розглянути під набори: {спаржа, квасоля }, ( f= 5), {спаржа, кабачки}, ( f= 5) і {квасоля,кабачки}, ( f= 6). Усі ці 2-набори є частими, отож частим є і 3-набір {спаржа, квасоля, кабачки}. Аналогічно можна впевнитись, що й набір { квасоля, кукурудза, помідори} також є частим, а набори {квасоля, кукурудза, кабачки} і {квасоля, кабачки, помідори} не є частими.

Изображение слайда
7

Слайд 7: Приклад роботи алгоритму Apriori (3) 7

Отож, множина F3 утворюється з двох наборів, які вже не можна зв’язати між собою. Тому задача пошуку частих предметних наборів на заданій множині транзакцій – вирішена і можна переходити до генерації АП. Для цього, до кожного частого набору s треба застосувати двох крокову процедуру: 1. Генерування усіх можливих піднаборів s; 2. Якщо піднабір ss є непустим піднабором s, то розглядається асоціація R: ss s де s – ss є набором s без під набору ss. R є АП, якщо вона задовольняє обмеженням мінімуму підтримки і достовірності. Процедура повторюється для кожної підмножини ss з s. Розглянемо набори - кандидати у АП з 2 предметами в умові, наприклад набір s= {спаржа, квасоля, кабачки} з множини F3. Відповідними під наборами s будуть: {спаржа}, {квасоля}, {кабачки}, {спаржа, квасоля}, {спаржа, кабачки}, {квасоля, кабачки}. Проаналізуємо утворювані асоціативні правила з двома предметами в умові: Для порогу достовірності 60% всі отримані асоціації будуть правилами. Для порогу 0,8 - правилами будуть лише дві перші асоціації. Тепер розглянемо кандидатів у правила, що мають одну умову і один наслідок, які згенеруємо на основі отриманої раніше множини F2, яка складалась з 7 2-х предметних наборів.

Изображение слайда
8

Слайд 8: Приклад роботи алгоритму Apriori (4) 8

Для перевірки значущості генерованих правил, перемножимо їх значення підтримки і достовірності та проранжуємо їх. Включимо до переліку правил лише ті асоціації, для яких отримане значення складе не менше за 80%: Розроблені правила можна використати для розробки більш досконалої маркетингової стратегії, оптимізації закупівель і розміщення товарів на прилавках і вітринах.

Изображение слайда
9

Слайд 9: Послідовні шаблони 9

АП мають ряд обмежень, які обмежують можливості аналізу асоціацій: 1. АП враховують лише факти спільної появи товарів і не враховують часовий аспект послідовності появи товарів і динаміку продажів. Якщо розглянути послідовність подій, таких, як зростання чи спад продажів певного товару або послуги за кілька послідовних періодів часу, то можна зробити деякі висновки, про готовність клієнтів до покупки нового товару або послуги, про доцільність стимулювання попиту і т. ін. Для розгляду часу і послідовності появи товарів достатньо фіксувати в транзакції її дату і час, що легко реалізується сучасними інформаційними системами. 2. АП не є клієнтоорієнтованими – не пов'язують набори предметів у транзакції з певним клієнтом. Але дослідження динаміки продажів для окремих клієнтів може бути цікавим. Клієнтоорієнтованими називають транзакції, які крім набору Предметів містять ідентифікатор клієнта. Отримати ідентифікаторів клієнтів можна, наприклад, при торгівлі по клієнтських картках, з правом на знижку. Розширення можливостей аналізу транзакційних даних з урахуванням часу, послідовності появи предметів і орієнтованості на конкретного клієнта, вирішує задача DM з назвою «послідовні шаблони» (time - serial sequential pattern). Теорія послідовних шаблонів (ПШ) є розширенням теорії АП, а для їх пошуку використовуються модифіковані варіанти алгоритму Apriori. Особливістю ПШ є обов ’ язкове урахування послідовності появи предметів і їх груп. Застосування ПШ виходить за межи аналізу ринкової корзини. ПШ дозволяють виявляти типові послідовності подій в різномантих предметних областях. Наприклад, послідовність може містити такі події, як взяття декількох фільмів клієнтом у відеопрокаті.Аналіз всіх послідовностей фільмів, взятих напрокат певними клієнтами, може виявити найбільш типові шаблони. Знання таких послідовностей допоможе стимулювати клієнтів, пропонуючи їм фільми в порядку, встановленому шаблоном.

Изображение слайда
10

Слайд 10: Постановка задачі пошуку послідовних шаблонів 10

Нехай є база даних D записів клієнтських транзакцій з полями: ідентифікатор клієнта, дата/час транзакції та набір куплених товарів, при обмеженні, що жоден клієнт має не більше однієї транзакцій у одну мить часу. Введемо поняття: Предметний набір – порожній набір предметів (товарів) однієї транзакції. Послідовність - впорядкований список предметних наборів. Послідовність записують у трикутних дужках, а набір - у круглих. Отож, набори будуть записані як (2,4,5),(1,3), а послідовність з цими набори, як <(2,4,5),(1,3)>. В одному наборі записуються лише ті товари, які були придбані одночасно. Позначимо предметний набір I={i 1, i 2, …, i j,…i n }, де i 1 – предмет, а послідовність S = I 1, I 2,..., I m, де I і - предметний набір. Послідовність S1 міститься у послідовності S2, якщо всі предметні набори S1 містяться у предметних наборах S2. Наприклад, послідовність <(3);(4,5);(8)> міститься в послідовності <(7);(3,8);(9);(4,5,6);(8)>, оскільки (3)  (3,8),(4,5)  (4,5,6) і (8)  (8). Але <(3);(5)>  <(3,5)> і навпаки, бо в першій послідовності предмети 3 і 5 були куплені один за іншим, а в другій - одночасно. Послідовність S називається максимальною, якщо вона не міститься в іншій послідовності. Послідовність S називається клієнтською якщо вона містить транзакції одного Клієнта, впорядкованих по даті, часу або номеру візиту. Тобто, клієнтська послідовність - це послідовність предметних наборів, що містяться в усіх транзакціях даного клієнта. Послідовність S називається підтримуваною клієнтом, якщо вона міститься в клієнтській послідовності даного клієнта. Тоді підтримка послідовності визначає кількість клієнтів, що підтримують дану послідовність. Таким чином, поняття підтримки в теорії послідовних шаблонів дещо відрізняється від аналогічного поняття теорії асоціативних правил.

Изображение слайда
11

Слайд 11: Задача пошуку послідовних шаблонів 11

Пошук ПШ полягає у виявленні максимальних послідовностей з підтримкою вищою за заданий поріг. Кожна максимальна послідовність і є ПШ. Частими послідовностями є ті, що задовольняють мінімальну підтримку. Розглянемо набір впорядкованих клієнтських транзакцій: Перетворимо набір транзакцій у набір клієнтських послідовностей: Задамо рівень мінімальної підтримки 25%. Йому задовольняють максимальні послідовності <(3);(9)> і <(3); (4,7)> підтримувані двома клієнтами (як мінімум). Вони і є шуканими ПШ. ПШ <(3);(9)> підтримують клієнти 1 і 4. Клієнт 4 купив предмети (4,7) між 3 і 9, але він підтримує шаблон <(3);(9)>, оскільки шаблони не обов'язково є безперервними послідовностями. Шаблон <(3);(4,7)> підтримують клієнти 2 і 4. Клієнт 2 купив предмет 6 між 4 і 7, але підтримує даний шаблон, оскільки набір (4,7) є підмножиною (4,6,7). Не задовольняє мінімальну підтримку послідовність <(1,2),(3)>, яку підтримує лише клієнт 2. Послідовності <(3)>,<(5)>,<(7)>,<(9)>,<(3);(4)>,<(3);(7)> і <(4,7)>, задовольняють мінімальній підтримці, але не є максимальними, оскільки містяться в більш довгих послідовностях.

Изображение слайда
12

Слайд 12: Пошук послідовних шаблонів (1) 12

Довжина послідовності - це кількість предметних наборів, які в ній містяться. Послідовність довжини k будемо називати k- (елементною) послідовністю. Підтримка предметного набору I дорівнює кількості клієнтів, які придбали предмети, що входять до нього, в одній транзакції. Таким чином, предметний набір I та 1-послідовність <I> мають однакову підтримку. Нагадаємо, що в АП предметний набір, що задовольняє рівню мінімальної підтримки, називається частим. Зауважимо, що будь-який предметний набір в частій послідовності також має бути частим, на що вказує властивість антімонотонності. Отже, будь-яка часта послідовність буде складатися тільки з частих предметних наборів. Наведемо часті предметні набори з нашого прикладу: Процес пошуку ПШ складається з таких кроків. Сортування - транзакції упорядковуються за кодами клієнтів, а транзакції кожного клієнта - за датою, часом або номером візиту. Таким чином, початкова база даних перетвориться в базу даних клієнтських послідовностей. 2. Пошук частих предметних наборів F. Одночасно шукається множина всіх частих 1- послідовностей, оскільки це просто множина {<f > |f  F}. Підтримкою частих предметних наборів на множині клієнтських транзакцій є кількість транзакцій, в яких представлено даний предметний набір. При пошуку ПШ - це кількість клієнтів, що купили даний набір хоча б в одній транзакції. Далі множину частих предметних наборів, якими у нас є (3), (4),(7),(4,7) і (9), подають у альтернативному вигляді букв, цілих чисел або двійкових послідовностей. Подання у вигляді окремих значень спрощує алгоритмічну реалізацію задачі. с

Изображение слайда
13

Слайд 13: Пошук послідовних шаблонів (2) 13

3. Перетворення - визначають часті послідовності, які містяться в клієнтській послідовності (КП). Для цього кожна транзакція КП заміщається множиною її частих предметних наборів. Якщо транзакція не містить жодного частого предметного набору, то внаслідок перетворення вона вилучається з розгляду. Якщо КП не містить жодного частого предметного набору, то уся послідовність також вилучається. Після перетворення кожна КП буде подана ​​як множина частих предметних наборів f1, f2,..., fn. Позначимо такий перетворений набір транзакцій DT. Наприклад, в процесі перетворення клієнтської послідовності 2, набір (1,2 ) був вилучений, оскільки він не є частим, а набір (4,6,7) було замінено множиною частих предметних наборів {(4); (7); (4,7)}. 4. На множині частих предметних наборів виконується пошук частих послідовностей. 5. Пошук максимальних послідовностей - серед частих послідовностей шукають максимальні послідовності. Іноді даний етап суміщають з попереднім, щоб зменшити витрати часу на обчислення не максимальних послідовностей. Найскладнішим етапом процесу пошуку ПШ є пошук частих послідовностей, оскільки велика кількість предметних наборів вимагає розгляду величезної кількості можливих комбінацій і багатократного проходу набором транзакцій.

Изображение слайда
14

Слайд 14: Алгоритм AprioriAll (1) 14

На кожному проході алгоритму AprioriAll скануються часті послідовності, знайдені на попередньому проході, і формуються нові послідовності- кандидати, а потім обчислюється їх підтримка в процесі нового проходу. Надалі вона використовується для визначення частих послідовностей. Часті предметні набори, знайдені на проході 1, є частими 1-послідовностями, тому іноді цей процес називають ініціалізацією. Позначимо F k-1 - множину всіх частих (k-1)-послідовностей. Вилучимо всі послідовності таким чином, що (k -1)- послідовності не належатимуть множині Fk -1, тобто не є частими. Наприклад, розглянемо множину 3-послідовностей F 3, подану у першому стовпчику таблиці: Після відсікання послідовностей, підпослідовності яких не містяться в F3, маємо єдину послідовність, подану в 3-му стовпці. Наприклад, послідовність 1243 відсікається, оскільки підпослідовність 243 не лежить в F3. Розглянемо базу даних клієнтських послідовностей, подану в таблиці:

Изображение слайда
15

Слайд 15: Алгоритм AprioriAll (2 ) 15

У даному прикладі ми не розглядаємо початкову базу даних. Клієнтські послідовності отримані шляхом заміни транзакцій містяться в них частими предметними наборами. Мінімальна підтримка визначена 40% (дві клієнтські послідовності). На першому проході по базі даних проводиться пошук частих предметних наборів, і, відповідно, частих 1-послідовностей. Результати, а саме часті послідовності довжин 2, 3, і 4 і значення їх підтримки, подамо таблицею: На 5-му проході нових кандидатів отримано не було. Таким чином, максимальними частими послідовностями є <1,2,3,4>, <1,3,5> і <4,5>, оскільки вони не містяться в послідовностях більшої довжини. Вони і будуть шуканими послідовними шаблонами. Узагальнену схему алгоритму AprioriAll подано ​​на рисунку, де F k- 1 –множина всіх частих (k- 1 ) -послідовностей, k – довжина послідовності, C k - множина послідовностей кандидатів довжини k, s i - послідовності-кандидати, що входять до C k, Sup – оператор обчислення підтримки.

Изображение слайда
16

Последний слайд презентации: Поняття асоціативного правила 1: Схема алгоритму AprioriAll 16

Изображение слайда