Vektorraum-Retrieval

Das Vektorraum-Retrieval ist ein Verfahren des Information Retrieval, bei dem Dokumente und Anfragen (Queries) als Punkte in einem hochdimensionalen, metrischen Vektorraum repräsentiert sind. Zum Retrieval wird die Distanz zwischen dem Queryvektor und dem Dokumentvektoren genutzt.

Der erste Schritt besteht in dem Aufbau eines Dokumentvektorenraumes DVR und der Dokument-Indexierung, bei welcher die Dokumente der Dokumentmenge auf jeweils genau einen Punkt (Dokumentvektoren) im DVR abgebildet werden. Hierzu existieren eine Vielzahl von Merkmalsgewichtungsmodellen, die alle auf der Häufigkeit von Merkmalen wie Termen, Lemmata oder n-Grammen in Einzeldokumenten sowie der gesamten Dokumentmenge aufbauen.

Das Retrieval im Vektorraummodell führt zunächst eine Query-Indexierung durch, bei welcher die Anfrage auf einen Vektor im Vektorraum abgebildet wird. Die nachfolgende Retrieval-Funktion ermittelt eine Teilmenge der Dokumentvektoren, die eine bestimmte Ähnlichkeit bezüglich dem Queryvektor besitzen, und die Rankingfunktion bildet diese Teilmenge auf eine geordnete Liste von Dokumentvektoren ab. Dem Nutzer, welcher die Query gestellt hat, wird eine Liste von Dokumenten präsentiert, welche zu der Liste der Dokumentvektoren korrespondiert.

Dokument-Indexierung im Vektorraummodell

Gegeben ist eine Dokumentmenge D = {D_i | i = 1, ..., m} mit m ∈ N Dokumenten zu einem Zeitpunkt t, wobei im weiteren vereinfachend D verwendet werden soll. Dokumente werden dabei allgemein als eine endliche Sequenz von Zeichen d_ij über einem endlichen Alphabet Φ betrachtet:

D_j = (d_jk | d_jk ∈ Φ).

Sei D(Φ) die Menge aller möglichen Zeichensequenzen über Φ. Von D(Φ) differenzieren muß man die Menge aller zugelassenen Dokumente D_VR-IR ⊂ D(Φ), da die Länge der Zeichensequenz einschränkt werden muss, weil in der Gesamtmenge D(Φ) so lange Sequenzlängen enthalten sind, die nicht sinnvoll verarbeitbar sind.

Ziel der Dokument-Indexierung ist es, jedem Dokument D_j genau ein Dokumentvektor x_j ∈ DVR als Repräsentation zuzuordnen, wobei den Dimensionen des betreffenden Dokumentvektorraumes DVR unterschiedliche Typen von Merkmalen (Feature) zugeordnet werden können:

• symbolische Merkmale, indem jedem Indexterm eine Dimension zugeordnet wird;
• subsymbolische Merkmale, indem z.B. jedem Zeichen-n-Gram eine Dimension zugeordnet wird.

Die Abbildung eines Dokumentes auf ein Dokumentvektor wird durch eine Dokument-Indexierungsfunktion A_VR-IR(D) durchgeführt. Wird angenommen, dass die Abbildung eines Dokumentes unabhängig von allen anderen Dokumenten aus D durchgeführt werden kann, so ergibt sich die Darstellung von A_VR-IR(D) mit D(Φ) als der Menge aller möglichen Zeichensequenzen über einem endlichen Alphabet Φ:

A_VR-IR(D): D_VR-IR -> DVR: D_j |-> x_j.

Es zeigt sich jedoch, dass die Eigenschaften aller restlichen m-1 Dokumente aus D verwendet werden müssen, um ein spezieles Dokument zu indexieren, sodass für die Indexierungsfunktion das (m-1)-fache Kreuzprodukt aus der Menge aller zugelassenen Zeichensequenzen verwendet werden muss:

A_VR-IR(D): D_VR-IR x D_VR-IR^m-1 -> DVR: (D_j, D \ {D_j}) |-> x_j.

Grundlage der unterschiedlichen Möglichkeiten, die Dokument-Indexierungsfunktion zu formulieren, sind die absoluten Häufigkeiten des Auftretens eines Merkmals (Feature F_i) in einem Dokument D_j, was mit h(F_i | D_j) bezeichnet werden soll, sowie die absoluten Häufigkeiten von F_i in der gesamten Dokumentmenge D, was mit h(F_i | D) bezeichnet werden soll.

Die allgemeine Vorgehensweise besteht darin, mit Hilfe der absoluten Häufigkeiten zunächst dokumentmengen-spezifische Merkmalsgewichtungen der Form w(F_i | D) zu berechnen, die mit Hilfe relativer Häufigkeiten h(F_i | D_j) in dokument-spezifische Merkmalsgewichtungen w(F_i | D_j) umgewandelt werden. Diese Merkmalsgewichtungen werden in den Dokumentvektoren als i'te Komponente x_ji eines Vektors x_j verwendet.

Beispiele für dokumentmengen-spezifische Merkmalsgewichtungen sind die logarithmische Gewichtung, mit m als der Anzahl der Dokumente:

w(F_i | D) = log_e[1+ [m/h(F_i | D)]]

oder die normalisierte logarithmische Gewichtung, mit h(F_max|D | D) als der absoluten Häufigkeit des Merkmals, welches in der Dokumentmenge am häufigsten auftritt:

w(F_i | D) = log_e[1+ [h(F_max|D | D)/h(F_i | D)]].

Weitere Beispiele sind die hyperbolische Gewichtung und die normalisierte hyperbolische Gewichtung:

w(F_i | D) = 1/h(F_i | D), w(F_i | D) = log_e[[m - h(F_i | D)]/[h(F_i | D)]].

Mit Hilfe des Informationsballastes (Salton & McGill (1987: 70)) bzw. des Rauschens noise(F_i | D) und des Signals sig(F_i | D) können weitere Maße definiert werden. Sei D(F_i) die Menge aller Dokumente aus D, in denen das Merkmal F_i auftritt, so gilt:

noise(F_i | D) = ∑_D(j) -[h(F_i | D_j)/h(F_i | D)] · log₂[h(F_i | D_j)/h(F_i | D)], ∀ D_j ∈ D(F_i); sig(F_i | D) = log₂[h(F_i | D) · noise(F_i | D)].

Aus diesen Maßen kann die Extropie

w(F_i | D)_Extropie = 1 - [noise(F_i | D)/log₂(m)],

sowie die folgenden drei Merkmalsgewichtungen abgeleitet werden:

w(F_i | D) = sig(F_i | D); w(F_i | D) = sig(F_i | D)/noise(F_i | D); w(F_i | D) = noise(F_i | D)_max - noise(F_i | D), mit noise(F_i | D)_max = max{noise(F_i | D) | ∀ F_i}.

Aus den dokumentmengenspezifischen Merkmalsgewichtungen w(F_i | D) werden dokumentspezifische Merkmalsgewichtungen w(F_i | D_j) erzeugt, die als Komponenten x_ji der Dokumentvektoren verwendet werden, indem die dokumentmengenspezifischen Merkmalsgewichtungen direkt übernommen werden, oder indem sie werden mit relativen Häufigkeiten r(F_i | D_j) multipliziert werden:

x_ji := w(F_i | D_j) = w(F_i | D), oder x_ji := w(F_i | D_j) = w(F_i | D) &midpoint; r(F_i | D_j).

Für die relativen Häufigkeiten r(F_i | D_j) existieren wiederum eine Reihe von verschiedenen Formulierungen. Die relative Häufigkeit für einen binären Vergleich wird definiert mit

r(F_i | D_j) = {1, wenn F_i ∈ F(D_j); 0, sonst.

Die logarithmische Häufigkeit wird definiert durch:

r(F_i | D_j) = 1 + log_e(h(F_i | D_j)).

Normalisierte relative Häufigkeiten werden angegeben mit dem Parameter K ∈ [0,3, 0,5], mit h(F_max|j | D_j) als der absoluten Häufigkeit des Merkmals F_max|j, das in D_j am häufigsten vorkommt:

r(F_i | D_j) = h(F_i | D_j)/h(F_max|j | D_j), oder r(F_i | D_j) = K + (1 - K) &midpoint; h(F_i | D_j)/h(F_max|j | D_j).

Werden auf diese Weise für alle Dokumente D_j aus der Dokumentmenge D genau ein Dokumentvektor x_j berechnet, so entsteht die Dokumentvektorenmenge DVM. Zu dieser Menge korrespondiert die Dokument-Term-Matrix, in der die Zeilen die Dokumentvektoren D_j und die Spalten die Merkmalsvektoren F_i repräsentieren. Die Zellen der m &midpoint; n-Matrix entsprechen den reellen Vektorkomponenten x_ji.

Dokument-Term-Matrix

Dj\Fi	F1	*	*	*	Fn
D1	x11	*	*	*	x1n
* * *	* * *	* * *	* * *	* * *	* * *
Dm	xm1	*	*	*	xmn

Metrik im Vektorraummodell

Unabhängig von der Dokument-Indexierung ist die Festlegung der Metrik im DVR, d.h. einer Distanzfunktion, die mehrere Zusatzbedingungen erfüllt, und mit der die Distanzen zwischen den Punkten im DVR eindeutig berechnet werden können. Eine entsprechende Metrik kann aus der Menge der möglichen bzw. sinnvoll für DVR verwendbaren Metriken stammen. Im weiteren soll M^DVR als die Menge der zugelassenen Metriken gelten, wobei eine mögliche parametrische Festlegung die Verwendung der Minkowski-Metrik ist:

M^DVR = {d_DVR(q_j, x_i, v) | d_DVR(q_j, x_i, v) = [∑_k=1ⁿ |q_jk - x_ik|^v]^1/v, v ∈ N }.

Retrieval im Vektorraummodell

Beim Retrieval wird durch einen Nutzer eine Query Q_j formuliert, die genau wie ein Dokument als eine endliche Zeichensequenz über endlichen Alphabet betrachtet wird. Vereinfachend wird angenommen, das beide Alphabete identisch sind, d.h. die Menge aller möglichen Zeichensequenzen einer Query soll gleich sein der Menge aller möglichen Zeichensequenzen eines Dokumentes:

Q(Φ) := D(Φ).

Für eine Query gilt somit in Analogie zu einem Dokument:

Q_j = (d_jk | d_jk ∈ Φ).

Mit der gleichen Argumentation wie bei den Dokumenten kann Q(Φ) von der Menge aller zugelassenen Suchfragen Q_VR-IR ⊂ Q(Φ) unterschieden werden, damit die Länge der Zeichensequenz einschränkt werden kann.

Indexierung der Query

Im ersten Schritt des Retrievals wird die Query Q_j durch eine Query-Indexierungsfunktion A_VR-IR(Q) abgebildet auf einen Queryvektor q_j, der Element des Dokumentvektorraumes DVR ist.

Die Query-Indexierung kann die Merkmalshäufigkeiten und -gewichtungen in analoger Weise wie die Dokument-Indexierung verwenden, d.h. die vorliegenden dokumentmengen-spezifischen Merkmalsgewichtungen w(F_i | D) werden durch Multiplikation mit relativen Häufigkeiten aus der Query zu queryspezifischen Merkmalsgewichtungen w(F_i | Q_j), die als Komponenten des Queryvektors verwendet werden. Dies bedeutet jedoch, dass potentiell alle n dokumentmengen-spezifischen Merkmalsgewichtungen verwendet werden müssen, die jeweils aus R, R⁺ oder [0, 1] stammen. Die Query-Indexierungsfunktion lässt sich somit definieren als:

A_VR-IR(Q): Q_VR-IR x Rⁿ -> DVR: (Q_j, w(F_i | D), i = 1, ..., n) |-> q_j.

Retrievalfunktion

Im nächsten Schritt wird mit einer Retrievalfunktion ret_VR-IR eine Teilmenge aus der Dokumentvektorenmenge DVM festgelegt, die in Abhängigkeit von dem Queryvektor q_j mit DVM_j bezeichnet wird. Sei P^DVM die Potenzmenge der Dokumentvektorenmenge, so ergibt sich die formale Spezifikation der Retrievalfunktion als:

ret_VR-IR: DVR^m x DVR x M^DVR x R⁺ -> P^DVM: (DVM, q_j, d_DVR, ε) |-> DVM_j.

Eine einfache Spezifizierung der Retrievalfunktion verwendet die Distanzen von q_j und allen Dokumentvektoren x_i, sowie ein Schwellenwert ε ∈ R⁺. Es werden alle Dokumentvektoren ermittelt, deren Abstand zu q_j kleiner ε ist, d.h. die in einer ε-Umgebung um q_j liegen:

DVM_j = {x_i | d_DVR(q_j, x_i) < ε, ∀ x_i ∈ DVM}.

Im einfachsten Fall könnte nun dem User, der die Query Q_j gestellt hat, die Dokumentmenge D(Q_j) als Retrievalergebnis präsentiert werden, die zu der Dokumentvektorenmenge DVM_j korrespondiert.

Rankingfunktion

Anstatt einer ungeordneten Dokumentmenge als Retrievalergebnis ist es jedoch besser, eine geordnete Liste zu präsentieren. Nachdem die Teilmenge DVM_j ermittelt wurde, soll diese in eine geordnete Liste umgewandelt werden, wobei dem Nutzer letztendlich die "vermutlich besten" Dokumente zuerst präsentiert werden sollen (Ranking). Dies geschieht durch die Rankingfunktion rank_VR-IR als Abbildung von DVM_j auf eine Liste der Dokumentvektoren DV_j unter Verwendung der Metrik d_DVR. Sei L^DVM die Menge aller möglichen Dokumentvektorlisten, die aus der Dokumentvektormenge DVM gebildet werden können, so ergibt sich für die formale Spezifikation der Rankingfunktion:

rank_VR-IR: DVR^m x M^DVR -> L^DVM: (DVM, d_DVR) |-> DV_j.

Naheliegend ist die Ordnung aller Dokumentvektoren aus DVM_j nach steigender Distanz zu dem Queryvektor q_j:

DV_j = (x_i | d_DVR(q_j, x_i) < d_DVR(q_j, x_i+1); ∀ x_i ∈ DVM_j).

Formale Beschreibung des Vektorraummodells

Fasst man die Betriebsarten Indexierung und Retrieval zusammen, so kann ein VR-IRS formal als 7-Tupel beschrieben werden, wenn die Möglichkeit des Relevanz-Feedbacks unberücksichtigt bleibt:

VR-IRS = (D_VR-IR, A_VR-IR(D), Q_VR-IR, A_VR-IR(Q), M^DVR, ret_VR-IR, rank_VR-IR), mit

• D_VR-IR: Menge aller zugelassenen Dokumente.

• A_VR-IR(D): Dokument-Indexierungsfunktion als Abbildung eines Dokumentes D_i auf einen Dokumentvektor x_i unter Verwendung aller m ∈ N Dokumente in einer gegebenen Dokumentmenge D:

A_VR-IR(D): D_VR-IR x D_VR-IR^m-1 -> DVR: (D_i, D \ {D_i}) |-> x_i.

• Q_VR-IR: Menge aller zugelassenen Suchfragen.

• A_VR-IR(Q): Query-Indexierungsfunktion als Abbildung einer Anfrage Q_j auf einen Queryvektor q_j:

A_VR-IR(Q): Q_VR-IR x Rⁿ -> DVR: (Q_j, w(F_i | D), i = 1, ..., n) |-> q_j.

• M^DVR: Menge aller zugelassenen Metriken für DVR.

• ret_VR-IR: Retrievalfunktion als Abbildung des Queryvektors q_j auf eine Teilmenge der Dokumentvektormenge DVM_j unter Verwendung der gegebenen Dokumentvektorenmenge DVM, der Metrik d_DVR und einem Distanzschwellenwert ε:

ret_VR-IR: DVR^m x DVR x M^DVR x R⁺ -> P^DVM: (DVM, q_j, d_DVR, ε) |-> DVM_j.

• rank_VR-IR: Rankingfunktion als Abbildung der ermittelten Teilmenge DVM_j auf eine Liste der Dokumentvektoren DV_j^t unter Verwendung der Metrik d_DVR:

rank_VR-IR: DVR^m x M^DVR -> L^DVM: (DVM, d_DVR) |-> DV_j.

Literatur

• Baeza-Yates, Richardo; Ribeiro-Neto, Berthier: Modern Information Retrieval. ACM Press, New York, 1999, 0-21-39829-X.

• Ferber, Reginald: Information Retrieval - Suchmodelle und Data-Mining-Verfahren für Textsammlungen und das Web. Heidelberg, 2003, 3-89864-213-5.

• Grossman, D.A.; Frieder, O.: Information Retrieval. Kluwer, 1998.

• Kowalski, Gerald; Maybury, M.T.: Information Storage and Retrieval Systems. Kluwer, Boston, 2000.

• Salton, Gerard; McGill, M.J.: Information Retrieval. MacGraw-Hill, 1987.

• Panyr, Jiri: Automatische Klassifikation und Information Retrieval. Tübingen, 1986.

• Zobel, Justin; Moffat, Alistair: Exploring the Similarity Space. In: SIGIR Forum, Vol. 32, 1998, Nr. 1, S. 18 - 34.

Siehe auch: Zipfsches Gesetz, Suchmaschine, Stemming