Data Mining und Information RetrievalInformationssysteme

Vorbemerkung zur Vorlesung Informationssysteme

1: Einführung


1.1: Literatursuche
1.2: Beispiel einer Datenbankrecherche

Abb. 1: Dokument aus der Literaturdatenbank INSPEC

Abb. 2: Anzahl der in INSPEC gefundenen Dokumente für die Zeit vom Januar bis Juni 1995


1.3: Faktendatenbanken und -retrieval

Abb. 3: Beispiel-Datenbank


1.4: Hypertext-Informationssysteme
1.5: Expertensysteme
1.6: Managementinformationssysteme
1.7: Knowledge Discovery / Data Mining
1.8: Ein Data Mining System zur Kategorisierung

Abb. 4: Scoring Table aus Carter and Catlett (1987)

Abb. 5: Ein kleines Trainingsset (aus Carter and Catlett, 1987)

Abb. 6: Entscheidungsbaum zum Trainingsset aus Abb. (nach Carter and Catlett, 1987)


1.9: Assoziative Regeln und der Warenkorb
1.10: Knowledge Discovery und Information Retrieval

Abb. 7: Anzahl der in INSPEC gefundenen Dokumente für die Zeit vom Januar bis Juni 1995

2: Grundlagen

2.1: Kommunikationsmodelle

2.1.1: Informationsübertragung

Abb. 8: Grundlegendes Schema der Informationsübertragung


2.1.1.1: Datenübertragung
2.1.1.2: Komplexere Übertragungsbeispiele

2.1.2: Dialoge

Abb. 9: Einfaches Dialogschema

Abb. 10: Grundlegendes Schema eines Informationssystems

2.2: Information Retrieval

2.2.1: Daten, Wissen, Information

2.2.2: Struktur eines Information Retrieval Systems


2.2.2.1: Zum Beispiel: Boolesches Retrieval in Literaturdatenbanken

Abb. 11: Schematische Darstellung eines textbasierten Booleschen Information Retrieval Systems

2.2.3: Information Retrieval: Definition und Abgrenzung

Abb. 12: Abgrenzung von Information Retrieval und Fakten Retrieval (Data Retrieval) nach Van Rijsbergen (1979)

3: Klassische Wissensrepräsentations- und Retrievalmodelle

3.1: Boolesches Retrieval

3.1.1: Logik des Booleschen Retrieval

3.1.2: Boolesches Retrieval für Textdokumente

3.1.3: Implementierung mit einer invertierten Liste

3.2: Zeichenketten, Wörter und Konzepte

Abb. 13: Trunkierungen, die nicht nur Tiere ausschließen (aus Ferber, Wettler, Rapp 1995)

3.2.1: Wortorientierte Reduktionsverfahren

Abb. 14: Schematische Darstellung der Verwendung von Grundformreduktionsverfahren in einem textbasierten Information Retrieval System


3.2.1.1: Lexikographische Grundformenreduktion nach Kuhlen

Abb. 15: Die verschiedenen Reduktionsformen nach Kuhlen am Beispiel (aus Kuhlen 1977, S. 58)

Abb. 16: Einige der Regeln zur lexikographischen Grundformenreduktion nach Kuhlen (1977)

Abb. 17: Anwendungsbeispiel für den Kuhlen Algorithmus


3.2.1.2: Lexikonbasierte Morphologieprogramme

Abb. 18: Die Wortform "Flüssen" in der Flexionsanalyse bei Lezius (1995)

3.3: Klassifikationen und Thesauren

3.3.1: Klassifikationen

3.3.1.1: Klassifikation

Abb. 19: Schematische Darstellung der Verwendung einer Klassifikation in einem Information Retrieval System


3.3.1.2: Internationale Dezimalklassifikation

Abb. 20: Die 10 Hauptabteilungen der internationalen Dezimalklassifikation (nach Manecke, 1997)

Abb. 21: Die 10 Abteilungen der Hauptabteilung 5 in der internationalen Dezimalklassifikation (nach Manecke, 1997)

Abb. 22: Ein Pfad durch die internationale Dezimalklassifikation (nach Manecke 1997)

Abb. 23: Ein Pfad durch die internationale Dezimalklassifikation (nach Fuhr 1995)

Abb. 24: Die Grundkategorien der Toman Facettenklassifikation (nach Manecke 1997)

Abb. 25: Die Facetten der ersten Grundkategorie der Toman Facettenklassifikation (nach Manecke 1997)

3.3.2: Thesauren

Abb. 26: Beispiele von Thesauruseinträgen

Abb. 27: Schematische Darstellung der Nutzung eines Thesaurus in einem Text Retrieval System

3.3.3: Semantische Netze

3.4: Das Vektorraummodell

3.4.1: Das Modell

3.4.1.1: Vektorraummodell:

3.4.1.2: Vektorraummodell mit Attributen:

Abb. 28: Schematische Darstellung eines Vektorraum Text Retrieval Systems

3.4.2: Vektorraummodell und Boolesches Retrieval

3.4.2.1: Skalarprodukt:

3.4.3: Gewichtungsmethoden


3.4.3.1: Globale Gewichtungseinflüsse

Abb. 29: Das Zipf'sche Gesetz am Beispiel des Brown- und des LOB-Korpus'

Abb. 30: Schematische Darstellung des Zipf'schen Gesetzes

Abb. 31: Abdeckung eines Texts durch seine Wörter

Abb. 32: Schematische Darstellung der Diskriminationskraft von Termen gegen die Häufigkeit aufgetragen (nach Salton & McGill 1983)


3.4.3.2: Lokale Gewichtungseinflüsse

3.4.4: Relevance Feedback

3.4.5: Das Retrievalsystem SMART


3.4.5.1: Automatische Indexierung
3.4.5.2: Berechnung von Dokumentclustern und ihrer Zentroide
3.4.5.3: Automatische Queryanalyse und Relevance Feedback Komponente
3.4.5.4: Dynamisierung des Dokumentenraumes

3.4.6: Ähnlichkeitsfunktionen


3.4.6.1: Das Skalarprodukt
3.4.6.2: Das Cosinusmaß
3.4.6.3: Das Pseudo-Cosinusmaß
3.4.6.4: Das Dice-Maß
3.4.6.5: Das Overlap-Maß
3.4.6.6: Das Jaccard-Maß

3.5: Evaluationsverfahren

3.5.1: Einflussfaktoren

3.5.2: Relevanz

3.5.2.1: Relevanz

3.5.3: Precision und Recall

3.5.3.1: Precision und Recall

3.5.3.2: Precision-Recall-Diagramm

Abb. 33: Beispiel eines Precision Recall Diagramms

3.5.4: Mittelwertbildungen

3.5.5: Testkollektionen

Abb. 34: Testkollektionen (nach Griffiths Luckhurst & Willett 1986 und Dumais, 1991)

3.5.6: Die TREC Experimente


3.5.6.1: Relevanzbestimmung

Abb. 35: Überprüfung der Relevanzbeurteilung bei TREC-2 nach Harman (1995)

Abb. 36: Größe der Grundmenge der auf Relevanz beurteilten Dokumente nach Harman (1995 - WWW, 1996 - WWW)

4: Neuere IR Methoden und Ansätze

4.1: Vektorraummodell als Fuzzy Set Ansatz

4.1.1: Unscharfe Mengen

4.1.1.1: Fuzzy Set

Abb. 37: Beispiele von Fuzzy Sets als Beschreibung von Lebensaltern

4.1.1.2: Träger, Kern, Schnitte und Höhe


4.1.1.3: Aussage:

Abb. 38: Rekonstruktion des Wertes der Zugehörigkeitsfunktion aus einem a - Schnitt.

4.1.1.4: Vereinigung, Durchschnitt und Komplement

Abb. 39: Vereinigung und Durchschnitt von unscharfen Mengen

4.1.2: Verallgemeinerte Boolesche Verfahren


4.1.2.1: Das MMM-Modell
4.1.2.2: Das Paice Modell
4.1.2.3: Das P-Norm Modell

4.2: Der probabilistische Retrieval Ansatz

4.2.1: Wahrscheinlichkeitsrechnung in endlichen Mengen

4.2.1.1: Endlicher Wahrscheinlichkeitsraum


4.2.1.2: Beispiel: Würfel

4.2.1.3: Bedingte Wahrscheinlichkeit und Unabhängigkeit

4.2.2: Abschätzung des Retrievalstatuswerts nach Fuhr

Abb. 40: Beispiele mit Relevanzangaben zur Schätzung des Retrievalstatuswertes zu einer Anfrage q=t1,...,t6

Abb. 41: Neue Dokumente und ihr Retrievalstatuswert

4.2.3: Robertson - Spark Jones Formel

4.3: Logikbasierte Modelle des Information Retrieval

Abb. 42: Modellieren von Wissen durch Regeln

4.3.1: Imaging

Abb. 43: Imaging

Abb. 44: Probleme des Imaging

4.3.2: Bayes'sche Inferenznetze

Abb. 45: Inferenznetz für das Information Retrieval nach Turtle und Croft 1990


4.3.2.1: Die Dokumentenschicht
4.3.2.2: Die Textrepräsentationsschicht
4.3.2.3: Die Konzeptrepräsentationsschicht

Abb. 46: Inferrenznetz des MAGIC Systems

Abb. 47: Inferenznetz, wie es zur Implementierung von INQUERY verwendt wurde (nach Turtle und Croft 1991)

4.3.3: Abduktive Anfrageoptimierung

4.4: Korpusbasierte Verfahren

Abb. 48: Aus dem Lob - und dem Brown-Korpus mit Kookurrenzdaten berechnete Assoziationen zu drei Termen

4.4.1: Der assoziative Ansatz

4.4.2: Kookurrenzverfahren


4.4.2.1: Term-Term-Matrizen
4.4.2.2: Anwendung im IR
4.4.2.3: Häufigkeit der Terme
4.4.2.4: Expansion von Termen oder Anfragen
4.4.2.5: Größe der Dokumentensammlung
4.4.2.6: Eine Untersuchung zur Bestimmung von Suchtermen

Abb. 49: Ergebnisse der Studie zur Simulationen der Wortwahl (Ferber, Wettler & Rapp 1995)


4.4.2.7: Komplexere Kookurrenzverfahren

4.4.3: Anwendung im mehrsprachigen Retrieval

Abb. 50: Ergebnisse der Studie zum mehrsprachigen Retrieval (nach Sheridan und Ballerini, 1996)

4.4.4: Deskriptoren bestimmen

Abb. 51: Datensatz aus der Idis Datenbank

Abb. 52: Mittlere Precision Werte bei einem Recall von 0.75 für unterschiedliche Werte der Parameter x und y.

Abb. 53: Parameterwerte für die sich nach den verschiedenen Maßen beste Ergebnisse für die Trainingsmenge ergaben mit den entsprechenden Ergebnissen für die Testmenge.

4.4.5: Latent Semantic Indexing

4.5: TREC: Passagenretrieval, Pseudo-Relevance-Feedback und verbesserte Ähnlichkeitsmaße

4.5.1: Die TREC 3 Ergebnisse von SMART

Abb. 54: Die SMART Verfahren aus TREC 3

Abb. 55: Die SMART Verfahren in TREC 3

4.5.2: Die TREC 4 Ergebnisse von SMART

Abb. 56: Vergleich der Ergebnisse nach der neuen Normierung

Abb. 57: Die SMART Verfahren aus TREC 4

Abb. 58: Die SMART Verfahren in TREC 4

4.5.3: Ein Spreading Activation Modell

Abb. 59: Das Nezt des PIRCS Systems

Abb. 60: Die PIRCS Verfahren aus TREC 4

Abb. 61: Die PIRCS Verfahren in TREC 4

4.5.4: INQUERY in TREC 4

Abb. 62: Ergebnisse mit INQUERY in TREC 4

4.5.5: Das Okapi System

Abb. 63: Ergebnisse mit Okapi in TREC 4

4.5.6: Schwerpunkte von TREC 5

Abb. 64: Ergebnisse einzelner Systeme aus TREC 4 mit unterschiedlichen Relevanzbeurteilungen

4.6: Strukturinformationen

4.6.1: Standard Generalized Markup Language (SGML)


4.6.1.1: SGML Elemente
4.6.1.2: Element Attribute
4.6.1.3: SGML Entities

4.6.2: HTML und XML

4.7: Metadaten


4.7.1: Dublin Core

Abb. 65: SGML Definitionen für Dublin Core Elemente (nach Weibel, Godby, Miller, Daniel 1996)


4.7.2: Warwick Framework

Abb. 66: SGML Definitionen für das Warwick Framework

4.8: Digitale Bibliotheken


4.8.1: Inhalte einer digitalen Bibliothek
4.8.2: Services
4.8.3: Archivierung