Home Up Mail an Joachim Pimiskern Impressum

Unscharfe Symbole

Joachim Pimiskern, 25.6.2002

Übersicht

Das folgende Verfahren ist ein Nebenprodukt bei der Entwicklung einer verbesserten Suchmaschine. Diese nimmt es dem Anwender ab, logische Junktoren wie UND bzw. ODER eingeben zu müssen. Außerdem ermöglicht sie es, unscharf zu suchen, d.h. der Benutzer kann z.B. "Dach Fenster Kamin Türe Zimmer" eingeben, wenn er Dokumente sucht, die das Wort "Haus" enthalten.

Im Kontext dieses Dokumentes bedeutet Unschärfe nicht, daß ein Wort Tippfehler enthalten oder ein bißchen anders geschrieben sein darf als es im Dokument vorliegt. Vielmehr ist damit gemeint, daß der Anwender die Bedeutung (Semantik) eines Wortes durch andere Worte umschreiben darf.

Semantische Distanz

Das menschliche Gehirn arbeitet assoziativ. Gibt man einen Begriff vor, so erinnert man sich quasi automatisch an weitere, z.B.
  Uhr - Zeit - Jahreszeit - Frühling - Blume - Biene - Insekt - Tier. 

Solche Assoziationsketten kann man als einen Graphen (semantisches Netz) darstellen. Jedes Symbol entspricht einem eindeutigen Knoten und jede Assoziation einer Kante. Man sieht in Anwendungen von semantischen Netzen häufig beschriftete Kanten. Dies spielt hier keine Rolle; die Kanten seien unbeschriftet.

Def.: Die semantische Distanz zweier Symbole ist die minimale Anzahl von Kanten im Graphen, die durchquert werden muß, um von einem Symbol zu einem anderen zu gelangen. Insbesondere hat ein Symbol zu sich selbst die semantische Distanz 0.

Forderungen

F1)
Ein gesuchtes Dokument soll nicht deswegen einen höheren Rang bekommen, weil ein Suchwort mehr als einmal auftaucht. Denn sonst könnte ein Autor eines Dokumentes dessen Rang durch stumpfsinniges Wiederholen von Schlüsselbegriffen aufwerten.
F2)
Haben zwei Suchwörter einer Suchanfrage eine kleine semantische Distanz, (d.h. eine sehr ähnliche Bedeutung), so soll zwischen diesen eher eine ODER-Verknüpfung stehen. Haben sie eine große semantische Distanz, so soll die UND-Verknüpfung angewandt werden, um die Zugehörigkeit eines Dokumentes zu einer Liste von Suchworten zu bewerten.

Beispiel: "Elefant Kuchengabel Kaffeelöffel Rhinozeros" ist so mit Junktoren auszustatten: (Elefant oder Rhinozeros) und (Kuchengabel oder Kaffeelöffel)

Fuzzy-Logik

In der Fuzzy-Logik haben Aussagen einen Wahrheitswert, der nicht nur 0 und 1 umfaßt, sondern auch dazwischen liegen kann, z.B. 0,1 (für "fast falsch") oder für 0,5 ("halb wahr, halb falsch") . Die Funktionen NICHT, UND und ODER werden geeignet erweitert. Für NICHT(x) nimmt man gewöhnlich 1-x, für UND(x,y) das Minimum aus x und y, und für die Oder-Operation ODER(x,y) nimmt man das Maximum aus x und y.

Erweiterung der Fuzzy-Logik auf semantische Netze

Betrachtet man für ein vorgegebenes Startsymbol alle Nachbarsymbole der semantischen Distanz d für d=0, d=1, d=2, usw, bis zu einer gewissen fest vorgegebenen maximalen semantischen Distanz maxD (noch weiter entfernte Symbole bekommen einfach per Definition die semantische Distanz maxD), so kann man die Fuzzy-Ähnlichkeit jedes Symbols zum Startsymbol als (maxD-d)/maxD definieren.

Anmerkung zu maxD: es zeigt sich, daß in der Regel zwischen je zwei Begriffen in einem semantischen Netz zwei Zwischenbegriffe stehen, d.h., in der Praxis kann man für maxD den Wert 3 nehmen.

Jedem Symbol im Graphen wird hierbei eine Zahl zwischen 0 und 1 bzgl. dem Startsymbol zugeordnet. Geht man von zwei (verschiedenen) Startsymbolen aus, so wird jedem Symbol im Graphen ein Paar von Zahlen (a,b) mit a aus [0.0 .. 1.0] und b aus [0.0 .. 1.0] zugeordnet. Nun kann man damit auch Fuzzy-Operationen anwenden, indem man das Minimum (UND-Operation) bzw. das Maximum (ODER-Operation) anwendet.

Beispiel: nehmen wir die Symbole Uhr und Tier in folgendem eindimensionalen semantischen Netz als Startsymbole. maxD sei hier 6. Die Verwendung einer maximalen semantischen Distanz dient lediglich dem Zweck, die Berechnung zu begrenzen, denn man hat evtl. sehr große semantische Netze vorliegen.

  Uhr - Zeit - Jahreszeit - Frühling - Blume - Biene - Insekt - Tier. 

Für die Distanzen bezogen auf Uhr ergeben sich die Distanzen

             | Uhr  | Tier |
  -----------+------+------+
  Uhr        |  0   |  6   |
  Zeit       |  1   |  6   |
  Jahreszeit |  2   |  5   |
  Frühling   |  3   |  4   |
  Blume      |  4   |  3   |
  Biene      |  5   |  2   |
  Insekt     |  6   |  1   |
  Tier       |  6   |  0   |

Dies mit der Formel (maxD-d)/maxD in Fuzzy-Werte umgerechnet:

             | Uhr  | Tier |
  -----------+------+------+
  Uhr        | 1.00 | 0.00 |
  Zeit       | 0.83 | 0.00 |
  Jahreszeit | 0.67 | 0.17 |
  Frühling   | 0.50 | 0.33 |
  Blume      | 0.33 | 0.50 |
  Biene      | 0.17 | 0.67 |
  Insekt     | 0.00 | 0.83 |
  Tier       | 0.00 | 1.00 |

Verwendet man die Minimum-Funktion für das Fuzzy-UND und die Maximum-Funktion für das Fuzzy-ODER, so ergibt sich:

             | Uhr  | Tier | Uhr UND Tier  | Uhr ODER Tier |
  -----------+------+------+---------------+---------------+
  Uhr        | 1.00 | 0.00 |     0.00      |     1.00      |
  Zeit       | 0.83 | 0.00 |     0.00      |     0.83      |
  Jahreszeit | 0.67 | 0.17 |     0.17      |     0.67      |
  Frühling   | 0.50 | 0.33 |     0.33      |     0.50      |
  Blume      | 0.33 | 0.50 |     0.33      |     0.50      |
  Biene      | 0.17 | 0.67 |     0.17      |     0.67      |
  Insekt     | 0.00 | 0.83 |     0.00      |     0.83      |
  Tier       | 0.00 | 1.00 |     0.00      |     1.00      |

Anmerkung: Die NICHT-Funktion wird hier nicht betrachtet. Das Verfahren soll ohne Operatoren wie z.B. 'not' oder '-' auskommen.

Anwendung auf Suchmaschinen

Mit Fuzzy-Logik kann man also Symbolen Zahlenwerte zuordnen. Diese Zahlenwerte sind geeignet, um Dokumente zu bewerten. Eine Methode soll vorgestellt werden, die es ermöglicht, auf die Verwendung von logischen Operatoren zu verzichten. Der Benutzer soll lediglich eine Liste von Suchwörtern eingeben.

Beziehungen zwischen den Suchwörtern und einem Dokument

Bei einer Suchanfrage wird zunächst für jedes der Suchworte eine Liste von Symbolen angelegt, die mit dem Suchwort assoziiert werden. Man beschränkt sich hierbei in der Länge der Liste und auch in der maximalen semantischen Distanz. Zu jedem Symbol in jeder Liste wird die jeweilige semantische Distanz zum Suchwort eingetragen.

Beispiel: Angenommen, der Anwender trägt ins Suchformular ein: Elefant Kuchengabel Kaffeelöffel Rhinozeros

Dann könnte das semantische Netz folgende Assoziationslisten liefern. Die Listenlänge wurde hier absichtlich auf 8 Nachbarn beschränkt. Die maximale semantische Distanz sei hier als 10 vorgegeben.

   Elefant (0)    | Kuchengabel (0) | Kaffeelöffel (0) | Rhinozeros (0)
   ---------------+-----------------+------------------+---------------
   Dickhäuter (1) | Gabel (1)       | Kaffee (1)       | Dickhäuter (1)
   Nilpferd (1)   | Löffel (2)      | Tee (2)          | Elefant (1)
   Nashorn (1)    | Messer (2)      | Teezeremonie (3) | Rüssel (2)
   Rhinozeros (1) | Gabel (2)       | Japan (4)        | Schlauch (3)
   Krokodil (2)   | schneiden (3)   | China (5)        | Feuerwehr (4)
   Nil (2)        | schnitzen (3)   | Peking (6)       | Fahrrad (4)
   Ägypten (3)    | Holz (4)        | Pagode (7)       | Wettrennen (5)
   Afrika (4)     | Bildhauer (5)   | Turm (8)         | Autorennen (6)

Nun werden mit herkömmlichen Suchmaschinen-Methoden Dokumente gesucht, die irgendeines der Symbole in irgendeiner dieser Listen enthalten. Für jedes der Suchworte wird für das betreffende Dokument gemerkt, was die jeweilige minimale semantische Distanz des Dokumentes zum Suchwort ist.

Beispiel: wenn das Dokument die Worte Löffel, Holz und Bildhauer enthält, so ist die Distanz zum zweiten Suchwort = 2, weil Löffel sowohl im Dokument vorkommt als auch den geringsten semantischen Abstand zu Kuchengabel besitzt.

Nehmen wir an, ein Dokument bestünde aus den Worten {Elefant, Tee, Turm, Schlauch}. Es ergeben sich dann folgende semantische Distanzen der Suchworte zum Dokument (dd genannt):

  Suchwort     |  dd  
  -------------+-----
  Elefant      |  0
  Kuchengabel  |  10
  Kaffeelöffel |  2
  Rhinozeros   |  1

Man beachte, daß die Distanz des Dokuments zu Kuchengabel 10 ist, weil keines der mit Kuchengabel assoziierten Symbole im Dokument enthalten ist. Hier wird das (willkürlich gewählte) Maximum eingesetzt.

Auf diese Weise ergeben sich für sämtliche Dokumente jeweils n-Tupel (n ist hier die Anzahl der Suchworte). Diese Tupel kann man nun zum Bilden einer Bewertungszahl (Rang) heranziehen.

Eine einfache Bewertungsmethode

Beispielsweise könnte man alle Komponenten des n-Tupels aufsummieren oder deren Quadrate.

Das wäre aber eine Vorgehensweise, die den Nachteil hätte, daß Suchworte, die einfach nur wiederholt werden, mit zu hoher Gewichtung in die Dokument-Bewertung einfließen.

Ein weiterer Nachteil ist, daß diese Methode nicht Gruppierungen in den Suchworten erkennt.

Nehmen wir als Beispiel die Suchanfrage "Collie Terrier Dackel Pudel Gebäude Wohnung Dach"

Es ist offensichtlich, daß es sich hier um zwei semantische Cluster handelt, nämlich "Collie Terrier Dackel Pudel" und "Gebäude Wohnung Dach". Entsprechend sollten semantische Distanzen zu Mitgliedern der Cluster jeweils nur ein einziges Mal gewertet werden.

Verbesserung der Bewertungsmethode

Eine Möglichkeit, diesem Problem zu begegnen, ist, in der Berechnung der Bewertungszahl eines Dokumentes die paarweise semantische Distanz zwischen den Suchworten zu berücksichtigen. Angenommen, die Suchwörter hießen S1, S2, ... Sn. Wenn man die paarweisen Komponenten der Distanzvektoren aufaddiert, so kann man dies auffassen als die Berechnung von f(S1 op S2) + f(S1 op S3) + ... f(S(n-1 ) op Sn) op ist hier eine fuzzylogische Operation. Diese sollte wegen Forderung F2 abhängen von der der semantischen Distanz der Suchworte untereinander. Das heißt, je näher ein Paar von Suchworten Si und Sj semantisch beieinander liegen, desto ODER-artiger sollte die Operation sein, und je weiter semantisch entfernt die Suchworte liegen, desto UND-artiger sollte die Operation aussehen.

Dies kann erreicht werden, indem man sowohl den ODER- als auch den UND-Wert ausrechnet und dann entsprechend gewichtet.

Ist ds die semantische Distanz zwischen zwei Suchworten in Bezug auf das semantische Netz, so bekommt man einen normierten Wert dn als (maxD - ds)/maxD.

Bei ds = 0 ist dn = 1, bei ds = maxD ist dn = 0. Bei kleinen semantischen Distanzen sollte der ODER-Anteil zur Geltung kommen, bei großen semantischen Distanzen der UND-Anteil. dn ist eine Zahl zwischen 0 und 1.

Für zwei Komponenten des Dokument-Distanz-Vektors dd1 und dd2 ergibt sich der UND-Anteil zu max(dd1,dd2) und der ODER-Anteil zu min(dd1,dd2). Man erinnere sich daran, daß dd1 und dd2 semantische Distanzen eines Dokuments zu zwei Suchworten S1 und S2 darstellen.

Nun müssen wir noch die semantische Distanz der Suchworte untereinander berücksichtigen und entsprechend proportional einen Wert zwischen min(dd1,dd2) und max(dd1,dd2) wählen.

Dokumentbewertung

Um ein Dokument bezüglich einer aus einer unstrukturierten Liste von Suchworten bestehenden Anfrage zu bewerten, bestimme für alle Suchworte die minimalen semantischen Abstände dd1, dd2 ... ddn zum Dokument. Addiere für alle Paare ddi und ddj mit i < j folgenden Ausdruck auf:

  f := max(ddi,ddj) - (maxD - ds)/maxD * (max(ddi,ddj) - min(ddi,ddj))

Das bedeutet: sind zwei Suchworte semantisch weit voneinander entfernt, so ist ds groß und der Term (maxD - ds) / maxD ist nahe bei 0. In diesem Fall zählt die größere Distanzkomponente max(ddi,ddj). Sind die Suchworte semantisch nahe beieinander, so ist (maxD - ds) / maxD nahe bei 1. Dann zählt die kleinere Distanzkomponente min(ddi,ddj).

Nachteile

Dieses Verfahren benötigt ein semantisches Netz. Es muß in der Regel vom Anwender selbst erstellt werden, denn die menschliche Umgangssprache kann durch Zusammensetzung von Teilworten neue Wortschöpfungen aufnehmen.

Beugungen von Worten werden nicht berücksichtigt. Wird zum Beispiel nach dem Begriff "Gans" gesucht und enthält ein Dokument nur das Wort "Gänse", so wird es nicht gefunden. Eine Abhilfemaßnahme ist, beim Einpflegen des Dokuments in die Datenbank zusätzliche Stichworte zu notieren, insbesondere Grundformen von Stichworten. Meist ist Autoren von Dokumenten diese Problematik bewußt und sie sehen von sich aus Stichworte vor - bei HTML z.B. mittels Meta-Tags.

Die Suche nach sehr vielen Suchworten ist sehr rechenaufwendig. Sie läßt sich aber gut parallelisieren. Wenn man z.B. nach Dokumenten im WWW sucht, könnte man mehrere Suchmaschinen zugleich befragen. Oder man könnte, statt mehrere Recherchen hintereinander auszuführen, eine einzige Suchmaschine von mehreren Prozessen aus befragen. In letzterem Fall wird das Problem der Parallelisierung auf die Suchmaschinen verlegt.

Home Up Mail an Joachim Pimiskern Impressum