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

Классификация информационно-поисковых систем

Информационно-поисковые системы (ИПС) подразделяются на три класса (рис.3.1): документальные, фактографические и ги­пертекстовые (ГИПС). [1]

Документальные ИПС хранят и выдают сведения о докумен­тах, основное содержимое которых представлено в виде связан­ного текста на естественном языке (ЕЯ).

Признаки документа, отражающие его содержание в ИПС, называют поисковым образом, а признаки запроса к ИПС — по­исковым предписанием.

Процедура перевода документа и запроса в форму представ­ления, принятую в ИПС, связана с ее индексированием. При со­поставлении поискового образа и поискового предписания ис­пользуется тот или иной критерий смыслового соответствия (релевантности).

Рис. 3.1 Классификация информационно-поисковых систем

Основным объектом информационного фонда документаль­ной ИПС является аннотация (реферат) и библиографическое описание документа (книги, события, предмета). Реферат (анно­тация) выражается на ЕЯ и отражает основные характеристики документа, представляющие интерес для пользователей. Предпо­лагается, что в подобном описании можно выделить ряд слов и словосочетаний, число которых значительно меньше общего чис­ла слов в описании.

В то же время выделенная информация достаточно точно характеризует описание. Такие слова и словосочетания называются ключевыми словами или дескрипторами. Запрос к документаль­ной ИПС формулируется в виде перечня дескрипторов, которые, по мнению пользователя, характеризуют искомый документ.

При вводе в ИПС нового объекта (реферата) его дескрипторы автоматически включаются в словарь дескрипторов. Каждому дескриптору присваивается номер, называемый индексом деск­риптора. Совокупность индексов, соответствующих полному на­бору дескрипторов реферата, составляет его поисковый образ. Новый поисковый образ снабжается уникальным идентификато­ром и включается в массив поисковых образов. Тем же иденти­фикатором помечается новый реферат, заносимый в массив рефе­ратов.

Поиск в дескрипторной ИПС организуется следующим обра­зом. Запрос, сформулированный на ЕЯ, подвергается анализу, в рамках которого в нем выделяются дескрипторы, входящие в сло­варь дескрипторов. Их совокупность образует поисковое предпи­сание, соответствующее запросу. Оно сопоставляется с поиско­выми образами, в результате чего определяется их релевантность. Если поисковый образ и предписание релевантны, то из поиско­вого образа извлекается идентификатор реферата, выдаваемого пользователю.

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

В целях ускорения поиска для каждого дескриптора в слова­ре дескрипторов указывается список идентификаторов рефера­тов, в которых он встречается. Такая информационная структура ИПС называется индексом.

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

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

В фактографических ИПС хранятся не документы, а собст­венно сведения (факты) об объектах предметной области. Подобные ИПС реали­зуются, в частности, на основе реляционных БД. С точки зрения обеспечения релевантности результатов поиска (выборки дан­ных) запросу фактографический поиск в отличие от докумен­тального является точным и полным.

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

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

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

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

Эффективность информационного поиска документов, обес­печиваемая ИПС, оценивается по информационной полноте и информационному шуму. Названные показатели выражаются ко­эффициентами полноты К_n и шума К_ш соответственно. Коэффи­циенты К_n и К_ш принимают значения в интервале от 0 до 1. В не­которых источниках эти коэффициенты выражают в процентах.[1]

Пусть ИПС предъявлен i-й запрос. Информационно-поисковая система содержит множество документов реле­вантных этому запросу. В результате поиска получено множество . Возможны следующие варианты.

1. . Идеальный вариант: полнота максимальна (К_n = 1), а шум нулевой (К_ш = 0).

2. . Имеет место неполнота (0 К_n < 1), а шум отсут­ствует (К_ш = 0).

3. . Неполнота исключается (К_n = 1), но есть шум (0К_ш <1).

4. Ø & Ø & Ø . Худший вариант: нулевая полнота (ни один релевантный документ не найден; К_n = 0) и максимальный шум (все, что выделено, не соответствует запросу; К_ш = 1).

5. Ø &&&. Имеют место и неполнота (0 К_n < 1 ), и шум (0 К_ш < 1).

Определим коэффициенты полноты и шума [1]:

(3.1)

(3.2)

где m — достаточно большое число, чтобы по теореме о больших числах обеспечить требуемую достоверность результата экспе­римента по определению К_n и К_ш.

Смысл коэффициентов полноты и шума на теоретико-мно­жественном уровне иллюстрирует рис.3.2.

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

Рис.3.2 Графическая интерпретация коэффициентов полноты и шума

(3.3)

(3.4)

Эффективность информационного поиска выражается че­рез коэффициенты К_n и К_ш, что позволяет рассматривать ее в ка­честве интегрального показателя эффективности информаци­онного поиска ИПС. В литературе в функции (К_n, К_ш) вместо К_ш принято использовать обратный ему показатель — коэффици­ент точности К_m.

Таким образом, запишем данную функцию в виде:

(3.5)

В теории информационного поиска предложен обобщенный комплексный показатель эффективности (мера Ван Ризбергена), позволяющий учитывать предпочтение, отдаваемое поль­зователем ИПС точности или полноте:

(3.6)

где β — параметр, отражающий предпочтение пользователя ИПС одному из показателей эффективности, входящих в (точности, полноте), над другим.

При β = 1 точность и полнота одинаково важны. На интервале β [0; 1] приоритет имеет точность, а на интервале β ]1; [ — полнота.