Вступ доаналізу асоціативних правил
Останнім часомзадачі пошуку нових знань у великих базах сирих даних стають все більшпопулярними та актуальними. Одним із популярних методів виявлення знань ставалгоритм пошуку так званих асоціативних правил (Association Rules). Суть задачі полягає в знаходженнянаборів об’єктів, які зустрічаються найчастіше серед всієї множини ймовірнихнаборів об’єктів. Першим застосуванням такої задачі був аналіз тенденцій вповедінці покупців у супермаркетах. При цьому аналізувались дані про всіздійснені покупки, які кожен покупець кладе у свій кошик, та одержуваласьінформація про те, які товари переважно купуються разом, в якій послідовності,якими категоріями покупців, в які періоди часу, тощо. Такого роду знання дозволяютьефективно планувати закупку товарів у магазин, розробляти ефективні рекламнікампанії та розкладати товар таким чином, щоб провокувати покупців нарізноманітні покупки.
Наприклад, знабору товарів, які купуються в магазинах, можна виділити такі набори товарів,що переважно купуються одночасно:
- {чіпси, пиво};
- {вода, горіхи};
- {чай, печиво};
- Тощо.
Таким чином,можна зробити висновок про те, що якщо купуються чіпси чи горіхи, то, якправило, купуються, пиво чи вода, відповідно. Отже, можна розмістити ці товарипоруч на прилавках, об’єднати їх в один пакет зі знижкою чи здійснити інші дії.
Задача пошукуасоціативних правил є актуальною не лише у сфері торгівлі. Наприклад, в сферіобслуговування цікавою є інформація про те, якими послугами клієнтикористуються в сукупності. Для одержання цієї інформації вирішується задачааналізу даних про послуги, якими користується один клієнт протягом певногочасу. Це допомагає визначити, наприклад, як найбільш вигідно сформувати пакетипослуг для клієнтів.
В медициніаналізуватись можуть симптоми та хвороби пацієнтів. В цьому випадку знання проте, які поєднання хворів та симптомів зустрічаються найчастіше, дозволяють вмайбутньому ставити правильні діагнози.
Визначення
Щоб датиозначення асоціативного правила, будемо вважати, що існує база даних, якіймістяться записи про всі здійснені покупки в супермаркеті. Кожен записназивається транзакцією і включає дані про набір товарів, куплених однимпокупцем за один візит. Таку транзакцію ще називаю ринковим кошиком.
Нехай /> – це всямножина товарів з супермаркету, що називаються елементами.
Приклад[1]:Ідентифікатор Найменування товару Ціна Шоколад 30.00 1 Чіпси 12.00 2 Кокоси 10.00 3 Вода 4.00 4 Пиво 14.00 5 Горіхи 15.00
Тобто вся множинаелементів (їх загальна кількість рівна /> ) /> буде:
/>.
Кожна транзакція /> описується як:/>. Прикладитранзакцій:
/>
/>
Набір усіхвідомих транзакцій (загальна їх кількість нехай рівна />) позначаємо як />: />.
Нехай для нашогоприкладу:
/>
Тоді множину /> можемопредставити у вигляді:№ транзакції Ідентифікатор товару Найменування товару Ціна 1 Чіпси 12.00 3 Вода 4.00 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.
При пошукуаналітик може вказати мінімальне значення підтримки для наборів, що йогоцікавлять – />.
Набір називаєтьсячастим, якщо значення його підтримки є більшим за вказане мінімальне значення,задане користувачем: />.
Таким чином, припошуку асоціативних правил необхідно знайти множину всіх частих наборів:
/>.
В даному прикладічастими наборами при /> є такі:
/>
З іншого боку,важливо не лише знайти часті набори, але виявити правила «якщо....., то...».Наприклад, в даному прикладі можна досліджувати, наскільки правдивим є правило:якщо «кокоси», то «вода». Тобто важливо не просто знати. Що ці ваелементи часто знаходяться в одному наборі, але й вміти прогнозувати, що припокупці «кокосів» ймовірно буде покупка «води» або навпаки.
Розіб’ємо нашдосліджуваний наборі на два піднабори: /> та />. Наприклад, набір />будемо розглядати як: /> та />, тобто />. Тоді асоціативнимправилом можна назвати імплікацію[2]: />, де />. Правило /> має підтримку:
/>, />
тобто /> – це відсоток зі всіх транзакцій />, що містять інабір />, інабір /> (тобтомістять набір />).
/>
Бо, як було вжезгадано вище, з чотирьох транзакцій дві містять і «Кокоси» і «Воду».
Достовірністю правила називаєтьсяймовірність того, що саме з /> випливає />. Правило /> має достовірність (confidence):
/>,
що показує, який відсоток з усіхтранзакцій />,що містить />,також містить і />.
/>.
Отже, підтримка правила /> рівна 50%(50% зі всіх транзакцій містять і «Кокоси», і «Воду»), а достовірність цьогоправила рівна 66.7% (66.7% зі всіх транзакцій, що містять «Кокоси», такожмістять і «Воду»).
Іншими словами,метою аналізу є встановлення наступних залежностей: якщо в транзакції зустрівсядеякий набір елементів />, то на підставі цього можназробити висновок про те, що інший набір елементів /> також повинен з'явитися в ційтранзакції. Алгоритми пошуку асоціативних правил призначені для знаходженнявсіх правил />,причому підтримка і достовірність цих правил повинні бути вищими за деякінаперед задані пороги, що називаються відповідно мінімальною підтримкою (/>) тамінімальною достовірністю (/>).
Деяківидозміни асоціативних правил
Узагальненіасоціативні правила (Generalized Association Rules)
При пошукуасоціативних правил вище припускалось, що всі аналізовані елементи є однорідними.Проте, повертаючись до аналізу ринкової корзини, не складе великих труднощівдоповнити транзакцію інформацією про те, до якої товарної групи входить товар іпобудувати ієрархію товарів. Приведемо приклад такого групування (таксономії) увигляді ієрархічної моделі.
/>
Нехай дана базатранзакцій та відомо, в які групи (таксони) входять елементи. Тоді з даних можнаодержувати правила, що пов'язують групи з групами, окремі елементи з групами іт.д. Наприклад, якщо покупець купив товар з групи «Безалкогольні напої», то вінкупить і товар з групи «Молочні продукти»: правило />. Ці правила носять назвуузагальнених асоціативних правил.
Введеннядодаткової інформації про угрупування елементів у вигляді ієрархії має своїпереваги, зокрема, допомагає встановити асоціативні правила не тільки міжокремими елементами, але й між різними рівнями ієрархії (групами). Проте здодаванням до транзакції понять груп збільшується кількість атрибутів і,відповідно, розмірність вхідного простору. Це ускладнює завдання, а такожпризводить до генерації більшої кількості правил. Для знаходження узагальненихасоціативних правил бажано використання спеціалізованого алгоритму, який усуваєвищеописані проблеми.
Групуватиелементи можна не тільки по входу до певної товарної групи, але й за іншимихарактеристиками, наприклад за ціною (дешево, дорого), брендом і т.д.
Чисельніасоціативні правила (Quantitative Association Rules)
При пошукуасоціативних правил все зводилося до того, чи присутній в транзакції елемент чині. Тобто, якщо розглядати випадок ринкової корзини, то розглядаємо два стани:куплено товар чи ні. При цьому ігнорується, наприклад, інформація про те,скільки чого було куплено, хто саме купив, тощо. Тобто було розглянуто«булеві» асоціативні правила. Проте можна аналізувати дані різнихтипів: числові, категоріальні і т.д.
Прикладчисельного асоціативного правила:
Якщо «[Вік:30-35]» і «[Сімейний стан: одружений]», то «[Місячний дохід: 1000-1500 гривень]».
Ознайомленняз аналітичною платформою Deductor
Deductor Studio –аналітичне ядро платформи Deductor, що містить повний набір механізмів імпорту,обробки, візуалізації й експорту даних для швидкого й ефективного аналізуінформації. У ньому зосереджені найсучасніші методи видобутку, очищення,маніпулювання та візуалізації даних, а також доступні методи моделювання,прогнозування, кластеризації, пошуку закономірностей та багато інших технологійвидобутку знань (Knowledge Discovery in Databases) і видобутку даних (DataMining).
В Deductor Studioвключений повний набір механізмів, що дозволяє одержати інформацію з будь-якогоджерела даних, провести весь цикл обробки (очищення, трансформацію даних,побудову моделей), відобразити одержані результати у найбільш зручний спосіб(OLAP, таблиці, діаграми, дерева рішень...) і експортувати результати.
Вся робота заналізу даних в Deductor Studio базується на виконанні наступних дій:
- /> Імпорт даних;
- /> Ообробка даних;
- /> Візуалізація;
- /> Експорт даних.
Відправноюточкою для аналізу завжди є процедура імпорту даних. Одержаний набір даних можебути опрацьований будь-яким доступним способом. Результатом опрацювання також єнабір даних, що може опрацьовуватись при потребі і далі. Результати опрацюванняможна звізуалізувати різними способами та експортувати в найбільш популярніформати. Послідовність дій, які проводяться при аналізі даних, називаються сценарієм,який можна автоматично виконувати на будь-яких даних.
DeductorStudio підтримує багато різних джерел даних: промислові СУБД (Oracle, MSSQL...), текстові файли, офісні ужитки (Excel, Access), ADO і ODBC джерела.Очевидно, що Deductor Studio є також повністю інтегрований з багатомірнимсховищем даних Deductor Warehouse.
Підобробкою чи опрацюванням даних мається на увазі будь-яка дія, пов'язана ізперетворенням даних, наприклад, побудова моделей, очищення від шумів чианомальних значень. При цьому механізми обробки можна комбінувати довільнимчином так, щоб досягти найкращого результату.
Візуалізація– це відображення імпортованих та опрацьованих даних. Візуалізувати можнабудь-який об'єкт у сценарії обробки. Програма самостійно аналізує, яким чиномможна відобразити інформацію, а користувач повинен лише вибрати потрібнийваріант.
Майстер імпорту даних />
Майстер імпортудопоможе в інтерактивному покроковому режимі вибрати тип джерела даних і налаштувативідповідні параметри. На першому кроці відкривається список всіх передбачених усистемі типів джерел даних, згрупованих за способом доступу до даних. Списокдоступних джерел може змінюватися залежно від налаштувань/>на панелі підключень, атакож індивідуальних налаштувань доступних дій і доступних джерел даних. Підключеннямназивається налаштоване і назване певним чином під’єднання до зовнішньоїсистеми, що дозволяє обмінюватись із нею даними (приймати чи передавати).
Для викликуМайстра імпорту можна скористатися кнопкою /> «Майстер імпорту» напанелі інструментів /> «Сценарії», вибрати відповіднукоманду з контекстного меню або натиснути . З доступних підключеньклацанням миші виберіть потрібне:
- Сховищаданих:
o /> VirtualWarehouse – імпорт даних з Virual Warehouse;
o /> DeductorWarehouse — імпорт даних з Deductor Warehouse.
- Бізнес-програми:
o /> 1С: Підприємство7.7 – імпорт даних з облікової системи 1С версії 7.7;
o /> 1С: Підприємство8.x – імпорт даних з облікової системи 1С 8.х.
- Бази даних:
o /> База даних – імпортданих з баз даних різних видів.
- Прямийдоступ до файлів:
o /> Текстовий файліз роздільниками – тобто у форматі, в якому стовпці даних розділені однотипнимисимволами-роздільниками;
o /> Імпорт з DBF –прямий доступ до файлів плоских баз даних типу DBF, що підтримується такими ужитками,як dBase, FoxBase, FoxPro.
- МеханізмMS ADO:
o /> MicrosoftExcel – книга Microsoft Excel (*.xls);
o /> MicrosoftAccess – файл СУБД Microsoft Access (*.mdb);
o /> Імпорт з DBF(ADO) – доступ через ADO[3] до файлів плоских базданих типу DBF, що підтримується такими ужитками, як dBase, FoxBase, FoxPro;
o /> Текстовий файлз доступом через ADO – тобто текстовий файл із роздільниками, доступ до якого здійснюєтьсячерез механізм ADO;
o /> ADO-джерело –імпорт даних безпосередньо за допомогою системних налаштувань механізму ADO.
Кількості кроківМайстри імпорту та параметрів відрізянються для різних типів джерел. На кожномукроці Майстра імпорту доступні кнопки «Далі» та «Назад», які дозволяють перейтидо наступного кроку або повернутися на попередній крок для внесення змін ураніше налаштовані параметри. Кнопка «Скасувати» дозволить відмовитися відвикористання Майстра імпорту.
Майстер опрацювання даних
Майстеропрацювання даних допоможе в інтерактивному покроковому режимі налаштувати всінеобхідні етапи обробки даних. У вікні першого кроку Майстри наведені всі доступнів системі методи опрацювання даних, згруповані за типом. Для виклику Майстраопрацювання даних можна скористатися кнопкою /> «Майстер обробки» на панеліінструментів /> «Сценарії», попередньо виділившипотрібну гілку у сценарії або вибравши відповідну команду з контекстного меню ().
Здоступних алгоритмів опрацювання даних потрібно вибрати один, скориставшисьмишкою:
- Очищенняданих:
o /> Парціальна обробка– алгоритми відновлення, згладжування та редагування аномальних даних.
o /> Факторний аналіз– для зниження розмірності вхідних факторів. Зниження розмірності необхідно увипадках, коли вхідні фактори є скорельованими один з одним, тобтовзаємозалежні. У факторному аналізі мова йде про виділення з множини вимірюваниххарактеристик об'єкта нових факторів, що більш адекватно відображають властивостіоб'єкта.
o /> Кореляційнийаналіз – усунення факторів, що не сильно впливають на результат (вихідні поля):такі фактори можуть бути виключені з розгляду практично без втрати корисноїінформації. Критерієм прийняття рішення про виключення фактора служить порогчутливості: якщо кореляція (ступінь взаємозалежності) між вхідним та вихіднимфакторами є нижчою за поріг чутливості, то відповідний вхідний факторвідкидається як незначний.
o /> Дублікати та протиріччя– виявлення дублікатів та суперечливих записів у вхідному наборі даних.
o /> Фільтрація –фільтрація записів вибірки за заданими умовами.
- Трансформаціяданих:
o /> Налаштуваннянабору даних – налаштування параметрів полів: можна змінити ім'я, мітку, тип,вид і призначення полів, а також налаштувати кешування проміжних даних.
o /> Ковзаюче вікно– дозволяє здійснювати перетворення даних методом ковзаючого вікна.
o /> Дата і час – опрацюванняданих у форматі «дата» і «час» (наприклад, перетворення вхідних даних у днях вдані по тижнях).
o /> Квантування значеньвибірки – процес, в результаті якого відбувається розподілення значеньнеперервних даних між скінченною кількістю інтервалів заданої довжини.
o /> Сортування –сортування записів у вхідній вибірці даних.
o /> Злиття – об'єднанняданих із двох таблиць.
o /> Заміна –заміна значень згідно таблиці підстановки.
o /> Групуванняданих.
o /> Разгрупуванняданих – відновлення вибірки, до якої була застосована операція групування.
- DataMining:
o /> Прогнозування часовогоряду. Наприклад, методом ковзаючого вікна було одержано часовий ряд: />, а потрібноспрогнозувати наступне значення /> на основі всіх попередніхзначень.
o /> Автокореляція –автокореляційний аналіз даних, метою якого є з'ясування ступеня статистичноїзалежності між різними значеннями випадкової послідовності. У процесіавтокореляційного аналізу розраховуються коефіцієнти кореляції (міра взаємноїзалежності) для двох значень вибірки, що перебувають один від одного на певній відстані(кількість проміжних значень між ними), яку називають також лагом. Сукупністькоефіцієнтів кореляції по всіх лагах називається автокореляційною функцією ряду.За поведінкою цієї функції можна судити про характер аналізованоїпослідовності: ступеня її гладкості, наявності періодичності, тощо.
o /> Лінійна регресія– будується модель даних у вигляді набору коефіцієнтів лінійного перетворення.
o /> Логістичнарегресія – будується бінарна логістична регресійна модель.
o /> Нейромережа –опрацювання даних за допомогою багатошарової нейронної мережі.
o /> Дерево рішень– опрацювання даних за допомогою дерев рішень.
o /> Самоорганізованікарти – виконується кластеризація даних.
o /> Асоціативніправила – виявлення залежностей між взаємозв'язаними подіями.
o /> Користувацькамодель – задання моделі вручну за формулами.
- Інше:
o /> Скрипт – застосуваннямоделі до нових даних. Скриптипризначені для автоматизації процесу додавання в сценарій однотипних гілокобробки. По суті скрипт є динамічною копією вибраної ділянки сценарію. Призміні оригінальної гілки змінюється і скрипт, який посилається на неї.Наприклад, після імпорту даних з двох різних баз даних потрібно провести їхпопередню обробку (очистити дані, згладити, поміняти назви стовпців, додатикілька однакових значень, тощо) та побудувати однакові моделі прогнозу, а потімекспортувати отримані дані назад. Для першої гілки (першої БД) ці діїпроводяться як звичайно: послідовними кроками будується ланцюжок обробників.Для другого джерела (другої БД) достатньо буде створити вузол імпорту, до якогопотрібно приєднати скрипт, що базується на побудованій першій гілці. У цьому скриптібудуть виконані точно такі ж дії, як в оригінальній гілці. На виході скриптаставиться вузол експорту, і друга гілка є готовою до використання. Аналогомскриптів є функції та процедури в мовах програмування: гілка обробки будуєтьсяодин раз, а потім за допомогою скриптів виконуються закладені в нійуніверсальні обробники.
o /> Калькулятор – дозволяє сформувати нове поле вибіркияк результат обчислень над даними з інших полів.
o /> Умова – дозволяє організувати умовне виконаннясценарію обробки даних.
o /> Команда OC – забезпечує формування й запускрізних команд операційної системи.
Залежновід обраного методу Майстер обробки буде містити різне число кроків і набірпараметрів, що надбудовуються на кожному кроці.На кожному кроці Майстра обробки доступні кнопки «Далі»,«Назад» та «Скасувати».
Майстер візуалізаціїданих
Майстервізуалізації допоможе в інтерактивному покроковому режимі вибрати та налаштуватинайбільш зручний спосіб подання даних. В залежності від обраного способу візуалізаціїбудуть налаштовуватись різні параметри, а Майстер, відповідно, буде міститирізне число кроків.
Длявиклику Майстра візуалізації можна скористатися кнопкою /> «Майстер візуалізації»на панелі інструментів /> «Сценарії», попередньо виділившипотрібну гілку у сценарії опрацювання або вибравши відповідну команду зконтекстного меню для даної гілки сценарію.
Виконання аналізу асоціативних правил
Напершому кроці необхідно імпортувати дані в Deductor. Використовуючи кнопку />, вказуємо шлях дотекстового файлу з роздільниками. Для прикладу, можна вибрати один із готовихприкладів у папці «Samples» – Supermarket.txt:
/>
Пілсянатискування кнопки «Далі» вказуємо тип роздільника та інші параметри імпорту. Наступнимкроком є вказання параметрів стопвпців:
/>
Після цьогонатискаємо кнопку «Далі», а потім – «Пуск». Після виконання процесу імпортуданих з текстового файлу потрібно вибрати спосіб їх відображення (зазамовчуванням – таблиця). Після цього маємо дані, готові для опрацювання:
асоціативнийправило аналітичний
/>
Стаємо навідповідну гілку в сценарії та натискаємо кнопку /> Майстра обробки даних:
/>
Серед методівопрацювання даних вибираємо /> Асоціативні правила, після чогопотрібно вказати, який стовпець відповідає за номер чи ідентифікатортранзакції, а який містить самі елементи (в даному випадку – покупки):
/>
Наступневікно дозволяє вказати значення мінімальних та максимальних підтримки тадостовірності правил:
/>
В наступномувікні натискаємо кнопку «Пуск», після чого здійснюється аналіз згідно вказанихзначень:
/>
Далі зновупропонуються різні способи візуалізації даних. Вибираємо всі способивідображення, що знаходяться в групі «Data Mining». В результаті одержуємо:
- Набірасоціативних правил з вказанням їх підтримки, достовірності та кількості.
- Популярнінабори елементів (в даному випадку – покупок).
- Деревоправил за наслідком, наприклад:
/>
щобуде показувати, після покупки яких продуктів далі ймовірно будуть купленісухарі.
- Можливістьрозрахувати умову «якщо… то...»: наприклад, можна вказати умову «вафлі», апотім натиснути кнопку «Розрахувати правила» або Ctrl+Enter. Після цього внизу в області наслідку з’являться відповідні записи«чай», «сухарі», «сухарі і чай» з вказанням всіх параметрів.