S2D2 IPD, Universität Karlsruhe 10. Januar 2006 Spezifikations- und Selektionsmethoden für Daten und Dienste Verfahren des Information Retrieval Maxim

S2D2

IPD, Universität Karlsruhe10. Januar 2006

Spezifikations- und Selektionsmethoden für Daten und Dienste

Verfahren des Information Retrieval

Maxim [email protected]

IPD, Universität Karlsruhe

S2D2

2Maxim Jochim

▪Grundlagen

–Information Retrieval

–Datenbank

–Datum <-> Wissen

▪Verfahren–Bool'sches

–Fuzzy

–Vektorraummodell

▪Gewichtung

Information Retrieval

Inhaltliche Suche in den Texten

– Textretrieval oder Dokumentenretrieval

– aber nicht nur

Klassische Anwendung:– Literaturdatenbanken (Digitale Bibliotheken)

Populär durch Internet Suchmaschinen– google

– yahoo

– zunehmend auch Bildersuche


S2D2

3Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Unterschiede zum klassischen Datenbanksystem

Schwierigere Formulierung einer Anfrage zum aktuellen Informationsbedürfnis

Sehr viele Antworte, aber nur wenig interessante.– Gesamtzahl der Treffer bei Internet-Suchmaschinen

Rangordnung der Antworten.– 90% der Nutzer betrachten nur die 10 ersten Antworte

Repräsentation des Inhalts.– Systeminterne Repräsentation des Inhalts steht teilweise nicht

im Zusammenhang mit dem Inhalt des Dokuments. (zumindest unsicherheitsbehaftet)


S2D2

4Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Beispiel einer Datenbankrecherche

Beispieldatenbank „AUTOS“

Besteht aus Dokumenten die Artikel beschreiben durch:– bibliografische Angaben

– kurze Zusammenfassung

– Einordnung in hierarchisches Indexsystem

– Stichwörter

Retrievalsystem liefert nur Dokumente mit angegebenen Wortkombinationen– ! Es müssen Stichwörter überlegt werden, die den

Informationsbedarf möglichst genau widerspiegeln.


S2D2

5Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung


Suche nach:– Literatur zum Stand der Forschung im Bereich der alternativen

Energien für den Einsatz in den Personenkraftwagen. Dabei interessiert uns insbesondere, was man bei BMW erreicht hat und Mercedes interessiert uns überhaupt nicht.


S2D2

6Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung


Suche nach:– Literatur zum Stand der Forschung im Bereich der alternativen

Energien für den Einsatz in den Personenkraftwagen, Dabei interessiert uns insbesondere, was man bei BMW erreicht hat und Mercedes interessiert uns überhaupt nicht.


S2D2

7Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung


Stichwörter:– Alternative Energie

– Personnenkraftwagen

– BMW

– Mercedes

Anfrage:– ALTERNATIVE ENERGIE and PERSONENKRAFTWAGEN and

BMW and not MERCEDES

Interpretation des Systems:– Suche alle Dokumente in denen „PERSONENKRAFTWAGEN“

und „ALTERNATIVE ENERGIE“ und „BMW“ nicht aber „MERCEDES“ irgendwo im Text vorkommen. Nicht „case sensitiv“; mit „white space“ (z.B. Zeilenumbruch)


S2D2

8Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Daten – Information - Wissen

Daten – syntaktische Ebene– Datenbasis ist eine Ansammlung von Werten ohne einer

realwertigen Semantik

Information – semantische Ebene– verwendbare, interpretierbare Semantik

– Datenbanksysteme und IR-Systeme enthalten Information

Wissen – pragmatische Ebene– Wissen ist die Information, die von jemanden in einer konkreten

Situation zur Lösung von Problem benötigt wird.


S2D2

9Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Wissen ist Information in Aktion

Wissen oft nicht vorhanden und muss gesucht werden– Informationsflut

– für gezieltes Wissen ist man bereit zu zahlen:∗ Tageszeitung

∗ werbefreies Fernsehen

IR-Systeme um Wissen zu extrahieren– Aufbereitung der Daten durch Retrieval-Verfahren

– Bereitstellung des benötigten Wissens in der konkreten Situation


S2D2

10Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Verbreitete Verfahren des Information Retrieval

Werden hier besprochen:– Bool'shes Retrieval

– Fuzzy-Retrieval

– Vektorraummodell

Existieren aber viel mehr– nicht in diesem Vortrag


S2D2

11Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Bool'sches Retrieval

Historisch erstes Retrieval Modell

Logische Klarheit,– doch ungeordnete Antwortmenge

Erster Einsatzzweck:– Retrieval mit Schlitzlochkarten. Auch später aus

Speichergründen das einzig anwendbare Modell.

– sofortige Entscheidungen

Implementierung mit invertierten Listen– zu jedem Term wird eingetragen, in welchen Dokumenten er

vorkommt.


S2D2

12Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Grundidee

Bis heute nicht grundlegend in Frage gestellt.

Einfache Mengenopertation auf Dokumentenmenge, die durch Attributwerte der Dokumente charakterisiert sind– z. B. Auftreten der Terme im Dokument

Anfrage: Verknüpfung der Attribut-Wert-Paare

Attribut-Wert-Paar in der Anfrage:– Menge der Dokumente mit dem entsprechenden Attributwert


S2D2

13Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Definition

D– Menge aller Dokumente

T– Menge der Indexterme

T: D → T, t(d) = ti

– ein Attribut

Dt,ti = t -1(ti) = { d D | t(d) = ti }

– Menge der Dokumente die durch den Attributwert ti charakterisiert sind

– Mehrere Attribut-Wert-Paare möglich

∗ (t, ti) AND (s, si) liefert Dt,ti ∩ Ds,si


S2D2

14Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Bool'sches Retrieval auf Textdokumente

Die wichtigsten Attribute das auftreten von Termen in verschiedenen Feldern der Dokumente

z. B. Attribut– Auftreten des Terms t1 im Titelfeld

Durch TI charakterisierte Dokumentenmenge:

} |{ 1 ,1

TitelfeldimtenthältDdD trueTIt

} ,{:1

truefalseDTI t


S2D2

15Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Bool'sches Retrieval auf Textdokumente

– Auftreten des Terms t1 in der Stichwortliste des Dokuments

– DTSt1, true t1 := ALTERNATIVE ENERGIE

– DTSt2, true t2 := PERSONNENKRAFTWAGEN

– DTSt3, true t3 := BMW

– DTSt4, false t4 := MERCEDES

Antwortmenge:

– Enthält alle Dokumente die t1, t2, t3 enthalten nicht aber t4

) ,( ) ,( ) ,( ) ,(

) ,( ) ,( ) ,( ) ,(

1111

4321

falseTStrueTStrueTStrueTS

falseTSANDtrueTSANDtrueTSANDtrueTS

tttt

tttt

DDDD

DA

} ,{: truefalseDTSit


S2D2

16Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Bool'sches Retrieval

Wurde für IR-ungeeignet befunden weil:– Größe der Antwortmenge ist schwer kontrollierbar

– keine Ordnung der Ergebnisse nach Relevanz

– Trennung in „gefunden“ und „nicht gefunden“ zu streng

∗ z.B q = t1 AND t2 AND t3 = false für t1,t2=true aber t3=false

– umständliche Anfrageformulierung

– schlechte Retrievalqaulität im vergleich zu anderen Modellen


S2D2

17Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Fuzzy Retrieval

Fragebeschreibung und Retrievalfunktion wie bei Bool'schem Retrieval

Gewichtete Indexierungen bei Dokumentbeshreibung

– dti [0, 1 ] : ein Attribut im Dokument hat einen Wert aus [0, 1]

Rangordnung der Antwortdokumente durch Retrievalfunktion:– ρ(qk

d, dt) [0, 1]


S2D2

18Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Fuzzy Retrieval

Beispiel:

Antwort: {d1, d2}

aber…

39.0 )d (q, , 0.4 )d (q,

0.99) (0.39, d , 0.4) (0.4, d

t t q

} t,{t T

21

21

21

21


S2D2

19Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Fuzzy Retrieval

Retrievalfunktion ungünstig, da:– d2 hat den höheren t2 wert, doch wegen der Minimumfunktion bei

der Konjunktion ist das höhere Gewicht des t1 für das höhere Retrievalgewicht von d1 ausschlaggebend

} ,{:

39.0 )d (q, , 0.4 )d (q,

0.99) (0.39, d , 0.4) (0.4, d

t t q

} t,{t T

21

21

21

21

21

ddAntwort


S2D2

20Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Beurteilung

Nachteil des strickten Bool‘schen Retrievals entfällt.

Vorteil:– Rangordnung der Dokumente durch gewichtete Indexierung

Nachteile:– Retrievalqualität ist immer noch schlecht im Vergleich zu, VR-

Modell

– Umständliche Frageformulierung wie beim bool'schen Retrieval


S2D2

21Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Vektorraummodell

Das bekannteste Modell

Dokumente und Fragen sind Punkte im Vektorraum

Suche nach Dokumenten, deren Vektoren ähnlich dem Fragevektor sind

Der Vektorraum wird als orthonormal angenommen– alle Termvektoren sind linear unabhängig

– alle Termvektoren sind normiert


S2D2

22Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Beschreibung des Modells

Gewichtete Indexierung bei der Dokumentbeschreibung– ähnlich der des Fuzzy- Retrievals

Gleiche Struktur der Frage:

Retrieval Funktion:– verschiedene Vektor-Ähnlichkeitsmaße, z. B. Kosinus-, Overlap-,

Jaccard-Maß, meistverwendete ist aber das Skalarprodukt:

1, ..., n id d ditt

Dt für mit

1, ..., n iq q qikk

Qk für mit

tktk dqdq

) ,(


S2D2

23Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

"Alternative Energie für den Einsatz in den Personenkraftwagen von BMW, nicht von Mercedes"

Beispiel

Ausgabe der Dokumente entsprechend den Retrievalgewichten, also d1, d4, d3, d2.

ti qki d1i d2i d3i d4iAlternative Energie 3 1 0,5 1

in den 1 1 0,5

Personenkraftwagen 1 1 1

Von 0,5 1 0,5

BMW 2 1 1 1

Mercedes -1 1 1

Retrievalgewicht

6 0,52 5


S2D2

24Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Beurteilung

Vorteile:– benutzerfreundlich da, einfaches, anschauliches Modell, mit

einfacher Frageformulierung

– unmittelbar auf neue Kollektionen anwendbar∗ im Gegensatz zu den probabilistischen Modellen, wo das Sammeln

der Relevance-Feedback-Daten teilweise erforderlich ist

– gute Retrievalqualität in Kombination mit Gewichtungsformeln.

Nachteile:– heuristischer Ansatzes bei der Berechnung der

Indizierungsgewichte erschwert die Erweiterung der Dokumentrepräsentation ∗ (Z. B. stärkere Gewichtung der Terme im Titelfeld)

– kein Bezug auf die Retrievalqualität, ∗ theoretisch nicht zu begründen, warum die zu einer Frage ähnlichen

Dokumente auch relevant sein sollen.


S2D2

25Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Gewichtung

Bis jetzt:– Ähnlichkeitsfunktionen betrachtet ohne zu wissen woher die

Gewichte kommen.

Einfachste Methode: von Hand– Gewichtungen bei der Indexierung eingegeben lassen ziemlich

– Gewichtung der Terme durch Anfragenden∗ diese können durch Feedbackmethoden verfeinert werden

– ! die Gewichtungen von dem jeweiligen Kontext abhängig∗ bei der Indexierung von dem Dokument, das indexiert wird,

∗ bei der Anfrage von dem Informationsbedürfnis der Anfragenden.


S2D2

26Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Kontext unabhängige Gewichtung

Feststellung:– Nicht fachgebietbezogene Terme sind schlechte Suchterme

∗ z. B. Ergebnis, Methode, Verfahren, Zusammenfassung

– gute Terme, die nur in bestimmten Wissensgebieten vorkommen

Betrachtung der Häufigkeit der Terme in Dokumenten– Terme, die in sehr vielen Dokumenten vorkommen, haben eine

schlechte Aussagekraft

– Termen, die nur in sehr wenigen Dokumenten vorkommen erzielen im allgemeinen keine umfassenden Suchergebnisse


S2D2

27Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Häufigkeit der Terme

– Häufige Terme können beim Retrieval durch eine Stoppwortliste ausgeschlossen oder durch eine schwache Gewichtung abgeschwächt werden.

– Seltene Terme werden meistens nicht gesondert behandelt, d.h., die rechte Trennlinie wird in der Regel ignoriert.


S2D2

Maxim Jochim

▪Grundlagen


–Datenbank

–Datum <-> Wissen


–Fuzzy

–Vektorraummodell

▪Gewichtung

Documents

S2D2 IPD, Universität Karlsruhe 10. Januar 2006 Spezifikations- und Selektionsmethoden für Daten und Dienste Verfahren des Information Retrieval Maxim