advertisement

IWM2 1 IR

50 %
50 %
advertisement
Information about IWM2 1 IR
Entertainment

Published on November 14, 2007

Author: Nevada

Source: authorstream.com

advertisement

2.1 Information Retrieval durch Volltextsuche:  2.1 Information Retrieval durch Volltextsuche Dokumente werden als Text interpretiert, der aus Wörtern besteht. Suche bezieht sich immer auf Wörter. Beispiel: Ein Kreditinstitut hat Richtlinien über die Vergabe von Krediten. Angenommen es kommt ein Kunde aus Bärlund und will einen Kredit in Höhe von 40.000 DM zum Kauf eines Autos. Der Sachbearbeiter muss auf Basis dieser Richtlinien entscheiden, ob der Kredit gewährt wird. Aufgabe: „Finde alle Dokumente, die Hinweise zur die Kreditbeurteilung für Personen aus Bärlund enthalten.“ Kreditbearbeiter formuliert eine Suchanfrage: Ich möchte alle Dokumente in denen die Wörter Kredit, Person und Bärlund vorkommen Kreditrichtlinie Nr. 247 Allerweltsbank AG Vorstand Die Analyse von 5000 Krediten an Personen und Firmen hat ergeben, dass Kredite an Personen aus Halva und Bärlund durch Sicherheiten oder Bürgschaften abgesichert werden müssen. Kredite an Firmen aus diesen Ländern unterliegen besonderen Richtlinien. Prinzip der Volltextsuche Variabilität der Sprache:  Variabilität der Sprache Beispieldokumente: Erwartete Antwort: Suchanfrage: Dokument D2 aber: Nicht alle Wörter der Anfrage kommen in dem Dokument Das einzige übereinstimmende Wort Bärlund kommt auch in D4 vor Problembereich Wortformen:  Problembereich Wortformen Flexionsformen: Konjugation und Deklination eines Wortes Haus - Hauses - Häuser laufen - läuft - lief - gelaufen Derivationsformen: verschiedene Wortformen zu einem Wortstamm Formatierung - Format - formieren - formatieren Komposita: mehrgliedrige Ausdrücke Deutsch: zusammengeschrieben oder Bindestrich, z.B. Geschäftsprozess Wissensmanagement Englisch: Wortfolgen knowledge management management of knowledge information retrieval retrieval of information information was retrieved Wörter kommen in mehreren Formen vor Problem: Wortbedeutung:  Problem: Wortbedeutung Synonyme Samstag - Sonnabend Junggeselle - unverheirateter Mann selten - nicht oft Varianten in der Schreibweise Delfin - Delphin Abkürzungen VW - Volkswagen Quasi-Synonyme, z.B. fremdsprachliche Bezeichnungen Rechner - Computer Homographen: verschieden gesprochene Wörter mit gleicher Orthographie Tenor Polyseme: Wörter mit mehreren Bedeutungen Bank Umgang mit bedeutungsgleichen oder bedeutungsähnlichen Wörtern Datenretrieval vs. Information Retrieval:  Datenretrieval vs. Information Retrieval Datenbankanfragen beziehen sich auf vordefinierte Struktur sind sehr exakt Daten werden auf der rein syntaktischen Ebene verarbeitet Dem DBMS ist es egal ob Anfrage select k.name, k.telefonnr from kunde k, bestellung b where k.kundennr = b.kundennr oder select k.sdf, k.fgsfdg from sfsdf k, dasfds b where k.gfsgh = b.ewrgsah Informationen sind oft unstrukturiert (z.B. Text, Bilder) Information Retrieval sucht auf der Bedeutungsebene Das System muss Inhalt von Dokument und Anfrage interpretieren Trotz unterschiedlicher Formulierungen sollen möglichst alle relevanten Dokumente gefunden werden. Auswahl nicht 100% richtig Dokumente werden nach Relevanz sortiert Probleme des Information Retrieval:  Probleme des Information Retrieval Effizienz Effektivität Wortformen Wortbedeutungen Naiver Ansatz zum Information Retrieval:  Naiver Ansatz zum Information Retrieval Durchsuchen aller Dokumenten nach den Wörtern der Suchanfrage ist nicht sinnvoll zu aufwendig, da man jedes Dokument anpacken müsste Besser: Zu jedem Dokument wird eine Repräsentation erzeugt, die alle relevanten Informationen enthält, für die Suche geeignet ist und effizient implementiert wird Ein Retrievalmodell:  Ein Retrievalmodell Ein Retrievalmodell besteht aus einer Menge D von Repräsentationen für Dokumente Einer Menge Q von Repräsentationen für Benutzeranfragen einer Rankingfunktion R, die jedem Anfrage/Dokumentpaar eine reelle Zahl (das Ranking) zuweist, nach der Dokumente sortiert werden: R: Q x D ® IR Je höher das Ranking, desto besser passt ein Dokument auf die Anfrage Retrievalsystem:  Retrievalsystem Schnittstelle Speichersystem Dokumente Anfrage- bearbeitung Darstellung erzeugen IDs zuweisen Ranking Anfrage Gewichtete Dokumente Terme Menge von Dokumenten Indexwörter Dokumente & IDs speichern Dokumentobjekte Text Antwort Frage Zu jedem Dokument wird ein Index und eine eindeutige ID erzeugt und zusätzlich zu den Dokumenten gespeichert Index: Dokumente können auf viele verschiedene Arten repräsentiert werden, z.B. Schlagworte, Menge aller enthaltenen Worte, Volltext, usw. Speicherung erfolgt in einem effizienten System bzw. Datenstruktur Die Anfrage wird nur mit Hilfe des Index und der ID beantwortet Durch die ID erhält man einen Verweis auf das Dokument Prinzipien der Volltextsuche:  Prinzipien der Volltextsuche Zwei prinzipielle Ansätze, um mit Problemen bei der Wortsuche umzugehen: informatischer Ansatz: Anfragebeantwortung ohne Vorverarbeitung Der Text ist ein Kette von Zeichen Suche ist Operation auf Zeichenketten computerlinguistischer Ansatz: Anfragebeantwortung mit Vorverarbeitung Normalisierung von Wortformen weitgehende Unabhängigkeit von konkreter Formulierung des Textes Dokumentrepräsentation nach informatischem Ansatz:  Dokumentrepräsentation nach informatischem Ansatz Der Text wird als Folge von Zeichen aufgefasst. Die Dokumentrepräsentation enthält den vollen Text. Zerlegung des Textes in einzelne Wörter: Leer- und Interpunktionszeichen werden als Worttrenner aufgefasst; meist keine Unterscheidung von Gross- und Kleinschreibung Dokumente müssen komplett durchsucht werden, dafür werden String Matching Algorithmen eingesetzt String Matching Problem: Finde alle Vorkommen eines Musters P im Text T Dokumentrepräsentation nach informatischem Ansatz: Beispiel:  Dokumentrepräsentation nach informatischem Ansatz: Beispiel d(D1): aktiengesellschaften ein kredit an eine aktiengesellschaft birgt ein geringeres risiko als ein kredit an eine person. d(D2): personen aus bärlund und halva bei krediten an personen aus halva oder bärlund muss eine bürgschaft oder eine sicherheit vorliegen d(D3): autofinanzierung bei einem kredit zum kauf eines autos muss eine kaskoversicherung für das auto abgeschlossen werden d(D4): firmen aus bärlund für kredite an firmen aus bärlund gelten keine gesonderten regelungen Naiver Algorithmus:  Naiver Algorithmus Das Muster wird Stück für Stück an dem Text vorbeigeschoben Von der ersten Position an wird jeweils das Muster mit dem darunterliegenden Tabelleninhalt verglichen. Im Fall eines Fehlvergleichs wird das Muster um ein nach rechts geschoben: Aufwand bei weitem nicht optimal: Information aus früheren Vergleichen wird nicht genutzt Beispiel für einen effizienteren Algorithmus: Der Boyer-Moore-Algorithmus:  Beispiel für einen effizienteren Algorithmus: Der Boyer-Moore-Algorithmus Grundidee: Ausnutzung der Information, die in dem Suchmuster enthalten ist Vergleiche das Muster von rechts nach links mit der aktuellen Tabellenposition Verschieben des Musters in Abhängigkeit des Zeichens: Kommt das Zeichen an der aktuellen Position in dem Muster vor, dann wird das Muster soweit nach rechts verschoben, bis das aktuelle Zeichen mit seinem Vorkommen im Muster übereinstimmt Kommt das Zeichen an der aktuellen Position nicht in dem Muster vor, dann wird das Muster um die ganze Länge nach rechts verschoben Es wird zu Beginn eine Distanztabelle errechnet, die zu jedem Buchstaben angibt, wie weit das Muster bei einem Vorkommen des Buchstabens zu verschieben ist Der Boyer-Moore-Algorithmus: Verdeutlichung der Idee:  Der Boyer-Moore-Algorithmus: Verdeutlichung der Idee aus [Gumm,Sommer 2000] Boyer-Moore-Algorithmus: Beispiel:  Boyer-Moore-Algorithmus: Beispiel aus [Gumm,Sommer 2000] Volltextsuche: Informatischer Ansatz:  Volltextsuche: Informatischer Ansatz Wie bekommt man beim informatischen Ansatz die Variabilität der Sprache in den Griff? Es stehen Zeichenketten-Operatoren zur Verfügung für einzelne Wörter: Truncation- und Maskierungsoperatoren, z. B. könnte ? für genau ein Zeichen stehen * für beliebig lange Zeichenfolgen Folgen von Wörtern: Kontextoperatoren, z.B. , beliebige Wortreihenfolge # gleicher Satz [n] genauer Wortabstand <n> maximaler Wortabstand Truncation und Maskierung: Suchen nach unterschiedlichen Wortformen:  Truncation und Maskierung: Suchen nach unterschiedlichen Wortformen Truncation: Wildcards stehen für Zeichenfolgen am Anfang und Ende eines Wortes, um beliebige Vorsilben und Endungen zuzulassen schreib* findet Konjugationen von schreiben, z.B. schreiben, schreibt, schreibst, schreibe ??schreiben findet man Wörter wie anschreiben, beschreiben, aber nicht verschreiben Maskierung bezieht sich auf Zeichen in der Mitte eines Wortes, da im Deutschen durch Deklination und Konjugation nicht nur die Endungen betroffen sind schr??b* kann stehen für schreiben, schrieb h??s* kann stehen für Haus, Häuser Nachteil: Man findet auch unerwünschte Wörter: schr??b* findet auch schrauben h??s* findet auch Hans, Hanse, hausen, hassen Kontextoperatoren: Suche nach Varianten in der Formulierung:  Kontextoperatoren: Suche nach Varianten in der Formulierung Kontextoperatoren ermöglichen die Suche nach Textphrasen, die in unterschiedlicher Form vorkommen, z.B. genauer Wortabstand Bezug [3] Telefonat Bezug nehmend auf unser Telefonat maximaler Wortabstand text <2> retrieval text retrieval text and fact retrieval beliebige Wortreihenfolge retrieval <1> , information information retrieval retrieval of information Bewertung des informatischen Ansatzes:  Bewertung des informatischen Ansatzes Effizienz Keine Vorverarbeitung notwendig Für Suche in grossen Dokumentmengen zu aufwendig Anwendbar für Suche nach Dokumenten innerhalb eine Ordners innerhalb eines Dokumentes (Editoren, Browser) Wortformen keine Unterstützung durch Suchalgorithmus allerdings dadurch sprachunabhängig Wortbedeutungen werden nicht berücksichtigt Das Auffinden von Termen in Dokumenten kann durch Vorverarbeitung der Dokumente erheblich beschleunigt werden Volltextsuche: Computerlinguistischer Ansatz:  Volltextsuche: Computerlinguistischer Ansatz Die Terme der Dokumentrepräsentation sind Normalformen der wichtigen Wörter Stoppwortelimination: Löschen nicht bedeutungstragender Wörter Stoppwortliste: Menge zu löschender Wörter, z.B. Artikel, Konjuktionen, Präpositionen, Hilfsverben Bei der Indexerzeugung werden die Stoppwörter nicht berücksichtigt Grundformreduktion: Flexions- und Derivationsformen werden automatisch in die Grundform übertragen Es gibt zwei verschiedene Vorgehensweisen lexikalische Verfahren heuristische Verfahren Erzeugung von Termen der Dokumentrepräsentation Lexikalische Verfahren:  Lexikalische Verfahren Grundformreduktion durch Einzelfallbehandlung über Lexikon Lexikon mit folgenden Relationen Flexionsform - Grundform Hauses - Haus ging - gehen Derivationsform - Grundform Lieblosigkeit - lieblos Berechnung - rechnen Komposita - Dekomposition Haustür - Tür Armbanduhr - Uhr Nachteil: großer Aufwand für Aufbau und Pflege des Lexikons Heuristiken zur Grundformreduktion:  Heuristiken zur Grundformreduktion Mit wenigen Regeln lassen sich sehr viele Fälle der Grundformreduktion abdecken, z.B: Schneide die Endungen „e“, „en“, „er“ ab Banken - Bank Häuser - Häus Ersetze Umlaute: ä - a, ö - o, ü - u Häus - Haus usw. Vollständige Regelmenge muss viele Ausnahmen berücksichtigen Oft nimmt man Fehler in Kauf Indexierung: Dokumentrepräsentation als Menge von Grundformen:  Indexierung: Dokumentrepräsentation als Menge von Grundformen Beispiel: d(D1): kredit aktiengesellschaft bergen risiko person d(D2): kredit person halva bärlund bürgschaft sicherheit vorliegen d(D3): finanzierung kredit kauf auto kaskoversicherung abschliessen d(D4): kredit firm bärlund regelung Beantwortung von Anfragen:  Beantwortung von Anfragen Klassifikation von Information Retrieval Modellen: Nicht-probabilitisches Information Retrieval Boolesches Retrieval Vektorraummodell Fuzzy-Retrieval Probabilistisches Information Retrieval basiert auf Wahrscheinlichkeitswerten für Benutzerinteresse „Intelligentes“ Information Retrieval Concept Search Ähnliche Dokumente Boolesches Retrieval:  Boolesches Retrieval In einer Anfrage können Terme mit den Booleschen Operatoren AND, OR oder NOT verknüpft werden Die Retrievalfunktion R wird rekursiv definiert: R(ti,di) = wi,j (wi,j = 1 wenn der Term ti in di vorkommt, und 0 sonst) R(q1 AND q2,di) = R(q1,di) AND R(q2,di) R(q1 OR q2,di) = R(q1,di) OR R(q2,di) R(NOT q,di) = NOT R(q,di) Die Retrievalfunktion R kann nur die Werte 0 oder 1 liefern. Die Antwort auf eine Anfrage teilt also die Dokumente in gefundene (R = 1) und nicht gefundene (R = 0). Beispiel für Boolesches Retrieval:  Beispiel für Boolesches Retrieval Dokumentrepräsentationen: d(D1): kredit aktiengesellschaft risiko person bergen d(D2): kredit person halva bärlund bürgschaft sicherheit vorliegen d(D3): finanzierung kredit kauf auto kaskoversicherung abschliessen d(D4): kredit firma bärlund regelung Resultat:Dokument D2 Resultat: Dokumente D1, D2 und D4 Vor- und Nachteile des Booleschen Retrieval:  Vor- und Nachteile des Booleschen Retrieval Vorteile Einfach zu implementieren, keine hohen Anforderungen an Rechner Nachteile Die Grösse der Antwortmenge ist schwer zu kontrolllieren (Bsp: t1 AND t2 : 100.000 Treffer, t1 AND t2 AND t3 : 0 Treffer) R ist eigentlich keine echte Rankingfunktion, da nur zwischen relevant (1) und nicht relevant (0) unterschieden wird (zu starke Trennung): Zu der Anfrage q = t1 AND t2 AND t3 werden Dokumente mit zwei gefundenen Termen ebenso zurückgewiesen wie solche mit 0 gefundenen Termen. Terme können nicht gewichtet werden. Boolesches Retrieval ist für Information Retrieval nicht besonders gut geeignet Vektorraummodell: Veranschaulichung:  Vektorraummodell: Veranschaulichung Terme spannen einen Raum auf Jeder Term entspricht einer Dimension Jedes Dokument entspricht einem Punkt im Raum bzw. einem Vektor vom Nullpunkt Dokumentvektor: Der Wert jeder Dimension entspricht dem Gewicht (Bedeutung) des Terms im Dokument, z.B. Häufigkeit des Vorkommens Beispiel: Terme: kredit, person, land zwei Dokumente Vektorraummodell zum Information Retrieval:  Vektorraummodell zum Information Retrieval Für effizientes Retrieval benötigt man einen Index, der ein effizientes Retrieval unterstützt. Volltext-Index als Vektor: Es gibt n verschiedene Terme t1, ... tn Jedes Dokuments D entspricht einem Vektor dj = (w1,j,...,wn,j) Jede Komponente wi,j repräsentiert das Vorkommen des Terms ti in dem Dokument dj Eine Menge von Dokumenten kann man durch eine Matrix beschreiben: jede Spalte der Matrix entspricht einem Dokumentvektor Anfrage-Beschreibungen sind Vektoren: q = (w‘1,...,w‘n) Dokumentvorverarbeitung: Darstellung von Dokumenten:  Dokumentvorverarbeitung: Darstellung von Dokumenten Wichtige Fragen: Was sind die Terme? Relevante Wörter Wie wird die Matrix effizient implementiert? wenig Speicherbedarf schnelle Beantwortung von Anfragen t1 t2 t3 t4 d1 w1,1 w2,1 w3,1 w4,1 d2 w1,2 w2,2 w3,2 w4,2 d3 w1,3 w2,3 w3,3 w4,3 ... dn w1,n w2,n w3,n w4,n Darstellung der Dokumente durch Vektoren: Die wi,j bezeichnen Gewichte. Die wi,j repräsentieren das Vorkommen des Terms ti im Dokument dj Retrieval im Vektorraummodell:  Retrieval im Vektorraummodell Das Vektorraummodell erlaubt effizienteres Retrieval Der Index eines Dokuments d = (d1,...,dn) und Frage-Beschreibungen sind Vektoren: q = (q1,...,qn) Gesucht ist das Dokument, das der Anfrage am ähnlichsten ist Eine mögliche Rankingfunktion ist das Skalarprodukt: R(q,d) = q * d Multipliziere die Komponenten und summiere sie auf Skalarprodukt als Rankingfunktion Entwicklung des Vektorraummodells:  Entwicklung des Vektorraummodells Wir gehen verschiedene Stufen durch Koordinatenmatching Termhäufigkeit (term frequency - TF) inverse Dokumenthäufigkeit (inverse document frequency - IDF) vollständiges Vektorraummodell Koordinatenmatching: Binäre Vektoren:  Koordinatenmatching: Binäre Vektoren Alle Gewichte wi,j sind entweder 0 oder 1 Binäre Vektoren repräsentieren nur, ob ein Term in dem Dokument vorkommt wi,j = 1 wenn tj in dem Dokument di vorkommt wi,j = 0 sonst Beispiel 1): 1) Der Darstellung wegen sind die Terme in den Zeilen und die Dokumente in den Spalten geschrieben Koordinatenmatching:  Koordinatenmatching Resultat: q * d1 = q * d2 = q * d3 = q * d4 = 2 3 2 2 Je mehr der gesuchten Terme in einem Dokument vorkommen, desto besser Anfrage ist ebenfalls ein Vektor, repräsentiert die darin vorkommenden Terme Diskussion Koordinatenmatching:  Diskussion Koordinatenmatching mächtiger als Boolesches Modell: ist eine Art Zwischenstufe zwischen Booleschem AND und Booleschem OR Drei entscheidende Nachteile berücksichtigt nicht die Häufigkeit von Termen in Dokumenten berücksichtigt nicht die Seltenheit von Termen über alle Dokumente lange Dokumente werden bevorzugt Term Frequency (TF): Häufigkeiten von Wörtern:  Term Frequency (TF): Häufigkeiten von Wörtern Term Frequency: Wie häufig taucht ein Term im Dokument auf, d.h. wij = m wenn der Term ti m-mal im Dokument dj vorkommt d1 d2 d3 d4 abschliessen 0 0 1 0 aktiengesellschaft 2 0 0 0 auto 0 0 3 0 bärlund 0 2 0 2 bergen 1 0 0 0 bürgschaft 0 1 0 0 finanizierung 0 0 1 0 firma 0 0 0 2 halva 0 2 0 0 kaskoversicherung 0 0 1 0 kauf 0 0 1 0 kredit 2 1 1 1 person 1 2 1 0 regelung 0 0 0 1 risiko 1 0 0 0 sicherheit 0 1 0 0 vorliegen 0 1 0 0 D1: Aktiengesellschaften Ein Kredit an eine Aktiengesellschaft birgt ein geringeres Risiko als ein Kredit an eine Person. D2: Personen aus Bärlund und Halva Bei Krediten an Personen aus Halva oder Bärlund muss eine Bürgschaft oder eine Sicherheit vorliegen. D3: Autofinanzierung Bei einem Kredit zum Kauf eines Autos muss eine Kaskoversicherung für das Auto abgeschlossen werden D4: Firmen aus Bärlund Für Kredite an Firmen aus Bärlund gelten keine gesonderten Regelungen Retrieval mit Vorkommenshäufigkeiten:  Retrieval mit Vorkommenshäufigkeiten Resultat: q * d1 = q * d2 = q * d3 = q * d4 = 3 5 2 3 IDF - Inverse Document Frequency:  IDF - Inverse Document Frequency Je seltener ein Term insgesamt ist, desto höher ist es zu bewerten, wenn er in einem Dokument vorkommt IDF (inversed document frequency) Faktor: in wievielen Dokumenten taucht ein Term ti auf? IDF ist um so höher, je seltener ein Term in der Dokumentkollektion auftritt Gewichte wji in Dokumentvektoren werden nun so berechnet: wi,i = tfi;j * idfi TF- und IDF-Faktoren:  TF- und IDF-Faktoren Bezeichnungen fi,j Anzahl der Vorkommen von Term ti in Dokument dj fi Anzahl der Dokumente, in denen Term ti vorkommt n Anzahl der Dokumente in der Kollektion Beispiele für die Berechnung von TF: tfi,j = fi,j (siehe vorherige Folien) tfi,j = 1 + loge (fi,j) Beispiele für IDF: idfi = 1 / fi idfi = loge (1 + n/fi,j) Es gibt noch Dutzende andere Varianten, die sich in der Qualität nur wenig unterscheiden Es gibt verschiedene Möglichkeiten, die TF- und IDF-Faktoren zu berechnen Retrieval mit TF und IDF-Faktoren:  Retrieval mit TF und IDF-Faktoren Resultat: q * d1 = q * d2 = q * d3 = q * d4 = 0.83 1,91 0,58 1,25 Natürlichsprachliche Anfragen:  Natürlichsprachliche Anfragen ist äquivalent zu Denn: Stoppwörter werden eliminiert Wörter werden in Grundform umgewandelt Ähnliche Dokumente finden:  Ähnliche Dokumente finden Formulieren einer guten Anfrage kann mühsam sein Wenn man ein gutes Dokumente hat, dann könnte man dieses als Vergleichsdokument nutzen um ähnliche Dokumente zu finden Wie kann man vorgehen? Vergleiche Dokumente dj nicht mit Anfrage, sondern mit vorgegebenem Dokument d Skalarprodukt s(dj,d) Cosinusmass cos(dj,d) Gleiche Verfahren anwendbar wie bei Suchanfrage! Ähnliche Dokumente finden:  Ähnliche Dokumente finden Resultat: d2 * d1 = d2 * d3 = d2 * d4 = 4 3 5 Finde die ähnlichsten Dokumente zu d2 Vollständiges Vektorraummodell:  Vollständiges Vektorraummodell Wir haben die Gewichte modifiziert, aber noch die gleiche Formel für die Rankingfunktion: Skalarprodukt: berechnet Ähnlichkeit von Dokumenten Nachteil: Skalarprodukt bevorzugt grosse Dokumente gegenüber kleinen Alternative Rankingfunktionen sind z.B. Euklidischer Abstand zwischen Endpunkten der Vektoren Nachteil: bevorzugt kleinere Dokumente, deshalb nicht besser Cosinus-Mass: Winkel zwischen den Vektoren Je kleiner der Winkel, desto ähnlicher sind q und d Das Cosinus-Mass vermeidet die Beeinflussung durch die Dokumentgrösse Cosinus-Mass als Rankingfunktion:  Cosinus-Mass als Rankingfunktion Sei q der Winkel zwischen q und d Da alle Werte wi,j in den Vektoren grösser oder gleich 0 sind, gibt es nur Winkel zwischen 0° und 90° je grösser der Winkel q, desto kleiner cos q je kleiner der Winkel q, desto grösser cos q Ein Dokument d ist um so relevanter für die Anfrage q, je mehr die Richtung der Vektoren für d und q übereinstimmen Beurteilung des Vektorraummodells:  Beurteilung des Vektorraummodells Das Vektorraummodell ... ist relativ einfach und anschaulich, ist effizient, ordnet die Dokumente nach Relevanz, ist unmittelbar auf neue Kollektionen anwendbar Das Modell enthält viele heuristische Komponenten oder Parameter, deren Gültigkeit beim Übergang auf neue Kollektionen fraglich ist, z.B. Heuristiken zur Berechnung der Terme Berechnungen von TF, IDF Rankingfunktion Es gibt keine theoretische Begründung, warum die zu einer Frage ähnlichen Dokumente auch relevant sein sollen Welche Parametereinstellungen gut sind, hängt von der Dokumentenkollektion ab Bewertung von IR-Verfahren: Recall und Precision:  Bewertung von IR-Verfahren: Recall und Precision Bei Datenbanksystemen beurteilt man die Kriteren Laufzeit und Speicherplatzbedarf Bei Information Retrieval kommt aufgrund der fehlenden Exaktheit noch die Beurteilung der Güte der Ergebnisse hinzu Zwei Masse haben sich durchgesetzt Recall: Anteil relevanter Dokumente, die gefunden wurden Precision: Anteil der gefundenen Dokumente, die relevant sind Berechnung von Recall und Precision:  Berechnung von Recall und Precision Evaluation: Führe mehrere Anfragen aus und berechne Recall- und Precisionwerte IR liefert eine sortierte Menge von Dokumenten Relevante Dokumente sollen möglichst weit vorne auftauchen Betrachte nur die ersten X Dokumente des Resultats Problem: Woher weiss man, welche Dokumente relevant sind? Möglichkeiten Nutze Referenzmenge von Dokumenten, die von Experten schon durchleuchtet wurden, z.B. die Sammlung der TREC (Text Retrieval Conference) Ist für Forschung interessant, für Anwendungen im Unternehmen nicht, da Dokumente in Unternehmen spezielle Eigenschaften haben können Verwende repräsentative aber überschaubare Teilmenge der Unternehmensdokumente Implementierung: Zugriffsstrukturen:  Implementierung: Zugriffsstrukturen Ziel: Finden von Dokumenten über die enthaltenen Wörter Invertierte Listen Dokumente mit eindeutigen Identifikator (URL) Zu jedem Term: Liste von Dokumenten, die den Term enthalten Beispiel: < person; 1, 2, 3 > < bärlund; 2, 4 > TF-Faktoren gibt es für jede Kombination von Termen und Dokumenten, werden also in der invertierten Liste gespeichert < person; (1, 1), (2, 2), (3, 1) > < bärlund; (2,2), (4,2) > IDF-Faktoren: Es existiert nur ein IDF-Faktor pro Term ändert sich, wenn neue Dokumente hinzukommen deswegen abspeichern dieses Wertes im Lexikon Beispiel: Invertierte Liste und Wörterbuch:  Beispiel: Invertierte Liste und Wörterbuch Wörterbuch: abschliessen (1) aktiengesellschaft (1) auto (1) bärlund (2) bergen (1) bürgschaft (1) finanizierung (1) firma (1) halva (1) kaskoversicherung (1) kauf (1) kredit (4) person (3) regelung (1) risiko (1) sicherheit (1) vorliegen (1) In Klammern steht die Anzahl der Dokumente, in denen der Term vorkommt. Daraus kann man den IDF-Faktor berechnen Für die effiziente Implementierung werden spezielle Datenstrukturen verwendet Relevanz-Feedback:  Relevanz-Feedback Reformulierung von Anfragen nach Rückmeldung durch den Benutzer Prinzip: 1. Benutzer stellt eine Anfrage q 2. Der Benutzer bewertet die Relevanz der ersten Dokumente der Rangordnung 3. Das System berechnet eine verbesserte Anfrage aufgrund des Feedbacks (z.B. Übernahme von Termen der ausgewählten Dokumente, Ausschluss von Termen der nicht gewählten Dokumente) 4. Retrieval mit der verbesserten Anfrage 5. Evtl. Wiederholung der Schritte 2-4 Informationsfilterung:  Informationsfilterung Idee: Nutze Wissen über den Nutzer, um ihm relevante Information zur Verfügung zu stellen Ansätze der Informationsfilterung:  Ansätze der Informationsfilterung Inhaltsbasierte Filterung Für jeden Nutzer eigene Filter Profil: Repräsentation des Nutzerinteresses Soziale Filterung Idee: Information ist relevant, wenn andere Benutzer, die bisher ähnliches Verhalten gezeigt haben, die Information ebenfalls als relevant betrachtet haben Bewertung der Relevanz von Informationen durch Benutzer Vergleich von Profilen mehrerer Nutzer Eine einfache Variante findet man z.B. bei Amazon: Käuferverhalten bei Büchern, CDs Personen, die dieses Buch gekauft haben, haben auch ... Probleme beim Filtern:  Probleme beim Filtern Akquisition und Pflege der Benutzerprofile Manuelle Pflege ist aufwendig, wird oft vernachlässigt Benutzer gibt Feedback, ob ein Dokument relevant ist Wie motivieret man den Benutzer dazu? Heuristik: Wenn der Benutzer ein Dokument lange geöffnet hat, dann hat er es wohl gelesen und dann war es wohl interessant Fragwürdig: Vielleicht stellt sich erst am Ende heraus, dass es irrelevant war, vielleicht war der Benutzer in der Mittagspause, ... Relevanz ist nicht zeitlos wie z.B. Musikgeschmack, sondern bezogen auf aktuelle Situation/Problemstellung/Anfrage Probabilistische Modelle:  Probabilistische Modelle „Trainieren“ bzw. „Lernen“ der Relevanzurteile durch Nutzerbefragung für gegebenen Dokumentmenge Berechnung der Termgewichte über Ermittlung der Wahrscheinlichkeit, dass ein aufgetretener Term relevant bzw. irrelevant ist N Anzahl der Dokumente in der Kollektion R Anzahl der relevanten Dokumente bzgl. Anfrage ri Anzahl der relevanten Dokumente, die Term ti enthalten ni Anzahl der Dokumente mit Term ti Problem: Wie bekommt man die Relevanzurteile von Nutzern? Abschätzung von Wahrscheinlichkeiten:  Abschätzung von Wahrscheinlichkeiten Wir geben dem Benutzer eine Reihe von Dokumenten zur Auswahl Der Benutzer sagt uns welche davon relevant und welche nicht relevant sind Zum Beispiel: Beantworte Anfrage durch Vektorraummodell Präsentiere die Ergebnisse dem Benutzer Wahrscheinlichkeiten können dann aus den jeweiligen Anzahlen der Dokumente abgeschätzt werden Benutzer steuert das Systemverhalten über Feedback Konzeptbasierte Suche:  Konzeptbasierte Suche Bisherige Suchverfahren: Berücksichtigung von Wortformen Aber: Suche ist nur erfolgreich, wenn der Suchende dasselbe Vokabular benutzt wie der Autor eines Dokuments Ziel: Suchen was gemeint ist, nicht was gesagt ist Suchen nach Gruppen von Wörtern, die gemeinsam das Gesuchte beschreiben unter Berücksichtung z.B. von Beispiel: Finden von Informationen unabhängig von verwendeten Wörtern soll auch Dokumente finden mit Kraftfahrzeug, Van, Familienwagen, ... Konzepte haben Bezug zu Wortkontext:  Konzepte haben Bezug zu Wortkontext Ohne zusätzliche Hilfsmittel sind Wortbeziehungen nicht bekannt. Idee: Zwei Wörter stehen in Beziehung zueinander, wenn Sie oft gemeinsam vorkommen Das Konzept zu einem Wort wird durch den Kontext bestimmt Beispiel: Das Wort Bank in Wirtschaftsnachrichten wird Bank wahrscheinlich eher zusammen mit Wörtern wie Geld, Wertpapiere, oder Kredit auftreten, in Romanen wird Bank vielleicht mit Wörtern wie Park, Baum, sitzen usw. vorkommen Konzepte sich spezifisch für die Dokumentkollektion Kann man Konzepte automatisch bestimmen? Wiederholung: Matrixdarstellung von Dokumentmengen:  Wiederholung: Matrixdarstellung von Dokumentmengen Betrachte Matrix als Vektoren von Dokumenten jede Spalte ist ein Dokumentvektor Ähnlichkeit von Dokumenten wird durch Rankingfunktion berechnet Skalarprodukt von Vektoren Cosinus-Mass von Vektoren Konzeptbasierte Suche: Automatische Erkennung von Wortähnlichkeiten:  Konzeptbasierte Suche: Automatische Erkennung von Wortähnlichkeiten Man kann die Matrix auffassen als Menge von Dokumentvektoren (bekannt aus Volltextsuche) Menge von Termvektoren Jede Zeile ist ein Termvektor Die Komponenten sind die Doku-mente, in denen der Term vorkommt Ähnlichkeit von Termen: Rankingfunktion auf Termvektoren Skalarprodukt, Cosinus-Mass (vgl. Volltextsuche) Beispiel: Ähnlichkeiten zwischen bärlund und halva 4 bärlund und person 4 bärlund und auto 0 Konzeptbasierte Suche: Berücksichtigung von Wortnähe:  Konzeptbasierte Suche: Berücksichtigung von Wortnähe Konzeptbasierte Suche auf Dokumentebene ist in vielen Fällen zu allgemein Verfeinerung: Berücksichtigung von Wortnähe, z.B. Wenn Wörter in gemeinsamen Abschnitt vorkommen ist die Beziehung enger Erfordert erweiterten Index mit Speicherung von Positionen von Termen wird in vielen Suchmaschinen bereits gemacht Anwendung der konzeptbasierten Suche:  Anwendung der konzeptbasierten Suche Automatisch Das Suchsystem erweitert die Suchanfrage um Konzepte Beispiel: Könnte intern z.B. um die „ähnlichsten“ Konzeptterme erweitert werden: Manuell Das System bietet dem Benutzer die zu seiner Anfrage ähnlichen Terme an Das System liefert auf Anfrage die ähnlichsten Terme. Der Benutzer erweitert die Anfrage um die Begriffe, die ihm am geeignetsten erscheinen Konzeptbasierte Suche: Diskussion:  Konzeptbasierte Suche: Diskussion Konzeptbasierte Suche berücksichtigt nicht die Bedeutung von Wörtern Konzepte werden manchmal auch als Term- oder Wortähnlichkeit bezeichnet Wortähnlichkeit hat aber nichts mit Bedeutungsähnlichkeit zu tun Konzepte sind spezifisch für die Dokumentkollektion (vgl. das Beispiel mit Bank) In verschiedenen Dokumentmengen sind die Konzepte zu einem Begriff unterschiedliche Die Güte der Konzeptbasierten Suche ist schwer zu beurteilen Eigene Versuche mit einem System zur Konzeptsuche haben gezeigt, dass im Ranking in den ersten 10 „ähnlichen“ Wörtern viele waren, die einen Bezug zu dem Ausgangswort hatten, zu anderen war ein Bezug nicht nachzuvollziehen Wissensentdeckung:  Wissensentdeckung Interessanter Effekt: Wissensentdeckung durch Konzeptsuche Beispiel: Versuche mit einer (veralteten) Dokumenten einer Nachrichtenagentur Gesucht: Ähnliche Terme zu „Volkswagen“ Ergebnis unter anderem: VW, Wolfsburg, fraud, car, ... Überraschung: Was hat fraud (Betrug, Täuschung) mit Volkswagen zu tun? Auflösung: Suchanfrage mit Volkswagen und fraud brachte Artikel über einen ehemaligen Manager, der Geld unterschlagen hatte Ohne Konzeptsuche wäre dieser Zusammenhang nicht erkennbar gewesen Semantische Hilfsmittel bei der Suche:  Semantische Hilfsmittel bei der Suche Die bisherigen Suchverfahren waren rein syntaktisch, ohne Kenntnis der Wortbedeutungen Die Suche kann oft verbessert werden, wenn Hilfsmittel zur Verfügung stehen, die etwas über die Semantik des Suchraums aussagen Wörterbücher alphabetisches Verzeichnis von Begriffen, z.B. zur Festlegung eindeutiger Schreibweise Übersetzung (mehrsprachiges Wörterbuch) Thesaurus Geordnete Zusammenstellung von Begriffen und ihren Beziehungen Thesauri sind eine spezielle Form von Wissensstrukturen

Add a comment

Related presentations

Related pages

Comparative evaluation of life cycle assessment models for ...

Comparative evaluation of life cycle assessment models for solid waste management ... IWM2 2.8E-04 1.1E-02 3733 3 10 ORWARE 5.6E-07 1.7E-03 305,464 3 9
Read more

Em - Defense Technical Information Center

IwM2 * uau Ml-F(rtT (APY RFSIl 1iTION ... $1 CuRIT Y CLA; ... The trends shown in Table 3 are consistent with the ir-backbonding 18. Table 3.
Read more

HON - Ignition Chairs - HON Office Furniture – Desks ...

Learn more about Ignition. HON Office Furniture; Our Products. Chairs; Endorse ... Ignition Brochure - pdf 1 MB Download Ignition Cut-Sheets
Read more

Casos prácticos de Information Seeking en el diseño de ...

Serrano Cobos, Jorge Casos prácticos de Information Seeking en el diseño de sistemas de información web., 2006 . In VIII Jornadas de Gestión de la ...
Read more

The Underside - South Africa Rock Climbing Routes Wiki

The Underside. From South Africa ... IR Irreverence 25 5B Guy Holwill June 2006 ... (Part 1) 21 4B Doug Ward June 2006 IWM2 I Want More (Part 2) ...
Read more

The Product of Two Pseudo-Differential Operators.

The Product of Two Pseudo-Differential Operators 57 for all x E ~n, where 00 >.(x,ry) ... Proof of Theorem 8.1 Fork= 0, 1, 2, ... , we define Ak by
Read more

Bristol news., January 08, 1878, Image 2

... January 08, 1878, Image 2 About Bristol news. (Bristol, Va. & Tenn.) ...
Read more

Combinación de logs internos y externos en la predicción ...

... n. 1, pp. 11-19 ... http://informationr.net/ir/10-2/paper217 ... http://www.cs.kent.ac.uk/people/staff/iwm2/personal/ieewebcoll. pdf ...
Read more