Ein Fuzzy Approach im Information Retrieval

Inhaltsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

1 Einleitung

2 Aspekte des Information Retrieval
2.1 Definition und Abgrenzung
2.2 Datenstrukturen in Informationssystemen
2.2.1 Hashbasierte und Intervallbasierte Datenstrukturen
2.2.2 Signature Files und Inverted Files
2.3 Verfahren zur Indexierung von Dokumenten
2.4 Suchtechniken im Information Retrieval
2.4.1 Boolesches Retrieval
2.4.2 Fuzzy Retrieval
2.4.3 Vektorraum-Modell
2.4.4 Probabilistisches Retrieval
2.5 Typologie von Informationssystemen
2.5.1 Information Retrieval Systeme
2.5.2 Datenbankmanagementsysteme
2.5.3 Expertensysteme
2.5.3.1 Werkzeuge für Expertensysteme
2.5.4 Weitere Informationssysteme

3 Der Einsatz von Information
3.1 Internet - Entwicklung und Wachstum
3.2 Information Overload
3.2.1 Information Overload im Unternehmen
3.2.2 Vom Information Retrieval zum Information Overload
3.2.3 Information Overload im Internet

4 Die Data Warehouse-Technologie
4.1 Einführung
4.2 Definition
4.3 Entwicklung der Data Warehouse-Technologie
4.4 Data Warehouse Konzepte
4.4.1 Data Warehouse Modell der META Group
4.4.2 Data Warehouse Funktionen nach SINGH
4.5 Datenverarbeitung im Data Warehouse
4.5.1 Transaction Processing und OLTP
4.5.2 Decision Support Processing
4.5.3 Online Analytical Processing (OLAP)
4.6 Data Warehouse und Data Marts
4.7 Data Warehouse Reifemodell
4.8 Data Warehousing in der Praxis

5 Verfahren des Data Mining
5.1 Einleitung
5.2 Definition
5.3 Knowledge Discovery in Databases (KDD)
5.4 Prozeßmodelle
5.5 Methoden und Muster
5.5.1 Muster
5.5.2 Methoden
5.5.2.1 Klassifikation
5.5.2.2 Schätzung
5.5.2.3 Vorhersage
5.5.2.4 Ähnlichkeitsgruppierung
5.5.2.5 Clustering
5.5.2.6 Deskription
5.6 Techniken
5.6.1 Entscheidungsbaumverfahren
5.6.2 Analyse von Beziehungen zwischen Datensätzen
5.6.3 Fallbasiertes Schließen
5.6.4 Automatische Clusteranalyse
5.6.5 Genetische Algorithmen
5.6.6 Neuronale Netze
5.6.7 Visualisierung
5.7 Data Mining-spezifische Problematiken
5.7.1 Datenprobleme
5.7.2 Prozeßprobleme
5.8 Data Mining im Unternehmen
5.8.1 Corporate Intranets
5.9 Anwendungen in der Praxis

6 Ein Fuzzy Approach im Information Retrieval
6.1 Verarbeitung unscharfer Daten
6.1.1 Rough Sets
6.1.1.1 Allgemein
6.1.1.2 Rough Set-Theorie
6.1.2 Fuzzy Logic
6.1.2.1 Allgemein
6.1.2.2 Entwicklungsüberblick
6.1.2.3 Fuzzy Sets
6.1.2.4 Possibilität versus Probabilität
6.1.2.5 Approximatives Schließen
6.1.2.6 Fuzzy Systeme
6.2 Entwicklung eines Fuzzy Approachs
6.2.1 Allgemein
6.2.2 Konzept
6.2.3 Realisierung

7 Die Implementierung eines Prototypen in C++
7.1 Allgemeine Programmbeschreibung
7.2 Klassen und Methoden
7.3 Input/Output Schnittstelle
7.4 Ein Musterbeispiel
7.5 Berechnung multipler Kategorie-Dependenzen

8 Zusammenfassung und Schlußbetrachtung

9 ANHANG
9.1 Überblick über die Literaturdatenbank INSPEC
9.2 C++ Fuzzy Approach Implementierung: Headerdatei <FuzzyWert.h>
9.3 Aktuelle Data Warehouse Lösungen (04/1999)
9.3.1 Administration, Management und Performance
9.3.2 Design und Methodik
9.4 OLAP Lösungen
9.5 Data Mart Lösungen
9.6 Data Mining Lösungen

10 Literaturverzeichnis

Abbildungsverzeichnis

Abbildung 2-1: Graphische Darstellung des Zipfschen Gesetzes

Abbildung 2-2: Benutzerinteraktion in einem Informationssystem

Abbildung 2-3: Aufbau eines Information Retrieval Systems

Abbildung 2-4: Architektur eines typischen Expertensystems

Abbildung 3-1: Globaler Wachstum des Internets

Abbildung 3-2: Prozeß der Wissensgenerierung

Abbildung 4-1: Data Warehouse-Wertschöpfungskette der META Group

Abbildung 4-2: 6-Schichten Data Warehouse-Referenzmodell

Abbildung 4-3: Datenstruktur im Data Warehouse

Abbildung 4-4: Die Kette der Data Warehouse Funktionen nach SINGH

Abbildung 4-5: Dreidimensionale Tabellenansicht mit OLAP

Abbildung 4-6: Data Warehouse Reifemodell (META GROUP)

Abbildung 5-1: Symbolischer Mining-Prozeß

Abbildung 5-2: KD-Phasen

Abbildung 5-3: The Virtuous Cycle of Data Mining

Abbildung 5-4: Unterscheidung zwischen Situationen und Parameterwerten

Abbildung 5-5: Neuro-Fuzzy System

Abbildung 5-6: SeeIt, Screenshot

Abbildung 5-7: SeeIt, Industry, Revenues and Profit.

Abbildung 5-8: Crossgraphs, U.S. Präsidentenwahl

Abbildung 5-9: DAISY, Data Analysis Interactively

Abbildung 6-1: Rough Approximation für Menge X

Abbildung 6-2: Exakte Menge "mittleres Alter"

Abbildung 6-3: Fuzzy Sets der Altersgruppen

Abbildung 6-4: Fuzzy System Klimaanlage

Abbildung 7-1: Programmfenster nach dem Start

Abbildung 7-2: Fehlerfreier Datenimport

Abbildung 7-3: Programmfenster nach dem Einlesen der drei Fuzzy Sets

Abbildung 7-4: Programmfenster nach der Verknüpfung der Fuzzy Sets

Abbildung 7-5: Ausgabefenster <Rough Set-Regelbasis>

Abbildung 7-6: Hauptfenster nach der Verknüpfung der sechs Kategorien

Abbildung 7-7: Regelbasis für sechs Kategorien

Tabellenverzeichnis

Tabelle 2-1: Abgrenzung von Fakten-Retrieval und Information Retrieval nach Van Rijsbergen.

Tabelle 2-2: Beispiel-Datenbank <Verwaltungsgliederung Kanada>

Tabelle 6-1: Possibilität und Probabilität für eine bestimmte Person

Tabelle 6-2: Fuzzy Control-Regelbasis zur Steuerung einer Klimaanlage

Tabelle 6-3: Kategorien und Attributausprägungen für das Fluglinien-Beispiel

Tabelle 6-4: Kundenpräferenz-Intervalle

Tabelle 7-1: Berechnungstabelle für neu erzeugte Objekte

Tabelle 7-2: Einbeziehung multipler Faktoren

1 Einleitung

Information ist die essentielle Basis für taktische und strategische Unternehmensentscheidungen. Ein effektives Informationsmanagement im Unternehmen muß gewährleisten, daß die benötigten Informationen aus den vorhandenen Datenbeständen extrahiert und zur Entscheidungsunterstützung mittels effizienter Informationslogistik an die richtigen Mitarbeiter weitergeleitet werden. Die praktische Umsetzung dieser Forderungen wird jedoch von unterschiedlichsten Problematiken begleitet und stellt Unternehmen gerade aufgrund der dynamischen Wirtschafts- und Informationsstruktur täglich vor neue Herausforderungen. Unter diesen Voraussetzungen erfordern die Bereiche Datensammlung, Informationsspeicherung und Wissensextraktion besondere Beachtung, da ausschließlich flexible, innovative und leistungsfähige Werkzeuge lösungsrelevante Resultate erzielen können, die mittel- und auch langfristig den Unternehmenserfolg und die Wettbewerbsfähigkeit sichern.

In den letzten Jahrzehnten wurde der Umgang mit Information einem starken Wandel unterzogen. Vor einigen Jahren existierten nur wenige Informationen, die meist schwierig abzurufen und auszuwerten waren. Sie waren zudem oft unvollständig und konnten kaum elektronisch bearbeitet werden, da die Leistungsfähigkeit der Systeme zu gering war und diese häufig inkompatibel waren. Entscheidungsunterstützendes Wissen mußte vorwiegend „manuell“ aus den Informationen extrahiert werden, damit es zur Lösung von Unternehmensproblemen verwendet werden konnte.

Im Laufe der Zeit haben sich jedoch die Informationsstrukturen entscheidend geändert. Aus dem Mangel an Informationen wurde ein Überschuß an Daten, der auch als Data Overload bezeichnet wird und in fast allen Bereichen des Lebens auftritt, da der Aufwand und die Kosten der Datensammlung nur mehr einen Bruchteil dessen ausmachen, was für die Informationsgewinnung und Wissensextraktion eingesetzt werden muß. Der häufig zitierte Begriff des Information Overload ist nur dann gegeben, wenn die gesammelten Daten mittels Datenvorbereitungs- und Datenhygiene-Verfahren so bearbeitet werden, daß daraus Informationen entstehen. Ein Unternehmen ist daher gefordert, unter den Bedingungen des Datenüberschusses alle relevanten Informationen zu speichern, um diese als Quelle für Wissensextraktionen zu verwenden.

Das unternehmensweite Data Warehouse bietet die Lösung eines umfassenden Informationsmanagements auf Basis des Information Retrievals. In diesem Zusammenhang sind Verfahren des Knowledge Discovery in Databases (Data Mining, Datenvisualisierung) von großer Bedeutung und essentiell für entscheidungsunterstützende Prozesse, da in gigantischen Datenmengen durch traditionell mathematisch-statistische Methoden, sowie durch Techniken der informationstheoretischen Kybernetik nach Informationen gesucht wird, aus denen im weiteren Wissen extrahiert wird.

In dieser Arbeit wird Ein Fuzzy Approach im Information Retrieval vorgestellt, der ein innovatives Verfahren darstellt, um vage bzw. ungenaue Daten, die in Form von Präferenz-Intervallen vorliegen, zur Wissensextraktion zu verwenden. Der neue Ansatz kombiniert die entscheidenden Theorien zur Behandlung unscharfer Daten und Mengen, Rough Sets und Fuzzy Sets, und extrahiert Zielintervalle, die einer approximativen Abbildung der Eingabedaten entsprechen. Aus diesen Rough Intervals werden Regeln formuliert, die als Regelbasis in wissensbasierten Systemen zur automatischen Entscheidungsunterstützung verwendet werden können.

In Kapitel 2 wird der Begriff des Information Retrieval in seinen Facetten erfaßt und klassifiziert. Dabei werden die unterschiedlichen Datenstrukturen, die Verfahren zur Indexierung von Dokumenten, sowie die Suchtechniken im Information Retrieval, verbunden mit den verschiedenartigen Computer-Informationssystemen, berücksichtigt. Dieser Teil versucht zudem, anhand der Entwicklung des elektronischen Information Retrievals den Bedarf und die Entstehung des heutigen Data Warehouse zu verdeutlichen.

Kapitel 3 betrachtet informationstheoretische Aspekte im Zusammenhang mit dem neuen Medium Internet, sowie die wachsende Informationsglobalisierung und die Problematiken der daraus resultierenden, exponentiell wachsenden Informationsmenge.

Neben den einführenden Grundlagen und Definitionen zum Thema Data Warehouse werden in Kapitel 4 das Konzept und die Möglichkeiten einer erfolgreichen Umsetzung analysiert. Im Vordergrund stehen dabei der wirtschaftliche Aspekt und die Erstellung eines unternehmensweiten Informationsmanagements auf Basis der Data Warehouse-Technologie. Hier werden auch die wichtigsten Funktionalitäten wie Online Analytical Processing (OLAP), Decision Support Processing (DSP) und Online Transaction Processing (OLTP) betrachtet, sowie Vergleiche gegenüber dem Einsatz von Data Marts gezogen.

Das anschließende Kapitel 5 klassifiziert den umfassenden Begriff des Data Mining in Zusammenhang mit Knowledge Discovery in Databases und stellt die grundlegenden Prozeßmodelle vor, auf denen die Methoden zur Mustererkennung basieren. Im weiteren werden anhand unterschiedlicher Techniken die Möglichkeiten und Problematiken des Data Mining, besonders in Verbindung mit Corporate Intranets, aufgezeigt und analysiert.

In Kapitel 6 wird der theoretische Hintergrund für den Fuzzy Approach im Information Retrieval erläutert. Während der erste Abschnitt die Verfahren zur Verarbeitung unscharfer Daten, Fuzzy Sets und Rough Sets, beschreibt und voneinander abgrenzt, wird anschließend das Konzept dieses auf Unschärfe basierenden Ansatzes zur Wissensextraktion vorgestellt und im Detail präzisiert. Danach wird die Funktionsweise des Verfahrens seitens einer praktischen Problemstellung demonstriert.

Mit der Programmbeschreibung des Fuzzy Approach im Information Retrieval bezieht sich Kapitel 7 auf den praktischen Teil der Arbeit. Das Konzept wurde in C++ implementiert und resultiert in dem Prototypen RoughProject.exe, das aus beliebig vielen Kategorien Rough Intervals extrahieren und damit entscheidungsunterstützende Regeln für wissensbasierte Systeme formulieren kann. Anhand eines komplett illustrierten Musterbeispieles werden die einzelnen Funktionalitäten aufgezeigt und die Anwendungsgebiete konkretisiert. Ein weiteres Beispiel erläutert den Programmeinsatz zur Extraktion multipler Kategorie-Dependenzen und veranschaulicht den praktischen Einsatz für innovative Problemstellungen.

Das Programm RoughProject.exe und die englische Version RoughEnglishProject.exe sind der Arbeit auf Diskette beigelegt. Neben den erforderlichen Libraries ist auch der gesamte Quellcode gespeichert.

2 Aspekte des Information Retrieval

Die Thematik des Information Retrievals (IR) kann mit inhaltlicher Suche in Texten umschrieben werden [Fuhr, 1993]. Diese allgemeine, vereinfachte Definition gilt für den bedeutendsten Bereich, das Text- und Dokumentenretrieval. Das Retrieval bezieht sich dabei auf den Abruf bzw. das Wiederauffinden dieser Informationen. [Salton und McGill, 1987], [Ferber, 1997].

Aufgabe der Forschung im Gebiet des Information Retrievals ist das Suchen von Lösungsansätzen für Problematiken dieser Art, um gerade mit elektronischer Unterstützung effiziente IR Systeme zu entwickeln. Da sich die Technologie im Bereich der Rechnerhardware und der Softwaretechniken in den letzten Jahren fortlaufend weiterentwickelt hat, ist auch das Forschungsinteresse auf dem Gebiet des Information Retrievals konstant hoch geblieben.

2.1 Definition und Abgrenzung

Information Retrieval^[1] hat sich allgemein als Oberbegriff für das Wiederauffinden von Informationen durchgesetzt. Genauer bezieht sich das Information Retrieval auf die Repräsentation, Speicherung und Organisation von Informationen und den Zugriff auf Informationen [Salton und McGill, 1987]. Diese sind überwiegend in Textform gespeichert, doch in der heutigen Zeit ergänzen gerade multimediale Dokumente, die Grafiken, Bilder, Video, Sprache oder Ton enthalten können, die bestehenden Informationssammlungen. Die in der Wissenschaft des IR entstandenen Information Retrieval Systeme (IRS) definiert Van Rijsbergen als automatische IRS. Automatisch kann dabei als Gegensatz zu manuell, Information gegenteilig zu Daten oder Fakten gesehen werden. Dabei zeigt sich die Vieldeutigkeit des Wortes Information. Lancaster bietet eine genauere Definition [Lancaster 1968, zitiert nach Van Rijsbergen, 1979]:

„Information Retrieval is the term conventionally, though somewhat inaccurately, applied to the type of activity discussed in this volume^[2]. An information retrieval system does not inform (i.e. change the knowledge of) the user on the subject of his inquiry. It merely informs on the existence (or non-existence) and whereabouts of documents relating to his request.“

Mit dieser Definition werden Frage-Antwort-Systeme sowie Data Retrieval Systeme (z.B. Online Aktienkurse) ausgegrenzt. Eine Gegenüberstellung von Fakten-Retrieval (Data Retrieval) und Information Retrieval liefert Tabelle 2-1 [Van Rijsbergen, 1979]. Rijsbergen vergleicht hier im Einzelnen die Merkmale des exakten Fakten-Retrievals, das einem Datenbankmanagementsystem entsprechen soll, mit einem Information Retrieval System.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2-1: Abgrenzung von Fakten-Retrieval und Information Retrieval
nach Van Rijsbergen.

Eine aktuellere Definition liefert die <Fachgruppe Information Retrieval der Gesellschaft für Informatik> an der Universität von Dortmund (zitiert nach [Fuhr, 1993]):

„Im Information Retrieval (IR) werden Informationssysteme in Bezug auf ihre Rolle im Prozeß des Wissenstransfers vom menschlichen Wissensproduzenten zum Informations-Nachfragenden betrachtet. Die Fachgruppe "Information Retrieval" in der Gesellschaft für Informatik beschäftigt sich dabei schwerpunktmäßig mit jenen Fragestellungen, die im Zusammenhang mit vagen Anfragen und unsicherem Wissen entstehen. Vage Anfragen sind dadurch gekennzeichnet, daß die Antwort a priori nicht eindeutig definiert ist. Hierzu zählen neben Fragen mit unscharfen Kriterien insbesondere auch solche, die nur im Dialog iterativ durch Reformulierung (in Abhängigkeit von den bisherigen Systemantworten) beantwortet werden können; häufig müssen zudem mehrere Datenbasen zur Beantwortung einer einzelnen Anfrage durchsucht werden. Die Darstellungsform des in einem IR System gespeicherten Wissens ist im Prinzip nicht beschränkt (z.B. Texte, multimediale Dokumente, Fakten, Regeln, semantische Netze). Die Unsicherheit (oder die Unvollständigkeit) dieses Wissens resultiert meist aus der begrenzten Repräsentation von dessen Semantik (z.B. bei Texten oder multimedialen Dokumenten); darüber hinaus werden auch solche Anwendungen betrachtet, bei denen die gespeicherten Daten selbst unsicher oder unvollständig sind (wie z.B. bei vielen technisch-wissenschaftlichen Datensammlungen). Aus dieser Problematik ergibt sich die Notwendigkeit zur Bewertung der Qualität der Antworten eines Informationssystems, wobei in einem weiteren Sinne die Effektivität des Systems in Bezug auf die Unterstützung des Benutzers bei der Lösung seines Anwendungsproblems beurteilt werden sollte.“

2.2 Datenstrukturen in Informationssystemen

Die Entwicklung zur Organisation gespeicherter Daten auf Massenspeichermedien gleicht einem dynamischen Prozeß, bei dem jede einzelne Struktur Vor- bzw. Nachteile für spezielle Datensätze oder Dokumente aufweist. Das Hauptproblem bei der Suche nach der richtigen Datenstruktur ist demnach, ein Verfahren zu finden, das Informationen auf einfache Art abspeichern und schnell wiederfinden kann. Geht man von der einfachsten Struktur, einer linearen Liste, aus, ist das Prinzip der Datenorganisation leichtverständlich [Salton und McGill, 1987]. Jeder neue Datensatz wird an das Ende der Liste angehängt und Datensätze können einfach gelöscht werden. Der gravierende Nachteil liegt aber in der Ineffizienz bei der Suche. Bei n Dokumenten müssen durchschnittlich (n+1)/2 Datensätze untersucht werden. Da Datenbanken in der heutigen Zeit die 1 Terabyte^[3] -Grenze schon überschritten haben und in Zukunft die Größenordnung von Exabytes^[4] erreichen werden, wäre es wohl kaum möglich, das gesuchte Dokument mit dieser Datenstruktur in kurzer Zeit zu finden. Daher wurden Verfahren entwickelt, die entweder durch die zugrundeliegende Struktur oder durch die darauf zugreifenden Algorithmen schnelle Retrieval-Zeiten haben. Folgende grundlegende Datenstrukturen stellen den Ausgangspunkt für ein effizientes Verfahren dar [Wirth, 1979], [Sedgewick, 1992]:

2.2.1 Hashbasierte und Intervallbasierte Datenstrukturen

Hashbasierte Datenstrukturen sind Arrays mit einer gleichmäßig verteilenden Abbildungsfunktion, die den Datensatz mit Hilfe eines Schlüssels einem Array zuweist, wobei Kollisionsprobleme durch eine spezielle Strategie gelöst werden. Das ermöglicht auch bei stark wachsenden Datenmengen ein schnelles Einfügen und Wiederauffinden von Datensätzen. Die verschiedenen Hash-Verfahren unterscheiden sich nur durch die Kollisionsbehandlung und Datenstruktur. Welches Verfahren für welche Anwendung im Information Retrieval geeignet ist, kann aber meist erst nach genauer Analyse der vorhandenen und zu erwartenden Datensätze eruiert werden. Intervallbasierte Datenstrukturen hingegen erleichtern Bereichsabfragen durch ihren geordneten Aufbau. Während in hashbasierten Datenstrukturen nur einzelne Datensätze schnell gesucht werden können, wird mit intervallbasierten Datenstrukturen eine mehrdimensionale Sortierung erreicht.

Hashbasierte Datenstrukturen

- statisches hashing
seperate chaining, linear probing, double hashing
- dynamisches hashing
linear hashing, extendible hashing, bounded index size extensible hashing

Intervallbasierte Datenstrukturen

- eindimensionale Strukturen
- B+ Baum, B* Baum
- k-dimensionale Strukturen (Quadtree als Spezialfall für die 2-dimensionale Struktur)
- k-d tree (Bäume mit k > 1 werden als grid file bezeichnet )
- AVL-Bäume
- digitale Such-Tries

2.2.2 Signature Files und Inverted Files

Im Dokumenten-Retrieval kommen vorwiegend Signature Files und Inverted Files zum Einsatz. Mit dem Verfahren von Signature Files erhält jedes Dokument eine Signatur in Form eines Bit-Strings, die durch Wort-Hashing und überlagertes Kodieren erstellt wird. Um nicht explizit die Begriffshäufigkeit für jedes Wort aufzuzeichnen, werden Wörter mit derselben Häufigkeit in einem Dokument zusammengruppiert und mittels Hashing in das Signature File geschrieben. Zu diesem Verfahren sind einige unterschiedliche Varianten verbreitet. Diese Signaturen werden in separaten Dateien gespeichert und ermöglichen aufgrund ihrer geringeren Größe eine viel schnellere Dokumentensuche. Nachteilig kann sich das Verfahren dann auswirken, wenn das Signature File sehr groß ist, da die Antwortzeit proportional zur Größe steigt.

Inverted Files [Salton und McGill, 1987] ermöglichen ein schnelles Dokumenten-Retrieval. Ein Index, der die relevanten Informationen des Dokuments enthält, wird erstellt und zur Dokumentensuche verwendet. Damit wird nur noch dieser Index und nicht mehr das gesamte Dokument durchsucht. Der Index wird sortiert und aufgrund der veränderten Reihenfolge gegenüber den Originaldokumenten als invertiert bezeichnet. Bei der Aufnahme eines neuen Dokumentes in die Datenstruktur wird jedes Schlüsselwort zusammen mit der Auftrittshäufigkeit in das Inverted File übernommen. Oftmals wird ein Index über dem Index aufgebaut oder es werden zusätzliche Suchalgorithmen eingesetzt, um den Suchprozeß zu beschleunigen. Nachteilig wirkt sich nur der Organisationsaufwand bei Modifikationen aus.

2.3 Verfahren zur Indexierung von Dokumenten

Zu den problematischen Aufgaben im Rahmen des Information Retrievals gehört das Auffinden geeigneter Deskriptoren, die ein Indexieren ermöglichen sollen. In einer Dokumentanalyse müssen Begriffe oder Deskriptoren gefunden werden, die das Dokument gut repräsentieren. Zusätzlich muß jedem Deskriptor ein Wert zugeordnet werden, der die potentielle Bedeutsamkeit für das Retrieval widerspiegelt. Das automatische Indexieren entspricht einer Speicherung der Dokumentverweise in einer Datenbank. H.P. Luhn [Luhn, 1958], ein Pionier der automatischen Indexierung, schreibt in seiner Arbeit über die automatische Erstellung von Abstracts:

„It is here proposed that the frequency of word occurence in an article furnishes a useful measurement of word significance. It is further proposed that the relative position within a sentence of words having give values of significance furnish a measurement for determining the significance of sentences. The significance of a sentence will therefore be based on a combination of these two measurements.“

Die Annahme, daß sich Wort- und Satzschwerpunkte als Schwerpunkte der Bedeutsamkeit interpretieren lassen, ergänzen [Salton und McGill, 1987]:

„Die meisten Ansätze zur automatischen Indexierung bauen auf der Beobachtung auf, daß die Häufigkeit einzelner Worttypen (d.h. einzelner Wörter) in der natürlichen Sprache mit der Bedeutsamkeit dieser Wörter für die inhaltliche Repräsentation korreliert.“

Die Bedeutsamkeit einzelner Wörter kann eruiert werden, indem deren Häufigkeit im Text ermittelt wird und diese danach gereiht werden. Mit Hilfe des Zipfschen Gesetzes läßt sich die Verteilung von Einzelwörtern aus einem Dokument absteigend nach der Häufigkeit ordnen:

Häufigkeit - Rangplatz » Konstant

Dieses Prinzip des geringsten Aufwandes besagt, daß ein Redner oder Schreiber eher dazu neigt, bestimmte Worte zu wiederholen, als ständig nach neuen zu suchen. Im normalen Wortgebrauch können sogar mit 20% der Wörter etwa 70% des Textes abgedeckt werden. Abbildung 2-1 zeigt, daß die Häufigkeit der Wörter am Beginn der Rangreihe stark abnimmt, während sie sich bei seltenen Wörtern nur wenig ändert.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2-1: Graphische Darstellung des Zipfschen Gesetzes

Folgende Vorgehensweise demonstriert ein automatisches Indexierungsverfahren [Salton und McGill, 1987]:

1.) Errechnung der Häufigkeit des Begriffs k im Dokument i (FREQIK).

2.) Errechnung der totalen Häufigkeit TOTALFREQK über alle Dokumente.

Abbildung in dieser Leseprobe nicht enthalten

3.) Sortierung der Begriffe nach abnehmender Häufigkeit mit Hilfe des Zipfschen Gesetzes. Bestimmung eines oberen Schwellwertes. Eliminierung aller Wörter mit einer Häufigkeit über dem Schwellwert.

4.) Eliminierung aller Wörter mit niedriger Häufigkeit durch Bestimmung eines unteren Schwellwertes.

5.) Die resultierenden Wörter mit mittlerer Häufigkeit werden zu Deskriptoren.

Ein anderes Verfahren definiert einen Diskriminanzwert, der die Ähnlichkeit zwischen zwei Dokumenten enthält. Dieser ist 0, wenn überhaupt keine Übereinstimmung vorhanden ist und 1 bei totaler Übereinstimmung. Weiters wird eine Durchschnittsähnlichkeit berechnet, zu der jeder Wert gewichtet wird. Der resultierende Diskriminanzwert multipliziert mit der Häufigkeit FREQIK ergibt ein Deskriptorgewicht jedes Wertes, das eine Art Bedeutsamkeitsfaktor eines Begriffes ist.

2.4 Suchtechniken im Information Retrieval

Die Wahl der richtigen Suchtechnik stellt beim Information Retrieval einen wichtigen Erfolgsfaktor dar. Bei einem Informationssystem, das die gesuchte Information gespeichert hat, sollte diese Information im Idealfall immer gefunden werden können. Da aber in den meisten Informationssystemen Wissen über Objekte verwaltet wird und nicht die Objekte selbst, kann lediglich die Art, wie Objekte im System repräsentiert werden, beeinflußt werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2-2: Benutzerinteraktion in einem Informationssystem

Abbildung 2-2 zeigt, wie wichtig es für eine erfolgreiche Informationssuche ist, daß die Repräsentation der Objekte in einem Informationssystem möglichst der Repräsentation des Informationsbedarfs entspricht [Ferber, 1997]. Die Wissensobjekte werden dem Informationssystem durch einen Informationskanal hinzugefügt. Die Ellipse symbolisiert den Interaktionsmechanismus zwischen den beiden Repräsentationen, der Vergleichs- und Anfrageverfahren beinhaltet. Der Dialog des Benutzers mit dem Informationssystem erfolgt durch seine Repräsentation des Informationsbedarfs, die möglichst exakt der eigentlichen Anfrage entsprechen soll.

Die drei Hauptmodelle der IR-Suchstrategien sind das Boolesche Retrieval, das Vektorraum - und das Probabilistische Retrieval-Modell. Prinzipiell unterscheiden sich die Modelle durch die Art des „match“^[5], wobei das Boolesche Retrieval auf dem „exact match“, die beiden anderen Verfahren auf dem „best“ oder „partial match“ basieren. Im folgenden werden die Verfahren kurz vorgestellt und voneinander abgegrenzt.

2.4.1 Boolesches Retrieval

Boolesche Anfragen an ein Informationssystem verknüpfen Attribut-Paare mittels geeigneter Operatoren (AND, OR, NOT, ...) und führen Mengenoperationen auf Dokumente oder Objekte durch. Das System sucht im invertierten Index jene Dokumente, die den Such- Term an der geforderten Stelle enthalten und dem Booleschen Logik-Operator entsprechen und gibt sie als Resultat aus. Ein Problem des Booleschen Retrievals ist die Schwierigkeit für die potentiellen Benutzer, die komplizierte Anfragesprache zu beherrschen, da derartige Systeme kaum benutzerfreundlich sind. Weitere Nachteile werden von [Fuhr, 1993] darin gesehen, daß zwei wesentliche Eigenschaften des Textretrievals vom Booleschen Retrieval ignoriert werden:

- Textinhalte lassen sich nie wie Datenbankinhalte mit präzisen Attributen abbilden.
- Vage Anfragen lassen sich nur schrittweise präzisieren und führen kaum schnell zu brauchbaren Ergebnissen.

Weitere Nachteile wurden von [Salton und McGill, 1987] erörtert:

- Das Ausgabevolumen ist nicht direkt steuerbar.
- Das System reagiert höchst sensibel auf die Wahl des gesuchten Terms.
- Die Terms werden nicht nach Relevanz gereiht.
- Es werden zwei Dokumentgruppen ermittelt: relevante und nicht relevante.

2.4.2 Fuzzy Retrieval

Die Theorie der Fuzzy Sets [Zadeh, 1965] (siehe Kapitel 6) kann zur Klassifikation von Dokumenten in unscharfe Ähnlichkeitsklassen und zur Steuerung des Retrievalprozesses verwendet werden [Salton und McGill, 1987]. Jedes Dokument wird dazu über eine Fuzzy-Funktion klassifiziert:

Abbildung in dieser Leseprobe nicht enthalten

Das Fuzzy Set-Modell kann als Erweiterung des Booleschen Retrievals gesehen werden, da nicht nur die exakten Werte 0 und 1, sondern auch unscharfe Zugehörigkeitsgrade zwischen 0 und 1 herangezogen werden können. Folgende Boolesche Regeln werden fuzzifiziert:

Abbildung in dieser Leseprobe nicht enthalten

Somit können auch gewichtete Indexierungen durchgeführt werden. Das ermöglicht im Gegensatz zum Booleschen Retrieval eine Reihung der Dokumente. Als nachteilig erläutert [Fuhr, 1993]:

„Die Retrievalqualität ist mangelhaft, verglichen mit dem Vektormodell; zudem bleibt die umständliche Boolesche Formulierung erhalten.“

2.4.3 Vektorraum-Modell

Das Vektorraum-Modell [Ferber, 1997], das einer besseren Unterscheidung der Dokumente dient, arbeitet mit Gewichten und Bedeutsamkeitsfaktoren, die den Deskriptoren zugewiesen werden und als Basis zur Ähnlichkeitsberechnung dienen. Zur näheren Beschreibung werden zwei Dokumente Doki und Dokj mit dem Gewicht TERMik (Deskriptor k des Dokuments i) betrachtet. In einem gewichteten Indexierungssystem können die Werte von TERMik kontinuierlich zwischen 0 und einem bestimmten Maximum verlaufen. Bei t unterschiedlichen Objekteigenschaften ergeben sich folgende Vektoren [Salton und McGill, 1987]:

Abbildung in dieser Leseprobe nicht enthalten

Mit Hilfe von vektoriellen Ähnlichkeitsfunktionen lassen sich nun die Ähnlichkeitskoeffizienten bestimmen. Grundlage der Berechnung ist das Skalarprodukt zwischen Anfrage- und Dokumentenvektor. Da aber statistisch gesehen längere Dokumente häufiger hohe Ähnlichkeitswerte aufweisen können als kurze Dokumente, die sich dann beim Skalarprodukt direkt auf die Retrievalergebnisse auswirken würden, versuchen folgende Maße, dies auszugleichen:

Abbildung in dieser Leseprobe nicht enthalten

Besonders häufig werden der JACCARD- und der COSINUS-Koeffizient eingesetzt. Diese Verfahren besitzen auch eine vergleichbare Wertecharakteristik. Allgemein kann gesagt werden: je höher die Zahl der gemeinsamen Merkmale ist, desto größer sind die Ähnlichkeitskoeffizienten. Aus diesen lassen sich dann sowohl die Dokumentähnlichkeiten als auch die Dokumentunterschiede ableiten.

2.4.4 Probabilistisches Retrieval

Das Gebiet des Information Retrievals umfaßt meist unscharfe Anfragen, bei denen Boolesche Verfahren nur unzureichende Ergebnisse erzielen. Probabilistische Modelle gelten als einer der erfolgreichsten Ansätze zur Behandlung von Unsicherheit. Dazu werden zwei Ansätze unterschieden [Fuhr, 1993]: Der klassische Ansatz basiert auf Relevanz und erfordert vom Benutzer, den Dokumenten relevante Kriterien zuzuweisen. Das Ziel des IRS ist eine möglichst genaue Approximation an die Menge relevanter Dokumente. Van Rijsbergen’s neuer Ansatz hingegen entfernt sich von einer subjektiven Definition einer Antwort in einem IRS und führt zu einer Generalisierung eines Datenbanksystems hinsichtlich unsicherer Inferenz.

Der erste Ansatz basiert auf dem Probability Ranking Principle (PRP), das nur dann ein optimales Retrieval erreicht, wenn alle Dokumente, in Hinblick auf die Anfrage, mit abnehmender Relevanz-Wahrscheinlichkeit gereiht sind [Van Rijsbergen, 1979]. Das führt zur Annahme, daß die Relevanz eines Dokumentes bezüglich einer Anfrage unabhängig von anderen Dokumenten sein soll.

P(Relevanz | Dokument) > P(Non-Relevanz | Dokument)

Im grundlegenden probabilistischen Modell kann jedes Dokument mit Hilfe eines binären Vektors repräsentiert werden, wenn das Dokument Deskriptoren aufweisen kann. Bayes’ Theorem wird zur Berechnung der diskreten Verteilung verwendet und führt zur äquivalenten Entscheidungsregel, da eine Schätzung der Wahrscheinlichkeiten nur schwer möglich ist [Van Rijsbergen, 1979]:

Abbildung in dieser Leseprobe nicht enthalten

Das Relevanz-Feedbackverfahren von Rocchio [Salton und McGill, 1987] beruht auf dieser Entscheidungsregel. Es geht davon aus, daß ein Benutzer am besten anhand relevanter Dokumentmengen entscheiden kann, was er genau sucht. Im ersten Schritt erhält der Benutzer Dokumente, aus denen er die interessantesten für sich auswählt. Daraufhin sucht das System weitere, ähnliche Dokumente und bleibt solange mit dem Benutzer interaktiv, bis dieser es beendet. Ziel ist es, den Bereich der Suchanfrage in Richtung der relevanten Dokumente zu bewegen, um mehr relevante als irrelevante Dokumente auszugeben.

2.5 Typologie von Informationssystemen

Die zur Zeit verwendeten Informationssysteme können in folgende Gruppen unterteilt werden, die im Einzelnen genauer erläutert werden: allgemeine Information Retrieval Systeme, Datenbankmanagementsysteme, Expertensysteme und speziell für Unternehmen entwickelte Systeme wie Management-Informationssysteme oder Entscheidungsunterstützende Systeme. Diese Systeme stellen für jeden Bereich die Basis eines elektronischen Information Retrieval Systems dar und führen zu den heutigen Schlüsseltechnologien Data Warehouse, Data Marts, OLAP und Data Mining.

2.5.1 Information Retrieval Systeme

Ein typisches IR System besteht aus drei Komponenten: Input, Prozessor und Output [Van Rijsbergen, 1979]. Dabei verarbeitet der Prozessor die Systemanfrage und die gespeicherten Dokumente als Input und erzeugt einen Output, der über eine Feedbackfunktion adjustiert werden kann. Dieses grundlegende Modell eines elektronischen IR Systems ist heute noch gültig und in verschiedensten Abweichungen zu finden, wobei jedes dieser Verfahren Informationen unterschiedlich verarbeitet. Ein modernes IR System ( Abbildung 2-3 ) besteht demnach aus den Komponenten Informationserschließung, Query Language (Abfragesprache) und Informationsausgabe oder -aufbereitung.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2-3: Aufbau eines Information Retrieval Systems

Der Teil der Informationserschließung durchsucht die Dokumente nach Merkmalen, die ein Retrieval ermöglichen sollen. Meistens werden den Dokumenten inhaltsbeschreibende Deskriptoren zugeordnet. Mit Hilfe einer Query Language wird das Information Retrieval durchgeführt, das dem Benutzer als Ergebnis die gefundenen Dokumente ausgibt. Nach [Salton und McGill, 1987] entsprechen IR Systeme meist Dokumenten- oder Textretrievalsystemen. Das Textretrieval als wichtigste Form der Informationssuche soll am Beispiel der Dokumentensuche in der Literaturdatenbank INSPEC^[6] vorgestellt werden [Vom Kolke, 1994], [Keitz et al., 1993].

Bei INSPEC wird das Textretrieval mit Hilfe einer künstlichen, Booleschen Abfragesprache durchgeführt. Jedes in der Datenbank erfaßte Dokument wird anhand spezifischer Informationen wie Titel, Autor, Abstract, etc. katalogisiert und in die Literaturdatenbank als Kurzfassung dieser Veröffentlichung eingespeist. Somit ist eine schnelle Suche von mehreren Millionen Dokumenten^[7] möglich, da nicht mehr jedes Dokument durchsucht werden muß, sondern nur mehr ein vergleichsweise kleiner Datensatz, der das Dokument im System repräsentiert.

Ergebnis einer INSPEC-Abfrage:

COPYRIGHT 1994 IEE AN 4712723 Abstract Numbers A9417-0762-003; B9409-7230C-003

TI GaAs/AlGaAs quantum well infrared detectors with an integral silicon grating.

AU Gou-Chung Chi; Cheng Juang CS Optoelectron. & Syst. Labs., ITRI, Hsinchu, Taiwan

JN Japanese Journal of Applied Physics, Part 1 (Regular Papers & Short Notes) (May 1994)

vol.33, no.5A, p.2483-6.

CODEN: JAPNDE ISSN: 0021-4922

DT Journal

TC Experimental

CP Japan

LA English

AB Single quantum well GaAs/AlGaAs infrared photodetectors (QWIPs) with an integral silicon

grating have been fabricated. An enhancement of radiation coupling efficiency over a 45 degrees

bevel device is observed at 77 K. In addition, this technology enables the device to detect

normally incident infrared radiation from the substrate side and makes possible the practical

packaging of detector arrays. (11 refs.)

CT aluminium compounds; electric sensing devices; gallium arsenide; iii-v semiconductors;

infrared detectors; semiconductor quantum wells

UT GaAs/AlGaAs; single quantum well; infrared photodetectors; integral Si grating; radiation

coupling efficiency; detector arrays; semiconductors; 77 K; GaAs-AlGaAs

CC A0762 Detection of radiation (bolometers, photoelectric cells, i.r. and submillimetre waves

detection); B7230C Photodetectors

CI GaAs-AlGaAs/int, AlGaAs/int, GaAs/int, Al/int, As/int, Ga/int, AlGaAs/ss, Al/ss, As/ss,

Ga/ss, GaAs/bin, As/bin, Ga/bin

NI temperature 7.7E+01 K

Quelle: URL(04/1999) http://www.biblio.tu-muenchen.de/bib/inspec.html

Legende:

Abbildung in dieser Leseprobe nicht enthalten

Bei INSPEC basiert die Abfragesprache für eine inhaltliche Suche auf dem Booleschen Retrieval. Dieses exakte Verfahren beruht auf der Suche nach einem oder mehreren gewünschten Terms im genauen Wortlaut und liefert nur dann ein Dokument, wenn alle in der Anfrage formulierten Wörter an der richtigen Stelle im Dokument vorkommen. Dazu werden die drei Grundoperatoren der Booleschen Logik - AND, OR und NOT - verwendet [Salton und McGill, 1987]. Eine Suchanfrage, die alle Dokumente über „Data Mining“ ermitteln soll, die nicht das „Intranet“ behandeln, kann folgendermaßen formuliert werden:

DATA AND MINING NOT INTRANET

Das System schlüsselt die Anfrage mittels folgender Operationen auf:

1) Durchsuche den invertierten Index nach dem Begriff „DATA“; die gefundene Menge wird als Verweismenge #1 bezeichnet
2) Durchsuche den invertierten Index nach dem Begriff „MINING“; die gefundene Menge wird als Verweismenge #2 bezeichnet
3) Die Schnittmenge der Verweismengen #1 und #2 ergibt Verweismenge #3
4) Durchsuche den invertierten Index nach dem Begriff „INTRANET“; die gefundene Menge wird als Verweismenge #4 bezeichnet
5) Lösche alle Verweise in Verweismenge #3, die auch Element der Verweismenge #4 sind
6) Anfrageergebnis = Verweismenge #3

Für eine Literaturdatenbankanfrage werden dem Benutzer noch weitere Operatoren wie „near4“, „in“, etc. zur Verfügung gestellt, um die Anfrage leichter zu präzisieren. Eine derartige Anfrage könnte wie folgt aussehen [Fuhr, 1993]:

Abbildung in dieser Leseprobe nicht enthalten

Diese Beispielrecherche zum Thema „ The side effects of drugs on memory or cognitive abilities, not related to aging“ ist eine Anfrage in 12 Schritten. Es wird bei jedem Schritt versucht, die Anzahl der erhaltenen Records, die anfangs bei 19248 liegt, so zu minimieren, daß möglichst nur die wirklich relevanten Dokumente als Verweismenge übrigbleiben. Es ist dabei sicherlich sinnvoll, die Anfrage so zu formulieren, daß eine vernünftige Anzahl an Verweisen (etwa bis zu 100) ausgegeben wird. Mit der Suchanfrage „DRUGS in TI“ (No.2) werden alle Dokumente gesucht, in denen der Begriff „DRUGS“ im Titel des Dokuments vorkommt.

Als Endergebnis (No.12) findet das System kein einziges Dokument, das diese Boolesche Suchfrage erfüllt, obwohl davon auszugehen ist, daß in der Datenbank mehrere gesuchte Dokumente gespeichert sind. Diese Tatsache ist eines der Hauptprobleme des exakten Booleschen Retrievals. Weitere Schwächen liegen in der fehlenden Benutzerfreundlichkeit der Anfragesprache für den Anwender, und in der Tatsache, daß unvollständig oder leicht fehlerhaft gespeicherte Dokumente durch das System nicht gefunden werden können.

2.5.2 Datenbankmanagementsysteme

In einem elektronischen Informationssystem wird die Sammlung der gespeicherten Informationseinheiten als Datenbank bezeichnet. In einer Faktendatenbank ist jeder Datensatz in Felder unterteilt. Jedes Feld enthält die bestimmten Ausprägungen einer Variable [Salton und McGill, 1987]. Ein Datenbanksystem (DBS) besteht aus einer Datenbank und dem dazugehörenden Datenbankverwaltungssystem, das auch als Datenbankmanagementsystem (DBMS) bezeichnet wird. Das DBS trennt dabei die Datenbank von den Applikationsprogrammen und ermöglicht dadurch Datenschutz, Flexibilität bei Änderungen und Redundanzfreiheit. Ein DBMS führt folgende Funktionen zentral durch [Elmasri und Navathe, 1989]:

- persistente Datenhaltung
- Hintergrundspeicherverwaltung
- Wiederanlaufverfahren
- Mehrbenutzer-Kontrolle
- ad hoc-Abfragen
- Datenschutz

Die Hauptaufgaben eines DBMS bestehen im Speichern, Retrieval, Aktualisieren und Löschen von Daten, dem Schutz der Daten vor Mißbrauch und dem Datentransfer zu anderen Softwaresystemen. Zu den Schwierigkeiten bei der Erstellung eines DBMS gehört die richtige Wahl der Indexdatenstrukturen sowie der physischen Datenorganisation auf dem Datenträger. Da nicht jede Datenstruktur für alle Anwendungen gleich effizient ist, muß das System und dessen Umgebung den jeweiligen Anforderungen angepaßt werden.

Die häufigsten Anwendungen von DBMS stellen Faktendatenbanken dar, die mittels eigener Datenbanksprachen bearbeitet werden können.

Die Bestandteile einer Datenbanksprache (z.B.: SQL-92) sind:

- Datendefinitionssprache
- Sprache zur Definition der physischen Speicherungsstrukturen
- Abfragesprache
- Datenmanipulationssprache

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2-2: Beispiel-Datenbank <Verwaltungsgliederung Kanada>

Quelle: Bertelsmann Lexikon 1998

Auf der Suche nach allen Provinzen bzw. Territorien, die eine größere Fläche als Saskatchewan haben, kann mittels SQL-92 eine einfache Abfrage für Tabelle 2-2 formuliert werden, die exakt die gewünschten Tupel liefert:

Abbildung in dieser Leseprobe nicht enthalten

Resultat:

Abbildung in dieser Leseprobe nicht enthalten

Sollte eine Anfrage an das System aber etwas unpräziser werden, ist eine Lösung mit Hilfe der Booleschen Logik schwierig. Anfragen wie „Welche Provinzen gelten als dicht besiedelt?“ oder „Welche sind die flächenmäßig größten Provinzen?“ machen die Problematik sichtbar. In diesen Fällen können nicht mehr exakt meßbare Daten aus der Datenbank abgerufen werden; es muß eine Form von Wissen extrahiert werden. Dafür müßte beispielsweise ein allgemein gültiger Wert als Schwellwert zwischen dicht besiedelt und nicht dicht besiedelt gefunden werden. Doch da dieser Wert immer nur in Relation zu seinem Umfeld steht, gilt gerade diesem Umfeld das Hauptaugenmerk. Hier ist sicherlich entscheidend, ob als Vergleichswert z.B. das dicht besiedelte Monaco herangezogen werden sollte, oder vielleicht die menschenleeren North Western Territories. Dies führt zwangsläufig zu einer gewissen Unschärfe, die nicht mehr mit Boolescher Logik behandelt werden kann, sondern den Einsatz spezieller Verfahren wie Fuzzy Logic, Genetische Algorithmen, Neuronale Netze oder Rough Sets erfordert. Ziel dieser Methoden ist vor allem die Übertragung menschlicher Unschärfe auf den „perfekt und exakt“ arbeitenden Rechner, um zu einer optimaleren Lösung zu gelangen.

2.5.3 Expertensysteme

Wenn einem System Informationen vorliegen, aus denen für jede Anfrage neues Wissen generiert wird, spricht man von Expertensystemen. Diese wissensbasierten Systeme^[8] sind ein Teilgebiet der Künstlichen Intelligenz (AI) und finden beispielsweise Anwendung in der medizinischen Ferndiagnose, bei Schachprogrammen oder auch bei einem trivialen Zugauskunftssystem, das dem Benutzer Zugverbindungen für bestimmte Strecken liefert. All diesen Systemen liegt zugrunde, daß das Computerprogramm das Urteilsvermögen und Verhalten eines menschlichen Experten oder einer Organisation mit Expertenwissen simuliert. Typischerweise enthält das System eine Wissensbasis, in der Erfahrung integriert ist, sowie Regelbasen, mit deren Hilfe die entsprechenden Regeln für den Zugriff auf die Wissensbasis definiert sind [Winkelmann, 1991]. Das integrierte Wissen sollte aus einem eng begrenzten Gebiet stammen, darüber hinaus problembezogen, sowie leicht zu ändern und zu verarbeiten sein. Daraus werden Schlüsse gezogen, entweder algorithmisch oder heuristisch, die dann im Dialog mit dem Benutzer oder unter Bezug auf konkrete Falldaten durch das Expertensystem erklärt werden [Lusti, 1990]. Die allgemeine Architektur eines typischen Expertensystems illustriert Abbildung 2-4.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2-4: Architektur eines typischen Expertensystems

Deep Blue als Beispiel eines leistungsfähigen Expertensystems:

Mit dem von IBM entwickelten System Deep Blue^[9] [Ibm, 1998] wurde erstmals mit einem Schachcomputer erreicht, daß ein Expertensystem den Weltmeister Kasparow^[10] und damit einen menschlichen Experten besiegte. Ein Sieg war in diesem Fall nicht durch die vergleichsweise überragende Rechnerleistung möglich, sondern vorwiegend durch das zugrundeliegende Expertensystem, das die verschiedenen Spielvarianten, Strategien und Taktiken der Großmeister als Expertenwissen zur Verfügung stehen hatte. Auch dieser Computer „denkt“ daher nicht selbst, sondern ermittelt nur in analytischer Denkweise - angelehnt an menschliche Experten - den rational besten Zug der jeweiligen Spielsituation. Als Kasparow im Jahr zuvor noch über Deep Blue triumphierte, weil er mitten im Spiel seine Strategie so grundlegend änderte, daß das System auf diese scheinbar widersinnige Irrationalität keine Antwort wußte und geschlagen werden konnte, implementierten die Entwickler auch dieses „Zusatzwissen“ und konstruierten damit das erfolgreiche Nachfolgemodell, das Kasparow am 11. Mai 1997 im alles entscheidenden sechsten Spiel besiegte.

2.5.3.1 Werkzeuge für Expertensysteme

Als erste symbolverarbeitende Programmiersprachen für Expertensysteme wurden LISP (LIS t P rocessing language) und PROLOG (PRO grammieren in LOG ik) entwickelt. LISP ist eine funktionale Programmiersprache mit dem grundlegenden Datentyp Liste, dessen Stärke weniger im Bereich der numerischen Manipulation als in der Symbolmanipulation liegt. PROLOG wurde als Sprache der formalen Logik entwickelt, die Problemstellungen intelligent verarbeitet. Setzt man voraus, daß intelligentes Verhalten einen Lösungsweg aus der Problemstellung heraus ableiten kann, sollte eine detaillierte Zustandsbeschreibung und implizites Wissen über mögliche Lösungswege ausreichen, um zu einer Lösung zu gelangen. Mit Hilfe der Aussagen- und Prädikatenlogik sowie der mathematischen Logik werden Zustandsbeschreibungen als Fakten und Regeln in PROLOG abgebildet. Zuerst werden diese Regeln vom Interpreter verarbeitet. Das System wartet dann auf eine Anfrage und versucht, diese Systemanfrage mit den definierten Regeln zu beweisen, um zu einer Antwort zu gelangen. Das folgende Beispiel implementiert einen Stammbaum in PROLOG und demonstriert die Funktionsweise eines einfachen Expertensystems [Shapiro und Sterling, 1994], [Clocksin und Mellish, 1990].

Abbildung in dieser Leseprobe nicht enthalten

Die natürlichsprachigen Zustandsbeschreibungen wie „Ernst ist der Vater von Erika“ werden als Fakten in das System aufgenommen. Als Faktum bezeichnet man eine wahre Aussage innerhalb eines konkreten Bezugsrahmens. Ein Prädikat (z.B. „Vater“) ist die Beschreibung eines Sachverhalts, das Boolesche Funktionen darstellt, die für diesen Fall wahr sind und für alle übrigen Fälle falsch (nicht beweisbar). Die Regeln sind Vorschriften, nach denen PROLOG prüft, ob sich Aussagen als Fakten aus der Wissensbasis ableiten lassen.

Abbildung in dieser Leseprobe nicht enthalten

Zu der Beispielanfrage nach den Enkeln von Tanja liefert das System die einzige Lösung „Christian“. In der Praxis werden heute zunehmend Shells und Toolkits verwendet. Eine Shell ermöglicht dem Benutzer eine leere Wissensbasis und eine möglichst allgemeine Problemlösungs- und Erklärungskomponente, die eine Kommunikationsschnittstelle mit dem Anwender darstellt [Lusti, 1990]. Damit wird ein flexibles Expertensystem bereitgestellt, das empirische Versuche leicht realisieren läßt. Toolkits hingegen bieten mehr Methoden als Shells, doch sind sie viel komplexer und ressourcenintensiver. Ein großer Vorteil sind die Systemschnittstellen zu anderer Software, die es den Toolkits ermöglichen, auch konventionelle Programmiersprachen einzubeziehen.

2.5.4 Weitere Informationssysteme

Management-Informationssysteme (MIS) bzw. Executive Information Systems (EIS) und Entscheidungsunterstützende Systeme (Decision Support Systems - DSS) werden von [Salton und McGill, 1987] als weitere Informationssysteme gesehen. Diese Systeme werden aber eher durch die Art der Präsentation der Inhalte des Systems charakterisiert und nicht als eigenständige Modelle betrachtet. [Ferber, 1997]. MIS sind der übergeordnete Terminus eines Computersystems, das im Unternehmen Informationen über die gewöhnliche Geschäftstätigkeit zur Verfügung stellt. MIS sind eng verbunden mit den jeweiligen Abteilungen und liefern Informationen für die funktionalen Einheiten im Unternehmen [Meta Group, 1998]. Oftmals ist in größeren Unternehmen diese Computerunterstützung durch eine eigene MIS-Abteilung zentral in die Organisation eingebunden und arbeitet auf Basis von Mainframe-Systemen oder über das Corporate Intranet (siehe Kapitel 5). Typische MIS-Anwendungen sind etwa Verkaufs-, Bestands- oder andere Daten, die den Manager mit unternehmensspezifischen Informationen versorgen, aus denen er leicht für seine Abteilung nützliches Wissen ableiten kann und damit bessere und schnellere Entscheidungen fällen kann.

In der Führungsebene der Unternehmen sind Executive Information Systems (EIS) zu finden, die analog zu MIS arbeiten. Die Daten werden dazu aggregiert und bieten der Unternehmensführung eine abstrakte Sicht auf die einzelnen Abteilungen. EIS und MIS sind gleichartige Systeme im automatischen Berichtswesen eines Unternehmens, die sich nur durch die Anwendergruppen unterscheiden. Sie bilden mit anderen Systemen die Basis für Data Warehouse Konzepte.

Die Verwendung von Entscheidungsunterstützenden Systemen (DSS) im Unternehmen dient grundsätzlich der grafischen Präsentation von Informationen und unterstützt die Führungsebene bei geschäftlichen Entscheidungen. Ein DS-System analysiert die Geschäftsdaten und visualisiert diese beispielsweise in Form von vergleichenden Grafiken. Zusätzlich kommen in vielen Bereichen Verfahren der Künstlichen Intelligenz (vorwiegend wissensbasierte Systeme) zum Einsatz.

Die zukunftsweisende OLAP-Funktionalität eines Data Warehouse, die im Kapitel 4 näher betrachtet wird, ist eine praxisnahe, leistungsstarke Weiterentwicklung von MIS, EIS und DSS und bildet die Basis für viele Entscheidungsfindungsprozesse in heutigen Unternehmen.

3 Der Einsatz von Information

Information ist zu einem wesentlichen Bestandteil unserer Gesellschaft geworden. In nahezu jedem Bereich entscheidet Information über Erfolg oder Mißerfolg. Mit der Entwicklung der elektronischen Datenverarbeitung und besonders der globalen Vernetzung durch das Internet hat Information einen noch größeren Stellenwert als vor wenigen Jahren.

Früher gab es nur unvollständige Informationssammlungen, die zudem wenig relevante Informationen enthielten. Das Problem der Informationsbeschaffung stand im Vordergrund. Oftmals existierte die gewünschte Information überhaupt nicht oder es konnte nur mühsam darauf zugegriffen werden. In der heutigen Zeit aber erleben wir eine umgekehrte Entwicklung. Information ist im allgemeinen zur Genüge vorhanden, da sie in fast allen Bereichen kostengünstig gesammelt und archiviert werden kann. Das Problem aber stellt die Wissensgewinnung aus der täglichen Informationsflut und die damit verbundene Umsetzung in konkrete Aktionen dar. Erst durch den Einsatz intelligenter Technologien können die unüberschaubaren Informationsmengen analysiert werden und damit den Aufwand der mit der Informationsgewinnung verbundenen Prozesse rechtfertigen.

3.1 Internet - Entwicklung und Wachstum

Im Jahre 1957, als die Sowjetunion den ersten künstlichen Satelliten Sputnik in den Weltraum schoß, ließ Präsident Dwight D. Eisenhower die Advanced Research Projects Agency (ARPA)^[11] errichten, die 18 Monate später den ersten amerikanischen Satelliten konstruierte. Daraus entwickelte sich 1962 das wichtigste Projekt, das ARPANET. Im selben Jahr veröffentlichte die RAND Corporation^[12] einen Report, der die Errichtung eines Kommunikationsnetzwerkes empfahl [Kyas, 1997]. Dieses sollte nicht zentral gesteuert sein und auch nach einem nuklearen Schlag, der Großteile des Netzes zerstören könnte, noch immer in der Lage sein, Informationen im Netz weiterzuleiten. Selbst nach der Zerstörung einzelner Knoten des Netzes sollte es durch „überlebende“ Knoten funktionsfähig bleiben. Von Anfang an ging man daher von einem unzuverlässigen Kommunikationsnetz mit unsicheren Teilverbindungen aus. Im Oktober 1967 kündigte ARPA den Plan an, 16 Forschungsgruppen großer amerikanischer Universitäten und Forschungszentren durch ein Computernetzwerk zu verbinden. Zwei Jahre später, im Herbst 1969, konnte von der beauftragten Gruppe BBN (Bolt, Beranek und Newman) eine telnet^[13] -ähnliche Verbindung zwischen zwei Host Computern (Honeywell 516 mit 12 KB Hauptspeicher) hergestellt werden. Bis 1971 wurden 15 Hosts ins Netz eingebunden, danach stieg die Zahl der Hosts von 35 (Januar 1973) auf 111 (1977). Nach der Einführung des Standardprotokolls TCP/IP^[14] (1974), wurde das im ARPANET verwendete NCP (N etwork C ontrol P rotocol) abgelöst und das ARPANET dadurch plattformunabhängig. In der Folge wurden die Kosten des Anschlusses an das Internet immer günstiger und ließen dieses neue Medium und die damit verbundenen Dienste stark wachsen. Das Europäische Kernforschungszentrum CERN^[15] entwickelte einen Browser^[16] und einen Netzserver, der für die Verteilung von Informationen unter den Physikern entwickelt wurde. Die besondere Fähigkeit des Browsers war die Eigenschaft, Informationserkundung mit Hypertext-Techniken visuell ansprechbar zu kombinieren. Durch die Entwicklung des Mosaic Browsers wurde das Internet auch bei der breiten Masse schlagartig populär und ließ das World-Wide-Web (WWW) enorm wachsen. Abbildung 3-1 zeigt das globale Wachstum des Internets seit 1993. Die statistischen Daten stammen vom Internet Domain Survey der Firma Network Wizards^[17]. Jedes Jahr erreicht das absolute Wachstum neue Rekordhöhen, das relative Wachstum hingegen wird wohl kaum wieder Wachstumswerte von über 100% p.a. wie zwischen 1995 und 1996 erreichen. Heute beträgt der tägliche Datenfluß der Dienste im Internet etwa 6 Billiarden Megabytes und steigt derzeit monatlich zwischen 10% und 20%. Nach einer aktuellen Schätzung, die 2,5 Menschen pro Host kalkuliert, benutzen derzeit etwa 92 Millionen Menschen das Internet, doch ist diese Zahl mit Vorsicht zu betrachten, da weder die Zahl der Hosts noch die durchschnittliche Zahl der Anwender einer repräsentativen Studie zugrundegelegt werden kann.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3-1: Globaler Wachstum des Internets

Im privaten Bereich sind e-mails, newsgroups und Web-Seiten die häufigsten Anwendungen im Internet, das vorwiegend als Informationsquelle und Kommunikationsmedium verwendet wird. Auf kommerzieller Seite dient das Internet insbesondere der nationalen und internationalen Präsentation von Firmen, dem Online-Support und immer mehr auch Bereichen des Internet Commerce. Das Internet wird nicht mehr allein als Informationsmedium zur schnellen Kommunikation verwendet, sondern in vielen Bereichen des Alltags eingesetzt. Die Entwicklungen der vergangenen Jahre haben gezeigt, daß größere Firmen, die nicht im Netz vertreten sind, mit Wettbewerbsnachteilen konfrontiert sind. Die Anwendungen erstrecken sich von Internetshopping bis hin zu Homebanking.

Damit steht auch die Sicherheitsfrage immer mehr im Vordergrund. Es ist allgemein bekannt, daß ein Netz mit Verbindungen zur Außenwelt nie gänzlich gegen Hacker abgeschirmt werden kann. Die Sicherheitsbarrieren können schwierig bis scheinbar unüberwindbar sein, doch ist die Schwachstelle in jedem System, daß von externer Seite eine Verbindung zum Computer hergestellt werden kann. Dieses Problem gibt es bei jeder Datenfernübertragung, da Daten abgefangen und entschlüsselt werden können. Neueste Sicherheitsstandards wie beispielsweise die Secure Socket Layer- 128-Bit-Technologie (SSL) verwenden 2128 Schlüssel und scheinen aus heutiger Sicht sicher zu sein, doch kann das Risiko eines Datendiebstahls nie gänzlich ausgeschlossen werden.

Auch im Information Retrieval spielt das Thema Sicherheit eine wichtige Rolle. Zum einen muß gewährleistet sein, daß auf viele Datenbestände schnell zugegriffen werden kann, zum anderen sollte ein System einem Eindringling keinesfalls ermöglichen, Sicherheitsstandards zu umgehen und so Zutritt zu den Daten zu bekommen. Ein unsicheres Netz bietet die schnellsten Zugriffs- und Übertragungszeiten; ein sicheres Netz hingegen blockiert mit Hilfe von Sicherheitsvorkehrungen den Datenfluß. Somit ist jede vernetzte Information Retrieval-Lösung ein Kompromiß aus Sicherheit und Effizienz. In dieser Arbeit wird aber vorwiegend auf die Verfahren der Informationsgewinnung eingegangen; sicherheitstechnische Aspekte bleiben weitgehend unberücksichtigt.

3.2 Information Overload

3.2.1 Information Overload im Unternehmen

Abbildung 3-2: Prozeß der Wissensgenerierung

Abbildung in dieser Leseprobe nicht enthalten

Der Informationsüberschuß, der unter der Bezeichnung Information Overload bekannt geworden ist, steht häufig nur für eine Datenlawine und kann meist als Data Overload bezeichnet werden [Meta Group, 1998]. Es ist daher wichtig, zwischen Daten und Informationen zu unterscheiden: Daten sind grundlegend betrachtet nur einfache Werte, die erst im Kontext oder unter besonderer Sichtweise zu Informationen und dann in Folge zu Wissen werden können ( Abbildung 3-2 ).

Das folgende Beispiel aus dem Bereich Warenhandel demonstriert, wie wichtig die Verwendung innovativer Technologien für das tägliche Geschäft ist:

Im heutigen Einzelhandel werden an der Kasse großteils optische Scannersysteme eingesetzt, die einen Artikel anhand des Barcode erfassen und in der Verkaufsdatenbank speichern. Diese Scannerdaten enthalten z.B. den Artikelcode, den Preis, die Warengruppe und die Verkaufszeit. Abgesehen von einer elektronischen Unterstützung bei der Preisauszeichnung bzw. zur Optimierung des Lagerwesens enthalten die enormen Datenmengen wertvolle Geschäftsinformationen, die aber erst durch eine Analyse der Daten in einem bestimmten Kontext extrahiert werden können. Da ein Mensch nicht mehr in der Lage ist, Datenbestände dieser Größenordnung ohne elektronische Unterstützung zu verarbeiten oder zu analysieren, kommen Verfahren des Data Mining (siehe Kapitel 5) zum Einsatz. Programme, wie beispielsweise SCAN*PRO oder BASKET von Nielsen^[18], extrahieren das versteckte Wissen aus den Datenbanken und ermöglichen eine Umsetzung in marketingpolitische Maßnahmen. Mit Hilfe dieser Warenkorb- und Warenverbundanalysen können z.B. Werbekampagnen auf Effektivität überprüft, die Sortimentspolitik optimiert oder das Angebot besser auf die Zielgruppen abgestimmt werden. Die Supermarktkette WAL-MART^[19], die zur Zeit täglich 25 Millionen Scannerdaten mit hohen Kosten sammelt, erhält durch diese Analyse- und Visualisierungsverfahren wertvolle Informationen zur Geschäftsoptimierung und Konkurrenzfähigkeit.

Als vor 40 Jahren ein Kaufmann bescheidene Umsätze machte und seine Kundschaft meist persönlich kannte, wurden Entscheidungen dieser Art intuitiv durchgeführt. Abhängig von den kaufmännischen Fähigkeiten konnten gute Erfolge erzielt werden. Der Kaufmann wußte meist, welche Artikel zusammen gekauft wurden und wie sich seine verschiedenen Zielgruppen unterschieden. In der heutigen Zeit werden zwar noch immer intuitive oder langerprobte Methoden in der Geschäftspolitik verwendet, doch können die Ergebnisse selbst im kleinen Rahmen eklatant gesteigert werden, wenn Daten gesammelt und ausgewertet werden. Die Kosten einer Systeminstallierung scheinen dabei auf den ersten Blick sehr hoch zu sein, doch kann ein Unternehmen vom richtigen Einsatz informationsverarbeitender Instrumente fast immer profitieren. In Kapitel 4 (Data Warehouse) wird auf die Möglichkeiten, wie ein Unternehmen gerade aus dem scheinbar problematischen Information Overload Nutzen ziehen kann, eingegangen.

3.2.2 Vom Information Retrieval zum Information Overload

Der Information Overload ist im Information Retrieval ein nicht zu unterschätzendes Problem. Häufig kommt es vor, daß IR Systeme auf Anfragen sehr viele Informationen liefern, die nur wenig oder geringfügige Relevanz aufweisen. Der Benutzer kann dann aus dieser Menge die für ihn relevanten Informationen auswählen. Dies ist keine leichte Aufgabe, da es oftmals überhaupt nicht möglich ist, zu erkennen, ob eine Information wirklich relevant ist.

Literaturdatenbanken liefern beispielsweise sehr schnell ein umfassendes Ergebnis auf eine Anfrage nach Artikeln zu einem bestimmten Thema, doch läßt sich die Relevanz oft nur anhand der Abstracts erkennen. Das eigentliche Problem zeigt sich erst dann, wenn das gewünschte Buch gar nicht oder nur auf sehr umständlichem Wege verfügbar ist. Nach [Van Rijsbergen, 1979] kann das beschriebene Problem in vielen Formen auftreten. Literaturlisten sind nur dann brauchbar, wenn auch auf die zugrundeliegenden Bücher oder Artikel sofort zugegriffen werden kann und diese Dokumente nicht nur nach langer Wartezeit oder unter immensen Kosten erhältlich sind. Es ist daher sehr wichtig, die wirklich relevanten Dokumente schnell und effizient aus der Menge der wahrscheinlich relevanten Dokumente zu filtern.

[...]

---

^[1] Information Retrieval = dt. etwa: Informationsabruf

^[2] „Information Retrieval Systems: Characteristics, Testing and Evaluation“

^[3] 1 Terabyte (TB) = 1.024 Gigabytes (GB) = 1,048.576 Megabytes (MB)

^[4] 1 Exabyte (EB) = 1.0242 Terabytes = 1,152.921.504.606.850.000 Bytes (=260)

^[5] Ein „match“ ist die Überprüfung von Daten auf Identität. Je nach Grad des „match“ kann von einer bestimmten Übereinstimmung gesprochen werden.

^[6] Beschreibung der Literaturdatenbank im Anhang.

^[7] Heutige Literaturdatenbanken enthalten 105 bis 107 Dokumente.5

^[8] Wissensbasierte Systeme = dt.: Knowledge Based Systems

^[9] Deep Blue ist ein auf der RS/6000 SP2 Supercomputer-Architektur von IBM laufendes Expertensystem, dem Schachstellungen und -züge der letzten 100 Jahre als Grundlage der Berechnung dienen, wobei das System in der Lage ist, etwa 200 Millionen Züge pro Sekunde zu berechnen; Kasparow hingegen kann nur 3 Züge pro Sekunde untersuchen.

^[10] Schachweltmeister seit 1985

^[11] ARPA steht für eine Abteilung des US Department of Defense, das für die Entwicklung neuer Technologien verantwortlich ist.

^[12] Rand Corporation steht für Research and Development im US Militär-Komplex - eine Art „Denkfabrik“ in Kalifornien.

^[13] Protokoll zur Terminalemulation bei der Kommunikation zweier Computer über Telefon/Internet.

^[14] T ransmission C ontrol P rotocol / I nternet P rotocol

^[15] „ C onseil E uropéen pour la R echerche N ucléaire“ in Genf

^[16] Programm zur multimedialen Darstellung von Informationen.

^[17] URL http://nw.com

^[18] Führendes Global Market Research-Unternehmen, URL: http://acnielsen.com/

^[19] URL: http://www.wal-mart.com/