Adaptive Informationssuche im Internet
Diplomarbeit

Vorgelegt von Sabrina Schulze

am Fachbereich Informatik
der Johann Wolfgang Goethe-Universität
Frankfurt am Main

Februar 2000

Betreuer: PD Dr. Rüdiger Brause

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
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
Anhang
Literaturverzeichnis ............ XXVIII

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.

¹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
⁴ 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