Визначення поняття Data Mining

Хеш–дерево з кандидатами–наборами побудовано, зараз, використовуючи хеш–дерево, легко підрахувати підтримку для кожного кандидата. Для цього потрібно "пропустити" кожну транзакцію через дерево і збільшити лічильники для тих кандидатів, чиї елементи також містяться і в транзакції, тобто C_k T_i = C_k. На кореневому рівні хеш–функція застосовується до кожного елемента з транзакції. Далі, на другому рівні, хеш–функція застосовується до других елементів і т.д. На k–рівні хеширується k–елемент. І так до тих пір, поки не досягнемо листа. Якщо кандидат, що зберігається в листі, є підмножиною даної транзакції, тоді збільшуємо лічильник підтримки цього кандидата на одиницю.

Після того, як кожна транзакція з  початкового набору даних "пропущена" через дерево, можна перевірити чи задовольняють значення підтримки кандидатів мінімальному порогу. Кандидати, для яких ця умова виконується, переносяться в розряд часто зустрічаємих. Крім того, слід запам'ятати і підтримку набору, вона нам стане в нагоді при витяганні правил. Ці ж дії застосовуються для знаходження (k+1)–елементних наборів і т.д.

Після того, як знайдені всі часто зустрічаємі набори елементів можна приступити безпосередньо до генерації правил.

Витягання правил – менш трудомістка задача. По–перше, для підрахунку достовірності правила достатньо знати підтримку самого набору і множини, що лежить в умові правила. Наприклад, є набір {А, B, С}, що часто зустрічається, і потрібно підрахувати достовірність для правила AB С. Підтримка самого набору нам відома, але і його множина {А, B}, що лежить в умові правила, також часто зустрічається через властивість анти–монотонності, і значить, його підтримка нам відома. Тоді ми легко зможемо підрахувати достовірність. Це позбавляє нас від небажаного перегляду бази транзакцій, який був б потрібен в тому випадку, якщо б це підтримка була невідома.

Щоб витягнути правило із часто зустрічає мого набору F, слід знайти всі його не порожні підмножини. І для кожної підмножини s ми зможемо сформулювати правило s (F – s), якщо достовірність правила                       conf(s (F – s)) = supp(F)/supp(s) не менше порогу minconf.

Помітимо, що чисельник залишається  постійним. Тоді достовірність має  мінімальне значення, якщо знаменник має максимальне значення, а це відбувається у тому випадку, коли в умові правила є набір, що складається з одного елемента. Все супермножина даної множини має меншу або рівну підтримку і, відповідно, більше значення достовірності. Ця властивість може бути використана при витяганні правил. Якщо ми почнемо витягувати правила, розглядаючи спочатку тільки один елемент в умові правила, і це правило має необхідну підтримку, тоді всі правила, де в умові стоїть супермножина цього елемента, також мають значення достовірності вище заданого порогу. Наприклад, якщо правило А BCDE задовольняє мінімальному порогу достовірності minconf, тоді AB CDE також задовольняє. Для того, щоб витягнути всі правила використовується рекурсивна процедура. Важливе зауваження: будь-яке правило, складене з набору, що часто зустрічається, повинне містити всі елементи набору. Наприклад, якщо набір складається з елементів {А, B, С}, то правило А B не повинне розглядатися.

 

3 DATA MINING ЯК ЧАСТИНА СИСТЕМИ АНАЛІТИЧНОЇ ОБРОБКИ ІНФОРМАЦІЇ

 

 

3.1 Сховища даних

 

Інформаційні системи  сучасних підприємств часто організовані так, щоб мінімізувати час введення і коректування даних, тобто організовані не оптимально з погляду проектування бази даних. Такий підхід ускладнює доступ до історичних (архівним) даних. Зміни структур в базах даних інформаційних систем дуже трудомісткі, а іноді просто неможливі.

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

Якщо дані зберігаються в базах даних різних інформаційних  систем підприємства, при їх аналізі виникає ряд складнощів, зокрема, значно зростає час, необхідний для обробки запитів; можуть виникати проблеми з підтримкою різних форматів даних, а також з їх кодуванням; неможливість аналізу тривалих рядів ретроспективних даних і т.д.

Ця проблема розв'язується шляхом створення сховища даних. Задачею такого сховища є інтеграція, актуалізація і узгодження оперативних даних з різнорідних джерел для формування єдиного несуперечливого погляду на об'єкт управління в цілому. На основі сховищ даних можливо складання всілякої звітності, а також проведення оперативної аналітичної обробки і Data Mining.

Тоді загальна схема  інформаційного сховища буде виглядати наступнім чином:

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 3.1 – Структура  інформаційної системи

 

Біл Інмон (Bill Inmon) визначає сховища  даних як "наочно орієнтовані, інтегровані, немінливі, підтримуючі хронологію набори даних, організовані з метою підтримки управління" і покликані виступати в ролі "єдиного і єдиного джерела істини", яке забезпечує менеджерів і аналітиків достовірною інформацією, необхідною для оперативного аналізу і ухвалення рішень[3].

Наочна орієнтація сховища даних означає, що дані з'єднані в категорії і зберігаються відповідно областям, які вони описують, а не застосуванням, що їх використовують.

Інтегрованість означає, що дані задовольняють вимогам всього підприємства, а не однієї функції бізнесу. Цим сховище даних гарантує, що однакові звіти, що згенерували для різних аналітиків, міститимуть однакові результати.

Прив'язка до часу означає, що сховище можна розглядати як сукупність "історичних даних": можливо відновлення даних на будь-який момент часу. Атрибут часу явно присутній в структурах сховища даних.

Незмінність означає, що, потрапивши один раз в сховищі, дані там зберігаються і не змінюються. Дані в сховищі можуть лише додаватися.

Річард Хакаторн, інший основоположник цієї концепції, писав, що мета Сховищ Даних – забезпечити для організації "єдиний образ існуючої реальності"[3].

Іншими словами, сховище  даних є своєрідним накопичувачем  інформації про діяльність підприємства.

Дані в сховищі представлені у вигляді багатовимірних структур під назвою "зірка" або "сніжинка".

 

 

3.2 Організація інформаційного сховища в реалізації бази даних. Схеми зірка та сніжинка

 

Схема типу зірки (Star Schema) – схема реляційної бази даних, що служить для підтримки багатовимірного представлення даних, які в ній зберігаються.

Особливості ROLAP-схеми типу "зірка":

а) одна таблиця фактів (fact table), яка сильно денормалізована. Є центральною в схемі, може складатися з мільйонів рядків і містить підсумовувані або фактичні дані, за допомогою яких можна відповісти на різні питання;

б) декілька денормалізованих таблиць вимірювань (dimensional table). Мають меншу кількість рядків, ніж таблиці фактів, і містять описову інформацію. Ці таблиці дозволяють користувачу швидко переходити від таблиці фактів до додаткової інформації;

в) таблиця фактів і таблиці розмірності зв'язані ідентифікуючими зв'язками, при цьому первинні ключі таблиці розмірності мігрують в таблицю фактів як зовнішні ключі. Первинний ключ таблиці факту цілком складається з первинних ключів всіх таблиць розмірності;

ґ) агреговані дані зберігаються спільно з початковими.

Рисунок 3.2 – Схема «зірка»

Схема типу сніжинки (Snowflake Schema) – схема реляційної бази даних, яка служить для підтримки багатовимірного представлення даних,що в ній знаходяться, є різновидом схеми типу "зірка" (Star Schema).

Особливості ROLAP-схеми типу "сніжинка":

а) одна таблиця фактів (fact table), яка сильно денормалізована. Є центральною в схемі, може складатися з мільйонів рядків і містити підсумовувані або фактичні дані, за допомогою яких можна відповісти на різні питання;

б) декілька таблиць вимірювань (dimensional table), які нормалізовані на відміну від схеми "зірка". Мають меншу кількість рядків, ніж таблиці фактів, і містять описову інформацію. Ці таблиці дозволяють користувачу швидко переходити від таблиці фактів до додаткової інформації. Первинні ключі в них складаються з єдиного атрибута (відповідають єдиному елементу вимірювання);

в) таблиця фактів і таблиці розмірності зв'язані ідентифікуючими зв'язками, при цьому первинні ключі таблиці розмірності мігрують в таблицю фактів як зовнішні ключі. Первинний ключ таблиці факту цілком складається з первинних ключів всіх таблиць розмірності;

ґ) в схемі "сніжинка" агреговані дані можуть зберігатися окремо від початкових.

Рисунок 3.3 – Схема «сніжинка»

 

 

3.3 OLAP-системи

 

В основі концепції OLAP, або  оперативної аналітичної обробки даних (On-Line Analytical Processing), лежить багатовимірне концептуальне представлення даних (Multidimensional conceptual view).

Термін OLAP введений Коддом (E. F. Codd) в 1993 році. Головна ідея даної системи полягає в побудові багатовимірних таблиць, які можуть бути доступний для запитів користувачів. Ці багатовимірні таблиці або так звані багатовимірні куби будуються на основі початкових і агрегованих даних. І початкові, і агреговані дані для багатовимірних таблиць можуть зберігатися як в реляційних, так і в багатовимірних базах даних. Взаємодіючи з OLAP-системою, користувач може здійснювати гнучкий перегляд інформації, одержувати різні зрізи даних, виконувати аналітичні операції деталізації, згортки, крізного розподілу, порівняння в часі. Вся робота з OLAP-системою відбувається в термінах наочної області[3].

Існує три способи зберігання даних  в OLAP-системах або три архітектура OLAP - серверів:

• MOLAP (Multidimensional OLAP);
• ROLAP (Relational OLAP);
• HOLAP (Hybrid OLAP).

Таким чином, згідно цієї класифікації OLAP-продукти можуть бути представлений трьома класами систем:

• у разі MOLAP, початкові і багатовимірні дані зберігаються в багатовимірній БД або в багатовимірному локальному кубі;
• в ROLAP-продуктах початкові дані зберігаються в реляційних БД або в плоских локальних таблицях на файл-сервері. Агрегатні дані можуть поміщатися в службові таблиці в тій же БД;
• у разі використовування гібридної архітектури, тобто в HOLAP-продуктах, початкові дані залишаються в реляційній базі, а агрегати розміщуються в багатовимірній.

Логічним уявленням є багатовимірний куб — це набір зв'язаних заходів і вимірювань, які використовуються для аналізу даних[3].

OLAP-куб підтримує  всі багатовимірні операції: довільне розміщення вимірювань і фактів, фільтрація, сортування, угрупування, різні способи агрегації і деталізації. Дані відображаються у вигляді крос-таблиць і крос-діаграм, всі операції відбуваються "на льоту", методи маніпулювання інтуїтивно зрозумілі.

OLAP-куб – могутній інструмент  дослідження, що дозволяє проводити  розвідувальний і порівняльний аналіз, виявляти тенденції, знаходити сезонність і тренд, визначати кращі і гірші товарні позиції, розраховувати їх частки у продажі.

 

 

 

3.4 Інтеграція OLAP і Data Mining

 

Обидві технології можна розглядати як складові частини процесу підтримки  ухвалення рішень. Проте ці технології як би рухаються у різних напрямах: OLAP зосереджує увагу виключно на забезпеченні доступу до багатовимірних даних, а методи Data Mining в більшості випадків працюють з плоскими одновимірними таблицями і реляційними даними.

Інтеграція технологій OLAP і Data Mining "збагатила" функціональність і  однієї, і іншої технології. Ці два  види аналізу повинні бути тісно  з'єднано, щоб інтегрована технологія могла забезпечувати одночасно багатовимірний доступ і пошук закономірностей.

Засіб багатовимірного інтелектуального аналізу даних повинен знаходити  закономірності як в тих, що деталізуються, так і в агрегованих з різним ступенем узагальнення даних. Аналіз багатовимірних даних повинен будуватися над гіперкубом спеціального вигляду, вічка якого містять не довільні чисельні значення (кількість подій, об'єм продажів, сума зібраних податків), а числа, що визначають вірогідність відповідного поєднання значень атрибутів. Проекції такого гіперкуба (що виключають з розгляду окремі вимірювання) також повинні досліджуватися на предмет пошуку закономірностей. J. Han пропонує ще більш просту назву - "OLAP Mining" і висуває декілька варіантів інтеграції двох технологій[3]:

а) "Cubing then mining". Можливість виконання інтелектуального аналізу повинна забезпечуватися над будь-яким результатом запиту до багатовимірного концептуального уявлення, тобто над будь - яким фрагментом будь - якої проекції гіперкуба показників;

б) "Mining then cubing". Подібно даним, витягнутим з сховища, результати інтелектуального аналізу повинні представлятися в гіперкубічній формі для подальшого багатовимірного аналізу;

в) "Cubing while mining". Цей гнучкий спосіб інтеграції дозволяє автоматично активізувати однотипні механізми інтелектуальної обробки над результатом кожного кроку багатовимірного аналізу (переходу між рівнями узагальнення, витягання нового фрагмента гіперкуба і т.д.).

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