Экспериментальная оценка метода

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

Для эксперимента использовалась программа Следопыт [9, 10], разработанная компанией МедиаЛингва (http://www.medialingua.ru). Эта программа реализует нечеткий поиск текстовой информации по запросу на естественном языке.

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

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

учет только информативных слов запроса (не входящих в словарь неинформативных слов и выражений);

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

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

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

учет количества слов и их взаимной информативности в появлении запроса (полном или частичном);

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

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

Качество поиска не зависит от лексики предметной области — Следопыт с одинаковой эффективностью производит поиск как по газетным или деловым текстам, так и по узким тематическим направлениям типа глазных болезней или порошковой металлургии.

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

Экспериментальная оценка проводилась путем анализа результатов поиска программой Следопыт по 8 запросам в массиве компьютерных текстов общим объемом 8 Мбайт.

Сравнивались 2 метода поиска:

исходный поиск — нечеткий поиск Следопыта с параметром степень расширения запроса, равным 25%;

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

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

содержали все слова запроса на небольшом (не более 5−6 слов) расстоянии друг от друга;

включали по 5 слов слева и справа от появления запроса в документе.

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

Отобранные вышеуказанным образом ассоциативные слова добавлялись к исходному запросу, и по этому расширенному запросу выполнялся поиск с помощью Следопыта.

Пример

Для запроса.

настольная картографическая система

сформирован расширенный запрос.

настольная картографическая система MapInfo

По всем 8 запросам был проведен поиск и вычислены значения полноты П и точности Т поиска. Эти два параметра являются общепринятыми характеристиками эффективности поиска [7, 11]. Определяются они по следующим формулам:

П = Nrf/Nr.

Т = Nrf/Nf.

Здесь:

Nrf — количество релевантных документов среди документов, найденных по запросу;

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

Nf — количество документов, найденных по запросу (из них Nrf документов релевантны запросу).

Полнота и точность, полученные по отдельным запросам, усреднены и сведены в приведенную ниже таблицу.

исходный поиск ассоциативный поиск

Полнота 0.74 1.0.

Точность 0.96 0.89.

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