ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ

ЮДІН Сергій Анатолійович

УДК 004.89

МЕТОД ФОРМУВАННЯ ОБРАЗІВ В ЗАДАЧАХ ІНТЕЛЕКТУАЛЬНОГО АНАЛІЗУ ДАНИХ

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

Автореферат

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

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

ОДЕСА – 2006

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

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

Науковий керівник: | доктор технічних наук, професор

Крісілов Віктор Анатолійович,

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

Офіційні опоненти: | доктор технічних наук, професор

Машталір Володимир Петрович,

Харківський національний університет радіоелектроніки,

професор кафедри інформатики;

кандидат технічних наук, доцент

Кондратенко Галина Володимирівна,

Національний університет кораблебудування

ім. адмірала Макарова,

доцент кафедри “Комп’ютеризовані системи управління”.

Провідна установа: | Донецький державний інститут штучного інтелекту НАН України, кафедра системного аналізу і моделювання, м. Донецьк

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

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

Автореферат розіслано “ 5 ” вересня 2006 р.

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

Савєльєва О.С.

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

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

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

Крім наявності апріорних обмежень на характеристики образів, важливу роль при отриманні результатів відіграє простір ознак (ПО), в якому вирішується задача ФО. Як правило, процес формування ПО розглядається як окрема задача ІАД, ніяк не пов’язана з іншими задачами, для яких він формується. Однак, дослідження процесу ФО в різних ПО показали, що існують певні характеристики простору ознак, специфічні для ФО. Урахування цих факторів ще на етапі формування ПО дозволяє суттєво підвищити якість результатів ФО.

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

Значний внесок у вирішення цих проблем ІАД зробили такі відомі вчені, як Машталір В.П., Івахненко А.Г., Шевченко А.І., Гладун В.П., Загоруйко Н.Г., Айвазян С.А., Заде Л. і деякі інші.

Зв’язок роботи з науковими програмами, планами, темами. Дисертація виконувалась відповідно до завдань НДР Одеського національного політехнічного університету № 329-62 “Апаратно-програмні засоби автоматизованих систем” та №329-73 “Розробка інформаційного та програмного забезпечення сучасних автоматизованих систем” (держ. рег. № 0100U001400), №393-73 “Інформаційні системи в проектуванні та керуванні” та № 434-73 “Дослідження та проектування засобів інтелектуальної обробки даних” (держ. рег. № 0103U000036).

Мета і завдання дослідження. Підвищення достовірності та зменшення часу формування образів в задачах ІАД шляхом формалізації процесу формування образів: розробки критерію якості ФО та урахування нових складових процесу, які впливають на якість результатів.

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

— проаналізувати специфіку сучасних методів розв’язання задачі ФО і застосування цих методів у інтелектуальних системах (ІС), розглянути відомі підходи до розв’язання задач ФО, обрати найбільш перспективний, визначити напрямки його розвитку;

— розробити показник та критерій якості ФО, в основу яких покласти характеристику компактності розташування об’єктів в образах;

— розробити алгоритм ФО на базі запропонованого критерію якості;

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

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

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

— виконати практичну реалізацію розробленого методу ФО в окремій програмній системі або в одному з модулів ІС;

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

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

Предмет дослідження – методи структурного синтезу просторів ознак, методи формування образів, властивості і склад критеріїв формування образів.

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

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

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

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

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

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

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

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

Система CLUSTER була впроваджена при розв’язанні такої задачі економічного моніторингу, як аналіз економічної ефективності функціонування мережі автозаправних станцій (АЗС) на основі ФО множини АЗС.

Розроблена система була впроваджена в ТОВ “Профіт”, яка є дилером підприємства з іноземними інвестиціями “ЛУКОЙЛ-Україна” в м. Одеса, та ТОВ “ВЕК”.

Автоматизація процесу розв’язання задачі оцінки ефективності функціонування АЗС в ТОВ “Профіт” та застосування відповідних організаційних заходів на основі отриманих результатів забезпечило збільшення ефективності функціонування мережі АЗС на 18% Розв’язання тієї ж задачі в ТОВ “ВЕК” забезпечило підвищення ефективності приблизно на 15 %.

За допомогою ІС CLUSTER було розв’язано задачу формування якісної навчальної вибірки при застосуванні нейронної мережі для прогнозування курсу валют. При навчанні нейронної мережі, мінімальну середню похибку навчання вдалось зменшити на 13% за умови прискорення процесу навчання в середньому на 15%.

Особистий внесок здобувача. Виконано аналіз існуючих методів розв’язання задачі ФО [1]. Здійснено формалізацію задач стосовно напрямку теми дисертаційної роботи [1, 2]. Вибрано та вдосконалено найбільш перспективні методи здійснення ФО на множині об’єктів у ІС [3, 5, 7]. Автор запропонував показник якості ФО, який базується не на абсолютному, а на відносному значенні відстані, враховує однорідність розподілу об’єктів у образах та реагує на зміну середнього значення л-відстані всередині образів [4]. На основі цього показника було розроблено метод ФО [4, 5]. Запропоновано методи вирішення проблем помилкової компактності на етапі формування простору ознак та метод оцінки класоутворючих здатностей ознак, що є важливим при рішенні задачі ФО [2, 5, 8]. Уперше аналіз розв’язання задач формування простору ознак та ФО було проведено в комплексі, а не окремо, що дало можливість розробити комплексний метод розв’язання задач ФО у загальному виді [4, 5, 6]. Цей метод було реалізовано в програмній системі та застосовано для розв’язання практичних задач інтелектуального аналізу даних [5].

Апробація результатів дисертації. Основні результати роботи доповідалися й обговорювалися на: тридцять восьмій науковій конференції “Сучасні інформаційні технології та телекомунікаційні мережі” (Одеса, 2003), третьому російсько-українському науковому семінарі “Інтелектуальний аналіз інформації – ІАІ-2003” (Київ, 2003), п’ятій міжнародній науково-практичній конференції “Штучний інтелект-2004” (Кацивелі, 2004), п’ятій міжнародній конференції “Інтелектуальний аналіз інформації – ІАІ-2005” (Київ, 2005), шостій міжнародній науково-практичній конференції “Штучний інтелект-2005” (м. Дивноморське, Росія, 2005).

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

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

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

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

У першому розділі на основі аналізу відомих підходів обговорюється гіпотеза компактності як базова при розв’язанні задач формування образів, та гіпотеза л-компактності, як розвиток гіпотези компактності. В літературі гіпотеза компактності здебільшого формулюється таким чином: при правильному формуванні простору ознак реалізації одного й того ж образу відображаються в ПО в геометрично близькі точки, утворюючи “компактні” сплески. Якщо визначити множину з k ознак як описуючу, додаткову номінальну ознаку як цільову, множину досліджуваних об’єктів як , новий об’єкт, що розпізнається як , а той факт, що об’єкти множини О “компактні” в просторі k ознак P як , гіпотезу компактності можна сформулювати таким чином:

.

На основі наведеного формулювання запропоновано формальну постановку задачі ФО, яка дозволила ввести оригінальну класифікацію задач ФО.

Дано: множина об'єктів, кожен з яких представлений множиною значень ознак.

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

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

Таблиця 1

Характеристики основних задач ФО

Тип | Апріорні дані | Критерій якості | Методи розв’язання задач

1 | Множина об'єктів (O), кількість образів (m) | F=f(m) | Нейронні мережі, методи, засновані на теорії нечітких множин, ієрархічні, генетичні, евристичні алгоритми.

2 | Множина об'єктів (O), кількість об'єктів у образах (v) | F=f(v)

3 | Множина об'єктів (O), розміри образів (r) | F=f(r)

4 | Множина об'єктів (O) | Евристичні критерії | Евристичні алгоритми

Проведено аналіз всіх видів задач ФО та запропоновано послідовність процесу розв’язання цих задач поділити на два основних етапи:

— формування простору ознак;

— етап застосування конкретного алгоритму розв’язання задачі ФО.

Для виділення найбільш ефективних алгоритмів розв’язання задачі ФО проведено порівняльний аналіз основних існуючих алгоритмів. На основі результатів аналізу одними з найперспективніших було виділено алгоритми ФО, засновані на гіпотезі л-компактності, яка є розвитком гіпотези компактності.

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

Для того, щоб обчислити значення ф необхідно побудувати повний граф, який об’єднує між собою всі об’єкти досліджуваної множини. Довжиною ребра графу, яке зв’язує дві вершини a та b, вважається значення евклідової відстані між цими вершинами. Тоді для визначення нормованої характеристики локальної неоднорідності ф, знаходиться відношення , де – довжина ребра (a, b), а вmin – найкоротше ребро із суміжних ребру (a, b). Нормована характеристика локальної неоднорідності , де фmax – максимальне значення ф*, знайдене в повному графі.

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

Якщо факт л-компактності множини об’єктів О в просторі Р визначити як , гіпотеза л-компактності може бути сформульована таким чином:

.

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

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

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

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

Наслідком гіпотези л-компактності є твердження про те, що чим більша величина л-відстані, що відповідає ребру л-ННШ, тим ймовірніша можливість проходження по цьому ребру границі між образами. Таким чином величина л-відстані зв’язана з можливістю розриву ребра графа л-ННШ. З кожною вершиною л-ННШ у загальному випадку може бути зв’язано k ребер. Показник ненадійності зв’язку між вершинами л-ННШ, який характеризує ступінь можливості розриву i-го ребра pi пропонується представити в такий спосіб:

(1)

де лi – л-відстань, що відповідає i-му ребру, зв’язаному з вершиною z у л-ННШ,

k – кількість ребер, зв’язаних з вершиною z.

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

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

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

Показник якості формування образів. Якщо серед усіх ребер побудованого л-ННШ знайти ребро, якому відповідає мінімальна л-відстань – два образи, з'єднані цим ребром графа, об’єднуються в один образ.

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

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

(2)

Критерій якості формування образів. Критерієм якості пропонується вважати таку величину, як характеристику найкращого варіанта ФО:

(3)

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

лp-алгоритм формування образів. На основі запропонованого критерію якості ФО в роботі розроблено лp-алгоритм ФО.

На відміну від свого найближчого аналога – алгоритму ФО л-KRAB, запропонований в роботі лр-алгоритм засновано на критерії якості, який формується виключно на базі просторових характеристик розподілу об’єктів. Крім того, завдяки відмові від повного перебору на кожному кроці алгоритму і зменшенню кількості кроків, лp-алгоритм є більш швидкодіючим ніж його аналог.

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

Помилковою компактністю є таке розташування об’єктів в ПО, при якому не виконується гіпотеза л-компактності.

Потрібно розрізнювати чотири види помилкової компактності:

? відносна близькість об’єктів різних образів;

? відносна віддаленість об’єктів одного образу;

? нерозрізненість об’єктів;

? рівномірне (некомпактне) розташування об’єктів різних класів у ПО.

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

Два об’єкти та будемо називати нерозрізненими, якщо виконується:

Окремим випадком нерозрізненості об’єктів є розташування об’єктів у наповненому просторі ознак, де в кожній точці ПО розташований об’єкт досліджуваної множини та , де – кількість можливих градацій j-ї ознаки, k – кількість ознак в ПО, n – кількість об’єктів. Але проблема помилкової компактності, що пов'язана з нерозрізненістю об'єктів, може виникати не тільки в заповненому просторі ознак. У дискретному обмеженому просторі ознак улучення більш ніж одного об'єкта в ту саму точку – ситуація цілком імовірна. І в цьому випадку об'єкти також будуть нерозрізнені.

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

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

Суть підходу „Локального збільшення кроку дискретизації простору” (ЛЗКДП) зводиться до визначення функції, що дозволяє штучно розподілити нерозрізнені об'єкти в околиці точки скупчення та перетворити точку в “хмару” об’єктів. Вираз (4) дозволяє обчислювати координати j-го нерозрізненого об'єкта в i-й точці нерозрізненості у випадку одномірного простору ознак.

, (4)

де j – номер нерозрізненого об’єкта i-ї “хмари”;

n – кількість нерозрізнених об’єктів i-ї “хмари”;

ki – величина відстані між нерозрізненими об'єктами i-ї “хмари”;

xi – координата точки нерозрізненості.

На основі виразу (4) розроблено підхід ЛКЗДП, спрямований на уникнення нерозрізненості об’єктів у ПО. Формально його може бути описано таким чином:

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

Інший підхід „Додавання ознаки „кількість об’єктів в точці” (ДО”КОТ”) полягає в перевірці наявності наборів об'єктів, що потрапляють у ту саму точку, а також кількості об'єктів у кожному такому наборі. Формування образів на множині пропонується здійснювати в модифікованому просторі ознак – первинний простір ознак та ще одна ознака, яка характеризує кількість повторень об’єктів вибірки.

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

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

Метод уникнення рівномірного розташування об’єктів. У роботі запропоновано метод вирішення проблеми рівномірного розташування об’єктів у ПО за рахунок виключення з ПО некласоутворюючих ознак. Цей вид проблеми помилкової компактності виникає не тільки у випадку ідеальної рівномірності в розташуванні об’єктів, а й тоді, коли компактні сплески в розташуванні об’єктів наявні, але незначні. В такому випадку ознака, яка забезпечує таке „розмиття” образів, може суттєво знизити якість результату та збільшити час аналізу.

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

Некласоутворюючою ознакою називається ознака ПО, яка забезпечує рівномірне розташування об’єктів: кількість образів, отриманих при ФО за цією ознакою, близька до кількості об’єктів або дорівнює одиниці.

Метод виключення з ПО некласоутворюючих ознак:

1. Оцінка ступеня компактності розташування об’єктів за кожною окремо взятою ознакою з простору ознак.

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

3. Оцінка допустимості розрахованих у попередньому пункті втрат.

4. Виключення з простору ознак, які не є класоутворюючими, або тих, які мають невеликі класоутворюючі властивості.

Користуючись критерієм якості ФО (3), можна визначити найкращий рівень деталізації ФО за кожною ознакою.

Показником класоутворюючих властивостей ознаки пропонується вважати таку величину:

(5)

де m – кількість образів, отриманих у відповідності з критерієм якості ФО;

n – кількість об’єктів вибірки.

Вираз (5) називається коефіцієнтом класоутворення ознаки.

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

Запропоновано значення показника класоутворюючих властивостей простору ознак при автоматичному формуванні ПО (6).

, (6)

де U(i) – значення показника класоутворюючих властивостей ПО;

– значення показника якості ФО відповідної ознаки.

Критерій якості простору ознак для визначення класоутворюючих властивостей може бути сформульований таким чином: найкращим рівнем показника якості ФО слід вважати максимум показника класоутворюючих властивостей ПО.

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

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

В об’єктно-орієнтованій моделі ФО виділено три групи класів: класи, які служать для модифікації простору ознак, група класів ФО та група класів вибірки та інтерпретації зовнішніх даних. Для опису реалізації другого етапу комплексного методу ФО „Попередній аналіз”, який складається з декількох процедур послідовного перетворення ПО, в моделі використовується перша група класів, зокрема клас „Список ознак”. Цей клас формує простір ознак. Список ознак утворюється шляхом виключення з первинного списку неінформативних ознак. Оцінка неінформативності здійснюється через клас „Ознака”, який звертається до класу „Тип неінформативності”. В останньому класі є метод „Обчислити значення неінформативності”, який повертає значення, обчислені різними способами в залежності від значення атрибута „функція типу неінформативності”. В залежності від „Списку ознак” формується клас „Список властивостей об’єкта”.

Група класів ФО використовується для реалізації алгоритму ФО. Клас „Об’єкт аналізу” пов’язаний з цим класом через атрибут „Список значень властивостей об’єкта”. Клас „Образ” може містити в собі від одного до n екземплярів класу „Об’єкт аналізу”. Виявлення зв’язку між класами „Список образів” та „Список об’єктів аналізу” є основною метою запропонованого комплексного методу формування образів.

У четвертому розділі на основі запропонованого методу формування образів було розроблено інтелектуальну програмну систему CLUSTER, яку було використано для розв’язання задач порівняльного аналізу існуючих та запропонованого методів ФО, а також для розв’язання декількох практичних задач.

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

Дано: зображення розміром 246Ч300, яке складається з квадратів розміром 3Ч3 точки, характеристики яких зафіксовані в чотирьох спектральних потоках. Оскільки з вибірки було виключено змішаний тип ґрунту, кількість аналізованих об’єктів n = 6435, кількість ознак k = 36.

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

При рішенні цієї задачі зменшення помилки першого та другого роду, порівняно з результатами отриманими з використанням мережі Кохонена та алгоритму л-KRAB, склало 16-20% та 13-20% відповідно. Час отримання результатів наведено в табл. 2.

Таблиця 2

Час розв’язання задач порівняльного аналізу

Задача | Мережа Кохонена, хв. | л-KRAB, хв. | Запропонований метод, хв.

Задача Фішера | 0,2 | 3 | 0,5

Задача сегментації зображення | 8 | 46 | 15

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

Не бралася до уваги й кількість ітерацій навчання та час, необхідний для аналізу та інтерпретації результатів, який суттєво залежить від кваліфікації експерта, який здійснює аналіз. На відміну від нейронної мережі Кохонена, запропонований метод не потребує ніякого додаткового настроювання, виключає виникнення необхідності в додаткових ітераціях та допускає мінімальний рівень кваліфікації користувача. Запропонований метод забезпечив на 12% більшу достовірність результатів порівняно з мережею Кохонена, та на 20% більшу достовірність і виграш у часі, в середньому, на 75% порівняно з алгоритмом л-KRAB. Така перевага системи CLUSTER, пояснюється тим, що завдяки гіпотезі л-компактності, запропонований лp-алгоритм ФО дозволяє виявляти однорідні зони. Більша достовірність порівняно з алгоритмом ФО л-KRAB обумовлена універсальністю запропонованого критерію якості ФО. Практичну реалізацію запропонованого методу ФО було здійснено при розробці удосконаленого методу формування навчальної вибірки для прогнозування зміни курсу валют на міжнародному ринку Forex.

Результатом застосування цього методу було зменшення мінімальної середньої похибки на 13% порівняно з класичним методом формування навчальної вибірки – методом „вікон”. Цей метод реалізовано в розробленій інтелектуальній системі CLUSTER.

За допомогою системи CLUSTER вирішено задачу аналізу економічної ефективності мережі АЗС, що належать ТОВ „Профіт” – дилеру ПІІ „ЛУКОЙЛ-Україна” в Одеській області та ТОВ „ВЕК”.

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

ВИСНОВКИ

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

1. За результатами аналізу відомих методів ФО, в якості найбільш перспективних, було обрано методи, засновані на гіпотезі л-компактності.

2. Розроблено показник якості ФО, заснований на гіпотезі л-компактності. В його основу покладено величину, яка характеризує зміну л-відстані всередині образів і не вимагає привнесення додаткових гіпотез щодо розташування об’єктів. На базі показника запропоновано критерії якості ФО.

3. На основі запропонованого критерію якості ФО розроблено лp-алгоритм ФО, що дозволило формалізувати процес розподілу об’єктів по образах.

4. Розроблено підходи до вирішення проблеми формування простору ознак з урахуванням можливості виникнення нерозрізненості, що забезпечило підвищення достовірності ФО.

5. Розроблено метод виключення з ПО ознак, які не забезпечують компактність розташування об’єктів, що дозволило підвищити достовірність та зменшити час ФО.

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

7. Здійснено практичну реалізацію розробленого комплексного методу формування образів в інтелектуальній системі CLUSTER. Ця система призначена для розв’язання задач ФО як окремої задачі ІАД і як елемента розв’язання інших задач. ІС CLUSTER може бути застосована для задач ФО будь-якого типу.

8. Розроблений програмний засіб було застосовано для порівняльного аналізу методів ФО та розв’язання практичних задач. При порівняльному аналізі досліджувалася достовірність результатів та час, витрачений на розв’язання задач ІАД: достовірність результатів склала 84-96%, а виграш у часі, порівняно з алгоритмом л-KRAB, 67-83%. Розв’язання практичних задач аналізу ефективності функціонування мереж АЗС забезпечило підвищення ефективності у середньому на 15-18 %.

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

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

1. Юдін С.А. Структурування баз даних на основі методів автоматичної класифікації // Тр. Одес. политехн. ун-та. – Одесса, 2005. – Спецвыпуск – С.40–44.

2. Крисилов В.А., Юдин С.А. Естественная и искусственная таксономия // Искусственный интеллект. – 2005 – №1. – C. 74–85

3. Крисилов В.А., Юдин С.А. Решение задачи таксономии на основе гипотезы компактности при анализе данных // Искусственный интеллект. – 2005 – №4. – C. 699–707.

4. Крисилов В.А, Юдин С.А, Крисилова Н.В. Проблемы “ложной” компактности в дискретном пространстве признаков в задачах таксономии // Тр. Одес. политехн. ун-та. – Одесса, 2004. – №2 (22). – С. 91–97.

5. Крисилов В.А., Сухарев Д.Е., Юдин С.А. Механизмы адаптивности автоматизированных систем управления предприятием // Холодильна техніка і технологія. – Одесса, 2003. – №3 (83) – С. 85–88.

6. Крисилов В.А., Юдин С.А. Метод выбора системы признаков на основе гипотезы л-компактности при решении задач ИАД // Тр. Междунар. конф. “Интеллектуальный анализ информации ИАИ-2005”. – К.: Просвіта, 2005. – С.187–195.

7. Крисилов В.А., Юдин С.А. Гипотеза компактности в задачах таксономии // Мат. междунар. конф. “Интеллектуальные и многопроцессорные системы - 2005”. – Таганрог: ТРТУ, 2005 – С. 251–257.

8. Юдін С.А. Гіпотеза компактності в задачах кількісного обґрунтування прийняття рішень // Тези доп. 38-ї наук. конф. „Сучасні інформаційні технології та телекомунікаційні мережі”. – Одеса: ОНПУ, 2003 – С.50.

Юдін С.А. Метод формування образів в задачах інтелектуального аналізу даних. – Рукопис.

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

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

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

На основі запропонованого критерію якості розроблено новий метод формування образів, який відрізняється від відомих підходів наявністю в ньому специфічних етапів процесу формування простору ознак в умовах розв’язання задачі ФО та вдосконаленим методом ФО. Результати роботи методу забезпечують в середньому на 10-15% більшу достовірність – відповідність вибірковим даним.

Розроблений метод реалізовано у вигляді інтелектуальної програмної системи CLUSTER, що показала високу ефективність при рішенні задач ФО як окремої задачі аналізу даних та інших задач, які потребують розв’язання задачі ФО. Достовірність результатів від 84 до 96%, економічний ефект від впровадження системи – збільшення прибутку на 15-18%.

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

Yudin S.A. Method of image creating in problems of intellectual data analyses. – Manuscript.

Thesis for a candidate’s degree by spatiality 05.13.23 – Systems and instruments of artificial intelligence. – Odessa national polytechnic university, 2006.

The aim of this work is improvement of effectiveness of decision-making processes in tasks of intellectual analysis by development methods of optimization the information sign space and improvements of the taxonomy tasks decision methods and shaping on base of these methods and algorithms the complex method directed to formalization, speedup and improvement validity of decision making.

In work is offered new factor of quality of taxonomy, which is founded on л-compactness hypothesis and allows to improve the automation of taxonomy tasks decision.

On base of the offered factor of quality, is worded criterion of quality and is designed taxonomy method, which results of the using provide 10-15% greater validity at the average, in the sense of adequacy got results and selective data.

It is designed new method of image creating, which differs from the known approaches by presence specific stages for formalization of the process of the shaping information space sign in condition of the decision of taxonomy tasks and use the advanced method of taxonomy. Designed method was realized as a intellectual program system CLUSTER, which has shown high effectiveness at decision of the taxonomy tasks as separate problem of the data analysis and the other tasks, which require the decision