автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Разработка методов представления и обработки некорректных данных и знаний в интеллектуальных информационных системах

Академия наук Украпга Гнститут кибернетики 1мен1 В. М. Глушкова

РГб од

'ЦОЬ

На правах рукопису

БОРОВА Ел1*на МиколаУвна

РОЗРОБКА МЕТОД1В ПРЕДСТАВЛЕНИЯ ТА ОБРОБКИ НЕКОРЕКТНИХ ДАНИХ ТА ЗНАНЬ В ЖТЕЛЕКТУАЛЬНИХ 1НФОРМАЦ1ЙНИХ СИСТЕМАХ

05.13.11 — математнчне та програмне забезпечення обчислю-вальних машин, комплексов, систем та мереж

Автореферат дисертацп на здобуття наукового ступеня кандидата ф|'зико-математичних наук

КиТв 1994

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

Робота виконана в 1нституп програмних систем АН Укра!-' ни.

Науковий кер1выик: доктор фшжо-математичних наук,

член-кореспондент АН Украши, професор АНДОН П. I.

Офщшш опоненти: доктор ф1зико-математичних наук,

професор КАП1ТОНОВА Ю, В.

кандидат ф13ико-математичних наук, доцент ШКИТЧЕНКО М. С.

Провщна оргашзашя: 1нститут прикладно! ¡нформатики.

Захист вадбудеться «/5? » —'^^— 199^ р. о —год. на зааданш спещалЬовано! вченоГ ради Д 016.45.01 при 1нститут1 к1бернетики ¡меш В. М. Глушкова АН УкраТни за адресою:

252207, Ки1и 207, проспект Акаде\пка Глушкова, 40.

3 дисертащею можна ознаиомнтися в науково-техшчному арх1в! шституту.

Автореферат роз1сланий -» 199^

Р

Учений секретар спец!ал130ван01 вчено! ради

СИНЯВСЬКИЙ В. Ф.

- 1 -

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

Дисертац!я присвячена досладженнп та розрсбц! питань представления та обробки некоректно! анформаци в !нтелектуальних 1нформац!йних системах CIC).

Актуальность роботи. На цей час у всьому cbítí е перспективними досл1дяення, к!нцевою метов яких е я!двищеиня хнтелектуальност! 1С шляхсм створення ново! !нформацЗй;ю1 технологи, яка використовуе ochobhí особливост! методов штучного хнтелекту, серед яких, перш за все, мсхливхсть описувати i обробляти íh$opKauiD з разними аномалоями, такими, як неповкота, суперечн1сть, ненад1йн1сть i т.i.

Традицойн! 1С, основними сферами застосування яких е науково-техн1чн1 та íhíuó добре формал1зован! предмета! облает!, базуються на формальному anapaTi дзозначно! лог i к v. та вкмагають несуперечност!, повкоти та 4ítkcctí bcíx закладених у 1С даних.

Однак за останна десяткл!ття к1льк!сть традшпйних застосувань 1С зкачно зменшилася, тол i як больийсть застосувань 1С стосусться зараз слабко формалгзованих предметных областей, Зростае складн1сть !нформацайних систем, а такох вамоги до них: системи noBHHHi адекватно в!добрахувати складно формал!зован! аспекта предметно! облает!. Одним оз шл.<шв ^телектуалазацП 1нформац!йних систем е розширення могливостей традицхйнкх 1С засобами формалозацП та обробки р1зких еид!в некоректно! iH$bpMauii. Сучасн! 1С повинн! пседнувати в соб! засоби легкого маншулввання великими масивами даних з можлив!стс релевантного опису складних предметних областей. У цьоыу напрямку в!дбуваеться процес зблихення систем керування базами даних та систем штучного !нтелекту.

Ие один аспект онтелектуалозаио! 1С пов'яэашгй э моделюванням cnocodiB м1ркувань, за допомогою яких система мохе отримувати hcbí знания, виходячи з наявних. ТрадиЩйно у 1С використовувались дедуктивно моркування, за якими мохна зробити окрем! висновки Í3 уже установлених закон!в або правил. Однак недедуктивно методи м1ркузань, так! як, напркклад, андуктквиий вивод, за яким по сум: окремих випадк!в Í факт!в намагасться вивести деякий загалъний закон,• безперечно, е бхлыа, хнтелектуальними, тому ш,о формулюзання г!потез або узагальнення емпоричних фактав як р!эновид онтелектуально! д1яльност1 по праву вважаеться одн!св з головних властивостей людського розуму. Тому наявн!сть у 1С uexaHiOMiB моделювання недедуктивннх- м1ркувань

природно розглядати як один э показншав !нтелектуальност1 1С. У зв'язку э цим особливо перспективним с зближення метод1в 1ндухтивного виводу з методами мхркувань в умовах неповноти та 1 анаоийкост!.

Дмсертагйя присвячена ■ досл!дхенню - проблема гпдвиаення !нтелек1уальност! 1С шляхом створення ыожливостей представления та обробки в них некоректно! !нфор:'ац!1.

Мотор дисертацШю! роботи е розробка теоретичних та прикладних питань опису та обробки неловко! та диз'енктивно! !нформац!! в .¡.нфор.мацдйних системах.

Виходячи з цього, досл1дгення проводились у .таких напрямках:

- вивчення та оцдаа !скуочих роб1т.та п1дход1в;

- 1нтеграц1я р1зко!^н1тних п1дход!в, побудова едино! системи понять. внзначекь, позначень;

- розробка релгпййних алгебр з неповною та диз' енктивнос !нформац!ев, вивчення !х властивостей.

Методом досл1джень с теоретико-модельний п1дх1д, який дозволяе сформувати нов! ыодел! даних, цо е узагальненням реляц!Яко! «одел!. У робот! використовуються елеыенти теорП. реляидйних баз даних, апарат алгебри та математично1 лог1ки.

Наукова новизна робота полягае в тому, цо запропоновано -ласиф!кац!ю аномал^ !нформацП в !нфориац1йних системах; введено розширен! реляц!йк1 модели як1 охоплгзвть неповну та диз'ьнктивну 1Нформац!с. На основ! запропонованого в!дношення приблизно! рхвност! введено узагальнен! функц!ональн! залежност! у в1дкошеннях з диз'енктивнос та неповною ¿нфоркалдес; дослужено властивост! вхдношення приблизно! р1вност1 та властивост! фунхц!ональних залехностей, розроблено алгоритма використання узагальнених залехностей для зменшення невизначеност! даних. Розроблено розиирен! реляц1йн1 оператори, доведена кореитсть цих оператор1в, досл!дхен1 властивост! в!дпов!дних алгебр. Запропоновано метод обробки неповних даних у системах !ндуктивного виводу, який називаеться ЖЗВ-ыетодом, а такох метод обробки ненад1Йних даних у таких системах.

Практична ц!нн!сть роботи полягае у тому, ш.о розроблен! нов! модел! даних мо.туть бути основою для створення 1Нформац 1йних систем, як! б дозволяли описувати та обробляти деяк! види некоректно! !нформацП.

Розроблен1 методи ! алгоритми можуть використовуватися: при розробц! систем керування базами даних, як1 дають

можливхсть опису та обробки неповно! та дяз'снктивао! 1нфориац11; при розробцд прикладних 1нформаЩйних систем; в учбовому npoueci при п1дготовЩ спецдал1ст!в " з прикладно! математики, штучного 1ктелекту, автоматичних систем керування.

Апробац1я результат1в роботи. Окреьи реэультати роботи п!д час II виконання допов1дались на сем:нар! "Новые информационные технологии и инструментально-технологические средства поддержки принятия решений" (сел.Кацдвел!, 1-5 листопада 1992 р.), на II Шжнародному науково-техничному ceuiKapi "Теоретические и прикладные проблемы моделирования предметных областей в системах баз данных я знаний" (Туапсе, 20-2S вересня 1393 р.), на конференцП "Инженерия и инструментальные средства программирования. " СКИ1В, 1-4 червня 1993 р.), на М1хнародк1й кокференцП "East-Vest Conference on Artificial Intelligence: From Theory to Practice", CMoscow, Sept. 7-9, 1993), на наукових ' семинарах та хонференц!ях у Гнститут! кхбернетики, Ки!вському университет!, 1нститут1 программах систем.

Робота виконана в рамках .науково-досл!дних po6iT по держбюдхетн1й та госпдогоз1рн1Я тематиид, по проводились протягом 1992-1994 poKiB у 1нституп програмних систем АН Укра1ни.

Публ1кацП. По тем1 диcepтaцiI опубликовано 9 друкованих роб!т.

До захисту пропонуються:

1) класиф!кац1я аномал1й даних в 1нформац1йних системах;

2) розширена реляцШна модель з трьома нульовими значениями та BiflnoBiflHa алгебра для в1дношень з такими нульовими значеннями;

3) розширена реляц^йна модель для в1дношень з , диз'внктивнов iH$opMauieD та в!дпов1дна розширена реляц!йна алгебра;

4) методи 1ндуктивного виводу, модиф!кован1 до умов неповноти та ненад!йност1.

Структура роботи. Дисертац1йна робота складаеться i3 вступу, чотирьох роздШв, висновклв та списку л1тератури. Робота викладена на 136 стор1нках тексту. Б1бл1ограф1Я - 69 найменувань.

Зм1ст роботи

У BCTyni обгрунтовуеться важлив^ть та актуальн!сть теми дисертацП, викладен1 мета та методика досл1джень. Сформульован1 основн1 положения та результати, досягнут1 п1д час виконання роботи, 1х наукова новизна. Стисло викладаеться 3MiCT розд1л1в дисертац!йно! роботи.

ПерцкЗ розд!л м1стить анал!а прадь, присвячених методам робота з некоректкоп 1нформац1ею. Приводиться пор1вняльний анал1э деяких п!дход1в до опису та обробки деяких вид!в некоректно! 1нформацП.

1нфориац1йна одиниця I визначаеться четв1рксс:

I = <о, , , d , Тут Oj - об'ект, oi € 0, де 0 - мнохина об'ект!в, тобто множила первикни" елемект!в, як1 вид1ленх у предметна облает!; а - атрий}., а, е А, де А - множина властивостей (атрибутав) цього класу od'eKTiB; d. ^ - значения атрибута а^ об'екта о, , d4J е Dorrr, де Doirtj - множина допустимих значень атрибута а^ (домен атрибута); w4J - впевненхеть, w4J е W, де V - множина значень визначеного типу, що характеризуем влевнен1сть у тому, до атрибут а мае значения ^.

Сукушисть ¿нформацЫних одиниць утворюе 1нформаидйну базу, яка е необх!дноо частиков кожно! 1нформаиийно1 системи.

Прспонуеться така класиф1кацдя можливих аномалin 1нформац11 ь 1кформац1йних системах:

j—--HEKOPEKTHICTb -^

НЕПЕВНЛСТЬ |-КЕВИЗНДЧЕН1СТЬ -1

НЕЧ1ТК1СТЬ СУПЕРЕЧН1СТЬ НЕПОВНОТА

Поняття "невизначен1сть" е характеристикою значения атрибута в 1нформац1йК1й одинкпд, а покдття "непевн1сть" - в1дпов!дност1

II д1йснсст1 Сскладова "впевнен1сть" в iH$opuai;iflHiit одиници. Кепевн1сть i невизначен1сть кожуть розглядатися як два взаемно доповншч! характеристики одше! 1нформац1йно1 одиниц1.

¡нформацдя е певнос, яхцо для задано! 1нформац1йно1 одиниц! I мнохкна W е двоелементно!) mkoxhhod, наприклад: (1,0>, {True, False) i т. i., 1накше 1Нформац1я е непевно£>.

Для обробки непевних даних створенi нехласичн! лохчки з многозначними та бхлыи складними значениями лстинност!. На практик кепевшеть представлявть 1моь1рн1ств, гпдпорядкованою законам Байеса за TeopieD 1Мов1рностей. ■ 1снусть такох методи 1нтервального оц!нввання по Демпстеру - Шаферу, метод нечд.тк'лх од1нок, запропонованний Л. Заде, метод супроводжувальних запис!в.

1иформац1Я е нечеткою, якш,о значения dtJ атрибута а.^ у 1нформац1йн1й одиниц! не е конкретним числовим або символьним значениям, але мае деяку б^льш складну структуру, наприклад, неч1тке значения, нечетка множина тощо. В основ! методis обробки неч^костей лежать теор1я неч!тких множин, теор!я суб'ективних

!мов!рностей, теор1я неч!тких та приблкзних М1ркувань, лог!ка з Л1нгв1стичниш( значениями хстинност!, нечетка логх.ка.

1нформац1я в систем! е неповною, якцо для деяхого об'екта Oj 6 0 для деякого атрибута aj немояливо стверяжувати. що значения цього атрибута дор!внюе чи не дор!внсе diJf хоча !нформац1я е певною. 1снують TaKi вида неповно! !нфсрмацП:

1. !Ндомо, що для деякого об'екта о( е 0 для деякого атрибута а. значения цього атрибута е елементом деяко! ск!нченно! множини, тобто dtJ е <dt;...,dn>, але не BiflOMO, чому саме ÄopiBHüe d4J. Такий вид неповноти називаеться диз'юнктивнсю !нформац!ею i представляеться або рсэаепленням початково! задано! модел! на ABi та бьчьше моделей, кожна з яких идентична задан!й, за винятком того, то вони м!стять у coöi по одному диз'снкту э тих, на як! розаеплвстъся наявка диз'юнктивна !нформац!л (при теоретико-модельному пгдходП, або шляхом введения диз'юнктивних BipHo побудованих формул в reopio 3i зм!кою в!дпов!дних акс!ом розширення Спри теоретико-доказовому niaxoAi)'.

2. ЕНдомо, то для деякого об'екта oi € 0 для деякого атрибута а^ значения аього атрибута нев!дсме i не обов'язково е елементом деяко! скхнченно! множини, але сама властяв!сть притаманна об'екту. Такий вид неповноти представляеться спе1Цальною зм1нною, наприклад и, яка називаеться нульовим або нев1домим ! снусчим значениям. Кев1дом! значения р!зних властивостей представляеться р1зними елементами w4 для кожного домена Donij.

3. В!домо, то для деякого об'екта о. г 0 властив!сть aj не притаманна взагаль незалежно в!д часу, хоча вона притаманна цьому класу об'еюпв. Така ситуация формал!зуеться шляхом введения спегиально! константи, то позначае не1снуюче значения. Ця константа е сильною для ycie! наявно! 1Нформац!1.

Суперечн!сть е формою невизначеност! хнформацП, пов'язано! не з нестачею, а э надм!рн!стю даних, i вказуе на те, то вйомо одночасно дек!лька р!эних оначень d^ для деякого атрибута а^ деякого об'екта о., хоча мохе !снувати т!льки одне значения.

Формал1зувати ситуацию -суперечност! можна за допомогою Koe$iuieHTiB ,дов!ри для кожного джерела !нформацП, методом i мов i рносного !нтервального оцшювання, методом вибору максимально! несуперечно! множини факт!в, а також за допомогою р!зних м!р невизначеност!, можливост!, необхшюст!, дов!ри, правдопод!бност1. Гакож можливо описувати суперечн!сть у 1С,

використовусчи лог1ку парадоксальност1 э 1стинносними значениями ■"тах", "hí", "i так, i hí">.

Запропонована класиф1кац1я можливих аномал!й 1нформац11 в !нформа1ййних системах дае единий п1дх1д до анал1зу методiв опису

та обробки в 1С р!зних вид1в некоректно! íh$opMaiiiI.

Другий розд1л присвячений роэробц! методу представления непсвно! 1нформад11 в 1С, який в::користовуе три види нульових або невкзначених значень. Зроблено бьчьш докладний лоравняяьний анал!з метод1в представления та обробки непсвно! !нформацП за допомогос нульових значень. IcHyD4i методи обробки неповно! !кформапд1 за допомогою двох вид!в нульових .значень, а саме "значения !снуе, але неь!доме" та "значения не icHye", . не охоплссть б!льш загального випадку неповноти 1нформацП, коли значения невгдоме, i його !снування також нев!доие. 3 метою опису ycix них вид i в неповно! ЛнформацП у реляц1йних базах даних ьропонуеться реляц!йна модель, що охоплюе тр_и нульових значения, а саме: А - значения icHye, але нев!доме, I - значения не icnye, U - значения невХдоме 1 його 1снуьання нев1доме. Для того, ш.об мати цомие!сть адекватно обробляти iu три нульових значения, v <сжина íctuhhochhx значень <Т - 1стина, F - хиба> поповнсеться ¿.е трьома астинносними значениями: I - незастосовуемо, А -можливо, U - неведомо, А чи I, одержуючи п'ятизначну лоПку S5. Вводяться основлi лог!чн1 onepaaií: V, & i -i.

Вводиться в1дношення порядку на множин! ícthhhochhx значень: А<=Т, F<=A, I<=F, U<=I. Таксж эадаеться множина акс1ом для лог!ки S5. Запропонована п'ятизначна лог1ка е консервативним розширенням звичайно! двозначно! лог!ки.

Неповним значениям атрибута А кортежу t Спозначаеться t.A) називаеться упорядкована пара значень: ívalCt.A), st(t.A)), де val Сt.А) е Dom(A) - значения власне даного t.A, а st(t.A) е {T,F,A,I,U> - його лог!чний статус. Якао лог!чний статус значения атрибута Á для кортежу t st.(t. А) е <1, A, U), то valCt.AD = *, де "*" - деяка стандартна константа.

На множин1 лог1чних статус1в <Т, F, А, I, Ю задаються предиката píbhoctí "=", HepiBHocTi та íhiíií, у тому числх предикат WW, який по пар! лог!чких статусов визначае, чи можуть вони характеризувати один об'ект, але належати р1зним неповним значениям; WWCsi ,st ) = F означае, що це неможливо.

i а

Неповним кортежем t називаеться упорядкована множина

неповних значекь атрибутов, до яка! додаеться статус кортежу Р5Т, який визначае, з якик !стинноснкм значениям входить цей кортеж, до даного в!дношення: 1?БТ е <Т,Г,А).

Два кортеж! I , I точно р!вн! по атрибуту. А, позначаються

1 .А = I .А, якщо \-alCt .А) = уа1а .А), .А)=Т. б^СС . АЗ=Т.

1 а 1 а « а

Два кортеж! I, 1г приблизно р!вн! по атрибуту А, позначаються .А = I .А, якщо МКвК! . АЭ.зШ .А))*Г та !з

.А^^а !а) сл!дуе уа1С1 .А)=уа1а ! А), а !з%1а ,А)=Г та

I а ' I г 1

з1С1г.А)=Т слхдус, що уа1С11. А)^уа1(1г. А).

У лем! 2.1 доводиться, що в!дношення пряблизко! р!вност! неповних значень мае властивост! рефяексивност! та симетричност!. що дал! зикористовуеться п!д час доведения властивостей залежностей даних -у в ^ношениях з неповними значениями.

Два кортеж! I , I точно ргвн!, позначаються I =1 , якщо для V А, е <А.....А }'а ГЕБТ = I ,Р£Т & I Л =1 .А. 3.

11 П I 2 11 2 1

Два кортеж! II , 12 приблизно р!вн1, позначаються I. = I , якш.0 для V А, € <А.....А ) I .А, а, ,А .

1 1 П 1 1 2 X

За допомогов в!дношень точно! та приблизно! р!вност!, як1 е розширеннями звичайного в^ношения р!вност! кортеж!в на кортеж! э нульовими значениями, виконувться реляц!йн1 оператору. над в!дношеннями з нульовими значениями та визначавться уэагальнен! функидональн! залежност! у них.

Множина кортеж!в з трьома нульовими значениями утворюе в!дношення з трьома нульовими- значениями.

Вводяться також узагальнен! функидональн! залежност! у в!дношеннях з нульовими значениями, за допомогов яких уводиться нормальна форма цих в!дношень.

У в!дношенн! Р эх схемою РСХУ) мае м!сце точна функциональна залежнють (ФЗ). позначаеться Х->У,.де X. У £ <А ,...А >, якщо для у . еРз1.Х = 1.Х вит1кае 1 Л »1.1.

1г 1 а 1 - а

У в!дношеши Р. з! схемов РСХУ) мае м1сце слабка функц!ональна залежн!сть, позначаеться X—>У, де Х,У 5 <А1,.. ,Ап}, якщо для у I Д еКз!.Х = 1.Х вит1кае I. Л = 1 Л.

'•и 1 г 1 г

Лема 2.2 докаэуе, що слабка функц!ональна эалежн!сть е б1льш загальним випадком точно! функц!онально! залежност!.

У в!дношенн! Р з! схемою РСХУ) мае м!сце залежшсть взаемного 1снування СЗВ1), позначаеться X <*> У, де ХД £ {А<. ,Ап>, якщо для у 1 € Р та для у А4 е X ! BJ <= У виконуеться ШСбК!. А4) ,з!С1. В^3Э.

Атрибут С або множина атрибут!в) X називаеться ключовим . для

в!дношення К, позначаеться X € КеуСЮ, якщо решта атрибутов в1дновення залехить в!д нього слабков функциональное залежн^ств. '.лвчов1 атрибуту. можуть мати свони значениями т!льки значения а логХчнкм статусом Т.

Для слабких <53 виконуються так! акс!оми виводу: для V ХЛ.г.У £ (А.....А } мае м!сце

£ П

А1. Рефлексивн!сть: X—>Х. А2. Доповкення: з X—>У випливас .12—>У. АЗ. Адктивнхсть: з X—>У ! X—>2 випливае X—>У2. А4. Проектлзн!сть: з Х-->У2 випливае Х-->У. А5. Транзитивн!сть: з X—>У ! У—>2 випливас Х~>2. А6. Псевдотранзитивнасть: з X—>У ! У2—випливае Х2—Ж Теорема 2.1. Система акс!ом А1-А6 е повнов. Для залежностей взаемного 1снування виконувться так; аксхоми виводу: для у Х,У,2 £ <А ....,Ап> мае м!сце Е1. Рефлексивн!сть: X <:» X - Т1 льки для X е .{А ,... ,Ап> Вй. Симетричзисть: з X У випливае У <£> X. ВЗ. Адитизн!сть: 3 X У I X <*> 2 випливае X <%> У2. В4. Проективн!сть: з X <%> Уг випливае X <%> У. Теорема 2.2. Система аксюм В1-В4 е повнов. Теореми 2.1 1 2.2 стверджувть, цо для задано! множини оалежностей даних Г не !снуе залежностей, ягЛ мають и¡сие заввди, коли мае м!сце Г, але не виводяться з Г за допомогов в!дпов!дних акс!ом виводу.

За допомогов узагальнених залежностей проводиться контроль цШсност! БД, уводиться нормальна форма, вхдношень з нульовими значениями. Узагальнен1 залехностх використовувться також для зменшекня неповноти !нформацП в систем!. Приводиться алгоритм зменшення неповноти iHoopMan.ii в систем!. який використовуе узагальнен! залежност! даних:

1. Множина узагальнених ФЗ Б' поступае на ВХ1Д алгоритму.

2. Якцо 3 X -> У е Б', то шукавться I .X = I .X.

Якщо уа1С1 . УЗ = уа1С1 .У), 51(1 1.У)'= Т, з!а . У) = Т, то

1 2 1 г

перейти до п.З.

Якщо уа1^ ,УЗ*уа1а .У), .У)=зК1 .УЗ=Т, то мае мЮде

1 2 1 Я

поручения ц!л!сност!, перейти до п. 5.

Якщо зКЦ.УЗ=Т, бК^. У)*Т, то уаК^.У) := уаК^Л), . У): =Т 1 повернутися до п. 1. 3. Якщо 3 X—>У е 8', то шукавться I .X = I .X. Якщо зи11.У)=5К1г.УЗ, уаК^.У^уаК^.У), то перейти до п?4.

Якцо valCti. Y)*valCt2.Y3 або stC^ . Y3*stCta. Y3, то Ф := maxCstC^ .Y3,stCt2.Y33, Д : = valCt^Y), .де *y. sUtj.Y)=«, stCtt.Y3=$, stCLa.YD=$? valCti. Y)=A, vaICt2.Y3=A i повернутися до n.l.' 2 1 2

4 Якщо 3 X Y е S', то для у t € R, у At е X i V В, е Y,

якцо WWCstCt. At3 ,stCt. Bj33 = F, то Ф = minCstCt. A. 3 ,stCt. B,)),

stCt.A,) = stCt. В «i = Ф, valCt. A. 3 = *, valCt.J^ =V 1 J 1 J

Якщо WCstCt. A ) ,stCt. Bj))^, то перейти до п. 5.

5. 0ск1льки подальш1 перетворення немохлив1, то к1нець роботи алгоритму.

Тут rain та max - з1дпов1дно onepauii знаходження ¡.анимума та максимума, виконання яких базуеться на вздношенн! порядку на мнояин1 ícthhhochhx значень.

Вводиться нормальна форма в1дношень з нульовими значениями: мдношення Rey неповнхй нормально $opjíÍ, якао yci його неклсчов! атрибути функидонально повно залекать В1Д ключа слабкою функидональною залеийстю.

Наведен1 розшкрення реляц1йних onepaTopiB, hkí дають можлив1сть обробляти вгдношення з трьома нульовими значениям. Щ оператори визначен1 т1льки для в1дношень, як1 е у неповн1й нормально форм1. Виконання них операторов базуеться на обробид значения атрибута А кортежу t за допомогоп значень stCt.A3, valCt.AD та t.RST. Такох при виконашй цих onepaTopiB використовуеться предикат приблизно! piBHOcTi неповних значень та кортеж!в.

Наприклад, розш,.рений оператор селекцП RCX в Y]"' для вхдношення R, де 0 е «,>,<,>,=,X - вираз типу valCt-А^З a6ost(t.An), Y б DomCA 3, або Y € <T,F,A,I,U) в1дпов1дно, задаеться так: RCX в YV = it: ЗЦе R, yAj s CA ,..,An> stCt. Aj) =

=stCt .A.), valCt. A. )=valCt .A,)/t.RST = t . RST & Cx"ff Y F3).

i 1 1 . 1 i 1

В1дношекня називаються сум!сними по з'еднаиню, якщо Mix Ix атрибутами icnye така взаемно-однозначна BiflnoBiAHicTb, ао надежна атрибути визначаються на одному домен!. В1дношення називаються несуперечними, якцо i3 строго! piBHocTi Ix кортеяав по клвчових атрибутах BHTixae приблизна pii-HicTb цих кортемв по íhuihx атрибутах. Теоретико-mhosmhhí оператори застосовуються т!льки до пар cyMicHnx та несуперечних в!дношень.

"Наприклад, розширений оператор перетину п' визначаеться так: R П" R =<t: 3teR,3tsR,tSt, у А. е С А.....A3,

1 2 1 I ' 2Z12 'l 1 П

stCt.A.) = maxCstCt .A 3,stCt .А. 33, valCt.A.) = valC'.A,),

i i i 2 l i j :

j e d,2): stet .Aj) = maxCstC^. A^ ,stCta. At33,

t.RST = WCstCt .AD, stCt .A 33 &...& WWCstCt .A3, stCt .A 33 &

ii г i in an

& t .RST & t .RST3.

I z

Аналогi4Hо виконуються розширен1 реляц1Ян1 оператори об'еднання, декартового добутку, теоретико-шгожинно! ргзност!, з'еднання в!дношень з трьома нульовими значениями.

Розширення у" звичайного реляцхйного оператора у називаеться консервативним. якцо на в1дношеннях, то м1стять у co6i Т1льки noBHi кортеж1 Скортех1 без нульових значень), мае Micue: - для унарних, у" Ra = Rt у Rz - для б1нарнкх оператор1в, тобто на повних кортежах у" виконуеться екв1валентно звичайному оператору у. Леми 2.3 - 2.9 доводять, ао Bei залропонован1 розширення реляц1йних оператор1в с консервативкими розширеннями. Таким чином, наведен! розширення операторхв реляц1йно! алгебри дають мoжливicть обробляти в!дношення з трьома нульовими значениями, а на кортежах без нульових значень ц! розширен1 оператори виконуються аналогi4Ho звичайним реляц!йним операторам.

Теорема 2.3 доводить, ад запропоновама реляцхйна алгебра з трьома нульовими значениями мае повноту не меншу, Hix звичайна реляц1йна алгебра.

У третьому роздал! розроблено метод представления та обробки диз'юнктивно! 1НформацП; викладений б1льш детальний пор1вняльний аналхз 1снуючих.метод1в представления та обробки диз'юнктивно! !нформацП в 1нформац1йних системах.

Пропонуеться розширена реляц1йна модель, що охоплюе диз'юнктивн1 значения. Диз'внктивним значениям СДЭЗ атрибута А для кортежу t € R називасться непуста п!дмножина в!дпов!дного домену dom(A) - ск!нченно! мнояини можливих значень атрибута.

Кортежем з |3 називаеться упорядкована множина диз'юнктивних значень атрибупв, до яко! додаеться статус кортежу RST, який визначае, з яким 1стинносним значениям входить цей кортеж до даного в!дношення: RST е <T,F,A>,

В!дношення R 13 схемою -С А^, •.., А > е в Сношениям ¿з диз'юнктивнкми значениями, якщо R е непустою падкиожиною декартового добутку з^отСАЗ х х tf^V. де х^У _ множима yeix п!дмножин домену domCA. 3, за винятком пусто! множини.

Кожному в!дношенню R, ао м!стить у codi ДЗ, i3 схемою ,..,АП>, ставиться у в!дпов!дн1сть множина в1дношень и°*еЧю.

- и -

що не м1стять у сосЦ ДЗ, таку, то Ц^СР) = V J 3 I € К,

уА4 € <А1,..,А ) а. ЮТ = Т & 31^4 А, е -> € Я*}*1 &

& Сук к*) -> $ р£е1)3 V С1.РБТ = А & З^Ча е 1.А ) ->

-> аде1€ & Зк = Р^е1 \ де - кортеж

вхдноиення К^ , в1дпов1дний заданому кортежу I € К для кожного j.

М!р.а неаизначеност! для диз'юнктивного значения атрибута А1

кортежу I була визначена так: ! I. А, 1

сна. А,) -------— ,

1 МотСА1Э!

де !1. А4! - к!льк1сть диз'вштв у 1.А Скардинал множини 1.А ¡бошСА.)! - кьлькость усах можливих значень атрибута.

М!ра невизначеносто кортежу I визначаеться так: ОКО = } аа.А :/п, де п к!лыасть атрибутов у

1 €<1,. . ,п>

в дношенно. Загальна мора невизначеност1 усього водношення К I ¡значаеться так: 01СЮ= 2 (На З/т, де т - колыасть

J еа,.. ,т>

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

Диз'снктивне значения N називаеться простим значениям, якщо N мае кардинал, р!вний 1. Кортеж називаеться детермонованим, якщо в1н складаеться тольки з простих значень атрибутов. 1накше кортеж називаеться недетерм1нованим. Просте значения М е елементом диз'снктивного значения N. якщо М 2 N. Два диз'юнктивних значения N о М точно р_овно, якщо вони обидза мають кардинал, р!вний 1, та 1х значения р1вн1, тобто ¡N1 = ', М! = 1 & N 5 М & М £ N. Диз'снктивне значения N. таке, що ¡N1 = 1, та деяке звичайне значения X точно р1вн1, якщо X е N.

Вводяться ще два параметри, як1 характеризувть р1вень невизначеност! онформацИ у выношеннп ГРАСМСЙЗ - р1вень фрагментами! Св!дношення к!лькост! не простих значень до загальноо колькосто значень у заношенно) ! ОЕТЕРМСЙ) . - частка детермонованих кортеж!в у в!дношенн! Р.

Для кортеж!в з ДЗ вводиться в!дношення приблизно! р1вност!, за допомогои якого виконуються реляцдйн! оператори. над вш-юшеннями з ДЗ та визначаються узагальнен! функидоналыи залежност! у в!дношеннях з ДЗ.

Два кортеж! ^ та 1 в!дношення Р приблизно р!вн! по атрибуту А, якщо Ц.А п А * 0. Два кортежа ^ и 12 в!дношекня Р приблизно ровн! на множин! атрибут!в X £ {д^,..,Ап>, позначаються СЦ,^) е 15СХ), якщо значения цих кортежЬч :;э всох атрибутах з множини X приблизно р!вн!, тобто 1л. А* п ^.А, * 0

о ^ "и

- 12 -

для ecIx А; е X. В1дношення ISCX) мае так! властивост!:

1) Ctj.i^ 6 ISCAjЭ для yt^eR, yAj 5<А1,..,АП> - ре$лексивн1сть;

2) (tjft2) e ISCAJ=> € ISC А О - симетричн!сть;

3) Ct ,t2) е ISCA,), Ct/\tO е ISCA,) Ct ,t,) e ISCA,)

iz j'a'i j i'd J

- нетранзитивн!сть.

Ще деяк! cyrTSBi властивост! в1дношення ISCX) були доведен! у таких теоремах: Теорема 3.1. Для у А £ <А^,..,АП> виконуеться ISCA)=a gAISCaj).

Теорема 3.2. Для у X, Y £ СА^,.. ,An> ISCX U Y)=ISCX) n ISCY). Теорема 3.3. Для V X, Y £ <А1,. .,An> ISCX) U ISCY) £ ISCX n Y). Теорема a_4,_ Для у X, Y £ iAj,.. ,An>, якщо X£Y, то ISCY)£lSCX). Даеться визначення ФЗ у в1дношеннях з ДЗ, яке використовуе в!дношення приблизно! piBHOCTi: узагальнена функидональна залежн!сть X >-> Y мае Micue у в!дношенн!, якщо ISCX) £ ISCY). За допомогою доведених властивостей Ыдношення IS доводиться властивост! узагалькених ФЗ.

Для узагальнених ФЗ виконуються такл акс!оми виводу: для у X,Y,2,W £ CAj,..,An) мають Micue D1. Рэфлексивн1сть: X >-> X. D2. Доповнення: з X >-> Y вит!кае Х2 ь> Y. D3. Адитивн1сть: з X >-> Y i X ь> Z вит!кае X >-> Y2. D4. Проектившсть: з X >-) Y2 BnriKae X >-> Y. D5. Транзитивн!сть: з X >-> Y ! Y v> Z вит!кае X >-> Z. D6. Псевдотранзит;'зн1сть: з X >-> Y i YZ >-> W в'.ткае Х2 >-> W. Теорема 3.5. Система aicciGM виводу D1-D6 в повною. Ця теорема стверджуе, що для задано! множини узагальнених ФЗ S не icHyc узагальнених ФЗ, як1 масть Micue завади, коли мае Micue S, але не виводяться з S за допомогою акс!ом D1-D6. •

За допомогою узагальнених ФЗ можливо проводити контроль цШсност! БД. Такоя узагальнен! ФЗ використовуються для змечшення неповноти !нформаци в систем!. Пропонуеться алгоритм зменшення м!ри кевизначеност! 1нформацЛ, який використовуе узагальнен! ФЗ:

1. На вх1д алгоритму поступай множина узагальнених ФЗ F+.

2. Для у А >-> В е F+, якщо 3 tt i t£: L .А = aj, ta.A = aa,

t.B = b,t.B = b,a =a,b ib -не npocTi значения, то 1 12 21212 r

b := b2.n b, ba := Ьг n b, повернутися до п. 1.

3. Для у А >-> В € F+, якщо 3 tt i ta: i .А = а , ta.A = аг, b , значения a , b , b - npocTi, a - диз'юнктивне значения,

¡г i i г г г

причому а п аг * 0, то мае Micue порушення ц!л1сности ! тому

СЛ1Д виконати перетворення аг := аг \ a i повернутися до п.1.

4. Якщо'хпд час перегляду множини F+ -не виконано ходне перетворення, то К1нець роботи алгоритму.

Доведена эавершуем1сть даного алгоритму. •

Якщо Mipy невизначеност! в1дношення R позначити QICR), а м!ру невизначеност! цього в!дношення п1сля обробки - QICR'), то виконуеться сп1вв!дношення QICR) > QICR').

Атрибут Сабо множина атрибут1в) X у розширенШ реляц!йн!й модел! називаеться ключовим для в1дношення R, позначаеться X € КеуСЕ), якщо решта атрибупв в1дношення залежить в!д нього узагальненою функциональною залежи ста, а значения самих ключових атрибут1в е простиш.

Введено дв! диз'юнктивн! нормальн! форми вадношень з ДЗ, аналог!чя1 першiЯ i друг!й нормальним фордам в1дношень звичайно! реляц!йно! модель

. Пропонуеться розширення реляц1Яних оператор1в, як! дають можлив!сть обробляти в!дношення з ДЗ. Щ оператори визначен! т1льки для з1дношень, як1 е у друПй диз'юнхтивнШ нормально форма. Виконання цих onepaTopiB базуеться на предикат! .приблизно! piBHOcTi ДЗ та коргежов з ДЗ.

Наприклад, якщо умова селекцП задаеться як t.a 0 X, де а е

€ <Ai,.. ,An>, X е DomCa),' або X - значения заданого атрибуту для

заданого кортежу Сале просте значения), 8 е {<,>,=,<,>>, тод!

розширений оператор селекц!1 визначаеться таким чином:

RaCt а д ю' = <t: С31, е R, у у е tt. а у 0 X => t.RST = tt .RSI,

V А 'б CA,,.. ,A„) t.A.'= t .A ) V C3t e R, 3 z e t .a : ' 1 l' n 111 2 2

z в К t.RST = А, у At e <AlP.. ,An> t. A4 = t2.A.3).

Теоретико-множишй оператори, як i у другому розд!л1, застосовуються т1льки до пар сум!сних та несуперечних в1дношень.

Наприклад, узагальнений оператор перетину п' над водношеннями з ДЗ задаеться так: R, П' R = <t: 3t € R , Et € R , V A € <Ai,. . ,A_>

1 Z 1 I 2 2 i i. II

t. A. = t . A n t . A, * 0, t.RST = t .RST & t . RST).

1112 1* 1 2

Значения останнього виразу розраховуеться в!дпов!дно до

таблиць трьохзначних лог!чних операций, наьедених Коддом.

Аналогично визначаютьсл й iHiui реляц1йн! оператори. Ця

узагальнена реляцойна алгебра дае можлив1сть магипулювати диз'юнктивними значениям.

У лемах 3.1 - 3.7 доводиться,, що запропонован1 розширення

рел."?ц!йних операторов на кортеж! з ДЗ е консервативными

розширеннями.

Наступиi теореми ствердгувть деяк1 властивост! запропоновано! розширено! реляидйно! алгебри, що охоплюе ДЗ.

Теорема 3.6. Оператори реляцМно! алгебри, яка дозволяе обробляти ДЗ, не знижують uipn невизначеностi одержаних' у результат! в1дкошень.

Описан! також основн! аспекти розробки конкретно! системи, яка обробляе диз'юнктивну ^формаЩв, та приклад реал!зацП запрспокованого п1дходу.

У четвертому роэд1л1 пропонуються методи та засоби практичного представления та обробки деяких вид1в некоректних знань у застосуванн1 до систем !ндуктивного виводу.

Пропонуеться метод обробки неповних даних у системах 1ндуктивного виводу, який називаеться ЖЗВ-методом, у якому неповн! дан! обробляються за допомогою нульових значень, описаних у другому роздШ.

. Пропонуеться також модель, виводу над ненад1йними данный, модиф1кована для використання в !ндуктивних системах. У запропонован!й методолог!! обробки ненадШних знань у системах !ндуктивного виводу за допомогою ouIhok кодуються дискретн! ймов1рност!, як1 квантиф1купть Mipy впевненост! експерта у ч1тко детерм1нованих под1ях. Для виконання виводу над ненад1йними Bxiднями даними та для уточнения апостер1орних оцхнок використовуеться механизм оперування з ненад1Яними даними, який у запропонованому п1дход1 носить приеднаний характер, тобто перерахування Mip неточность обумовлених сп1вв1дношеннями на множив наявних даних, супроводжуе кожний крок процесу виводу.

Ця модель виводу використовувалась при розробц! препроцесора обробки ненад!йних даних у !нструментальн!й експертн1й систем! ИндЭкс 2.0, в як12 було реал1зовано взазмод!ю методов индуктивного виводу з обробков нечетких та неповних даних.

Система ИндЭкс 2.0 призначека для прискорення розробки прикладних ЕС у слабо формал1зованих галузях, II використання дае MoxuKBicTb зам1сть вир1шення задач! за допомогою правил, вир!шувати П на 6a3i пор!внянь з под1бними задачами, виршеними ран1ш. Система ИндЭкс 2.0 дае можлив!сть використання-б!бл!отеки стратега !ндуктивного виводу, що метить в codi алгоритм ID3, модиф!коваиий для роботи з неловкими даними.

Ка 6asi ¿нструментально! експертно! системи ИндЭкс 2.0

були створен! encnepTHi системи, призначенг для класифхкацИ та прийняття р1шень по . стасИлХзацП еконо.'Лчно! ситуацП С класиф1катор .комплексу ЭКОЮ та для д1агностики захворювань Одихально! системи тварин. Описана технолог!я обробки неповних даних використовувалась також у багатофункидональному програмному комплекс! для оптим!зац!1 обстеження ociö, як! зазнали впливу pafliaui! в результат! аварП на ЧорнобильськЫ ^ЕС.

У шдсумках формулюються основн! результата, досягнутi в процес! виконання дисертац!йно1 роботи.

Список л!тератури м!стить у coöi основн! джерела вивчення та нараховуе 69 найменувань.

OCHOBHI РЕЗУЛЬТАТИ РОБОТИ

1. Зроблено анал!тичний огляд !снуючих метод!в представления та обробки неповно! !нформацП в !нформац1йних системах, "апропоновано рсзширення реляц1йно! модел! з метою представления ¡еловно! ДнформацП в базах даних за допомогов трьох вщЦв нульових значень. Побудовано розширену реляидйну алгебру, що охоплюе в!дношення з трьома нульовими значениями. Дослхдхено властивост! розширених оператор1в та розширено! алгебри. Розроблено принципи, методи та алгоритм! побудови 1С, як! представлявть та обробляють неповну !нформац1ю Сна приклад! систем !ндуктивного виводу).

2. Проведено огляд та анал!з !снуючих методiB представления та обробки диз'юнктивно! шформацП в 1нф0рмац1йних системах, запропоновано розширення релятийно! модел! з метою представления тако! !нформацп в ба-ах даних. Побудовано. розширену реляц!йну алгебру, но охоплюе в!дношення з диз'юнктивними значениями. Дослхджен! властивост! розширених операторов та розширено! алгебри. Запропоновано приклад реал!зацП п!дходу до обробки та представления диз'юнктивно! 1нформацП в !нформацдйних системах.

3. Визначено нормальш форми в розширених реляц1йних моделях, запропоновано узагальнен! функц1ональн! залежност! в розширених реляц1йних моделях, вивчен! найсйльш icTOTHl властивост! цих функцдональних залекностей. Запропоновано алгоритм:! використання узагальнених функц!ональних залекностей даних з метою довизначення даних у 1С.

Основн! положения дисертацП опубл!кован! в таких працях:

1. Андон Ф. И., Боровая Э.Н. Реляционная модель с тремя нулевыми значениями - Киев, 1992. - 16 с. - СПрепр. / АН Украины. Ин-т кибернетики им. В. М. Глушкова; 92-23).

2. Андон Ф. И.,' Боровая Э. Н. Обработка дизъюнктивной информации в базах данных // Использование математических методов и информационных технологий в технических и экономических системах - Киев: Ин-т кибернетики им. В.М.Глушкова АН Украины, 1992. - С. 40-47.

3. Боровая Э. Н. Функциональные зависимости в базах данных с неточной информацией // Тез. докл. семинара "Новые информационные технологии и инструментально-технологические средства поддержки принятия решений" СКацивели, 1-5 нояб. 1992 г.).- Киев, 1992.-С. 29-31.

4. Боровая Э.Н., Рогушина Ю. В. Работа с неполными, нечеткими и ненадежными данными в системах индуктивного вывода // Там же. -Киев, 1992. - С. 31-33.

5. Боровая Э. Н., Рогушина Ю. В., Нечваленко Е. И. Методика извлечения знаний из примеров в системах, обрабатывающих неполные данные // Представление знаний в информационных системах. - Киев: Ин-т кибернетики им. В. М. Глушкова АН Украины, 1993. - С. 60-64.

6. Боровая Э. Н.. Расширение ER-модели для описания сложных объектов // Тез. докл. II Мехдунар. науч.-техн. семинара "Теоретические и прикладные проблемы моделирования предметных областей в системах баз данных и знаний" СТуапсе, 20-25 сент. 1993 г.). - Киев, 1993,- С. 110-115.

7. Моделирование слабоформализуемых предметных областей с неполными данными с применением индуктивного ■ вывода / Э.Н.Боровая, Ю.В. Рогушина, Е.И. Нечваленко, Н.И. Галаган // Там же. - Киев, 1993,- С. 119-124.

8. Метод выявления противоречий в информационных системах / Ф.И. Андон, Э.Н. Боровая, A.B. Резниченко, Ю.В. Рогушина// Тез. докл. конф. "Инженерия и инструментальные средства программирования" СКиев, 1-4 июня 1993 г.).- Киев, 1993,- С. 10-13.

9. Processing of Incomplete Data in Example-Learning Systems / E.N. Borovaya, N.I. Galagan, J.V. Rogushina, E.I. Nechvalenko //Proceedings of EWAIC (Moscow, Sept. 7-9, 1993). - M., 1993.- P. 301-305.