Information Retrieval
Information Retrieval
Uni-KölnInstitut für Sprachliche InformationsverarbeitungComputerlinguistik IJ. Hermes13.10.200916-17.30h
ReferentenAdalbert Wrona
Klaus Jettkant
Klassisches Information RetrievalDefinition und EinführungEntwicklungenArten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei SuchmaschinenRankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Klassisches Information RetrievalDefinition und EinführungEntwicklungenArten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei SuchmaschinenRankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Klassisches Information RetrievalDefinition und EinführungEntwicklungenArten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei SuchmaschinenRankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Definition und Einführung
� Information Retrieval ist gezieltes Abrufen von Information aus unstrukturiertem Material (gewöhlich Dokumente), dass in großen Sammlungen gespeichert ist (gewöhnlich auf Rechnern)
� alle Verfahren, die mit der Aufbereitung, Speicherung und Wiedergewinnung (Recherche) von Wissen (Texte, Fakten) zu tun haben
Definition und Einführung
Konzepte� Vagheit: Der Benutzer kann sein "diffuses"
Informationsbedürfnis nicht präzise und formal ausdrücken. Die Anfrage enthält daher vage Bedingungen.
� Unsicherheit: Dem System fehlen Kenntnisse über den Inhalt der Dokumente. Dies führt zu fehlerhaften und fehlenden Antworten. Probleme bei Texten bereiten z. B. Homographe (Wörter, die gleich geschrieben werden; z. B. Bank - Geldinstitut, Sitzgelegenheit) und Synonyme (Bank und Geldinstitut)
Klassisches Information RetrievalDefinition und EinführungEntwicklungen
Arten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei SuchmaschinenRankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Entwicklungen
Vier Entwicklungen haben das Aufkommen des Information Retrieval in Online Datenbanken im wesentlichen beeinflusst:
1. Wachsende Anerkennung der Bedeutung von Information (Sputnik-Schock)
2. Digitalisierung von Referatorganen, Schriftstücken
3. Entwicklung im Computerbereich: 4. Entwicklung der Telekommunikationsnetze
Klassisches Information RetrievalDefinition und EinführungEntwicklungenArten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei SuchmaschinenRankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Arten von Datenbanken
� Referenz- oder Literatur-DB
� Volltext-DB
� Fakten-DB
Klassisches Information RetrievalDefinition und EinführungEntwicklungenArten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei SuchmaschinenRankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Terme und Indexierung
� Terme
� Deskriptoren
� Indexierung
� Thesaurus
� Relationen
� Weitere Merkmale
Klassisches Information RetrievalDefinition und EinführungEntwicklungenArten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei SuchmaschinenRankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Lemmatisierung / Stemming
� Grundformenreduktion
� Stammformenreduktion
Klassisches Information RetrievalDefinition und EinführungEntwicklungenArten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei SuchmaschinenRankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Retrieval Modelle
� Mengentheoretische Modelle: Boolsche Logik
� Algebraische Modelle: Vektor-Raum-Modelle
� Probabilistische Modelle: stochastische Verfahren, Abstufung über Wahrscheinlichkeiten (z.B. Inferenznetze)
Retrieval Modelle
Das Boolesche Retrieval
OR � Es werden die Dokumente gefunden, die entweder
Element der Menge 1 oder Element der Menge 2 oder Element beider Mengen sind
AND
� Es werden die Dokumente gefunden, die sowohl Element der Menge 1 als auch Element der Menge 2 sind
Retrieval Modelle
Das Boolesche Modell
NOT
� Es werden die Dokumente gefunden, die Element der Menge 1, aber nicht Element der Menge 2 sind
Retrieval Modelle
Das erweiterte Boolesche Retrieval
� Werte werden mathematisch über einem Interval [0,1] definiert, wobei null für "falsch", eins für "wahr" steht.
Retrieval Modelle
Grenzen und Nachteile der BooleschenRecherche
Klassisches Information RetrievalDefinition und EinführungEntwicklungenArten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei SuchmaschinenRankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Klassisches Information RetrievalDefinition und EinführungEntwicklungenArten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei SuchmaschinenRankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Die Größe des Web und seine Abdeckung durch Suchmaschinen
Die Betreiber von Suchmaschinen werben in der Regel damit "The Worlds Information" (Google) zugänglich zu machen.
Die Größe des Web und seine Abdeckung durch Suchmaschinen
Indexierte Dokumente 2004/2005
• Google: ~8 Mrd. Dokumente
• MSN: ~5 Mrd. Dokumente
• Yahoo: ~5 Mrd. Dokumente
• Teoma: ~2,5 Mrd. Dokumente
Die Größe des Web und seine Abdeckung durch Suchmaschinen
Indexierte Dokumente 2005
• Yahoo: 20 Mrd Dokumente
• Google: „etwa drei mal so viel“
Seitdem sind keine Angaben über Indexgrößen veröffentlicht mehr worden.
Klassisches Information RetrievalDefinition und EinführungEntwicklungenArten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei SuchmaschinenRankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Strukturinformationen
Für die Erschließung von Web-Dokumenten ist die Einbeziehung der Dokumentstruktur von besonderer Bedeutung.
Strukturinformationen
Unterscheidung der Dokumente aufgrund ihrer Struktur nach
• Free Text (Fließtext)
• Structured Text (strukturierter Text)
• Semistructured Text (schwach strukturierter Text)
Strukturinformationen
Explizit inhaltsbeschreibendeHTML-Tags
� abbr Abkürzung� acronym Akronym� address Adresse� blockquote abgesetztes Zitat� cite Zitat� code Quellcode� usw.
HTML-Tags, die zur Extraktion von Strukturinformationen eingesetzt werden können
� b fett � big, small größere/kleinere
Schrift in Relation� br Zeilenumbruch � font size Schriftgröße � hr Trennlinie � i kursiv� usw.
Strukturinformationen
In den Datenbanken der Suchmaschinen werden die Dokumente (dokumentarische Bezugseinheit - DBE) durch einen Repräsentanten (Dokumentationseinheit) repräsentiert.
Klassisches Information RetrievalDefinition und EinführungEntwicklungenArten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei Suchmaschinen
RankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Anwendung klassischer Verfahren des IR bei Suchmaschinen
Die Unterschiede zwischen klassischem Information Retrieval und Web Retrieval lassen sich in vier Klassen unterteilen:
• Dokumentenkorpus
• Inhalt
• Nutzer
• Eigenarten des IR-Systems
Anwendung klassischer Verfahren des IR bei Suchmaschinen
Bei der automatischen Erschließung der Web-Suchmaschinen bleibt stets die Frage offen, ob auch wirklich alle relevante Information gefunden wurde und ob Dokumente ausgeschlossen werden, die als qualitativ nicht relevant angesehen werden können.
Anwendung klassischer Verfahren des IR bei Suchmaschinen
Boolesche Retrievalsysteme
• kostengünstige Umsetzung (AND, OR, AND NOT)
• Implementiert in Interfaces der Suchmaschinen
• dennoch keine wirkliche Boolesche Suche
Anwendung klassischer Verfahren des IR bei Suchmaschinen
Vektorraummodell
• sucht nach Ähnlichkeiten zwischen Dokumenten und Suchanfrage
• Abfrageterme und Dokumente als Vektor
• Gemeinsamkeiten als Kosinus des Winkels zwischen den Vektoren
Anwendung klassischer Verfahren des IR bei Suchmaschinen
Vektorraummodell
Anwendung klassischer Verfahren des IR bei Suchmaschinen
Wie man anhand der Eigenschaften des Booleschen und des Vektorraum orientierten Modell sieht, setzen die Betreiber Mischformen von Modellen ein, wie zum Beispiel auch das erweiterte Boolesche Modell, welches um Wertigkeiten von Suchtermen erweitert wurde.
Anwendung klassischer Verfahren des IR bei Suchmaschinen
Das probalistische Modell
• Wahrscheinlichkeitsermittlung der Relevanz
• Ähnlichkeit zwischen der Anfrage und dem Dokument
• Ähnlichkeitswert abhängig von der Häufigkeit der Suchbegriffe im Dokument
Klassisches Information RetrievalDefinition und EinführungEntwicklungenArten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei SuchmaschinenRankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Ranking
Rankingverfahren sollen erreichen, dass Dokumente innerhalb einer Trefferliste so sortiert werden das die relevantesten Dokumente oben stehen.
Ranking
Anfrageabhängige Faktoren
• Worthäufigkeiten
• Position der Suchbegriffe im Dokument
Anfrageunabhängige Faktoren
• Bestimmung der Qualität bzw. die Autorität eines Dokuments unabhängig von einer Suchanfrage
Ranking
Anfrageabhängige Faktoren im Ranking:
� Dokumentspezifische Wortgewichtung (WDF� Wortabstand� Position der Suchbegriffe� Reihenfolge der Suchbegriffe in der Anfrage� Metatags� Stellung der Suchbegriffe innerhalb des Dokuments� Betonung von Begriffen durch HTML-Elemente� Groß-/Kleinschreibung� Inverse Dokumenthäufigkeit (IDF)� Ankertext� Sprache- Geo-Targeting.
Ranking
Anfrageunabhängige Faktoren im Ranking
� Verzeichnisebene� Anzahl eingehende Links� Linkpopularität� Klickhäufigkeit� Aktualität� Dokumentlänge� Dateiformat� Größe der Site
Klassisches Information RetrievalDefinition und EinführungEntwicklungenArten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei SuchmaschinenRankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Informationsstatistische und Informationslinguistische Verfahren
Textstatistische Verfahren gehören zu den klassischen Verfahren des Information Retrieval.
Informationsstatistische und Informationslinguistische Verfahren
Auswertung von Nutzungsstatistischen bestimmt die Güte eines Dokuments
Informationsstatistische und Informationslinguistische Verfahren
Informationslinguistische Verfahren dienen der Vorbereitung von Dokumenten zur Indexierung
Informationsstatistische und Informationslinguistische Verfahren
Informationslinguistische Verfahren
• Worterkennung • Morphologie • Lexikon • Syntax • Semantik • Diskursanalyse • Pragmatik • Stemming• Rechtschreibfehler
Informationsstatistische und Informationslinguistische Verfahren
Soundex-Algorithmus am Beispiel von „economics"
(1) Der erste Buchstabe des Wortes bleibt erhalten (2) Falls der zweite Buchstabe identisch mit dem ersten
ist, übergehe ihn [E](3) Falls zwei aufeinander folgende Buchstaben im
Ausgangswort identisch sind, übergehe den jeweils zweiten
(4) Falls zwei aufeinander folgende Buchstabenim entstehenden Codewort identisch sind, notiere
beide (5) Übergehe die Buchstaben AEIOUYWH [Ecnmcs](6) Falls ein Buchstabe CGJKQSXZ ist, notiere C [ECnmC](7) Falls ein Buchstabe BFPV ist, notiere B (8) Falls ein Buchstabe DT ist, notiere D (9) Falls ein Buchstabe MN ist, notiere M [ECMMC](10) Die Buchstaben L und R bleiben erhalten (11) Falls der letzte Buchstabe AIOUY, notiere Y
Klassisches Information RetrievalDefinition und EinführungEntwicklungenArten von DatenbankenTerme und IndexierungLemmatisierung und StemmingRetrieval Modelle
Web Information RetrievalDie Größe des Web und seine Abdeckung durch SuchmaschinenStrukturinformationenAnwendung klassischer Verfahren des IR bei SuchmaschinenRankingInformationsstatistische und Informationslinguistische VerfahrenLinktopologische Rankingverfahren
Linktopologisches Rankingverfahren
Neben den Vorgestellten Kriterien zur Bewertung von Qualität und Güte von Dokumenten im Web stellt das Linktopologische Rankingverfahren das wichtigste Verfahren dar
Linktopologisches Rankingverfahren
Methoden des Linktopologischen Verfahrens
• Sience Citation Indexing
• PageRank
• Kleinbergs HITS
• Hilltop
Linktopologisches Rankingverfahren
Sience Citation Indexing
(Eugene Garfield)
Wissenschaftliches Prinzip der Zitation
Linktopologisches Rankingverfahren
PageRank-Verfahren
(Lawrence Page)
Ordnet jedem indexierten Dokument einen statischen PageRank-Wert zu
Linktopologisches Rankingverfahren
PageRank-Verfahren
(Lawrence Page)
Linktopologisches Rankingverfahren
Kleinbergs HITS
Das Kleinbergs-HITS Verfahren (Hyperlink induced topic search) versucht, die Einschränkungen einfacher Linkzählungen bzw. die themenunabhängige Bewertungen von Webseiten zu überwinden und wichtigsten Seiten (sog. Autoritäten) passend zum Thema der jeweiligen Suchanfrage ermitteln.
Linktopologisches Rankingverfahren
Kleinbergs HITS
Linktopologisches Rankingverfahren
Hilltop
Hilltop beschreibt ein Verfahren, das die besten Seiten zu populären Themen mit Hilfe von sogenannten Expert Pages finden soll.
Linktopologisches Rankingverfahren
Anmerkung zu den Problemstellungen des Linktopologischen Verfahrens
Bibliographie
� LEWANDOWSKI, Dirk; OCKENFELD, Marlies (Hg.): Web Information Retrieval. Technologie zur Informationssuche im Internet. Reihe de Informationswissenschaft der DGI. Band 7, Frankfurt am Main 2005
� BENJAMINS, V. Richard; CASANOVAS, Pompeu; BREUKER, Joost; GANGEMI, Aldo: Law and the Semantic Web. Legal Ontologies, Methodologies, Legal Information Retrieval, and Applications, Berlin Heidelberg, 2005
� BERRY, Michael W.; BROWNE, Murray; DONGARRA, Jack J. (Hg.): Understanding Search Engines. Methematical Modeling and Text Retrieval. Second Edition. Software - Environments - Tools, Philadelphia, 2005
� GROSSMANN, David A.; FRIEDE, Ophir: Information Retrieval. Algorithms and Heuristics. Second Edition, Dordrecht, 2004
� BUßMANN, Hadumod: Lexikon der Sprachwissenschaft, Stuttgart, 1990� MÜLLER, Horst M. (Hg.): Arbeitsbuch Linguistik, Paderborn, 2002� POETSCH, Eleonore: Information Retrieval. Einführung in Grundlagen
und Methoden, Saarbrücken, 1998
URLS
� "Yahoo hat über 20 Mrd. Items Indexiert", internetmarketing-news.de
http://www.internetmarketing-news.de/2005/08/09/yahoo-hat-uber-20-mrd-items-indexiert/
� "Größe des Web", The Web Characterization Project des Online Computer Library Center (OCLC)
http://www.oclc.org/research/projects/archive/wcp/
� [Google, MSN, Yahoo, Ask Jeeves]