Информационные системы. Лекции

51

Лекция 8. Поисковый аппарат АИПС. Критерии эффективности АИПС

∙Поисковый аппарат АИПС

∙Оценка эффективности поиска

Поисковый аппарат АИПС

Технология функционирования АИПС состоит в переводе сообщений (докумен- тов, текстов) и информационных запросов на ИПЯ (формировании поисковых образов документов и запросов), сравнение ПОЗов и ПОДов и выдачи пользователям АИПС сообщений, отвечающих их информационным потребностям.

При переводе сообщений на ИПЯ возможны различные подходы:

∙полный перевод сообщения на ИПЯ;

∙частичный перевод сообщения на ИПЯ (перевод на ИПЯ только отдельного элемента сообщения, например, его названия или реферата);

∙полный отказ от перевода на ИПЯ и использование в процессе поиска ориги- нального сообщения или его составляющих (текста, аннотации, заглавия, реферата и т.д.).

Перевод запросов на ИПЯ тоже может быть выполнен в различных вариантах:

∙ - перевод всею информационного запроса на ИПЯ и формирование единого

ПОЗа;

∙- перевод отдельных составляющих на ИПЯ и формирование поисковых об- разов подзапросов.

Поисковое предписание (ПП), т. е. задание АИПС на поиск информации тоже может быть сформулировано по-разному:

∙- формулировка единого ПП. соответствующего единому ПОЗу;

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

Причем в несколько ПП может быть развернуто и единое ПП. Процедура срав- нения ПОЗов (или ПП) и ПОДов и принятия решений о выдаче или невыдаче пользова- телям АИПС тех или иных сообщений тоже характеризуются большим многообразием. Такое многообразие определятся многими факторами и, прежде всего, возможностями использования при формировании ПП логических операций И, ИЛИ, НЕ и различных критериев выдачи.

Организация и используемые методы и средства реализации процессов индекси- рования документов и запросов и проведения собственно поиска оказывают основопо- лагающее влияние на эффективность поиска и, соответственно, эффективность АИПС.

Совокупность методов и средств реализации процесса поиска информации в ав- томатизированных ИПС назовем аппаратом поиска иди поисковым аппаратом.

Поисковый аппарат АИПС включает:

52

∙ математический аппарат формализованного представления и поиска инфор-

мации;

∙методы и средства структурирования информационных запросов;

∙критерии выдачи (смыслового соответствия) информации;

∙стратегии поиска и организации массивов.

Оценка эффективности поиска

Оценка эффективности АИС связана с анализом как затрат АИС на информаци- онное обеспечение основной деятельности, так и эффекта, получаемого в основной деятельности в результате использования предоставляемой АИС информации. Однако "полезность" результатов основной деятельности в большинстве своем не может быть выражена количественно, в особенности, если такие результаты носят социально- политический, юридический, моральный, психологический и т. д. характер. Еще боль- шие сложности возникают при оценке той доли эффекта основной деятельности, кото- рая получена в результате использования информации.

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

Всвязи с этим основными показателями функциональной эффективности АИПС являются:

∙полнота поиска;

∙точность поиска;

∙оперативность поиска;

∙специфичность поиска;

∙коэффициент корреляции;

∙интегральный энтропийный показатель.

Оценка любого показателя функциональной эффективности связана с определе- нием неформальной релевантности выданной информации информационному запросу.

Примечание

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

Формированием поискового образа запроса и переводом его в машиночитаемую форму заканчи- вается один из важнейших этапов процесса поиска информации - этап предмашинной обработки запроса. Следующий этап - непосредственно процесс автоматизированного поиска информации, состоящий в сравнении ПОДов сообщений (документов) базы данных АИПС с заданным поисковым образом запроса (или их совокупности) с целью выборки документов (сообщений), релевантных информационному за- просу. Критерий, позволяющий принять решение о релевантности сообщения информационному запро- су, носит названия критерия релевантности (КР) или критерия смыслового соответствия (КСС), или кри- терия выдачи (KB).

Различают два понятия релевантности - релевантность и формальную релевантность.

Понятие релевантности связано со смысловым соответствием сообщения (документа) тексту

53

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

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

Ясно, что при переводе информационной потребности в информационный запрос, а запрос в ПОЗ, так же как и при переводе сообщения в ПОД, возникают определенные семантические искажения. В связи с этим формальная релевантность весьма существенно отличается от действительной релевант- ности. Документ, признанный системой формально релевантным. может не оказаться таковым с точки зрения потребителя. Однако, альтернативы нет, АИПС может пользоваться только понятием формальной релевантности.

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

-подмножество релевантных документов - М1

-подмножество нерелевантных документов - М2

Ml M2

N2

Рис. 1. Таблица сопряженности поиска

Суть работы АИПС состоит в разбиении множества документов БД тоже на два подмножества (рис.1):

-подмножество формально релевантных запросу документов (выдаваемых до- кументов) - N1;

-подмножество формально нерелевантных запросу документов (невыдаваемых документов) - N2.

Полнота поиска определяется отношением числа выданных релевантных доку- ментов (а) к общему числу релевантных документов массива (а + с):

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

Точность поиска - отношение числа выданных релевантных документов (а) к общему числу выданных документов (а + b):

Т = а а+ b , 0 ≤ Т ≤ 1.

54

Специфичность поиска - отношение числа невыданных нерелевантных доку- ментов (d) к общему числу нерелевантных документов (d+b):

С = d d+ b , 0 ≤ С ≤ 1.

Теоретически и экспериментально показано, что показатели полноты и точности поиска находятся в обратно пропорциональной зависимости, т. е. повышение полноты поиска в рамках данной ИПС всегда сопровождается снижением (по крайней мере не- повышением) точности поиска. И наоборот. Подробно эти вопросы будут обсуждаться в разделе моделирования ИПС.

Для определения релевантности документов в исходной базе данных использу- ются различные методы, позволяющие оценить число релевантных (а + с) документов в БД не прибегая к анализу всей БД.

1.Случайная выборка некоторой части документов. Определение доли реле- вантных документов в выборке и аппроксимация полученных данных на всю БД.

2.Использование запросов, ориентированных на поиск заранее заданных доку- ментов и определение в выдаче доли заданных документов. Этим методом можно не- посредственно оценить полноту поиска.

3.Проведение серии поисков по последовательно модифицируемому запросу и определение накапливаемых в процессе модификации запроса релевантных документов выдачи.

56

Характеристики полей

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

определяется и фиксируется максимальная длина поля для работы с информацией большого объема.

Многие пакеты прикладных программ с фиксированной длиной полей имеют верхнюю границу длины поля (часто - 255 символов, иногда - короче). Этого верхнего ограничения часто недостаточно для вмещения всей информации, которую необходимо ввести в поле.

Длина и содержание каждого поля обычно широко варьируются от записи к за- писи, а одни и те же поля представлены в каждой из записей. Поля нужны для стан-

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

Повторяющиеся значения в полях

Одной из характеристик для большинства текстовых БД является потребность в нескольких значениях в данном поле. Количество авторов в библиографическом файле, например, может варьироваться от нуля до нескольких, или количество ингредиентов в рецепте может варьироваться от одного до многих. Практически всегда встречается не- сколько ключевых слов в соответствующем поле. Повторяемость значения в полях не- возможно предсказать. В поле "автор" в одной записи может быть два автора, а в дру- гой -10. Каждое из значений в таких полях обычно равно по значимости другому, и ка- ждое, в целях обращения к ним, должно восприниматься равнозначно.

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

Системы БД, позволяющие иметь только одно значение на одно поле, заставля- ют разработчика БД идти на компромиссы, что приводит к расходам дискового про- странства и ухудшению результатов выдачи документов на запрос. Можно, например, решить, что библиографические записи должны включать до трех авторов. Если поле может содержать только одно значение, то придется создать три поля:

АВТОР1, АВТОР2 и АВТОРЗ. Это приведет к невозможности работать с запи- сями, которые имеют более трех авторов. Более объективно можно судить об этих про- блемах с точки зрения возможностей выдачи. Чтобы найти записи, в которых Иванов

57

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

Несколько ключей доступа

Так как пользователи обычно ищут неизвестный набор значений, а не выбирают из известных значений, природа процесса выдачи в текстовых БД является сложной. Одним из аспектов этой сложности является количество способов определения записей, необходимых для выдачи. Во многих случаях пользователь не знает, какое количество записей будет найдено для удовлетворения его или ее запроса, и выданные записи обычно имеют несколько уровней удовлетворительности.

Одним из путей повышения качества поиска является поддержка как можно большего количества способов поиска записей, т.е. необходимо позволять проводить поиск по всем полям. Во многих случаях, все или почти все поля обеспечивают доступ к содержимому БД. Более того, доступ к полю может быть обеспечен еще лучше, если запрос будет содержать фрагменты содержимого разного вида (ключевые слова из на- званий, усеченные имена и т.д.).

Сложные запросы

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

Поисковые функции ИПС

Информационно-поисковые системы на микрокомпьютерах обычно предлагают широкий выбор гибких поисковых функций в зависимости от вида индексирования по- лей. Эти функции включают в себя: усечение (truncation), возможность просмотра на экране файла инвертированных индексов, поиск по словарной близости - корневому родству (proximity searching), с помощью булевых операторов, создание наборов (set building) и пошаговое сужение области поиска (stepwise refinement), поиск по размеру

(range searching) и поиск по сравнению (comparison searching), а также возможность за-

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

Поиск с помощью усечения

Большинство систем позволяют пользователю использовать усечение терминов

58

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

пользователь дает системе команду найти входы инвертированных индексов БИБЛИОТЕКА, БИБЛИОТЕЧНЫЙ, БИБЛИОТЕЧНАЯ АВТОМАТИЗАЦИЯ и др. (Символ усечения различен в разных системах, но обычно это символы ?, #, *, и /). В некоторых системах можно найти и другие вариации усечения. Левостороннее усече- ние не используется всеми системами, но в некоторых случаях оно может оказаться не- обходимым (например, в химической БД).

Чаще встречается функция определения максимальной длины термина или на- бора букв (например, для выдачи терминов КОМПЬЮТЕР, КОМПЬЮТЕРА, а не КОМПЬЮТЕРИЗАЦИЯ или КОМПЬЮТЕР-НЫЙ). Вставной символ неопределенно- сти, иногда называемый internal wildcard character, используется там, где необходима замена символов (например, WOM*N). Некоторые системы поддерживают такой сим- вол неопределенности для замены некоего набора букв в середине слова, например при выражении ПРИВ*ТЬ будут выданы ПРИВЫКАТЬ, ПРИВЫКНУТЬ и любое другое слово, начинающиеся на ПРИВ и заканчивающиеся на ТЬ, например, ПРИВИНТИТЬ.

Использование усечения имеет особое значение для пофразово проиндексиро- ванных полей, поскольку это позволяет пользователю получить необходимые записи без необходимости знать фразы целиком. Используя усеченный поиск автора ИВАНОВ можно найти все записи, содержащие автора с фамилией Иванов, так как не будет не- обходимости вводить пробелы, знаки пунктуации или инициалы таким образом, как это требуется при пофразовом индексировании, так как все они будут следовать за симво- лом усечения.

Поиск с помощью просмотра индексов

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

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

Многие системы при выдаче алфавитного списка индексов для каждого термина дополнительно указывают количество записей, содержащих искомый термин (postings). Это помогает при формировании стратегии поиска. Некоторые системы позволяют пе- ремещение вверх или вниз по списку, другие требуют от пользователя указать пределы выдаваемого списка (например, от БАБОЧКИ до БУЛОЧКИ, а некоторые выводят лишь ограниченное количество терминов сверху и снизу указанного термина.

Поиск по словарной близости (proximity searching)

Он является особенно мощной функцией для пословно проиндексированных по-

59

лей.

Поиск по словарной близости позволяет пользователю посткоординировать фра- зы из пословно проиндексированных полей, таких как "название" и "реферат". Эта функция становится возможной из-за наличия информации о позициях при каждом из терминов-входов" в файле инвертированных индексов. Эта информация представляет собой указание на поле и положение данного термина в этом поле. Пользователь, на- пример, может сделать запрос на слово БИБЛИОТЕЧНАЯ, после которого сразу же идет слово АВТОМАТИЗАЦИЯ в пословно или смешанно проиндексированном поле. Система, в этом случае, использует информацию о позициях для воссоздания фразы, даже если каждое слово представляет собой отдельный инвертированный индекс- "вход". Функции поиска по словарной близости в каждой системе могут быть разными.

Поиск с помощью булевых логических операторов

Одним из способов удовлетворения сложных запросов является использование булевых логических операторов AND, OR и NOT. Они являются эквивалентами пере- сечения, объединения и исключения. Эти три оператора в той или иной форме можно найти практически во всех информационно-поисковых системах. С помощью операто- ра AND поиск сужается организацией набора, чьи элементы являются общими для обоих наборов искомых компонентов. Например, выражение ПРИНТЕР AND ДИСПЛЕЙ будет выполняться с набором документов, содержащим термин ПРИНТЕР и другим набором, содержащим термин ДИСПЛЕЙ. В результате будут выданы записи, каждая из которых содержит и термин ПРИНТЕР, и термин ДИСПЛЕЙ. Записи, содер- жащие только термин ПРИНТЕР, выданы не будут, так же, как и записи, содержащие только термин ДИСПЛЕЙ.

Напротив, при формулировании выражения ПРИНТЕР OR ДИСПЛЕЙ будут выданы документы, содержащие хотя бы один из указанных терминов.

В случае, если выражение сформулировано как ПРИНТЕР NOT ДИСПЛЕЙ, бу- дут выданы документы, содержащие термин ПРИНТЕР, и притом только те из них, в которых не содержится термин ДИСПЛЕЙ.

Используя логические операторы в сложных сочетаниях, необходимо учиты- вать, что существует общий порядок предпочтения (организации их выполнения), где сначала выполняется оператор NOT, затем - AND, а потом - OR. Например, в выраже- нии ДИСПЛЕЙ OR ПРИНТЕР NOT ЛАЗЕРНЫЙ AND CANON сначала будет сформи- рован набор документов о нелазерных принтерах, затем - набор документов, где гово- рится о нелазерных принтерах, выпускаемых фирмой CANON, а в результате будут выданы записи о нелазерных принтерах , выпускаемых фирмой CANON и всех диспле- ях.

Большинство систем также поддерживают возможность сложного комбиниро- вания булевых операторов подобно выполнению арифметических операций со скобка- ми. При этом, сначала выполняются операции внутри скобок, а затем - между скобка- ми. Таким образом, при обработке выражения (ДИСПЛЕЙ OR ПРИНТЕР) AND (CANON OR SUMSUNG) сначала будут сформированы: отдельно набор документов,

60

содержащих информацию о принтерах или дисплеях и отдельно набор документов, со- держащих информацию о фирмах, а затем - с этими двумя наборами документов будет произведена операция AND, т.е. в результате будет выдан набор документов, содержа- щих информацию только о тех принтерах или дисплеях, которые были выпущены фир-

мами CANON или SUMSUNG.

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

-очень трудно определить насколько будет варьироваться "глубина" поиска для выдачи большего или меньшего количества информации;

-выдача - это процесс, выражаемый фразой "все или ничего", и частичное соот- ветствие не поддерживается. Невозможно установить критерий выдачи, если говорить об уровне соответствия запроса и документов;

-выдача не может быть представлена в определенном порядке по степени уменьшения соответствия выданных документов запросу.

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

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

Метод пошагового сужения области поиска требует от системы способности хранить (или просто воссоздавать) результаты каждого запроса, воспринимать каждый из таких результатов в качестве меченого набора (обычно набору присваивается опре- деленный номер), а также комбинировать вновь созданные наборы со старыми.

Система, не поддерживающая сложное комбинирование или группировку буле- вых операторов, запрос о принтерах, дисплеях и фирмах может выполнить пошагово следующим образом:

ПРИНТЕР OR ДИСПЛЕЙ -> НАБОР1,

CANON OR SUMSUNG -> НАБОР2 ,

НАБОР1 AND НАБОР2 -> НАБОРЗ

Некоторые системы требуют ввода каждого термина в качестве отдельного ша- га, а оперируют булевыми операторами только с номерами наборов. В таких системах вышеприведенный запрос будет выполнен за 7 шагов:

ПРИНТЕР -> НАБОР1 ДИСПЛЕЙ -> НАБОР2 CANON -> НАБОРЗ SUMSUNG -> НАБОР4

НАБОР1 OR НАБОР2 -> НАБОР5