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



Ки1вська м!ська адм1н1страц1я 1нститут прикладнсЯ 1иформатияи

На правах рукопису

ЖОГОВ Георг1й ЕЗолодимирович

• ШЛТКВНИИ ШФОРМАЦШШ ПОШУК. ШДШ I РЕАЛ13АД1Я

05.13.17 - теоретичн1 основи 1нформаткки

Автореферат дисертацИ на здобуття наукового ступени кандидата ф1зико-математичних наук

Науковий кер1вник - старший науковий сп1вроб1тник

кандидат ф1зико-математичних наук ДРГЯНСЬНИЙ В.М.

Ки!в - 1994

Диеерташя е рукопие

Робота виконана в 1нститут1 нрикладно! шформатики Науковий кбр1вник кандидат ф1зико-математичних наук, старший нау-коьий с]пьро01тник Др1янський Володимир Михайлович 0ф1ц1йн1 опоненти:

1. Доктор ф1зико-математичнад наун, плен-ксресповдент АН Укра1ни, Ющанко Катерина Логв!н1вна

2. Кандидат ф1зико-математичних наук, старший науковий сп1вроб1т-ник, Иолум1енко Серг1Й Костянтинович

Пров 1 дна орган!зац1я г/->

___УШ (М.

Захист в1дбудеться "26" ъъг'О ¿?гФск 199_^' р. об '10 год. на зас1данн1 Спец1ал1зовано1 вчено! ради Л -/¿Ф.о-А 0<! в 1н— ститут1 прикпадноI 1нформатики (Шр1н) за адресом: 252004, м. Ки1в, вул. ЧервоноармШська, 23-6.

3-диеертаШею можна ознайомитися у 01бл1отец1 Институту нрикладно! 1нформатики.

Автореферат роз 1сланий "¿В" {/е^рс-и^ 199^ р.

! Биений секре<ар

0иец1ал1аовано1 вчено! ради Ыелент'еь Г.Б.

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

Акч'уальншть теми. В 1нформац1£Ших системах, ор!ентованих ¡а ефективну обробку великих об'ем1в текстограф1чно1 1нформацП:

¡1бЛ1йТ6ЧНИХ, НауК0Б0-Т6ХН1ЧНИХ, ЮрИДИЧНИХ, Оф1сНИХ и т.п.,. осо-

!ливе значения набувають можливост! аДаптацП пошукових механ1з-«1в до 1нформац1йних 1итербс1в конкретних абонент1в, тобто наяв-¡1сть засоб1в, як!чзабезц8ЧуютЬ| по-перще, початкове 1нформац1й-ш позицкшуьання користувача I створення його особи^того 1нфор-шшйного середовщца I, по-друге, Шдтримку Цього середовшда в штуальному стан1.

У в1домих пощунових схемах для р1шення ц!еI проблема в значн!й м1р! використовуються 1нтелектуалып зусилля абонент1в тошуково! системи. Ось чому створення нових пошукових моделей з элементами штучного ¡нтелекту, як! значно аменшують 1нтелекту-У)ьне навантажения абоненту, е актуальном.

Шль роботи - розробка схеми адаптивного щформацШюго по-иуку 1 визначедая' в н1й пропесш, як! дозволяють використания здаптащйних механ1зм!в; моделюеання них процес1в, розробка алгоритм^ функцшнування побудованих моделей 1 створення прототн-1у вишлпдно! 1нформац1йно1 системи.

■ Иаукова новина. Запропонована концепШя адаптивного 1нфор-иац!йного пошуку 1 схема 1нформац1йно1 технологи, яка базуеться на цШ концеицП. В рамках ц1е1 схеми иобудован! модел! локал!-зац! I' ШформацШна! потреби абонент1в 1 вивчеи! И властиваст1, запропонован! семантичш розширення■них моделей, розроблеш алгоритма 1х функшонування. Створено прототип системи адаптивного ¡.нформацШного пошуку 1 здШсщно цикл експеримент1в, як1 п1д-твердили правильтсть заиропоновано! концепцП.

Загацьна методика досл1джень. Для маделквання процес1в'ло-кал1зац11 ¡нформацЩкЯ потреби вид!ляються два рГвня опиоу: м1жсеансовий та внутршньосеансовий. Модел! м!жсеансового р!ьня побудован! з використанням алгебрз1чного п1дходу до теорП роз-п^знаванпя образ1в (по ЮЛ.Жураальову). Для внутр1шньосеансового моделювання використозуеться байесовський тдх1д у статистичшй теорП прийняття'ршень, а для побудови семантичних розширень -теор1я в!днсшей>.

П^^ТИУна Ц1НН1СТ1;- Реализатя концепц! 1 адаптивного пошуку

приводить до появи принципово нового класу 1нтелектуальних Ш-формацШних систем з "проворим" Штерфейсом' користувача, Викори-стаиня под!бних систем дозволяе по-новому подивитись на ц!лий ряд галузей використання !нформац!Йних технолог1й: перш за все це б!бл!ограф!чн1 ¿нформагийн! система, електронн! каталоги I шформацШЦ мережи, оск1льки в мека?с запропонованого Шдходу може бути зд!Ценено автоматичне виявлення !нформац1йних потрёб користурач1в I подальше автоматичне висНркове розповсюдження 1н-формацЦ в 1х иерсональн1 бази даних (БД), ;

Реалпзацш реаультатш дослпджеиь. Реализовано I дарев!ренс на експериментальнШ БД прототип"системи адаптивного !нформац!й-ного пошуку. Система була запроваджена в Експо-центр! "Наука" АН Укра1ни. Елементи Ше1 системи були використан1 при розробц! ек-спертно! системи скришнгу хворих вторинним- 1муцодефщитом I систем! обробки кореспонденц!1 ДКНТ Укра1ни, За ир<л роб1т "Настраивающиеся документальные 'системы; математические модели, алгоритмы, программное обеспечение" автор сшльно з Л.Г.Катерини-чем та 0.Я.Колтуном був удостоений у 1986 р. медал! АН Укра1ни з премГею для молодих вчених.

Апробац1я роботи. Матер|али дисертацП допов1 дались на се-М1нарах Науково! ради АН УкраНщ з проблеми "Юбернетика"; "Проблемы проектирования автоматизированных банков данных"; "Лингвистические проблемы проектирования информационных систем"; "Распознавание и оптимальное управление развитием систем" (Слав-ское, 1989 р.); на Республ!канськ!й науково-техшчнШ конферен-цП "Пути дальнейшего совершенстзования системы научно-технической информации и пропаганды в Украинской ССР в XII пятилетке" (Хмельницкий, 1986 р.); на Всесоюзному науково-техн!чному сем1нар1 "Мобильное программное обеспечение" (Калшш, 1988 р.); на 5 Всесоюзна конферешЩ по БД та знань (Льв1в, 1991 р.).

Публ1кац11. За результатами виконавдх досл!джень опубл1ко-ьано 11 роб 1т, одна колективна монограф!я ■(глави 6, 10).

Обсяг 1 структура рюботи. ДисертаЩя складаеться з вступу , трьох глав, заключения, списку л1тератури (63 найменування)' ! додатк1в. Дисрртаци! викладена .на 130 стор1нках, м1стить 4 ма-лыика та 2 таблиц!. Додатки на 31 сторшк^х.

• - 5 -ЗМ1СТ РОБОТИ

ДисертаШйна робота присвячена питаниям розробки! реал1за-ц11 схеми адаптивного 1нФормац1йного пошуку:

- моделюваннгс пронес1в локал!ззц11 1 ведения 1нформац1Пно1 потреби користувача, а також власне 1нформац1йного пошуку 1 оц!нки знайдено! 1нформац11;

- використанню для п!двищення адекватност! моделгсвэння 1н-формаШйно-пошукових пронес 1в семантичних залежностей (пзраднг-матичних в1дношеНь)- лексики БД;

- розробЩ прототипу 1нформац1йно1 системи адаптивного пошуку;

- анал!зу результат!в тестування прототипу оистеми на экспериментальна БД.

У вступ! обгрунтовуеться актуальн1сть вибрано! теми, нада-еться огляд 1снуючих пошукових схем. Автором пропонузться нова пошукова схема - схема адаптивного 1нформац!йного пошуку. Суть II полягае у сл!дуючому (див. мал. 1).

. Для початково! локал1зац11 информац1йно1 потреби абоненту надавться кластерне де;.зво, яке в1дображае тематите розпод!лен-ня БД. В процес! його перегляду абонент визначае деяку п1дмножи-ну кластер!в, як1 його зац1кавили. На баз1 Ц1е1 Iнформац11 автоматично формулюеться запит в , по якому орган!зовуеться 1терз-ц1йний пошук. Тобто, зо подаеться на вх1д пошукового мехаШзму <р, Результати пошуку <р(э1) (в початковий момент 1=0) прогляда-ються абонентом. Результати оц1нок <р(а .) подаються на вх1д про-цедури внутр1шньосеансово! локал1зац11 1нформац1йно1 потреби, результати роботи яко1 визначають подальшу роботу процедури автоматичного формулювання запиту з1+1. Новий запит знову подаеть-ся на вх1д пошукового механ!зму. 1тераЦ1Йний цикл зугошявться або системою, або користувзчем. Результати сп1лкування з систо- -мою 'залам'ятовуються для подальйого використання у процедур1 М1жсеансово1 локал!зац11 1нформац!йНо1 потреби, яка дозволяе, йо-перше, в1дсл!дкувати динам!ку зм1нювання 1нформац1йно1 потреби абонента в1д сеанса до сеансу 1, по-друге, впливати на роботу процедури внутр!шньосеансово1 локал1зац!1.

Процедура кластериза-Ц11 БД

ч.

Процедура локал1зац11 м1жсеансо-boÎ 1нфор~ мац!йно1 ■ потреби

Абонентй

Перегляд tp(Sj^)

Оц1нки релевантност!

ношуковии механ!зм <р

Процедура автоматичного формулювання запиту а.

Результат

пошуку <Ив±)

Процедура ранжування

Процедура локал1зац!1 внутр1шньосе-аноово! 1нфор-маЦ1йно1 потреби

............- 1нфорМац1йниЙ зв'язок

-»• - функц1ональний зв'язок

,,Малюнок 1. Схема адаптивного 1нформац1йного пошуку

У перш1й глав! описуються розроблен1 автором математич модел1 локал1зац11 1нформац1Йно1 потреби корйстувача. в схв адаптивного1.1нформац1йного пошуку. Дня вир1шення задач1 локал зацИ 1нформац1йно1 потреби на баз! схеМй адаптивного Пошу продонуеться ВИД1ЛИТИ два види 1Нформац1Йно1 потреби*- м1жсеа сову i внутр1шньосеансову, Локал1зац1я М1ксеансово1 1нфорМац1 но1 потреби спрямована на вйзначення динаШки зм1нювання 1нфо мац1йних lmepeciB користувачей i використовуеться для вир1шен задач1 класиф1кац11 абонент!в. Локал1эац}я внутр1шньосеансов 1нформац1йно1 потреби необх1дна для ефективно1 нав1гац11 абонё та по БД в межах одного сеансу сп1лкуванйя його з системою.

Вйзначення 1. М1жсеаНсовою 1нформац1Йною потребою буде називати Шдмножину кпастер!в класйф1кац1йно1 структура БД, я були визнан! абонентом пертинентними в процес! IÎ Перегляду.

Очевидно, що задачу локал1зац11 м1жсеансово1 1йформац1йн потреби можна розглядатй як класичну задачу розп!знавання, а с

по опису множили документ!в К = К, ® К2, про яку В1ДОМО, що :ументи з К, визнан! абонентом пертинентними, а документи з К2 юпертинентними, 1 по опису центра кластера йз <е 91 (31 - класи-:ац1йна структура БД) вшЛчити предиката йз € К, 1 йз € де I Яг в1дпов1дна класи пертинентних I непертинентних докумен-

Нехай = {^(51) - результат застосування розШзнаючого ап-и'тму (по типу вирахування оЩнок) И до I на баз! навчаючо1 1рки К; & - дискретний час вЦносно деяко1 Т04КИ в1дл1ку, й пов'язаний з номером сеансу зв'язку абонента з системою ,к, яшцо Тл-й сеанс прийняти за точку в1дл!ку, то в сеано1

+ к! в = к (к > 0)){ Щ0а2 - терм1нальш вершили структури эц,

.Йдено1 в к1нц! сеансу 9'абонента г; (О, Т*1 - деякий ц!лочис-

¡ий Штервал (Т* - деяка пост1йна, яка характеризуе час стаШ-

,рност1 1нформац1йно! потреби абонента а) I нехай кожн1й вер-

[1 а,, е 91 певним чином поставлено у в1дпов1дн!сть ц[лочисловий

1 т

шетр Т € £0,Т*1, причому V а,« ! Т = Т*. Для користу-

•■а, . 1 • ч | & а.

. т '

:а а наступним чином побудуемо множину А0°2:

1) при а = 1

2) при 9 = 2

3) при а >2

X,

А

б,г

щ, 0,

то = 0. т > 0;

=

К I а1

9,г **6-1 ,г'

- V »е 3,

\ = К I а* « хе & \ •

«е " {а! I е хе * V 0 3 а;( €

т 51 °

6-1,2'

V» шлях за. в а,.

. а, Д ^

, т

Визначения 2. Множину А° будемо називати множииою актив... 6,2

вершин.

т.

5м1стовно, Аеиг формуетье'я на баз! зостосування алгоритма Н

до >1 з урахуванням досв!ду, накодиченого за сеанс , При цьому

т т • т

в AfJ„ включаються ьсi верцшш з Щ ° „ i Ti вершиня.з Ай°,

« »2, ,р У—

Сщо не уьШшш ъ ( j, у жшх значения параметрiв Та О за

т 1

умоьою, що не iciiye шлях, з в Т1 вершини, KOTpi за цае

Т* ни розп1знаються Н як релевантна, вилучаються з множини

актнвних вершин.

■т

Бизначимо на множиШ ■ А0° л i н iйний порядок р так, щоб в першу чергу вшилити найб!лыи актуальш рершшщ (на баз1 значень Т ). а серед mix найб1льш пертинентн! (з використанням Н), як! становлять кластери щших р1вней 1врарх1чно1 структур«

• Тг Тп

Визначення 3. Структуру GT« z- <га « z,р> Оудемо цазивати глобальною 1нформаШйною структурою абонента г в ¡итервал1 часу [ Т , То+ T*J , а Т* - часом стаЩонариост1. .

Зафиссуемо деякий штервал часу [ Т,, Tgl с t Т , То+ Т*] , i пехай Т - нова точка в!дл!ку.

т т

Визначення 4. Структуру L 1 = <А„'_Ф , р> назвемо ло-к&льноы ¡нформаШйною структурою абонента а в fТ1, Т£], якщо

card Г П гаах (cardial^1 }) > 5, (1)

Ч = 1 т, ' = 1.....тг" Т1

де Ж - деяка парогова величина.

т

Визначення 4. Ядром структур« I,' назвемо множину , .

: ' L2'Z ......

Кег CI,*' ) = П •

1г,г е = 1,...-,т2- т1 0,2

т, .

Заувашення. V ьл Кег CL„ ) Т = Т*.

1 . . х£. 2 ■ , а4

Визначення б. •

т т т .

1. Якщо.. V в €.11, т'] : Ав-1,^'п Ае?з Ae?z' то' : ОУДвмо ьважати, що абонент 2 мае пост1йну 1нформац}йну потребу. Клао таких абонент 1 в поэначимо О. > г

2. якщо' У t t fO, Г ), s A V^t^At?.^ » <2> то будемо ьважати, що 1нформа!ийна потреба абонента обмежь^а^дв-нккм пост Шним колам Штересш. Клас таких абонент 1в пазначимо

через С2.

3. Якшо не виконуеться (2), то Оудемо вваж-зти, що коло иь терес!в абонента г не мае ф!ксованих границь в заланому ¡нтерва-стац!онарност1. Клас таких абонент!в позначимо С3.

Виявимо сп1вв1дношення м!ж глобальною 1 локальною структурами для р!зних клас!в абонент!в.

т. т

Теорема 2. Для г е С, : Ьт 0Т? ^ з точШстю до р.

т_+ т* т

.Теорема 3. Для г ? С2 : ^ = , з точшстю до р.

Результат, отриманий в теорем! 3, дозволяв для абонента 3 ? С2 не вести з момента То+ Т* на протяз! кванту Т* його гло-0альну 1нформац1йну структуру, що значно зменьшуе к1льк!сть об-?|ислень.

Нехай, як 1 ран!ше, 2 е Сг; $ - деякий пор1г. Розглянемо

т т т +1 т +т* посл1довн1сть = (51,°,, .....) .

Вйзиачёння 6.' 1нформаЩйна потреба абонента ?, мае марк!в-

т т +е

ський характер, яйцо V 9е(0,Т*1: 3 Ьт +1+е_г8: 3 Ьт°+е+г 2.

о о

Очевидно, що для абонента г з марк!вським характером 1Нфор-т

мац!йно! потреби О^,? г мае властив!сть: саг*{кег

--:----:--- > <5 &

т +9 г т +9 +1

г ( т +» г i ta +1 11

max | card ja^ card { ||

card {.iter [ц? 0 + 2 г]}

max ( card П

e = 1 .г.з1- 1 *

Г 1

Побудуемо Ймов1рШсНиЙ прост!р Mi Л. 2 , P >, ДМ0 - '

элементарна под1я, яка полягае у тому, що перетин двох сус1дн!х т

елемент1в DT? г в пустим; (1 = 1....Т - 1) - елементарна по-

д!я, яка полягае у тому, що Перетин т1льки i + 1 безпосередньо

. т

сл!дуючих один за одним елемент!в нэ е пустим 1 задоволь-

няе (1); Pj^ - ймов1рн1сть поди Р : {íij^jPi] - Функц1я

така, що Р (£J = р±.

Teopetoa 4. Якщо z е С,, то Р = 1 • (3)

Визначення 7. Абонент г ? С. {"i" - слабо належить), якщо

Г Т л / г т Л

cardjKercV^j^/ max ^^|card(ae°z3j > í с$ е (0, .Из.

Теорема 5. рправедливо, що s t С, *=» z £ С,.

Теорема 6. Справедливо, що Рсбт+ = 1 ==* z С,. Нехай ? - ймов1рна величина така, що = 1+1 з ймов1р-

И1стю р±, а Мс - II математике спод1ваННя. Тод1:

якщо PceT*_tD = 1, то з урахуванням теореми G' г ? С( 1 для г на протяз! часу [ То+Т*,То+2Т*] достатНьо вести в кожний мот +т*+е

M9HT 0€Е1,Т*] Т1льки структуру Ьт°+т*+е+1tZJ

т т

якщо V [T,,TJstT ,Т +Т* ]: LJ = G_? , то zeC, 1 в цьому

12 о о X 2, z i , z i

випадку в 1нтервал1 часу [1 vr\T +2Т1 для обслуговування дос-

О О

татньо з0ер1гати т!лькиЬт? ; '

якщо zeCP (у в1дпов1дност1 з (2)), то з урахуванням теореми .

3 в ,1нтервал1 ГТо+Т ,То+2Т] необх1Дно збер1гати G^» z; кр1м

цього для z з марк1вським характером 1нформац1йно1 потреби в

. т +т*+е -1

кожний момент 0€t1,T ] необх1дно збер1гати т1льки Ьтс?+т*+е , а

* о '

для z з немарк!вським характером 1йформац1йно1 потреби в 1нтер-

т +т*+е

вали. [ То+Т* ,То+2Т] необх1дно збер!гатй V'+T'+e+Mc- , де

0 = 1,1+Mí....,1+kMc; k = t (T*-1}/MU . '

Випадок, коли zeC3< можна Штерпретувати як ситуац!ю з

марк!вським характером 1нформац1йно1 потреби при Т*-* Для т

таких z вести GT? не мае сенсу, а його положения в И в кожний

.т +т*+е -1

момент 9 сл1д визначати на баз! LT°+T*+e а •

о

Таким чином, при допущенi 1снування Н, вирiшено задачу ло-кал!зац11 м!жсеансово1 1нформац1йНо1 потреби абоНент1в. (Для побудови II можуть бути застосован1 алгоритм1Чн1 схеми, як1 базу-ються на алгебра!чному п1дход! до теорП розШзнавання образ1в

-li-

ra ЮД.Журавльову.)

Дал! огшсувться модель внутр1шньосеансово! 1нформац1йио1 готрбби, яка базуеться на гШотез1 зв'язност1 (ван Р1йсберген, '.Джоунс): якщо термШ х± добре розд1ляе класи релевантних I не-юлевантних документ!!*, то будь-який термш, що часто зустр1ча-¡ться разом з х1? тако» волод1е ц1ею властив1стю. Тому задача [олягае в знаходкенн1 множини терм1н!р UD, як1 розд1ляють доку-(енти БД на пертинентн! I непертинентн! (для конкретного абонен-:а). KpiM цього, так як терм!ни з UD використовуються у процеду-ii автоматичного формулювання запиту, то бажано в LTD' включати як •ерм1ни, що п1двищують точн!сть пошуку, так 1 термини, що змень-|ують пошуковий шум.

Визначення 8А. Внутр!ишьосеансовою 1нформац1йною' потребою юристувача UD+, яка забезпечуе п1двищення точносп пошуку, бу-[емо називати множину термш1в БД, ймов1рн1сть яких знаходитись I пертинвнтних документах вице деякого порогу J/+.

Визначення 8В. ВнутрШньосеансовою !нформац!йною потребою »ристувача UD", яка забезпечуе м1н1м1зац1ю пошукового шуму, Оу-(емо називати множину термШв БД, ймов1рн!сть яких знаходитись I непертинентних документах вице деякого порогу JT.

Не хай D^idj,} - множина документ ¡в. переглянутих абонентом и протяз1 первого циклу роботи процедура ранжування, i нехай ' 1=Сt^> - множина термiHiв, як1 знаходяться у Bcix цих докумен-•ах. Розглянемо тр!йку <tJ,aj,b;J>, де t^T,, а^ - шлыисть до-:умент1в, як1 в!дм1чен1 абонентом як пертинентш i в яких знахо-[иться термШ tj, bj - к!льк!сть документа в. БД, в яких знахо-¡иться термш tj.

На множив! Xt={<tj,ajfbj>} визначимо функцш I: ¡R (де ; - множина д1йсних чисел), яку <5удемо називати ]нФормативн1стю ■ёрм!на, Як цриклад може. виступати

UX )= log [(Pj- (1-q^) ■ (1-Pj)) 3,

a. + 0.5 . (b,- a.) + 0.5

[e p. = —2-q. ~ —3—J---, N - загалыш К1лыйсть

J N + 1 3 M + 1

юртинентних документ!в, M - к1льк1сть документ lb БД за втслю-*

енням N.

3м1сторно, шформативШсть в1дображае здатн1сть терм!ну юзд!ляти документа БД на пертинентн! ¡непертинентн!.

Видно, що задача локал1зап11 внутр1шньосеансово1 ¡нформа-

ц1йно! потреби може бути зведена до задач! вид!лення з множию терм1н!в, як1 входять в уже переглянут1 користувачем документа, таких терм1н!в, у яких 1нформативн1сть б!льше (для позитивни? значень 1нформативност!) або меньше (для негативних значень 1н-формативност1) деякого порогу.

Розглянемо задачу визначення Ш)+. Нехай Г+= (Г^) - множина р1зних позитивних значень 1нформативност1 терм1н!в Т,. ПобудуеМс

^ I Л ^ I

ймов!рн1сний пр'ост!р <{е1},2 1 ,Р>, де ц (1=1,...,сагс1(Г )) -елементарна под!я, яка полягае у тому, що 1нформативн1сть.терм1-на прийме значения Г*; р^ - ймов!рн!сть подИ е1; Р: {е1)=»{р^) -функц1я така, що Р(«1) = РА-

Нехай £ - випадкова величина така, що ^ (е1) = Г^ з ймов1р-н1стю р±, а Мс - И математичне спод!вання.

Тод1 з вид1Лимо Шдмножину терм1н1в таку, що для будь-якого ^е 1нформативн1сть Г^ терм!ну ^ б1льша або до-•р!внюв М{. 3 ^ вид!лимо п1дмножину яка в1дпов!дае . По-будована таким чином (якщо покласти М*= М?} якраз J е внутр!-шньосеансовою 1нформац1йною потребою корйстувача, яка забезпечуе п!двищення точност! 1нформац1йного пошуку перьд другим циклом роботи процедури ранжування.

Для 1-о1 (1 > 2) пошуково1 транзакц!ГТ1 будуеться наступ-ним чином: Т±= ит^), де Т(С1) .- множина терм1н!й документе Б±, як! О у ли переглянут1 користувачем за час 1-о1 трай-закц11. Для Т1.будуеться в!дпов!дна 1й множина ЗГ*, яка в свою чергу е внутр1шньосеансовою 1нформац1йною потребою корйстувача, що забезпечуе п1двищення точност! 1Нформац1йиого пошуку перед наступною пошуковою транзакц!ею.

ймов!рн!сть р± вйпадково1 под!! е1 будемо в1дновлювати таким чином, щоб б1льш1 значения !нформативност! мали 01л>шу ймо-в!рн!сть. Тод! р4 1 Мс можна обчислюватй за формулами:

схем1 адаптивного 1нформац!Йного пошуку.

Для визначення ШГ сл!д ураховувати термГни з негативными

Множина може бути вйкористана для п!двйщення точност! пошуку процедурою формування запиту на (1+1)-ому цикл! роботи у

значениями !нформйтивност!, У цьому випадку 1х можна було б ви-користовувати в запитах з! зв'язкою "не". Для здобуття таких TepMiHlB, аналог1чно будуеться множина . яка м1стить тер-м!ни tj, у яких значения !нформативност1 негативне 1 меньше де С, ~ випадкова.величина, визначена на множин! р1зних негатив-них значень ¡нформативностей.

В залежност! в!д того, до якого класу буде в1днесено конкретного користувача, застосовуються наступт дП:

1. Для користубач!в з пост!йною 1нформац1йною потребою тер-м!нолог1чн1 словники не зм1нюються i використовуються для автоматичного забезпечення режиму виб1ркового розповсюдження 1нфор-МацП.

2. Для користувач1в, !нформац!йна потреба у яких зм1нюеться в межах деякого пост!йного кола !нтерес!в, процедура локад1зац!1 внутр1шньосеансово1 !нформаЩйно! . потреби пост^йно провалить "раф^ування" терм i нолог Иного словника перед кожною новою пошу-ковою транзакцию.

'3. Для користувач!в, у яких !нформац!йна потреба пост1йно зм!нюеться, терминологии! словники не збер1гаються 1 так1 або-ненти повинн! переглядати кластерне дерево (для початкового по-зиШонування в БД) перед черговим сеансом зв'язку з системою.

Друга глава присвячена опису семантично1 модел! та II вико-рйстанню у cxéMi адаптивного 1нформац1йного пошуку. Ключов1 мо-менти пропонованоГ модел1 полягають у наступному.

Нехай X - (х±) - множина терм1н1в* як1 позначають поняття Р = tp1) вИх1дно1 предметно1 галуз!, а о- множина парадигматич-них в1дношень на множин! Р (вс1 парадигматичн! в!Дношення s толе рантними або транзитйвно-антисиметрйчними).

Ё1дношення ш € п !ндукуе в!дношення ш на множин! X: V Р*. PjC Р: p4G X±u> ху

Транзитивне в!дношення w e n e-(e-1 )-ор!ентоване, якщо V (x^.xj) € w : M^p М^ (M^-1^)* де Mlt'И^ - множина об'ект!в, як1 в!доов1дають поняттям 1 р^, р - деяке в1дношвння уточнения властивостей, дробления об'ект!в i т.п. Додамо до п в!днсшен-ня зворотнв до транзитивйих, |юзглянемо транзитивне замкнення п* множили n 1 введемо на п* асоц!ативну операц!» "*" добутку в^-нотень: Xjw,* 3 хд: x£utxs & XgW^j (ulfb»g€ п+). Эамика-

ючи п+ в!дносно "*", утворимо ун!версальну алгебру складних в!д-

ношень Unc= <nc,{«}>.

Представления ш i у виглац! К(«0 = u, *...* ш назвемо

I 3

каношчним, якщо V к = 1,...,з-1 : и * ш гз+.

к хк+1

Теорема 1. Для будь-якого w с пс К (и) едине. Добуток w(* шг назвемо добутком ш^и^-my, якщо K(ut ). = ы11*...* u1k 1 К(ы2) = ш21*,.,« <dgg. Визначення 1. Канонi4He представления називаеться направлении, якщо в ньому не зустр1чаються добутки ш^ы'^-типу.

Теорема 2. Якщо ы ■ добуток ulku2)-my i и1к?* u2J, то К(ш,* = K(Ul) * К(ш£). . '

Насл1док. В каношчному представлен! не можуть зустр1чатися

ДОбуТКИ ы ^-THIJiB.

Можлив1сть представления складних в|дношеиь у канон1чному вигляд1 дозволяв Еиконувати к!льк1сну оц1нку складних в!дношень на баз1 простих. • •

Використовуючи властивост! алгебри Uno, будуеться функц1я семантичного зв'язку i: а0-»- (0,1). При цьому враховуються як тополог1чн1 характеристики графа залежност! (довжина шляху м!ж. терминами, ширина основи под1лу, тщ Ыдношень в!дпов1дних компонент 1 в зв'язностП, так 1 деяний наб1р/семантичних передумов (характерних для задач кластеризацП БД, локал1зац11 1нформац1й-но! потреби, 1нформац1Иного пошуку), як! обумовлюють властивостх функцП f (симетричн1сть; значения Г для транзитиьних в!дношень 01льше 11 значенъ для тодарантних в1дношень; значения Г для в1д-н'ошень w, канон1чн1 представления яких не мостить толерантних Ыдношень, перевершують значена г для в1дношень, як1 м1стять толерантн1 Ыдношешя; значения 1 узгоджен! з порядком t, який задаеться щ, о+). '. '• , "

Задамо на о л1н1йний порядок г i перенумеруемо в1дношення у в1дпов!дност1 з цим порядком; Uj 1 < 3 . Тод! для складного в1дношення ы, з урахуванням вигляду графа залежност! i вве-дених семантичних передумов, функция семантичного зв'язку мае

вигляд: к

m , п г п (&-, V Р 1

sv...v«>-riM гк Ы^г ¿>rj •

31 m . п 1 = 1 1 к=1 . к!- к=1.1 к-1 s=1 si

до В. - параметр, який в1дпов1дае транзитивному.в1дношенню ы, ; к

V

V

- параметр, який в!дпов1дае толерантному в!дношенню ы. ; р -

П

цовжина шляху 1к-о1 транзитивно1 компоненти складного в!дношен-яя; к,- к!льк1сть ланок толерантного в1дношення «> , як! входять

у шлях, що з'еднуе терм!ни х 1 у; п - к!льк1сть транзитивних з!дношень в К(ы); гп - к!льК1сть толерантних в!дношень в в!дносний коеф1ц1ент уточнения, який е функц1ею в1д

эснови подолу; параметри В1 1 А^ задовольняють умовам

В13 V 0< ч<кч / 1: V \ 1 •

о 1 1 1+1 к к+1

Для транзитивних (простих 1 складних) в1дношень значения &ункц11 Г повинн! задовольняти умов!

Ь1' < <

1 (д) , . . . Ь) . с.

т с 1 "

х тат * якшо 1 = N. де ^ € { 1,...,п1 таке;

" що V к = ОТТьЗ = 1.+ к; у 1ншому випадку; 3*к 3

, якщо 1н= И;

' , у ;ншому випадку; п п ^

* - к!льк!сть транзитивних в1дношень; 1о= М+1; И I ^ о.

Для транзитивно-толерантних в1дношень, як1 м!стять т!льки то одному простому толерантному в!дношенню, значения функцИ Г ювинно задовольняти умов! (к =1,2):

, ш .

■1 к г 11

,) "''К)

Теорема 3. Для того, щоб 0 <. I < 1, достатньо

В±/Вл 4 \ + 47$ах ], 1 > ;} ; 0 < Ак < 1;

19 7 та* = шах(7 )>тах{гпах{г,. 5), г.,,- довжина к-го шляху в 1-1Й

21 Я Я к 1 1К

компонент! зв'язност1, - ширина основи под!лу, М - клас осно-

зи под!лу.

• Теорема 4. Рекурентн! сп!вв!дношення

Вн-1 > ?ятаХЛ/Ь 5 В1 > ТйтаХ'В1+, V* ! не 0 < Ь < 1, в достатн!ми для виконання (1).

шах Г "V "V-

шах г ■V ••ы1 '"и п

П)1П г 1п-1

гп1п г V п-1

1

к

М^.-Ы'""'1*!- 121

N-i

Насл1док 1. Зйачення параметров Blt 1=ТТП, можна обчислюва-

, max У ^<

ти за формулою В1=[7?1 / bj Насл1док 2. Умови

W А1>Ам; vt1-^'^—)/[(7Slmax+1)-c2N"'1)=L, А,<А^.Ь! де i<J, М - к!льк!сть толерантних в!дношёнь в п, с=7щах/Ь, е до-стат^ми для виконання (2)..

Насл1док 3. Л1н1йний порядок, 1ндукований по Г на п при-родним порядком на (0,1), сп!впадае з t.

Побудуемо скалярно-семантичну 1 семантичну функцП кбрреля-ц!1 документ1в dlt d^.

1. Скалярно-семантична функц!я корреляцП документ1в f* ви-

бираеться у'вигляд! 1* 'SjY~' 4)t(d;()J, де функц1я i|>t визнача-

|еться наступним чином (t - терм!н):

1) V t: 4>t{d1).q>t(d J = 1 —. q»t(d^) = ^(dp;

2) V t: cp+(d.)-v.td.) = 0 — 4>.(d.) = max £ f (t.r) )

' 1 3 . . r€ds! 'Mffi0

i 4>tf) = 1, якщо.t i dj, i <pt(d1). = 0 - у протилекному випад-ку.

2.- Скалярно-семантична функц!я f* дозволяв оц1нити лише

найб!льш суттев! семантйчн1 зв'язки м!ж терм!нами пор1внюваних

документ1в. Для врахування вс!х семантйчних зв'зк!в визначаються

поняття семантично1 сйли терм!ну к у деяк1й множин! терм.1н1в

К = {.t. ,...,ti ) 1 узагальнююче його поняття семантично1 сили 1 в

множили терм!н1в К, у деяк1Й множин! терм!н!в к2 " рк к *

Pi.R= z • тг 3 • € V V-

6 т±Пк д ■ . . J

причому якщо !снуе дек!лька ш € t.u t. , то для визначення

1 гз

f вибираеться в1дношення, яке дае найб!льшу силу зв'язку, тоб-

то 1(1,1:) = „шах { f~(l,l,)); •' Sen010 1

tl€ к,

Тод! семантичну функц!ю Г** корреляцП документ!в, . яка вра-

ховуе вс1 взаемозв'язки дослижуемих документов, можна визначити

наступним чшюм; í (d1,dJ) =. pd d //mln(p|1

BiflMjTHMO, що функцП Г* i узагальнюють "'корреляции! функцП, у яких враховуе'гься т!льки синон!м!я.

■ Трвтя глава присьячена опису реал1зованого автором ррограм-ного прототипу системи адаптивного шформац1 Иного пошуку та ана-л!зу проведених експеримент!в. Даний прототип реал1зовано в ото-ченн! IPÍC, ycl програмШ компонент!! написан! на мов! C!. Для роботи системи необх!днй мати персональний комп'ютер! cyulcmñ з IBM РС/АТ у стандартна конф1гурац11, та операц!йну систему MS DOS версИ 3.0 та вище. Для експеримент!в використовувалась БД в галуз! обчислювально! техн!ки 1 програмного забазпечення (300 цокумент1в). При реал!зацН системи велика увага прид1лялася !н~ терфейсу користувача, який був зведений до того, що в!д абонента вимагалося лише здШснювати оц!нку пред'явлених йому системою документíb. Вся решта роботи по визначенню 1нформац!йно1 потре-1и, формулюванню запиту, зд!йсненню пощукових 1терац1й, упоряд-куванню результат i в пошуку перед переглядом з урахуванням !нфор-лаЩйних !нтерес!в користувача зд!йснювалась автоматично самою системою. Для кожного абонента система створюе i веде його пер-зональну в!ртуальну БД.

Експерименти, проведен1 на дан i й систем!, показали, що вона росить добре' адаптуеться до 1нформац1йно1 потреби користувача. ]ередн1й показник точности при майже 100 % повнот! становив б!ля 50 % (у звичайних пошукових системах- показник точност! не пере-1ершуе 20%), характер ощнок документ!в у пред'являемих системою гарц!ях мав.коливальний вигляд, тобто;погано .-. краще ;-■'добре -югано - краще - добре,-, ... Причому перех!д до слхдуючого nepi-)ду означав, що система вже шчерпала, розд1ляюч1 ..властивост! тйб1льш !нформатцвних терм1н!в i намагаеться. "зачепитися" : за лшу ,лексику, семантично <5лизьку до'вйбрано1 тематики.,,.',

У таблиц! приведено'рц!нки'документ íb, як i .давались:, у. кож-, пй порцП, пред'являемо!: системою,, та' Стоп-правила,. як i; впкорп-¡товувала система у.випадку адаптацП .11 .на шформацШп Литере--:и У галуз!. мережевогр забезпечення. • • ■

П!сля bcíx uiariB- "рафгнування"- словника користувача' вт mí-'-:тив,!24-:Тбрм1на. .як) погшетю. покривали мережеву терм!полог iи-

- ¡а -

БД (в1дм1тимо, що на початков!й стадП, п!сля проглядання кластерного дерева, словник м!стив 11 терм1Шв).

Портя Оц!нки документ!в Стоп-правило

йо а, ¿6 й7 й8

1 + + - - - - - переуцорядкувати

2 + - + + + + - + - переупорядкувати

3 + + + - + + - - - + переупорядкувати

4 + + + + + — + + продовжити

+ + + + + + — .' - — продовжити

6 - . — новий запит

1 - + новий запит

1 + + - новий запит

ф(83)=0 К1НЩЬ

"+" - документ в!дм!чений як релевантний, - документ в!дм!чений як нерелевантний. Таблица.

Основой виводи I результата, отриман! автором по тем! дисертацП, полягають у сл!дуючому;

14 Автором запропонована нова схема !нформац)йного цошуку -адаптивний !нформац!йний пошук,- яка б роавитком !терац!йних по-шукових схем,

2. Для реал1зацП ц!е! схеми автором запропонована модель локал!вац11 м1жоеансоьо1 1нформац}$но1 потреби абонента. Запро-понован! стратег!Глокал!зацП м1жсеансово! !нформац!йно1 потреби, вивчен! види Н м1нливост!, 8 ц!<?ю метою введен! цоняття глобально! 1 Локально! !нформац!йних структур, видЦено три класи абоненту ! знайдено умови в1днесення абонента до того чи 1ншого класу на п1дстав! сп!вв!дн0ш9нь' м1ж цими структурами.

3. Для локал!зац11 1нформац!йно1 потреби в межах одного сеансу зв'язку абонента а системою введено поняття внутр1шньосеан-сово! 1нформац!Йно1 пбтреби 1 запропонована ймов!рн!сний п!дх!д до побудови в1дпов1дних терм!нолог!чних словник!в.

4. Запропонована сеиантична модель 1нформац1йно-пошукрвих процес!в для задач клас.теризацИ БД, локал1зад!1 1нформац1йНо1 потреби коркстувача, пошуку 1 ранжування найдених Документ1в. Побудована всюди визначена функц!я сили зв'язку м1к двома терм!-нами, на баз! яко! побудован1 скалярно-семантична 1 семантична

функцП корреляцП документ 1в,

. 5. Для апробацП схеми адаптивного 1нформац!йного пошуку розроблено 1 реал1зовано прототип. система адаптивного пошуку. При реал1зац!1 системи велика увага прид1лялась 1нтерфейсу користувача, який був зведений до того, що в1д абонента вимагалось лише зд!йснювати оц!нку пред'явлених йому системою документ^. Вся решта роботи по визначеннй 1нформац1йно1 потреби, Формулю-ванн» запиту»' ЗД1ЙСН9ННЮ пошукових 1терац1й, упорядкуванню результат! в пошуку перед переглядом з урахуванням iнформацiйних 1нтерес1в користувача зд1йснювалась автоматично самою системою.

6. 3 метою перев!рки адекватност1 моделей була проведена сер1я експеримент!в.з використанням експериментально1 БД в галу-з! обчислювально1 техН1кй i програмування. Експерименти показали, що дана схема 1 використан1 автором для II реал1зац!1 модел! даютъ, по-перше, добр! показники повноти ! точност! !нформац!й-ного пошуку 1, по-друге, терм!нолог!чний словник користувача, який будувться системою, фактично покривае всю представшщьку (природньо, у статйстичному розум1нн1) терм!нолог1ю по вибран!й тем! в конкретн!й БД.

Основн! Еезультати дисертацП опубл!кован1 в роботах:

1. Дриянский В.М., Жогов Г.В. Модель локализации информационной потребности абонентов настраивающихся документальных информационно-поисковых систем//Кибернетика. -1986. - N 4.

С. 81-84. ;

2. Дриянский B.M«, Жогов Г.В. Система программных интерфейсов // Базы данных й знаний в автоматизированных региональных системах. - К. гНаукова думка, 1990. - С. 269 - 278.

3. Дриянский В.М., Жогов Г.В., Алешкина C.M« и др. Персональная электронная библиотека // Проблемы информатики (Научно практическая конф. о межд. участием). - Самара-Астрахань-Самара, 11 - 18 мая 1991. - С. 35 - 37.

4. Дриянский В.М., Жогов Г.В., Катеринич'Л.Г. Алгоритм принятия решений в моделях локализации входной информационной потребности "// Проблемы создания ретроспективных поисковых массивов в автомат. центрах НТИ. Тез. док. XV Всес. научн. сем. "Систем, исследов. ГАСНТИ" (г^Рига, 20 - 22 мая 1985) 4.1 - С. 134-135.

5. Дрияйский В.М., Йогов Г.В., Катеринич Л.Г. . Алгоритмы классификации в моделях локализации инф. потребности пользовате-

лей документальной информационно-поисковой системы // Математические методы в автоматизированных информационных системах и банках данных. - К.: ПК АН Украины, 1985. - 49 - 55.

6. Дриянский В.Ч., Жогов Г.В., Катеринич Л.Г. Концепция настраивающегося информационного поиска в АСИО но ВТ // Создание автоматизированных систем информационного обеспечения научных исследований. - К.: ПК АН Украины, 1986. - С. 27 -38.

7. Дриянский В.М., Жогов Г.В., Катеринич Л.Г. Математйчес-^ кие модели настраивающегося документального поиска//В кн. Автоматизация информ. поиска.- К.гНаукова думка,1990. - С. 121 - 181

8. Дриянский В.М., Жогов Г.В., Катеринич Л.Г. Нужен ли язык запросов в информационно-поисковых системах //• УСиМ. - 1991. -N 7. - С. 158 - 160.

9. Дриянский В.М., Жогов Г.В., Капустин В. А., Катеринич Л.Г. Информационно-поисковая система с открытой архитектурой // Проблемы информатики города: Сб. науч. тр. - К.: Наукова думка, 1990. - С. 218 - 228.

10. Дриянский В.М., Жогов. Г.В., Колтун А.Я. Количественные оценки парадигматических отношений и их использование в документальных ДОС // НТИ. Сер. 2. - 1985. - N 10. - С. 6 - 16.

' 11. Дриянский В.М., Жогов Г.В., Чалый И.А. Концепция операционной оболочки Для создания информационных технологий // Проблемы разработки и внедрения программного' обеспечения ЭВМ и систем. - К.: ИК АН Украины, 1988. - С. 24 - 30.

12. Дриянский В.М., Жогов Г.В., Чалый H.A. Мобильные инструментальные средства поддержки протоколов Коммуникации прикладных процессов//Программирование. - 1990. - N 6. - С. 103-108