#!/usr/bin/perl print qq§Content-Type: text/html §;

2 Einführung in das Information Retrieval *

2.1 Begriff des Information Retrieval *

2.2 Evaluierung von Information Retrieval Ergebnissen *

2.2.1 Precision und Recall *

2.2.2 Beispiel mit Precision Recall Diagramm *

3 Dokumentrepräsentation *

3.1 Freitextverarbeitung *

3.1.1 Informatischer Ansatz *

3.1.2 Computerlinguistischer Ansatz *

3.2 Dokumentationssprachen *

3.2.1 Klassischer Ansatz *

3.2.2 KI-orientierter Ansatz *

4 Information Retrieval Modelle *

4.1 Boolsches Retrieval *

4.2 Fuzzy Retrieval *

4.3 Vektorraummodell (VRM) *

4.4 Dokumenten Clustering *

5 Literaturliste *

Einleitung

Der Begriff Ähnlichkeit kommt in sehr vielfältiger Form beim Wissenschaftsgebiet Information Retrieval zur Geltung. Man kann sogar sagen, daß das Information Retrieval auf dem Prinzip der Ähnlicheit beruht, da einerseits Abfragen auf ähnliche Dokumente und andererseits ähnliche Abfragen auf gleiche Dokumente innerhalb des Information Retrievals durchgeführt werden.

Einführung in das Information Retrieval

In einem ersten Schritt soll der Begriff des Information Retrieval geklärt werden. Es muß dabei darauf hingewiesen werden, daß es keine einheitliche Definition gibt. Es werden an dieser Stelle deswegen mehrere Erklärungsansätze aus verschiedenen Literaturquellen angeführt.

2.1Begriff des Information Retrieval

Grundsätzlich kann gesagt werden, daß sich der Wissenschaftsbereich des Information Retrieval mit dem Prozeß des Wissenstransfers vom menschlichen Wissensproduzenten zum Informations-Nachfragenden beschäftigt. In diesem Zusammenhang ermöglichen sogenannte Information Retrieval (IR) Systeme die Repräsentation, Speicherung und den Zugriff auf Dokumente (meist Textdokumente) [PRÖ, S. 6]. Dabei handelt es sich hauptsächlich um "unsicheres Wissen", das in solchen Systemen verwaltet wird und "vage Anfragen", die Wissen filtern sollen. Das klassische Anwendungsgebiet des Information Retrieval sind Literaturdatenbanken, in denen Kurzfassungen von Veröffentlichungen gespeichert werden, und die den Anwendern die Suche nach für sie relevanter Literatur in einem bestimmten Fachgebiet ermöglichen sollen [FUHR, S. 9]

IR-Systeme haben dabei nicht die Aufgabe den Benutzer aufgrund von Anfragen zu informieren, d.h. das Wissen des Benutzers zu erweitern, sondern es wird lediglich über die Existenz oder Nicht-Existenz von Dokumenten informiert.

Eine andere Herangehensweise an den Begriff des Information
Retrieval wird in
Abb. 1 dargestellt. Es werden dabei drei Komponenten dargestellt: Input, Prozessor und Output. (RIJS, Chapter 1). Die Input-Komponente beschäftigt sich dabei hauptsächlich mit der Repräsentation aller relevanten Dokumente im IR-System sowie mit den Abfragen (Queries), die auf diese Dokumente angewandt werden. Dabei werden die Dokumente nicht in ihrem vollen Umfang im IR-System dargestellt, der Text eines Dokuments geht bei der Übernahme verloren. Es wird nur noch eine Repräsentation des Textes im IR-System abgespeichert. Auf die Art und Weise der Repräsentation von Dokumenten in solchen Systemen wird zu einem späteren Zeitpunkt noch näher eingegangen.

Die zweite Komponente des IR-Systems ist der Prozessors. Seine wichtigste Aufgabe ist der Retrieval-Vorgang, d. h. das Auffinden Dokumenten, die der gestellten Anfrage entsprechen. Dazu gehört auch die Strukturierung der Informationen auf eine bestimmte Art und Weise, z. B. durch Klassifizierung der Dokumente.

Schlußendlich wird durch den Output das Suchergebnis für den Benutzer z. B. in Form einer bestimmten Menge von Dokumenten sichtbar gemacht. An diese drei globalen Aufgabenbereiche kann dann in einem weiteren Schritt ein Evaluierungsprozeß anschließen, dessen Aufgabe es ist, die Ergebnisse der Suche zu bewerten. Dazu bedarf es Kriterien, anhand welcher die Bewertung durchgeführt werden kann. Diese werden nun in einem nächsten Schritt beschrieben.

2.2Evaluierung von Information Retrieval Ergebnissen

Zwei wichtige Kriterien, um Information-Retrieval-Systeme zu bewerten sind die Effizienz und die Effektivität: Die Effizienz umfaßt dabei vor allem die Kosten und die Zeit, um eine Aufgabe zu erfüllen, d. h. Ziel ist es, möglichst sparsam mit den Systemressourcen umzugehen (Speicherplatz, CPU-Zeit, Anzahl I/O-Operationen, Antwortzeiten. Die Effektivität dagegen beschreibt die Fähigkeit des Systems, eine vom Benutzer gewünschte Leistung zu erbringen, d. h. es geht um die Qualität der Antworten des System auf vom Benutzer gestellte Anfragen.

Um die Frage nach der Effektivität und Effizienz eines Retrieval-Prozesses zu beantworten, muß zuerst beschrieben werden, welche Faktoren die Qualität der Suche beeinflussen. Diese sind unter anderen:

Auswahl und Eingabe der Dokumente bestimmen vor allem den Inhalt und die Aktualität der Datenbank sowie die Fehlerrate in den Dokumenten
Dokumentenformate bestimmen vor allem, wie die Dokumente gespeichert werden, und was ihre Repräsentation im IR-System beinhaltet.
Die Indexierungsmethoden, d. h. die Repräsentation der Dokumente, beschreiben, wie spezifisch bzw. breit die Dokumente im IR-System festgelegt werden. Dies ist vor allem dann wichtig, wenn bestimmte Dokumente auch bei globaleren Anfragen noch gefunden werden sollen
Die Anfrageformulierung selbst beeinflussen vor allem die Qualität und Quantität der Suchergebnisse. Die Güte der Abfrage wiederum ändert sich dabei unter anderem durch den fachlichen Kenntnisstand der Anfragenden und durch die Vertrautheit des Benutzers mit dem System.
Die Präsentation der Ergebnisse bestimmen als Abschluß des Retrieval-Prozesses, ob aus dem Ergebnis Nutzen gezogen werden können.

Ein erstes Problem, das bei der Bewertung von solchen Ergebnissen auftritt, ist die Frage danach, welche überhaupt die richtige Antwort für eine Anfrage an das System ist, d. h., daß bekannt sein muß, welche Dokumente in der Datenbank vorhanden sind, die zu einer bestimmten Anfrage gehören. Dies wird durch die sogenannte Relevanz ausgedrückt. Sie beschreibt die Korrespondenz zwischen einer Anfrage an das IR-System auf der einen Seite und einem Dokument, das durch das System gefunden wird auf der anderen Seite. Dabei steigt die Relevanz eines Textes, falls das ihm zugrundeliegende Dokument die nachgefragte Information stärker abdeckt, als ein anderes Dokument, das ebenfalls Ergebnis des Retrieval-Prozesses war. Damit bleibt die Frage aber offen, wann ein Dokument eine Informationsnachfrage stärker abdeckt als ein anderes. Dies ist aber nicht Aufgabe des IR-System sondern kann nur durch Menschen eingeschätzt werden. Dieser Aspekt wird bei vielen Untersuchungen oft außer acht gelassen und damit der Anschein erweckt, daß es sich bei den verwendeten Methoden um von menschlichen Einflüssen unabhängige Maße handle.

Formal gesehen kann die Relevanz als eine Relation r beschrieben werden, wobei gilt:

wobei D={d1, ..., d_m} die Menge der Dokumente, Q die Menge der Anfragen und R eine Menge von "Wahrheitswerten", d. h. aus der Menge {0,1}, ist, die darüber Auskunft geben, ob ein Dokument relevant ist oder nicht. Diese Relation wird in der Regel durch die Befragung von Experten zu konkreten Anfragen und Dokumentmengen ermittelt und dann festgelegt.

Auf dieser Definition bauen nun die beiden am häufigsten verwendeten Evaluierungsmaße auf: Precision und Recall

2.2.1Precision und Recall

Precision beschreibt den Anteil der relevanten Dokumente an den gefundenen Dokumenten, Recall gibt den Anteil der relevanten Dokumente an, die gefunden wurden. Dies kann durch folgende Formeln beschrieben werden:

Dabei steht REL für alle relevanten Dokumente und GEF für alle gefundenen Dokumente.

Dabei bedeutet ein Wert von 1 für Precision bzw. Recall, daß genau alle relevanten Dokumente als Antwortmenge zurückgeliefert werden. Die beiden Maße Precision und Recall sind in gewissem Maße gegenläufig. Dies soll an einem Beispiel demonstriert werden:

Werden beispielsweise auf eine Anfrage hin alle Dokumente eines IR-Systems zurückgeliefert, ist der Recall gleich 1, da ja alle Dokumente durch das System geliefert wurden. Im Gegensatz dazu wird die Precision aber sehr gering sein, vor allem dann, wenn nicht alle Dokumente tatsächlich relevant sind. Wird im Gegensatz dazu nur ein einziges relevantes Dokument gefunden, so ist die Precision gleich 1, da ja das einzig gefundene Dokument auch das einzig relevant darstellt, der Recall dagegen wird aber sehr schlecht sein, da aus der Menge aller Dokumente nur eines als relevant erkannt wurde.

Die Precision wie auch der Recall können durch Variationen der Abfrageformulierungen beeinflußt werden. So wird durch eine spezifischere Anfrage eine bessere Precision, aber ein schlechterer Recall erreicht. Wird dagegen durch eine allgemeinere Anfrage die Antwortmenge vergrößert, verbessert sich der Recall auf Kosten der Precision. Diese beiden Maße dienen damit vor allem auch dazu, um verschiedene IR-Systeme zu vergleichen, wobei davon ausgegangen wird, daß bessere Precision- als auch Recallwerte ein bestimmtes IR-System im Gegensatz zu einem anderen auf eine qualitativ höhere Stufe stellen. An einem konkreten Beispiel soll nun noch einmal der Zusammenhang zwischen Precision und Recall erklärt werden:

2.2.2Beispiel mit Precision Recall Diagramm

n	Dok#	relevant	Recall	Precison
1	588	X	1/5	1/1
2	589	X	2/5	2/2
3	576
4	590	X	3/5	¾
5	986
6	592	X	4/5	4/6
7	984
8	988
9	578
10	985
11	103
12	591
13	772	X	5/5	5/13
14	990

Abbildung 2: Precision Recall Tabelle

Grundsätzlich besteht zwischen Recall und Precision eine inverse Beziehung: Je mehr Ergebnisse ein IR-System liefert, desto größer wird der Recall und desto kleiner wird die Precision. Die Abbildung 2 zeigt die Entwicklung von Precision und Recall. Durch ein X

gekennzeichnete Dokumente stellen relevante Dokumente dar. Genau diese Dokumente beeinflussen die Werte für Recall und Precision.

Abbildung 3 zeigt ein sogenanntes Precision Recall Diagramm. Das Diagramm liegt nicht der Tabelle aus Abbildung 2 zugrunde. Es werden dabei Paare von zusammengehörenden Recall- und Precisionwerten aufgetragen. Auch hier wird sehr schön die inverse Beziehung dieser beiden Maße sichtbar. Steigender Recall führt zu sinkender Precision und umgekehrt.

Um aus diesen Maßen nun aussagekräftige Ergebnisse zu erhalten, müssen die Precision und Recallwerte über mehrere Anfragen gemittelt werden. Dafür gibt es zwei verschiedene Ansätze. Der nutzenorientierte Ansatz (od. Makrobewertung) bildet das arithmetische Mittel über die Werte. Dabei wird nicht berücksichtigt, ob ein Wert aufgrund von wenigen oder vielen relevanten Dokumenten zustande gekommen ist. Der systemorientierte Ansatz (od. Mikrobewertung) berücksichtigt im Gegensatz zur Makrobewertung auch die in die Precision bzw. den Recall eingegangene Dokumentenzahl. Hier wird also der Mittelwert gemäß der Anzahl der beteiligten Dokumente berechnet. Dadurch gehen Anfragen mit wenigen relevanten Dokumenten schwächer in den Mittelwert ein, als Anfragen mit vielen relevanten Dokumenten.

Nachdem nun geklärt wurde, wie Ergebnisse von Retrieval-Prozessen evaluiert werden können und welche Maße dafür zur Verfügung stehen soll im nächsten Schritt beschrieben werden, wie Dokumente überhaupt in Information Retrieval Systeme übernommen werden und wie diese Dokumente repräsentiert werden.

3.Dokumentrepräsentation

Es wird nun beschrieben, wie Dokumente bzw. Texte in Information Retrieval Systemen repräsentiert werden können. Ziel dieser Dokumentrepräsentation ist es zum einen unterschiedliche Formulierungen auf die gleiche Repräsentation abzubilden und damit den Recall zu steigern und zum anderen unklare Formulierungen, d. h. Mehrdeutigkeiten, eindeutig abzubilden und damit die Precision zu steigern. Zwei verschiedene Ansätze sollen an dieser Stelle beschrieben werden: die Freitextverabeitung und Dokumentationssprachen.

3.1Freitextverarbeitung

Die Freitextverarbeitung basiert auf folgender Vorgehensweise:

Zerlegung des Textes in einzelne Wörter
Stoppworteliminierung (Eliminierung v. nichtrelevanten Wörtern aus dem Dok.)

Bei dieser Dokumentenfilterung können verschiedenste Probleme auftreten, die in folgender Tabelle zusammengefaßt werden:

Homographen	Verschieden gesprochene Wörter mit gleicher Schreibweise	Wach-stube Wachs-tube
Polyseme	Wörter mit mehreren Bedeutungen	Bank = Geldinstitut oder Sitzgelegenheit
Flexionsformen	Entstehen durch Konjugationen und Deklinationen eines Wortes	Haus-Hauses-Häuser, schreiben-schrieb-geschrieben
Derivationsformen	Verschiedene Wortformen zu einem Wortstamm	Formatierung-Format-formatieren
Komposita	Mehrgliedrige Ausdrücke	Information retrieval, retrieval of information

Abbildung 3: Probleme bei Freitextverarbeitung

Bei der Freitextverarbeitung bzw. –suche wird zwischen zwei Ansätzen unterschieden, dem informatischen und dem computerlinguistischen Ansatz.

3.1.1Informatischer Ansatz

Es stehen dabei spezielle Zeichenkettenoperationen zur Suche zur Verfügung:

Truncations- und Maskierungsoperatoren

Unter Zuhilfenahme von Wildcards können ein oder mehrere Zeichen "maskiert" werden. Das $-Zeichen für ein, das #-Zeichen für beliebig viele Zeichen. Beispiele sollen dies verdeutlichen:

Operation	Es wird gefunden
Schreib#	Schreiben, schreibt, schreibst, schreibe
schreib$$	Schreiben, schreibst
#schreiben	Schreiben, beschreiben, anschreiben, verschreiben
schr$$b#	Schreiben, schrieb, aber auch für schrauben
h$$s#	Haus, Häuser, aber auch für heiser

Abbildung 4: Beispiele für Truncations- und Maskierungsoperatoren (PRÖL, S. 27)

Diese Beispiele zeigen bereits, daß dadurch auch unerwünschte Wörter berücksichtigt werden. Außerdem ist dadurch die Anfrageformulierung für Benutzer schwierig

Kontextoperatoren

Hier werden Wildcards zur Maskierung ganzer Wörter verwendet:

Operation	Es wird gefunden
Retrieval $ information	Retrieval of information, retrieval with information loss
Text ## retrieval	Text retrieval, text and fact retrieval
Information #, retrieval	Information retrieval, retrieval of information
Information # retrieval.	Findet nicht: ... this information. Retrieval of data ...

Abbildung 5: Beispiele für Kontextoperatoren (PRÖL, S. 28)

3.1.2Computerlinguistischer Ansatz

Bei diesem Ansatz werden Algorithmen bereitgestellt, die die verschiedenen Flexions- und Derivationsformen eines Wortes zusammenführen. Diese Algorithmen sind natürlich sprachabhängig. Auch hier sollen zwei Verfahren beschrieben werden

Graphematische Verfahren (geeignet für Englisch)

Grundformreduktion	Ies-->y / es-->y	Applies-appl-apply
Stammformreduktion	Wörter werden auf Stamm reduziert	Compter,compute,computation -->comput

Abbildung 6: Anwendung Graphematischer Verfahren (PRÖL, S. 29)

Lexikalische Verfahren (geeignet für Deutsch)

Flexionsform-->zugehörige Grundform	Hauses-->Haus, ging-->gehen
Derivationsform-->zugehörige Grundform	Berechnung-->rechnen
Komposita-->zugehörige Dekomposition	Armbanduhr-->Uhr

Abbildung 7: Anwendung Lexikalischer Verfahren (PRÖL, S. 30)

3.2Dokumentationssprachen

Dokumentationssprachen können dabei helfen, die Nachteile der Freitextverarbeitung zu überwinden. Sie dienen zur unabhängigen Repräsentation des Textinhaltes durch Verwendung eines speziellen Vokabulars. Zwei verschiedene Ansätze werden unterschieden: der klassische Ansatz und der KI-orientierte Ansatz.

3.2.1Klassischer Ansatz

Die beiden Methoden, die in diesem Zusammenhang erwähnt werden sind die Klassifikation, bei der Dokumente in Klassen eingeordnet werden, und Thesauri, die zur Zusammenstellung von Begriffen mit gleicher bzw. ähnlicher Bedeutung dienen.

Klassifikationen

Klassifikationen dienen dazu, um Wissensgebiete nach einem vorgegebenen Schema zu klassifizieren. Dabei werden einzelne Dokumente einer bestimmten Klasse zugeordnet (FUHR, S. 61). Dabei sollte auch berücksichtigt werden, daß es Dokumente geben kann, die zu mehreren Klassen gehören. Diese Klassifikationen können nach verschiedenen Kriterien unterschieden werden (FUHR, S. 62ff)

Monohierachie vs. Polyhierarchie

Bei Monohierarchien werden die Klassen von Dokumenten in eine Baumstruktur eingeordnet. Jede Klasse hat genau eine Vorgängerklasse. Bei Polyhierarchien kann im Gegensatz dazu eine Klasse mehrere Vorgängerklassen bzw. Superklassen haben.

Obstbaum

Kernobstbaum Steinobstbaum

Apfelbaum Birnbaum Kirschbaum Pfirsichbaum

Abbildung 8: Beispiel für eine Monohierarchie

Obstbaum Nutzholzbaum

Kernobstbaum

Birnbaum

Abbildung 9: Beispiel für eine Polyhierarchie

Monodimensionalität vs. Polydimensionalität

Im Falle der Polydimensionalität kann es auf einer Stufe Merkmale geben, nach denen es eine weitere Aufteilung in Unterklassen gibt. Diese Aufteilung ist im Fall der Monodimensionalität nicht gegeben.

Obstbaum

Nach Fruchtart nach Stammbildung

Steinobstbaum Kernobstbaum Hochst. Obstbaum

Mittelst. Obstbaum

Abbildung 10: Beispiel für eine Polydimensionalität Niederst. Obstbaum

Analytische versus synthetische Klassifikation

Die analytische Klassifikation folgt dem top-down-Ansatz. Ausgehend von einer Menge von Objekten sucht man nach dem nächsten Kriterium zur weiteren Aufteilung in Subobjekte. Die synthetische Klassifikation dagegen folgt dem bottom-up-Ansatz. Nach der Erhebung der relevanten Merkmale der zu klassifizierenden Objekte werden diese im Klassifikationssystem zusammengestellt. In einem zweiten Schritt werden dann die Klassen durch Kombination der Merkmale gebildet. Abbildung zeigt eine solche synthetische Klassifikation:

Klassifikation 1	Klassifikation 2	Klassifikation 3
A Fruchtart	B Stammart	C Erntezeit
A1 Apfel	B1 hochstämmig	C1 früh
A2 Birne	B2 halbstämmig	C2 mittel
A3 Kirsche	B3 niederstämmig	C3 spät
A4 Pfirsich
A5 Pflaume

Abbildung 11: Beispiel für eine Synthetische Klassifikation

Thesauri

Thesauri sind eine Zusammenstellung von Begriffen mit gleicher bzw. ähnlicher Bedeutung in ein und der selben Äquivalenzklasse und dienen dadurch zur Reduzierung von Mehrdeutigkeiten und Unschärfen der natürlichen Sprache
(PRÖ, S. 36).

Folgende Vorgehensweise wird empfohlen (PRÖ, S. 37ff):

Synonymkontrolle
Es werden Bezeichnungen mit geringem Bedeutungsunterschied in Äquivalenzklassen zusammengefaßt (z. B.: UN-UNO-Vereinte Nationen, Pferd-Gaul, Wohnen-Wohnung)
Homographen- und Polysemkontrolle
mehrdeutige Bezeichnungen werden auf mehrere Äquivalenzklassen aufgeteilt
(z. B.: Wachstube , Bank)
Zerlegungskontrolle
Es wird die Frage beantwortet, wie spezifisch die Begriffe im Thesaurus sein sollen. Es wird zwischen Präkoordination (Thesaurus enthält zusammengesetzte Wörter) und Postkoordination (Thesaurus enthält nicht weiter zerlegbare Wörter)
Deskriptor
Deskriptoren dienen zur Benennung einer Äquivalenzklasse, d. h. ein Element der Äquivalenzklasse wird zur Benennung ausgewählt.
Beziehungen
Es werden Beziehungen zwischen Begriffen hergestellt: z. B.: Unterbegriff-, Oberbegriff-, Verwandtschaftsbeziehungen

3.2.2KI-orientierter Ansatz

Der Künstliche Intelligenz-orientierte Ansatz soll anhand von Semantischen Netzen illustriert werden.. In solchen Semantischen Netzen werden Relationen zwischen Begriffen definiert. Es soll damit erreicht werden, daß die Bedeutung des Begriffs aus dem Zusammenhang ersichtlich wird (PRÖ, S. 41). Anhand eines Beispiels soll dies demonstriert werden:

BESCHÄFTIGTE

PERSONEN ARBEITGEBER

INSTITUTION

STUDENT
IMMATRIKULIERT
UNIVERSITÄT

BESCH. STUDENT

Abbildung 12: Beispiel für ein semantisches Netz

4.Information Retrieval Modelle

Im folgenden Kapitel werden die in der Literatur genannten Information Retrieval Modelle vorgestellt, damit man sich einen Eindruck über die Vorgehensweise bei der Dokumentensuche machen kann. Die IR-Modelle bauen auf die im vorhergehenden Kapitel vorgestellten Dokumentrepräsentationen auf, da die Art der Repräsentation entscheidende Bedeutung für die Auswahl des IR-Modells hat.

Für das Anwenden der IR-Modelle benötigt man neben einer Datenbasis, in der Repräsentationen von Dokumenten abgelegt sind, eine Anfrage-Repräsentation in Form einer formalisierten Anfrage und eine Retrievalfunktion, die die Anfrage mit dem Dokument vergleicht und ein Retrievalgewicht berechnet.

Die ersten drei IR-Modelle basieren auf einem ähnlichen Retrieval-Konzept.. Um die Unterschiede besser zu illustrieren, werden die Modelle anhand eines Beispiels vorgestellt. Es existieren fünf Dokumente, die mit verschiedenen Termen beschrieben werden können. Die Terme pro Dokument sind in diesem Fall die Repräsentation des Dokumentes in der Dokumentendatenbasis.

Dok#	Terme der Indexierung
1	Getränke, Cola, Bacardi, Cocktails
2	Cola, Bacardi, Barkeeper
3	Getränke, Cocktails
4	Cola, Bacardi, Cocktails
5	Bacardi, Cocktails, Barkeeper

Grundsätzlich sind die IR-Modelle unabhängig von der Art der Dokumentenrepräsentation, d.h. die Indizierung über Terme ist nicht zwingend vorgeschrieben, um die IR-Modelle anwenden zu können. Wird jedoch die Indizierung über Terme verwendet, vereinfacht sich die Anwendung der IR-Modelle.

Formale Dokumentbeschreibung für IR-Modelle: [PRÖL, S. 23]

Ein Dokument wird durch einen Beschreibungsvektor x = (x₁,...,x_n) repräsentiert, wobei die Komponente x_i jeweils das Vorkommen des Terms t_{t Î}T = {t₁,...,t_n} in einem aktuellen Dokument beschreibt. Im vorgestellten Beispiel beinhaltet der Term T = {Getränke, Cola, Bacardi, Cocktails, Barkeeper).

Im einfachsten Fall sind die Vektor-Komponenten binär, also x_i= 1 (falls t_i im Dokument vorkommt) oder x_i= 0. Als eine Verbesserung dieser Repräsentationsform kann man die Vorkommenshäufigkeit des Terms im Dokument berücksichtigen.

4.1Boolsches Retrieval

Das ist das am einfachsten zu handhabende Retrieval-Modell. Die Dokumentenbeschreibung D^D erfolgt mittels ungewichteter Indexierungen, d.h. es existiert für jedes Dokument ein Beschreibungsvektor d_m, der angibt, ob die Indexierungsterme in diesem Dokument vorkommen oder nicht (d_mi Î {0,1}).

Für das vorgestellte Beispiel sind die Beschreibungsvektoren:

d1 = ( 1 , 1 , 1 , 1 , 0 )

d2 = ( 0 , 1 , 1 , 0 , 1 )

d3 = ( 1 , 0 , 0 , 1 , 0 )

d4 = ( 0 , 1 , 1 , 1 , 0 )

d5 = ( 0 , 0 , 1 , 1 , 1 )

Die Fragebeschreibung Q^D sind boolsche Ausdrücke über ein vorgegebenes Indexierungsvokabular, die nach verschiedensten Regeln für UND, ODER bzw. NICHT Abfragen gebildet werden. Damit gestalten sich die Abfragen sehr flexibel, da man die Dokumente nach mehreren Gesichtspunkten suchen kann.

Die verwendete Retrievalfunktion j definiert die Berechnungsfunktion für die Bewertung der Dokumente. Das Ziel jedes IR-Modells ist die Suche nach auf die Anfrage passenden Dokumenten. Die Retrievalfunktion beim Boolschen Retrieval liefert den Wert 1 für Dokumente, die genau auf die Anfrage passen. Die Retrievalfunktion liefert den Wert 0 für Dokumente, die wenig oder gar keine Gemeinsamkeit mit den Fragetermen aufweisen.

Anwendung des Boolschen Retrievals bei der Beispieldokumentenmenge:

Der Benutzer sucht nach Dokumente, die die Terme Cola und Bacardi
(Q^D = (Cola Ç Bacardi)) in der Dokumentrepräsentation beinhalten.

Bei einer UND-Abfrage ist die Retrievalfunktion j (q₁ _^ q₂, dm) = min(j (q₁, dm),
j (q₂, dm)).

Das Information Retrieval System hat einerseits die Aufgabe die Anfrage mit den vorhandenen Dokumenten in Verbindung zu bringen und andererseits die Retrievalfunktion zu berechnen.

j (Cola _^Bacardi, d₁) = min(j (Cola, d₁), j (Bacardi, d₁)) = min(1,1) = 1

j (Cola _^Bacardi, d₂) = min(j (Cola, d₂), j (Bacardi, d₂)) = min(1,1) = 1

j (Cola _^Bacardi, d₃) = min(j (Cola, d₃), j (Bacardi, d₃)) = min(0,0) = 0

j (Cola _^Bacardi, d₄) = min(j (Cola, d₄), j (Bacardi, d₄)) = min(1,1) = 1

j (Cola _^Bacardi, d₅) = min(j (Cola, d₅), j (Bacardi, d₅)) = min(0,1) = 0

Das Boolsche Retrieval liefert drei passende Dokumente retour, d. h. es trifft die Aussage, daß der Benutzer nach Dokument 1,2 und 4 gesucht hat.

Vorteile des Boolschen Retrieval:

Der größte Vorteil des Boolschen Retrievals ist die einfache Implementierung dieses Modells. Daher wird es sehr oft in kommerziellen Systemen verwendet. Ein weiterer Vorteil ist die Mächtigkeit der boolschen Logik.

Nachteile des Boolschen Retrieval:

Das Boolsche Retrieval hat die Eigenschaft, daß es keine Rangordnung der Dokumente zuläßt, d. h. es unterscheidet nur in gefundene und nicht gefundene Dokumente.
Beim Boolschen Retrieval existiert keine Möglichkeit für die Gewichtung der Anfrage, d. h. die einzelnen Suchbegriffe haben die gleiche Wertigkeit.
Beim Boolschen Retrieval existiert keine Möglichkeit für die Gewichtung der Indexierung, d. h. die einzelnen Indexierungsterme haben die gleiche Wertigkeit. In der Praxis tritt oft der Fall ein, daß sich ein Dokument hauptsächlich mit einem Beschreibungsterm beschäftigt und die anderen Beschreibungsterme nur eine untergeordnete Rolle spielen.
Die Erstellung der Anfrageformulierung ist sehr umständlich, da der Benutzer die Anfrage in der formalisierten Form eingeben muß. Dabei können einerseits leicht Fehler auftreten, andererseits kann es zu einer Mißinterpretation der Anfragesyntax durch den Benutzer kommen.
Ein entscheidender Nachteil des Boolschen Retrievals ist sein Prinzip des "exact match" - dabei berücksichtigt es in keiner Weise die Vagheit der Anfrage (woher soll der Benutzer wissen, welche Indexierungsterme verwendet wurden) bzw. die Unsicherheit der Repräsentation (wurde überhaupt richtig indiziert, d.h. wurden alle notwendigen Begriffe in den Term aufgenommen).

4.2Fuzzy Retrieval

Dieses Retrieval-Modell kann man eigentlich als Erweiterung des Boolschen Retrieval Modells sehen. Im Unterschied zum Boolschen Retrieval bietet dieses Modell die Möglichkeit, gewichtete Indexierungen bei der Dokumentenbeschreibung D^D zu verwenden. Es existiert daher für jedes Dokument ein Beschreibungsvektor d_mder angibt, in wieweit die Indexierungsterme für dieses Dokument relevant sind oder nicht (d_mi Î [0,1]).

Für das vorgestellte Beispiel sind die Beschreibungsvektoren:

d1 = (0.1, 0.3, 0.3, 0, 0)

d2 = (0, 0.2, 0.1, 0, 0.1)

d3 = (0.1, 0, 0, 0.4, 0)

d4 = (0, 0.29, 0.99, 0.7, 0)

d5 = (0, 0, 0.5, 0.6, 0.4)

Die Fragebeschreibung Q^D bzw. die Retrievalfunktion j wird wie beim Boolschen Retrieval gehandhabt.

Anwendung des Fuzzy Retrievals bei der Beispieldokumentenmenge:

Der Benutzer sucht ebenfalls nach Dokumente, die die Terme Cola und Bacardi
(Q^D = (Cola Ç Bacardi)) in der Dokumentrepräsentation beinhalten.

Wie beim Boolschen Retrieval ist die Retrievalfunktion j (q₁ _^ q₂, dm) =
min(j (q₁, dm), j (q₂, dm)).

Das Ergebnis der Anfrage:

j (Cola _^Bacardi, d₁) = min(j (Cola, d₁), j (Bacardi, d₁)) = min(0,3 | 0,3) = 0,3

j (Cola _^Bacardi, d₂) = min(j (Cola, d₂), j (Bacardi, d₂)) = min(0,2 | 0,1) = 0,1

j (Cola _^Bacardi, d₃) = min(j (Cola, d₃), j (Bacardi, d₃)) = min(0,0) = 0

j (Cola _^Bacardi, d₄) = min(j (Cola, d₄), j (Bacardi, d₄)) = min(0,29 | 0,99) = 0,29

j (Cola _^Bacardi, d₅) = min(j (Cola, d₅), j (Bacardi, d₅)) = min(0 | 0,5) = 0

Das Fuzzy Retrieval liefert ebenfalls drei passende Dokumente retour, d. h. es trifft ebenfalls die Aussage, daß der Benutzer nach Dokument 1,2 und 4 gesucht hat. Im Unterschied zum Boolschen Retrieval liefert es aber auch eine Rangordnung zurück, d. h. das IRS macht anhand der Berechnungen die Aussage, daß das Dokument 1 am besten der Anfrage entspricht.

Vorteile des Fuzzy Retrieval:

Der entscheidende Vorteil des Fuzzy Retrievals gegenüber dem Boolschen Retrievals ist die Rangordnung der gefundenen Dokumente - das ist eine wertvolle Zusatzinformation für den Benutzer.

Nachteile des Fuzzy Retrieval:

Weiterhin existiert keine Möglichkeit für die Gewichtung der Fragetermen, damit ist es nahezu unmöglich, gute Anfragen an das IRS zu stellen.
Die Retrievalqualität ist grundsätzlich noch immer schlecht, da die Retrievalfunktion die mathematischen Funktionen min und max verwendet. Diese Funktionen messen einem der beiden Funktionsparameter überdurchschnittlich viel Bedeutung bei. Man betrachte Dokument 4 des Beispieles, um die schlechte Qualität zu erkennen. Augenscheinlich ist, daß das Dokument 4 (min(0.29, 0.99)) eher auf die Anfrage paßt als Dokument 1 (min(0.3, 0.3)). Die Minimum-Funktion bewirkt, daß Dokument 1 besser gereiht ist als Dokument 4.
Auch das Problem mit der umständlichen Frageformulierung ist noch immer nicht gelöst.

4.3Vektorraummodell (VRM)

Dieses Retrieval-Modell stellt eindeutig eine Verbesserung gegenüber den ersten beiden Modellen dar. Einerseits ermöglicht VRM die Anwendung des Relevance Feedbacks, d. h. der Benutzer hat die Möglichkeit eine Rückmeldung auf die gefundenen Dokumente (in wieweit trifft dieses Dokument auf die Anfrage zu) abzugeben, andererseits wird die Vagheit der Anfrage besser berücksichtigt (VRM funktioniert nach dem "best match"-Prinzip, d. h. es erfolgt ein Ranking der Dokumente, nach der Wahrscheinlichkeit in wieweit dieses Dokument auf die Anfrage zutrifft).

Abbildung 13: Beispiel für ein semantisches Netz

Das VRM ist ein anschauliches Modell zur Beschreibung der Ähnlichkeit von der Frage in Bezug auf das Dokument, da beide in einem Vektorraum abgebildet werden. In der Abbildung 12 ist dieses Prinzip graphisch für eine dreidimensionale Dokumentenbeschreibung, d. h. es existieren nur 3 Terme bei der Indexierung, aufbereitet. Die Dreidimensionalität wurde nur für die graphische Darstellung gewählt. Grundsätzlich können mit dem VRM n-dimensionale Dokumentbeschreibungen ausgewertet werden.

Im Unterschied zum Fuzzy Retrieval definiert der Beschreibungsvektor d_mfür jeden Term die Anzahl, wie oft dieser Term in einem bestimmten Dokument vorkommt. (d_mi Î R). Die Fragebeschreibung Q^D ähnelt der Gestalt des Beschreibungsvektors (q_ki Î R).

Für das vorgestellte Beispiel sind die Beschreibungsvektoren:

d1 = ( 1 , 3 , 3 , 0 , 0 )

d2 = ( 0 , 2 , 1 , 0 , 1 )

d3 = ( 1 , 0 , 0 , 1 , 0 )

d4 = ( 0 , 4 , 2 , 7 , 0 )

d5 = ( 0 , 0 , 1 , 1 , 1 )

Die Retrievalfunktion j definiert das Ähnlichkeitsmaß, d. h. es legt die Formel für die Ähnlichkeit eines Dokuments mit der Anfrage fest.

Anwendung des VRMs bei der Beispieldokumentenmenge:

Der Benutzer sucht ebenfalls nach Dokumente, die die Terme Cola und Bacardi

(Q^D = (Cola Ç Bacardi)) in der Dokumentrepräsentation beinhalten.

Anfragevektor q_k = (0, 1, 1, 0, 0)

Die Retrievelfunktion j wird durch das Cosinusmaß definiert.

j (q_k, d_m) = ¾ ¾ ¾ ¾ ¾ ¾ ¾ [PRÖL, S. 26]

Das Ergebnis der Anfrage:

j ( (0,1,1,0,0), d₁) = 0,97

j ( (0,1,1,0,0), d₂) = 0,87

j ( (0,1,1,0,0), d₃) = 0

j ( (0,1,1,0,0), d₄) = 0,51

j ( (0,1,1,0,0), d₅) = 0

Das Vektorraummodell liefert eine Rangliste der gefundenen Dokumente zurück. Aufgrund der Berechnung der Ähnlichkeit empfiehlt das IRS Dokument 1 als das der Anfrage am ähnlichsten Dokument.

Relevance Feedback:

VRM ermöglicht es dem IRS Relevance Feedback vom Benutzer einzubauen. Diese soll die Qualität der Ergebnisse auf Anfragen steigern und dem Benutzer die Möglichkeit geben, die Leistung des IRS zu beurteilen.

Vorgehensweise beim Einbau von Relevance Feedback Daten: [PRÖL, S. 27]

1. Retrievalanfrage mit Fragevektor q_k vom Benutzer

2. Relevanzbeurteilung der obersten Dokumente der Rangordnung

3. Berechnung eines verbesserten Fragevektors q_k’ aufgrund der Feedback-Daten

4. Nochmaliges Retrieval mit dem verbesserten Anfragevektors

5. Evtl. Wiederholung der Schritte 2. - 4.

Vorteile des Vektorraummodells:

Das VRM ist einfach zu verstehen und auch für den Benutzer anschaulich (durch die Vorstellung der Ähnlichkeit im Vektorraum).
Das VRM bietet eine gute Retrievalqualität, da es das Relevance Feedback unterstützt.

4.4Dokumenten Clustering

Die Ausgangsbasis für das Dokumenten Clustering ist die Ähnlichkeit relevanter und nicht relevanter Dokumente untereinander, d. h. es werden die nicht relevanten Dokumente in einem Cluster bzw. die relevanten Dokumente in einem anderen Cluster abgelegt. Dabei werden die Cluster unabhängig von der Frage schon beim Aufbau der Kollektion berechnet.

Vorgang beim Dokumenten Clustering: [PRÖL, S. 28]

Festlegung eines Ähnlichkeitsmaßes - hier könnte man wieder das Cosinusmaß des eben vorgestellten VRMs verwenden
Berechnung der Ähnlichkeitsmatrix für alle möglichen Dokumentenpaare, die innerhalb des IRS abgelegt sind
Berechnung der Cluster - dabei wird ein Schwellenwert für die Ähnlichkeit von Dokumenten verwendet, d. h. die Dokumente werden aufgrund ihres Ähnlichkeitswertes bestimmten Clustern zugeordnet
Im letzten Schritt werden die Dokumente eines Clusters physisch gemeinsam abgespeichert. Damit wird einerseits die Anzahl der I/O Zugriffe minimiert und andererseits ist es anschließend einfacher ein Cluster-Retrieval durchzuführen.

Cluster-Retrieval:

Suche ähnlicher Dokumente zu bereits gefundenen Dokumenten, d. h. nachdem man einmal ein "passendes Dokument" identifiziert hat, sind die anderen Dokumente des Clusters ähnlich gegenüber dem "passenden Dokument".
Suche Cluster mit potentiell relevanten Dokumenten und anschließend werden die angefragten Dokumente des Clusters durch ein anderes Retrievalmodell gefiltert.

5.Literaturliste

[FERB] Reginald Ferber, Data Mining und Information Retrieval, Skript zur Vorlesung an der TH Darmstadt im Wintersemester 1996/97

http://www-cui.darmstadt.gmd.de/~ferber/vorlesung-96-97/framevor/book_1.html

[FUHR] N. Fuhr: Skriptum Information Retrieval, 1997

http://ls6.informatik.uni-dortmund.de/ir/teaching/courses/ir/

[PRÖL] Birgit Pröll, Information Retrieval und Hypermedia Techniken, FAW, 1997

[RIJS] C.J. van Rijsbergen: Information Retrieval, Butterworths, 1979

http://www.dcs.glasgow.ac.uk/Keith/Preface.html