Реферат Інтелектуальний аналіз даних

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Курсовая работа Дипломная работа Контрольная работа Реферат Отчет по практике Эссе Доклад Решение задач Научно-исследовательская работа Монография Аспирантский реферат Магистерская работа Научная статья Публикация статьи в ВАК Публикация статьи в Scopus Дипломная работа MBA Бизнес-план Тест/экзамен online Чертеж Рецензия

Принимаю Политику конфиденциальности

Продолжить

Скидка 25% при заказе до 26.12.2024

ВСТУП
Останнім часом для вирішення практичних завдань все частіше застосовуються методи інтелектуального аналізу даних (Data Mining). Інтелектуальний аналіз даних (англ. Data Mining) — виявлення прихованих закономірностей або взаємозв'язків між змінними у великих масивах необроблених даних. Підрозділяється на завдання класифікації, моделювання і прогнозування та інші.

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

-       постановка задачі;

-       підготовка даних;

-       перегляд даних;

-       побудова моделей;

-       дослідження, перевірка, прогнозування за допомогою моделей;

-       розгортання і оновлення моделей.

До складу  Microsoft SQL Server 2005 і 2008 входить цілий ряд служб, які дозволяють виконати кожен крок. Вихідна база даних , як правило, є реляційною,  для побудови і наповнення даними інформаційного сховища використовується служба Integration Services, куб будується і представляється  в Analysis Services, робота з моделями здійснюється в  Biseness Intelligence Studio з використанням спеціальної мови DMX.

На основі цих методів були розроблені алгоритми пошуку асоціативних правил. Вперше ці алгоритми були запропоновані для знаходження типових шаблонів покупок, що здійснюються в супермаркетах. Згодом завдання було розширене, і зараз ці алгоритми вирішують проблему пошуку закономірностей між зв'язаними подіями. Прикладом асоціативного правила може служити вислів, що людина, що купила молоко, також купить хліб за один візит в магазин.

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

Для досягнення цієї мети необхідно вирішити ряд задач:

-       створити структуру інформаційного сховища на базі OLTP (Online Transaction Process) бази даних, що містить інформацію про продажі товарів; 

-       організувати періодичне перевантаження даних з OLTP в інформаційне сховище;

-       створити модель інтелектуального аналізу структури споживчої корзини по алгоритму  асоціативних правил;

-       провести аналіз моделі і прогнозування.

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

Після створення моделі можна провести її аналіз на предмет виявлення цікавих для нас (шаблонів) правил.

Метою аналізу є встановлення наступних залежностей: якщо в транзакції зустрівся деякий набір елементів X, то на підставі цього можна зробити висновок про те, що інший набір елементів Y також повинен з'явитись в цій транзакції. Встановлення таких залежностей дає нам можливість знаходити дуже прості і інтуїтивно зрозумілі правила.

Сучасні бази даних мають дуже великі розміри, досягаючи гіга- і терабайтів, і  тенденцію до подальшого збільшення. І тому, для знаходження асоціативних правил потрібні ефективні масштабовані алгоритми, що дозволяють вирішити задачі за певний час. Один з алгоритмів, що ефективно вирішують подібний клас задач – це алгоритм Apriori.

На основі аналізу можемо створити прогноз даних. 

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

Для створення прогнозів використовується мова Data Mining Extensions (DMX), яка є розширенням SQL і містить команди для створення, зміни моделей і здійснення передбачень на підставі різних моделей.


1 ОГЛЯД ІСНУЮЧИХ МЕТОДІВ ІНТЕЛЕКТУАЛЬНОГО АНАЛІЗУ ДАНИХ
1.1 Визначення поняття Data Mining
Data Mining – це процес підтримки ухвалення рішень, заснований на пошуку в даних прихованих закономірностей (шаблонів інформації).

Технологію Data Mining достатньо точно визначає Григорій Піатецкий - Шапіро (Gregory Piatetsky-Shapiro) – один із засновників цього напряму: “Data Mining – це процес виявлення в сирих даних раніше невідомих, нетривіальних, практично корисних і доступних інтерпретації знань, необхідних для ухвалення рішень в різних сферах людської діяльності” [4].

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

Неочевидних – це значить, що знайдені закономірності не виявляються стандартними методами обробки інформації або експертним шляхом.

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

Практично корисних – це значить, що висновки мають конкретне значення, якому можна знайти практичне застосування.

Знання – сукупність відомостей, яка утворює цілісний опис, відповідний деякому рівню обізнаності про описуване питання, предмет, проблему і т.д.

Використовування знань (knowledge deployment) означає дійсне застосування знайдених знань для досягнення конкретних переваг (наприклад, в конкурентній боротьбі за ринок).

Приведемо ще декілька визначень поняття Data Mining.

Data Mining – це процес виділення з даних неявної і неструктурованої інформації і представлення її у вигляді, придатному для використовування.

Data Mining – це процес виділення, дослідження і моделювання великих об'ємів даних для виявлення невідомих до цього шаблонів (patterns) з метою досягнення переваг в бізнесі (визначення SAS Institute).

Data Mining – це процес, мета якого – знайти нові значущі кореляції, зразки і тенденції в результаті просівання великого об'єму бережених даних з використанням методик розпізнавання зразків плюс застосування статистичних і математичних методів (визначення Gartner Group).

 «Mining»  англійською означає «видобуток корисних копалин», а пошук закономірностей у величезній кількості даних дійсно схожий на цей процес.

Перш ніж використовувати технологію Data Mining, необхідно ретельно проаналізувати її проблеми [4]:

-       Data Mining не може замінити аналітика;

-       не може складати розробки і експлуатації додатку Data Mining;

-       потрібна  підвищена кваліфікація користувача;

-       витягання корисних відомостей неможливе без доброго розуміння суті даних;

-       складність підготовки даних;

-       висока вартість;

-       вимога наявності достатньої кількості репрезентативних даних.

Data Mining тісно пов’язана з різними  дисциплінами , що засновані на    інформаційних технологіях та математичних методах обробки інформаціі (рисунок 1.1). 




Рисунок 1.1 –  Data Mining як мультідісциплінарна область
Кожний з напрямів, що сформували Data Mining, має свої особливості. Проведемо порівняння з деякими з них.

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

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

Статистика оперує даними, що отримані в результаті спостережень або експериментів.

Перевагами є:

-       більш ніж Data Mining, базується на теорії;

-       більш зосереджується на перевірці гіпотез.

Єдиного визначення машинного навчання на сьогоднішній день немає.

Машинне навчанняможна охарактеризувати як процес отримання програмою нових знань. Мітчелл в 1996 році дав таке визначення: «Машинне навчання – це наука, яка вивчає комп'ютерні алгоритми, автоматично що поліпшуються під час роботи».

Одним з найпопулярніших прикладів алгоритму машинного навчання є нейронні мережі.

Алгоритми машинного навчання є:

-       більш евристичні;

-       концентрується на поліпшенні роботи агентів навчання.

Переваги Data Mining:

-       інтеграція теорії і евристик;

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




1.3  Методи Data Mining

Методи, що використовує технологія Data Mining можна розподілити на технологічні, статистичні та кібернетичні.

Таблиця 1.1- Методи Data Mining

Методи Data Mining	Характеристика
Технологічні методи	а) безпосереднє використання даних, або збереження даних. Методи цієї групи: кластерний аналіз, метод найближчого сусіда; б) виявлення і використання формалізованих закономірностей, або дистиляція шаблонів - логічні методи, методи візуалізації, методи крос-табуляції, методи, що засновані на рівняннях.
Статистичні методи	а) дескриптивний аналіз і опис вихідних даних; б) аналіз зв'язків (кореляційний і регресійний аналіз, факторний аналіз, дисперсійний аналіз); в) багатовимірний статистичний аналіз (компонентний аналіз, дискримінантний аналіз, багатовимірний регресійний аналіз, канонічні кореляції і ін.); г) аналіз тимчасових рядів (динамічні моделі і прогнозування).
Кібернетичні методи	а)штучні нейронні мережі (розпізнавання, кластеризація, прогноз); б) еволюційне програмування (в т.ч. алгоритми методу групового обліку аргументів);  в) генетичні алгоритми (оптимізація); ґ) асоціативний алгоритм; г) нечітка логіка; д) дерева рішень; є) системи обробки експертних знань.

1.4 Відмінності Data Mining від інших методів аналізу даних
Традиційні методи аналізу  даних  в основному орієнтовані на перевірку наперед сформульованих гіпотез (статистичні методи) і на «грубий розвідувальний аналіз», що становить основу оперативної аналітичної обробки даних (Online Analytical Processing, OLAP), тоді як одне з основних положень Data Mining – пошук неочевидних закономірностей. Інструменти Data Mining можуть знаходити такі закономірності самостійно і також самостійно будувати гіпотези про взаємозв'язки. Оскільки саме формулювання гіпотези щодо залежності є найскладнішою задачею, перевага Data Mining в порівнянні з іншими методами аналізу є очевидною.

Більшість статистичних методів для виявлення взаємозв'язків в даних використовує концепцію усереднювання по вибірці, що приводить до операцій над неіснуючими величинами, тоді як Data Mining оперує реальними значеннями.

OLAP більше підходить для розуміння ретроспективних даних, Data Mining спирається на ретроспективні дані для отримання відповідей на питання про майбутнє.


2 МАТЕМАТИЧНА ПОСТАНОВКА ЗАДАЧ ІНТЕЛЕКТУАЛЬНОГО АНАЛІЗУ – АЛГОРИТМ АСОЦІАТИВНИХ ПРАВИЛ
Однією з задач Data Mining є асоціація. Метою пошуку асоціативних правил (association rule) є знаходження закономірностей між зв'язаними подіями в базах даних.

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

Наведемо простий приклад асоціативного правила: покупець, що придбаває банку фарби, придбає пензлик для фарби з вірогідністю 50%.

Вперше ця задача була запропонована пошуку асоціативних правил для знаходження типових шаблонів покупок, які придбають в супермаркетах, тому іноді її ще називають аналізом ринкової корзини (market basket analysis).

Хай є база даних, що складається з купівельних транзакцій. Кожна транзакція – це набір товарів, куплених покупцем за один візит. Таку транзакцію ще називають ринковою корзиною.

Визначення 1. Хай I = {i₁, i₂, i3 ... i_n} – безліч (набір) товарів, званих елементами. Хай D - безліч транзакцій, де кожна транзакція T – це набір елементів з I, TI. Кожна транзакція є бінарним вектором, де t[k]=1, якщо i_k елемент присутній в транзакції, інакше t[k]=0. Ми говоримо, що транзакція T містить X, деякий набір елементів з I, якщо XT. Асоціативним правилом називається імплікація XY, де XI, YI і XY=. Правило XY має підтримку s (support), якщо s% транзакцій з D, містять XY,                       supp(XY) = supp(XY). Достовірність правила показує, яка вірогідність того, що з X слідує У. Правило XY справедливо з достовірністю (confidence) з, якщо c% транзакцій з D, що містять X, також містять У,                                         conf(XY) = supp(XY)/supp(X).

Покажемо на конкретному прикладі: "75% транзакцій, що містять хліб, також містять молоко. 3% від загального числа всіх транзакцій містять обидва товари". 75% - це достовірність (confidence) правила, 3% це підтримка (support), або "Хліб" "Молоко" з вірогідністю 75%.

Іншими словами, метою аналізу є встановлення наступної залежності: якщо в транзакції зустрівся деякий набір елементів X, то на підставі цього можна зробити висновок про те, що інший набір елементів У також повинен з'явитись в цій транзакції. Встановлення такої залежності дає нам можливість знаходити дуже прості і інтуїтивно зрозумілі правила.

Алгоритми пошуку асоціативних правил призначені для знаходження всіх правил X У, причому підтримка і достовірність цих правил повинна бути вищою за деякі наперед певні пороги, звані відповідно мінімальною підтримкою (minsupport) і мінімальною достовірністю (minconfidence).

Задача знаходження асоціативних правил розбивається на дві підзадачі:

а)     знаходження всіх наборів елементів, які задовольняють порогу minsupport. Такі набори елементів називаються тими, що часто зустрічаються;

б)    генерація правил з наборів елементів, знайдених згідно п. a) з достовірністю, що задовольняє порогу minconfidence.

Один з перших алгоритмів, ефективно вирішальних подібний клас задач, – це алгоритм APriori. Окрім цього алгоритму останнім часом був розроблений ряд інших алгоритмів: DHP, Partition, DIC і інші.

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

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

2.1 Узагальнені асоціативні правила (Generalized Association Rules)
При пошуку асоціативних правил, ми припускали, що всі аналізовані елементи однорідні. Повертаючись до аналізу ринкової корзини, це товари, абсолютно однакові атрибути, що мають, за винятком назви. Проте не складе великих труднощів доповнити транзакцію інформацією про те, до якої товарної групи входить товар і побудувати ієрархію товарів.

Наприклад, якщо Покупець купив товар з групи "Безалкогольні напої", то він купить і товар з групи "Молочні продукти" або "Сік". Ці правила носять назву узагальнених асоціативних правил.

Визначення 2. Узагальненим асоціативним правилом називається імплікація XY, де XI, YI і XY= і де жоден з елементів, що входять в набір У, не є предком жодного елемента, що входить в X. Підтримка і достовірність підраховуються так само, як і у разі асоціативних правил (див. Визначення 1).

Введення додаткової інформації про угрупування елементів у вигляді ієрархії дасть наступні переваги:

а)     це допомагає встановити асоціативні правила не тільки між окремими елементами, але і між різними рівнями ієрархії (групами);

б)    окремі елементи можуть мати недостатню підтримку, але в цілому група може задовольняти порогу minsupport;

в)    для знаходження таких правил можна використовувати будь-який з вищеназваних алгоритмів.

Групувати елементи можна не тільки по входженню в певну товарну групу, але і по інших характеристиках, наприклад за ціною (дешево, дорого), бренду і т.д.

Алгоритм пошуку асоціативних правил, заснований на аналізі частих наукових наборів. Спочатку в базі даних транзакцій шукаються усі частини наукових наборів, а потім генеруються асоціативні правила на основі тих з них, які задовольняють заданому рівню підтримки і достовірності.

При цьому для скорочення простору пошуку асоціативних правил використовується властивість апріорності. Воно затверджує, що якщо науковий набір Z не є частим, то додавання будь – якого нового предмету А до набору Z не робить його таким. Іншими словами, якщо набір Z не є частим, то і Z + A – теж.
2.2 Властивість анти–монотонності
Виявлення наборів елементів, що часто зустрічаються, – операція, що вимагає багато обчислювальних ресурсів і, відповідно, часу. Примітивний підхід до рішення даної задачі – простий перебір всіх можливих наборів елементів. Це потребує O(2^|I|) операцій, де |I| – кількість елементів. Apriori використовує одну з властивостей підтримки, що свідчить: підтримка будь-якого набору елементів не може перевищувати мінімальної підтримки будь-якої з його підмножин. Наприклад, підтримка 3–елементного набору {Хліб, Масло, Молоко} буде завжди менше або рівно підтримці 2–елементних наборів {Хліб, Масло},                   {Хліб, Молоко}{Масло, Молоко}. Річ у тому, що будь-яка транзакція, що містить {Хліб, Масло, Молоко}, також повинна містити {Хліб, Масло},               {Хліб, Молоко}, {Масло, Молоко}, причому зворотне не вірно.

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

Властивості анти–монотонності можна дати і інше формулювання: із зростанням розміру набору елементів підтримка зменшується, або залишається такою ж. Зі всього, що було сказано раніше витікає, що будь–який k–елементний набір буде часто зустрічатися тоді і тільки тоді, коли всі його (k–1)–елементні підмножини будуть часто зустрічатись. Всі можливі набори елементів з I можна представити у вигляді грат, що починаються з порожньої множини, потім на 1 рівні 1–елементні набори, на 2–м – 2–елементні і т.д. На k рівні представлені k–елементні набори, пов'язані зі всіма своїми (k – 1) – елементними підмножинами.

Розглянемо малюнок, ілюструючи набір елементів I – {А, B, З, D}. Припустимо, що набір з елементів {А, B} має підтримку нижче заданого порогу і, відповідно, не є тим, що часто зустрічається. Тоді, згідно властивості анти–монотонності, всі його супермножини також не є тими, що часто зустрічаються і відкидаються. Вся ця гілка, починаючи з {А, B}, виділена фоном. Використовування цієї евристики дозволяє істотно скоротити простір пошуку.



Рисунок 2.1 – Набір елементів I
2.3 Алгоритм Apriori
Для того, щоб було можливе застосувати алгоритм, необхідно провести предобработку даних: по-перше, привести всі дані до бінарного вигляду; по-друге, змінити структуру даних[9]. Вигляд транзакційної бази даних представлен в таблиці 2.1 і таблиці 2.2.

Таблиця 2.1 – Звичайний вигляд

Номер транзакції	Назва елемента	Кількість
1001	А	2
1001	D	3
1001	E	1
1002	А	2
1002	F	1
1003	B	2
1003	A	2
1003	C	2
…	…	…

Таблиця 2.2 – Нормалізований вигляд

TID	A	B	C	D	E	F	G	H	I	K	…
1001	1	0	0	1	1	0	0	0	0	0	…
1002	1	0	0	0	0	1	0	0	0	0	…
1003	1	1	1	0	0	0	0	0	1	0	…

Кількість стовпців в таблиці рівно кількості елементів, присутніх в безлічі транзакцій D. Кожний запис відповідає транзакції, де у відповідному стовпці стоїть 1, якщо елемент присутній в транзакції, і 0 в осоружному випадку. Помітимо, що початковий вид таблиці може бути відмінним від приведеного в таблиці 2.1. Головне, щоб дані були перетворені до нормалізованого вигляду, інакше алгоритм не застосовний. Крім того, всі елементи повинні бути впорядкований в алфавітному порядку (якщо це числа, вони повинні бути впорядкований в числовому порядку).

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

Наступні кроки складатимуться з двох частин: генерації наборів елементів (їх називають кандидатами) і підрахунку підтримки, що потенційно часто зустрічаються, для кандидатів[4].

Описаний вище алгоритм можна записати у вигляді наступного псевдокоду:

F₁ = {1-елементні набори, що часто зустрічаються}

для (k=2; F_k-1 <> ; k++) {

C_k = Apriorigen (F_k-1) // генерація кандидатів

для всіх транзакцій t T {

C_t = subset(C_k, t)// видалення надмірних правил

для всіх кандидатів с C_t

c.count ++

}

F_k = {с C_k | c.count >= minsupport} // відбір кандидатів

}

Результат F_k

Опишемо функцію генерації кандидатів. На цей раз немає ніякої необхідності знов звертатися до бази даних. Для того, щоб отримати k–елементні набори, скористаємося (k–1)–елементними наборами, які були визначені на попередньому кроці і є тими, що часто зустрічаються.

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

Генерація кандидатів також складатиметься з двох кроків.

Крок 1. Об'єднання. Кожний кандидат C_к формуватиметься шляхом

розширення набору розміру (k–1), що часто зустрічається, додаванням елемента з іншого (k–1)–елементного набору.

Приведемо алгоритм цієї функції Apriorigen у вигляді невеликого SQL –подібного запиту.

insert into C_k

select p.item₁, p.item₂ ., p.item_k-1, q.item_k-1
From F_k-1 p, F_k-1 q
where p.item₁= q.item₁, p.item₂ = q.item₂ ., p.item_k-2 = q.item_k-2, p.item_k-1 < q.item_k-1

Крок 2. Видалення надмірних правил. На підставі властивості анти–монотонності, слід видалити всі набори с  C_k якщо хоча б одна з його (k–1) підмножин не є тим, що часто зустрічається.

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

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

Хеш–дерево з кандидатами–наборами побудовано, зараз, використовуючи хеш–дерево, легко підрахувати підтримку для кожного кандидата. Для цього потрібно "пропустити" кожну транзакцію через дерево і збільшити лічильники для тих кандидатів, чиї елементи також містяться і в транзакції, тобто 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, тоді ABCDE також задовольняє. Для того, щоб витягнути всі правила використовується рекурсивна процедура. Важливе зауваження: будь-яке правило, складене з набору, що часто зустрічається, повинне містити всі елементи набору. Наприклад, якщо набір складається з елементів {А, 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), які нормалізовані на відміну від схеми "зірка". Мають меншу кількість рядків, ніж таблиці фактів, і містять описову інформацію. Ці таблиці дозволяють користувачу швидко переходити від таблиці фактів до додаткової інформації. Первинні ключі в них складаються з єдиного атрибута (відповідають єдиному елементу вимірювання);

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

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