Modèle booléen

Un modèle booléen est une méthode ensembliste de représentation du contenu d'un document. C'est l'un des premiers modèles utilisés en recherche d'information, permettant de fouiller automatiquement les grand corpus de bibliothèques. Il en existe un modèle étendu qui généralise également le modèle vectoriel.

Modèle standard

Le modèle booléen est une représentation mathématique du contenu d'un document, selon une approche ensembliste.

Les documents sont représentés par des ensembles de termes et les requêtes traitées comme des expressions logiques. Considérant un vocabulaire $T={t_1,\dots,t_m}$ , un document est caractérisé par la présence ou l'absence de chaque $t i$ dans son contenu. La requête s'exprime alors avec des opérateurs logiques selon le formalisme de l'algèbre de Boole. Un document du corpus est ainsi considéré comme pertinent uniquement quand son contenu est vrai pour l'expression de la requête.

Avantages et inconvénients

La simplicité du modèle le rend aisément compréhensible pour un utilisateur. Dans le cas de corpus explorés par des spécialistes, ayant notamment une très bonne connaissance du vocabulaire, cela le rend très efficace.

Cette simplicité le rend néanmoins peu adapté à des recherches sur des corpus généralistes, surtout lorsque les utilisateurs n'ont pas d'expertise sur ce dernier. En particulier, la formulation des requêtes devient vite laborieuse quand la requête se fait précise (donc longue). Un autre inconvénient majeur du modèle dans sa version la plus simple est l'impossibilité de rendre compte d'une correspondance partielle d'un document à une requête. Enfin, la pondération binaire des termes du vocabulaire limite la pertinence des résultats et ne permet pas de les ordonner.

Une part des inconvénients du modèle booléen standard est corrigé avec l'utilisation du modèle vectoriel ou du modèle booléen étendu.

Modèle étendu

L'extension du modèle booléen standard généralise également le modèle vectoriel. Il consiste principalement à pondérer les termes des documents au moyen d'un schéma tel celui du TF-IDF. Elle a été proposée par Salton, Fox et Wu en 1983^[1]

Si on munit l'espace (vectoriel) de représentation d'une métrique Lp, un document peut ainsi appartenir à l'intérieur de la boule ouverte définie par l'intersection de la boule unité et de $\mathbb{R}^*_+$ (autrement dit « entre 0 et 1 pour chaque dimension »), alors que le modèle booléen standard le contraint à appartenir à l'adhérence de celle-ci (i.e ses coordonnées ne peuvent que $0$ ou $1$ ).

Dans le cas d'une requête comportant deux termes, une condition logique de type ET est alors représentée par la distance entre le document est les coordonnées « idéales » $(1,1)$ tandis qu'une condition de type OU est calculée par la distance du document à l'origine. Cette définition peut être généralisée à un nombre quelconque de termes.

Formulation pour deux termes

Similarité d'une requête de type ET ( $T_1 \land T_2$ ) entre une requête

q

et les documents

D j

D j + 1

Considérons le cas d'un requête ne comportant que deux termes $T 1$ et $T 2$ et examinons le cas des requêtes disjonctives ( $T 1$ ET $T 2$ ) et conjonctives ( $T 1$ OU $T 2$ ), le but étant d'ordonner les documents $D j$ en réponse à cette requête $q$ .

Dans le cas d'une requête $q=T_1 \land T_2$ (i.e $T 1$ ET $T 2$ ), le point idéal est (1,1) représentant le cas où les deux termes sont présents dans le document. Ainsi, la similarité de la requête $q$ à un document est donnée par:

$sim(q_{or},d)=1-\sqrt{\frac{(1-w_1)^2+(1-w_2)^2}{2}}$

Similarité d'une requête de type OU $T_1 \lor T_2$ entre une requête

q

et les documents

D j

D j + 1

Dans le cas de la requête $q=T_1 \lor T_2$ (i.e $T 1$ OU $T 2$ ) il s'agit d'être le plus éloigné possible de l'origine $(0,0)$ qui représente le pire cas où aucun des deux termes n'est présent. Ainsi:

$sim(q_{and},d)=\sqrt{\frac{w_1^2+w_2^2}{2}}$

Généralisation à un nombre quelconque de termes

Les requêtes conjonctives et disjonctives peuvent être généralisées aux cas où la requête comporte plus de deux termes ( $m$ termes). On utilise pour cela les p-normes qui dépendent d'une paramètre $p$ pouvant varier dans l'ensemble des entiers naturels. La généralisation de la similarité conjonctive (OU) s'exprime ainsi:

$sim(q_{or},D_j)=\sqrt[p]{\frac{w_1^p+w_2^p+....+w_m^p}{m}}$

Et la généralisation d'une requête disjonctive (ET) par:

$sim(q_{and},D_j)=1-\sqrt[p]{\frac{(1-w_1)^p+(1-w_2)^p+....+(1-w_m)^p}{m}}$

Quand le paramètre p=1 on retrouve le cas du modèle vectoriel tandis que lorsque p tend vers l'infini, on se ramène au cas du modèle booléen standard, avec des requêtes ET et OU strictes. En ce sens, le modèle booléen étendu est une généralisation de ces deux modèles.

Combinaison de requêtes conjonctives et disjonctives

La généralisation précédente s'applique à des requêtes conjonctives ou disjonctives « pures », c'est-à-dire ne comportant que l'un des opérateur ET ou OU à l'exclusion de l'autre. Le modèle booléen étendu permet néanmoins de les combiner les opérateurs^[2] au moyen de regroupements récursifs.

Par exemple, pour la requête $q=(T_1 \land T_2) \lor T_3$ , la similarité entre la requête $q$ et un document $D$ comportant les trois termes pourra s'exprimer par:

$sim(q,D)=\sqrt[p]{\frac{\left( 1-\sqrt[p]{(\frac{(1-w_1)^p+(1-w_2)^p}{2}})\right)^p + w_3^p}{2}}$

Voir aussi

Liens externes

(en) modèle booléen étendu

Références

↑ Gerard Salton,Edward A. Fox, Harry Wu, Extended Boolean information retrieval, Communications of the ACM,Volume 26 , Issue 11 ,1983
↑ R. Baeza-Yates, B. Ribeiro-Neto; Modern Information Retrieval Chapter 2, p. 40; Addison-Wesley (1999)

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Modèle booléen de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

Modèle vectoriel — Un modèle vectoriel (parfois nommé sémantique vectorielle) est une méthode algébrique de représentation d un document visant à rendre compte de sémantique. Elle est utilisée en recherche d information, notamment pour la recherche documentaire, la … Wikipédia en Français
Modèle probabiliste de pertinence — Le modèle probabiliste de pertinence est une méthode probabiliste de représentation du contenu d un document, proposée en 1976 par Robertson et Jones[1]. Elle est utilisée en recherche d information pour exprimer une estimation de la probabilité… … Wikipédia en Français
booléen — booléen, enne [ buleɛ̃, ɛn ] adj. • v. 1950; du mathématicien angl. G. Boole ♦ Math., log., inform. Relatif à l algèbre de Boole. Variable booléenne, qui ne peut prendre que deux valeurs distinctes. ⇒ binaire. On dit aussi boolien, ienne et… … Encyclopédie Universelle
Modèle lecteurs-rédacteurs — Problème des lecteurs et des rédacteurs Le problème des lecteurs et des rédacteurs est un problème classique en théorie informatique, qui permet de modéliser les accès à des bases de données. Il fut énoncé sous cette forme par Edsger Dijkstra,… … Wikipédia en Français
TF-IDF — Le TF IDF (de l anglais Term Frequency Inverse Document Frequency) est une méthode de pondération souvent utilisée en recherche d information et en particulier dans la fouille de textes. Cette mesure statistique permet d évaluer l importance d un … Wikipédia en Français
BOOLE (ALGÈBRE ET ANNEAU DE) — BOOLE ALGÈBRE & ANNEAU DE La notion d’algèbre de Boole, introduite par G. Boole (1847) et par A. De Morgan afin d’algébriser les opérations propositionnelles de la logique, joue un rôle très utile dans plusieurs branches des mathématiques… … Encyclopédie Universelle
booléien — booléen, enne [ buleɛ̃, ɛn ] adj. • v. 1950; du mathématicien angl. G. Boole ♦ Math., log., inform. Relatif à l algèbre de Boole. Variable booléenne, qui ne peut prendre que deux valeurs distinctes. ⇒ binaire. On dit aussi boolien, ienne et… … Encyclopédie Universelle
Syntaxe JavaScript — Traduction à relire JavaScript syntax → … Wikipédia en Français
Syntaxe Javascript — Traduction à relire JavaScript syntax → … Wikipédia en Français
Lambda-Calcul — « La notion de λ définissabilité fut la première de ce qui est accepté maintenant comme l équivalent exact des descriptions mathématiques pour lesquelles des algorithmes existent. » Stephen Kleene, in Origins of Recursive Function … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Modèle booléen

Sommaire

Modèle standard

Avantages et inconvénients

Modèle étendu

Formulation pour deux termes

Généralisation à un nombre quelconque de termes

Combinaison de requêtes conjonctives et disjonctives

Voir aussi

Liens externes

Références

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Modèle booléen

Sommaire

Modèle standard

Avantages et inconvénients

Modèle étendu

Formulation pour deux termes

Généralisation à un nombre quelconque de termes

Combinaison de requêtes conjonctives et disjonctives

Voir aussi

Liens externes

Références

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link