Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Асоціаційні правила. Послідовне відображення шаблонів даних




Класифікація з учителем у випадку нормальних спостережень.

Категорія навчання з учителем представлена такими задачами Data Mining: класифікація, оцінка, прогнозування. Класифікація (Classification) - найбільш проста і поширена завдання Data Mining. В результаті рішення задачі класифікації виявляються ознаки, які характеризують групи об'єктів досліджуваного набору даних - класи; за цими ознаками новий об'єкт можна віднести до того чи іншого класу. Якщо значеннями змінної є значення кінцевого безлічі, то вона має категоріальний тип. Якщо безліч значень змінної у кінцева, то завдання називається класифікацією. Якщо ж безліч значень є множиною дійсних чисел, то завдання називається регресією. Прогнозування (Forecasting) - в результаті рішення задачі прогнозування на основі особливостей історичних даних оцінюються пропущені або ж майбутні значення цільових чисельних показників. В результаті рішення задачі прогнозування на основі особливостей історичних даних оцінюються пропущені або ж майбутні значення цільових чисельних показників.Для вирішення таких завдань широко застосовуються методи математичної статистики, нейронні мережі та ін Оцінювання (Estimation) - завдання оцінювання зводиться до передбачення безперервних значень ознаки.

Останнім часом неухильно зростає інтерес до методів "виявлення знань у базах даних" (knowledge discovery in databases). Обсяги сучасних баз даних, які дуже значні, викликали стійкий попит на нові масштабовані алгоритми аналізу даних. Одним з популярних методів виявлення знань стали алгоритми пошуку асоціативних правил. Асоціативні правила дозволяють знаходити закономірності між пов'язаними подіями. Прикладом такого правила, служить твердження, що покупець, що придбає "Хліб", придбає і "Молоко" з імовірністю 75%. Перший алгоритм пошуку асоціативних правил, що називався AIS був розроблений в 1993 році співробітниками дослідницького центру IBM Almaden. З цією піонерської роботи зріс інтерес до асоціативних правил; на середину 90-х років минулого століття припав пік дослідних робіт у цій області, і з тих пір кожен рік з'являлося по кілька алгоритмів. Алгоритми пошуку асоціативних правил призначені для знаходження всіх правил XY, причому підтримка і достовірність цих правил повинні бути вище деяких наперед визначених порогів, званих відповідно мінімальною підтримкою (minsupport) і мінімальної достовірністю (minconfidence). Задача знаходження асоціативних правил розбивається на дві підзадачі:1. Знаходження всіх наборів елементів, які задовольняють порогу minsupport. Такі набори елементів називаються часто зустрічаються.2. Генерація правил з наборів елементів, знайдених з вірогідністю, що задовольняє порогу minconfidence.Один з перших алгоритмів, ефективно вирішують подібний клас задач, - це алгоритм APriori. Крім цього алгоритму останнім часом було розроблено ряд інших алгоритмів: DHP, Partition, DIC та інші. Значення для параметрів мінімальна підтримка і мінімальна достовірність вибираються таким чином, щоб обмежити кількість знайдених правил. Якщо підтримка має велике значення, то алгоритми знаходитимуть правила, добре відомі аналітикам або настільки очевидні, що немає ніякого сенсу проводити такий аналіз. З іншого боку, низьке значення підтримки веде до генерації величезної кількості правил, що, звичайно, вимагає істотних обчислювальних ресурсів. Тим не менше, більшість цікавих правил знаходиться саме при низькому значенні порогу підтримки. Хоча занадто низьке значення підтримки веде до генерації статистично необгрунтованих правил. При пошуку асоціативних правил ми припускали, що всі аналізовані елементи однорідні. Повертаючись до аналізу ринкової корзини, це товари, що мають абсолютно однакові атрибути, за винятком назви. Однак не складе великої праці доповнити транзакцію інформацією про те, в яку товарну групу входить товар і побудувати ієрархію товарів. Наведемо приклад такого угрупування (таксономії) у вигляді ієрархічної моделі. Введення додаткової інформації про угруповання елементів у вигляді ієрархії дасть наступні переваги:1. Це допомагає встановити асоціативні правила не тільки між окремими елементами, але і між різними рівнями ієрархії (групами).2. Окремі елементи можуть мати недостатню підтримку, але в цілому група може задовольняти порогу minsupport.Для знаходження таких правил можна використовувати будь-який з вищеназваних алгоритмів. Для цього кожну транзакцію потрібно доповнити всіма предками кожного елемента, що входить в транзакцію. Однак, застосування "в лоб" цих алгоритмів неминуче призведе до наступних проблем:1. Елементи на верхніх рівнях ієрархії прагнуть до значно більших значень підтримки порівняно з елементами на нижніх рівнях.2. З додаванням в транзакції груп збільшилася кількість атрибутів і відповідно розмірність вхідного простору. Це ускладнює завдання, а також веде до генерації більшої кількості правил.3. Поява надлишкових правил, що суперечать визначенню узагальненого асоціативного правила, наприклад, "Сок" "Прохолодні напої". Очевидно, що практична цінність такого "відкриття" нульова при 100% достовірності. Отже, потрібні спеціальні оператори, що видаляють подібні надмірні правила.При пошуку асоціативних правил завдання було суттєво спрощена. По суті все зводилося до того, присутній у транзакції елемент чи ні. Тобто якщо розглядати випадок ринкової корзини, то ми розглядали два стани: куплено товар чи ні, проігнорувавши, наприклад, інформацію про те, скільки було куплено, хто купив, характеристики покупця і т.д. І можна сказати, що розглядали "булеві" асоціативні правила. Якщо взяти будь-яку базу даних, кожна транзакція складається з різних типів даних: числових, категоріальних і т.д. Для обробки таких записів і витягання чисельних асоціативних правил був запропонований алгоритм пошуку. Приклад чисельного асоціативного правила: [Вік: 30-35] і [Сімейний стан: одружений] [Місячний дохід: 1000-1500 тугриків]. Крім описаних вище асоціативних правил існують непрямі асоціативні правила, асоціативні правила c запереченням, тимчасові асоціативні правила для подій пов'язаних у часі та інші. Як було сказано, завдання пошуку асоціативних правил вперше була представлена ​​для аналізу ринкової корзини. Асоціативні правила ефективно використовуються в сегментації покупців по поведінці при покупках, аналізі переваг клієнтів, плануванні розташування товарів у супермаркетах, крос-маркетингу, адресній розсилці. Однак, сфера застосування цих алгоритмів не обмежується лише однією торгівлею. Їх також успішно застосовують і в інших областях: медицини, для аналізу відвідувань веб-сторінок (Web Mining), для аналізу тексту (Text Mining), для аналізу даних по перепису населення, в аналізі та прогнозуванні збоїв телекомунікаційного устаткування і т.д. Для розширення можливостей аналізу транзакційних даних з урахуванням тимчасового аспекту, послідовності появи предметів і орієнтованості на конкретного клієнта існує завдання Data Mining під назвою послідовні шаблони (sequential pattern, time-serial sequential pattern). Теорія послідовних шаблонів в чому заснована на теорії асоціативних правил і, по суті, є її розширенням. Зокрема, базовими поняттями в ній також є транзакція, предметний набір, частота набору, підтримка і т.д. Крім цього, для пошуку послідовних шаблонів широко використовується адаптований алгоритм Apriori і його модифікації. Але при розгляді послідовних шаблонів необхідно враховувати ряд особливостей. Головна з них полягає в тому, що якщо в асоціативних правилах розглядається тільки факт спільного появи товарів в одній транзакції, то послідовних шаблонах розглядається послідовність появи товарів. Послідовний шаблон - це завжди послідовність появи предметів і їх груп. Інтуїтивно зрозуміло, що типовою послідовністю (шаблоном) може бути тільки така послідовність, яка зустрічається в базі даних досить часто. Тому при пошуку послідовних шаблонів виникає та ж проблема, що і при пошуку асоціативних правил. Велике число розглянутих предметів породжує величезну кількість можливих послідовностей, що призводить до серйозних обчислювальних витрат при використанні повного перебора.Но і тут застосуємо принцип антімонотонності - послідовності, що містять рідкісні події, не можуть бути частими, що дозволяє істотно знизити простір пошуку. Розглянемо постановку задачі пошуку послідовних шаблонів, використовуючи завдання аналізу ринкової корзини. Саме так вона була спочатку сформульована в основоположною статті Р. Агравал і Р. Шрікант "Mining Sequential Patterns", що дозволить провести аналогії з асоціативними правилами і виявити найбільш істотні відмінності. При цьому будемо дотримуватися термінології першоджерела. Нехай є база даних D, в якій кожен запис являє собою клієнтську транзакцію. Кожна транзакція містить наступні поля: ідентифікатор клієнта, дата / час транзакції, і набір куплених товарів. Введемо обмеження, що жоден клієнт не має двох або більше транзакцій, здійснених в один і той же момент часу. Введемо кілька основних понять. Предметний набір - це непорожній набір предметів (товарів), що з'явилися в одній транзакції. Послідовність - це впорядкований список предметних наборів. Послідовність будемо укладати в трикутні дужки, а предметний набір - в круглі. Тоді, якщо позначати предмети цілими числами, то предметні набори будуть записані у вигляді (2, 4, 5), (1, 3), а послідовність, що містить ці набори <(2, 4, 5), (1, 3)>. Якщо предмети з'явилися в одному наборі, це означає, що вони були придбані одночасно. Позначимо предметний набір I = (i1, i2,..., im) (від англ. Itemset - предметний набір, набір елементів) де ij - предмет. Позначимо послідовність S = I1, I2,..., Im, де Ii - предметний набір. Послідовність 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 називається максимальною, якщо вона не міститься в будь іншій послідовності. Усі транзакції одного клієнта можуть бути показані у вигляді послідовності, в якій вони впорядковані по даті, часу або номером візиту. Такі послідовності будемо називати клієнтськими. Формально це записується таким чином. Нехай клієнт здійснив кілька впорядкованих в часі транзакцій T1, T2,..., T3. Тоді кожен предметний набір у транзакції Ti позначимо I (Ti), а кожну клієнтську послідовність для даного клієнта запишемо як I (T1), I (T2),..., I (T3). Іншими словами, клієнтська послідовність - це послідовність предметних наборів, які містяться в усіх транзакціях, скоєних даним клієнтом. Послідовність S називається підтримуваної клієнтом, якщо вона міститься в клієнтській послідовності даного клієнта. Тоді підтримка послідовності визначається як число клієнтів, що підтримують дану послідовність. Таким чином, поняття підтримки в теорії послідовних шаблонів дещо відрізняється від аналогічного поняття теорії асоціативних правил. Для бази даних клієнтських транзакцій завдання пошуку послідовних шаблонів полягає у виявленні максимальних послідовностей серед усіх послідовностей, що мають підтримку вище заданого порогу. Кожна така максимальна послідовність і є послідовний шаблон. Далі будемо називати послідовності, що задовольняють обмеженню мінімальної підтримки, частими послідовностями (за аналогією з часто зустрічаються предметними наборами або популярними наборами в теорії асоціативних правил). Довжина послідовності - це число предметних наборів, яке в ній міститься. Послідовність довжини k будемо називати k-послідовністю. Підтримкою предметного набору I є число клієнтів, які придбали вхідні в нього предмети в одній транзакції. Таким чином, предметний набір I і 1-послідовність <I> мають одну і ту ж підтримку. Нагадаємо, що в асоціативних правилах предметний набір, що задовольняє рівню мінімальної підтримки, називається частим. Звернемо увагу, що будь-який предметний набір в частій послідовності також повинен бути частим, на що вказує властивість антімонотонності. Отже, будь-яка часта послідовність буде складатися тільки з частих предметних наборів.




Поделиться с друзьями:


Дата добавления: 2015-05-24; Просмотров: 2287; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.013 сек.