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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Вступ

Актуальність теми. На сучасному етапі розвитку програмного та апаратного забезпечення комп'ютерних систем стало можливим накопичувати великі об'єми інформації. Це спричинило появу нової концепції збереження корпоративних даних, яку у 1992 році запропонував W. Inmon, а саме - сховища даних. Як зауважив N. Raden, “багато підприємств створили чудові сховища даних, ідеально розклавши по поличках гори інформації, яка не використовується і сама по собі не забезпечує ні швидкої, ні достатньо грамотної реакції на ринкові події”. У зв'язку з цим виникає необхідність створення новітніх методів та засобів інтелектуального опрацювання інформації, що зберігається в сховищах даних інформаційних систем, які б дозволяли людині поповнювати свої знання про предметну область. У свою чергу великої актуальності набуває подальший розвиток технологій побудови інтелектуальних систем підтримки прийняття рішень, які б поєднували у собі як наявні методи опрацювання інформації, так і ті, що розроблюються, і виконували б функцію інформаційного забезпечення процесів прийняття керівних рішень, використовуючи при цьому усі доступні дані та знання про предметну область.

Для багатьох інтелектуальних систем підтримки прийняття рішень важливою компонентою є система інтелектуального аналізу даних, функція якої полягає у пошукові закономірностей на великій зростаючій множині даних, що зберігаються в сховищі даних, та у допомозі людині при формуванні знань про предметну область на основі віднайдених закономірностей. Зазначимо, що на сьогодні для інтелектуального аналізу даних пропонується використовувати достатньо широкий спектр методів, великий вклад у розроблення та дослідження яких внесли вчені С.А. Айвазян, В.П. Гладун, М.Г. Загоруйко, А.Г. Івахненко, Г.С. Лбов, Б.Г. Міркін, R. Agrawal, R.J. Bayardo, W. Buntine, U.M. Fayyad, J. Han, D. Heckerman, H. Mannila, G. Piatetsky-Shapiro, J.R. Quinlan, R. Srikant, H. Toivonen та ін. Частина цих методів спеціально розроблялася для вирішення окремих підзадач інтелектуального аналізу даних (пошук асоціацій та послідовностей, побудова дерев рішень та індукція правил). У той же час інші були розроблені поза контекстом баз даних та інформаційних систем (баєсівські методи, нейронні мережі, методи міркування на основі аналогій, генетичні алгоритми, методи нечіткої логіки, методи прикладного статистичного аналізу тощо). Це призвело до певної розрізненості у пропонованих підходах.

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

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

Мета дисертаційної роботи визначає необхідність розв'язання таких задач:

формалізація постановки задачі інтелектуального аналізу даних, які зберігаються у реляційній базі даних (РБД);

побудова моделі системи інтелектуального аналізу даних як інформаційної системи (ІС), що дозволяє сформувати знання про предметну область (ПО) на основі даних, що зберігаються в РБД;

побудова математичної моделі багатовимірного подання даних в РБД, яка враховує характер їх опрацювання під час аналізу;

побудова алгоритмів інтелектуального аналізу даних в РБД, базованих на інформаційно-статистичному підході до формування значущих закономірностей;

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

1. Побудова моделі системи інтелектуального аналізу даних як загальної

При цьому автор виходив з таких передумов: по-перше, СІАД повинна працювати як окрема система, що виконує функцію інтелектуального аналізу даних і містить усі компоненти, необхідні для виконання цієї функції; по-друге, СІАД повинна розглядатися як підсистема ІСППР, яка виконує загальнішу функцію підтримки процесів прийняття рішень. З цією метою у першому розділі проведено аналіз інформаційних технологій, спрямованих на підтримку процесів прийняття рішень. До цих технологій належать: системи підтримки прийняття рішень (СППР), бази даних (БД) і сховища даних (СД), системи баз знань (БЗ) та моделі подання знань.

Головною функцією СППР є інформаційне забезпечення процесів підтримки прийняття рішень у конкретній ПО. З огляду на це СППР має виконувати такі завдання: накопичувати та зберігати первинні дані про усі об'єкти конкретної ПО та зв'язки між ними; надавати особі, що приймає рішення (ОПР), інформацію довідково-нормативного та звітного характеру; надавати ОПР аналітичну та статистичну інформацію на різних рівнях деталізації; накопичувати та зберігати експертні знання про ПО; здійснювати пошук закономірностей у накопичених даних про ПО; надавати ОПР інформацію, виведену на основі накопичених знань та даних.

Перераховані завдання є окремими підфункціями головної функції СППР, які доцільно реалізовувати як окремі підсистеми загальної СППР. Окрім того, СППР має містити ще дві компоненти, у яких зберігаються дані та знання про ПО і до яких звертаються підсистеми СППР. Побудова СППР з такою структурою стає можливою завдяки поєднанню перерахованих вище технологій. При цьому як компоненту для збереження даних СППР пропонується використовувати СД, а як компоненту для збереження знань - БЗ. У результаті отримуємо ІСППР на основі СД.

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

побудована модель має відображати закономірності, які виникають у ПО, причому значущість закономірностей повинна мати кількісні характеристики;

побудована модель повинна описувати закономірності у такому вигляді, щоб їх міг проінтерпретувати користувач системи;

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

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

Процес ІАД супроводжується етапами, зображеними на рис. 1.

Рис. 1. Етапи, що супроводжують інтелектуальний аналіз даних

Далі у розділі побудовано моделі ІСППР та СІАД. ІСППР задана, як трійка , де - схема СД, - схема БЗ, - набір операцій над множинами та . Схеми СД та БЗ конкретної ІСППР визначаються на етапі проектування цієї системи. Набір операцій визначає, які дії можна виконувати над даними та знаннями у системі, а, отже, якого типу ІС можна побудувати, використовуючи наявні у наборі операції. Набір містить операції таких типів: операції над даними вигляду , операції над знаннями вигляду , операції формування знань із даних та операції виведення нових даних .

Система інтелектуального аналізу даних є підсистемою ІСППР і задається, як відображення:

, (1)

де - структура ПО.

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

Структура СІАД, яка відповідає запропонованій у роботі математичній моделі (1), зображена на рис. 2.

Рис. 2. Структура системи інтелектуального аналізу даних

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

2. Математична постановка задачі ІАД

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

Структура ПО задається, як кортеж:

,

де - множина атрибутів, - множина доменів, - функція, яка кожному атрибуту з ставить у відповідність домен з , - структура класу об'єктів ПО, - структура співвідношення між об'єктами ПО, - структура класу подій ПО, - структура співвідношення між подіями ПО.

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

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

Розрізнятимемо дескриптивні (описові) та прогностичні (передбачувальні) знання для елементів ПО. Дескриптивні знання подаватимемо у вигляді узагальнень даних, а прогностичні - у вигляді правил.

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

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

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

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

Задача ІАД сформульована автором так. Нехай маємо сховище даних зі схемою . Атрибути описують номінальні величини і набувають значень на відповідних дискретних доменах , на яких не задано відношення порядку. На основі даних, які зберігаються в інформаційних відношеннях СД , потрібно сформувати БЗ , яка складається з множини узагальнень вигляду , правил вигляду , і має схему .

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

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

Далі у розділі досліджені властивості запропонованих функцій значущості.

Нехай та - узагальнення, отримані на основі інформаційного відношення , причому на підмножині відношення, на якій виконується , виконується також . Тоді має місце нерівність:

.

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

.

У роботі показано, що мають місце такі співвідношення:

,

.

Окрім того, для залежностей вигляду та , таких, що , мають місце нерівності:

,

.

На основі отриманих співвідношень у роботі сформульовані такі твердження.

Твердження 1. Якщо узагальнення , яке описує деяку підмножину відношення , не є значущим, то узагальнення , яке описує підмножину відношення , також не є значущим.

Твердження 2. Якщо значущість залежності вигляду менша за порогове значення значущості правил, то усі правила вигляду , отримані на основі відношення , не є значущими.

Твердження 3. Якщо значущість залежності вигляду менша за порогове значення значущості правил, то значущість залежності вигляду , таких, що , також менша за порогове значення значущості правил.

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

Алгоритм формування множини значущих узагальнень.

Крок 1. Сформувати початкову множину одноатрибутних узагальнень.

Крок 2. Дослідити значущість сформованих узагальнень та залишити у множині тільки значущі узагальнення.

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

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

Алгоритм формування базисної множини значущих узагальнень.

Крок 1. Сформувати початкову множину найдовших узагальнень.

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

Крок 3. Якщо множина отриманих незначущих узагальнень не порожня, то сформувати нову множину узагальнень, які коротші від отриманих на 1, і перейти до кроку 2; інакше - закінчити алгоритм.

На рис. 3 зображена загальна схема алгоритму формування усіх значущих залежностей та правил.

Рис. 3. Загальна схема алгоритму формування залежностей та правил

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

Рис. 4. Загальна схема алгоритму формування базисної множини залежностей та правил

Кількість інформації про залежність вигляду визначається через ентропію Шенона за формулою:

,

яка, у свою чергу, обчислюється за формулою:

,

де .