R. Ferber: Data Mining & Information Retrieval 1.5.5.3

4.5.2: Unscharfe Mengen

Während in Clusterverfahren Teilmengen von ähnlichen Beispielen konstruiert werden, kann man auch versuchen, die Definition von Mengen so zu verallgemeinern, dass vage Zuordnungen von Beispielen in unterschiedliche Teilmengen besser abgebildet werden können. Dazu wurden bereits 1965 von L. A. Zadeh [->] sogenannte unscharfe Mengen oder Fuzzy Sets eingeführt. Die folgende Darstellung orientiert sich an Bademer & Gottwald [->] (1993).

Die Theorie der Fuzzy Sets stellt als eine Verallgemeinerung des Mengenkonzepts den "Grad der Mitgliedschaft in einer Menge" zur Verfügung. Diese Verallgemeinerung wird mit Hilfe einer Zugehörigkeitsfunktion definiert:

4.5.2.1: Fuzzy Set

Bei unscharfen Mengen muss für ein Element also nicht mehr eindeutig gesagt oder bestimmt werden, ob es in einer bestimmten Menge liegt oder nicht, sondern es kann ein Zahlenwert zwischen Null und Eins angegeben werden, der die Zugehörigkeit des Elements zu der Menge beschreibt. Das entspricht der Gewichtung von Termen in der Vektordarstellung eines Dokuments. Dort war allerdings keine Einschränkung der Werte auf das Intervall [0,1] festgelegt worden. Eine solche Einschränkung kann allerdings im Allgemeinen durch eine geeignete Normierung erreicht werden. Dabei müssen aber die Auswirkungen auf die verwendeten Ähnlichkeitsmaße berücksichtigt werden. Andererseits ist die Definition von unscharfen Mengen nicht auf eine endliche Menge von Termen beschränkt. Sie wurde für beliebige Mengen eingeführt.

Die herkömmliche Mengendefinition (oder die Definition einer scharfen Menge) läßt sich als Spezialfall der Definition einer unscharfen Menge schreiben. Dazu wählt man als Zugehörigkeitsfunktion einer Menge UD die charakteristische Funktion:

Das ist das gleiche Vorgehen, wie bei der Beschreibung des Booleschen Retrievals als Spezialfall des Vektorraummodells.

Abb. 62: Unscharfe Mengen als Beschreibung von Lebensaltern

Zwei unscharfe Mengen sind genau dann gleich, wenn ihre Zugehörigkeitsfunktionen gleich sind. Die leere unscharfe Menge ist durch die Zugehörigkeitsfunktion

m_Ø0

gegeben, die Grundmenge D durch

m_D1

Weiter können folgende Begriffe definiert werden:

4.5.2.2: Träger, Kern, Schnitte und Höhe

Zur weiteren Untersuchung der Eigenschaften unscharfer Mengen, bzw. zur weiteren Verallgemeinerung von Eigenschaften scharfer Mengen auf unscharfe Mengen kann man die folgende Aussage benutzen, die eine Beziehung zwischen scharfen und unscharfen Mengen herstellt.

4.5.2.3: Aussage:

Abb. 63: Rekonstruktion des Wertes der Zugehörigkeitsfunktion aus einem a - Schnitt.

Mit dieser Äquivalenz lassen sich Eigenschaften und Operationen von scharfen Mengen auf unscharfe Mengen übertragen. Geht man von der Teilmengenrelation für scharfe Mengen aus, kann man fordern, dass die - Schnitte einer Teilmengenrelation unscharfer Mengen die Teilmengenrelation für scharfe Schnitte erfüllen sollen. Man erhält als Definition also

YX:Y^>=X^>= [0,1]

Aus der rechten Seite kann man eine äquivalente Bedingung für die Zugehörigkeitsfunktionen ableiten: Für ein beliebiges dD setzen wir =m_Y(d) . Dann folgt aus dY^>= dass auch dX^>= gilt und damit m_X(d)>= also m_X(d)>=m_Y(d) dD .

Umgekehrt folgt aus m_X(d)>=m_Y(d) dD nach der Definition des Schnittes X^>=Y^>=

Zusammen gilt also

YXm_Y(d)<=m_X(d) dD

Man kann also für unscharfe Mengen die Teilmengenrelation durch diese Äquivalenz definieren.

Es folgt dann unmittelbar für diese Teilmengenrelation:

ØXD

YX, XYY=X

sowie

YX, XW YW

Wie bei den scharfen Mengen gibt es auch bei unscharfen Mengen verschiedene sinnvolle Maße für die Größe einer Menge, je nachdem ob der Träger endlich, abzählbar oder meßbar ist. Bei endlichem Träger kann man analog zur Anzahl der Elemente einer scharfen Menge die Summe der Werte der Zugehörigkeitsfunktion verwenden.

Bei abzählbarem Träger kann diese Summe (anders als bei der scharfen Menge) endlich sein oder auch nicht. Bei meßbarem, aber nicht endlichem Träger kann man das Integral über die Zugehörigkeitsfunktion als Maß für die Größe der Menge verwenden.

Interessant sind dabei vor allem relative Größenangaben, also Angaben darüber, welchen Anteil der Größe der Grundmenge eine Teilmenge einnimmt. Diese relativen Größenangaben können für die verschiedenen Größenmaße berechnet werden.

4.5.2.4: Vereinigung, Durchschnitt und Komplement

Abb. 64: Vereinigung und Durchschnitt von unscharfen Mengen

Man sieht, dass sich diese Definitionen bei der Verwendung von scharfen Mengen, also von charakteristischen Funktionen, mit den herkömmlichen Definitionen von Vereinigung, Durchschnitt und Komplement decken.

Aus den entsprechenden Eigenschaften der Maximumsfunktion ergeben sich auch sofort

die Kommutativität:
YX=XY
die Assoziativität:
(YX)W=X(YW)
die Idempotenz:
XX=X
und die Monotonie:
YXYWXW

Diese Eigenschaften lassen sich auch für den Durchschnitt zeigen. Entsprechend lassen sich auch Distributivgesetzte und deMorgansche Regeln auf unscharfe Mengen übertragen. Schließlich gilt

(YX)^>=Y^>X^>

und

(YX)^>=Y^>X^>

Neben dieser "kanonischen" Definition von Vereinigung und Durchschnittsbildung gibt es noch weitere Möglichkeiten, solche Operationen zu definieren. Darauf soll hier aber nicht eingegangen werden.

Es soll im folgenden aber noch angedeutet werden, wie Fuzzy Methoden zum unscharfen Schließen bzw. unscharfen Kategorisieren verwendet werden können. Dazu kann man unscharfe Relationen analog zu scharfen Relationen als Teilmengen der entsprechenden kartesischen Produkte definieren:

Eine (scharfe) Relation zwischen zwei Attributen A₁:D->R₁ und A₂:D->R₂ kann als Teilmenge des kartesischen Produkts der Wertemenge der Attribute geschrieben werden.

TR₁×R₂={(x,y) | xR₁,yR₂}

Die Gleichheit zweier Attribute kann damit z. B. als Relation der Form

T={(x,y) | x=y}

geschrieben werden.

Kategorisierungsregeln, wie sie z. B. beim AQ-Algorithmus beschrieben wurden, können auch als Relationen dargestellt werden. Im folgenden beschränken wir uns der Einfachheit halber auf Kategorisierungen, die durch ein vorherzusagendes Attribut A₂ beschrieben sind, und sich nur auf ein vorhersagendes Attribut A₁ stützen. Wie beschrieben, läßt sich ja jede Kategorisierung durch die geeignete Wahl bzw. Konstruktion von A₁ auf diese Aufgabe reduzieren. Sie ist dann eine Funktion, die sich als Regel in der Form

IF (A₁=x) THEN A₂=y

schreiben lässt und als Relation in der Form

{(x,y) | A₁=x,A₂=y}

Die charakteristische Funktion der Gleichheitsrelation auf der Menge der Paare ergibt sich z. B. für R=R₁=R₂={0,1,2} in der Form:

Ein Eintrag t_i,j in dieser Matrix gibt an, ob der Wert x_i der Variablen x und der Wert y_j der Variablen y die Relation erfüllen (1) oder nicht (0). Schreibt man ein Element aus R auch als seine charakteristische Funktion, also z. B. 1R als x=(0,1,0)^t , so ergibt sich die Kategorisierung als Multiplikation der Matrix T mit dem Vektor x . Man kann sie in der Form

IF (A₁=x) THEN A₂=T·x

schreiben oder einfacher als

A₂(x)=T·x

In dieser Weise werden Kategorisierungen beschrieben, solange die Matrix eine Permutationsmatrix ist, d. h. solange in jeder Zeile und in jeder Spalte genau eine 1 steht. Allgemeiner kann man die IF-THEN Regel als eine Verknüpfung der charakteristischen Funktion des Wertes von A₁ mit der Relation betrachten.

Die Darstellung der Relation durch die charakteristische Funktion ermöglicht die Verallgemeinerung der Relation zu einer unscharfen Relation und damit die Definition einer unscharfen Kategorisierung. Während bei der scharfen Relation nur 0 und 1 als Beschreibungen der Zugehörigkeit zulässig sind, sind bei der unscharfen Relation Zugehörigkeiten aus dem Intervall [0,1] erlaubt, z. B:

Eine unscharfe IF-THEN-Regel kann nun mit Hilfe einer unscharfen Relation folgendermaßen geschrieben werden:

IF (A₁=X) THEN A₂=Y

wobei X und Y unscharfe Mengen sind und die Zugehörigkeitsfunktion von Y folgendermaßen definiert ist:

m_Y(y)=sup_{_xR₁}{min(m_X(x),m_T(x,y))} yR₂

Diese von Zadeh vorgeschlagene Definition lehnt sich an das Produkt zwischen dem Vektor und der Matrix an. Die Multiplikation wird dabei durch das Minimum ersetzt und die Addition durch die Supremumsbildung. Das Ergebnis dieser unscharfen Kategorisierung ist eine unscharfe Menge, also eine Zugehörigkeitsfunktion.