Київський національний університет

імені Тараса Шевченка

Шевченко Олександр Володимирович

УДК 681.3.06

Методи добування тематичної інформації

з глобальної мережі на основі агентного підходу

01.05.03 – математичне та програмне забезпечення
обчислювальних машин і систем

АВТОРЕФЕРАТ

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

кандидата фізико-математичних наук

Київ – 2007

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

Робота виконана на кафедрі інформаційних систем факультету кібернетики Київського національного університету імені Тараса Шевченка

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

Анісімов Анатолій Васильович,

Київський національний університет імені Тараса Шевченка, завідувач кафедри

Офіційні опоненти: доктор фізико-математичних наук, професор
Лавріщева Катерина Михайлівна,

Інститут програмних систем НАН України, завідувачка відділом, м. Київ

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

Гороховський Семен Самуїлович,

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

Провідна установа: Інститут кібернетики ім. В.М.Глушкова НАН України,
м. Київ, відділ рекурсивних обчислювальних машин.

Захист дисертації відбудеться “ 6 “ квітня 2007 року о “14“ годині на засіданні спеціалізованої вченої ради Д 26.001.09 Київського національного університету імені Тараса Шевченка (03127, м. Київ, пр. Глушкова, 2, корп. 6, ф-т кібернетики, ауд. 40.Тел. 521-33-66. Факс 259-70-44. E-mail: rada1@unicyb.kiev.ua)

З дисертацією можна ознайомитися у Науковій бібліотеці Київського національного університету імені Тараса Шевченка (01033, м. Київ, вул. Володимирська, )

Автореферат розісланий “ 6 “ березня 2007 року.

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

доктор фізико-математичних наук, професор Д.Я.Хусаінов

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

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

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

Універсальні пошукові системи (ПС) мають попередників з обмеженими можливостями, що були орієнтовані на локальні сховища даних, але зараз вони реалізують нові можливості як стосовно сховищ, так і методів доступу до них через Інтернет. Бази даних таких систем містять HTML-документи та їх індекси (наприклад, системи AltaGoogle, Yandex та інші).

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

Пошук певної інформації в Інтернет для багатьох людей поки що виконується 1-2 рази, або епізодично і користувача зовсім не цікавить, або мало цікавить як змінилася інформація, що була одержана раніше. “Разовий” пошук у мережі автоматизують відомі пошукові системи, які базуються на класичних методах розпізнавання, лінгвістичних методах і пошуку ключових слів. Централізовані ПС включають в індекс усі доступні тематичні документи, хоча тематика індексованих документів змінюється дуже швидко і у широких межах. Крім того, система відповідно до заданих у запиті ключових слів подає велику кількість не релевантних документів і користувачу необхідно витрачати зайвий час для їх аналізу.

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

Математичні моделі інформаційного пошуку поділяються на 3 види: теоретико-множинні (булеві, нечіткі множини), алгебраїчні (векторні, латентно-семантичні, нейромережеві) та імовірнісні. Критика занадто “жорсткої” булевої моделі Joyce та Needham, а згодом Gerard Salton та Karen Sparck-Jones призвела до появи векторної моделі. Пізніше Robertson й Sparck-Jones математично обґрунтували та реалізували імовірнісну модель. Вивчення та апробація цих моделей дозволили розробити стратегію ефективного пошуку тематичної інформації у глобальної мережі, базисом якої є метод семантичного індексування, розвинутий у напрямку поліпшення якості і точності інформації, що здобувається користувачами.

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

Проблематику агентних систем досліджували: П.І.Андон, А.В.Анісімов, К.М.Лавріщева, О.А.Летичевський, С.С.Гороховський, Н.М.Майкевич, О.О.Морозов, Ю.В.Обухов, використання цих систем у навчальному процесі – М.М.Глибовець, в економіці - Philip Agre, Arie Segev, Carrie Beam, для захисту інформації - А.В.Зубенко та інші.

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

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

Зв’язок з науковими програмами, планами, темами. Дослідження виконувалися згідно плану науково-дослідних робіт Київського національного університету імені Тараса Шевченка за темою „Розробка системи інтелектуалізації інформаційних технологій та дистанційного навчання (ДР № 0101U002170) на кафедрі інформаційних систем факультету кібернетики Київського національного університету імені Тараса Шевченка.

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

Для досягнення поставленої мети у дисертації розв’язуються наступні задачі:

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

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

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

розробка алгоритму брокера, що обслуговує та маршрутизує запити і оброблює їх черги;

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

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

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

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

Наукова новизна отриманих результатів полягає у розробці:

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

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

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

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

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

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

Особистий внесок автора. Всі результати дисертаційної роботи одержані автором самостійно. В дослідженнях, описаних у тезах [6], студенту Замковому О.В. належить адміністрування мережного експерименту.

Апробація результатів дисертації. Результати досліджень доповідались на міжнародних наукових конференціях та семінарах:

одинадцятій міжнародній науковій конференції імені академіка М.Кравчука, 18-20 травня 2006 р., Київ;

п’ятій міжнародній науково-практичній конференції з програмування УкрПРОГ’2006, 23-25 травня 2006 р., Київ;

третій міжнародній школі-семінарі “Теорія прийняття рішень”, 2-7 жовтня 2006 р., Ужгород;

а також на наукових семінарах Київського національного університету імені Тараса Шевченка, Інституту кібернетики НАН України, Інституту програмних систем НАН України, Національного університету “Києво-Могилянська Академія”.

Публікації. За результатами дисертаційної роботи опубліковано 4 статті у фахових виданнях наукових праць, затверджених ВАК України та 2 тез конференцій.

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

Основний зміст

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

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

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

Проаналізовані основні базові моделі індексування – методи індексування тематичної інформації, до яких відносяться

булеві,

векторного простору,

імовірнісні,

латентного (скритого) семантичного індексування,

імовірнісного латентного семантичного індексування – ІЛСІ.

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

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

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

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

Агент – це програма, яка повинна ефективно, надійно і коректно виконувати запити користувачів у мережі; може мати різні призначення і спеціалізації: агент користувача, інформаційний агент, агент-посередник, агент постачальник інформації, тощо.

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

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

пошук інформації відповідно запиту;

можливість автономного виконання частин завдань у запиті;

фільтрацію потоків інформації;

можливість доставки отриманої інформації безпосередньо на комп’ютер користувача тощо.

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

Агент-посередник - забезпечує сервісні функції шляхом взаємодії з агентом користувачем і агентами постачальниками інформації та забезпечує доступ до БД або баз знань при формуванні відповіді на запит.

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

Різні типи агентів мають такі загальні властивості:

самостійно працюють і контролюють свої дії;

співпрацюють з іншими агентами;

змінюють поведінку в залежності від стану зовнішнього середовища;

мають можливість переходу до іншої платформи;

видають достовірну інформацію тощо.

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

Базовими складовими цих систем є:

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

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

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

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

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

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

Прикладами децентралізованих ПС є:

розроблена компанією Fast Search & Transfer система, яка діє як масштабована архітектура і має швидкий алгоритм індексування тематичних масивів на серверах. Індекс включає до 80 млн. сторінок, кількість яких зростає до 200 млн.

Слід також відзначити промислову систему Convera RetrievalWare, продукт компанії Convera Technologies Corp.

Також існує декілька створених у Росії децентралізованих ПС серед яких найбільш цікавою і функціональною є пошукова машина Russian Context Server від компанії “Гарант-Парк-Интернет”. Russian Context дозволяє враховувати морфологію російської та англійської мов, використовує SQL-подібну мову запитів з можливостями обмежень на контекст та атрибути документів.

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

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

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

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

Виходячи з запропонованого, алгоритм аналізу документів інформаційним агентом починається з ядра множини НТМL, завантаження тих документів, на які посилаються документи з цього ядра, включення в індекс інформації про документи, що проходили через фільтр на основі аналізу ядра. Основні компоненти підтримки інформаційного агенту наведені на рис.1.

Рис. 1. Архітектура інформаційного агента

Аналізатор ядра індексу готує інформацію для генерації тематичних фільтрів, яка складається з обчислених ваг усіх термів з Т(К(D)) ядра індексу К(D). Агент визначає сховані фактори (теми) у колекції документів D і за допомогою функції tfвизначає число входжень терму t у документ d, чим забезпечується ефективне обчислення ваг термів, необхідних для вирішення задачі аналізу ядра індексу.

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

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

Завантаження документів з мережі Інтернет виконується за допомогою повідомлення URL і стандартної утиліти wget системи Linux. Документи заносяться до спеціальної керованої черги.

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

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

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

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

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

Означення. Під графом запитів будемо розуміти неорієнтований граф G вершинами якого є множина усіх термів V, що зустрічаються в архіві запитів, і Е – множина ребер. Дві вершини графу G з термами t1, t2 з'єднані ребром (t1, t2) Е, якщо ці два терми зустрічаються разом хоча б в одному запиті користувача.

Введемо такі позначення: Told - множина термів зі словника архіву запитів, що входять у словник ядра індексу, Tnew– множина термів зі словника архіву запитів, що не входять у словник ядра індексу, W(t) – вага терму t Told , Х(t) - невідома вага терму t Тnew, NG(t)={t' (t, t') E} – множина термів з T(Q), яким у графі G відповідають вершини, суміжні з вершиною, відповідною терму t.

Wnew(t) _вага термів t з множини Тпеw , обчислюються шляхом розв’язання наступної системи лінійних рівнянь: |

(1)

Питання розв'язання цієї системи розглядається, як для системи, що має вигляд X = B X + C.

Теорема. Метод простої ітерації

X(i+1) = B X (i)+ C, i = 0,1,2,……

збігається до розв’язку системи (1) при будь-якому початковому наближенні X0, якщо для кожного терму t Тnеw, є запит q Q, у який входить терм t і хоча б один t' Told .

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

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

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

За допомогою індексів ядра виконується:

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

порівняння даних із запиту з описом тематичного документа з архіву, а саме з посиланнями, ключовими словами, вагами термів документів та ін.;

надання даних про всі доступні тематичні документи та відомості про останні зміни проіндексованих документів в ядрі індексів;

здобування релевантного документа та інших даних, ранжирування результатів і формування відповіді.

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

Процес обслуговування запитів складається з таких етапів:

Етап 1. Реєстрація агентом користувача, що звертається до мережі, у спеціальній таблиці;

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

Етап 3. Трансформація інформаційним агентом запиту у форму, прийняту іншим агентом процесу його обслуговування (брокером, менеджером та ін.).

Етап 4. Розгляд та просування запиту за маршрутом, визначеним агентом-брокером, та постановка запиту в чергу.

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

Етап 6. Фільтрація агентом нових документів для їх завантаження у відповідні архіви.

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

Етап 8. Розгляд користувачем отриманого результату щодо запиту та витрат на його виконання.

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

.

Рис. 2. Загальна структура системи обслуговування запитів

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

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

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

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

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

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

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

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

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

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

Для формального опису взаємодії агентів в роботі пропонується використовувати механізми розподіленої мови дій DAL (Distributed Action Language), яка розроблена А.А.Летичевським, і базується на понятті компонента розподіленої дії (Distributed Action Component - dac).

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

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

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

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

Інтерпретація отриманого контенту (скажімо розбиття сторінки на колекцію слів, наприклад на сторінці міститься вислів “file not found”, отримуємо впорядковану колекцію (“file”, “not”, “found”)).

Фільтрація інформації, яка не є корисною для ОШІ (як то html-теги, службові символи тощо).

Розроблений брокер може співпрацювати із ОШІ за наступними схемами.

Схема 1. Один брокер, один ОШІ і брокеру передається вся колекція посилань. За цією схемою ОШІ запускає брокер, передає усю колекцію посилань та очікує від нього відповіді. Після обробки посилань брокер повертає результати до ОШІ.

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

Схема 3. Багато брокерів, один ОШІ, i–му брокеру передається колекція посилань розміру ni, n1+…+nk = n, i = 1,…,k, k<n. За цією схемою ОШІ запускає k<n брокерів для k підмножин наявної колекції посилань та очікує від кожного брокера відповіді асинхронно. При цьому і-му брокеру передається ni посилань. Після обробки заданої колекції посилань брокер повертає колекцію результатів розміру ni до ОШІ.

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

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

Результат, як було описано раніше повертається до ОШІ. Таким чином для реалізації першої схеми ОШІ метод веб-сервісу викликає 1 раз і передає до нього всю колекцію власних посилань розміру n. Для реалізації другої схеми ОШІ викликає n однакових методів веб-сервісу асинхронно у різних потоках приблизно в один і той самий час і передає у кожний метод одне посилання із власної колекції. Для реалізації останньої схеми ОШІ викликає k однакових методів веб-сервісу асинхронно у різних потоках приблизно в один і той самий час і передає у кожний метод підмножину колекції власних посилань розміру ni, n1+…+nk = n, i = 1,k, k<n.

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

Брокер працює із ОШІ по протоколу SOAP (версії 1.1 та 1.2) та HTTP.

ВИСНОВКИ

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

Основні результати дисертаційної роботи:

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

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

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

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

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

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

СПИСОК ПУБЛІКАЦІЙ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Шевченко О.В. Підходи до здобування тематичної інформації із мережі Інтернет // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки, 2006. – № 1. – С.235 – 239.

Шевченко О.В. Методи обслуговування запитів агентом-брокером // Матеріали п’ятої міжнародної науково-практичної конференції з програмування УкрПРОГ’2006, 23-25 трав., 2006 р., Україна, Київ // Проблеми програмування – 2006. – № 2-3. – С.150 – 155.

Шевченко О.В. Розробка архітектури агента-здобувача тематичної інформації // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки, 2006. – № 2. – С.253 – 260.

Шевченко О.В. Взаємодія агентів в мережі. Аналіз та методи її представлення // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки, 2006. – № 3. – С.291 – 295.

Шевченко О.В. Агентний підхід до добування тематичної інформації з глобальної мережі // Одинадцята міжнародна наукова конференція імені академіка М.Кравчука, 18-20 трав., 2006 р., Київ: Матеріали конф. – К.: ТОВ “Задруга”, 2006. – С. 954.

Замковий,О.В., Шевченко О.В. Використання агентної технології пошуку інформації для систем прийняття рішень. Праці ІІІ-ї міжнародної школи-семінару “Теорія прийняття рішень”, Ужгород, УжНУ, 2006.- С.54-55.

АНОТАЦІЯ

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

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.03  математичне та програмне забезпечення обчислювальних машин та систем. Київський національний університет імені Тараса Шевченко, Київ, 2007.

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

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

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

За допомогою технології .NET створено програмні прототипи та виконано експериментальне випробування запропонованих алгоритмів інформаційного агента та агента–брокера.

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

АННОТАЦИЯ

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

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.03 - математическое и программное обеспечение вычислительных машин и систем. Киевский национальный университет имени Тараса Шевченко, Киев, 2007.

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

Определены основные аспекты поиска информации в сети: релевантность документов в соответствии с запросом пользователя, критерии качества поиска – полнота и точность. Дан обзор современных поисковых систем, которые действуют в сети Интернет и построены на базовых математических моделях поиска и агентах. Определена классификация интеллектуальных агентов: агент пользователя, информационный агент, агент-посредник, агент-поставщик.

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

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

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

минимизация затрат на получение ссылок в ядре индекса документов;

получение оптимальной стоимости доставки ответа на запрос;

штрафные санкции за не релевантный документ;

доход от получения релевантного документа.

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

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

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