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

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

Алгоритм [ править ]

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

${\ displaystyle {\ overrightarrow {Q_ {m}}} = {\ bigl (} a \ cdot {\ overrightarrow {Q_ {o}}} {\ bigr)} + ​​{\ biggl (} b \ cdot {\ tfrac { 1} {| D_ {r} |}} \ cdot \ sum _ {{\ overrightarrow {D_ {j}}} \ in D_ {r}} {\ overrightarrow {D_ {j}}} {\ biggr)} - {\ biggl (} c \ cdot {\ tfrac {1} {| D_ {nr} |}} \ cdot \ sum _ {{\ overrightarrow {D_ {k}}} \ in D_ {nr}} {\ overrightarrow { D_ {k}}} {\ biggr)}}$

Переменная	Ценить
${\ displaystyle {\ overrightarrow {Q_ {m}}}}$	Измененный вектор запроса
${\ displaystyle {\ overrightarrow {Q_ {o}}}}$	Исходный вектор запроса
${\ displaystyle {\ overrightarrow {D_ {j}}}}$	Связанный документ вектор
${\ displaystyle {\ overrightarrow {D_ {k}}}}$	Вектор несвязанного документа
${\ displaystyle a}$	Исходный вес запроса
${\ displaystyle b}$	Связанные документы Вес
${\ displaystyle c}$	Вес не относящихся к делу документов
${\ displaystyle D_ {r}}$	Комплект сопутствующих документов
${\ displaystyle D_ {nr}}$	Комплект документов, не относящихся к делу

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

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

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

Сложность времени [ править ]

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

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

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

Использование [ править ]

Классификация Роккио

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

Ограничения [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

• Отзыв о релевантности при поиске информации
• Отзыв о релевантности и расширение запроса
• Классификация векторных пространств
• Классификация данных