Алгоритм Роккио

Алгоритм Роккио основан на методе обратной связи по релевантности , обнаруженном в системах информационного поиска , который произошел от системы информационного поиска SMART, разработанной между 1960 и 1964 годами. Как и многие другие поисковые системы, алгоритм Роккио был разработан с использованием модели векторного пространства . Его основополагающее предположение заключается в том, что большинство пользователей имеют общее представление о том, какие документы следует обозначить как релевантные или нерелевантные. ^[1] Поэтому поисковый запрос пользователя пересматривается и включает в себя произвольный процент релевантных и нерелевантных документов в целях повышения поисковой системы и запоминаемости , возможно, также точности. Количество релевантных и нерелевантных документов, разрешенных для ввода в запрос, определяется весами переменных a, b, c, перечисленных ниже в разделе «Алгоритм» . ^[1]

Алгоритм

Формула : и определения переменных для обратной связи по релевантности Роккио следующие ^[1]

${\vec {Q}}_{m}=a\,{\vec {Q}}_{o}+b\,{\frac {1}{|D_{r}|}}\sum _{{\vec {D}}_{j}\in D_{r}}{\vec {D}}_{j}-c\,{\frac {1}{|D_{nr}|}}\sum _{{\vec {D}}_{k}\in D_{nr}}{\vec {D}}_{k}$

Переменная	Ценить
${\vec {Q}}_{m}$	Модифицированный вектор запроса
${\vec {Q}}_{o}$	Исходный вектор запроса
${\vec {D}}_{j}$	Вектор связанного документа
${\vec {D}}_{k}$	Вектор несвязанных документов
$a$	Исходный вес запроса
$b$	Сопутствующие документы Вес
$c$	Вес несвязанных документов
$D_{r}$	Комплект сопутствующих документов
$D_{nr}$	Набор несвязанных документов

Как показано в формуле, связанные веса (a, b, c) отвечают за формирование модифицированного вектора в направлении ближе или дальше от исходного запроса, связанных и несвязанных документов. В частности, значения b и c должны увеличиваться или уменьшаться пропорционально набору документов, классифицированных пользователем. Если пользователь решает, что измененный запрос не должен содержать термины ни из исходного запроса, ни из связанных документов, ни из несвязанных документов, то соответствующее значение веса (a, b, c) для категории должно быть установлено равным 0.

В более поздней части алгоритма переменные $D_{r}$ , и $D_{nr}$ представлены как наборы векторов, содержащих координаты связанных и несвязанных документов. Хотя $D_{r}$ и $D_{nr}$ сами по себе не являются векторами, ${\vec {D}}_{j}$ и ${\vec {D}}_{k}$ — векторы, используемые для перебора двух наборов и формирования векторных сумм . Эти суммы нормализуются (делятся) на размер соответствующего набора документов ( $D_{r}$ , $D_{nr}$ ).

Чтобы визуализировать изменения, происходящие с модифицированным вектором, обратитесь к изображению ниже. ^[1] По мере увеличения или уменьшения весов для определенной категории документов координаты модифицированного вектора начинают перемещаться либо ближе, либо дальше от центроида коллекции документов. Таким образом, если вес для связанных документов увеличивается, то координаты измененных векторов будут отражать близость к центроиду связанных документов.

Временная сложность

Переменная	Ценить
$\mathbb {D}$	Маркированный набор документов
$L_{ave}$	Среднее количество токенов на документ
$\mathbb {C}$	Набор классов
$V$	Словарь/набор терминов
$L_{a}$	Количество токенов в документе
$M_{a}$	Количество типов в документе

Временная сложность обучения и тестирования алгоритма указана ниже, после чего следует определение каждой переменной . Обратите внимание, что на этапе тестирования временная сложность может быть уменьшена до расчета евклидова расстояния класса между центроидом и соответствующим документом. Как показано: $\Theta (\vert \mathbb {C} \vert M_{a})$ .

Обучение = $\Theta (\vert \mathbb {D} \vert L_{ave}+\vert \mathbb {C} \vert \vert V\vert )$
Тестирование = $\Theta (L_{a}+\vert \mathbb {C} \vert M_{a})=\Theta (\vert \mathbb {C} \vert M_{a})$ ^[1]

Использование

Хотя ранжирование документов как нерелевантных имеет свои преимущества, соответствующее ранжирование документов приведет к тому, что пользователю станут доступны более точные документы. Следовательно, традиционные значения весов алгоритма (a, b, c) в классификации Роккио обычно составляют около a = 1, b = 0,8 и c = 0,1. Современные системы поиска информации перешли к исключению несвязанных документов, установив c = 0 и, таким образом, учитывая только связанные документы. Хотя не все поисковые системы устранили необходимость в несвязанных документах, большинство из них ограничили влияние модифицированного запроса, учитывая только самые сильные несвязанные документы в $D_{nr}$ набор.

Ограничения

Алгоритм Роккио часто не может классифицировать мультимодальные классы и отношения. Например, страна Бирма была переименована в Мьянму в 1989 году. Таким образом, два запроса «Бирма» и «Мьянма» будут располагаться гораздо дальше друг от друга в модели векторного пространства , хотя оба они имеют схожее происхождение. ^[1]

См. также

Классификатор ближайшего центроида , он же классификатор Роккио

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Кристофер Д. Мэннинг, Прабхакар Рагхаван, Хинрих Шютце: Введение в поиск информации , страницы 163–167. Издательство Кембриджского университета, 2009.

[ir-manning-1] Jump up to: ^а ^б ^с ^д ^и ^ж Кристофер Д. Мэннинг, Прабхакар Рагхаван, Хинрих Шютце: Введение в поиск информации , страницы 163–167. Издательство Кембриджского университета, 2009.

[1]