|
fit 2002 > Wissensakquisition
> Konzepte und Techniken > Information
Retrieval |
|
Überblick |
|
Beginn des systematischen Ordnens von Information kann mit dem Dewey Decimal Classification Systemangegeben werden: 1876 Dewey Dezimal Classification System
In den 50' er und 60' er Jahren: Versuche zur Strukturierung von Schlüsselwörtern zur Indexierung von Büchern in z.B. Bibliotheken:, zwei grundlegende Möglichkeiten: Precoordinative: Alle relevanten Schlüsselworte werden gesammelt und für das jeweilige Dokument angegeben, bis gewünschte Genauigkeit erreicht ist. Keine Querverweise zwischen den einzelnen Schlüsselwörtern, Beispiel: Schlüsselworte für ein bestimmtes Dokument: „Information Retrieval History“, Permutationen der Worte werden alphabetisch gespeichert, Problem ist die Grösse des Index „Information Retrieval History“ „History Information Retrieval“ „Retrieval History Information“ etc. etc. Postcoordinative: Dokument werden Schlüsselworte zugewiesen, Querverweise unter den Schlüsselwörterm: Beispiel: „Information“ „Retrieval“, „History“ sind Schlüsselworte, die mit dem Dokument unabhängig voneinander verknüpft sind. Durch logische Verknüpfung der Begriffe kann relevantes Dokument gefunden werden: Information AND retrieval AND history.html Diese Methode bietet sich viel eher an, maschinell verarbeitet zu werden.
KWOC Key Word Out of Context. Der Index besteht aus Schlüsselworten, welche von einem Menschen ausgesucht werden. Die Auswahl beschränkt sich nicht notwendigerweise auf den titel des Dokumentes. Für maschinelle Bearbeitung eher ungeeignet
KWIC indexing Key Word In Context. Eine Form von automatischer Indexierung für Bibliotheken, Bei Eingabe von Daten in dieDatenbank werden Schlüsselworte vom Titel und oft auch aus der Zusammenfassung extrahiert. Ein KWIC index besteht normalerweise aus vier Spalten, die zweite enthält das indizierte Schlüsselwort, die erste und dritte enthalten Worte, die links bzw. rechts vom Schlüsselwort vorkomme, die vierte Spalte enthält die Referenznummer
Indizierung mithilfe des Computers: Auswahl von Schlüsselworten nach bestehenden Klassifikationssystemen (z.B Dewey D. C.), dadurch Einordnen des Dokumentes in das Klassifikationssystem (zugewiesene Indizierung) - Wird von Menschen durchgeführt, kann im nachhinein mit Hilfe des Computers manipuliert werden ODER Identifikation aller in einem Dokument vorkommenden Worte und Selektion von Schlüsselworten anhand von z.B.: der Häufigkeit (abgeleitete Indexierung) - Kann in erster Linie nur mit Hilfe des Computers durchgeführt werden, wenn der Inhalt in maschinenlesbarer Form vorliegt
Vocabulary problem: Synonyme: Nur in 20% der Fälle benutzen Menschen dasselbe Wort zur Bezeichnung eines bekannten Objektes
Polyseme: Innerhalb verschiedener Dokumente können gleiche Schlüsselworte in einem anderen Zusammenhang vorkommen. Lösung: kontrolliertes Vokabular, Nachteil ist erforderlicher manueller Indexierungsprozess, Suche kann nur durch geschultes Personal durchgeführt werden.
Semantisches Modell der Dokumentesnsammlung: Lösung: Zusammenfassung von gebräuchlichen Bezeichnern zu „Gruppen“, Dokumente nicht mehr durch einzelne Worte repräsentiert, sondern durch Gruppen
Retrieval Modelle:
„Boole'sches Retrieval" : Exact match Einfach zu realisieren, eher mäßige Qualität der Ergebnisse
" Vektorraum Modell " : Dokumente und Queries werden als Vektoren in einem hoch- dimensionalen Raum betrachtet " Relevante Dokumente befinden sich nahe bei den Queries Die mit dem Dokument verknüpften Schlüsselworte werden als Komponenten von Vektoren betrachtet, welche auch je nach Bedeutungsgrad in ihrem „Wert“ gewichtet sein können. Beim Retrievalprozeß wird die Anfrage ebenfalls in einen Vektor umgewandelt, der dann mit den Vektoren der einzelnen Dokumente verglichen wird, die ähnlichsten Vektoren werden als passend betrachtet und ausgegeben. Beispiel: >[SMART]
" Probabilistische Modelle ": Aussagen über die Wahrscheinlichkeit der Relevanz eines Dokumentes Beispiel: >[INQUERY] Benutzt eine Bayesianische Netzwerkstruktur, besteht aus zwei Teilen, ein Dokumentnetzwerk und ein Querynetzwerk. Das Dokumentnetz ist statisch, Knoten die Dokumente repräsentieren sind mit Knoten verbunden, welche Schlüsselworte darstellen. Auf diese Weise kann das System für ein gegebenes Dokument die Wahrscheinlichkeit dafür berechnen, dass ein bestimmtes Schlüsselwort instanziert ist. Das Anfrage(Query)netz wird erstellt, indem Schlüsselworte der Anfrage mit Knoten verbunden werden, die die Art und Weise darstellen, wie die Schlüsselworte der Anfrage kombiniert werden sollen (z.B. Wahrscheinlichkeit dass eine AND Verknüpfung hinreichend getroffen wird, wird durch das Produkt der einzelnen Wortwahrscheinlichkeiten errechnet). Diese Kombinationsterme können wiederum verbunden werden, um den Bedürfnissen der Anfrage zu entsprechen. Beim Retrieval werden die beiden Netzwerke verknüpft und die Wahrscheinlichkeit pro Dokument berechnet, ob die enthaltene Information der Anfrage genügt. Die Ergebnisse werden danach nach deren Wahrscheinlichkeit geordnet zurückgegeben.
Beispiel Websuchmaschine Google:
Unüberschaubare „Dokumentensammlung“ bringt neue Probleme, „PageRank“ Methode , bewertet Treffer einer Anfrage unter anderem auch nach der Anzahl an Webseiten, die auf die einzelnen gefundenen Dokumente verweisen, je mehr Links existieren, desto höher wird die gefundene Seite bewertet. Darüber hinaus werden die Beschreibungen von Hyperlinks, die auf eine andere Seite zeigen nicht nur als Schlüsselwort für die aktuelle Seite gewertet, sondern auch für das Ziel des Links, wodurch z.B. auch die Suche nach nichttextinhalten erleichtert wird. Ein eigener Server, der „URLresolver“, sammelt URL' s, die von einem sogenannten Crawler besucht und auf einem eigenen Server komprimiert und gespeichert werden. Jede Webseite erhält eine asoziierte ID, welche immer dann vergeben wird, wenn eine neue URL aus einer Webseite herausgeparst wird. Zwei Programme, ein Indexer und ein Sorter, übernehmen die Indexierungsfunktion. Der Indexer liest die komprimierten Webseiten, dekomprimiert und parst die enthaltenen Dokumente, jedes dieser Dokumente wird in einen Satz von Wortvorkommnissen „Hits“ genannt, konvertiert. Diese Hits speichern das jeweilige Wort, die Position innerhalb des Dokumentes und andere Informationen, wie z.B. Fontgrösse und vergin'bt eine „WordID“. Danach verteilt der Indexer die „Hits“ in sogenannte „Barrels“, wodurch ein teilweise vorsortierter Index entsteht. Darüber hinaus parst der Indexer alle Hyperlinks der Webseiten aus und speichert wichtige Information darüber in einem „Anchors File“. Diese Datei enthält genug Information um festzustellen, wohin und woher der jeweilige Link zeigt und, darüber hinaus, wie die Beschreibung des Verweises lautet. Der URLresolver liest das „Anchors file“ , wandelt relative URL' s in Absolute um und weist diesen dann DocID' s zu. Danach wird der Ankertext (Beschreibung der URL) mit einem Verweis auf die verbundene DocID dem erstellten vorsortierten Index zugefügt. Darüber hinaus wird eine Datenbank erstellt, die Links als Paare von DocID' s darstellt. Diese Datenbank wird benutzt, um den „Page Rank“ für alle Dokumente zu ermitteln Der Sorter nimmt die nach DocID' s geordneten Barrels (vorsortierten Index) und erstellt einen invertierten Index, der nach WortID' s geordnet ist. Aus dem vorsortierten Index und dem invertierten wird ein Lexikon generiert, welches dann zusammen mit dem Page Rank vom eigentlichen Suchprogramm benutzt wird. Der Suchvorgang sieht - vereinfacht - so aus:
Sortieren der gefundenen Dokumente nach ihrem PageRank
|
|
Weiterführende Informationen |
|
>[http://www.electric-words.com/dict/k/kwic.html] fabulous fact finder >[http://pi0959.kub.nl/Paai/Onderw/V-I/Content/history.html#indices] The retrieval of information from historical perspective >[http://www.ifs.tuwien.ac.at/~dieter/Lehre/188098.html] Vorlesungsskriptum IFS TU wien
>[http://www.uni-karlsruhe.de/~uo3f/seminarir/SeminarWeb.html#chapter2] advanced information retrieval methods
>[http://www7.scu.edu.au/programme/fullpapers/1921/com1921.htm] The Anatomy of a web engine (google)
|
|
Verweise auf Arbeiten anderer gruppen |
|
|
|
>Entstehungskontext | Konzepte und Techniken | Entwicklung und Auswirkungen | Praxis | Bewertung |