Adaptive Informationssuche im Internet

Inhaltsverzeichnis

  Abbildungsverzeichnis  III

  Tabellenverzeichnis  IV

  Algorithmenverzeichnis  V

  Beispielverzeichnis  VI

  Abkürzungsverzeichnis  VII

1  Einleitung  1

1.1  Motivation  1

1.2  Zielsetzung  2

1.3  Gliederung  3

2  Grundlagen  5

2.1  Data mining, Data Warehouse  5

2.1.1  Regeln  6

2.1.1.1  Klassifikationsregeln  6

2.1.1.2  Charakteristische Regeln  7

2.1.1.3  Regressionsregeln  8

2.1.1.4  Assoziationsregeln  8

2.1.2  Cluster  9

2.2  Information Retrieval  9

2.2.1  Standardverfahren  12

2.2.1.1  Boolesches Retrieval  13

2.2.1.2  Fuzzy Retrieval  15

2.2.1.3  Vektorraummodell  18

2.2.1.4  Cluster-Retrievalverfahren  22

2.2.1.5  Probabilistische IR-Verfahren  28

2.3  Software-Agenten  31

2.3.1  LAW: A learning Apprentice for the WWW  33

2.3.2  Syskill Webert  34

2.3.3  Letizia  34

2.3.4  WebWatcher  34

2.4  Selbstorganisierende Merkmalskarten  35

2.4.1  WEBSOM  38

2.5  Multidimensionale Skalierung  40

2.5.1  MDS nach dem Verfahren von Kruskal  43

2.5.2  MDS nach dem SMACOF-Verfahren  44

3  Eigener Ansatz  47

3.1  Szenario  47

3.2  Dokumentbearbeitung  48

3.2.1  Anforderungen an einen Stoppvektor  48

3.2.2  Anforderungen an einen Thesaurus  49

3.2.3  Generierung von Dokumentenvektoren  49

3.3  Dokumentenkartenerstellung  52

4  Simulation  53

4.1  Dokumentbearbeitung  53

II  adaptive Informationssuche im Internet  

4.1.1  Generierung eines Stoppvektors  53

4.1.2  Generierung eines Thesaurus  55

4.1.3  Generierung eines Dokumentenvektors  56

4.2  Dokumentenkartenerstellung  63

4.2.1  Definition eines Ähnlichkeitsmaßes  64

4.2.2  Anordnung der Dokumente nach dem CARD-Algorithmus  64

4.2.3  Anordnung der Dokumente mit MDS-Algorithmen  77

4.2.3.1  Anordnung nach dem Verfahren von Kruskal  77

4.2.3.2  Anordnung nach dem SMACOF-Verfahren  80

5  Softwarestruktur  83

5.1  Implementierung der Dokumentbearbeitung mit ACCESS  83

5.1.1  Generierung des Stoppvektors  83

5.1.2  Generierung eines Thesaurus  85

5.1.3  Erstellung des Dokumentvektors  88

5.2  Implementierung der Dokumentenkartenerstellung mit JAVA  90

5.2.1  Basismethoden  90

5.2.2  Der CARD-Algorithmus  93

5.2.3  Der MDS-Algorithmus nach Kruskal  95

5.2.4  Der MDS-Algorithmus nach der SMACOF-Methode  96

6  Diskussion und Ausblick Fehler Textmarke nicht definiert  

Anhang Fehler  Textmarke nicht definiert  

  Literaturverzeichnis XXVIII  

  adaptive Informationssuche im Internet  

  Abbildungsverzeichnis  

  Abbildung 1 : Überblick über die Funktionen eines IR-Systems  

  Abbildung 2 : Typische Formen für Zugehörigkeitsfunktionen  

  Abbildung 3 : Darstellung relevanter Begriffe  

  Abbildung 4 : Bildung von single-link Clustern für verschiedene Schwellwerte  

  Abbildung 5 : Beispiel einer Clusterhierarchie beim Clusterretrieval  

  Abbildung 6 : Architektur eines lernenden Agenten nach EBGP96  

  Abbildung 7 : unterschiedliche Ausgabefunktionen für Neuronen  

  Abbildung 8 : 2 dim. SOM  

  Abbildung 9 : Basisarchitektur der WEBSO-MMethode (nach HKLK97 )  

  Abbildung 10 : Konfiguration nach Anwendung von MDS auf die Flugdistanzen (nach  

  KW78 )  

  Abbildung 11 : Architektur des eigenen Modells  

  Abbildung 12 : Beispiel einer HTML-Seite  

  Abbildung 13 : Anordnung eines neuen Dokumentvektors nach CARD  

  Abbildung 14 : Punkte im kartesischen Koordinatensystem  

  Abbildung 15 : Bezeichnungen am rechtwinkligen Dreieck  

  Abbildung 16 : Berechnung der Position von d i  

  Abbildung 17 : Anordnung der Beispiel-DV aus Tabelle 14  

  Abbildung 18 : Berechnung der Position von d i bei fehlendem Schnittpunkt, Fall 1  

  Abbildung 19 : Berechnung der Position von d i bei fehlendem Schnittpunkt, Fall 2  

  Abbildung 20 : Anordnung der Beispiel-DV nach Modifikation des Abstandsmaßes  

  Abbildung 21 : Anordnung der Beispiel-DV mit Maximalabstand 10 000 000  

  Abbildung 22 : Anordnung der Beispiel-DV mit Abstandsmaß aus Formel (88 )  

  Abbildung 23 : Anordnung der Beispiel-DV nach modifiziertem CARD-Algorithmus  

  Abbildung 24 : Anordnung der Beispiel-DV mit CARD (2maliger Durchlauf)  

  Abbildung 25 : Anordnung der Beispiel-DV nach 10 maliger Neupositionierung  

  Abbildung 26 : Anordnung der Beispiel-DV nach 100 maliger Neupositionierung  

  Abbildung 27 : Anordnung der Städte nach Anwendung von MDS nach Kruskal  

  Abbildung 28 : Anordnung der Beispiel-DV nach MDS, Stress ???  

  Abbildung 29 : Anordnung der Beispiel-DV nach MDS Stress 0 ,239 ,  

Iterationsschritte  500  

  Abbildung 30 : Anordnung der Städte nach dem SMACOF-Algorithmus  

  Abbildung 31 : Anordnung der Beispieldokumente nach dem SMACOF-Algorithmus  

  Abbildung 32 : Anordnung der Beispieldokumente mit SMACOF UW ij 1 AGW ij  

  Abbildung 33 : Auszug aus dem Dokumentquelltext des Infodata-Thesaurus  

IV  adaptive Informationssuche im Internet  

  Tabellenverzeichnis  

Tabelle 1  : Daten Retrieval versus Information Retrieval  10

Tabelle 2  : Standardverfahren des IR  12

Tabelle 3  : Flugdistanzen zwischen 10 amerikanischen Städten (nach KW78 )  41

Tabelle 4  : Statistik des Stoppvektors  53

Tabelle 5  : Zipf'sches Gesetz  54

Tabelle 6  : Auszug aus der generierten Stoppwortliste  54

Tabelle 7  : Wortvektor für HTML-Seite aus Abbildung 12  58

Tabelle 8  : Um Stoppworte reduzierter Wortvektor  59

Tabelle 9  : Basisworte für zu ersetzende Worte aus Wortvektor  60

Tabelle 10  : Verwandte Begriffe für Basisworte aus Tabelle 9  61

Tabelle 11  : Wortvektor nach Synonymabgleich  61

Tabelle 12  : Werte der prozentualen Schranke  63

Tabelle 13  : Dokumentvektor für HTML-Seite aus Abbildung 12  63

Tabelle 14  : Beispiel-Dokumentvektoren  67

Tabelle 15  : Distanzen zwischen 9 amerikanischen Städten (nach SBO97 )  77

Tabelle 16  : ACCESS-Tabelle HTML-Code  84

Tabelle 17  : Auszug aus der Tabelle Vector mit den nach Häufigkeit  

  sortierten Stoppworten  84

Tabelle 18  : Auszug aus der Tabelle Worttabelle  86

Tabelle 19  : Synonyme in Tabelle Worttabelle  86

Tabelle 20  : Tabelle BF  87

Tabelle 21  : Verwandte Begriffe in Tabelle Worttabelle  87

Tabelle 22  : Tabelle VB  87

Tabelle 23  : in der Worttabelle enthaltene Worte aus Abbildung 33  88

  adaptive Informationssuche im Internet  V

  Algorithmenverzeichnis  

  Algorithmus 1 : Pseudo-Algorithmus zur hierarchischen Clusterbildung  23

  Algorithmus 2 : Pseudo-Algorithmus zur heuristischen Clusterbildung  24

  Algorithmus 3 : Pseudo-Algorithmus für eine top-down Clustersuche  26

  Algorithmus 4 : Pseudo-Algorithmus für eine bottom-up Clustersuche  27

  Algorithmus 5 : Pseudo-Algorithmus für einen Software-Agenten  32

  Algorithmus 6 : Pseudo-MDS Algorithmus  43

  Algorithmus 7 : Pseudo-Majorisierungs Algorithmus  44

  Algorithmus 8 : Pseudo-SMACOF Algorithmus  46

  Algorithmus 9 : Pseudo-CARD Algorithmus zur Dokumentenkartenerstellung  66

  Algorithmus 10 : Modifizierter Pseudo-CARD Algorithmus zur  

  Dokumentenkartenerstellung  73

  Algorithmus 11 : Endgültige Version des Pseudo-CARD Algorithmus  77

VI  adaptive Informationssuche im Internet  

  Beispielverzeichnis  

  Beispiel 1 : Klassifikationsregel  7

  Beispiel 2 : Charakteristische Regel  8

  Beispiel 3 : Assoziationsregel  8

  Beispiel 4 : Regeln zur Dokumentenvereinfachung  13

  Beispiel 5 : Boolesche Suche nach van Rijsberg in RIJS79 :  14

  Beispiel 6 : Dokumentenbeschreibung im Fuzzy Retrieval  17

  Beispiel 7 : Bewertung von Dokumenten beim Fuzzy Retrieval  17

  Beispiel 8 : Prozeß des Relevance Feedback  19

  Beispiel 9 : top-down Clustersuche  27

  Beispiel 10 : bottom-up Clustersuche  27

  Beispiel 11 : WEBSO-MArtikellandkarte für Newsgroup-Artikel  40

  Beispiel 12 : Auszug aus dem Infodata-Thesaurus  56

  Beispiel 13 : Auszug aus dem Quellcode eines HTML-Dokuments  58

adaptive Informationssuche im Internet VII

Abkürzungsverzeichnis

AGW Anteil gleicher Worte AVI Advanced visual interfaces ÄW Ähnlichkeitswert ASCII American Standard Code for Information Interchange BF Benutzt für Synonym BII Binary independence indexing BIR Binary independence retrieval BS Benutze Synonym CARD Comparison, Arrangement and Representation of Documents CR Clusterrepräsentant DKK Dokumentenkarte DM Data Mining DR Daten Retrieval DV Dokumentvektor DW Data Warehouse GIF Graphic interchange format GMD Gesellschaft für Mathematik und Datenverarbeitung HTML Hypertext Markup Language IDN Identifikationsnummer IIR Intelligentes Information Retrieval IM iterative Majorisierung IR Information Retrieval IT Informationstechnolgie JPEG Joint picture expert group KDD Knowledge Discovery in Databases KI Künstliche Intelligenz KNN Künstliche neuronale Netze MDS Multidimensionale Skalierung MIT Massachusetts Institute of Technology ML Maschinelles Lernen MP3 MPEG Layer 3 MPEG Motion picture expert group ÖFAI Österreichisches Forschungsinstitut für Artificial Intelligence PDF Portable document format PRP Probability ranking principle PS Postscript RSW Retrieval Status Wert

SMACOF Scaling by Majorizing a Complicated Function SOM selbstorganisierende Merkmalskarte SW Schwellwert TFIDF Term Frequency x inverse Document Frequency URL Universal resource locator

VIII adaptive Informationssuche im Internet

UW Unähnlichkeitswert VB Verwandter Begriff VRM Vektorraummodell WKK Wortkategoriekarte WWW World Wide Web

1 Einleitung

“The greatest problem of today is how to teach people to ignore the irrelevant, how to refuse to know things, before they are suffocated. For too many facts are as bad as none at all.” (W.H. Auden)

Die heutzutage im Internet vorhandene enorme und immer noch rapide anwachsende Datenmenge macht es einem Benutzer, der auf der gezielten Suche nach Informationen ist, nahezu unmöglich, sinnvoll relevante Informationen zu suchen bzw. zu finden. In der Regel wird er entweder keine der gesuchten Informationen erhalten oder aber so viele, daß ein Rausfiltern der tatsächlich gewünschten Informationen aus den redundanten Informationen einen enormen Zeitaufwand darstellt. Das alleinige Vorhandensein einer Fülle von Informationen/Datenmengen hilft dem Anwender demnach noch nicht, Informationen leichter und/oder schneller zu finden, als dies mit alt hergebrachten Methoden möglich war. Es ist somit notwendig, Systeme zu entwickeln, die den Anwender sinnvoll bei seiner Informationssuche unterstützen, ohne ihn in einer unkontrollierten Informationsflut ersticken zu lassen.

1.1 Motivation

Das aus dem ARPANET ¹ entstandene, ursprünglich als Versuchsnetz zur Kopplung verschiedenartiger Rechner entwickelte, globale Netzwerk, das heutzutage als Internet bezeichnet wird, hat sich in den letzten Jahren von einem, anfangs nur von einigen wenigen Forschungseinrichtungen genutzten Netzwerk zu einem, zur Zeit ca. 36,7 Millionen Hosts (Rechnern) umfassenden Netzwerk für die breite Öffentlichkeit entwickelt. Nach Schätzungen der Nua Internet Surveys gab es im Juni 1999 weltweit etwa 179 Millionen Online Nutzer (Erwachsene und Kinder). Ein Grund für diese weltweite Popularität ² liegt sicherlich in der Möglichkeit, über das Internet elektronische Nachrichten (emails) zu verschicken. Der Hauptgrund dürfte allerdings darin liegen, daß seit der Einführung des World Wide Web (WWW) Anfang der 90er Jahre, dank dessen einfach zu bedienender grafischen Benutzeroberfläche, auch Computerneulinge die Möglichkeit haben, sowohl Informationen der

unterschiedlichsten Art zu suchen und zu finden als auch verschiedenartigste Dienste in Anspruch zu nehmen [VET99] und [MUS99]. Die Informationssuche im WWW erfolgt über die dort vorhandenen Hypertextdokumente ³ (HTML-Dokumenten), die über sog. Links (Querverweise) mit anderen HTML-Dokumenten verbunden sein können. Genau diese Verlinkung verschiedener HTML-Dokumente, teilweise über den gesamten Globus hinweg, und das daraus entstandene und sich ständig weiter vermehrende Wissenspotential macht es notwendig, dem Anwender des Internets Systeme an die Hand zu geben, die ihn bei seiner Informationssuche sinnvoll unterstützen, bevor er droht in einer unkontrollierten Informationsflut unterzugehen.

¹ Advanced Research Project Agency NET

² Quelle: www.nua.ie, Stand Aug. 1999

³ Dokumente werden im WWW mit Hilfe der Hypertext Mark-up Language (HTML) realisiert

2 Einleitung

Das gezielte Suchen von Informationen ist kein neues Phänomen, sondern spätestens seit der Literatursuche in großen Literaturdatenbanken bekannt. Die anfänglich als Text oder auch Dokumenten Retrieval entwickelten Methoden zur Unterstützung der Suche nach bestimmten Informationen in großen Datenmengen haben sich seit dieser Zeit in verschiedene Richtungen weiterentwickelt. Eine Richtung ist der unter den Schlagwörtern Data mining ⁴ und Data Warehouse ⁵ bekannte Bereich, der sich mit der Sammlung, Verwaltung und Wiederaufbereitung von auf meist unterschiedlichen Datenbasen verteilten Daten beschäftigt. Eine weitere Richtung ist der unter dem Schlagwort Information Retrieval 6 (IR) zusammengefaßte Bereich verschiedener Verfahren, die sich mit der Problematik beschäftigen, textbasierte Informationen durch nicht exakt spezifizierte Anfragen auf unvollständiges Wissen zu erhalten. Basierend auf diesen IR-Verfahren wurden Suchmaschinen (search engines) wie z.B. AltaVista, Lycos, Yahoo, Excite und Infoseek entwickelt, die den Anwender bei seiner Suche nach Informationen im WWW unterstützen. Dabei durchsuchen sie unter Zuhilfenahme verschiedener Techniken das Internet nach, vom Benutzer definierten, Schlüsselworten und geben dem Benutzer nach relativ kurzer Zeit als Antwort auf die, durch die Schlüsselworte gestellte Suchanfrage eine Liste von Links, die auf HTML-Seiten mit den gesuchten Informationen verweisen. Suchmaschinen bieten dem Anwender jedoch nur eine relativ einfache Unterstützung bei der Informationssuche, da sie nicht in der Lage sind adaptiv zu arbeiten und sich daher nicht an die Bedürfnisse eines bestimmten Benutzers anpassen können. Hinzu kommt, daß bei der Informationssuche mit Suchmaschinen die im Internet häufig angewandte Aktivität des browsens 7 (oder auch surfens), bei der der Anwender wahllos oder gezielt nach Informationen sucht, indem er sich von einem Link zum nächsten hangelt, unbeachtet bleibt. Diese zusätzlichen Anforderungen erfüllen Software-Agenten, die in der Lage sind für einen Anwender aktiv und autonom nach der gewünschten Information zu suchen. Alternativ dazu existieren Verfahren, die eine vorhandene Datenmenge grafisch anordnen. Dazu zählt zum einen das WEBSOM-Verfahren, das, basierend auf selbstorganisierenden Merkmalskarten, als ein IR-Verfahren mit integriertem Browsing-Werkzeug angesehen werden kann. Es bietet, durch die Abbildung aller vorhandenen Dokumente auf eine 2-dimensionale "Landkarte", auf der ähnliche Dokumente nahe beieinander angeordnet sind, vor allem Benutzern, die das zu durchsuchende Informationsgebiet nicht eindeutig mit einer Frage eingrenzen können, die Möglichkeit Informationen zu erlangen. Ein anderes Modell zur Visualisierung von sich ähnelnden Daten ist die multidimensionale Skalierung, die es ermöglicht, die Ähnlichkeit zwischen hochdimensionalen Daten auf einen niederdimensionalen Raum abzubilden.

1.2 Zielsetzung

Diese Arbeit beschäftigt sich mit der adaptiven Informationssuche im Internet. Ziel ist die Implementierung eines Verfahrens, das die für einen Benutzer, bei der

⁴ Data Mining = Wissensextraktion aus Datenbeständen, wörtl. Daten-Bergbau

⁵ Data Warehouse = System zur Speicherung von großen Datenmengen

⁶ Information Retrieval = Informationswiedergewinnung

⁷ to browse = schmökern, blättern

Einleitung 3

Informationssuche im WWW, auftretenden Probleme minimiert. Ausgehend von einer Informationssuche mittels einer Suchmaschine sind dies folgende Probleme:

• die genaue Spezifizierung der Frage

Wird die Frage vom Benutzer schlecht spezifiziert, d.h. ungenau gestellt, erhält er entweder zu viele, und damit auch unrelevante, oder zu wenige Dokumente

• die ungeordnete Informationsflut

das gesuchte Dokument wird im ungünstigsten Fall erst zum Schluß angezeigt/gefunden

• die enorme Verlinkung der Dokumente in sich und untereinander der Benutzer verliert leicht die Übersicht und damit unter Umständen das eigentliche Suchziel aus den Augen

• das Erkennen von doppelten Dokumenten

ein und dasselbe Dokument wird möglicherweise unter verschiedenen Titeln mehrfach in der Antwortmenge aufgeführt.

Um einen Benutzer sinnvoll bei der Informationssuche unterstützen zu können sollte das zu implementierende Verfahren daher in der Lage sein:

• den Inhalts eines Dokumentes und

• ähnliche Dokumente als solche zu erkennen sowie

• die Dokumente übersichtlich zu präsentieren.

1.3 Gliederung

In Kapitel 2 wird zunächst ein Überblick über verschiedene Verfahren, die zur Informationssuche in großen Datenbeständen genutzt werden können, gegeben. Es handelt sich dabei um einige ausgewählte Verfahren aus den Forschungsbereichen des maschinellen Lernens (ML), der künstlichen Intelligenz (KI), der künstlichen neuronalen Netze, des Information Retrieval (IR) und der multivariaten Analysemethoden. Da bei der Informationssuche im WWW insbesondere der textuelle Teil einer HTML-Seite von Bedeutung ist, bilden die IR-Verfahren in diesem Kapitel den Schwerpunkt.

Das 3. Kapitel enthält einen groben Entwurf des zu implementierenden Modells und gibt einen Überblick über die als Testumgebung ausgewählten Daten sowie die für die Implementierung zu leistende Vorarbeit und die dabei auftretenden Probleme.

In Kapitel 4 erfolgt die detaillierte Beschreibung des implementierten Modells anhand der einzelnen Entwicklungsphasen, sowie eine Präsentation der erhaltenen Ergebnisse.

Kapitel 5 gibt einen Überblick über Implementierungsdetails anhand der jeweils zur Implementierung des Modells verwendeten Software. Eine detaillierte Erklärung sowie eine Dokumentation der implementierten Programme erfolgt im Anhang und auf der, dieser Arbeit beigefügten, CD-ROM ⁸ .

⁸ vgl. Verzeichnis \Dokumentation

4 Einleitung

Abschließend erfolgt in Kapitel 6 eine Bewertung der in dieser Arbeit erlangten

Ergebnisse sowie ein Ausblick über eine mögliche Weiterentwicklung des hier

vorgestellten Modells.

2 Grundlagen

Die heutzutage bestehende Informationsflut, der ein Mensch bei der Suche nach gezielten Informationen gegenübersteht, ist das Ergebnis einer jahrhundertlangen Entwicklung. Verdoppelte sich die Zahl der Informationen über mehrere Jahrhunderte hinweg noch etwa alle 15 Jahre [RID44], ging man schon 1982 von einer Verdopplung alle 5 Jahre, 1988 alle 2,2 Jahre und 1992 sogar von einer Verdopplung alle 1,6 Jahre [DW95] aus. Dieser explosionsartige Anstieg an Information läßt sich u.a. auf den stark gestiegenen Einsatz des Internet und die in ihm enthaltene Anzahl an Publikationen zurückführen. So rechneten die MIT Labs ⁹ 1996 sogar mit einer Verdopplung der

Informationen im WWW alle 50 Tage. Bei diesem immensen Anstieg an Publikationen ist das Auffinden von Informationen ohne technische Hilfsmittel kaum noch zu bewältigen. Zur Unterstützung des Anwenders bei seiner Suche im WWW existieren eine Vielzahl der unterschiedlichsten Lösungsmodelle aus den Forschungsbereichen des maschinellen Lernens (ML), der künstlichen Intelligenz (KI), der Computerlinguistik und des Information Retrieval (IR) sowie aus dem, seit einigen Jahren bestehenden, Bereich des Intelligenten Information Retrieval (IIR), der vereinfacht als eine Überlappung der Forschungsgebiete der KI und des IR angesehen werden kann [CRF87].

Das nachfolgende Kapitel gibt einen Überblick über einige Methoden, die der Unterstützung bei der Suche nach bestimmten Informationen in großen Datenmengen dienen, wobei das Gebiet des IIR unbeachtet bleibt.

2.1 Data mining, Data Warehouse

Data Mining (DM), auch bekannt als Knowledge Discovery in Databases (KDD), steht für eine Vielzahl von Verfahren aus dem Bereich der statistischen Modelle, des maschinellen Lernens (ML) sowie der künstlichen Intelligenz, die dem Auffinden und der Extraktion von relevanten Informationen aus Datenbanken dienen. Die Besonderheit bei der Informationssuche mit DM-Verfahren ist, daß, anders als bei den im Abschnitt 2.2 beschriebenen Information Retrieval-Verfahren, der Anwender meist im Vorfeld noch nicht weiß, wonach er sucht. Vielmehr erhält der Anwender vom DM-Verfahren Daten in für ihn verständlich aufbereiteter Form, die das Verfahren auf der Suche nach Abhängigkeiten und Regelmäßigkeiten zwischen den einzelnen Datenbankeinträgen findet. Aus den so gewonnenen Informationen ist es dem Anwender dann möglich, Prognosen für die Zukunft abzuleiten [BBM97]. Wie schon die Bezeichnung Data Mining (wörtl. Daten-Bergbau) erahnen läßt, "durchgräbt" ein DM-Verfahren den vorhandenen "Datenberg", erkennt und analysiert selbständig relevante Daten (Informationen) und ist dadurch in der Lage, Erkenntnisse und Zusammenhänge zu liefern, die bisher unbekannt waren [MM99]. DM-Verfahren automatisieren somit den Vorgang des Auffindens von sogenannter vorhersagbarer Information, Information, die sich durch das Auswerten vergangener Abläufe und Daten konstruieren (vorhersagen) läßt und ergänzen und beschleunigen dadurch die schon vorhandenen statistischen

⁹ Massachusetts Institute of Technology Labaratories

6 Grundlagen

Verfahren um neue Analysemethoden. Als Beispiel sei das Treffen von Vorhersagen über das Kaufverhalten von Kunden in einem Supermarkt durch Auswertung der Daten über die von den Kunden gekauften Waren und/oder die Kunden selber genannt [BOL96]. Das Treffen solcher Vorhersagen wird durch den Entwurf von Modellen möglich. Ein Modell bildet den Zustand einer Situation, für die alle Antworten bekannt sind, auf eine vordefinierte Art und Weise ab und läßt sich dann auf andere Situationen, für die Antworten gesucht werden, übertragen. In dem speziellen Fall des Supermarktes könnte als Modell die Erstellung einer Liste typischer Einkaufswaren von Kunden der Käse- und der Backabteilung dienen, um so mögliche Verbindungen zwischen den in diesen Abteilungen verkauften Waren erkennen zu können und später u.a. für Werbezwecke gezielter nutzen zu können.

Ziel des Data mining ist es also, durch Untersuchung der vorhandenen Daten auf Abhängig- und Regelmäßigkeiten (sog. Muster) untereinander noch unbekannte Zusammenhänge zu entdecken und die so gewonnenen neuen Informationen aus den Gesamtdaten zu extrahieren. Da die Suche nach Mustern in der Regel auf sehr großen Datenmengen erfolgt, entwickelte sich die Forderung nach einer Organisation der Daten, die eine individuelle Aufbereitung der Information erlaubt, dem Data Warehouse 10 (DW). Obwohl ein Data Warehouse für den Prozeß des DM nicht

zwingend erforderlich ist, da dieser auch direkt auf großen relationalen Datenbeständen laufen könnte, ist die Architektur eines DW dabei sehr hilfreich [MM99a]. Vergleichbar mit einem riesigen Zentrallager für Daten, hauptsächlich bestehend aus einer zentralen Datenbank, verwaltet es sämtliche Daten, indem es mit Hilfe vorhandener Softwareprogramme regelmäßig Informationen sammelt, konsolidiert, filtert und katalogisiert, so daß mit entsprechenden DM Methoden die gewünschten Informationen aus den gesammelten Daten gewonnen werden können [BBM97].

Der nachfolgende Abschnitt dient als Überblick über die, vom Österreichischen Forschungsinstitut für Artificial Intelligence (ÖFAI) genannten, am häufigsten auftretende Arten von Mustern und die zur Suche dieser Muster benutzten Methoden [PET97].

2.1.1 Regeln

Regeln dienen der Beschreibung von Zusammenhängen zwischen den verschiedenen Attributen eines Objektes. Zur Beschreibung dieser Zusammenhänge existieren unterschiedliche Regeln, die nachfolgend im einzelnen kurz erläutert werden.

2.1.1.1 Klassifikationsregeln

Das Lernen von Klassifikationsregeln entstammt dem Forschungsbereich des ML, der sich damit befaßt, Klassifizierungsverfahren zu entwickeln, die anhand von Erfahrungen lernen. Aufgrund des erlernten Wissens erzeugen sie dann selbständig Regeln, die ein möglichst fehlerfreies Einordnen von neuen, unbekannten Objekten in eine zugehörige Klasse ermöglichen, wobei der Vorgang des Lernens in der Regel anhand von

¹⁰ wörtl. Datenwarenhaus

Grundlagen 7

vorklassifizierten Trainingsbeispielen erfolgt. Ein Beispiel für eine gelernte Regelmenge ist folgende, aus einer Datenbank von Kreditbeschreibungen einer Bank zur Abschätzung der Kreditwürdigkeit eines Kunden gelernte, hypothetische Regelmenge:

Aus obiger Regel geht somit hervor, daß jemand, der ein Haus besitzt und Angestellter ist, wenn er einen Kredit vom Typ A mit einem Betrag kleiner als 500.000 und einer Laufzeit von mindestens 6 Jahren beantragt, in die Klasse mit hoher Kreditwürdigkeit einzuordnen ist. Die Klassifikationsregel hilft also die fehlende Information über die Kreditwürdigkeit eines Kunden aus schon vorhandenen Daten herzuleiten. Die gesuchten Regeln sollten so einfach wie möglich sein und dennoch für alle vorhandenen Klassen Bedingungen formulieren sowie einen möglichst großen Teil der vorhandenen Daten abdecken. Zum Erlernen der Klassifikationsregeln existieren zahllose, unterschiedliche Algorithmen, von denen hier nur zwei kurz aufgeführt werden.

Entscheidungsbäume (decision trees)

Mit Hilfe von Entscheidungsbäumen lassen sich Entscheidungsprobleme graphisch darstellen und bearbeiten. Die Auswertung eines Entscheidungsbaumes beginnt bei der Wurzel: Jeder Knoten des Baumes, mit Ausnahme der Blätter, enthält seinerseits ein Entscheidungsproblem, das Teil des Gesamtproblems ist; die Blätter enthalten die Ergebnisse der jeweiligen Entscheidungsfolgen. In dem speziellen Fall, der automatischen Erstellung und Optimierung von Entscheidungsbäumen anhand von Beispielen, wird die Menge der Beispiele solange durch jeweils ein Attribut pro Knoten aufgeteilt (klassifiziert), bis sich in einer Teilmenge nur Beispiele einer Klasse befinden [HUS94]. Die bekanntesten Algorithmen dieser Art sind ID3 und C4.5 von Quinlan [QUI94].

Regellernen mittels Abdeckung (Covering)

Bei dieser Art des Erlernens von Regeln wird zuerst nach einer Regel gesucht, die möglichst viele Beispiele einer Klasse abdeckt. Ist eine solche Regel gefunden, werden alle, durch die Regel abgedeckten Beispiele aus der Klasse entfernt und für die übrig gebliebenen Beispiele wird eine neue Regel gesucht/gelernt. Dieser Vorgang wird solange wiederholt, bis alle Beispiele durch Regeln abgedeckt sind. Typische Vertreter dieser Art von Algorithmen sind AQ von Michalski [MCM83] und CN2 von Clark & Niblett [CN89].

2.1.1.2 Charakteristische Regeln

Diese Arten von Regeln beschreiben Eigenschaften, die alle zu einer Klasse gehörenden Beispiele gemeinsam haben. Sie sagen jedoch nichts darüber aus, wieviele andere

8 Grundlagen

Beispiele diese Regeln auch erfüllen. Für das Beispiel der Kreditwürdigkeit könnte eine charakteristische Regel wie folgt aussehen:

Diese Regel besagt, daß Personen mit hoher Kreditwürdigkeit in der Regel einen Kredit des Typs A oder B beantragen und Angestellte sind. Mit Hilfe von charakteristischen Regeln lassen sich "typische" Merkmale von Daten einer bestimmen Klasse beschreiben. Eine häufig angewandte Methode zum Finden charakteristischer Regeln ist die Methode der attribut-orientierten Induktion.

Attribut-orientierte Induktion

Bei diesem Verfahren entstehen Regeln durch das Verschmelzen von identischen Datensätzen, die durch das Generalisieren von Attributwerten entstanden sind. Als Generalisierungsoptionen können z.B. das Weglassen einer Bedingung in einer Konjunktion, das Hinzufügen einer Alternative in einer Disjunktion oder das Umwandeln einer Konjunktion in eine Disjunktion angewandt werden [FEB99]. Die Generalisierung erfolgt auf Basis von Hintergrundwissen, welches in diesem speziellen Fall Abstraktionshierarchien sind. Als praktisches Beispiel dieser Vorgehensweise sei hier das Programm DBMiner von Han, Fu, Wang, Chiang, Gong, Koperski, Li, Lu, Rajan, Stefanovic, Xia und Zaiane genannt [HFW+96].

2.1.1.3 Regressionsregeln

Im Unterschied zu den Klassifikationsregeln, bei dem ein neues Objekt auf die Zugehörigkeit zu den schon vorhandenen Klassen überprüft wird, wird bei den Regressionsregeln ein numerischer Wert für das neue Objekt vorhergesagt. Dieses Verfahren wird immer dann eingesetzt, wenn der Wert eines numerischen Attributs aus anderen Attributen hergeleitet wird. Dies ist z.B. bei der Vorhersage von Aktienkursen oder bei medizinischen Problemen, bei denen Vorhersagen anhand von Diagnosedaten getroffen werden müssen, der Fall.

2.1.1.4 Assoziationsregeln

Assoziationsregeln dienen dazu, Beziehungen zwischen gemeinsam auftretenden Objekten aufzudecken. Eine Assoziationsregel ist ein Ausdruck der Art W => B, mit W als einer Menge von Attributen und B einem einzigen Attribut. Die Interpretation einer solchen Regel ist, daß für die Daten, für die W zutrifft, auch das Attribut B zuzutreffen scheint [MTV94], [KMP+94] und [AIS93]. Eine typische Anwendung von Assoziationsregeln ist die Warenkorbanalyse, die dazu dient, zwischen den vom Kunden gekauften Waren Beziehungen festzustellen. Eine beispielhafte Assoziationsregel für eine Warenkorbanalyse wäre dann:

Grundlagen 9

Die Interpretation obiger Regel lautet: "In 45% Prozent der Fälle, in denen Lachs und Weißwein gekauft wurden, wurde auch Weißbrot gekauft; die Kombination dieser Transaktion kam in 3% aller Transaktionen vor" [BOL96].

2.1.2 Cluster

Anders als beim Lernen von Klassifikationsregeln ist beim Lernen von Clustern ¹¹ die Einteilung der Objekte nicht schon im Vorfeld gegeben, sondern muß erst selbständig ermittelt werden. Dieser Vorgang, eine große Menge von Objekten, basierend auf einem "divide and conquer ¹² " Verfahren in kleinere Gruppen mit sich ähnelnden Objekten zu unterteilen, ist in der Literatur als Clustering bekannt und dient der Vereinfachung der späteren Auswertung. Für den Vorgang des Clusterns existieren eine Vielzahl von unterschiedlichen Verfahren, was u.a. daran liegt, daß Clustering nicht nur allein im DM, sondern beispielsweise auch in der Statistik, im ML und im IR zum Einsatz kommt. Die klassischen statistischen Verfahren verwenden distanzbasierte Methoden, während neuere Algorithmen aus den Bereichen des ML und des IR wahrscheinlichkeitsbasierte, informationstheoretische oder Bayes'sche Methoden verwenden, auf die im Abschnitt 2.2.1.5 noch näher eingegangen wird. Für die Cluster-Methoden im DM ist zusätzlich zum Finden der Gruppen eine verständliche Beschreibung der Gruppen, etwa in Form von Klassifikationsregeln, von Interesse [CHY96].

2.2 Information Retrieval

Bei den Information Retrieval (IR) Verfahren handelt es sich um Verfahren, die es ermöglichen, aus einem Pool von vorhandenen Daten durch Formulierung einer Frage gleichzeitig soviel passende und so wenig unpassende Daten wie möglich als Antwort auf die gestellte Frage zu erhalten. Anzumerken ist hierbei, daß es sich bei diesen Daten um Dokumente handelt, da sich IR mit der Repräsentation und Speicherung von Dokumenten und dem Zugriff auf diese Dokumente befaßt [SMG87]. Auf den ersten Blick scheinen IR-Verfahren somit keine wesentliche Verbesserung zu den schon seit einiger Zeit bekannten und bei der Literatursuche in großen Literaturdatenbanken genutzten Daten Retrieval (DR)-Verfahren zu sein. Bei näherer Betrachtung beider Verfahren erkennt man jedoch, daß sich die Funktionalität im Bereich der Informationssuche bei den IR-Verfahren im Gegensatz zu den DR-Verfahren erheblich verbessert hat. Zur Verdeutlichung der bestehenden Unterschiede und für eine genauere Definition des Begriffes Information Retrieval wird nachfolgend, in Anlehnung an die von van Rijsberg in [RIJS79] vorgestellte Tabelle, eine Unterscheidung von DR und IR anhand einiger besonderer Merkmale getroffen. Basis für den Vergleich der beiden Methoden ist eine Menge von Textdokumenten, aus der jeweils die Dokumente in einer Antwortliste aufgeführt werden sollen, die Informationen zu der gestellten Frage enthalten.

¹¹ wörtl. Gruppen, Haufen

¹² wörtl. teile und herrsche

10 Grundlagen

Tabelle 1: Daten Retrieval versus Information Retrieval

Ausschlaggebend für die Art der Antworten, die der Anwender auf eine gestellte Frage erhält, ist der in der Tabelle verwandte Begriff Matching ¹³ . Bei dem, im DR

angewandten, exakten Zeichenkettenabglcich (exakten Matching) genügt schon eine kleine Abweichung des Suchbegriffs von den im Dokument vorhandenen Worten, um für die Antwort ein negatives Ergebnis zu bekommen, das Dokument also nicht mit in die Antwortliste aufzunehmen. Daher eignet sich diese Methode gut, um ein Dokument auf das Vorhandensein eines bestimmten Wortes zu überprüfen. Um allerdings Antworten auf die eher unexakt gestellten Fragen beim IR zu erhalten, ist es nötig das "exakte Matching" auf einen partiellen Zeichenkettenabgleich (partielles Matching bzw. "best match") abzuschwächen. Die als Antwort in Frage kommenden Dokumente werden dann, absteigend sortiert vom passendsten bis zum unpassendsten, in der Antwortliste aufgeführt und abhängig von ihrem Standort in der Liste ziemlich oder eher gar nicht auf die Fragegestellung zutreffen.

Die Art der Inferenz gibt Aufschluß darüber, wie die beiden Verfahren schon gefundene Dokumente nutzen, um aufgrund der zwischen ihnen bestehenden Beziehungen weitere, als Antwort ebenfalls zutreffende, zu finden. Die beim DR verwendete ist "deduktiver" Art, d.h. wenn gilt: Dokument a steht in Relation zu Dokument b (aRb) und Dokument b steht in Relation zu Dokument c (bRc), dann muß auch Dokument a in Relation zu Dokument c stehen (aRc) und deshalb in die Antwortliste mit aufgenommen werden. DR läßt sich somit als ein deterministisches Verfahren ansehen. Im Gegensatz zum eher probabilistischen IR, bei dem Relationen nur mit einem gewissen Grad von Sicherheit bzw. Unsicherheit angegeben werden können, die Art der Inferenz somit "induktiv" ist. Dies hat zur Folge, daß Schlußfolgerungen in Bezug auf die Relevanz von einem Dokument auf ein anderes mit Hilfe von Wahrscheinlichkeiten, häufig unter Zuhilfenahme des Bayes Theorem, getroffen werden.

Der Begriff der Fragesprache befaßt sich mit den unterschiedlichen Formulierungsmöglichkeiten einer Frage. Beim DR erfolgt die Fragestellung mittels einer "künstlichen" Sprache, d.h. die zu stellende Frage muß basierend auf einem vorgegebenen, eingeschränkten Vokabular und einer beschränkten Syntax formuliert werden. Beim IR hingegen basiert die Fragestellung auf einer "natürlichen" Fragesprache, so daß, bis auf einige Ausnahmen, eine Fragestellung ohne Einschränkung möglich ist.

Der Begriff der Fragespezifikation trifft eine Aussage über den Umfang einer gestellten Frage. Im DR ist normalerweise eine "vollständige" Spezifikation der gesuchten Information in der gestellten Frage gegeben, wohingegen beim IR meist nur

¹³ matching = wörtl. passend

Grundlagen 11

"unvollständig" spezifizierte Fragen für die gesuchten Informationen gestellt werden. Dieser Unterschied in der Fragespezifikation beruht auf der Qualität der Antworten. Die gewünschten Objekte im DR sind "passende", also solche, die exakt den in der Frage gestellten Termen entsprechen. Beim IR ist man dagegen daran interessiert, als Antwort auf eine gestellte Frage anstelle weniger, exakt passender Objekte, möglichst viele "relevante" Objekte zu finden.

Die durch obigen Vergleich der beiden Retrieval Methoden gewonnene Definition des IR läßt sich noch um eine, von der Fachgruppe "Information Retrieval" ¹⁴ gegebene, aktuellere Definition erweitern. Diese Fachgruppe definiert IR als ein Gebiet, das sich mit Fragestellungen beschäftigt, die im Zusammenhang mit ungenauen Fragen und unsicherem Wissen (z.B. Texte, multimediale Dokumente, Fakten, etc.) entstehen. Wobei ungenau gestellte Fragen sich u.a. dadurch auszeichnen, daß sie teilweise nur im Dialog iterativ durch Reformulierung beantwortet werden können und für ihre Beantwortung eventuell mehrere Datenbasen durchsucht werden müssen. Die Unsicherheit oder auch Unvollständigkeit des Wissens resultiert häufig aus der eingeschränkten Repräsentation von z.B. Dokumenten und der sich daraus ergebenden fehlenden Semantik.

Bevor nachfolgend eine nähere Betrachtung der Standardverfahren des IR und ihrer unterschiedlichen Methoden erfolgen kann, ist es notwendig, sich die fundamental bei IR-Systemen auftretenden Probleme zu vergegenwärtigen. Diese sind:

• Festplattenplatzprobleme durch das Abspeichern der gefundenen Dokumente

• Zugriffszeiten auf bestimmte Dokumente

• Bestimmung des Inhalts eines Dokumentes

• Unterscheidung in passende und unpassende Dokumente

• Repräsentation eines vorhandenen Dokumentes

Die Problematik des Festplattenplatzes und der Zugriffszeit auf ein Dokument wird heutzutage durch die immer besser werdende Technologie von der hardwaretechnischen Seite so stark minimiert, daß eine nähere Betrachtung entfällt. Bleibt das Problem, Aussagen über den Inhalt eines Dokumentes treffen zu können ohne das Dokument komplett zu lesen, um so eine Unterscheidung in, für eine gestellte Anfrage, passende und unpassende Dokumente vornehmen zu können. Dies führt unmittelbar zum Problem der Repräsentation des vorhandenen Dokumentes im System. Ein Computer ist momentan noch nicht in der Lage, den in einem Dokument vorhandenen Text sowohl syntaktisch als auch semantisch zu verstehen. Es ist daher notwendig, die im Dokument vorhandenen Informationen so zu extrahieren und zu repräsentieren, daß mit Hilfe eines geeigneten IR-Verfahrens eine maschinelle Auswertung über die Relevanz des Dokumentes erfolgen kann. Abhängig von der Wahl des IR-Verfahrens werden relevante Dokumente ungeordnet oder aber nach Relevanz geordnet in eine Antwortmenge aufgenommen. Im letzteren, weitaus häufigeren, Fall wird anhand eines sog. Retrieval Status Wert (RSW) als Antwort eine, nach Relevanz geordnete, Liste der relevanten Dokumente erstellt. Dieses, in der Literatur als Ranking bezeichnete

¹⁴ diese Fachgruppe wurde 1991 innerhalb der „Gesellschaft für Informatik“ gegründet

12 Grundlagen

Verfahren, läßt sich durch Feedback des Benutzers, wie z.B. Bestätigung oder Verwurf der vorgeschlagenen Dokumente, optimieren, um so mit der Zeit möglichst genaue Antworten auf die gesuchten Informationen geben zu können.

2.2.1 Standardverfahren

Zum besseren Verständnis der in nachfolgender Tabelle aufgeführten und im weiteren Verlauf näher betrachteten IR-Standardverfahren verdeutlicht nachfolgende Abbildung noch einmal die schon vorab erläuterten Grundfunktion eines IR-Systems [SAL89] und [SMG87].

Die als IR-Standardverfahren betrachteten Verfahren, die alle auf einem Vergleich zwischen der gestellten Frage und den vorhandenen Dokumenten basieren ¹⁵ , sind in

nachfolgender, in Anlehnung an die von Fuhr in [FUH96] erstellte Tabelle, aufgeführt:

Tabelle 2: Standardverfahren des IR

Die einzelnen Verfahren unterscheiden sich in der ihnen zugrundeliegenden theoretischen Basis, die im einzelnen in den nachfolgenden Abschnitten erläutert wird, der Beschreibung der einzelnen Dokumente und der gewählten Fragestruktur.

Die Beschreibung der Dokumente durch gewichtete oder ungewichtete Indexierung entspricht einer vereinfachten Darstellung der jeweiligen Dokumente, die eine bessere maschinelle Bearbeitung ermöglicht. Beim Indexieren werden die Dokumente, durch manuelle oder automatische Auswahl geeigneter Deskriptoren, auf ihren wesentlichen Inhalt reduziert, wobei darauf geachtet werden sollte, daß die ausgewählten Deskriptoren folgende Funktionen erfüllen:

¹⁵ bei der Clusteranalyse erfolgt dieser Vergleich nur indirekt

Grundlagen 13

• Dokumentensuche

Für eine vom Anwender gestellte Frage werden die relevanten Dokumente gesucht und, falls vorhanden, gefunden.

• Dokumentenverknüpfung

Thematisch zusammengehörige Dokumente werden miteinander in Verbindung gesetzt.

• Dokument-Relevanzbestimmung

Ermittlung der Relevanz für die einzelnen Dokumente in Bezug auf die gestellte Frage.

Für die Indexierung wird, abhängig von vorher festzulegenden Regeln, das Dokument in einzelne Worte, die sog. Indexterme zerlegt und dann als indiziertes Dokument neu abgespeichert. Ein typisches Regelwerk für eine solche Dokumentenvereinfachung könnte dann wie folgt aussehen:

^• Entfernen sämtlicher Interpunktionszeichen aus einem Text

^• Entfernen sogenannter Stoppwörter. Dies sind Wörter, die i.a. keinen Beitrag für das Verständnis des Textes leisten, wie z.B. Präpositionen, Artikel, etc.

^• Reduzierung von Wörtern auf ihren Wortstamm

^• Entfernen aller Duplikate eines Wortes

^{• Verwendung von Thesauri, d.h. eine Zusammenstellung der im Dokument vorhandenen Wörtern, geordnet nach ihrer Bedeutung als Oberbegriffe, Spezialisierungen oder verwandte Begriffe} Beispiel 4: Regeln zur Dokumentenvereinfachung

Da nach Luhn [LUH58] die Vorkommenshäufigkeit eines Wortes in einem Dokument ein nützliches Maß für die Signifikanz dieses Wortes im Dokument liefert, lassen sich die Nachteile, die bei einer solchen Verkürzung des Originaldokumentes entstehen, durch unterschiedliche Gewichtung der einzelnen Indexterme, abhängig von ihrer Relevanz im untersuchten Dokument, minimieren. Für eine detaillierte Vorgehensweise bei der Gewichtung von Indextermen vgl. Abschnitt 2.2.1.3. Genauso wie die Dokumente, müssen auch die gestellten Fragen in eine maschinell verständliche Struktur gebracht werden. Dazu wird, abhängig vom benutzten Verfahren, als Fragestruktur eine Beschreibung der Frage mit booleschen Ausdrücken oder als linearer Vektor gewählt.

2.2.1.1 Boolesches Retrieval

Das boolesche Retrievalverfahren ist historisch gesehen das älteste der Informationssuchverfahren. Es basiert auf einem logischen Vergleich zwischen der gestellten Frage und den vorhandenen Dokumenten und liefert als Antwort genau die Dokumente, die den Wahrheitswert "wahr" als Antwort auf die gestellte Frage liefern. Um diesen logischen Vergleich durchführen zu können, müssen nicht nur die Dokumente in Form von Indextermen vorliegen, auch die Fragen müssen mit Hilfe von Indextermen formuliert werden. Die Formulierung einer Frage erfolgt durch Verknüpfungen von Indextermen mit den logischen Operatoren UND, ODER und NICHT. Da bei diesem Verfahren eine direkte Überprüfung auf das Vorhandensein eines bestimmten Indexterms erfolgt, reicht zur Darstellung des Dokumentes eine ungewichtete Indexierung aus.

14  Grundlagen  

  Die Implementierung eines booleschen Retrievalsystems erfolgt über invertierte Listen  

  Eine invertierte Liste enthält für jeden Indexterm eine Referenz auf die, diesen  

Indexterm  enthaltende, Dokumente. Daß pro Indexterm eine eigene invertierte Liste  

  existiert, ist zugleich Vorteil als auch Nachteil dieses Retrievalverfahrens. Der Vorteil  

  liegt in der Mächtigkeit des Verfahrens, da es möglich ist, mit einer gestellten Frage  

  jede beliebige Teilmenge von Dokumenten zu erlangen (vgl. FUH96 ) Andererseits ist  

  das Verfahren dadurch sehr speicherintensiv, insbesondere dann, wenn die Dokumente  

  einen gewissen Umfang erreichen und somit viele Indexterme vorhanden sind  

  Nachfolgend ist ein einfaches Beispiel skizziert, das die Vorgehensweise bei einer  

  boolesche Suche skizziert:  

  T i : Liste des jeweiligen Indexterms  

  D i : die, den Indexterm enthaltenden Dokumente  

  Frage (T 1 UND T 2 ) ODER (T 3 UND (NICHT T 4 ))  

  T 1 Liste: D 1 , D 2 , D 3 , D  4

  T 2 Liste: D 1 , D  2

  T 3 Liste: D 1 , D 2 , D  3

  T 4 Liste: D  1

  Antwort: (T 1 UND T 2 ) D 1 , D 2 , D 3 , D 4 UND D 1 , D  2

  D 1 , D  2

  (NICHT T 4 ) D 2 , D 3 , D  4

  (T 3 UND (NICHT T 4 )) D 1 , D 2 , D 3 UND D 2 , D 3 , D  4

  D 2 , D  3

  (T 1 UND T 2 ) ODER (T 3 UND (NICHT T 4 )) D1 , D2 ODER  

  D2 , D3  

  D1 , D2 , D3  

  Beispiel 5 : Boolesche Suche nach van Rijsberg in RIJS79 :  

  Obiges Beispiel liefert auf die gestellte Frage eine Ergebnismenge, die diejenigen  

  Dokumente enthält, die bei der Überprüfung auf das Vorhandensein der gesuchten  

Indexterme  den Wahrheitswert wahr zurückgegeben haben  

  Eine Einordnung in geeignete oder weniger geeignete Dokumente, bzw. ein Ranking  

  der Antwortdokumente bezüglich ihrer Relevanz auf die gestellte Frage, entfällt. Dieser  

  Umstand und die komplizierte Eingabe der zu stellenden Frage machen das boolesche  

  Retrieval für das IR äußerst ungeeignet. Hinzu kommt der Umstand, daß die vom  

  Anwender gesuchte Information ziemlich genau in eine formale Frage umgesetzt  

  werden muß, da die Fragestellung vom Booleschen System exakt ausgewertet wird  

  (exaktes Matching) Das hat u a. zur Folge, daß eine zu spezielle Frageformulierung als  

  Antwortmenge die leere Menge liefern wird. Ähnliche oder teilweise zutreffende  

  Dokumente bleiben unberücksichtigt und es bleibt dem Anwender selbst überlassen,  

  anhand einer erneut zu formulierenden Frage, eine weniger spezielle Suche zu starten  

  Für den Fall, daß das Boolesches Retrieval trotzdem in IR-Systemen benutzt wird, wird  

  es meist so modifiziert, daß nur UND-Verknüpfungen erlaubt sind. Als Ausgleich für  

  diese Einschränkung wird die tatsächliche Anzahl der Terme, die ein Dokument mit der  

  gestellten Frage gemeinsam hat, beachtet. Der für diese Vorgehensweise gängige  

  Ausdruck heißt Simple Matching 16 , da für jedes Dokument D die Übereinstimmung der  

16  simple matching einfache Übereinstimmung  

Grundlagen 15

zugehörigen Indexterme mit der gestellten Frage F nach dem simple matching

Koeffizient |D ∩ F| berechnet wird.

Matching Funktionen

Außer dem soeben erwähnten simple matching Koeffizienten existieren noch weitere, bei Suchverfahren verwendete Koeffizienten. Matching Koeffizienten messen, abhängig von ihrer zugrundeliegenden Funktion, die Verbindungen, die zwischen zwei Objekten, in diesem Fall einer Frage und einem Dokument, bestehen. Je mehr Übereinstimmungen (Verbindungen) zwischen einem Dokument und der gestellten Frage bestehen, desto größer ist das gemessene Maß. Da beim IR normalerweise die vorhandenen Dokumente durch Listen von Indextermen repräsentiert werden, gilt für die nachfolgend aufgeführten matching Koeffizienten, daß ein Objekt durch eine Menge von Indextermen repräsentiert wird und die Maßzahl |.| die Anzahl der Elemente der Menge angibt.

Nachfolgend die fünf meistgebrauchten matching Koeffizienten im IR [RIJS79]: M = |D ∩ F| Simple matching Koeffizient (1)

2|D ∩ F|

M =

M =

M =

M =

mit M: matching Funktion

2.2.1.2 Fuzzy Retrieval

Das im IR angewandte Verfahren des Fuzzy Retrieval ¹⁷ stellt eine Erweiterung des Booleschen Retrieval um gewichtete Indexierung, basierend auf der Theorie der Fuzzylogik, dar. Anders als beim Booleschen Retrieval ist nun ein Ranking der gefundenen Dokumente möglich, wobei sich die Relevanz eines Dokuments aus der Übereinstimmung von Index- und Fragetermen berechnet. Waren beim Booleschen Retrieval die Indexterme darauf beschränkt, in einem Dokument vorhanden (wahrbzw. 1) oder fehlend (falsch - bzw. 0) zu sein, können ihnen jetzt, durch Zuordnung eines Zahlenwertes aus dem reellen Intervall [0,1], unterschiedliche Gewichtungen für das Vorkommen in einem Dokument gegeben werden. Durch dieses Vorgehen erhält man für die Dokumente nicht mehr nur die exakten Retrieval Status Werte Null oder Eins, sondern auch Werte zwischen Null und Eins. Dadurch wird die Ausgabe auch solcher Dokumente ermöglicht, die keine vollständige Übereinstimmung von Index-und Fragetermen aufweisen. Es werden also die Dokumente ausgegeben, die das beste Ergebnis bezüglich der Anzahl der gefundenen Suchbegriffe erzielten, weshalb hier auch von einem Best-Matching-Verfahren gesprochen wird.

¹⁷ Fuzzy Retrieval = Wiedergewinnung aus unscharfen Mengen

16 Grundlagen

Grundlage für dieses Verfahren ist die 1965 von Lotfi A. Zadeh [ZAH65] entwickelte mathematische Theorie der unscharfen Mengen (Fuzzy Sets), die versucht, ungenaue Beschreibungen zu formalisieren und damit eine Möglichkeit bietet, umgangssprachliche Begriffe wie groß, klein, ungefähr etc. zu modellieren. Damit entspricht sie einer Verallgemeinerung des Mengenbegriffs, die Aussagen über den "Grad der Mitgliedschaft in einer Menge" trifft. Mit Hilfe einer sogenannten Zugehörigkeitsfunktion kann für ein Element ein Zahlenwert zwischen Null und Eins angegeben werden, der die Zugehörigkeit des Elements zur Menge beschreibt; die Zuordnung in zwei eindeutige Werte (wahr oder falsch) wird demnach um Werte zwischen Null und Eins erweitert, um Ausdrücke und Formeln semantisch interpretieren zu können, die weder eindeutig wahr noch eindeutig falsch sind. Die Definition der Zugehörigkeitsfunktion lautet [BG93]: m x : D ^→ [0,1] Zugehörigkeitsfunktion (6) mit D: Menge

X: ^{unscharfe Menge (Fuzzy Set) über dem Grundbereich} Der Grad der Zugehörigkeit eines Elements d ∈ D zur Menge X wird durch den Funktionswert m x (d) ^∈ [0,1] Grad der Zugehörigkeit (7)

gegeben. Fuzzymengen erlauben somit einen "weichen" Übergang von den Werten, die mit Sicherheit als wahr angesehen werden zu den Werten, die nicht zutreffend sind. Dabei nimmt der Zugehörigkeitsgrad der die Lösung repräsentierenden Fuzzymenge mit zunehmendem Abstand vom mit Sicherheit zutreffenden Wert ab. Die in Abbildung 2 abgebildeten Formen der Zugehörigkeitsfunktionen sind die üblicherweise verwandten einfachen Funktionen der Dreiecks-, Trapez- und Gaußfunktion, die sich mit wenigen Parametern festlegen lassen [KN96].

Im Fall des Fuzzy Retrieval bedeutet dies, daß über die Gewichtung der Indexterme der Grad der Zugehörigkeit eines Indexterms zu einem bestimmten Dokument, respektive die Relevanz eines Indexterms für ein bestimmtes Dokument, angezeigt wird [FUE97]. Es ergibt sich somit die Zugehörigkeitsfunktion m x : T ^→ [0,1] Zugehörigkeitsfunktion (8) mit T: Menge von Indextermen

X: Menge der unscharfen Begriffe

und der Grad der Zugehörigkeit eines Indexterms t ∈ T zur Menge X wird durch den Funktionswert

Grundlagen 17

m x (t) ^∈ [0,1] Grad der Zugehörigkeit (9)

gegeben. Die Integration der Zugehörigkeitsgradwerte in die Dokumentenbeschreibung ist im folgenden Beispiel zu sehen:

Mathematisch bedeutet dies, daß das Dokument D i durch die Summe der Deskriptoren T j , deren Zugehörigkeit durch die Zugehörigkeitsfunktion m festgelegt ist, beschrieben wird. Anhand des Gewichtungswerts läßt sich die Relevanz eines Deskriptors für ein Dokument ablesen [Pan86a].

n D i = ∑ m Di (T j ) ^{Fuzzy Indexierung (10)} T j j=1

Für die zur Formulierung einer Frage verwendeten booleschen Operationen gilt [FEB99]: ∀ t ∈ T X UND Y := MIN{m X (t), m Y (t)} ^{Durchschnitt (11)} X ODER Y := MAX{m X (t), m Y (t)} ∀ t ∈ T ^{Vereinigung (12)} ∀ t ∈ T NICHT X := T\X = 1 - m x (t) Komplement (13)

mit X und Y: unscharfe Mengen über einer Grundmenge T

In experimentellen Untersuchungen hat sich jedoch gezeigt, daß die Minimum- und Maximumberechnung nicht immer günstig ist. Dies wird nachfolgend für die Dokumente aus Beispiel 6 illustriert.

Obwohl das Dokument D 2 bezüglich t 2 ein deutlich höheres Indexierungsgewicht besitzt, werden durch die Minimumberechnung beide Dokumente mit einem Retrieval Status Wert von 0,3 bewertet und würden damit beim Ranking der Dokumente den gleichen Rangplatz einnehmen.

Trotz der Vorteile, die Fuzzy Retrieval in Bezug auf Boolesches Retrieval bietet, sind immer noch einige, bereits aus dem Booleschen Retrieval bekannten Nachteile vorhanden. Da auch hier die Fragestellung über Boolesche Logik erfolgt, entfällt eine partielle Berücksichtigung der einzelnen Fragekomponenten. Das hat zur Folge, daß bei einer Suchanfrage mit acht unterschiedlichen, durch UND verbundenen Suchbegriffen, nur Dokumente gefunden werden, die alle acht Suchbegriffe enthalten. Dokumente, die sieben der acht Suchbegriffe enthalten, werden trotz des wahrscheinlich vorhandenen Interesses des suchenden Benutzers an ihnen, ebenso wie schon im Booleschen Retrieval, unberücksichtigt gelassen.

18 Grundlagen

2.2.1.3 Vektorraummodell

Das Vektorraummodell (VRM), ursprünglich aus dem von G. Salton entwickelten SMART-Retrievalsystem [SAL71a] entstanden, faßt die Dokumente und Fragen als Vektoren eines n-dimensionalen, durch die Dokumentterme aufgespannten, Vektorraumes auf. Die Informationssuche erfolgt über eine Ähnlichkeitsfunktion, die sog. Retrievalfunktion, die dazu dient, die Ähnlichkeit zwischen der gestellten Frage und den vorhandenen Dokumenten zu bewerten. Die Darstellung der Dokumente erfolgt durch gewichtete Indexterme, analog dem Fuzzy-Retrieval, wobei jetzt auch negative und Gewichte größer Eins zulässig sind: D i = (t i1 , ..., t in ) (14)

mit t ik ^{∈ |R} gewichteter Indexterm in Dokument D i , für k = 1,

.., n

Die Darstellung der Fragen erfolgt ebenfalls durch Vektoren: F j = (f j1 , ..., f jn } (15)

mit f jk ^∈ |R gewichteter Frageterm in Frage F j , für k = 1,

.., n

Die Gewichtung der Terme kann nach verschiedenen Verfahren vorgenommen werden,

das bekannteste ist das TFIDF ¹⁸ Schema, das nachfolgend (vgl. S. 32) noch näher erläutert wird. Für die Implementierung des VRM können, ebenso wie beim Booleschen Modell, invertierte Listen verwendet werden, es müssen allerdings zusätzlich zu den Positionsangaben die Gewichte gespeichert werden.

Zuletzt wird noch eine Retrievalfunktion benötigt, die für jedes Paar aus zwei Vektoren einen "Ähnlichkeitswert" errechnet. Unter der Annahme, daß der zugrundeliegende Vektorraum orthonormal ist, d.h. alle Term-Vektoren sind orthogonal (woraus die lineare Unabhängigkeit der Vektoren folgt) und alle Term-Vektoren sind normiert, kann als Retrievalfunktion für ein gegebenes Dokument D r und eine gestellte Frage F s das Skalarprodukt gewählt werden: n Ähn SK (D i , F j ) = ∑ t ik f jk Skalarprodukt (16)

k = 1

Das Skalarprodukt ist die am häufigsten gewählte Retrievalfunktion. Erlaubt man für die Gewichtung der Indexterme nur die Werte 0 und 1, erhält man den schon aus Abschnitt 2.2.1.1 bekannten Simple matching Koeffizienten. Gleichermaßen wie der Simple matching Koeffizient lassen sich die Formeln (2) bis (5), nach entsprechender Modifikation, als Ähnlichkeitsmaß für das VRM anwenden [FEB99]. n

2 ∑ t ik f jk k=1 Ähn Dice (D i , F j ) = ^{Dice's Koeffizient (17)} n n

¹⁸ TFIDF = Term Frequency x inverse document frequency

Grundlagen 19

n

∑

t ik f jk k=1

Ähn JC (D i , F j ) =

n n n

Ähn cos (D i , F j ) =

k=1

Ähn Üb (D i , F j ) = Überlappungs-Koeffizient (20)

n n

min( ∑ t ik ∑

Die Berechnung eines Ähnlichkeitsmaßes zwischen dem Fragevektor und den vorhandenen Dokumentvektoren ermöglicht auch hier eine Unterscheidung in relevante und nicht relevante Dokumente. Da beim VRM, ebenso wie im Fuzzy-Retrieval, die Indexterme gewichtet sind, ist es möglich den ursprünglichen Fragevektor, nach Erhalt einer passenden Antwort, durch Veränderung der Gewichte zu modifizieren. Diese Veränderung anhand von ermittelten Dokumenten ist als Relevance Feedback bekannt und kann bei mehrfacher Anwendung die Retrievalqualität erheblich verbessern.

Relevance Feedback

Der 1965 von J. Rocchio vorgestellte Prozeß des Relevance-Feedback [ROC65] baut auf der Annahme auf, daß sich Dokumente, die für eine bestimmte Frage als relevant eingestuft werden, insofern gleichen, als daß sie durch ähnliche Vektoren dargestellt werden. Aufbauend auf diese Annahme ist es möglich, die Fragequalität einer gestellten Frage zu verbessern. Dies geschieht, indem über die Terme des Fragevektors eine Anpassung an den Dokumentvektor eines, als relevant betrachteten Dokumentes, vorgenommen wird. Die Schwierigkeit bei diesem Vorgehen besteht darin, eine geeignete Methode zu finden, die einen gestellten Fragevektor hin zu den relevanten und weg von den unrelevanten Dokumenten verschiebt. Die von J. Rocchio [ROC71] vorgestellte Methode geht dabei folgendermaßen vor:

1. Der Anwender stellt eine Anfrage an das Retrieval System

2. Das System liefert eine (geordnete) Antwortmenge von Dokumenten, die es als relevant für die Anfrage beurteilt

3. Der Anwender wählt nun die für ihn relevant erscheinenden Dokumente aus dieser Antwortmenge aus und "füttert" das Retrieval System mit diesen Informationen

^{4. Eine erneute Anfrage, aufbauend auf die Benutzerauswahl, wird vorgenommen} Beispiel 8: Prozeß des Relevance Feedback

Eine Wiederholung der Schritte 3 und 4 ist beliebig oft möglich. Bei obiger Vorgehenswiese erhält der Anwender auf eine gestellte Frage F eine, auf ihre Relevanz hin zu beurteilende, (geordnete) Menge an Dokumenten. Nach Beurteilung durch den Anwender ergeben sich aus dieser Antwortmenge zwei Mengen von Dokumenten: R = {r i }, die Menge der als relevant eingestuften Dokumente und U = {u i }, die Menge der