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

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

Одеський національний політехнічний університет

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

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

05.13.23 - Системи та засоби штучного інтелекту

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

Шабадаш Дарія Валеріївна

Одеса 2007

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

Робота виконана в Одеському національному політехнічному університеті Міністерства освіти і науки України на кафедрі системного програмного забезпечення.

Науковий керівник доктор технічних наук, професор Крісілов Віктор Анатолійович, Одеський національний політехнічний університет, завідувач кафедри системного програмного забезпечення

Офіційні опоненти доктор технічних наук, професор Машталір Володимир Петрович, Харківський національний університет радіоелектроніки, професор кафедри інформатики;

кандидат технічних наук, доцент Коваль Василь Сергійович, Тернопільський національний економічний університет, доцент кафедри інформаційно-обчислювальних систем та управління

Захист відбудеться “ 12 ” грудня 2007 року о 1330 годині на засіданні спеціалізованої вченої ради К 41.052.08 Одеського національного політехнічного університету за адресою: 65044, м. Одеса, проспект Шевченка, 1, ауд. 400-А.

З дисертацією можна ознайомитись у бібліотеці Одеського національного політехнічного університету за адресою: 65044, м. Одеса, проспект Шевченка, 1.

Автореферат розісланий “ 8 ” листопада 2007 р.

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

1. Загальна характеристика роботи

штучний інтелект невизначеність

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

Будь-який опис ПО системи ШІ має невизначеність. Джерелами цієї невизначеності можуть бути вхідні дані, наприклад, в силу неможливості одержання точних даних. Крім того, використовувані методи одержання, зберігання й обробки знань також можуть вносити невизначеність.

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

Значний внесок у рішення проблем врахування невизначеності зробили такі відомі вчені як: Заде Л., Коско Б., Ягер Р., Колмогоров А.М., Загоруйко М.Г., Машталір В.П., Тоценко В.Г., Коваль В.Н., Кук Ю.В., Ротштейн А.П..

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертація виконувалась відповідно до завдань НДР Одеського національного політехнічного університету № 539-73 “Методи і засоби побудови автоматизованих систем обробки інформації і управління”, №393-73 “Інформаційні системи в проектуванні та керуванні”, №434-73 “Дослідження та проектування засобів інтелектуальної обробки даних” та “Дослідження та розробка інформаційної технології інтелектуальної обробки даних” (номер державної реестрації № 0105U007571).

Мета і завдання дослідження. Метою дослідження є підвищення інформативноcті, зменшення розмірності та обсягу опису ПО системи ШІ шляхом формалізованого формування її моделі.

Відповідно до мети дослідження необхідно вирішити наступні задачі:

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

-- проаналізувати джерела невизначеності в задачах ШІ і класифікувати різні види невизначеності;

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

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

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

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

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

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

Об'єктом дослідження є опис предметної області системи ШІ.

Предметом дослідження є методи і засоби формування опису предметної області системи ШІ.

Методи дослідження. Наведені в дисертаційній роботі результати базуються на комплексному використанні методів системного аналізу на етапі аналізу джерел невизначеності в системах ШІ; методів теорії інформації і теорії нечітких множин на етапі розробки кількісних показників для оцінки значень різних видів невизначеності і на етапі розробки методу формалізованого формування виміру; методів комбінаторики на етапі розробки методу формування агрегатів в OLAP-системах.

Наукова новизна одержаних результатів:

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

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

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

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

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

Система Dimensions використовувалася для вирішення задачі формування опису часових характеристик експонатів в Одеському археологічному музеї. Було отримане зменшення обсягів зберігання часових характеристик експонатів у середньому в 6 разів, а також підвищення інформативності представлення датувань у середньому в 1,16 рази і зменшення їхньої невизначеності в середньому в 2,16 рази.

Також система Dimensions була впроваджена в ТОВ Одеський Торговий Дім “Сонячна долина” для вирішення задачі розрахунку агрегованих значень для OLAP-системи, яка використовується на підприємстві в якості аналітичної системи. У результаті було отримано зменшення обсягів зберігання агрегатів в 1,72 рази.

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

Наукові результати, отримані в дисертаційній роботі, використані в навчальному процесі на кафедрі системного програмного забезпечення, ІКС, ОНПУ, у рамках дисциплін “Засоби інтелектуальної обробки інформації”, “Основи проектування систем штучного інтелекту” та „Технології розробки програмного забезпечення”.

Особистий внесок здобувача. Виконано аналіз джерел невизначеності в системах ШІ [1, 8, 11]. Сформульовано дві задачі оцінки й врахування невизначеності даних [2, 11]. Введено поняття схованої й проявленої невизначеності і запропоновані кількісні показники для їхньої оцінки [7, 8, 9]. На підставі розроблених кількісних показників схованої й проявленої невизначеності, одержав подальший розвиток метод формування лінгвістичної змінної [5]. Розроблено методи врахування невизначеності інформаційної грануляції даних, а саме: метод формалізованого формування виміру ПО [6] і метод формування агрегатів в OLAP-системах [13]. Розроблені методи застосовувалися при формуванні опису предметної області хімічних речовин (холодоагентів) [3, 4, 12], а також при аналізі наукових задач, пов'язаних з стисканням відео даних для передачі їх через мережу Інтернет [10].

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

Апробація результатів дисертації. Основні результати роботи доповідалися й обговорювалися на: 38-й науковій конференції “Сучасні інформаційні технології та телекомунікаційні мережі” (Одеса, Україна, 2003), 5-й міжнародній науково-практичній конференції “Штучний інтелект-2004” (Кацивелі, Україна, 2004), науково-практичній конференції “Современные информационные и электронные технологии” (Одеса, Україна, 2004, 2007), 11-й міжнародній конференції “Knowledge-Dialogue-Solution” (Варна, Болгарія, 2005), 11-й російській конференції по теплофізичним властивостям речовин (Санкт-Петербург, Росія, 2005), 16-му симпозіумі по термофізичним властивостям речовин “An Automated System for Calculating Risk and Ecological Damage of Refrigerants” (Болдер, Колорадо, США, 2006).

Публікації. Матеріали дисертації викладені у 13 публікаціях, 6 з яких опубліковані у фахових журналах відповідно до списку ВАК України.

Структура дисертації. Дисертація складається зі вступу, чотирьох розділів, двох додатків. Обсяг дисертації - 164 стор., з них додатків - 6 стор. Дисертація містить 43 рисунки, 9 таблиць та посилання на 109 літературних джерел.

2. Основний зміст роботи

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

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

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

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

Будемо розрізняти поняття шкали й виміру.

Визначення 1. Шкала - це математична абстракція, яка використовується для відображення значень властивостей деякої характеристики об'єкта.

Визначення 2. Вимір - це одномірна математична модель деякого поняття, яка на практиці повинна розглядатися тільки з певними обмеженнями.

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

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

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

Розрізняють чітку і нечітку ІГ. Чітка ІГ передбачає відсутність перетинань між гранулами, при цьому самі гранули є чіткими множинами. У процесі чіткої ІГ з'являється невизначеність, пов'язана з кількістю включених у гранулу об'єктів, що не розрізняють. Чим більше об'єктів сховано в гранулі, тим вище її невизначеність. Найбільш поширене на сьогоднішній день застосування чіткої ІГ в інтелектуальних системах, що використовують багатомірні бази даних (ББД) - OLAP-системах. Актуальність розгляду питань чіткої грануляції в OLAP-системах зв'язана в першу чергу з питанням оптимального формування агрегатів для даних, збережених у ББД. Правильно побудовані ієрархії вимірів і правильний вибір тих членів ієрархії, для яких необхідно зберігати агреговані значення, кардинально впливає на продуктивність всієї OLAP-системи.

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

Однак при застосуванні будь-якого виду ІГ залишається актуальним питання, який рівень невизначеності грануляції є припустимим для розв'язуваної задачі ШІ. Для оцінки рівня невизначеності та інформативності використовують різні кількісні показники. Для визначення ступеня нечіткості нечіткої множини часто використовується міра Ягера Р., що зводиться до виміру відстані між нечіткою множиною і її запереченням. Інша ентропійна міра нечіткості була запропонована Коско Б., і заснована вона на понятті кардинального числа нечіткої множини.

Крім того, часто використовується показник інформативності по Колмогорову А. М., який оцінює комбінаторну складову інформації, яку має деяка змінна відносно залежної змінної. Однак вищезазначені показники не дозволяють дати інтегральну кількісну оцінку невизначеності опису ПО, оскільки характеризують тільки окремі її аспекти. Так, показник інформативності по Колмогорову А.М. розглядає тільки комбінаторний аспект невизначеності, а міри нечіткості Коско Б. і Ягера Р. - тільки рівень нечіткості множин.

Таким чином, наприкінці даного розділу зроблений висновок про доцільність досліджень, спрямованих на розробку кількісних показників невизначеності вимірів, сформованих у процесі ІГ і комплексного підходу до оцінки невизначеності процесу формування опису ПО в системах ШІ.

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

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

Для підвищення конструктивності й наочності аналізу джерел і видів невизначеності в системах ШІ будемо розглядати деяку систему у вигляді “чорної скриньки”

функціонування системи . Під невизначеністю системи мається на увазі невизначеність, внесена процесом формування рішення.

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

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

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

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

Нехай G - деякий процес грануляції, що складається з n кроків.

Визначення 3. Під рівнем грануляції будемо розуміти розбивку виміру, отриману на і-ому кроці грануляції G, i=0..n.

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

Визначення 4. Відображення F множини гранул, що лежать на деякому рівні грануляції , у множину гранул, що лежать на наступному рівні грануляції будемо називати і-м етапом грануляції:

.

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

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

Для обчислення проявленої невизначеності використаємо формулу:

, (біт) (1)

де m - кількість можливих значень деякого виміру.

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

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

Сховану невизначеність i-й гранули виміру будемо обчислювати як:

, (біт)

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

Загальну сховану невизначеність одного виміру будемо обчислювати як:

, (біт)

де , - відповідно число отриманих у ході грануляції гранул і число вихідних гранул, на підставі яких проводилася грануляція. З умови дискретності та скінченного числа гранул, одержуваних у процесі грануляції: .

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

, (

,

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

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

, .

Цей випадок відповідає верхньому рівню грануляції . Слід зазначити, що існують задачі, в яких одна гранула на вимірі має сенс. Наприклад, в OLAP-системах - це кореневий елемент на верхньому рівні ієрархії. В інших задачах мінімальне число значень на номінативній шкалі - два. Тоді мінімальне значення виявленої невизначеності: .

Сформулюємо вищезазначене у вигляді аксіом.

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

Аксіома 2. Для будь-якого процесу грануляції G існує нульовий рівень грануляції , для якого вся невизначеність виміру визначається тільки проявленою невизначеністю:

.

Аксіома 3. Для будь-якого процесу грануляції G існує верхній рівень грануляції , для якого проявлена невизначеність виміру мінімальна, а схована невизначеність - максимальна:

.

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

На основі аксіом 1 - 3 була встановлена наступна залежність.

Якщо на t-ому етапі грануляції , де n - кількість етапів грануляції G, для будь-якої гранули на рівні грануляції , j=1..l, де l - кількість гранул на , виконується:

1. всі гранули формуються рівномірно й немає значень, не включених ні в яку із гранул: , j=1..l, i=1..l де , - кількість значень рівня , схованих в i-й або j-й гранулі рівня ;

2. гранули не мають перетинань: Ш, j=1..l, i=1..l;

3. всі гранули чіткі множини: , де - кардинальне число гранули , тоді справедливе рівняння:

, (4)

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

Виконання рівняння (4) означає, що процес грануляції не вніс додаткової невизначеності в опис ПО системи ШІ. У реальних системах строге виконання умов 1 - 3 можливо рідко, однак при порівнянні різних способів опису предметної області системи найбільша близькість до виконання даного рівняння може служити критерієм найкращого із запропонованих описів.

З рівняння (4) слідує, що для грануляції без втрат інформативності схована невизначеність отриманого виміру дорівнює:

.

Назвемо цю сховану невизначеність оптимальною - :

(5)

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

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

(6)

Можливі кілька варіантів значень .

1. означає, що процес грануляції не вніс невизначеності в опис ПО системи.

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

3. означає недоцільність використання отриманого виміру в силу його високої невизначеності для розв'язуваної задачі.

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

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

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

Поняття лінгвістичної змінної було запропоновано Заде Л. для приблизного опису явищ, які настільки складні, що не піддаються опису в кількісних термінах. В основі поняття лінгвістичної змінної полягає поняття нечіткої ІГ.

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

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

Пропонується формалізувати процес формування лінгвістичної змінної шляхом оцінки рівня її невизначеності на основі розроблених кількісних показників схованої і проявленої невизначеності. Для оцінки невизначеності сформованої лінгвістичної змінної пропонується використати характеристику грануляції (6).

Лінгвістична змінна характеризується набором (Х, Т(Х), U, С, M), де Х - назва змінної, Т(Х) - терм-множина змінної Х (кожне із цих значень є нечіткою змінною Х зі значеннями із універсальної множини U з базовою змінною u), С - синтаксичне правило, що породжує назви Х значень змінної, М - семантичне правило, що ставить у відповідність кожній нечіткій змінній Х її зміст М(Х).

Представимо процес формування лінгвістичної змінної як процес нечіткої ІГ. Початковим рівнем грануляції будемо вважати множину U. Наступним рівнем грануляції будемо вважати терм-множину Т(Х). Верхнім рівнем грануляції будемо вважати вимір, що має одне значення Х.

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

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

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

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

Розглянемо застосування розроблених показників схованої і проявленої невизначеності для процесу чіткої ІГ. Чітка ІГ застосовується в OLAP-системах для побудови ієрархій вимірів і обчислення агрегованих значень показника для кожного члена ієрархії. Зі збільшенням розміру ББД стає актуальним питання оптимального формування агрегатів. При збільшенні об'ємів збережених у OLAP-системі даних і наповненні її надлишковими ієрархічними рівнями об'єм збережених агрегованих значень росте по експонентній залежності. З іншого боку, якщо відмовитися від формування агрегатів, продуктивність OLAP-системи буде падати, оскільки для одержання результату запиту користувача необхідно буде в реальному часі формувати необхідні в запиті агрегати.

Представимо процес побудови ієрархій одного j-го виміру куба як процес чіткої ІГ , де j=1..x, x - кількість вимірів куба. Тоді кожному рівню ієрархії j-го виміру куба буде відповідати рівень грануляції , де t=0..k, k+1 - кількість рівнів ієрархії j-го виміру куба. Нульовому рівню j-й грануляції відповідає початковий рівень ієрархії j-го виміру куба, на якому представлені значення вихідних даних. Верхньому рівню j-й грануляції відповідає верхній рівень ієрархії j-го виміру куба, на якому представлений тільки один кореневий елемент ієрархії.

Позначимо - кількість гранул (значень) на рівні грануляції . Тоді дорівнює кількості значень вихідних даних для j-го виміру куба, а . Тоді z-ю гранулу на рівні грануляції позначимо як , де z=1...

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

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

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

Для кількісної характеристики ступеня обчислювальних витрат системи на обчислення агрегованих значень у реальному часі і ступеня агрегованості OLAP-куба використовуються відомі показники відповідно й . При цьому: =0 , =1 - ситуація, коли всі агреговані дані зберігаються в системі; =1, =0 - ситуація, коли всі агреговані дані обчислюються системою в реальному часі.

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

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

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

Програмна система Dimensions використовувалася для вирішення різних задач формування опису ПО. Однією з них була задача формування опису часових характеристик експонатів в Одеському археологічному музеї. Часові характеристики експонатів мають високу невизначеність, пов'язану з неможливістю точно віднести експонат до певного року. Експерт, що оцінює часові характеристики даного експоната, вносив додаткову невизначеність розпливчастими формулюваннями датувань, наприклад “друга половина I століття н.е.”. У результаті датування експонатів були представлені у вигляді строкової слабо формалізованої інформації, у різних термінах і з різним ступенем точності, що ускладнювало аналіз часових характеристик об'єктів.

Результати застосування методу формалізованого формування виміру в цій задачі показали зменшення характеристики грануляції в 3,43 рази. На підставі цього показника було отримане підвищення інформативності представлення часових характеристик експонатів у середньому в 1,16 рази, зменшення їхньої невизначеності в середньому в 2,16 рази та зменшення обсягів їх зберігання у середньому в 6 разів. Отримані результати веріфікувалися шляхом обчислення значень показників нечіткості Ягера й Коско і показником інформативності Колмогорова.

З використанням програмної системи Dimensions була вирішена задача розрахунку агрегатів для OLAP-системи підприємства Одеський Торговий Дім “Сонячна долина”. Загальне число членів вимірів досліджуваної OLAP-системи дорівнювало 2646. Результати вирішення задачі формування агрегатів у системі Microsoft SQL Server Analysis Services і в системі Dimensions представлені.

Для будь-якого фіксованого значення значення на графіку Dimensions буде менше, ніж на графіку Microsoft SQL Server Analysis Services. Це справедливо й для будь-якого фіксованого значення . Таким чином, використання розробленого методу дозволяє оптимізувати обчислювальні витрати OLAP-системи й кількість збережених агрегованих значень у ній. Отже, гіпотеза 1 одержала емпіричне підтвердження.

В табл.1 наведені значення продуктивності та обсягу зберігання агрегатів досліджуваної OLAP-системи, де , - відповідно продуктивність системи та обсяг агрегатів, що зберігаються для Microsoft SQL Server Analysis Services; , - аналогічні показникі для системи Dimensions. Отримані результати свідчать про ефективність розробленого методу формування агрегатів, який дозволяє при встановленому рівні продуктивності системи зменшити обсяг зберігання агрегатів. Для OLAP-системи підприємства замовником було обрано значення продуктивності 75%. В результаті використання системи Dimensions було отримано зменшення обсягів зберігання агрегатів в 1,72 рази, порівняно з системою Microsoft SQL Server Analysis Services.

Висновки

У дисертаційній роботі були вперше розроблені і обґрунтовані: метод формалізованого формування виміру ПО системи ШІ, заснований на розроблених кількісних показниках схованої і проявленої невизначеності інформаційної грануляції даних, і метод формування агрегатів в OLAP-системах, заснований на оцінці кількості схованої невизначеності гранул вимірів куба OLAP-системи.

1. На початковому етапі дослідження був проведений аналіз існуючих методів врахування невизначеності в системах ШІ. Серед них були виділені як найбільш перспективні методи теорії нечітких множин.

2. Новий підхід до аналізу джерел невизначеності в системах ШІ дозволив виділити різні її види й сформулювати дві задачі оцінки й врахування невизначеності в системах ШІ.

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

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

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

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

7. Виконано практичну реалізацію розроблених методів у вигляді інтелектуальної програмної системи Dimensions.

Дана програмна система використовувалася для вирішення задачі формування опису часових характеристик експонатів в Одеському археологічному музеї. Було отримано зменшення обсягів зберігання часових характеристик експонатів у середньому в 6 разів, а також підвищення інформативності представлення збережених датувань у середньому в 1,16 разів і зменшення їхньої невизначеності в середньому в 2,16 разів.

Також система Dimensions була впроваджена в ТОВ Одеський Торговий Дім “Сонячна долина” для вирішення задачі розрахунку агрегованих значень для OLAP-системи. У результаті було отримано зменшення обсягів зберігання агрегатів в 1,72 рази.

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

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

1. Крисилов В.А., Шабадаш Д.В. Неопределенность данных и знаний в системах поддержки принятия решений // Искусственный интеллект. - 2003. - №1. - C. 67 - 74.

2. Крисилов В.А., Шабадаш Д.В. Две задачи оценки и учета неопределенности данных в СППР // Искусственный интеллект. - 2004. - №4. - С. 368 - 375.

3. Дубро И.В., Бодюл О.И., Шабадаш Д.В. Анализ решений при оценке экологической опасности холодильных агентов // Холодильная техника и технология. - 2004. - №4 (90). - C. 33 - 39.

4. Бодюл О.И., Дубро И.В., Шабадаш Д.В. Информационно-вычислительная система для определения экологических показателей холодильных агентов // Холодильная техника и технология. - 2006. - №2 (100). - C.85 - 90.

5. Шабадаш Д.В. Оценка неопределённости лингвистической переменной. // Східно-Європейський журнал передових технологій. - 2007.-№1/2(25). - C. 39-43.

6. Крисилов В.А., Шабадаш Д.В. Метод формализованного формирования измерения предметной области системы ИИ. // Східно-Європейський журнал передових технологій. - 2007. - №3/2(27). - C. 26 - 30.

7. Krissilov V., Shabadash D. Towards the Problems of an Evaluation of Data Uncertainty in Decision Support Systems // Information theories & applications. - 2006. - Vol.13, № 4. - P. 376 - 379.

8. Шабадаш Д.В. Формалізація опису об'єктів аналізу в системах підтримки прийняття рішень // Тези доповідей 38-ої наук. конф. молодих дослідників ОПУ-магістрантів “Сучасні інформаційні технології та телекомунікаційні мережі”- Одесса: ОНПУ, 2003. - С. 66.

9. Крисилов В.А., Шабадаш Д.В Формирование описания предметной области систем поддержки принятия решений //Материалы междунар. научно-технической конференции “Искусственный интеллект. Интеллектуальные и много-процессорные системы”. - Кацивелі, 2004. - Т. 2. - С. 111.

10. Чепелев Д.В., Боровков И.В., Шабадаш Д.В. Программный комплекс трансляции видео через Интернет // Труды седьмой междунар. НПК “Современные информационные и электронные технологии”. - Одесса, 2006. - Т. 1. - С. 126.

11. Шабадаш Д.В. Крисилова Н.В. Анализ источников неопределённости в задачах принятия решений // Труды пятой междунар. НПК “Современные информационные и электронные технологии”. - Одесса, 2004. - С. 111.

12. Bodyul O.I., Dubro I.V., Bodyul E.S., and Shabadash D.V. An Automated System for Calculating Risk and Ecological Damage of Refrigerants // Proc. of Sixteenth Symposium on Thermophysical Properties - Boulder, 2006. - 1 електр. опт. диск (CD-ROM):цв; 12 см. - Систем. вимоги: Windows ME/2000/XP. Acrobat Reader. - Заголовок з титул.екрану.

13. Крисилов В.А., Шабадаш Д.В. Метод формирования агрегатов в OLAP-системах, основанный на оценке количества скрытой неопределённости гранул измерений куба. // Труды восьмой междунар. НПК “Современные информационные и электронные технологии”. - Одесса, 2007. - С. 73.

Аннотация

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

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

Метою роботи є підвищення інформативноcті, зменшення розмірності та обсягу опису ПО системи ШІ шляхом формалізованого формування її моделі.

У роботі запропоновано новий підхід до аналізу джерел невизначеності в системах ШІ. На його основі були введені поняття схованої і проявленої невизначеностей ІГ даних та розроблені кількісні показники для їхньої оцінки. На базі цих показників одержав подальший розвиток метод формування лінгвістичної змінної. Запропоновано формалізувати цей процес шляхом оцінки рівня невизначеності сформованої змінної. Крім того, на підставі запропонованих показників невизначеності був розроблений метод формалізованого формування виміру. Також в роботі розроблено метод формування агрегатів в OLAP-системах, заснований на оцінці кількості схованої невизначеності гранул вимірів куба. Розроблені в дисертаційній роботі методи застосовувалися при вирішенні задач формування опису предметних областей системи аналізу даних та розрахунку агрегованих значень для OLAP-систем. Виконано практичну реалізацію розроблених методів у вигляді інтелектуальної програмної системи Dimensions.

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

Annotation

Shabadash D.V. Methods of account of data's information granulation uncertainty at subject domain modelling in artificial intelligence systems. - Manuscript.

Thesis for a candidate's degree by speciality 05.13.23 - Systems and instruments of artificial intelligence. - Odessa national polytechnic university, 2007.

The aim of the work is increase of informativity, reduction of description's dimension and size of subject domain in AI systems by the formalized formation of its model.

In work new approach to the analysis of uncertainty sources in AI systems is offered. On its basis concepts of hidden and shown uncertainty of data granulation were entered and quantity indicators for their estimation were developed. On the basis of these parameters the method of linguistic variable formation received further development. It is offered to formalize this process by estimation of variable's uncertainty level. Besides on the basis of the offered parameters was developed method of formalized formation of dimension. Also in the work the method of aggregates formation in the OLAP-systems, based on estimation of hidden uncertainty quantity of cube's granules was developed. The methods developed in this work were used to solve problems of formation of subject domains description for data analysis systems and calculation of aggregated values for OLAP-systems. The practical realization of the developed methods was executed in the form of program system Dimensions.

Keywords: uncertainty, linguistic variable, information granulation, intellectual data analysis, online analytical processing system (OLAP-system).

Аннотация

Шабадаш Д.В. Методы учёта неопределённости информационной грануляции данных при моделировании предметной области в системах искусственного интеллекта. - Рукопись

Диссертация на соискание учёной степени кандидата технических наук по специальности 05.13.23 - Системы и средства искусственного интеллекта - Одесский национальный политехнический университет, Одесса, 2007.

В рамках развития современных систем ИИ для учёта неопределённости наибольшее распространение получили методы нечёткой логики, основанные на понятии нечёткой информационной грануляции. Однако существенным недостатком данных методов является то, что формирование нечётких информационных гранул полностью возложено на эксперта и не формализовано. Существующие показатели информативности и нечёткости позволяют лишь косвенно оценить величину неопределённости ПО системы ИИ. Отсутствие комплексных количественных показателей неопределённости не даёт возможности сравнить различные способы описания одной и той же ПО и выбрать наилучший из них с точки зрения требований к точности результатов работы системы ИИ. Разработка таких показателей позволила бы сделать процесс формирования описания ПО итеративным, но целеориентированным.

Целью диссертационной работы является увеличение информативности, уменьшение размерности и объёма описания ПО системы ИИ путём формализованного формирования её модели.

В работе предложен новый подход к анализу источников неопределённости в системах ИИ. На его основе были введены понятия скрытой и проявленной неопределённостей ИГ данных и разработаны количественные показатели для их оценки.

На базе этих показателей получил дальнейшее развитие метод формирования лингвистической переменной. Предложено формализовать данный процесс путём оценки уровня неопределённости сформированной переменной. Соотношение значений скрытой и проявленной неопределённостей позволяет оценить переход от базовой числовой переменной к нечётким множествам, а также сравнивать неопределённость лингвистической переменной для разных видов функций принадлежности. В результате процесс формирования описания ПО системы ИИ с использованием методов теории нечётких множеств остаётся итеративным, но становится целеориентированным.

На основе предложенного подхода к оценке неопределённости лингвистической переменной был разработан метод формализованного формирования измерения. Данный метод отличается от существующих тем, что содержит на этапе анализа сформированного измерения количественные характеристики неопределённости. Это позволяет на основе объективных, численных показателей выбрать то измерение из всех сформированных экспертом, которое имеет наименьшую неопределённость для решаемой задачи ИИ. В целом для системы ИИ это приводит к повышению информативности представления хранимых данных и уменьшению объёмов хранимой информации.

Также в работе предложен метод формирования агрегатов в OLAP-системах, основанный на оценке количества скрытой неопределённости гранул измерений куба. Использование данного метода позволяет оптимизировать вычислительные затраты OLAP-системы и объём хранимых в ней агрегатов.

Разработанные в работе методы использовались при решении задач формирования описания предметных областей системы анализа свойств хладагентов и системы свёртки виодео данных.

Выполнено практическую реализацию разработанных методов в виде програмной системы Dimensions. Данная система использовалась для решения задачи формирования описания временных характеристик экспонатов в Одесском археологическом музее. Было получено уменьшение объёма хранения временных характеристик экспонатов в среднем в 6 раз, а также повышение информативности представления хранимых датировок в среднем в 1,16 раза и уменьшение их неопределённости в среднем в 2,16 раза.

Также система Dimensions была внедрена в ТОВ Одесский Торговый Дом “Солнечная долина” для решения задачи расчёта агрегированных значений для OLAP-системы. В результате было получено уменьшение объёмов хранения агрегатов в 1,72 раза.

Ключевые слова: неопределённость, лингвистическая переменная, информационная грануляция, интеллектуальный анализ данных, система оперативной обработки информации (OLAP-система).

Размещено на Allbest.ru

...