Вступ до аналізу асоціативних правил. Звіт до лабораторної роботи з Алгоритми. Робота № 524674

Перехід до торгівельного партнера Binance

Вступ до аналізу асоціативних правил

Інформація про навчальний заклад

ВУЗ:

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

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Не вказано

Інформація про роботу

Рік:

2013

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Алгоритми

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки, молоді та спорту України Національний університет «Львівська політехніка» Звіт до лабораторної роботи №3 «Вступ до аналізу асоціативних правил» Львів - 2013 Короткі теоретичні відомості Останнім часом задачі пошуку нових знань у великих базах сирих даних стають все більш популярними та актуальними. Одним із популярних методів виявлення знань став алгоритм пошуку так званих асоціативних правил (Association Rules). Суть задачі полягає в знаходження наборів об’єктів, які зустрічаються найчастіше серед всієї множини ймовірних наборів об’єктів. Першим застосуванням такої задачі був аналіз тенденцій в поведінці покупців у супермаркетах. При цьому аналізувались дані про всі здійснені покупки, які кожен покупець кладе у свій кошик, та одержувалась інформація про те, які товари переважно купуються разом, в якій послідовності, якими категоріями покупців, в які періоди часу, тощо. Такого роду знання дозволяють ефективно планувати закупку товарів у магазин, розробляти ефективні рекламні кампанії та розкладати товар таким чином, щоб провокувати покупців на різноманітні покупки. Наприклад, з набору товарів, які купуються в магазинах, можна виділити такі набори товарів, що переважно купуються одночасно: {чіпси, пиво}; {вода, горіхи}; {чай, печиво}; Тощо. Таким чином, можна зробити висновок про те, що якщо купуються чіпси чи горіхи, то, як правило, купуються, пиво чи вода, відповідно. Отже, можна розмістити ці товари поруч на прилавках, об’єднати їх в один пакет зі знижкою чи здійснити інші дії. Задача пошуку асоціативних правил є актуальною не лише у сфері торгівлі. Наприклад, в сефрі обслуговування цікавою є інформація про те, якими послугами клієнти користуються в сукупності. Для одержання цієї інформації вирішується задача аналізу даних про послуги, якими користується один клієн протягом певного часу. Це допомагає визначити, наприклад, як найбільш вигідно сформувати пакети послуг для клієнтів. В медицині аналізуватись можуть симптоми та хвороби пацієнтів. В цьому випадку знання про те, які поєднання хворів та симптомів зустрічаються найчастіше, дозволяють в майбутньому ставити правильні діагнози. Визначення Щоб дати означення асоціативного правила, будемо вважати, що існує база даних, якій містяться записи про всі здійснені покупки в супермаркеті. Кожен запис називається транзакцією і включає дані про набір товарів, куплених одним покупецем за один візит. Таку транзакцію ще називаю ринковим кошиком. Нехай – це вся множина товарів з супермаркету, що називаються елементами. Приклад: Ідентифікатор Найменування товару Ціна 0 Шоколад 30.00 1 Чіпси 12.00 2 Кокоси 10.00 3 Вода 4.00 4 Пиво 14.00 5 Горіхи 15.00 Тобто вся множина елементів (їх загальна кількість рівна ) буде: . Кожна транзакція описується як: . Приклади транзакцій: Набір усіх відомих транзакцій (загальна їх кількість нехай рівна ) позначаємо як : . Нехай для нашого прикладу: Тоді множину можемо представити у вигляді: № транзакції Ідентифікатор товару Найменування товару Ціна 0 1 Чіпси 12.00 0 3 Вода 4.00 0 4 Пиво 14.00 1 2 Кокоси 10.00 1 3 Вода 4.00 1 5 Горіхи 15.00 2 5 Горіхи 15.00 2 2 Кокоси 10.00 2 1 Чіпси 12.00 2 2 Кокоси 10.00 2 3 Вода 4.00 3 2 Кокоси 10.00 3 5 Горіхи 15.00 3 2 Кокоси 10.00 Множину транзакцій, в яку входить об’єкт позначимо як: . Наприклад, множина транзакцій, в які входить елемент «вода»: Деякий довільний набір елементів позначимо так: . Набір, що складається з об’єктів називається -елементним набором. Приклад 2-елементного набору: . Множину транзакцій, в яку входить набір , позначимо : . В даному прикладі: . Відношення кількості транзакцій, в які входить , до загальної кількості транзакцій називається підтримкою (support) набору та позначається : . Можна підтримку рахувати у відсотках (тоді треба помножити на 100%). Для набору підтримка рівна 0.5 або 50%, так як цей набір входить у дві транзакції (з номерами 1 та 2), а всього транзакцій є 4. При пошуку аналітик може вказати мінімальне значення підтримки для наборів, що його цікавлять – . Набір називається частим, якщо значення його підтримки є більшим за вказане мінімальне значення, задане користувачем: . Таким чином, при пошуку асоціативних правил необхідно знайти множину всіх частих наборів: . В даному прикладі частими наборами при є такі: З іншого боку, важливо не лише знайти часті набори, але виявити правила «якщо....., то...». Наприклад, в даному прикладі можна досліджувати, наскільки правдивим є правило: якщо «кокоси», то «вода». Тобто важливо не просто знати. Що ці ва елементи часто знаходяться в одному наборі, але й вміти прогнозувати, що при покупці «кокосів» ймовірно буде покупка «води» або навпаки. Розіб’ємо наш досліджуваний наборі на два піднабори: та . Наприклад, набір будемо розглядати як: та , тобто . Тоді асоціативним правилом можна назвати імплікацію: , де . Правило має підтримку: , тобто – це відсоток зі всіх транзакцій , що містять і набір , і набір (тобто містять набір ). Бо, як було вже згадано вище, з чотирьох транзакцій дві містять і «Кокоси» і «Воду». Достовірністю правила називається ймовірність того, що саме з випливає . Правило має достовірність (confidence): , що показує, який відсоток з усіх транзакцій , що містить , також містить і .. Отже, підтримка правила рівна 50% (50% зі всіх транзакцій містять і «Кокоси», і «Воду»), а достовірність цього правила рівна 66.7% (66.7% зі всіх транзакцій, що містять «Кокоси», також містять і «Воду»). Іншими словами, метою аналізу є встановлення наступних залежностей: якщо в транзакції зустрівся деякий набір елементів , то на підставі цього можна зробити висновок про те, що інший набір елементів також повинен з'явитися в цій транзакції. Алгоритми пошуку асоціативних правил призначені для знаходження всіх правил , причому підтримка і достовірність цих правил повинні бути вищими за деякі наперед задані пороги, що називаються відповідно мінімальною підтримкою () та мінімальною достовірністю (). Деякі видозміни асоціативних правил Узагальнені асоціативні правила (Generalized Association Rules) При пошуку асоціативних правил вище припускалось, що всі аналізовані елементи є однорідними. Проте, повертаючись до аналізу ринкової корзини, не складе великих труднощів доповнити транзакцію інформацією про те, до якої товарної групи входить товар і побудувати ієрархію товарів. Приведемо приклад такого групування (таксономії) у вигляді ієрархічної моделі. INCLUDEPICTURE "http://www.victoria.lviv.ua/html/oio-l/2/7.gif" \* MERGEFORMATINET INCLUDEPICTURE "http://www.victoria.lviv.ua/html/oio-l/2/7.gif" \* MERGEFORMATINET INCLUDEPICTURE "http://www.victoria.lviv.ua/html/oio-l/2/7.gif" \* MERGEFORMATINET Нехай дана база транзакцій та відомо, в які групи (таксони) входять елементи. Тоді з даних можна одержувати правила, що пов'язують групи з групами, окремі елементи з групами і т.д. Наприклад, якщо покупець купив товар з групи «Безалкогольні напої», то він купить і товар з групи «Молочні продукти»: правило . Ці правила носять назву узагальнених асоціативних правил. Введення додаткової інформації про угрупування елементів у вигляді ієрархії має свої переваги, зокрема, допомагає встановити асоціативні правила не тільки між окремими елементами, але й між різними рівнями ієрархії (групами). Проте з додаванням до транзакції понять груп збільшується кількість атрибутів і, відповідно, розмірність вхідного простору. Це ускладнює завдання, а також призводить до генерації більшої кількості правил. Для знаходження узагальнених асоціативних правил бажано використання спеціалізованого алгоритму, який усуває вищеописані проблеми. Групувати елементи можна не тільки по входу до певної товарної групи, але й за іншими характеристиками, наприклад за ціною (дешево, дорого), брендом і т.д. Чисельні асоціативні правила (Quantitative Association Rules) При пошуку асоціативних правил все зводилося до того, чи присутній в транзакції елемент чи ні. Тобто, якщо розглядати випадок ринкової корзини, то розглядаємо два стани: куплено товар чи ні. При цьому ігнорується, наприклад, інформація про те, скільки чого було куплено, хто саме купив, тощо. Тобто було розглянуто "булеві" асоціативні правила. Проте можна аналізувати дані різних типів: числові, категоріальні і т.д. Приклад чисельного асоціативного правила: Якщо «[Вік: 30-35]» і «[Сімейний стан: одружений]», то «[Місячний дохід: 1000-1500 гривень]». Виконання роботи: Запустив програмний пакет Deductor та ознайомився із його основними можливостями. Відкрив тестовий приклад сценарію та проаналізував готову гілку з асоціативними правилами. Набір асоціативних правил з вказанням їх підтримки, достовірності та кількості. Дерево правил за наслідком, наприклад: Популярні набори елементів Уважно ознайомився з методикою формування асоціативних правил. Використовуючи готовий файл даних, пройшов всі необхідні кроки для одержання асоціативних правил. Для цього необхідно завантажити Майстер обробки. Сформував власні дані та тему: аналіз даних про покупців зацікавлених фототехнікою. Ця інформація може бути корисною при додаванні супутніх товарів до фотоапаратів в інтернет-магазинах, а також при мерчендайзингу:Номер Чеку Товар 160698 Canon EOS 600D, Рюкзак Lowepro, Карта Пам'яті Team SDHC 32GB Class 10 160698 Спалах Canon Speedlite 600ex 160698 Canon Ef 50mm 160747 Спалах Canon Speedlite 600ex 160747 Світлофільтр 160747 Canon Ef 50mm 161217 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 161217 Спалах Canon Speedlite 600ex 161217 Салфетка Для Чистки 161243 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 161243 Спалах Canon Speedlite 600ex 161243 Салфетка Для Чистки 161354 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 161354 Спалах Canon Speedlite 600ex 161354 Canon Ef 50mm 161833 Спалах Canon Speedlite 600ex 161833 Світлофільтр 161833 Canon Ef 50mm 162185 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 162185 Спалах Canon Speedlite 600ex 162185 Canon Ef 50mm 162579 Салфетка Для Чистки 162579 Світлофільтр 162579 Canon Ef 50mm 162661 Чистячий Олівець Для Оптики 162661 Салфетка Для Чистки 162661 Canon Ef 50mm 162718 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 162718 Спалах Canon Speedlite 600ex 162718 Салфетка Для Чистки 162788 Чистячий Олівець Для Оптики 162788 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 162788 Canon Ef 50mm 162915 Чистячий Олівець Для Оптики 162915 Запасна Кришечка 162915 Canon Ef 50mm 163029 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 163029 Світлофільтр 163029 Canon Ef 50mm 163261 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 163261 Спалах Canon Speedlite 600ex 163261 Салфетка Для Чистки 163331 Canon Ef 50mm 163331 Світлофільтр 163331 Салфетка Для Чистки 163439 Світлофільтр 163439 Запасна Кришечка 163439 Canon Ef 50mm 164014 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 164014 Спалах Canon Speedlite 600ex 164014 Canon Ef 50mm 164078 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 164078 Спалах Canon Speedlite 600ex 164078 Canon Ef 50mm 164079 Чистячий Олівець Для Оптики 164079 Запасна Кришечка 164079 Canon Ef 50mm 164110 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 164110 Салфетка Для Чистки 164110 Canon Ef 50mm 164200 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 164200 Спалах Canon Speedlite 600ex 164200 Салфетка Для Чистки 164453 Чистячий Олівець Для Оптики 164453 Світлофільтр 164453 Canon Ef 50mm 165325 Чистячий Олівець Для Оптики 165325 Запасна Кришечка 165325 Canon Ef 50mm 165417 Чистячий Олівець Для Оптики 165417 Спалах Canon Speedlite 600ex 165417 Запасна Кришечка 165698 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 165698 Спалах Canon Speedlite 600ex 165698 Світлофільтр 166110 Запасна Кришечка 166110 Світлофільтр 166110 Canon Ef 50mm 166881 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 166881 Спалах Canon Speedlite 600ex 166881 Світлофільтр 166966 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 166966 Спалах Canon Speedlite 600ex 166966 Салфетка Для Чистки 167022 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 167022 Спалах Canon Speedlite 600ex 167022 Світлофільтр 167381 Canon Eos 600d, Рюкзак Lowepro, Карта Пам'яті Team Sdhc 32gb Class 10 167381 Спалах Canon Speedlite 600ex 167381 Світлофільтр 167514 Чистячий Олівець Для Оптики 167514 Nikon 50mm 167514 Запасна Кришечка 160227 Nikon d7000, Рюкзак Pro, Flash 32gb Class 10 160227 Спалах Nikon SX 160227 Світлофільтр 160227 Nikon 50mm 160487 Nikon d7000, Рюкзак Pro, Flash 32gb Class 10 160487 Спалах Nikon SX 160487 Світлофільтр 160487 Nikon 50mm 163213 Nikon d7000, Рюкзак Pro, Flash 32gb Class 10 163213 Спалах Nikon SX 163213 Салфетка Для Чистки 163213 Nikon 50mm 163346 Nikon 50mm 163346 Спалах Nikon SX 163346 Запасна Кришечка 163346 Салфетка Для Чистки 163741 Чистячий Олівець Для Оптики 163741 Запасна Кришечка 163741 Салфетка Для Чистки 163741 Nikon 50mm 164085 Світлофільтр 164085 Запасна Кришечка 164085 Салфетка Для ЧисткиПройшов всі кроки для імпорту нових даних. Дані після імпорту: Вмикаю майстер обробки (F7): Результати: Популярні набори Дерево правил Отже, можна зробити висновок, що найчастіше в парі "йдуть" об'єктиви Canon Ef 50mm з комплектом фотоапарат + рюкзак + карта пам'яті. Також з таблиці асоціативні правила по елементах трансакціях можна побачити правила типу Умова -> Наслідок. Висновок: в ході виконання даної лабораторної роботи я ознайомився з алгоритмом пошуку асоціативних правил (Association Rules).

Звіт до лабораторної роботи Алгоритми

savruksergiy

11.06.2013 17:06-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись