Adaptive Informationssuche im Internet

Inhaltsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

Algorithmenverzeichnis

Beispielverzeichnis

Abkürzungsverzeichnis

1 Einleitung
1.1 Motivation
1.2 Zielsetzung
1.3 Gliederung

2 Grundlagen
2.1 Data mining, Data Warehouse
2.1.1 Regeln
2.1.1.1 Klassifikationsregeln
2.1.1.2 Charakteristische Regeln
2.1.1.3 Regressionsregeln
2.1.1.4 Assoziationsregeln
2.1.2 Cluster
2.2 Information Retrieval
2.2.1 Standardverfahren
2.2.1.1 Boolesches Retrieval
2.2.1.2 Fuzzy Retrieval
2.2.1.3 Vektorraummodell
2.2.1.4 Cluster-Retrievalverfahren
2.2.1.5 Probabilistische IR-Verfahren
2.3 Software-Agenten
2.3.1 LAW: A learning Apprentice for the WWW
2.3.2 Syskill & Webert.
2.3.3 Letizia
2.3.4 WebWatcher
2.4 Selbstorganisierende Merkmalskarten
2.4.1 WEBSOM
2.5 Multidimensionale Skalierung
2.5.1 MDS nach dem Verfahren von Kruskal.
2.5.2 MDS nach dem SMACOF-Verfahren

3 Eigener Ansatz
3.1 Szenario
3.2 Dokumentbearbeitung
3.2.1 Anforderungen an einen Stoppvektor
3.2.2 Anforderungen an einen Thesaurus
3.2.3 Generierung von Dokumentenvektoren
3.3 Dokumentenkartenerstellung.

4 Simulation
4.1 Dokumentbearbeitung
4.1.1 Generierung eines Stoppvektors
4.1.2 Generierung eines Thesaurus
4.1.3 Generierung eines Dokumentenvektors
4.2 Dokumentenkartenerstellung
4.2.1 Definition eines Ähnlichkeitsmaßes
4.2.2 Anordnung der Dokumente nach dem CARD-Algorithmus
4.2.3 Anordnung der Dokumente mit MDS-Algorithmen
4.2.3.1 Anordnung nach dem Verfahren von Kruskal
4.2.3.2 Anordnung nach dem SMACOF-Verfahren.

5 Softwarestruktur
5.1 Implementierung der Dokumentbearbeitung mit ACCESS
5.1.1 Generierung des Stoppvektors.
5.1.2 Generierung eines Thesaurus
5.1.3 Erstellung des Dokumentvektors.
5.2 Implementierung der Dokumentenkartenerstellung mit JAVA
5.2.1 Basismethoden.
5.2.2 Der CARD-Algorithmus
5.2.3 Der MDS-Algorithmus nach Kruskal.
5.2.4 Der MDS-Algorithmus nach der SMACOF-Methode

6 Diskussion und Ausblick ... Fehler! Textmarke nicht definiert. Anhang. Fehler! Textmarke nicht definiert. Literaturverzeichnis

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 WEBSOM-Methode (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 ibei fehlendem Schnittpunkt, Fall 1

Abbildung 19: Berechnung der Position von d ibei 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 .73 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 .80 Abbildung 32: Anordnung der Beispieldokumente mit SMACOF; UWij = 1 – AGWij.81 Abbildung 33: Auszug aus dem Dokumentquelltext des Infodata-Thesaurus

Tabellenverzeichnis

Tabelle 1: Daten Retrieval versus Information Retrieval

Tabelle 2: Standardverfahren des IR

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

Tabelle 4: Statistik des Stoppvektors

Tabelle 5: Zipf'sches Gesetz

Tabelle 6: Auszug aus der generierten Stoppwortliste

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

Tabelle 8: Um Stoppworte reduzierter Wortvektor

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

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

Tabelle 11: Wortvektor nach Synonymabgleich

Tabelle 12: Werte der prozentualen Schranke

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

Tabelle 14: Beispiel-Dokumentvektoren

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

Tabelle 16: ACCESS-Tabelle HTML-Code

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

sortierten Stoppworten

Tabelle 18: Auszug aus der Tabelle Worttabelle

Tabelle 19: Synonyme in Tabelle Worttabelle

Tabelle 20: Tabelle BF

Tabelle 21: Verwandte Begriffe in Tabelle Worttabelle

Tabelle 22: Tabelle VB

Tabelle 23: in der Worttabelle enthaltene Worte aus Abbildung 33

Algorithmenverzeichnis

Algorithmus 1: Pseudo-Algorithmus zur hierarchischen Clusterbildung

Algorithmus 2: Pseudo-Algorithmus zur heuristischen Clusterbildung

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

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

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

Algorithmus 6: Pseudo-MDS-Algorithmus

Algorithmus 7: Pseudo-Majorisierungs-Algorithmus

Algorithmus 8: Pseudo-SMACOF-Algorithmus

Algorithmus 9: Pseudo-CARD-Algorithmus zur Dokumentenkartenerstellung

Algorithmus 10: Modifizierter Pseudo-CARD-Algorithmus zur Dokumentenkartenerstellung

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

Beispielverzeichnis

Beispiel 1: Klassifikationsregel

Beispiel 2: Charakteristische Regel

Beispiel 3: Assoziationsregel

Beispiel 4: Regeln zur Dokumentenvereinfachung

Beispiel 5: Boolesche Suche nach van Rijsberg in [RIJS79]:

Beispiel 6: Dokumentenbeschreibung im Fuzzy Retrieval

Beispiel 7: Bewertung von Dokumenten beim Fuzzy Retrieval

Beispiel 8: Prozeß des Relevance Feedback

Beispiel 9: top-down-Clustersuche

Beispiel 10: bottom-up-Clustersuche

Beispiel 11: WEBSOM-Artikellandkarte für Newsgroup-Artikel

Beispiel 12: Auszug aus dem Infodata-Thesaurus

Beispiel 13: Auszug aus dem Quellcode eines HTML-Dokuments

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

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.

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 ⁶ (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 ⁷ (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 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⁸.

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

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 ¹⁰ (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

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:

Abbildung in dieser Leseprobe nicht enthalten

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

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

WENN Kreditwuerdigkeit = hoch

DANN KreditTyp = A,B UND Angestellter = ja

Beispiel 2: Charakteristische Regel

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:

Lachs, Weißwein -> Weißbrot [0.45 / 0.003]

Beispiel 3: Assoziationsregel

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.

Abbildung in dieser Leseprobe nicht enthalten

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

"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

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].

Abbildung in dieser Leseprobe nicht enthalten

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

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:

Abbildung in dieser Leseprobe nicht enthalten

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:

- 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.

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.

Abbildung in dieser Leseprobe nicht enthalten

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 ¹⁶, da für jedes Dokument D die Übereinstimmung der zugehörigen Indexterme mit der gestellten Frage F nach dem s imple 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]:

Abbildung in dieser Leseprobe nicht enthalten

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 (wahr – bzw. 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.

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]:

Abbildung in dieser Leseprobe nicht enthalten

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].

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Typische Formen für Zugehörigkeitsfunktionen

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

Abbildung in dieser Leseprobe nicht enthalten

Beispiel 6: Dokumentenbeschreibung im Fuzzy Retrieval

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].

Abbildung in dieser Leseprobe nicht enthalten

Beispiel 7: Bewertung von Dokumenten beim Fuzzy Retrieval

Obwohl das Dokument D2 bezüglich t2 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.

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:

Abbildung in dieser Leseprobe nicht enthalten

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:

Abbildung in dieser Leseprobe nicht enthalten

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].

Abbildung in dieser Leseprobe nicht enthalten

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 =

Abbildung in dieser Leseprobe nicht enthalten

mit: n' r (n' u ) = Anzahl der relevanten (unrelevanten)

Dokumente, die im vorangegangenen Iterationsschritt gefunden wurden.

Eine ausführliche Betrachtung des Relevance Feedback-Verfahrens findet sich bei [IDE71], [IDS71] und [SAL89] Kapitel 10.1.2.

Das Gewichtungsverfahren TFIDF

Wie schon in Abschnitt 2.2.1 erwähnt, kann durch eine Gewichtung der Indexterme die potentielle Bedeutsamkeit der Deskriptoren für ein Dokument und somit auch für das Retrieval ausgedrückt werden. Es ist daher wünschenswert die Berechnung der Gewichte für einen Indexterm anhand einer automatischen Methode vornehmen zu können. Diese Methode muß in der Lage sein, automatisch zu erkennen, welche Deskriptoren als gute Charakteristika für ein Dokument dienen.

H. P. Luhn [LUH58] zeigte, daß die Häufigkeit einzelner Worte in einem Dokument ein nützliches Maß für die Signifikanz dieses Wortes bildet. Für die Verteilung von Worten, absteigend nach ihrer Häufigkeit geordnet, gilt nach dem Zipf'schen Gesetz [ZIP49]:

Häufigkeit · Rangplatz ~ konstant (23)

Obige Gleichung läßt die Schlußfolgerung zu, daß einige wenige, häufig im Dokument vorkommende Worte einen Großteil des Dokumententextes abdecken, während eine große Anzahl der selten im Dokument vorkommenden Worte nur einen geringen Anteil am Dokumententext besitzen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Darstellung relevanter Begriffe

Für die Beschreibung eines Dokumentes eignen sich daher die Begriffe, die in Abbildung 3 im mittleren Bereich liegen. Begriffe, die in die Zone der zu häufigen Terme fallen sind u.a. Stoppwörter wie Konjunktionen, Präpositionen, Pronomen etc. Für Begriffe aus der Zone der selten auftretenden Terme gilt, daß ein Schwellwert definiert werden kann, so daß auch diese Terme nicht mehr als relevant angesehen werden. Allerdings ist bei der Wahl dieses Schwellwertes zu bedenken, daß selten vorkommende Begriffe gut dazu genutzt werden können, die wenigen Dokumente, in denen sie vorkommen, von den vielen, in denen sie fehlen, zu unterscheiden. Die

Überlegung von Luhn liefert somit eine Liste von Schlüsselwörtern (Termen), die anhand ihrer Häufigkeit¹⁹ im Dokument gewichtet werden.

tf ij Termhäufigkeit (24)

mit tf ij: Vorkommenshäufigkeit von Term t j in einem Dokument d i

Die lokale Vorkommenshäufigkeit in einem Dokument allein ergibt leider noch keinen guten Gewichtungswert, da ein Term, der durch sein häufiges Vorkommen in einem Dokument durchaus ein guter Indexterm für dieses spezielle Dokument sein kann, für die Menge aller vorhandenen Dokumente ein schlechter Wert sein kann, wenn er auch in den übrigen Dokumenten häufig vorkommt. Für die Unterscheidung der einzelnen Dokumente ist dieser Term dann weniger nützlich als ein Term, der nur in einigen wenigen Dokumenten auftritt. Deshalb wird für die Berechnung der

Deskriptorengewichte zusätzlich für jeden Term t j dessen globale Vorkommenshäufigkeit, die Dokumentenhäufigkeit df(j) ²⁰, ermittelt. Basierend auf der Annahme, daß die Häufigkeit eines Terms umgekehrt proportional zu dessen

Dokumentenhäufigkeit ist, kann die Berechnung anhand einer inversen Funktion der Dokumentenhäufigkeit eines Terms erfolgen. Typische Formen der inversen Dokumentenhäufigkeit²¹ sind durch

Abbildung in dieser Leseprobe nicht enthalten

gegeben ([FEB99] und [SPJ72]). Durch Verknüpfen der lokalen und globalen Vorkommenshäufigkeit eines Terms erhält man das als TFIDF-Verfahren bekannte Indexierungs-Modell:

Die Verwendung von Formel (26) schwächt die Gewichte seltener Terme ab, da durch die Verwendung des Logarithmus eine Abschwächung großer Werte geschieht.

2.2.1.4 Cluster-Retrievalverfahren

Im Unterschied zu den in den vorangegangenen Abschnitten vorgestellten Verfahren, baut das Cluster-Retrievalverfahren nicht explizit auf einem Frage-Antwort-Modell auf, sondern nutzt die Ähnlichkeit von Dokumenten, um von einem relevanten Dokument zu weiteren, möglicherweise ebenfalls relevanten Dokumenten zu gelangen. Grundlage für dieses Vorgehen bildet die von van Rijsberg [RIJS79] aufgestellte 'Cluster-Hypothese':

"Eng verwandte Dokumente tendieren dazu, für dieselben Fragen relevant zu sein."

Wie schon bei den DM-Verfahren in Abschnitt 2.1.2 erwähnt, werden bei Clusterverfahren Objekte aufgrund von Ähnlichkeiten in Cluster, Gruppen von ähnlichen Objekten, eingeordnet. Beim IR dient die Clusterbildung dazu, die Ähnlichkeit einer gestellten Frage mit einem bereits vorhandenen Cluster zu ermitteln. Ziel des Cluster-Retrievals ist es, die Cluster, unabhängig von den später gestellten Fragen, schon beim Aufbau der Dokumentenkollektion anhand eines festgelegten Ähnlichkeitsmaßes (Skalarprodukt, Kosinus-Maß etc.) zu berechnen. Dies geschieht, indem zuerst die Ähnlichkeit (oder Distanz) zwischen den einzelnen Dokumenten berechnet wird und anschließend alle Dokumente, die eine ausreichend hohe Ähnlichkeit (oder ausreichend niedrige Distanz) aufweisen, in einem Cluster zusammengefaßt werden. Es sollten dabei allerdings, bei der für die Clusterung ausgewählten Methode, folgende Kriterien beachtet werden [JAS71]:

1. Die Methode sollte wachstumsstabil sein, d.h. bei einer Hinzunahme neuer Dokumente verändert sich die vorhandene Clusterstruktur nur minimal.
2. Die Methode sollte stabil gegenüber kleinen Fehlern sein, d.h. eine Veränderung vorhandener Dokumente führt nur zu kleinen Änderungen an der Clusterstruktur (bspw. bei einer fehlerhaften Beschreibung der Dokumente).
3. Die Methode ist unabhängig von der erstmaligen Ordnung der Objekte.

Für die Berechnung der Cluster existieren eine Vielzahl unterschiedlicher Cluster- Algorithmen, die im einzelnen hier nicht näher betrachtet werden (vgl. [CRO72], [FRI74], [RIJS79], [SAL68] und [SAL71a] sowie , [BB63], [BON64] und [NSJ64], die

sich im besonderen mit dem Clustern von Dokumenten befassen). Stattdessen wird ein allgemeiner Überblick über das Vorgehen bei der Clustererzeugung gegeben.

Clustererzeugung

Für die Clusterbildung von Objekten existieren hauptsächlich zwei verschiedene Methoden:

- die Clusterung basiert auf einem Ähnlichkeitsmaß zwischen den zu clusternden Objekten (hierarchische Methoden)
- die Clusterung ergibt sich direkt aus den Objektbeschreibungen (heuristische Methoden)

Für den ersten Fall bietet sich die Verwendung von graphentheoretischen Methoden an. Eine Vorgehensweise dabei wird in nachfolgendem Pseudo-Algorithmus und anhand eines Beispiels erläutert:

1. Gegeben: n Objekte
2. Berechne für alle n(n – 1)/2 unterschiedlichen Paare die zugehörigen Ähnlichkeitswerte anhand eines Ähnlichkeitsmaßes
3. Erstelle eine Ähnlichkeitsmatrix für die in 2 berechneten Ähnlichkeitswerte (ÄW)
4. Definiere einen Schwellwert (SW)
5. Verbinde alle Dokumentenpaare mit einer Kante, für die gilt ÄW ³ SW
6. Bilde für alle, durch eine Kante zusammenhängenden Objekte, ein eigenes Cluster

Algorithmus 1: Pseudo-Algorithmus zur hierarchischen Clusterbildung

Der soeben beschriebene Algorithmus verwendet die sog. "single-link" -Methode²² und ist eine Methode, die alle auf Seite 22 aufgeführten Kriterien erfüllt. Es ist klar ersichtlich, daß die Anzahl der gebildeten Cluster stark vom gewählten Schwellwert abhängt. Zur Verdeutlichung nachfolgend ein Beispiel für die Bildung von Clustern für 5 Objekte nach der single-link-Methode:

Graphen und die gebildeten Cluster (in gestrichelten Linien) für den jeweils angegebenen SW:

Abbildung in dieser Leseprobe nicht enthalten

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

Außer der single-link-Methode existieren noch weitere hierarchische Methoden zur Clusterbildung, wie z.B. complete-link und average-link, die hier jedoch nur erwähnt sein sollen. Für eine detaillierte Beschreibung und Bewertung vgl. [SAL89] und [SIB71].

Für die soeben beschriebenen Methoden der Clusterbildung ist es notwendig, im Vorfeld die paarweisen Ähnlichkeitswerte zwischen allen Objekten zu berechnen. Da diese Vorgehensweise nicht sonderlich effizient ist, versuchen heuristische Methoden eine Clusterbildung direkt aus der Objektbeschreibung heraus; sie bilden mit relativ geringem Aufwand schnell grobe Cluster. Die Vorgehensweise wird auch hier anhand eines Pseudo-Algorithmus erläutert. Auf die im Algorithmus aufgeführten Clusterrepräsentanten (CR) wird im nachfolgenden Abschnitt (Clusterretrieval, S. 25) näher eingegangen, hier sei dazu lediglich angemerkt, daß CR Objekte sind, die die in einem Cluster vorhandenen Objekte zentralisieren und repräsentieren:

1. Gegeben: n Objekte
2. Wähle jeweils ein Objekt in beliebiger Reihenfolge aus
3. Das erste Objekt wird gleichzeitig das erste Cluster und der Clusterrepräsentant des ersten Clusters
4. Jedes nachfolgend ausgewählte Objekt wird mit allen bereits vorhandenen CR's verglichen
5. Wenn die Ähnlichkeit zwischen dem aktuellen Objekt und einem
bereits bestehenden Cluster über einem festgelegten SW liegt, wird das Objekt in das bereits bestehende Cluster eingefügt
sonst bildet das Objekt gleichzeitig sein eigenes Cluster und seinen eigenen CR
6. Wenn ein Objekt einem Cluster hinzugefügt wird, wird der CR für dieses Cluster neu berechnet

Algorithmus 2: Pseudo-Algorithmus zur heuristischen Clusterbildung

Der soeben beschriebene Pseudo-Algorithmus ist ein sog. "single-pass" -Algorithmus, da er zur Clusterbildung nur einen Durchlauf durch die vorhandene Objektmenge benötigt. Im allgemeinen bildet ein single-pass-Algorithmus eine ungleiche Clusterstruktur, d.h. es werden zum einen Cluster mit sehr vielen Objekten gebildet während zum anderen Cluster mit nur einem oder zwei Objekten gebildet werden. Aus diesem Grund werden bei den meisten heuristischen Clusteralgorithmen einige zusätzliche, empirisch ermittelte, Parameter benutzt, die:

- die Anzahl der gewünschten Cluster
- eine minimale und maximale Größe für jedes Cluster und
- das Verhältnis der Überlappung (die Anzahl der gemeinsamen Items) kontrollieren. Der wahrscheinlich wichtigste heuristische Clusteralgorithmus ist der von J. Rocchio im Zuge des SMART-Projekts entwickelte [GM71], [ROC66], [ROC71]; die wahrscheinlich einfachste Version die von Hill [HIL68]. Ebenfalls erwähnenswert erscheinen die Algorithmen von Dattola [DAT68] und MacQueen [MCQ67].

Der größte Vorteil der heuristischen Clustermethoden gegenüber den hierarchischen ist ihre Geschwindigkeit: O(n log n) im Gegensatz zu O(n²). Nachteilig ist allerdings zu bewerten, daß die endgültige Clusterstruktur von der Reihenfolge der zu clusternden Objekte abhängt. Wird auf eine Erfüllung der auf S. 22 aufgeführten Kriterien Wert gelegt, sollte demnach ein hierarchischer Clusteralgorithmus einem heuristischen vorgezogen werden.

Clusterretrieval

Durch die Bildung von Clustern wird beim Clusterretrieval ein Abgleich einer Suchanfrage mit einem bestehenden Cluster auf die zwischen der Suchanfrage und dem Cluster bestehende Ähnlichkeit ermöglicht. Um diesen Vergleich durchführen zu können, ist es notwendig, daß die einzelnen Cluster durch einen sog. "Clusterrepräsentanten" repräsentiert werden. Der Vergleich zwischen der gestellten Frage und den jeweiligen Clustern erfolgt dann über die Berechnung des Ähnlichkeitsmaßes zwischen der Frage und allen vorhandenen Clusterrepräsentanten (CR). Obwohl aus theoretischer Sicht als CR jedes Dokument eines Clusters gewählt werden könnte, bietet es sich aus praktischer Sicht an, ein Dokument zu wählen, das im Mittelpunkt eines Clusters liegt und somit auf gewisse Art und Weise eine "durchschnittliche" Beschreibung der zum Cluster gehörenden Dokumente darstellt. Da die Repräsentation der einzelnen Dokumente und Fragen, wie beim Vektorraummodell, über Indextermen erfolgt, ergibt sich für den CR folgende Formel:

[...]

---

¹ A dvanced R esearch P roject A gency NET

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

³ Dokumente werden im WWW mit Hilfe der H yper t ext M ark-up L anguage (HTML) realisiert

⁴ 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

⁸ vgl. Verzeichnis \Dokumentation

⁹ Massachusetts Institute of Technology Labaratories

¹⁰ wörtl. Datenwarenhaus

¹¹ wörtl. Gruppen, Haufen

¹² wörtl. teile und herrsche

¹³ matching = wörtl. passend

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

¹⁵ bei der Clusteranalyse erfolgt dieser Vergleich nur indirekt

¹⁶ simple matching = einfache Übereinstimmung

¹⁷ Fuzzy Retrieval = Wiedergewinnung aus unscharfen Mengen

¹⁸ TFIDF = Term Frequency x inverse document frequency

¹⁹ T erm F requency tf

²⁰ die Dokumentenhäufigkeit (document frequency) df(j) ist definiert als die Anzahl der Dokumente, die Term j enthalten

²¹ i nverse D ocument F requency idf

²² single link = wörtl. einfache Verbindung