Автоматизована метапошукова система на основі адаптивної онтології

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

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

УДК 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); підготовці для монографії „Застосування інформаційних технологій для координації наукових досліджень” розділу „Засоби реалізації інтелектуальних систем та їх застосування у матеріалознавстві”, де, зокрема, детально описано побудову онтології засобами (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. Повна вага W_jⁱ класу онтології дорівнює сумі власної ваги , ваги підкласів та ваги суміжних класів (класів, зв'язаних з даним класом не „is-a” зв'язком):

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

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

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

3. Під час встановлення зв'язку між поняттями k₁ та k₂ між відповідними вершинами графа онтології з'являється ребро, а до ваги суміжних класів Wn₁ додається вага Wс₂ і, навпаки, до Wn₂ додається вага нового, суміжного до нього, класу Wс₁:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нехай онтологія складається з n елементів загальним об'ємом пам'яті М. У ролі „рюкзака” виступає певна задана частка об'єму N = 1/10M, до якої слід віднести найменш цінні елементи (поняття з мінімальною семантичною вагою та максимальним об'ємом) для подальшого їх вилучення. Тоді необхідно максимізувати сумарний зиск: таких елементів і, для яких та > 0, > 0, , де x_i - поняття онтології, x_i = 1, якщо поняття вносимо в “рюкзак” та 0 - у протилежному випадку; W_i - вага поняття; m_i - об'єм пам'яті, який займає цей елемент.

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

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

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

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

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

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

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

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

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

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

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

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



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

За результатами десяти експериментів, наведеними на рис. 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. G., Darevych R. R., Lytvyn V. 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.

Дисертацію присвячено питанню розроблення методів автоматичної адаптації онтології інтелектуальної метапошукової системи до інформаційних потреб користувачів. Сформульовано основні підходи до підвищення ефективності функціонування такої системи, що полягають в оптимізації її онтології за визначеними критеріями. Обґрунтовано та сформовано множину критеріїв оптимальності структури та змісту онтології, які відображають вимоги до експлуатаційних характеристик та технічних можливостей реалізації інтелектуальних метапошукових систем, а саме: обмеження фізичного об'єму пам'яті, швидкодія, повнота онтології, її цілісність та збалансованість. На основі критеріїв швидкодії і повноти розроблено метод оптимізації змісту онтології адаптивної метапошукової системи, який полягає у періодичному її доповненні новими поняттями та зв'язками з вилученням тих елементів, семантичне значення яких для системи найменше. В методі враховано необхідність виявлення і усунення суперечності та надлишковості під час наповнення онтології, що забезпечує дотримання критерію її цілісності. Для оптимізації змісту онтології застосовано методи дискретної оптимізації, до розв'язання задачі нормалізації її структури ? теорію доведення теорем та теорію графів. Удосконалено метод визначення вагових коефіцієнтів понять та зв'язків між ними в онтології, який завдяки розробленим правилам їх розрахунку дозволяє автоматично змінювати семантичну вагу елементів онтології під час експлуатації метапошукової системи, що дає можливість ефективно застосовувати його для оптимізації онтології та порівняння текстових документів. Розроблено новий метод оцінювання подібності за змістом електронних текстових документів, який в середньому на 10…20% підвищує точність визначення подібності двох текстових документів порівняно з відомими методами. На основі побудованої імітаційної моделі генерування та оптимізації онтології досліджено процес адаптації інтелектуальної метапошукової системи до заданої предметної області. Показано, що через 40...50 циклів (наповнення-робота-оптимізація) онтологія налаштовується на задану предметну область і відображає інформаційні потреби користувача. Розроблено архітектуру інтелектуальної метапошукової системи як однієї з основних служб віртуального автоматизованого робочого місця наукового працівника.

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

Darevych R.R. Automated metasearch system based on adaptive ontology. ? Manuscript.

The thesis for nomination to a Philosophy Doctor scientific degree (Engineering) in specialty 05.13.06 ? “Automated management systems and advanced information technologies”. ? Karpenko Physico-Mechanical Institute of the NAS of Ukraine mechanics, 2007.

The thesis is devoted to question of development of methods of intelligent meta-search system ontology adaptation to users information needs. The basic approaches to increase such system efficiency which consist in the ontology optimization by the certain criteria are formulated. Methods of discrete optimization are applied for ontology content optimization and the theorem proving theory and the graph theory are applied for solving the problem of ontology structure normalization that allows to improve characteristics of such systems. The set of optimality criteria of structure and content of an ontology which reflects requirements to exploitation characteristics and technical possibilities of realization of intelligent meta-search systems is formed and proved, namely: restriction of a physical memory capacity, speed, ontology completeness, integrity and balancing. On a basis of completeness and speed criteria the method of an ontology content optimization of an adaptive meta-search system was elaborated. Method consist in it periodical complementing by a new concepts and/or relations with exclusion of elements, which semantic importance for the system is smallest. Necessity of detection and elimination of contradictions and redundancy was taken in account in the method. It provides an ontology integrity criteria maintenance. The method of evaluation of ontology concepts and relations weight coefficients was improved. This method enables to change automatically the semantic weight of ontology elements during system exploitation using developed rules of weight calculation. It gives a possibility to use this method effectively for ontology optimization and text documents comparison. The developed method of dynamic evaluation of semantic weight of meta-search system ontology elements is based on the chosen optimality criteria. It provides an effective selection of elements which must be excluded during optimization. The new method of text content similarity estimation is developed. It provides up to 10...20% increase of accuracy of text documents similarity estimation in comparison to known methods. The process of adaptation of an intelligent meta-search system to given knowledge domain has been investigated using the developed simulation model of dynamically generated adaptive ontology. It is shown that after 40-50 cycles (supplementation-working-optimization) the ontology is adjusted to the given knowledge domain and more correctly represents users informational needs. The architecture of an intelligent meta-search system - the main unit of the virtual workstation of researcher is developed.

Keywords: automated meta-search system, text mining, conceptual graph, adaptive ontology.



Даревич Р.Р. Автоматизированная метапоисковая система на основе адаптивной онтологии. - Рукопись.

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

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

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

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

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

Создан комплект программного обеспечения, позволяющий генерировать симуляционные модели онтологии, расчитывать весовые коэффициенты понятий и семантических связей между ними, а также динамически изменять их значение в процессе наполнения и оптимизации онтологии. Это дает возможность исследовать процес адаптации интеллектуальной метапоисковой системы к заданной предметной области. Экспериментально показано, что через 40…50 циклов (наполнение-работа-оптимизация) онтология настраивается на заданную предметную область и таким образом отражает информационные потребности пользователя интеллектуальной метапоисковой системы.

...