Algorithme de Rocchio

L' algorithme de Rocchio est basé sur une méthode de rétroaction de pertinence que l'on retrouve dans les systèmes de recherche d'informations issus du système de recherche d'informations SMART développé entre 1960 et 1964. Comme de nombreux autres systèmes de recherche, l' algorithme de Rocchio a été développé en utilisant le modèle d'espace vectoriel . Son hypothèse sous-jacente est que la plupart des utilisateurs ont une conception générale des documents qui doivent être considérés comme pertinents ou non pertinents. Par conséquent, la requête de recherche de l'utilisateur est révisée pour inclure un pourcentage arbitraire de documents pertinents et non pertinents afin d'augmenter le taux de rappel du moteur de recherche , et éventuellement la précision également. Le nombre de documents pertinents et non pertinents autorisés à entrer dans une requête est dicté par ce que l'on appelle les poids , c'est-à-dire les variables , et répertoriés ci-dessous dans la section Algorithme .

La formule et les définitions des variables pour le feedback de pertinence de Rocchio sont les suivantes :

Comme le montre la formule, les pondérations associées ( , , ) sont responsables de la mise en forme du vecteur modifié dans une direction plus proche ou plus éloignée de la requête d'origine, des documents associés et des documents non associés. En particulier, les valeurs de et doivent être incrémentées ou décrémentées proportionnellement à l'ensemble des documents classés par l'utilisateur. Si l'utilisateur décide que la requête modifiée ne doit pas contenir de termes de la requête d'origine, des documents associés ou des documents non associés, la valeur de pondération correspondante ( , , ) pour la catégorie doit être définie sur 0.

Dans la dernière partie de l'algorithme, les variables , et sont présentées comme des ensembles de vecteurs contenant les coordonnées de documents liés et de documents non liés. Dans la formule, et sont les vecteurs utilisés pour parcourir les deux ensembles et et pour former des sommes vectorielles . Ces sommes sont normalisées, c'est-à-dire divisées par la taille de leur ensemble de documents respectif.

Afin de visualiser les changements qui se produisent sur le vecteur modifié, veuillez vous référer à l'image ci-dessous. Lorsque les poids augmentent ou diminuent pour une catégorie particulière de documents, les coordonnées du vecteur modifié commencent à se rapprocher ou à s'éloigner du centroïde de la collection de documents. Ainsi, si le poids augmente pour les documents associés, les coordonnées des vecteurs modifiés refléteront le fait d'être plus proches du centroïde des documents associés.

La complexité temporelle de la formation et du test de l'algorithme est indiquée ci-dessous et suivie de la définition de chaque variable . Notez que lors de la phase de test, la complexité temporelle peut être réduite à celle du calcul de la distance euclidienne entre un centroïde de classe et le document correspondant. Comme le montre : .

Formation = Test =

Bien qu'il y ait des avantages à classer les documents comme non pertinents, un classement de documents pertinents permettra de mettre à la disposition de l'utilisateur des documents plus précis. Par conséquent, les valeurs traditionnelles des pondérations de l'algorithme ( , , ) dans la classification de Rocchio sont généralement d'environ = 1, = 0,8 et = 0,1. Les systèmes modernes de recherche d'informations ont évolué vers l'élimination des documents non liés en définissant c = 0 et en ne prenant ainsi en compte que les documents liés. Bien que tous les systèmes de recherche n'aient pas éliminé le besoin de documents non liés, la plupart ont limité les effets sur la requête modifiée en ne prenant en compte que les documents non liés les plus forts de l' ensemble.

L'algorithme de Rocchio ne parvient souvent pas à classer les classes et les relations multimodales. Par exemple, le pays de Birmanie a été renommé Myanmar en 1989. Par conséquent, les deux requêtes « Birmanie » et « Myanmar » apparaîtront beaucoup plus éloignées dans le modèle d'espace vectoriel , bien qu'elles contiennent toutes deux des origines similaires.