Как рассчитывается релевантность документа
| Данный узел или опция доступны, только если они включены в лицензии PolyAnalyst Server. |
Поисковый запрос, Таксономия, Производные колонки, Фильтрация строк, а также некоторые другие узлы PolyAnalyst используют общий поисковый механизм при применении PDL-выражения к ряду записей и расчете их релевантности. PDL-выражения используют простой булевый синтаксис алгебраического типа. Сначала выполняется анализ и разбор запроса, после чего поисковый механизм исследует текстовую колонку для обнаружения соответствий, которые затем ранжируются по релевантности.
В данном разделе под документом понимается содержимое соответствующей текстовой колонки в таблице данных.
| Компания Мегапьютер постоянно ищет способы улучшения ранжирования по релевантности. Алгоритм расчета релевантности периодически изменяется в новых версиях PolyAnalyst. В связи с этим при обновлении программы могут поменяться и значения релевантности. Это может привести к неожиданным результатам, например, когда вы используете режим Лучшее соответствие для деления записей на категории в узле Таксономия, и какой-либо документ становится более релевантным по отношению к другой категории. |
PolyAnalyst использует собственной доработку достаточно известного алгоритма ранжирования по релевантности Okapi BM25.
Okapi BM25 использует принцип "набора слов", который игнорирует порядок слов в документе (т.е. близость искомых слов в документе не влияет на степень релевантности этого документа поисковому запросу). Вместо этого алгоритм сосредотачивается на наличии или отсутствии слов в каждом документе и на частоте использования слов в конкретном документе, а также на частоте каждого искомого слова во всех документах, по которым выполняется поиск. Длина документа (т.е. число слов в каждом документе) также является важным фактором.
Выходными данными алгоритма является мера релевантности конкретного документа поисковому запросу. Релевантность каждого найденного документа вашему поисковому запросу измеряется по шкале от 0 до 100, где значение 100 означает высокое релевантное соответствие.
Ниже перечислены особенности алгоритма определения релевантности PolyAnalyst в сравнении с традиционным алгоритмом BM25:
-
Вместо того, чтобы выполнять поиск в исходном (необработанном) тексте, PolyAnalyst использует индексы. Вы можете контролировать определенные параметры индексирования с помощью узла Индекс. Добавление текстового индекса обязательно предполагает создание репрезентации исходного текста, которая может отличаться от самого текста (некоторая информация, например, сведения о близости слов, теряется).
-
Вы можете использовать дополнительные инструменты, например, узел Замена терминов для внесения изменений в исходный текст до индексирования.
-
Вы можете использовать PDL-выражения, содержащие такие функции, как phrase() или near(), для создания ограничений на близость слов.
-
PolyAnalyst анализирует морфологию слов, т.е. способен осуществлять поиск слова в документах не только в строго заданном виде, но и во всех его морфологических формах (стемминг). Например, при поиске слова кот будет также найдено слово коты. Частота термина в документе в результате морфологического поиска изменяется, поскольку слова считаются не уникальными знаками, а потенциальными альтернативными средствами выражения одного и того же семантического содержимого (значения). Алгоритм BM25 более наивен в этом отношении.
-
PolyAnalyst использует специальные схемы взвешивания для определенных конструкций терминов. Упрощенно это можно объяснить как применение коэффициента к некоторым терминам для изменения веса определенных терминов с целью повлиять на результат формулы BM25.
-
PolyAnalyst позволяет создать конструкцию семантического типа, например поиск на основе гиперонима, который так же, как и морфологическая группировка (стемминг различных символов по тому же символу в ходе предварительной обработки) влияет на результаты, рассматривая уникальные при обычных обстоятельствах символы как похожие.
| Проекты и узлы, созданные в PolyAnalyst версии 6.0.1380 и ранее, будут использовать прежний метод расчета релевантности, описанный ниже. Для использования нового метода необходимо установить более позднюю версию PolyAnalyst и создать в ней соответствующий узел. |
Используемые методы определения релевантности
В настоящее время пользователям доступны два метода расчета релевантности: Точный и Приближенный. Каждый из них использует свой способ оптимизации и учитывает различный набор факторов, которые описаны ниже на примере точного метода.
Среди основных факторов выделяют:
-
Обратная частота документа (англ. inverse document frequency, IDF)
Обратная частота документа (IDF) – это фактор веса лексемы, при учете которого вес наиболее часто встречающихся в наборе документов терминов уменьшается, а тех, что встречаются редко – увеличивается. Определяется как обратная функция к количеству документов, где были найдены соответствия, и напрямую зависит от количества таких документов, которое может меняться по мере добавления или удаления новых записей из таблицы данных. Точный метод использует статистические сведения о лексемах, полученные на специально подобранном корпусе текстов (Статистический словарь):
\[IDF_{lex}=0.5+log(\frac{DiN_{all}}{DiN_{lex}})\]где \(DiN_{all}\) – общее количество документов, которые были использованы для составления словаря, а \(DiN_{lex}\) – количество документов, в которых присутствует конкретная лексема (\(lex\)). Менее популярные слова характеризуются меньшим значением делителя, что увеличивает показатель IDF.
-
Дополнительный статистический фактор
Если нам известно количество слов и количество документов, мы можем рассчитать значение переменной, которая характеризует среднюю длину документа. Данное значение впоследствии будет использовано при расчете релевантности:
\[DiL_{avg}=\frac{\sum_{i} DiL_{i}}{DiN_{all}}\]где \(DiL_{i}\) – длина \(i\)-го документа (в токенах) в таблице данных словаря. Данное значение уже рассчитано для конкретного Статистического словаря, который используется при расчете релевантности.
-
Фактор документа
Теперь рассмотрим переменные, значения которых зависят от конкретного документа при расчете релевантности. Пара основных переменных является очевидной и не вызывает трудностей при расчете:
\(DoL_{all}\) – длина документа (количество токенов в конкретном документе);
\(DoC_{lex}\) – количество обнаруженных в документе лексем (\(lex\)).
На данном этапе можно сделать промежуточный вывод: если вторая переменная равно 0, то таким же будет и значение релевантности документа по отношению к данной лексеме.
Основной фактор документа – это мера того, насколько длина документа отличается от среднего значения. Расчет выполняется следующим образом:
\[F_{doc}=\frac{DoL_{all}}{DiL_{avg}}\]
Второстепенные факторы не участвуют в исходной формуле Okapi BM25, но могут быть полезны для определения более релевантных документов в таблицах данных, которые содержат схожие записи. Второстепенные факторы основаны на наших знаниях о структуре документа. К таким факторам относятся:
-
Уровень заголовка
Если документ имеет особую структуру с обозначенными заголовками, мы считаем, что параметр \(HL_{doc}\) равен \(1.2\) (при условии, что хотя бы одна из лексем запроса входит в одно из предложений верхнего уровня), \(1.1\), если соответствующий уровень не является верхним, и \(1.0\), если отсутствует четкая структура или в заголовке не было найдено соответствий для лексемы запроса.
-
Значимость предложения
Изучив особенности поисковых запросов в документах, мы пришли к выводу, что лексемы, которые расположены ближе к началу документа, имеют большую значимость при расчете релевантности, чем те, что располагаются в конце. Таким образом, можно назначить веса предложениям согласно их положению в документе.
Рассматривая \(SeW_{k}\) как вес \(k\)-го предложения при проведении исследования, мы получили следующую серию значений:
\(SeW_{0}=3.0;\ SeW_{1}=2.5;\ SeW_{2}=2.0; ... SeW_{k}=1+\frac{1}{k}\ for\ k>2\)
-
Фактор разреженности
Данный фактор принимает во внимание положение нескольких вхождений лексемы в пределах одного предложения. Если лексема распределена с высокой плотностью, то релевантность соответствующего предложения увеличивается.
Если \(\{p_{1},...,p_{n}\}\) – положение лексем в предложении, то \(\{d_{1},...,d_{n-1}\}\) – расстояние между ними.
Фактор разреженности для предложения \(k\) определяется как:
\[SF_{lex}^{k}=\frac{SeL_{k}}{SeL_{k}+\sum_{i}log(e+d_{i}-1)}\]где \(SeL_{k}\) – длина \(k\)-го предложения (в токенах). Значение фактора разреженности у предложений с одним вхождением лексемы составляет \(1\).
-
Фактор предложения
Используя алгоритм синтаксического анализа, который разбивает документ на части (предложения), мы можем рассчитать некоторые относительные меры релевантности. Среди основных переменных выделяют:
\(SeL_{avg}\) – средняя длина предложений (в токенах);
\(SeL_{lex}\) – общая (совокупная) длина предложений, которые содержат конкретную лексему (\(lex\));
\(SeN_{lex}\) – количество предложений, которые содержат \(lex\);
\(SeC_{lex}^{k}\) – количество конкретных лексем в \(k\)-ом предложении документа.
Используя описанный выше фактор значимости предложения, мы можем получить соответствующий вес лексемы на основе предложения. Данный фактор зависит от особенностей и порядка предложений в документе, поэтому его значение изменится в случае реорганизации документа:
\[SeR_{lex}=\frac{\sum_{i}SeW_{i}*SeC_{lex}^{i}*SF_{lex}^{i}}{DoC_{lex}}\]В свою очередь, второстепенный фактор предложения может быть охарактеризован как мера распределения предложений, содержащих лексему, в пределах документа:
\[F_{sent}=\frac{SeL_{lex}}{SeL_{avg}*SeN_{lex}*SeR_{lex}}\]
Основная формула расчета (точный метод)
| Соответствующая формула для приближенного метода доступна в разделе ниже. |
где \(k\) и \(b\) – нормирующие константы, \(k=2\) и \(b=1\) .
После замены констант на значения и сокращения дроби мы получим упрощенную формулу:
В случае поискового запроса с несколькими лексемами, \(R_{Q}=\sum_{lex\ ∈\ Q}R_{lex}\).
Пара функций нормирования используется для сглаживания и нормализации значений в точках экстремума (\(0\) и \(inf\)) до желаемого рабочего диапазона \([0-100\)]. В реальных случаях они оказывают минимальное влияние на релевантность.
Первое дополнительное нормирование (нормализация \([0-100\)], обратно пропорционально \(x+\frac{1}{100-x}\)):
Второе дополнительное нормирование (сглаживание до значения \(100\)):
Различия между точным и приближенным методами
Приближенный метод изначально был разработан как простой и быстрый способ определения релевантности. Он использует внутренний механизм индексации текстов, что позволяет существенно увеличить производительность.
Когда выбран приближенный метод, алгоритм обрабатывает документ целиком, игнорируя какие-либо ограничения, которые явно указывает пользователь в своем поиском запросе (например, с помощью position()). Таким образом, вместо того, чтобы рассчитать \(R_{Q}\) для фрагмента, который соответствует поисковому запросу, мы фактически рассчитываем \(R_{Q}^{doc}\), где \(doc\) – номер документа.
Для некоторых переменных также доступны оптимизированные методы расчета.
При расчете фактора документа \(F_{doc}\) с использованием приближенного метода алгоритм использует сведения из самой таблицы данных вместо обращения к Статистическому словарю:
где \(DoL_{i}\) – длина \(i\)-го документа (в токенах) в текущей таблице данных, а \(DoN_{all}\) – общее количество документов в таблице данных.
Основной фактор документа при приближенном методе:
Если таблица данных состоит из одного документа, то значение фактора документа составляет \(1\). Показатель данного фактора меняется по мере добавления или удаления документов из таблицы данных (даже если эти документы не являются релевантными).
Как и в случае с фактором документа, значение IDF также рассчитывается с использованием сведений из самой таблицы данных без обращения к соответствующему словарю:
где \(DoN_{lex}\) – количество документов в таблице данных, которые содержат конкретную лексему (\(lex\)). Лексемы с высокой частотой присутствия в большинстве документов таблицы данных (например, артикли), имеют практически равные значения в числителе и знаменателе, поэтому \(IDF_{lex}^{app}\approx0.5\).
При расчете релевантности с использованием приближенного метода второстепенные факторы не учитываются. Соответствующая формула фактически является упрощенной версией формулы, которая применяется при точном методе:
С учетом того, что переменные \(k\) и \(b\) имеют те же значения:
И, наконец:
Старый метод определения релевантности
Алгоритм ранжирования, используемый в PolyAnalyst до версии 6.0.1380 – это собственная модификация известного алгоритма определения релевантности на основе векторно-пространственной модели. Основное отличие алгоритма PolyAnalyst состоит в том, что он учитывает близость слов. Данная характеристика может быть полезна в следующей ситуации:
Релевантность – это степень похожести поискового запроса и документа. В векторно-пространственной модели (ВПМ) документы рассматриваются как наборы слов. Порядок слов и их близость не важны. При подготовке модели составляется список всех слов в документе. Для каждого слова рассчитывается, сколько раз оно встречается в документе. Подобная операция повторяется для всех документов (или строк текстовых значений) в ряде документов.
Таким образом, формируется огромная матрица документов и слов, ячейки которой означают частоту использования терминов в отдельных документах. Все это помогает визуализировать матрицу. В представленной ниже таблице каждая строка является документом, а каждая колонка – термином.
Слово 1 |
Слово 2 |
Слово 3 |
|
Документ A |
5 |
2 |
0 |
Документ B |
3 |
0 |
7 |
Документ C |
6 |
1 |
4 |
Порядок колонок и порядок документов не имеют значения. Каждая цифра означает частоту термина в соответствующем документе. На примере выше Слово 1 появляется в Документе A 5 раз.
Теперь подумайте, как часто каждое слово появляется в каждом документе хотя бы один раз. Подобные ситуации возникают крайне редко. Могут быть тысячи слов, которые появляются лишь в небольшом количестве документов. Это означает, что в матрице имеется много пустых ячеек (со значением 0). Это особый тип матрицы – разреженная матрица, т.к. большая ее часть пустая.
Далее каждый документ может рассматриваться как вектор. Представьте, что Документ A выражен в виде списка пар [1:5, 2:2, 3:0]. Это значит, что Слово 1 встречается в документе 5 раз, Слово 2 – 3 раза, а Слово 3 – 0 раз.
Векторы имеют ряд важных свойств. Прежде всего, векторы можно разместить на графике с осями XY при наличии двух измерений (двух слов или понятий). Векторы документов, которые находятся ближе к слову на оси Y (вертикальная ось), располагаются ближе к вертикальному горизонту. Векторы документов, которые находятся ближе к оси X (горизонтальная ось), располагаются ближе к горизонтальному горизонту.
Эта область графика (верхний правый квадрант) называется пространством термина. Документы рассматриваются как векторы, направленные в данное пространство. Отсюда и название – векторно-пространственная модель.
Когда оценивается поисковый запрос, он также рассматривается как документ. Затем он располагается в том же пространстве терминов, что и все документы. После этого рассчитать релевантность так же просто, как и рассчитать "векторное расстояние" между вектором запроса и вектором каждого документа в пространстве терминов. Эти векторы документов, расположенные на крайне небольшом расстоянии от вектора запроса, считаются очень схожими с запросом. Чем больше схожесть, тем больше релевантность документа по отношению к поисковому запросу.
Измерение векторного расстояния учитывает и направление, и длину каждого вектора. Это важно, поскольку можно рассчитать сходство между запросом и большими и малыми документами, а также получить различные результаты в зависимости от длины.
Существуют и другие особенности работы алгоритма. Например, алгоритм должен учитывать, что более длинные документы добавляют больше веса определенным словам, нежели короткие. Следовательно, необходима нормализация документов. Также известно, что многие термины, встречающиеся чаще всего, несущественны с точки зрения значения. Они просто заполняют пространство и создают "шум". Такие слова, как артикли, занимают большую часть документа, но не определяют его уникальность, и, следовательно, не играют большой роли в определении релевантности, даже несмотря на векторно-пространственное расстояние. Эти стоп-слова можно добавить в специальный список. В этом случае алгоритм сможет обработать список стоп-слов и извлечь каждое слово из матрицы терминов и документов. Это значительно повысит производительность алгоритма за счет сокращения количества обрабатываемых слов, поскольку слова, которые изначально не соответствуют поисковому запросу, будут проигнорированы.
Кроме стоп-слов остаются еще тысячи разных слов. Интересен ли пользователю, который ищет слово "dogs", документ, в котором несколько раз используется слово "dog"? Мы полагаем, что да. Поскольку алгоритм является символьным, он работает со словами как с символами и понимает их не так, как человек: алгоритм не способен понять, что "dogs" и "dog" имеют схожее значение. Следовательно, еще один способ повышения релевантности документа заключается в том, чтобы показать, что "dogs" и "dog" – это разные формы слова, которые указывают на одно и то же понятие. Применяемый при этом алгоритм называется морфологическим поиском. Вместо фактически набранного/сохраненного слова учитывается его основа. Теперь каждое употребление слова "dogs" рассматривается так же, как и употребление слова "dog". В результате многие документы, в которых используется форма множественного числа, и документы, в которых поисковый запрос включает форму единственного числа, считаются похожими.
Объем настоящего руководства не позволяет нам в полной мере раскрыть принцип работы современных поисковых алгоритмов. Более подробную информацию вы можете найти самостоятельно. В сети Интернет по запросу "поиск в векторном пространстве" доступно множество результатов. Для полного понимания алгоритма потребуются серьезные знания математики. Ниже приведены ключевые факты об алгоритме определения релевантности:
-
Документы, в которых слова из поискового запросе встречаются чаще, будут иметь более высокую релевантность.
-
Документы с более высокой плотностью найденных ключевых слов (слова расположены ближе друг к другу), будут иметь более высокую релевантность, чем документы с редким употреблением искомых слов.
Одним из возможных недостатков определения релевантности системой PolyAnalyst является то, что большой документ может быть таким же важным, как и небольшой, поскольку длина документа (число слов в документе) имеет значение.
Порядок слов в запросе не влияет на релевантность. Поиск "dog and cat" равносилен запросу "cat and dog", т.е. слово, которое стоит первым в запросе, не имеет приоритета перед остальными.
Если вы хотите узнать больше о том, как работает поиск в векторном пространстве, посетите следующие сайты:
-
Создание поискового запроса в векторном пространстве в Perl: http://www.perl.com/pub/a/2003/02/19/engine.html;
-
Векторно-пространственная модель (Википедия): ru.wikipedia.org/wiki/Векторная_модель