Неточный поиск лучших К документов

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

С точки зрения пользователя такой приблизительный поиск К документов не всегда плох. В любом случае нет никаких гарантий, что К документов, определенных на основекосинусной меры сходства, на самом деле лучше всего соответствуют запросу: косинусная мера сходства сама по себе лишь приблизительно оценивает релевантность документа запросу. Мы опишем эвристические приемы, с помощью которых можно найти А" документов, релевантности которых, определенные на основе косинусной меры сходства, близки к релевантности лучших К документов. Основные вычислительные затраты обусловлены необходимостью определения косинусных мер сходства между запросом и большим количеством документов. Кроме того, при большом количестве документов с близкими значениями релевантности стоимость поиска К наилучших документов алгоритмом частичной пирамидальной сортировки также увеличивается. Рассмотрим ряд идей, позволяющих удалить из рассмотрения большое количество документов, не вычисляя для них косинусную меру сходства. Эти эвристические приемы выполняются в два этапа

Чемпионский список

Идея чемпионских списков (champion lists), который иногда называют также списками фаворитов (fancy lists) или списками топ-документов (top docs), заключается в предварительном определении для каждого словарного термина t набора из г документов с наибольшими весами по отношению к термину t. При этом величина г выбирается заранее. В схеме взвешивания tf-idf эти г документов имеют наибольшие значения tf по отношению к термину t. Этот набор из г документов называется чемпионским списком для термина t.

Теперь, имея запрос q, мы можем создать множество А следующим образом: объединим списки чемпионов для каждого термина, содержащегося в запросе q. Вычисление косинусной меры сходства теперь ограничивается только документами множества А. Критический параметр к этой схеме — значение г, сильно зависящее от приложения. Интуитивно ясно, что величина г должна быть большой по сравнению с К, особенно если используется любая форма сокращения индекса. Одна из проблем заключается в том, что величина г определяется в момент построения индекса, в то время как число К зависит от приложения и может оставаться неопределенным вплоть до момента, пока не будет получен запрос q. В результате мы можем (как и в случае сокращения индекса) обнаружить, что множество А содержит меньше К документов. Нет никаких причин полагать число г одинаковым для всех терминов в словаре; например, для более редких терминов его можно установить на более высоком уровне

tel-icq