Національний університет “Львівська політехніка”

Шаховська Наталія Богданівна

УДК 51.001.57+004.652.4+004.827

Моделювання сховищ даних з невизначеністю на основі реляційної моделі

01.05.02 — математичне моделювання

та обчислювальні методи

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Львів-2007

Дисертацією є рукопис.

Робота виконана в Національному університеті “Львівська політехніка” Міністерства освіти і науки України.

Науковий керівник доктор технічних наук, доцент

Пасічник Володимир Володимирович,

Національний університет “Львівська політехніка”,

завідувач кафедри “Інформаційні системи

та мережі”.

Офіційні опоненти:

- доктор технічних наук, професор Дивак Микола Петрович, Тернопільський національний економічний університет, декан факультету комп'ютерних інформаційних технологій, завідувач кафедри комп’ютерних наук.

- доктор технічних наук, професор Соловйова Катерина Олександрівна, Харківський національний університет радіоелектроніки, завідувач кафедри соціальної інформатики.

Провідна установа – Державний науково-дослідний інститут інформаційної інфраструктури Міністерства транспорту та зв’язку України і НАН України, відділ інформаційних технологій і систем.

Захист відбудеться 13 квітня 2007 р. о 1600 на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка” (79013, м. Львів, вул. С.Бандери, 12).

З дисертацією можна ознайомитись у науково-технічній бібліотеці Національного університету “Львівська політехніка” (79013, м. Львів, вул. С.Бандери, 12).

Автореферат розісланий 6 березня 2007 р.

Вчений секретар спеціалізованої вченої ради,

доктор технічних наук, професор Бунь Р.А.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Проблема опрацювання невизначеності у реляційних базах даних, системах прийняття рішень тощо постала ще у 60-х роках минулого століття та поширювалася на різні об’єкти дослідження. Значний внесок у вирішення цієї проблеми зробили вчені: Codd E.F.,
Van Emden M.H., Bagai R., Netz A., Godo L., Kacprzyk J., Дейт К.Дж., Заде Л., Малюта Т.А., Поспелов Д.А., Абдулін А.А., Батиршин І.З., Тавпаш Ю.А.,
Аленфельд Г., Базаров М.Б. Частина методів стосувалася певних типів невизначеностей, інші роботи були спрямовані на побудову схем баз даних для введення невизначеності. Це призвело до певної розрізненості підходів до вирішення задач подання, опрацювання та усунення невизначеностей.

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

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

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

Зв’язок теми дисертації з цільовими програмами та планами перспективних наукових досліджень. Дисертаційна робота виконувалась в рамках пріоритетного наукового напрямку, затвердженого в числі актуальних проблем Міністерством освіти і науки України “Перспективні інформаційні технології, прилади комплексної автоматизації, системи зв’язку” за темами: ДБ/Ізоморф “Розроблення методів і засобів побудови інтелектуальних інформаційних систем на основі часових реляційних баз даних”, № держ. реєстр. 0104U002299 (автор розробила логічні моделі даних для моделювання різних типів невизначеностей та правил їх опрацювання у сховищах даних, що дозволило увести у відношення ті типи невизначеностей, які раніше не опрацьовувалися у сховищах даних та реляційних базах даних); “Демонстраційний проект просторового розвитку Миколаївського району Львівської області”, № держ. реєстр. 0104U002189, договір № 7 від 15 січня 2004 р. для Інституту регіональних досліджень НАН України (автор розробила алгоритми зменшення невизначеності, які побудовані на основі залежностей даних, що дало можливість не тільки підвищити повноту інформації у сховищах даних, але й досліджувати залежності між даними).

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

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

- формалізація та математичний опис задачі моделювання сховищ даних з невизначеністю на основі реляційної моделі;

- аналіз формальних моделей інформаційних ресурсів із врахуванням факту невизначеності;

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

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

- розроблення алгоритмів опрацювання та усунення невизначених даних;

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

Об’єктом дослідження є процеси функціонування сховищ даних за умов невизначеності.

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

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

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

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

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

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

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

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

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

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

Впровадження результатів роботи. Одержані в роботі результати використано при розробленні інформаційно-аналітичної системи підтримки аналізу та планування гармонійного розвитку території (“Демонстраційний проект просторового розвитку Миколаївського району Львівської області”), комплексній інформаційній системі планового відділу Міського споживчого товариства міста Львова, що підтверджено відповідними актами впровадження. Розроблення впроваджено також в навчальний процес в курсах “Експертні системи”, “Основи проектування систем штучного інтелекту”, “Математичні основи представлення даних та знань” у вигляді методичних вказівок до вивчення окремих розділів курсу та виконання лабораторних робіт.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися на наступних семінарах та конференціях: Міжнародній науково-практичній конференції “Сучасні технології в інформаційному суспільстві”, Київ, 2001; Першій міжнародній конференції “Проблеми індуктивного моделювання”, Львів, 2002; Дев’ятій всеукраїнській науковій конференції “Сучасні проблеми прикладної математики та інформатики”, Львів, 2002; Міжнародній конференції “Комп’ютерні системи та мережі ACSN-2005”, Львів, 2005; Міжнародній технічній конференції “Інтелектуальні системи прийняття рішень та інформаційні технології”, Чернівці, Буковинський університет, 2006; Науково-технічній конференції “Комп’ютерні науки та інформаційні технології CSIT-2006”, Львів, 2006; Науковій конференції для молодих вчених “Комп’ютерні науки та інженерія CSE”, Львів 2006; наукових семінарах Міжнародних комп’ютерних виставок “Комп’ютер і Офіс”, Львів (2001 – 2005); наукових семінарах міжнародних комп’ютерних виставок “Комп’ютер+Бізнес”, Львів (2001 – 2006);
на наукових семінарах кафедри ІСМ та щорічних (2001-2006) наукових конференціях викладачів та науковців Національного університету “Львівська політехніка”.

Особистий внесок здобувача. Усі наукові результати, подані у дисертації, одержані здобувачем особисто. У друкованих працях, опублікованих у співавторстві, особистий внесок здобувача такий: [1] – формальна модель сховища даних, модель кортежа з невизначеністю, алґебра опрацювання невизначеності у сховищах даних; [4] – розроблення алгоритмів породження класифікаційних правил та розроблення схем даних задачі аналізу результатів соціологічних опитувань; [8] – розроблення алгоритмів усунення невизначеності за допомогою класифікаційних правил; [9] – методи опрацювання нечіткостей та лінгвістичних змінних у задачах формування замовлень; [10] – формальна модель сховища даних, побудованого на основі реляційної моделі, схема сховища даних ГІС; [11] – використання багатозначної логіки та лінґвістичних змінних для оцінювання знань студента; [12] – введення узагальненого типу невизначеності, алгоритми усунення невизначеності на основі мережних зв’язків; [13] – кількісне порівняння та оцінка обсягів аудиторій сайтів на основі нечітких множин; [14] – формальна класифікація типів невизначеності, методи побудови класу для опрацювання невизначеностей у сховищах даних; [15] – введення нечітких квантифікаторів та розроблення методів для аналізу успішності;
[17] – опис проблем координації інтелектуальних інформаційних систем з врахуванням факту невизначеності; [19] – формальна модель сховища даних, використання лінгвістичних змінних для аналізу успішності студентів.

Публікації. Основні результати дисертаційного дослідження опубліковано у 26 наукових публікаціях, із них 10 – одноосібні, 15 праць опубліковано у фахових наукових виданнях та 6 – у матеріалах міжнародних конференцій.

Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, списку літературних джерел та додатків. Робота містить 149 сторінок основного тексту, загальний обсяг дисертації — 176 сторінок, 10 таблиць, 42 рисунки, 108 найменувань використаних літературних джерел.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність теми, сформульовано мету та основні задачі досліджень, подано короткий зміст роботи.

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

Автором введено формальну модель сховища даних, побудованого на основі реляційної моделі (СДРМ):

,

де DB – множина реляційних баз даних (РБД) (або множина відношень, їх схем та обмежень цілісності, які містять інформацію з вхідних баз даних),
rf – множина відношень фактів, RF – схема rf, rm – множина відношень метаданих, RM – схема rm, func – множина процедур прийняття рішень.

Нові дані (або рішення) – це результат застосування функцій сховища даних над відношенням фактів:

,

де – множина параметрів користувача (або вимог), які ставляться до рішення.

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

Виміром називаємо множину відношень бази даних
Vi Universum(DBi). Кожен вимір включає напрямки консолідації даних, що складаються із серії послідовних рівнів узагальнення (рівнів ієрархії).

Відношення між вимірами – це відношення, яке є зв’язком між певними вимірами та відношенням фактів: .

Формування значень відношення rf здійснюється на основі функції агрегування Agg: .

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

Схема СДРМ із зазначеними рівнями введення невизначеності подана на рис. 1.

Рис. 1. Схема сховища даних із рівнями введення невизначеності.

Невизначеність у відношеннях реляційної моделі може зустрічатися на різних рівнях:

- невизначеність на рівні відношення – невідомо, чи властивість притаманна сутності;

- невизначеність на рівні кортежів – відомо, що властивість притаманна сутності, але невідомо, чи вона притаманна певному об’єктові;

- невизначеність на рівні значень атрибутів – відомо, що властивість притаманна сутності і певному об’єкту, але невідомо, як вона на об’єкті проявляється.

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

Отже, внаслідок встановлення відношень між вимірами, перенесення невизначеності у СДРМ з РБД та застосування операцій аґреґування, гіперкуб (багаторівневий набір даних) у переважній більшості випадків є сильно розрідженим, тому проблема опрацювання невизначеності є важливішою, ніж у РБД. Крім того, як вже зазначалося, СДРМ орієнтоване на аналіз даних, який не може бути ефективним за наявності невизначеностей. Тому, на відміну від РБД, робота з невизначеністю у сховищах даних складається з трьох аспектів:

- подання – фізичне зазначення факту невизначеності у відношеннях сховища даних;

- опрацювання – забезпечення правильності результатів запитів до сховища даних із врахуванням наявності невизначеності;

- усунення – заміна невизначених значень відомими або даними із більшим ступенем довіри для ефективнішого аналізу даних та видобування нових знань.

Далі у розділі наведено причини появи невизначеностей у СДРМ та типи невизначеностей (рис. 2). Ці типи невизначеностей можуть накладатись один на одного або бути джерелом появи один одного. Враховуючи багатовимірність подання даних, виникнення невизначеності слід розглядати окремо для кожного типу відношень СДРМ. Так, якщо невизначеність виникла у відношеннях вимірів, то вона буде поширена на всі об’єкти у відношенні фактів rf, які містять зовнішній ключ вказаного виміру. Якщо невизначеність виникає у відношенні фактів та стосується вимірів, то виникає задача визначення приналежності виміру до вказаного об'єкта.

Рис. 2 Типи невизначеності у сховищі даних та рівні їх введення.

Для опису невизначених даних використовують: теорію ймовірностей, нечітку логіку (нечіткі множини, лінґвістичні змінні, інтервальні оцінки, нечіткі числа, емпіричні оцінки), k-значну логіку.

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

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

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

Схемою відношення із невизначеністю називаємо скінченну множину імен атрибутів
{А1, А2, ..., Аn}, значення яких є чіткими; множину імен атрибутів {A_unk1, A_unk2, … A_unkp} з нечіткими або недермінованими значеннями; множину імен атрибутів {Unk1, Unk2, …, Unkm}, доменами яких є числові дані, що подають ймовірність, значення функції приналежності нечітких множин, ступінь істинності багатозначної логіки, відсоткові відношення, коефіцієнти, різноманітні шкали або лінґвістичні оцінки. Невизначеними вважаються значення атрибутів множини A_unk, а рівень довіри до них зберігається у значеннях атрибутів множини Unk.

Для відображення зв’язків між атрибутами множин A_unk та Unk використано бінарне відношення Meta, значення якого визначаються як:

Meta=|metaij|, ,

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

Кортежем із невизначеністю t_unk називаємо кортеж, підмножина значень атрибутів якого містить неповні, нечіткі чи недетерміновані дані. Крайній випадок незнання про об’єкт відображається у відношенні як існування значення первинного ключа у кортежі з невизначеністю.

Отже, кортеж із невизначеністю t_unk – це множина значень характеристик об’єкта сутності, описана трійкою

t_unk = <A, A_unk, Unk>,

де А – підмножина значень атрибутів із чіткими значеннями, A_unk – підмножина значень атрибутів із нечіткими та недетермінованими значеннями, Unk – підмножина значень атрибутів із ступенями істинності значень атрибутів A_unk і meta(A_unk,Unk)=1.

Тоді відношенням із невизначеністю називаємо відношення із схемою та множиною кортежів t_unk.

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

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

Розглянемо моделювання різних типів невизначеностей у відношенні з невизначеністю у СДРМ.

1. Значення невідоме (відсутнє) – значення атрибута з A_unk традиційно позначається як , зустрічається у відношеннях фактів та вимірів.

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

3. Нечіткість, неточність, недетермінованість – множини атрибутів A_unk та Unk містять більше ніж по одному елементу, зв’язок між їх елементами відображений в Meta. Зустрічається у відношеннях фактів та вимірів.

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

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

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

Нехай r – відношення зі схемою R, – відношення зі схемою . Доповнення до відношення працює коректно у разі присвоєння усім значенням атрибута Unk найнижчого ступеня довіри .

Оператор вибірки передбачає аналіз нечіткого значення за множиною значень атрибутів Unk

,

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

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

Здійснюючи проекцію відношення з кортежами з невизначеністю слід відслідковувати зв’язок підмножини атрибутів Unk із підмножиною атрибутів A_unk. Тому розширюємо оператор проекції:

де IIF(умова; дія1; дія2) – операція вибору. Розширений оператор проекції зберігає властивості традиційного оператора проекції (якщо , то ).

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

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

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

,

де r – традиційне відношення, – відношення з невизначеністю (з множиною атрибутів Unk), R – множина атрибутів відношення r, S – множина атрибутів відношення , не включаючи підмножини атрибутів Unk (), В – множина тих атрибутів з S, яких нема у відношенні r (, ), min – значення, яке означає найнижчий ступінь довіри, – операція, яка присвоює min усім значенням Unk для нез’єднувальних кортежів відношення , – ліве з’єднання (включаються усі кортежі відношення r і лише ті кортежі відношення , у яких значення по з’єднувальних атрибутах збігаються). Спочатку виконується операція лівого з’єднання для відношень із схемами і R. Потім над отриманим з попередньої операції відношенням здійснюється операція проекції, за якою утвореним у результаті з’єднання порожнім значенням підмножини атрибутів Unk присвоюється значення min.

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

,

де – множина відношень зі схемою (які можуть бути об’єднані у єдине універсальне відношення); A_unk – множина цільових атрибутів, ; lingvistic – множина нечітких змінних, з якими порівнюємо значення цільових атрибутів у ; – множина операторів реляційної алгебри над . Результатом виконання оператора є множина відношень , яку будують на основі застосування до операторів з по атрибутах з множини A_unk з урахуванням значення нечіткої змінної з множини lingvistic (або множини нечітких змінних) та додаванням до отриманого відношення атрибута Unk (), який характеризує ступінь відповідності значень цільових атрибутів у вихідних кортежах до значення змінних з lingvistic.

Наведемо приклад -оператора – оператор лінґвістичної вибірки:

,

де r – традиційне реляційне відношення зі схемою R; А_unk – атрибут (множина цільових атрибутів) у R, по якому виконується вибірка; UNK – відношення, яке містить значення лінґвістичних змінних, unk(lingvistic_variable, infimum, supremum) з атрибутами, які позначають назву лінґвістичної змінної і її нижнє та верхнє значення; – вираз, результатом якого є порівняння за обраним правилом значення а атрибута А_unk зі значеннями [u1, u2] лінґвістичної змінної U; В – послідовність атрибутів, значення яких обов’язково повинні відповідати параметрам вибірки (_unk); – оператор лінґвістичної вибірки; unk – ступінь істинності значень критичних атрибутів відношення, який визначений у результаті застосування .

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

Далі у другому розділі автором проаналізовано особливості опрацювання інтервальних величин у СДРМ. Оскільки такі властивості інтервальної математики як A-A0, A/A1 тощо призводять до збільшення інтервалу, то потрібно ввести спосіб компенсації похибки обчислень. Для цього автором введено операцію збереження історії, яка враховує такі властивості інтервалів, як монотонність включення та субдистрибутивність:

,

де – математичні операції (додавання, віднімання, множення, ділення та порівняння); nm – назва відношення; id – код кортежу.

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

.

Далі розв’язано задачу усунення невизначеності. З цією метою введено поняття класифікаційного правила.

Класифікаційним правилом називаємо залежність між підмножинами атрибутів X () та Y (), яка зустрічається у тестовому наборі відношення із ступенем довіри s, при якій .

Міткою класу називаємо лінґвістичну змінну або типову характеристику об’єктів із значеннями підмножини атрибутів Y. Вона подає об’єкти зі спільними (подібними зі ступенем s) значеннями підмножини атрибутів Х. Домени атрибутів, що належать до підмножини Y, , обов’язково повинні містити скінченну та наперед відому множину значень.

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

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

Далі з метою усунення невизначеності розроблені методи аналізу мережних зв’язків між кортежами відношення фактів.

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

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

Оператором визначення предка Up називаємо оператор виду

,

де – універсальне відношення, в якому зберігається інформація про зв’язки між об’єктами; Х – первинний ключ відношення; Y – зовнішній ключ відношення r (вказує на підпорядкування записів); – значення первинного ключа запису, для якого здійснюється пошук предка; – значення зовнішнього ключа, на який здійснює посилання нащадок (код предка).

Оператором визначення нащадка Down назвемо оператор виду

.

Тоді оператор усунення невизначеності за даними предка Heir:

.

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

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

У СДРМ відношення meta реалізуємо у вигляді відношення метаданих attr із схемою Attr, у якому зберігатиметься залежність між чіткими та нечіткими атрибутами відношень сховища даних. Відношення attr – це відношення, що містить метадані (тобто, описує дані). Інформація у ньому вважається апріорі чіткою. Схема Attr подана у таблиці 1.

Таблиця 1.

Схема Attr

Id

Rel_name

Attr_name

Unk_name

Prior_id | Первинний ключ

Назва відношення

Назва атрибута

Назва атрибута з невизначеністю

Зовнішній ключ відношення Attr

Автором розроблено алгоритм ґенерації правил на основі аналізу кортежів відношення (рис. 3) та на основі наявних правил (рис. 4).

Рис. 3. Логічна схема алгоритму породження класифікаційних правил на основі аналізу кортежів відношення |

Рис. 4. Логічна схема алгоритму ґенерації правил на основі наявних

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

Нехай у відношенні підтримується класифікаційне правило s(X1, ..., Xn>Y). Через символ позначаємо визначене значення, – відсутнє значення; tі – кортеж відношення (послідовність кортежів значення не має).

1.

і {t1 (X1) , ..., t1 (Xn) = t2 (X1) , ..., t2 (Xn) } і { t1 (Y) } і {t2 (Y) = },

то замінюємо на t1 (Y) і .

2.

і {в t2 m з n значень атрибутів – , n - m значень атрибутів – , }

і {} – ступінь довіри до правила більший ніж міра необхідності кортежа t2 і { t1(Xm) = t2(Xm) } і { t1 (Y) } і { t2 (Y) = }, то замінюємо у r на t1 (Y) і .

3.

і {в tj mj з n значень атрибутів – , } і { ti(Xm) = t2(Xm) } і { tj(Xm) = t2(Xm) } і {} і {} і { ti (Y) } і { tj (Y) }

і { t2 (Y) = }, то замінюємо на tj (Y) і .

Для зменшення невизначеності шляхом аналізу зв’язків між кортежами відношень спроектовано відповідну структуру.

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

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

1. Виділення підмножини атрибутів Х та Y, а також атрибуту А, який містить значення нечіткої змінної як характеристики об’єкта.

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

3. Групування кортежів отриманого відношення за значеннями атрибутів Х.

4. Групування кортежів усередині групи X=x за значеннями атрибутів Y.

5. Виконання всередині групи за значенням атрибута Y=y логічної операції “і” для значень атрибута А.

6. Виконання всередині групи за значенням атрибута Х логічної операції “або” для значень атрибута А.

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

8. Заміна (занесення) значення атрибута Y для всіх кортежів усередині групи по Х, для яких значення атрибута А є найвищим.

9. Знищення кортежів, що повторюються.

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

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

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

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

У розділі досліджено продуктивність програмних компонент, що реалізують алгоритми усунення невизначеності на основі аналізу мережних зв’язків (рис. 5). Для цього з тестового набору даних із визначеними значеннями було взято частину як невизначених та проаналізовано на різних рівнях мережної структури.

а) б)

Рис. 5. Результат усунення невизначеності на основі аналізу ієрархії відношення фактів:а) детальні дані; б) відсоток довизначених даних

Також здійснено порівняння якості усунення невизначеності методами, запропонованими у роботі, та нечіткими функціональними залежностями (рис. 6).

а) б)

Рис. 6. Діаграма результатів усунення невизначеності: а) порівняння з існуючими методами; б) кількість довизначених значень

Для аналізу невизначеності, що задається користувачем, використано лінґвістичні змінні. Аналіз проводився на тестових даних системи “Успішність”, а саме досліджувалась ефективність застосування модульної системи для навчання студентів по базових дисциплінах. Засоби та результати аналізу подані на рис. 7 та рис. 8.

Рис. 7. Форма для задання нечіткої інформації Рис. 8. Результат аналізу

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

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

ВИСНОВКИ

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

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

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

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

4. Запропоновано та обґрунтовано використання класифікаційних правил для відображення закономірностей даних та усунення невизначеностей. Запропоновано методи ґенерації таких правил.

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

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

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

СПИСОК ОСНОВНИХ ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Пасічник В.В., Шаховська Н.Б. Моделювання невизначеностей у сховищах даних, побудованих на основі реляційної моделі // Вісник Національного університету “Львівська політехніка”: Інформаційні системи та мережі. – № 549. – С.128-138.

2. Шаховська Н.Б. Застосування багатозначної логіки для аналізу баз даних // Вісник Національного університету “Львівська політехніка”: Комп’ютерна інженерія та інформаційні технології. – 2002. – №450. – С.180-184.

3. Шаховська Н.Б. Моделювання нечіткостей у системі планування діяльності підприємства // Вісник Національного університету “Львівська політехніка”: Інформаційні системи та мережі. – № 464. – С.327-340.

4. Шаховська Н.Б, Кравець Р.Б. Застосування багатозначної логіки для інтелектуального аналізу даних // Вісник Національного університету “Львівська політехніка”: Комп’ютерна інженерія та інформаційні технології. –2002. – №468. – С. 58-65.

5. Шаховська Н.Б. Моделювання невизначеностей та інтелектуальний аналіз баз даних засобами багатозначної логіки // Вісник національного університету ім. І.Франка. – Львів: Нац. ун-т ім. І.Франка, 2003. – № 6. – С.218-227.

6. Шаховська Н.Б. Методи усунення невизначеностей у базах знань, побудованих на основі реляційного підходу // Вісник Національного університету “Львівська політехніка”: Інформаційні системи та мережі. –2003. – № 484. – С.315-325.

7. Шаховська Н.Б. Аналіз мережних зв’язків між кортежами у відношеннях сховища даних, побудованого на основі реляційної моделі, як метод зменшення невизначеності // Автоматизированые системы управления и приборы автоматики. – Харків: Харк. нац. ун-т радіоелектроніки, 2004. – № 127. – С.74-80.

8. Шаховська Н.Б., Кісь Я.П. Використання класифікаційних правил для зменшення невизначеності у сховищах даних, побудованих на основі реляційної моделі // Вісник Національного університету “Львівська політехніка”: Комп’ютерні науки та інформаційні технології. –2005. – №546. – С.155-162.

9. Тарасов Д.О., Шаховська Н.Б. Опрацювання нечіткостей на різних етапах формування замовлення // Вісник Національного університету “Львівська політехніка”: Інформаційні системи та мережі. –2001. –№438. – С.145-151.

10. Кісь Я.П., Шаховська Н.Б., Вальчук О.Б. Інтелектуальні геоінформаційні системи. Міжнародний досвід та шляхи розвитку в Україні // Автоматизированные системы управления и приборы автоматики. – Харків: Нац. ун-т радіоелектроніки, 2006. – № 134. – С.77-82.

11. Шаховська Н.Б., Голощук Р.О. Моделювання та алгоритмізація процесів дистанційного навчання // Вісник Національного університету “Львівська політехніка”: Комп’ютерні науки та інформаційні технології. –2004. – № 521. – С.106-112.

12. Шаховська Н.Б., Сєров Ю.О. Подання невизначеностей у геоінформаційних системах // Вісник Національного університету “Львівська політехніка”: Інформаційні системи та мережі. – 2004. – № 519. – С.317-327.

13. Пелещишин А.М., Шаховська Н.Б. Використання апарату нечітких множин для опису аудиторії Веб- сайту // Штучний інтелект. – Донецьк: Ін-т. проблем штучного інтелекту, 2005. – № 3. – С.521-526.

14. Пелещишин А.М., Шаховська Н.Б. Застосування алгоритмів класифікації для зменшення невизначеності // Вісник Національного університету “Львівська політехніка”: Комп’ютерні науки та інформаційні технології.– 2005.– №543. – С.174-179.

15. Жежнич П.І., Шаховська Н.Б. Методи подання та опрацювання невизначеностей для систем навчання // Вісник Національного університету “Львівська політехніка”: Комп’ютерні науки та інформаційні технології. –2006.– № 565. – С.275-282.

16. Шаховська Н.Б. Аналіз баз даних засобами багатозначної логіки /І Міжнар. наук.-практ. конф. “Індуктивне моделювання”. – Львів, 2002. – Т.2 – С.154-157.

17. Литвин В.В., Шаховська Н.Б. Проблема координації інтелектуальних інформаційних систем / ІІІ Міжнар. наук.-практ. конф. “Системний аналіз та інформаційні технології”. – Київ, 2001. – С.77-81.

18. Шаховська Н.Б. Деякі аспекти застосування багатозначної логіки у реляційних базах даних / IX Всеукр. наук. конф. “Сучасні проблеми прикладної математики та інформатики”. – Львів, 2002. – С.134-135.

19. Пелещишин А.М., Жежнич П.І., Шаховська Н.Б. Засоби моделювання невизначеностей у системі “Аналіз успішності” / І Міжнар. наук.-техн. конф. “Інтелектуальні системи прийняття рішень та інформаційні технології”. – Чернівці: Буковинський ун-т, 2006 – С.10-11.

20. Shakhovska N. The modelling uncertainty in datawarehouses, based on relational model / І Міжнар. конф. “Комп’ютерні науки та інформаційні технології CSIT-2006”. – Львів, 2006. – С.69-73.

21. Шаховська Н.Б. Методи усунення невизначеності у сховищах даних / І Міжнар. конф. “Комп’ютерні науки та інженерія CSE-2006”. – Львів, 2006. – С.40-44.

АНОТАЦІЇ

Шаховська Н.Б. Моделювання сховищ даних з невизначеностю на основі реляційної моделі. – Рукопис.

Дисертаційна робота на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 – “математичне моделювання та обчислювальні методи”. – Національний університет “Львівська політехніка”, Львів, 2007.

У дисертаційній роботі розв’язано науково-технічну задачу моделювання сховищ