Голицына О.Л., Максимов Н.В. Информационные системы

Подождите немного. Документ загружается.

101

yLL=

\ - количество документов, содержащих термин T, но не

содержащих термин t;

zLL=

\ - количество документов, содержащих термин t, но не

содержащих T;

vL L L=∪

01 2

\( ) - количество документов, не содержащих ни од-

ного из терминов T и t.

xyzv L n++

Проблема оценки эффективности информационного поиска фор-

мально сходна с задачей сопоставления множеств документов и мно-

жеств терминов. Для измерения эффективности системы используются

разностные меры множеств истинно релевантных (с точки зрения ко-

нечного потребителя) L

и выданных (формально, с точки зрения систе-

мы, релевантных) L

документов.

Рассмотрим так называемые первичные координаты описания вы-

хода ИПС, представляющие соотношение выданных и не выданных

множеств документов (диаграмму Эйлера-Венна <L> и таблицу сопря-

женности <a,b,c,d>).

Диаграмма <L> представляет соотношение множеств L

– всего

информационного потока, L

– множества истинно релевантных доку-

ментов (т.е. документов, отвечающих информационной потребности

пользователя) и L

– множество документов, выданных системой в ответ

на поисковый запрос (рис.4.3). Соотношение этих множеств и количест-

венные оценки меры их близости могут характеризовать эффективность

поискового механизма системы.

Рис. 4.3. Диаграмма <L>

Таблица сопряженности <a,b,c,d> отображает количественное

соотношение выданных системой множеств релевантных (с точки зре-

ния потребителя) и нерелевантных документов и не выданных множеств

релевантных и нерелевантных документов (табл. 4.1).

Релевантные

Выданные

102

Таблица 4.1.

Таблица сопряженности выдачи и релевантности

Релевантные Нерелевантные

Выданные

(формально релевант-

ные)

a b

Не выданные

c d

Очевидна следующая взаимосвязь представленных координат:

- число выданных релевантных документов:

ax L L

== ∩

;

- oбщее число релевантных документов:

acx L+= =

;

- количество выданных документов:

abn L+==

;

- общее число документов в

000

: LndcbaL ==+++ ;

- число выданных нерелевантных документов:

bnx LL

=−= \

;

- число не выданных релевантных документов:

cx x LL

=−=

\ ;

- число не выданных документов:

cdn n L L+= −=

;

- число нерелевантных документов:

bd n x L L+= − =

00 0

;

- число не выданных нерелевантных документов:

dn x nx L L L

=−−−= ∪

00 0

() \( )

С приведенными первичными координатами связаны частные

критерии оценки:

полнота (доля выданных релевантных документов по сравнению

с их общим количеством в информационном массиве):

∩

; (4.1)

точность (доля релевантных документов среди выданных):

∩

; (4.2)

специфичность (доля не выданных документов по сравнению с

не выданными и выданными нерелевантными):

=−

−

∪

LL L

; (4.3)

103

- общность (или точность массива L

), характеризует качество

комплектования поискового массива (доля релевантных документов в

информационном массиве):

dcba

p ==

+++

. (4.4)

Каждая из переменных (4.1) - (4.4) изменяется в пределах от 0 до

1. Этот перечень может быть дополнен показателем относительного

объема выдачи:

+++

abcd

(4.5)

Значение показателей технической эффективности во многом за-

висит от характеристик поисковых механизмов – моделей и методов от-

бора документов, а также возможностей используемого лингвистическо-

го обеспечения.

4.3. Модели механизмов информационного поиска в

документальных БД

Модели поиска в диалоговой АИПС должны быть ориентированы

на то, что реальная информационная потребность не удовлетворяется

одним множеством документов, найденных по единственному запросу, а

требует проведения серии отдельных поисков и выделения нужных

фрагментов информации на каждой стадии развития запроса. Такие мо-

дели должны учитывать следующие факторы:

поисковые запросы являются не статичными, а развивающимися

(в том числе и с изменением представлений пользователя о предмете и

задачах поиска);

пользователь отбирает информацию итеративно, по частям, а не

всю сразу в ответ на единственный запрос;

пользователю доступны разнообразные поисковые методы,

включая не только поиск по дескрипторам поискового запроса, но и, на-

пример, поиск документов по сходству;

пользователь для работы с лексикой предметной области может

применять широкий круг вспомогательных средств – тезаурусы, отрас-

левые рубрикаторы, словари и т.п.

Отвечающие этим требованиям модели будут намного ближе к ре-

альному поведению человека, чем традиционная модель информацион-

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

запроса, и может лучше управлять проектированием эффективных ин-

терфейсов.

104

Для определения требований к поисковым механизмам рассмот-

рим АИПС как средство отыскания пользователем (субъектом поиска)

решения находящейся в сфере его основной деятельности задачи P

, ас-

социируемой с системой понятий C

, путем поиска документов, содер-

жащих описание искомого решения. В этом случае процесс непосредст-

венного решения задачи заменяется процессом поиска решения или ме-

тодов его построения, полученных и

опубликованных ранее. То есть, как

показано на рис. 4.4, для получения решения задачи P

, представляемой

системой понятий C

, необходимо найти множество документов D

, ис-

пользуя в качестве поисковых (характеристических) признаков множе-

ство терминов T

, представляющих понятия C

Рис. 4.4. Информационный поиск в процессе основной деятельности

Очевидно, что чем более структурирована и систематизирована

предметная область основной деятельности (и система понятий как ос-

нова структуризации – отображение C

<–>P

), чем более устойчива тер-

минологическая система (однозначность именования понятий и их ком-

позиций – отображение C

<–>T

), чем более «проработана» предметная

область (полнота представления результатов ОД в пространстве доку-

ментов – отображение D

<–>P

), тем более детерминированным должен

быть механизм отбора S, реализующий отображение T

<–>D

. При ис-

пользовании для индексирования нормализованной лексики (ключевых

слов, обеспечивающих однозначность именования понятий) поиск эф-

фективно реализуется на основе жесткой булевой логики.

«Нечеткость» приведенных отображений (конечно при требовании

обязательного нахождения решения задачи) означает, что неточность

любого из соответствий должна быть компенсирована увеличением пол-

ноты выдачи за счет уменьшения точности. Это может быть обеспечено

следующими путями: 1) обогащением выражения запроса, 2) использо-

ванием менее жесткого механизма отбора, 3) использованием много-

этапных итеративных процедур поиска, обеспечивающих последова-

Решение

задачи ОД

Поиск

документов

(с решением)

Основная деятельность

Ин

ма

ионная деятельность

105

тельное расширение терминологического и документального простран-

ства, например, по технологии обратной связи по релевантности. Обоб-

щенная схема итеративного процесса поиска приведена на рис. 4.5.

Рис. 4.5. Схема итеративного процесса поиска

Такая схема, обеспечивающая выполнение требования сопостави-

мости и оцениваемости результатов, включает в себя два типа обратной

связи: внешнюю, отражающую оценку пользователя (выделение истин-

но релевантных документов Zd – отображение D

<–>D

), а также внут-

реннюю, учитывающую статистические особенности использования

терминов в конкретной базе данных (выделение информативных для

данной предметной области терминов – процесс S

-1

, реализующий ото-

бражение D

<–>T

). Отметим, что на схеме приведен и другой тип

внешней обратной связи Zt, реализующий на уровне терминологии

предметной области выделение информативных терминов – процедуру

отображения T

<–>T

Результаты различных исследований, посвященных анализу мето-

дов и оценке эффективности поиска в интерактивных БД, позволяют

сделать следующие выводы:

стратегии, используемые при поиске информации, весьма раз-

нообразны, и их анализ не позволяет однозначно выделить наиболее оп-

тимальную;

Решение

задачи ОД

Поиск

Реформули-

рование S

-1

Поиск

106

- для повышения эффективности поиска поисковый аппарат

должен включать развитые возможности как собственно поиска (ис-

пользование контекстного расстояния, учет грамматических характери-

стик текстов и т. п.), так и отображения информации (форматы выдачи,

удобные средства листания и пр.);

полезно включение в состав лингвистического обеспечения ИС

не только традиционных тезаурусов и рубрикаторов, но и дополнитель-

ных структур, являющихся результатом статистической обработки сло-

варей БД.

Таким образом, для повышения эффективности поисковых про-

цессов ИПС должна обеспечивать различные поисковые стратегии, по-

зволяющие не только постоянно модифицировать исходный запрос, но и

получать результаты, основываясь на статистической значимости лекси-

ки релевантных документов и на критериях, позволяющих искать «по-

хожие» документы.

Далее будет рассмотрена совокупность моделей механизмов ин-

формационного поиска, в которых в качестве запроса используются как

множества дескрипторов, так и множества документов (соответственно,

модель механизма поиска по совпадению терминов, модели механизмов

поиска по сходству), а также логические конструкции, построенные над

этими множествами (модель механизма поиска по логическому выраже-

нию, модель механизма поиска с использованием контекстных опера-

ций, модель механизма поиска документов-аналогов).

Каждый из механизмов поиска предназначен для определенных

типов БД, находится в соответствии с требованиями запросов и обладает

уникальными достоинствами. В ИПС же особенно важно обеспечить

возможность использования различных механизмов поиска (а также их

комбинаций) для реализации всех типов поисковых задач.

4.3.1. Матрица «термин-документ»

В соответствии с [Попов1996] используем понятие универсального

словаря

D (прообразом которого может быть, например, тезаурус, руб-

рикатор, УДК), содержащего множество лексических единиц всего по-

тока документов. Таким образом,

⊂ для всех i,

где

– совокупность лексических единиц некоторого документа

(сообщения), который является элементом некоторого потока

{}

Ll,l,...l,...lL

∈=

Аналогично универсальному словарю вводится понятие универ-

сального потока (массива)

(прообразы - поисковый массив ИПС, от-

раслевой справочно-информационный фонд, массив библиотеки), под-

множеством которого являются все документы:

107

{}

010

Ll,l,...l,...lL

ini

∈= для всех i, причем

nL =

где

- мощность множества L

Линейное представление теоретико-множественного образа доку-

мента:













где







входит не если 0

документ й-k в входит ермин тй-i если 1

Универсальный массив в линейном представлении есть матрица

размерности













11211

DnDD

inii

bbb

LLLLL

(4.6)

Подобные матрицы известны под названием матрицы

«термин-

документ»

. Каждый столбец матрицы соответствует документу и опи-

сывает множество терминов, содержащихся в нем. Таким образом, стол-

бец матрицы характеризует поисковый образ документа (ПОД).

Строка матрицы соответствует отдельному термину и является пе-

речнем документов, содержащих данный термин. Сумма элементов

строки представляет собой частотную характеристику термина (

), при-

сутствующую обычно в частотном словаре информационного массива:

∑

iki

Формализуем понятие механизма поиска как преобразователя

ПОЗа, представленного с помощью матрицы

, в бинарный вектор ре-

зультата

Q (размерности n

) и рассмотрим математическую интерпрета-

цию основных поисковых механизмов.

4.3.2. Модель механизма поиска по совпадению терминов

При поиске по условию совпадения терминов в паре запрос-

документ задается требование полного и/или частичного совпадение

терминов (ключевых слов) для отбора документов, содержащих эти

ключевые слова [Озкарахан1989]. Условие частичного совпадения мож-

но задать, используя в терминах поискового образа так называемый не-

существенный символ – символ маскирования (обычно для этого ис-

пользуется знаки «*», «?» и «%»). Такие символы могут начинать тер-

108

мин, заканчивать его или находиться в середине, причем их может быть

фиксированное или переменное число.

Формирование ПОЗа – это выбор из матрицы

строк, соответст-

вующих терминам, указанным в запросе. При этом, если некоторый тер-

мин не найден в словаре

D, ему ставится в соответствие строка, состоя-

щая из одних нулей (нулевая строка). Таким образом, для

k терминов

получаем подматрицу запроса (

), в которой отдельные строки могут

быть нулевыми:













LLLLL

0222

0111

niii

kkk

bbb

Построим результирующий вектор запроса:













∑∑∑

===

lll

bbbQ

L (4.7)

Окончательный поисковый результат далее может быть сформи-

рован по двум правилам: документ считается формально релевантным

запросу, если содержит все

k терминов, или документ считается фор-

мально релевантным запросу, если содержит хотя бы часть (один, два,

три и т.д.) из

k терминов.

При реализации первого правила получаем:

()











∑

случае противном в - 0

если ,1

где ,

ink

qqqqQ

Для реализации второго правила зададим порог

m, определяющий

минимальное количество терминов (из

k терминов запроса, km ≤ ), необ-

ходимое для отнесения документа к множеству формально релевантных

запросу:

()











≥

∑

случае противном в - 0

если 1

где

ink

mb,

q,qqqQ

4.3.3. Модель механизма поиска по логическому выражению

Логическое выражение поискового условия – это синтаксическая

конструкция языка, задающая порядок и способ вычисления величины,

принимающей значение «0» или «1» («истина» или «ложь»).

В соответствии с правилами выражение представляет собой по-

следовательность

операндов, соединенных друг с другом знаками опе-

109

раций. Некоторые фрагменты выражения могут быть заключены в круг-

лые скобки.

Нотация Бэкуса для такого выражения следующая:

<Выражение> ::=

<Операнд>

<Выражение><Операция><Операнд>

<Операнд><Операция><Выражение>



(<Выражение>)<Операция><Операнд>



<Операнд><Операция>(<Выражение>)

В качестве

операнда в поисковом выражении обычно выступают

термины (дескрипторы), а в качестве

операции – одна из логических

операций AND (И), OR (ИЛИ), XOR (ИСКЛЮЧАЮЩЕЕ ИЛИ) и NOT

(НЕ).

Первый этап вычисления логического выражения может состоять

в построении двоичного дерева операций. Исходя из того, что все логи-

ческие операции (кроме операции НЕ, которая, по существу, представ-

ляет собой инверсию исходного значения) являются бинарными, можно

представить любое логическое выражение запроса в виде несбалансиро-

ванного двоичного дерева, прохождение по которому снизу вверх при-

водит к получению результата.

В узлах такого дерева (рис.4.4), включая корневую вершину, рас-

положены логические операции (

), а листья (конечные узлы) представ-

ляют собой строки матрицы

, соответствующие терминам запроса

(

)

,1, njbt

iji

== ).

Рис. 4.4. Дерево структурных единиц запроса

Например, логическому выражению:

4321

tttt

∧

∨

∧

, где t

– термины

запроса, соответствует двоичное дерево, приведенное на рис. 4.5.

k-2

k-1

…… …

…

… … …

110

Рис. 4.5. Дерево логического выражения

4321

tttt ∧∨

∧

Будем далее называть

операндом запроса отдельно вычисляемое

выражение, соответствующее поддереву запроса.

Рассмотрим расширенную матрицу «термин-документ»

′

, строки

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

терминов в документах информационного массива, но и результирую-

щие векторы запросов (

)













′′′

′

′′′

22221

11211

nDDD

bbb

LLLLL

, где

′

, (4.8)

K – количество включенных в матрицу результирующих векторов

запросов,











′

запроса результат собой етпредставля строка если ,

матрице тпринадлежи строка если ,

Далее, поставим в соответствие каждой логической операции пра-

вило ее выполнения с использованием расширенной матрицы:

(

)

,n,j,bobbob

mjkijmki 0

′′

(4.9)

где

o из множества бинарных логических операций:

{

}

oooOOo ,...,,,

=∈ (4.10)

Для унарной операции NOT это правило реализуется следующим

образом:

(

)

,1, njbb

iji

′

¬=

′

¬ (4.11)

Тогда алгоритм разрешения двоичного дерева поискового запроса

состоит в последовательном выполнении снизу вверх логических опера-

ций и в пополнении на каждом шаге матрицы

очередной строкой-

результатом.

Условием выполнения

k-той операции служит наличие в матрице

′

строк, соответствующих правому и левому операнду. После выпол-

нения

k-той операции формируется результирующий вектор

mkik

bobq

′

= ,

который становится (

′

D )-й строкой матрицы.

٨٨