Модификация модели векторного пространства для ранжирования документов

В модели векторного пространства документ и запрос представляются в виде векторов и релевантность рассчитывается по следующей формуле [1]:

где, — векторное представление запроса, — векторное представление документа. В качестве векторов в эксперименте использовалась оценка веса запроса и нормированный вес термина в документе — .

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

где — размер базы документов, — количество документов с данным термином.

В данном примере вес термина в документе учитывал только частоту термина, но возможны и другие варианты [2] взвешивания документа. Ручной подбор схемы взвешивания для коллекции документов займет большое время, проведем эксперимент для подбора схемы взвешивания используя одну из трех, , или c помощью генетического алгоритма, который получает на вход количество коэффициентов используемых в модели и возвращает подобранные коэффициенты. Общий алгоритм выглядит следующим образом:

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

• 2. Вычисляем приспособленность хромосом. Оцениваем ошибку, для каждого набора коэффициентов.
• 3. Выбираем двух родителей с наименьшей ошибкой для операции скрещивания.
• 4. Выбор хромосом для операции мутации.
• 5. Оценка приспособленности нового набора коэффициентов.
• 6. Если ошибка — набора больше заданной ошибки, то переходим к пункту 3, иначе пункт 7.
• 7. Полученный набор коэффициентов, который минимизирует ошибку, возвращается в модель поиска.

Рассмотрены более детально основные аспекты:

• · Все коэффициенты генерируются изначально случайным образом по равномерному закону при ограничении сверху и снизу. Затем переводятся в двоичный вид, чтобы можно было применять операции скрещивания и мутации.
• · Ошибка оценивается по следующей формуле:

где, — средняя оценка документа экспертами, по запросу. — полученная релевантность документа, по запросу .

Для проверки эффективности применения генетического алгоритма (ГА), сравним полученные метрики оценки для двух систем по 30 запросам.

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

В большинстве случаев ГА показывает лучшую полноту. Среднее значение полноты: ГА= 0,245; ВМ=0,153.

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

Среднее значение точности: ГА=0,207; ВМ=0,144.

Среднее значение аккуратности: ГА=0,87; ВМ=0,83.

Среднее значение ошибки: ГА=0,153; ВМ=0,16.

Отметим основные свойства:

· .

• · если или, то
• · если, то
• ·

F-мера алгоритмов полказана на рисунке 5.

генетический алгоритм векторный ранжирование.

Среднее значение f-меры: ГА=0,20; ВМ=0,14.

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

• 1. Маннинг, Кристофер Д.

  Введение

  в информационный поиск. М.: Вильямс, 2011.

• 2. Дубинский А. Г. Некоторые вопросы применения векторной модели представления документов в информационном поиске // Управляющие системы и машины. 2001. № 4.