Даревич Романа Романівна

УДК 004.78:025.4.036+004.91

АВТОМАТИЗОВАНА МЕТАПОШУКОВА СИСТЕМА

НА ОСНОВІ АДАПТИВНОЇ ОНТОЛОГІЇ

05.13.06 – Автоматизовані системи управління

та прогресивні інформаційні технології

АВТОРЕФЕРАТ

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

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

Львів – 2007

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

Робота виконана в Фізико-механічному інституті ім. Г.В. Карпенка

Національної академії наук України.

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

Досин Дмитро Григорович

Фізико-механічний інститут ім. Г.В. Карпенка НАН України,

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

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

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

Медиковський Микола Олександрович

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

професор кафедри автоматизованих систем управління, заступник директора Інституту комп’ютерних наук та інформаційних технологій;

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

Олецький Олексій Віталійович

Національний університет „Києво-Могилянська Академія”, доцент факультету інформатики.

Захист відбудеться "11" жовтня 2007 р. о 14:00 год. на засіданні спеціалізованої вченої ради Д35.052.14 при Національному університеті "Львівська політехніка" за адресою: 79013, м. Львів, вул. С. Бандери, 12.

З дисертацією можна ознайомитися у бібліотеці Національного університету "Львівська політехніка" за адресою: 79013, м. Львів, вул. Професорська, 1.

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

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

кандидат технічних наук, доцент А.Є. Батюк

загальна характеристика роботи

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

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

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

Розвинуті у роботі положення ґрунтуються на результатах досліджень українських та зарубіжних вчених, зокрема: Дж. Солтона, П. Фолтса, Дж. Сови, Т. Андреасена, О. В. Палагіна, А. В. Анісімова, В. П. Гладуна, О. В. Олецького, О. Г. Дубинского, І. Є. Кураленка, І. В. Некрасова, І. В. Совпеля та інших.

Зв’язок роботи з науковими програмами, планами, темами.

Робота виконана в рамках таких науково-дослідних тем: „Розробка базових технологій побудови експертних систем та систем підтримки рішень в області фізико-хімічної механіки конструкційних матеріалів на основі використан-ня локаль-них корпоративних баз даних та засобів Інтернету”, № держреєстрації 0103U003344; „Розробка інтелектуальної системи автоматизації інформаційного пошуку в мережі Інтернет та в локальних корпоративних базах даних із засобами машинного навчання”, № держреєстрації 0102U002684; „Розробка методичних рекомендацій для здійснення автоматизованого документообігу та інформаційного пошуку в мережі Інтернет”, № держреєстрації 0105U004326; „Інформаційно-технічне забезпечення досліджень з розробки нових матеріалів”, № держреєстрації 0105U004313.

Участь автора полягала у побудові синтаксично-семантичного аналізатора природної мови та аналізі функціонування пошукових систем у мережі Інтернет (0103U003344); розробленні методу визначення подібності (релевантності) двох електронних текстових документів, поданих у вигляді концептуальних графів, адаптації аналізатора Link Parser до задач МПС автоматизованого робочого місця (0102U002684); побудові та дослідженні моделі онтології інтелектуальної МПС, методу зважування її елементів та процедур оптимізації (0105U004326); підготовці для монографії „Застосування інформаційних технологій для координації наукових досліджень” розділу „Засоби реалізації інтелектуальних систем та їх застосування у матеріалознавстві”, де, зокрема, детально описано побудову онтології засобами Protйgй (0105U004313).

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

Для досягнення поставленої мети в роботі необхідно вирішити такі завдання:

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

· розробити метод динамічного обчислення коефіцієнтів важливості понять та зв’язків між ними в онтології;

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

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

· побудувати та дослідити імітаційну модель процесу генерування та оптимізації онтології;

· розробити архітектуру МПС у складі віртуального автоматизованого робочого місця (ВАРМ) наукового працівника.

Об’єкт дослідження: процес пошуку та опрацювання інформації у МПС;

Предмет дослідження: методи та засоби оцінювання релевантності текстових документів автоматизованою МПС на основі адаптивної онтології.

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

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

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

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

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

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

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

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

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

· розроблена архітектура інтелектуальної МПС як однієї з основних служб ВАРМ наукового працівника забезпечує автоматизацію інформаційного пошуку електронних анотацій наукових публікацій у мережі Інтернет;

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

Розроблені методи, алгоритми та відповідні програмні засоби застосовані для побудови служби автоматизованого інформаційного пошуку електронних анотацій наукових публікацій у мережі Інтернет у складі віртуального автоматизованого робочого місця наукового працівника, впровадженого у Фізико-механічному інституті ім. Г. В. Карпенка НАН України та Інституті надтвердих матеріалів ім. В. М. Бакуля НАН України, що засвідчено відповідними актами. Результати наукових досліджень використано також у навчальному процесі Національного університету “Львівська політехніка”, зокрема при викладанні дисципліни “Бази даних та знань” як в окремих розділах лекційних курсів, так і в лабораторних та практичних роботах.

Особистий внесок здобувача. Усі наукові результати одержані здобувачем особисто. У працях опублікованих у співавторстві внесок здобувача такий: [1], [10] – розроблено систему опрацювання текстової інформації на основі синтаксичного аналізатора; [2] – аналіз відомих систем у термінах моделі кількісної оцінки інтересу суб’єкта; [3] – огляд існуючих підходів до визначення міри подібності текстів, чисельне моделювання методу порівняння документів; [4] – реалізація моделі в програм-ному середовищі CLIPS та його об’єктно-орієнтованому розширенні CLIPS Object-Oriented Language (COOL); [5] – розроблення моделі онтології у вигляді зваженого графа та принципів побудови системи зважуван-ня, чисельне моделювання розподілу вагових коефіцієнтів понять онтології за рівнями; [6] – модель експертної системи для прогнозування пошкоджень в енергетиці та нафтохімії, принцип формування бази знань системи; [8] – метод оцінювання подібності текстових документів, поданих їх концептуальними гра-фами, побудова концептуального графа анотації за допомогою аналізатора Link Parser; [9] – аналіз особливостей інформаційного пошуку в мережі Інтернет; [12], [13] – алго-ритм семантичного порівняння текстів, доповнених контекстом з адаптивної онтології; [16] – аналіз існуючих підходів, алгоритми оптимізації структури та змісту онтології бази знань; [17] – розроблення архітектури МПС як окремої компоненти ВАРМ наукового працівника.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися на семінарах та конференціях, зокрема: Міжнародному молодіжному форумі „Інформаційні технології в ХХІ столітті”, Дніпропетровськ, 2003; Міжнародній науково-практичній конференції студентів, аспірантів та молодих вчених „Системний аналіз та інформаційні технології”, Київ, 2003; Міжнародній конференції по автоматичному управлінню „Автоматика”, Київ, 2004; Міжнародній конференції „Інтернет-освіта-наука”, Вінниця, 2004; Відкритій науково-технічній конференції молодих науковців і спеціалістів Фізико-механічного інституту ім. Г.В. Кар-пенка НАН України, Львів, 2005; Міжнародній науково-практичній конферен-ції „Математичне та програмне забезпечення інтелектуальних систем”, Дніпро-петровськ, 2005; Міжнародній науко-во-технічній конференції „Штучний інтелект”, Кациве-лі, 2004, 2006; International Conference on Computer Science and Information Technologies, Львів, 2006; Міжнародній конференції „Ефективність реалізації наукового, ресурсного і промислового потенціалу в сучасних умовах”, Славськ, 2007.

Публікації. Результати досліджень за темою дисертації відображені в 17 наукових працях, із них 8 опубліковано у фахових виданнях, чотири – одноосібні.

Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, списку використаної літератури, що містить 126 найменувань, та трьох додатків. Загальний обсяг дисертації становить 143 сторінки, у тому числі 43 рисунки та 5 таблиць.

основний Зміст роботи

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

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

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

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

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

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

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

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

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

· забезпечувати контроль цілісності онтології;

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

Модель адаптивної онтології подано у вигляді п’ятірки: G(C,R,F,W,L), де C – скінченна множина атомарних понять ПрО; R – скінченна множина семантичних зв’язків між атомарними поняттями ПрО; F – скінченна множина функцій інтерпретації, яка встановлює аксіоматичну взаємозалежність понять з множини С через множину зв’язків R; W, L – множина коефіцієнтів важливості понять та зв’язків відповідно, обчислювати які запропоновано за таким алгоритмом:

1. Повна вага Wji класу онтології дорівнює сумі власної ваги , ваги підкласів та ваги суміжних класів (класів, зв'язаних з даним класом не „is-a” зв'язком):

, | (1)

де ? вага k підкласів j-го класу i-го рівня;

? вага класу ; ? вага зв’язку між класами та .

2. У момент внесення на і+1-й рівень нового підкласу йому присвоюється власна вага , рівна половині власної ваги класу, вищого (і-го) рівня. Вага класу та усіх бать-ківських класів аж до кореневого збільшується на величину ваги новоствореного підкласу:

. | (2)

3. Під час встановлення зв’язку між поняттями k1 та k2 між відповідними вершинами графа онтології з’являється ребро, а до ваги суміжних класів Wn1 додаєть-ся вага Wс2 і, навпаки, до Wn2 додається вага нового, суміжного до нього, класу Wс1:

. | (3)

4. Вага екземпляра у базі знань дорівнює повній вазі (1) його класу в онтології.

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

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

Рис. 1. Програмний інтерфейс імітаційної моделі адаптивної онтології

Зокрема, дослідження стосувалося:

· виявлення можливих зворотних залежностей (циклів) під час обчислення коефіцієнтів важливості елементів онтології;

· оцінювання кількості елементів з однаковою мінімальною вагою;

· визначення діапазону значень, які можуть приймати коефіцієнти важливості понять.

В моделі застосовано статистику розподілу елементів за рівнями таксономії лексичної бази даних WordNet.

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

Досліджено розподіл елементів онтології за діапазонами ваг для визначення кількості елементів з мінімальною однаковою вагою (рис. 3). Їх кількість повинна бути обмежена, для того щоб при подальшому вилученні цих елементів, як найменш цінних з точки зору їх важливості в даній ПрО, не виникала неоднозначність вибору. Діапазони ваг вибрано шляхом поділу різниці між максимальною та мінімальною вагою елементів на рівні частини. Встановлено, що розподіл дає змогу однозначно вибирати в онтології 10% елементів з мінімальною вагою від їх загальної кількості.

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

Рис. 2. Зміна середньої ваги на рівнях графа залежно від частоти згадування зв'язків в онтології |

Рис. 3. Розподіл кількості елементів онтології по діапазонах ваг

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

Згідно з розробленим методом, семантичну відстань між двома вершинами та графа, якщо вони з’єднані дугою, визначено виразом: |

(4)

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

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

, | (5)

де n - кількість вершин графа.

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

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

Якщо побудовано суміщений граф, в якому С1 – центр ваги першого графа, а С2 – другого, то визначається мінімальна відстань d12 між цими центрами:

. | (6)

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

У третьому розділі на основі вибраних та обґрунтованих критеріїв оптимальності онтології МПС розроблено метод оптимізації її структури та змісту.

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

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

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

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

1) знання подаються в логічній формі;

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

3) застосовується метод резолюцій для виявлення суперечностей;

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

Достовірність джерела твердження означено як імовірність отримання від нього істинного твердження Dn = P(s=1). Для незнайомого джерела апріорна досто-вірність встановлюється рівною 0,5. Апостеріорну достовірність під час поступо-вої перевірки істинності s наданих n-м джерелом тверджень визначають за формулою:

, | (7)

де s – істинність твердження, що приймає значення 1, якщо твердження істинне, або 0 – у протилежному випадку, i – номер кроку підтвердження/за-перечен-ня істинності одного з тверджень n-го джерела.

Для розв’язання задачі оптимізації змісту онтології МПС необхідно на основі критеріїв швидкодії та повноти визначити оптимальну кількість понять такої онтології. Для заданих критеріїв цільова функція:

, | (8)

, . |

(9)

де – швидкодія, виражена як середній ексцентриситет вершин графа, що представляє онтологію; k – кількість рівнів у графі; G – відносна кількість понять в онтології, G K/N; K – кількість понять в онтології; N – кількість понять в словнику ПрО.

На основі аналізу лексичної бази даних WordNet досліджено статистику розподілу елементів за рівнями типової онтології Р(і). Встановлено, що за такого розподілу, означених критеріїв оптимальності та словника, який містить 100000 понять, мінімум цільової функції (8) відповідає оптимальній кількості 31000 понять в адаптивній онтології МПС (рис. 4).

Рис. 4. Цільова функція пошуку оптимальної кількості понять онтології МПС

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

Нехай онтологія складаєть-ся з n елементів загальним об’ємом пам’яті М. У ролі „рюкзака” виступа-є певна задана частка об’єму N = /10M, до якої слід віднести найменш цінні елементи (поняття з мінімальною семантичною вагою та максимальним об’ємом) для по-даль-шого їх вилучення. Тоді необхідно максимізувати сумарний зиск:

таких елементів і, для яких та > , > , ,

де xi – поняття онтології, xi = , якщо поняття вносимо в “рюкзак” та 0 – у протилежному випадку; Wi – вага поняття; mi – об’єм пам’яті, який займає цей елемент.

Задача спрощується, якщо вважати, що об’єм робочої пам’яті, зайнятий i-м елементом, mi = m = const, що як правило відповідає умовам реалізації онтології МПС Показано, що сформульо-вану задачу можна розв’язати за допомогою жадібного алгоритму.

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

Четвертий розділ присвячено розробці автоматизованої МПС як однієї зі служб ВАРМ наукового працівника. Описано функціональну структуру ВАРМ, реалізованого за клієнт-серверною архітектурою засобами PHP, Java, MySQL.

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

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

Основними компонентами розробленої МПС (рис. 6) є:

· пошуковий агент, реалізований на базі Wget, який працює під управлінням ОС Linux і забезпечує видобування анотованих публікацій з мережі Інтернет;

· супровідна база даних під управлінням СУБД MySQL, в якій зберігається профілі користувачів, відповідні ПрО, запити користувачів, а також знайдені анотації;

· програмний пакет синтаксично-семантичного аналізу на базі Link Parser, який забезпечує побудову семантичних образів знайдених анотацій для їх подальшого порівняння та рангування, а також автоматичного поповнення онтології МПС;

· онтологія реалізована мовою OWL засобами Protйgй API, структура та зміст якої оптимізовані відповідно до інформаційних потреб користувачів;

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

Рис. 6. Архітектура автоматизованої МПС

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

, | (10)

де ? потужність множини дійсно релевантних документів, знайдених за відповідним методом (згідно оцінки експерта з даної ПрО); ? потужність множини усіх релевантних документів знайдених за відповідним методом, .

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

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

Загалом ефективність підхо-ду, який ґрунтується на використанні даних онтології МПС, налаштованої на ПрО користувача, визначена за параметром , в серед-ньому на 10…20% вища у порівнянні з іншими методами. Покращення досягається завдяки використанню апріор-ної інформації про ПрО користувача через зважування вершин (понять та зв’язків) концепту-альних графів взірцевої та досліджу-ваної анотацій під час виділення анотацій, зміст яких най-більше відповідає змісту анотації-взірця.

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

Основні результати та висновки

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

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

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

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

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

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

6. Експериментально перевірено ефективність застосування до задачі інформаційного пошуку розробленого методу оцінювання подібності текстових документів за змістом порівняно з відомими методами коефіцієнтів Дайса та Монтес-Гомеза, що не використовують даних з адаптивної онтології. Запропонований підхід на основі адаптованої до інформаційних потреб користувачів онтології дає змогу в середньому на 10...20% підвищити точність пошуку документів при його застосуванні в інтелектуальних автоматизованих МПС.

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

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

1. Досин Д. Г., Даревич Р. Р., Митроган М. М. Розробка портальної експертної системи для автоматизованого пошуку науково-технічної інформації в мережі Інтернет // Відбір та обробка інформації. – 2003. – Вип. 18(94) – С. 123-126.

2. Досин Д. Г., Даревич Р. Р. Побудова базової ланки онтології елемента мультиагентної системи // Научно-теоретический журнал „Искуственный интелект”, ІПШІ „Наука і освіта”. – 2003. – Вип. 3. – С. 436-444.

3. Досин Д. Г., Даревич Р. Р. Метод визначення подібності текстів представлених у вигляді зважених концептуальних графів // Відбір та обробка інформації. – 2004. – Вип. 21(97). – С. 106-110.

4. Модель представлення знань за допомогою об’єктів для побудови інтелектуальних систем підтримки прийняття рішень / В. В. Литвин, Д. Г. Досин, Р. Р. Даревич, Т. М. Пугач // Научно-теоретический журнал „Искуственный интелект”, ІПШІ „Наука і освіта”. – 2004. – Вип. 3. – С. 343-349.

5. Даревич Р. Р., Досин Д. Г., В. В. Литвин. Mетод автоматичного визначення інформаційної ваги понять в онтології бази знань // Відбір та обробка інформації. – 2005. – Вип. 22(98). – С. 105-111.

6. Даревич Р. Р., Марков А. Д., Студент О. З. Створення експертної системи прогнозування пошкоджень в енергетиці та нафтохімії на основі металографічного аналізу // Машинознавство. – 2005. – №2. – С. 48-53.

7. Даревич Р. Р. Підвищення ефективності інтелектуального аналізу тексту шляхом зважування понять в моделі онтології // Научно-теоретический журнал „Искуственный интелект”, ІПШІ „Наука і освіта”. – Вип. 3. – 2005. – С. 571-577.

8. Оцінка подібності текстових документів на основі визначення інформаційної ваги елементів бази знань / Р. Р. Даревич, Д. Г. Досин, В. В. Литвин, З. Т. Назарчук // Научно-теоретический журнал „Искуственный интелект”, ІПШІ „Наука і освіта”. –Вип. 3. – 2006. – С. 500-509.

9. Досин Д. Г., Даревич Р. Р., Литвин В. В. "Ноев ковчег" в информационном потопе // аrgc&argv: журнал для профессиональных програмистов. Прогаммирование. Информационные технологии. Стандарты. – 4 (55). – 2004. – С. 50-53.

10. Досин Д. Г., Даревич Р. Р., Митроган М. М. Розробка портальної експертної системи для автоматизованого пошуку науково-технічної інформації в мережі Інтернет // Информационные технологии в XXI веке: Сб. докл. и тезисов I-го Молодежного научно-практического форума, Днепропетровск, 23-24 апреля 2003г. - Д.: ИПК ИнКомЦентра УГХТУ. – 2003. – С. 86-87.

11. Даревич Р. Р. Розробка і впровадження технології побудови бази знань для систе-ми автоматичного пошуку інформації // Тези доп. V Міжнар. наук.-практ. конф. студентів, аспірантів та молодих вчених „Системний аналіз та інформаційні технології” – К.: НТУУ „КПІ”, 2003. – С. 150-151.

12. Даревич Р. Р., Досин Д. Г. Агентна система автоматичного опрацювання науково-технічної інформації на основі її інтелектуального аналізу // Матеріали 11-ої Міжнар. конф. по автоматичному управлінню „Автоматика-2004”. – К.: НУХТ, 2004. – т.4 – С. 35.

13. Dosyn D.Darevych R.Lytvyn V.Modelling of the intelligent text recognition agents based on dynamic ontology. // Тези доп. IV міжнар. конф. „Інтернет – Освіта – Наука - 2004”, Збірник матеріалів конференції. – Вінниця: УНІВЕРСУМ – Вінниця, 2004. – Т. 2. – С. 577-579.

14. Даревич Р. Р. Загальний алгоритм оптимізації структури автоматично гене-ро-ва--ної бази знань // Матеріали ХІХ відкритої наук.-техн. конф. моло-дих науковців і спеціалістів ФМІ НАН України, КМН-2005. – Львів, 2005. – С. 429-432.

15. Даревич Р. Р. Процедура оптимізації структури автоматично генерованої бази знань // Тези доп. IІІ Міжнар. наук.-практ. конф. „Математичне та програмне забезпечення інтелектуальних систем”. – Дніпропетровськ, 2005. – С. 46.

16. New knowledge evaluation using massage model of NLT document / D. Dosyn, R. Darevych, V. Lytvyn, U. Dalyk // Proceedings of the International Conference on Computer Science and Information Technologies (CSIT’2006). September 28-30, Ukraine, Lviv, 2006. – P. 118-119.

17. Даревич Р.Р., Досин Д.Г. Віртуальне автоматизоване робоче місце з інтелектуальною компонентою // Материалы Cедьмой ежегодной междунар. конф. “Эффективность реализации научного, ресурсного и промышленного потенциала в современных условиях”, 12–16 февраля 2007 г., п. Славское – К.: УИЦ "Наука. Техника. Технология", 2007. – С. 69-71.

Анотація

Даревич Р.Р. Автоматизована метапошукова система на основі адаптивної онтології. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 – “Автоматизовані системи управління та прогресивні інформаційні технології”. – Фізико-механічний інституті ім. Г.В. Карпенка НАН України, 2007.

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