Algoritmo de Rocchio

El algoritmo de Rocchio se basa en un método de retroalimentación de relevancia que se encuentra en los sistemas de recuperación de información que se originó a partir del Sistema de recuperación de información SMART desarrollado entre 1960 y 1964. Al igual que muchos otros sistemas de recuperación, el algoritmo de Rocchio se desarrolló utilizando el modelo de espacio vectorial . Su suposición subyacente es que la mayoría de los usuarios tienen una concepción general de qué documentos deben denotarse como relevantes o irrelevantes. ^[1] Por lo tanto, la consulta de búsqueda del usuario se revisa para incluir un porcentaje arbitrario de documentos relevantes e irrelevantes como un medio para aumentar la recuperación del motor de búsqueda y posiblemente también la precisión. La cantidad de documentos relevantes e irrelevantes que se permiten para ingresar en una consulta está dictada por los llamados pesos , es decir, las variables , y se enumeran a continuación en la sección Algoritmo . ^[1] ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$

Algoritmo

La fórmula y las definiciones de variables para la retroalimentación de relevancia de Rocchio son las siguientes: ^[1]

${\displaystyle {\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}}$

Como se demuestra en la fórmula, los pesos asociados ( , , ) son responsables de dar forma al vector modificado en una dirección más cercana o más lejana de la consulta original, los documentos relacionados y los documentos no relacionados. En particular, los valores de y deben incrementarse o decrementarse proporcionalmente al conjunto de documentos clasificados por el usuario. Si el usuario decide que la consulta modificada no debe contener términos de la consulta original, los documentos relacionados o los documentos no relacionados, entonces el valor del peso correspondiente ( , , ) para la categoría debe establecerse en 0. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$

En la parte posterior del algoritmo, las variables , y se presentan como conjuntos de vectores que contienen las coordenadas de documentos relacionados y no relacionados. En la fórmula, y son los vectores utilizados para iterar a través de los dos conjuntos y y formar sumas vectoriales . Estas sumas se normalizan, es decir, se dividen por el tamaño de su respectivo conjunto de documentos. ${\displaystyle D_{r}}$ ${\displaystyle D_{nr}}$ ${\displaystyle {\vec {D}}_{j}}$ ${\displaystyle {\vec {D}}_{k}}$ ${\displaystyle D_{r}}$ ${\displaystyle D_{nr}}$

Para visualizar los cambios que se producen en el vector modificado, consulte la imagen siguiente. ^[1] A medida que se aumentan o disminuyen los pesos de una categoría particular de documentos, las coordenadas del vector modificado comienzan a acercarse o alejarse del centroide de la colección de documentos. Por lo tanto, si se aumenta el peso de los documentos relacionados, las coordenadas de los vectores modificados reflejarán que están más cerca del centroide de los documentos relacionados.

Complejidad temporal

A continuación se detalla la complejidad temporal para el entrenamiento y la prueba del algoritmo, seguida de la definición de cada variable . Tenga en cuenta que, durante la fase de prueba, la complejidad temporal se puede reducir a la del cálculo de la distancia euclidiana entre un centroide de clase y el documento respectivo. Como se muestra en: . ${\displaystyle \Theta (\vert \mathbb {C} \vert M_{a})}$

Entrenamiento = Prueba = ^[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})}$

Uso

Clasificación de Rocchio

Aunque clasificar los documentos como no relevantes tiene sus ventajas, una clasificación de documentos relevantes dará como resultado que se pongan a disposición del usuario documentos más precisos. Por lo tanto, los valores tradicionales para los pesos del algoritmo ( , , ) en la clasificación de Rocchio suelen rondar = 1, = 0,8 y = 0,1. Los sistemas de recuperación de información modernos han avanzado hacia la eliminación de los documentos no relacionados estableciendo c = 0 y, por lo tanto, solo teniendo en cuenta los documentos relacionados. Aunque no todos los sistemas de recuperación han eliminado la necesidad de documentos no relacionados, la mayoría ha limitado los efectos en la consulta modificada al tener en cuenta solo los documentos no relacionados más sólidos del conjunto. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle D_{nr}}$

Limitaciones

El algoritmo de Rocchio a menudo no clasifica las clases y relaciones multimodales. Por ejemplo, el país de Birmania cambió su nombre a Myanmar en 1989. Por lo tanto, las dos consultas de "Birmania" y "Myanmar" aparecerán mucho más alejadas en el modelo de espacio vectorial , aunque ambas tengan orígenes similares. ^[1]

Véase también

• Clasificador de centroide más cercano , también conocido como clasificador de Rocchio

Referencias

1. Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze: Introducción a la recuperación de información , páginas 163-167. Cambridge University Press, 2009.

• Retroalimentación de relevancia en la recuperación de información
• Retroalimentación de relevancia y ampliación de consultas
• Clasificación del espacio vectorial
• Clasificación de datos