Erweitertes Boolesches Retrieval

Erweitertes Boolesches Retrieval

Ein erweitertes Boolsches Modell wird definiert durch den 4-Tupel (T, Q, D, rank(.,.)) mit

T = {t_i | i = 1, ..., n}: Menge der Indexterme, die Dokumente und Queries beschreiben.
Q = {q_j | i = 1, ...}: Menge aller erlaubten Queries.
D = {d_k | k = 1, ..., m}: Menge der vorliegenden Dokumente. Bei den erweiterten Boolschen Modellen besitzt jeder Term t_ki eines Dokumentes d_k ein Gewicht w_ki ∈ [0,1], welches die Wichtigkeit des Termes im Dokument repräsentiert. Ein Dokument d_k besitzt somit die Struktur d_k = ((t_k1, w_k1), ..., (t_kn, w_kn)).
rank(.,.): Rankingfunktion, welche die Ähnlichkeit eines Dokumentes mit einer Query beschreibt. Sie ist allgemein definiert durch: rank(d_k, q_j): D x Q -> [0,1]: (d_k, q_j) |-> rank(d_k, q_j) ∈ [0,1].

Die Rankingfunktion beschreibt die unterschiedlichen Klassen von erweiterten Boolschen Modellen, wobei alle Modelle zwischen der Verwendung der logischen Operatoren AND und OR in der Query unterscheiden.

Table of contents

1 Erweiterte Boolsche Modelle ohne Query-Gewichte
2 Erweiterte Boolsche Modelle mit Query-Gewichten
3 Literatur

Erweiterte Boolsche Modelle ohne Query-Gewichte

Bei dieser Klasse von Modellen wird jede Query repräsentiert als eine Kombinationen der Indexterme und der logischen Operatoren AND, OR, NOT unter der möglichen Verwendung von beliebig geklammerten Ausdrücken. Es wird angenommen, dass alle Terme die gleiche Bedeutung besitzen, was durch fehlende Termgewichte in der Query repräsentiert ist. Folgende erweiterte Boolsche Modelle lassen sich unterscheiden:

1) Einfache Fuzzy-Mengen-Modell [Buell (1981), Bookstein (1980), Radecki (1979)]

rank(d_k, t₁ AND t₂) = MIN{w_k1, w_k2};

rank(d_k, t₁ OR t₂) = MAX{w_k1, w_k2}.

Dieses einfache Modell besitzt die Einschränkung, dass es nur zwei Terme evaluieren kann, im Gegensatz zu den folgenden Modellen, die beliebig viele Terme verarbeiten können.

2) \'Waller-Kraft-Modell' [Waller&Kraft (1979)]

rank(d_k, t₁ AND ... AND t_n) = (1 - γ) · MIN{w_k1, ..., w_kn} + γ · MAX{w_k1, ..., w_kn}, 0 ≤ γ ≤ 0,5;

rank(d_k, t₁ OR ... OR t_n) = (1 - γ) · MIN{w_k1, ..., w_kn} + γ · MAX{w_k1, ..., w_kn}, 0,5 ≤ γ ≤ 1.

3) Paice-Modell [Paice (1984)]

Bei einer AND-Verknüpfung ordne zunächst die Gewichte w_ki mit ansteigenden Werten, d.h. w_k1 ≤ ... ≤ w_kn, und berechne dann

rank(d_k, t₁ AND ... AND t_n) = [∑_i=1ⁿ (r^i-1 · w_ki)]/[∑_i=1ⁿ r^i-1], 0 ≤ r ≤ 1.

Bei einer OR-Verknüpfung ordne zunächst die Gewichte w_ki mit absteigenden Werten, d.h. w_k1 ≥ ... ≥ w_kn, und berechne dann

rank(d_k, t₁ OR ... OR t_n) = [∑_i=1ⁿ (r^i-1 · w_ki)]/[∑_i=1ⁿ r^i-1], 0 ≤ r ≤ 1.

4) P-Norm-Modell [Salton et al. (1983)]

rank(d_k, t₁ AND ... AND t_n) = 1 - [1/n · ∑_i=1ⁿ (1 - w_ki)^p]^1/p, 1 ≤ p < ∞,

rank(d_k, t₁ OR ... OR t_n) = 1 - [1/n · ∑_i=1ⁿ (w_ki)^p]^1/p, 1 ≤ p < ∞.

5) Infinite-One-Modell [Smith (1990)]

rank(d_k, t₁ AND ... AND t_n) = γ · [1 - MAX{1 - w_k1, ..., 1 - w_kn}] + (1 - γ) · [1/n · ∑_i=1ⁿ w_ki], 0 ≤ γ ≤ 1;

rank(d_k, t₁ OR ... OR t_n) = γ · MAX{w_k1, ..., w_kn} + (1 - γ) · [1/n · ∑_i=1ⁿ w_ki], 0 ≤ γ ≤ 1.

Erweiterte Boolsche Modelle mit Query-Gewichten

Die Retrieval-Effektivität lässt sich steigern, indem den Termen Wichtigkeitsfaktoren in Form von Gewichten zugeordnet werden. Eine Query q_j bekommt somit eine Struktur analog zu einem Dokument d_k mit Tupeln aus Termen und Gewichten. Werden Terme, die nicht in der Ursprungs-Query auftreten mit einem Gewicht von Null kodiert, so kann jede Ursprungs-Query in eine Query umkodiert werden, die alle in T vorkommenden Terme mit berücksichtigt:

q_j = ((t_q(j)1, w_q(j)1), ..., (t_q(j)n, w_q(j)n)).

Bei den Relevanz-Gewichtungs Ansätzen (siehe Buell (1981)) werden die Rankingfunktionen derart reformuliert, dass die Gewichte der Dokumente und Queries multipliziert werden, d.h.:

rank(d_k, (t_q(j), w_q(j))) = w_k · w_q(j).

Unter dieser Annahme sind von den vorgestellten erweiterten Boolschen Modellen das P-Norm- und das Infinite-One-Modell in der Lage, die Gewichte in den Dokumenten und einer Query zu evaluieren:

1) P-Norm-Modell mit Query-Gewichten

rank(d_k, (t_q(j)1, w_q(j)1) AND ... AND (t_q(j)n, w_q(j)n)) = 1 - [[∑_i=1ⁿ (1 - w_ki)^p · w_q(j)i^p]/[∑_i=1ⁿ w_ki^p]]^1/p, 1 ≤ p < ∞,

rank(d_k, (t_q(j)1, w_q(j)1) OR ... OR (t_q(j)n, w_q(j)n)) = 1 - [[∑_i=1ⁿ w_ki^p · w_q(j)i^p]/[∑_i=1ⁿ w_ki^p]]^1/p, 1 ≤ p < ∞.

2) Infinite-One-Modell mit Query-Gewichten

rank(d_k, (t_q(j)1, w_q(j)1) AND ... AND (t_q(j)n, w_q(j)n)) =

γ · [1 - [[MAX{(1 - w_k1) · w_q(j)1, ..., (1 - w_kn) · w_q(j)n}]/[MAX{w_q(j)1, ..., w_q(j)n}]] + (1 - γ) · [[∑_i=1ⁿ (w_ki · w_q(j)i]/[∑_i=1ⁿ w_q(j)i]], 0 ≤ γ ≤ 1;

rank(d_k, (t_q(j)1, w_q(j)1) OR ... OR (t_q(j)n, w_q(j)n)) =

γ · [MAX{w_k1 · w_q(j)1, ..., w_kn · w_q(j)n}]/[MAX{w_q(j)1, ..., w_q(j)n}] + (1 - γ) · [[∑_i=1ⁿ (w_ki · w_q(j)i)]/[∑_i=1ⁿ w_q(j)i]], 0 ≤ γ ≤ 1.

Literatur

Buell, D.A.: A general model for query processing in information retrieval system. In: Information Processing and Management, 17, 1981, S. 249 - 262.

Bookstein, A.: Fuzzy requests: an approach to weighted boolean searches. In: Journal of the American Society for Information Science, 31, 1980, S. 240 - 247.

Fox, E.A.; Betrabet, S.; Koushik, M.; Lee, W.: Extended boolean models. In: Frankes, W.B.; Yates, R.B. (eds): Information Retrieval Data Structures and Algorithms. Prentice Hall, 1992, S. 393 - 418.

Kim, M.H.; Lee, J.H.; Lee, Y.J.: Analysis of fuzzy operators for high quality information retrieval. In: Information Processing Letters, 46 (5), 1993, S. 251 - 256.

Lee, J.H.; Kim, M.H.; Lee, Y.J.: Ranking documents in thesaurus-based boolean retrieval systems. In: Information Processing and Management, 30, 1994, S. 79 - 91.

Lee, J.H.; Kim, M.I.I.; Lee, Y.J.: Enhancing the fuzzy set model for high quality document rankings. In: Proceedings of the 19th Euromicro Conference.1992, S. 337 - 344.

Lee, J.H.; Kim, W.Y.; Kim, M.H.; Lee, Y.J.: On the evaluation of boolean operators in the extended boolean retrieval framework. In: SIGIR 1993, 1993, S. 291 - 297.

Lee, Joon Ho: Properties of extended Boolean models in information retrieval. In: Croft & Rijsbergen (1994): SIGIR 1994, S. 182 - 190.

Paice, C.P.: Soft evaluation of boolean search queries in information retrieval systems. In: Information Technology: Research and Development, 3 (1), 1984, S. 33 - 42.

Radecki, T.: Fuzzy set theoretical approach to document retrieval. In: Information Processing and Management, 15, 1979, S. 247 - 259.

Sachs, W.M.: An approach to associative retrieval through the theory of fuzzy sets. In: Journal of the American Society for Information Science, 27, 1976, S. 85 - 87.

Salton, G.; Fox, E.A.; Wu, H.: Extended boolean information retrieval. In: Communication of the ACM, 26(11), 1983, S. 1022 - 1036.

Smith, M.E.: Aspekts of the p-norm model of information retrieval: syntactic query generation, efficiency, and theoretical properties. PhD thesis, Cornell University, 1990.

Waller, W.G.; Kraft, D.H.: A mathematical Model for weighted Boolean retrieval systems. In: Information Processing and Management, 15, 1979, S. 235 -245.