Fuzzy Retrieval - LinkFang.de





Fuzzy Retrieval


Das Fuzzy Retrieval hat sich seit den 1970er Jahren entwickelt. Hier benennt Fuzzy-Information-Retrieval ein Information Retrieval, das auf der Fuzzy-Logik basiert.

Das Fuzzy-IR-Modell

Das Fuzzy-IR-Modell ist zu definieren mit einem Quadrupel [math]\langle T, Q, D, F \rangle[/math], wobei

  • [math]T = \{t_1, t_2 ,\dotsc, t_n\}[/math] eine Menge von Indextermen, die Abfragen und Dokumente beschreiben.
  • [math]Q = \{q_1, q_2 ,\dotsc, q_m\}[/math] eine Menge von Abfragen, die aus Indextermen bestehen. Dabei lassen sich die Indexterme durch logische Operationen AND, OR und NOT verknüpfen.
  • [math]D = \{d_1, d_2,\dotsc, d_k\}[/math] eine Menge von Dokumenten. Jedes [math]d_j \in D, j = 1, 2, \dotsc, k[/math] ist durch [math]\{(t_1, w_{j1}), \dotsc,(t_n, w_{jn})\}[/math] zu repräsentieren, wobei [math]w_{ji} (i = 1,2,\dotsc, n)[/math] die Wichtigkeit von Term [math]t_i[/math] in [math]d_j[/math] darstellt und einen Wert aus dem Intervall [math][0, 1][/math] einnimmt.
  • [math]F[/math] ist eine Rankingfunktion
[math]F\colon D \times Q \to [0, 1][/math],
[math]F(d,q) \in [0, 1][/math].

Der Wert repräsentiert die Ähnlichkeit zwischen dem Dokument [math]d[/math] und der Abfrage [math]q[/math].

Für eine Abfrage gilt Folgendes:

  1. Eine Abfrage [math]q[/math] ist eine wohlgeformte, propositionale Formel.
  2. Ein individueller Indexterm ist eine Abfrage: [math]q = t_i[/math]. Diese Art von Abfrage nennt man Atomabfrage.
  3. Wenn [math]q[/math] eine Abfrage ist, ist [math]\neg q[/math] (die Negation von [math]q[/math]) auch eine Abfrage.
  4. Wenn [math]q[/math] und [math]q'[/math] Abfragen sind, sind [math]q \cup q'[/math]([math]q[/math] oder [math]q'[/math]) und [math]q \cap q'[/math] ([math]q[/math] und [math]q'[/math]) auch Abfragen.

Die Fuzzy-Mengen-Operationen werden wie folgt verwendet:

[math]F(d_j, t_1 \text{ AND } t_2) = \min(w_{j1}, w_{j2})[/math]
[math]F(d_j, t_1 \text{ OR } t_2) = \max(w_{j1}, w_{j2})[/math]
[math]F(d_j, t_1') = 1 - w_{j1}[/math]

Nun wird ein Beispiel zur Verdeutlichung der Anwendung von Fuzzy-IR-Modell genannt. Die Abfrage lautet:

[math]q_1 = \text{Golden AND Silver}[/math]

Es gibt zwei Dokumente:

[math]d_1 = \{(\text{Golden},\, 0{,}4),\, (\text{Silver},\, 0{,}4)\}[/math]
[math]d_2 = \{(\text{Golden},\, 0{,}4),\, (\text{Silver},\, 0{,}7)\}[/math]

Nach der Operation kommt es zum Ergebnis:

[math]F(d_1, t_1 \text{ AND } t_2) = \min(0{,}4,\ 0{,}4) = 0{,}4[/math]
[math]F(d_2, t_1 \text{ AND } t_2) = \min(0{,}4,\ 0{,}7) = 0{,}4[/math]

Die gleichen Resultate bei [math]d_1[/math] und [math]d_2[/math] sagen aus, dass die Ähnlichkeit zwischen [math]d_1[/math] und [math]q_1[/math] mit der zwischen [math]d_2[/math] und [math]q_1[/math] gleich ist. Aber die meisten Leute würden entscheiden, dass [math]d_2[/math] dem [math]q_1[/math] ähnlicher als [math]d_1[/math] wäre. Hier ist das unerwünschte Ergebnis darauf zurückzuführen, dass die Operation nur auf ein Termgewicht Rücksicht nimmt. Zudem beschränken sich die einfachen Fuzzy-Menge-Operationen lediglich auf zwei Terme. Folgend werden zwei entwickelte Fuzzy-Modelle vorgestellt, die beliebig viele Terme evaluieren können. Weiterhin lässt sich ein Parameter als „softness factor“ zur Lösung des obengenannten Problems (des auf ein Gewicht angewiesenen Ergebnisses) in die Modelle einführen

Erweiterte Fuzzy-IR-Modelle

Das Waller-Kraft-Modell

[math]F(d_j, t_1 \text{ AND } \dots \text{ AND } t_n) = (1 - \gamma) \cdot \min\{w_{j1}, \dots, w_{jn}\} + \gamma \cdot \max{w_{j1}, \dots, w_{jn}}[/math], [math]0 \leqq \gamma \leqq 0{,}5[/math];

[math]F(d_j, t_1 \text{ OR } \dots \text{ OR } t_n) = (1 - \gamma) \cdot \min\{w_{j1}, \dots, w_{jn}\} + \gamma \cdot \max\{w_{j1}, \dots, w_{jn}\}[/math], [math]0{,}5 \leqq \gamma \leqq 1[/math].

Das Modell mischt die Operation Maximum mit Minimum und hat bessere Effektivität als beim einfachen Fuzzy-Modell.

Das Paice-Modell

Bei einer AND-Verknüpfung: [math]w_{ji}[/math] der Größe nach in ansteigender Reihenfolge sortiert, d.h. [math]w_{j1} \leqq \dots \leqq w_{jn}[/math]

[math]F(d_j, t_1 \text{ AND } \dots \text{ AND } t_n) = \left[ \sum_{i=1}^n (r^{i-1} \cdots w_{ji}) \right] / \left[ \sum_{i=1}^n r^{i-1} \right][/math], [math]0 \leqq r \leqq 1[/math].

Bei einer OR-Verknüpfung: [math]w_{ji}[/math] der Größe nach in absteigender Reihenfolge sortiert, d.h. [math]w_{j1} \geqq \dots \geqq w_{jn}[/math]

[math]F(d_j, t_1 \text{ OR } \dots \text{ OR } t_n) = \left[ \sum_{i=1}^n (r^{i-1} \cdot w_{ji}) \right] / \left[ \sum_{i=1}^n r^{i-1} \right][/math], [math]0 \leqq r \leqq 1[/math].

Dieses Modell berücksichtigt alle Termgewichte bei der Berechnung der Ähnlichkeit. Aber es verlangt höheren Berechnungsaufwand als beim Waller-Kraft-Modell.

Vergleich

In der folgenden Tabelle werden die Ergebnisse von [math]d_1[/math] und [math]d_2[/math] bei einfachem Fuzzy-IR-Modell, Waller-Kraft-Modell sowie Paice-Modell miteinander verglichen.

[math]q_1 = t_1 \text{ AND } t_2[/math] Einfaches Fuzzy IR-Modell Waller-Kraft-Modell ([math]\gamma = 0{,}3[/math]) Paice-Modell ([math]r = 0{,}3[/math])
[math]d_1 = \left( (t_1,\, 0{,}4),\, (t_2, 0{,}4) \right)[/math] [math]0{,}4[/math] [math](1 - 0{,}3) \cdot 0{,}4 + 0{,}3 \cdot 0{,}4 = 0{,}4[/math] [math](0{,}3^0 \cdot 0{,}4 + 0{,}3^1 \cdot 0{,}4) / (0{,}3^0 + 0{,}3^1) = 0,4[/math]
[math]d_2 = \left( (t_1,\, 0{,}4),\, (t_2, 0{,}7) \right)[/math] [math]0{,}4[/math] [math](1 - 0{,}3) \cdot 0{,}4 + 0{,}3 \cdot 0{,}7 = 0{,}49[/math] [math](0{,}3_0 \cdot 0{,}4 + 0{,}3^1 \cdot 0{,}7) / (0{,}3^0 + 0{,}^1) = 0,47[/math]

Der Ähnlichkeitsgrad zwischen [math]d_1[/math] und [math]q_1[/math] ist bei den drei Modellen gleich, das ist verständlich. Der Unterschied entsteht bei den Ergebnissen von [math]d_2[/math], wobei die veon den zwei erweiterten Modellen größer als das bei einfachem Fuzzy-IR-Modell sind, was eher der Erwartung entspricht. Deswegen kann man sagen, dass die beiden Modelle bessere Effektivität beim Auffinden als das einfache Fuzzy-IR-Modell haben.

Zwar mischt das Waller-Kraft-Modell Maximum mit Minimum, aber es beachtet nur diese zwei Termgewichte, was zum Problem bei Abfragen mit mehr als zwei Termen führen kann. Beispiel:

[math]q_2 = t_1 \text{ OR } t_2 \text{ OR } t_3 \text{ OR } t_4 \text{ OR } t_5[/math]
[math]d_3 = \{(t_1,\, 0{,}1),\, (t_2,\, 0{,}5),\, (t_3,\, 0{,}5),\, (t_4,\, 0{,}5),\, (t_5,\, 0{,}8)\}[/math]
[math]d_4 = \{(t_1,\, 0{,}1),\, (t_2,\, 0{,}2),\, (t_3,\, 0{,}2),\, (t_4,\, 0{,}2),\, (t_5,\, 0{,}8)\}[/math]

Es ist klar, dass der Ähnlichkeitsgrad zwischen [math]d_3[/math] und [math]q_2[/math] größer als der zwischen [math]d_4[/math] und [math]q_2[/math] ist. Aber nach der Gleichung bei Waller-Kraft-Modell werden gleiche Ergebnisse bei [math]d_3[/math] und [math]d_4[/math] berechnet, welcher Wert für den Parameter [math]\gamma[/math] auch bestimmt wird, weil es bei diesem Modell nur auf das [math]\min[/math] und [math]\max[/math]-Termgewicht Rücksicht genommen wird. Somit entsteht das Problem. Im Vergleich dazu ist das Paice-Modell zwar komplexer, aber es berücksichtigt alle Termgewichte bei der Berechnung und vermeidet deswegen dieses Problem.

Die Einführung des Termgewichtes in die Abfrage

Die gerade gezeigten Modelle berücksichtigen keine Gewichte von Termen in Abfrage, wobei alle Terme die gleiche Wichtigkeit in Abfragen haben. Es ist bekannt, dass die Einführung der Gewichte von Termen in die Abfragen die Effektivität des Auffindens verbessern kann. Mit dem Termgewicht wird die Abfrage repräsentiert: [math]q_k = \{(t_1, w_{k1}), \dots, (t_n, w_{kn})\}[/math], [math]w_k \in [0, 1][/math]. Im Retrieval werden die Gewichte von Termen in Abfragen und Dokumenten multipliziert, das heißt

[math]F \bigl(d_j, (t_i,w_{ki}) \bigr) = w_{ji} \cdot w_{ki}[/math].

Eine Abfrage ohne Termgewicht gleicht einer Abfrage, in der die Gewichte von allen Termen „1“ betragen. Ein Term wird weggenommen, wenn dessen Gewicht null ist, das bedeutet, dass der Term keinen Einfluss auf die Abfrage hat.

Obwohl das Waller-Kraft-Modell und das Paice-Modell keine Methode anbieten, die Termgewichte in Abfragen zu evaluieren, hat das P-Norm-Modell Formeln für die Kalkulation der Termgewichte in Abfragen.

Fuzzy-IR-Modell mit Abfrage-Gewichten

Das P-Norm-Modell mit Abfrage-Gewichten[1]

[math]F \bigl(d_j, (t_{q(k)1}, w_{q(k)1}) \text{ AND } \dots \text{ AND } (t_{q(k)n}, w_{q(k)n}) \bigr) = 1 - \left[ \left[ \sum_{i=1}^n (1 - w_{ji})^p \cdot w_{q(k)i}^p \right] / \left[ \sum_{i=1}^n w_{ji}^p \right] \right]^{1/p}[/math], [math]1 \leqq p \lt \infty[/math],

[math]F \bigl(d_j, (t_{q(k)1}, w_{q(k)1}) \text{ OR } \dots \text{ OR } (t_{q(k)n}, w_{q(k)n}) \bigr) = 1 - \left[ \left[ \sum_{i=1}^n w_{ji}^p \cdot w_{q(k)i}^p \right] / \left[ \sum_{i=1}^n w_{ji}^p \right] \right]^{1/p} [/math], [math]1 \leqq p \lt \infty[/math].

Hier ist [math]p[/math] der Parameter und repräsentiert den Grad an Genauigkeit. „1“ bedeutet wenig genau, während [math]\infty[/math] sehr genau heißt.

Term-Relationen

Fuzzy-Term-Relationen bezeichnet man als Fuzzy-Thesauren. Hier bedeutet diese Relation eine Fuzzy-Relation auf einer Fuzzy-Menge, die die Interpretation von einem Fuzzy-Graph hat. Formal wird angenommen: [math]T = \{t_1, t_2, \dotsc, t_m\}[/math] ist eine Menge von Termen und [math]D = \{d_1, d_2, \dotsc, d_n\}[/math] eine Menge von Dokumenten. Eine (allgemeine) Term-Relation wird definiert durch eine Fuzzy-Relation auf [math]T \cup D : R (x, y), x , y \in T \cup D[/math]. (Hier werden Terme und Dokumente in eine gesamte Menge vereinigt, obwohl man es Term-Relation nennt.) Drei Typen der Relationen sind einbezogen:

  1. Eine Relation zwischen zwei Termen, [math]R(t, t'), t, t' \in T[/math],
  2. Eine Relation zwischen zwei Dokumenten, [math]R(d, d'), d, d' \in D[/math],
  3. Eine Relation zwischen einem Term und einem Dokument: [math]R(t, d)[/math] oder [math]R(d, t), t \in T, d \in D[/math].

Die untengenannten Probleme in Term-Relationen werden dann diskutiert:

  1. konkrete Beispiele für Term-Relationen,
  2. Methode von Beschaffung und Bildung der Term-Relationen,
  3. Methode von Verwendung der Term-Relationen in Information Retrieval.

Beispiele für Term-Relationen

Die Thesauren und ihre Fuzzy-Versionen sind typische Beispiele für Term-Relationen, wobei die Fuzzy-Relation [math]R[/math] nicht auf [math]T \cup D[/math], sondern auf [math]T[/math] definiert wird. Verschiedene Typen von Fuzzy-Thesauren werden berücksichtigt. Zum Beispiel sieht Reisinger Fuzzy-Äquivalenz und Fuzzy-ordnende Relationen als natürliche Generalisationen von scharf kategorischen und hierarchischen Relationen an.[2] Tahani erwähnt auch partielle Fuzzy-Ordnung.[3] Redecki schlägt die Verwendung von einer Fuzzy-Äquivalenz-Relation zusammen mit einer Teilmenge der elementaren Terme und einer Termgeneralisationsrelation vor.[4]

In der Forschung von Fuzzy-Thesauren werden symmetrische und unsymmetrische Fuzzy-Relationen sowie Fuzzy-Transitivität beachtet, deren Annahme jedoch zu einem Problem führt, weil man in Realität keine Fuzzy-Transitivität direkt finden kann. Dieses Problem ist durch die Berücksichtigung von Fuzzy-Graphen (ungerichtete Graphen) und Digraphen[5] zu lösen. Angegeben ist eine Fuzzy-Relation [math]R[/math], die nicht transitiv sein muss. Diese Relation lässt sich durch einen Fuzzy-Digraph repräsentieren, und ein „transitive closure“ wird überdacht, [math]R^* = R \cup R_2 \cup \dots \cup R_k \cup \cdots[/math] ([math]R^k = R_{k-1} \circ R[/math], wobei [math]\circ[/math] die [math]\max[/math]-[math]\min[/math]-Komposition impliziert). [math]R^*[/math] bedeutet den Grad von Erreichbarkeit auf dem Digraph, und zwar ist [math]R*(x, y)[/math] der [math]\max[/math]-Wert von [math]\alpha[/math]-Schnitt, wobei [math]x[/math] auf dem scharfen Digraphen von [math]y[/math] aus erreichbar ist.

Die obengenannten Operationen und Eigenschaften von Fuzzy-Relationen werden hier zusammengefasst:

  1. Angegeben sind zwei Fuzzy-Relationen [math]R[/math] und [math]S[/math], die auf [math]T[/math] definiert werden. Die [math]\max[/math]-[math]\min[/math]-Komposition: [math](R \circ S) (x,z) = \max_{y \in T} \min[R(x,y), S(y,z)][/math].
  2. Eine Relation [math]R[/math] auf einer Menge [math]T[/math] wird bezeichnet als
    1. reflexiv, wenn für alle [math]x[/math], [math]x \in T[/math], [math]R(x,x) = 1[/math],
    2. symmetrisch, wenn für alle [math]x[/math] und [math]y[/math], [math]x,y \in T[/math], [math]R(x,y) = R(y,x)[/math],
    3. transitiv, wenn für alle [math]x[/math] und [math]y[/math], [math]x,y \in T[/math], [math]R(x,y) \leqq \max_{z \in T} \min[R(x,z), R(z, y)][/math].

Konstruktion der Term-Relationen

Verschiedene Forschungen behandeln unter unterschiedlichen Annahmen die Methoden von automatischer Konstruktion der Fuzzy-Relation von Termen oder von Dokumenten. Eine typische Methode dafür ist die Verwendung von Dokument-Term-Matrix [math]A = (a_{ij})[/math], wobei [math]a_{ij}[/math] das Gewicht von Term [math]t_j[/math] in dem Dokument [math]d_i[/math] darstellt. Hier wird angenommen: [math]\gamma_j = \sum_i a_{ij} / d_i[/math] ist die Fuzzy-Menge, die dem Term [math]t_j[/math] entspricht. Eine symmetrische Relation [math]R_s(t_j, t_k)[/math] und eine unsymmetrische Relation [math]R_n(t_j, t_k)[/math] sind definiert durch

[math]R_s(t_j, t_k) = \vert \gamma_j \cap \gamma_k \vert / \vert \gamma_j \cap \gamma_k \vert[/math],
[math]R_n(t_j, t_k) = \vert \gamma_j \cap \gamma_k \vert / \vert \gamma_j \vert[/math],

wobei [math]\vert \gamma_j \vert = a_{1j} + a_{2j} + \dots + a_{nj}[/math] die [math]\sum[/math]-Summe ist. Diese Methode basiert auf der Annahme, dass die Bedeutung von den beiden Termen auch ähnlich ist, wenn die zwei Patterns von [math]\gamma_j[/math] und [math]\gamma_k[/math] ähnlich sind. Die Annahme von [math]R_n(t_j, t_k)[/math] ist, dass [math]\gamma_j[/math] eine engere Bedeutung als [math]\gamma_k[/math] hat, wenn [math]\gamma_j[/math] der [math]\gamma_k[/math] inklusive ist.

Verwendung von Term-Relationen in den reellen Zahlen

Es gibt zwei Basismethoden von Verwendung der Term-Relationen in Information Retrieval. Wenn eine Term-Relation als ein Netzwerk ermöglicht wird, in dem die Dokumente Terminalknoten sind und eine Abfrage ein Originalknoten ist, wird das Retrieval durch die Verfolgung vom Netzwerk durchgeführt. Andererseits, wenn eine Term-Relation [math]R[/math] auf [math]T[/math] zusammen mit einer Fuzzy-Relation [math]F(d, t)[/math] und einem Fuzzy-Abfrage-Vektor [math]q = \sum \nolimits _j \frac{w_j}{t_j}[/math] angegeben wird, ist eine einfache Standardmethode für Retrieval der Dokumente die Kalkulation von einer Fuzzy-Menge [math]\delta = F \circ R \circ q[/math] durch die Anwendung von MAX-MIN-Komposition der Fuzzy-Relationen.[6]

Literatur

  • Lee, Joon Ho: Properties of extended Boolean models in information retrieval. In: Croft & Rijsbergen (1994): SIGIR 1994. Seiten 182–190.
  • Miyamoto, Sadaaki: 1989, Two approaches for information retrieval through fuzzy associations IEEE Trans. Syst. Man Cybernet. SMC-19 123-30 — 1990b Fuzzy Sets in Information Retrieval and Cluster Analysis (Dordrecht: Kluwer).
  • Miyamoto, Sadaaki: Information Retrieval. In: Ruspini, Enrique H.; Bonissone, Piero P.; Pedrycz, Witold (eds.): Handbook of fuzzy computation. Bristol, Institute of Physics Publ.1998: F.4.2.
  • Paice, C.P.: Soft evaluation of boolean search queries in information retrieval systems. In: Information Technology: Research and Development, 3 (1), 1984, Seiten 33–42.
  • Panyr, Jiří: Die Theorie der Fuzzy-Mengen und Information-Retrieval-Systeme. In: Nachrichten für Dokumentation 37, 1986. Seiten 163–168.
  • Salton, G.; Fox, E.A.; Wu, H.: Extended boolean information retrieval. In: Communication of the ACM, 26(11), 1983, Seiten 1022–1036.
  • Waller, W.G.; Kraft, D.H.: A mathematical Model for weighted Boolean retrieval systems. In: Information Processing and Management, 15, 1979, Seiten 235–245.

Quellen

  1. Salton et al, 1983
  2. Reisinger, 1974
  3. Tahani, 1976
  4. Redecki, 1976
  5. Miyamoto, 1990b, Seite 30
  6. Miyamoto, 1990b, S. 195.

Kategorien: Fuzzylogik | Dokumentation

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Fuzzy Retrieval (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.