Fuzzy Clusteranalyse - Funktionsweise und Anwendungsmöglichkeiten

Inhaltsverzeichnis

1 Fuzzy-Clusteranalyse
1.1 Grundlagen der Fuzzy-Set-Theorie und Datenanalyse
1.2 Clusteranalyse mit Bewertungsfunktion
1.3 Der Fuzzy c-Means Algorithmus
1.4 Algorithmen höherer Komplexität
1.5 Cluster-Gütemaße
1.6 Qualität der Algorithmen

2 Anwendungen
2.1 Digitale Bilderkennung
2.2 Fuzzy-Szenarienauswahl im strategischen Controlling
2.3 Fuzzy-Kundensegmentierung im Finance-Sektor
2.4 Handschrifterkennung auf Fuzzy-Regelbasis

Literaturverzeichnis

Kapitel 1

1 Fuzzy-Clusteranalyse

1.1 Grundlagen der Fuzzy-Set-Theorie und Datenanalyse

Trotz des mächtigen Werkzeugapparates der Wahrscheinlichkeitstheorie konnte man bis weit in die zweite Hälfte des 20.Jahrhunderts bei der Formulierung von Modellkonzepten nur gewisse - stochastische - Unsicherheiten berücksichtigen, während Ungenauigkeiten nicht-stochastischen Charakters (intrinsische bzw. informationale Unschärfe wie z.B. in den Ausdrücken ‘sportliches Auto‘, ‘vertretbare Kosten‘ oder ‘kreditwürdig‘ inherent) meist unbefriedigend durch Reduktion auf Mittelwerte integriert wurden. Erst 1965 wurde mit der Vorstellung der Theorie unscharfer Mengen (Fuzzy Sets) durch Zadeh diese Barriere durch eine Verallgemeinerung der zweiwertigen Mengenlogik - für ein beliebiges Objekt x und eine Menge M gilt stets auf der Basis des Cantorschen Mengenbegriffs x ∈ M oder x [Abbildung in dieser Leseprobe nicht enthalten] M - durchbrochen. Anstatt die Zugehörigkeit scharf festzulegen (’0’ für x [Abbildung in dieser Leseprobe nicht enthalten] M und ’1’ für x ∈ M), wird der Grad der Zugehörigkeit zu der nun unscharf beschriebenen Menge M mit Hilfe einer charakteristischen Funktion µ M geregelt ([5]):

Abbildung in dieser Leseprobe nicht enthalten

Je näher der Wert dieser Funktion bei 1 liegt, desto ausgeprägter der Grad der Zugehörigkeit dieses Elements zu der betrachteten Menge. Damit wird

Abbildung in dieser Leseprobe nicht enthalten zu einer unscharfen Menge auf X. Oftmals wird die charakteristische Funktion einer Menge selbst schon als Fuzzy-Menge dieser Menge bezeichnet. Wir übernehmen diese Sprechweise von nun an. Die Menge aller Fuzzy-Mengen von X wird mit

Abbildung in dieser Leseprobe nicht enthalten bezeichnet ([1]). Die Zugehörigkeitswerte hängen stark von der subjektiven Einschätzung von Individuen sowie der Struktur der Grundmenge X ab. Mit Hilfe dieser Darstellung können nun unscharfe linguistische Beschreibungen der obigen Art in einen mathematisch bearbeitbaren Rahmen eingebettet werden. Eine klassische (scharfe) Menge M ˆ mit der charakteristischen Funktion

Abbildung in dieser Leseprobe nicht enthalten wird somit als Spezialfall eines Fuzzy Sets identifiziert.

Aufgrund ihrer guten Eignung zur Handhabung von mit Unsicherheit behafteten Informationen werden Fuzzy-Mengen auch im Bereich der Datenund speziell der Clusteranalyse eingesetzt, mit der wir uns im folgenden beschäftigen werden.

Die klassische Datenanalyse vollzieht sich in vier Stufen steigender Komplexität ([1]): Nach einer einfachen Häufigkeitsanalyse mit Eliminierung von Ausreißern folgt eine qualitative Mustererkennung mit Datengruppierung auf Basis eines A¨ hnlichkeitsbegriffs ohne zugrundeliegendes mathematisches Modell (explorative Datenanalyse). Darauf aufbauend folgen schließlich quantitative Untersuchungen auf Basis mathematischer Modelle mit dem Ziel der Detektion funktionaler Beziehungen zwischen den Daten (z.B. ein linearer Zusammenhang via einer Regressionsanalyse) sowie das Extrahieren von Schlußfolgerungen und die Bewertung selbiger. Die Fuzzy-Clusteranalyse als Teilgebiet der Fuzzy-Datenanalyse deckt im Rahmen dieser Klassifizierung die Stufen zwei (qualitative Mustererkennung) und drei (quantitative Untersuchungen) ab. Bevor wir im nächsten Abschnitt zur Modellierung des Analyseraums übergehen, sei an dieser Stelle noch auf eine wichtige Abgrenzung hingewiesen ([1]): Es können sowohl Fuzzy-Daten (verrauschte Daten) als auch scharfe Daten mit Fuzzy-Techniken wie der Fuzzy-Clusteranalyse untersucht werden. Dabei ist zu beachten, dass sich die Fuzzy- Clusteranalyse umso eher eignet (gegenüber der klassischen scharfen Clusteranalyse), je gröber und unzuverlässiger die Daten sind. Wir werden uns im folgenden auf die Analyse scharfer Daten beschränken.

1.2 Clusteranalyse mit Bewertungsfunktion

Allgemein dient eine Clusteranalyse vorrangig dem Ziel, ein gegebenes Set von Daten in zusammengehörige Gruppierungen - Cluster - mit folgenden elementaren Eigenschaften einzuteilen ([3]): Homogenität innerhalb der Cluster und Heterogenität zwischen den Clustern, d.h. der Grad der A¨ hnlichkeit zwischen Daten eines Clusters soll möglichst hoch und zwischen Daten verschiedener Cluster möglichst niedrig sein, wobei dem Begriff der A¨ hnlichkeit hier eine entscheidende Bedeutung zukommt. Während intuitiv der euklidische Abstand zwischen zwei vektorwertigen Daten als A¨ hnlichkeitsmaß einleuchtend erscheint, muss jedoch auch berücksichtigt werden, dass einzelne Komponenten der Vektoren unterschiedlich stark in ihrer Bedeutung gewichtet sind, Skalierungen angepaßt oder abstrakte Komponenten (z.B. der Familienstand bei einem Datenset von Bankkunden) integriert werden müssen. Dies läßt den Begriff der A¨ hnlichkeit schon in einem weitaus komplexeren Licht erscheinen als das zunächst der Fall zu sein schien.

Aus der Vielzahl von klassischen Verfahren von z.B. der unvollständigen, überlappenden, hierarchischen und Objectiv e- F unction-Clusteranalyse widmen wir uns hier der letztgenannten, in der jeder möglichen Clustereinteilung mit Hilfe einer Bewertungsfunktion (Objective Function) ein Gütewert in Form einer Zahl zugeordnet wird, die ganz im Sinne der Optimierungstheorie zu minimieren sein wird.

Bevor wir nun die zentralen Begriffe wie probabilistische und possibilistische Clustereinteilung und damit charakteristische Eigenschaften eines ersten Algorithmus in Angriff nehmen können, bedarf es noch der Klärung einiger wesentlicher Grundbegriffe ([1]):

Zu einem strukturell mit dem aus der Stochastik bekannten Set (Ω , F) (bestehend aus Wahrscheinlichkeitsraum Ω und σ -Algebra F) verwandten Tupel (D, E) bestehend aus einem Datenraum D [Abbildung in dieser Leseprobe nicht enthalten] = 0 und einem Ergebnisraum E (E ist somit eine Menge von Mengen, die mindestens zwei Elemente enthalten muss) definieren wir als Analyseraum die Menge der Abbildungen von D in E via

Abbildung in dieser Leseprobe nicht enthalten

Interpretieren läßt sich diese formale Darstellung der Datenanalyse wie folgt: Die Beantwortung einer Fragestellung entspricht der Zuordnung einer Menge gegebener Daten (X) aus einer Grundmenge (D) zu einer Antwort (K) aus der Menge der möglichen Antworten (E). Einem Ergebnis einer Datenanalyse entspricht allgemein gesprochen somit ein f ∈ A (D , E). Um diese Ergebnisse vergleichen zu können, führen wir anhand der Bewertungsfunktion

Abbildung in dieser Leseprobe nicht enthalten eine Maßzahl ein. Ferner sei für eine Abbildung

Abbildung in dieser Leseprobe nicht enthalten die einem Ergebnis f ∈ A (D, E) einer Datenanalyse einen booleschen Wahrheitswert { wahr, falsch } zuordnet, die Analysefunktion

Abbildung in dieser Leseprobe nicht enthalten zu W definiert, falls gilt

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten wobei P (D) die Potenzmenge von D (die Menge aller Teilmengen von D mit der Mächtigkeit | P (D) | = [Abbildung in dieser Leseprobe nicht enthalten]) bezeichne. Zu einem Datenset X ⊆ D heißt A (X) Analy- seergebni s, das durch einen Algorithmus wie wir später sehen werden, gewonnen wird. Vor der eigentlichen Datenanalyse hat jedoch eine Strukturanalyse zu erfolgen, bei der u.a. die Bewertungsfunktion b und das Kriterium W festgelegt sowie der Datenraum D und der Ergebnisraum E aufeinander abgestimmt werden, so dass Inkompatibilitäten wie ein zu feines E oder ein zu grobes D vermieden werden. Ist dies sichergestellt, besteht die Aufgabe der Datenanalyse aus der Bestimmung der Analysefunktion A bezüglich W. Beispielsweise kann dies dadurch geschehen, dasjenige Element x ∈ X zu ermitteln, für das eine spezielle Bewertungsfunktion den größten bzw. kleinsten Wert annimmt.

Der Vorteil dieser funktionalen Definition des Analyseergebnisses liegt nun in der Auf- teilung der Daten in gewisse Klassen (Cluster) ([1]): Sei A (D, E) eine Analyseraum wie oben beschrieben, dann heißt f ∈ A (D, E) Clustereinteilung genau dann, wenn die Menge

Abbildung in dieser Leseprobe nicht enthalten eine Klasseneinteilung von X ist, d.h. die (A k) k ∈ K bilden eine echte, disjunkte Zerlegung von X der Form

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Eine Abbildung f: X [Abbildung in dieser Leseprobe nicht enthalten] K ist somit eine Clustereinteilung genau dann, wenn f surjektiv ist (f (X) = K, d.h. f füllt den Bildraum komplett aus) und X und K jeweils mindestens zwei Elemente enthalten.

Wie ausgangs des letzten Abschnitts beschrieben, widmen wir uns hier der Analyse scharfer Daten mit unscharfen Cluster-Zugehörigkeiten, weshalb eine sogenannte Fuzzifizierung (Verrauschung) des Analyseergebnisses bzw. der Menge K, also der U¨ bergang von

Abbildung in dieser Leseprobe nicht enthalten betrachtet wird. Analog definiert man dazu mit

Abbildung in dieser Leseprobe nicht enthalten den entsprechenden Fuzzy-Analyseraum A F (D, E) zu A (D, E). Betrachten wir ferner in Anlehnung an die Wahrscheinlichkeitstheorie folgende Bedingungen ([2])

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten und interpretieren f (x)(k) (das doppelte Argument der Funktion rührt daher, dass das Bild von x unter f, f (x) ∈ F (K) wieder eine Funktion darstellt, die K in [0 , 1] abbildet, also f (x)(k) ∈ [0 , 1]) als Grad der Zugehörigkeit des Datums x ∈ X zum Cluster k ∈ K. Dann nennt man so ein f ∈ A F (D, E) eine possibilistische Clustereinteilung wenn

(1.5) gilt und eine probabilistische Clustereinteilung, wenn sowohl (1.4) als auch (1.5) gelten. Bedingung (1.4) normiert dabei ähnlich einem Wahrscheinlichkeitsmaß die Summe der Zugehörigkeiten eines Datums zu allen Clustern auf Eins, während Bedingung (1.5) verlangt, dass kein leeres Cluster existieren darf. Die Bedingungen (1.4) und (1.5) stellen dabei eine Abschwächung der harten Clustereinteilung (1.1) bis (1.3) dar, was bereits an der Aufgabe der Forderung nach disjunkten Clustern ersichtlich wird, die nach der Fuzzifizierung mit graduellen Zugehörigkeiten nicht mehr haltbar ist. Jede probabilistische Clustereinteilung ist damit übrigens auch eine possibilistische Clustereinteilung aber nicht umgekehrt. Letztgenannte Einteilung ist oft dann von Vorteil, wenn es (Stör-)Daten gibt, die sich keinem der Cluster eindeutig zuordnen lassen. Damit wird vermieden, dass dennoch einem Datum aufgrund der Normierung (1.4) fälschlicherweise ein hoher Zugehörigkeitswert zu einem der Cluster zugewiesen wird ([3]).

Als Gütewert der Zuweisung solcher Zugehörigkeitswerte bzw. des Analyseergebnisses f: X [Abbildung in dieser Leseprobe nicht enthalten] F (K) haben sich Bewertungsfunktionen der folgenden Struktur bewährt ([2]):

Abbildung in dieser Leseprobe nicht enthalten

Die Suche nach einer Bewertungsfunktion reduziert sich somit auf den sogenannten F uzzifier m (Gewichtungsfaktor) und eine geeignete Distanzfunktion d, die den Abstand zwischen Datum x und Cluster k für alle Daten und alle Cluster in die Bewertung einfließen läßt. Diese Distanzfunktion stellt auch den Hauptunterschied zwischen den verschiedenen Algorithmen der folgenden Abschnitte dar. Beim Fuzzy-c-Means- Algorithmus wird für d z.B. der euklidische Abstand gewählt. Klar ist nun auch, dass ein optimales Analyseergebnis eine Bewertungsfunktion dieser Struktur minimiert. Es läßt sich auch zeigen, dass je mehr der Fuzzifier m > 1 sich der Eins nähert, desto schärfer wird die Einteilung und umgekehrt für [Abbildung in dieser Leseprobe nicht enthalten] ([6]):

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Demnach ist folgende Strategie für die Wahl des Parameters m ratsam: Sind die Cluster nahezu ununterscheidbar, ist m groß zu wählen, um die in die Bewertungsfunktion eingehenden modifizierten Zugehörigkeiten zu zwingen, keine hohen Werte anzunehmen. Für klar getrennte Cluster gilt genau der umgekehrte Fall und es ist m = 1 zu wählen. Dies bedarf natürlich eines gewissen Vorwissens, das in den meisten Fällen (vor allem bei höherdimensionalen Daten) nicht vorhanden ist. In diesem Fall ist m = 2 eine sichere Wahl ([2]).

Angenommen, man habe sich um die optimale Clusteranzahl, die u.a. von der Distanzfunktion (1.6) abhängt und deshalb stets individuell zu bestimmen ist, nicht mehr zu kümmern (darauf kommen wir noch zurück), läßt sich durch simple Differentiation zeigen, dass wenn die Bewertungsfunktion (1.6) für alle probabilistischen Clustereinteilungen A F (D , E) ein Minimum bei f: X [Abbildung in dieser Leseprobe nicht enthalten] F (K) annimmt, für die Zugehörigkeitsgrade gilt ([1])

Abbildung in dieser Leseprobe nicht enthalten

Dabei wurde ausgenutzt, dass in der Distanzfunktion selbst keine Zugehörigkeiten der Form g (f (x)(k)) für beliebiges g [Abbildung in dieser Leseprobe nicht enthalten] constan t vorkommen. Falls x zu mehr als einem Cluster den Abstand Null hat, so ist f (x)(k) für diese Cluster nicht eindeutig bestimmt. In diesem Fall ist bei der Implementierung des Algorithmus (bei dem wir das Minimum von dem (1.7) ausgeht erst finden wollen) darauf zu achten, dass sich die Summe der Zugehörigkeiten zu Eins ergbt. Die für eine probabilistische Clustereinteilung notwenige Bedingung (1.5) gilt u.a. dann, wenn es mindestens ein Datum gibt, das zu allen Clustern einen positiven Abstand hat. Bei punktförmigen Clustern ist (1.5) demnach z.B. erfüllt, wenn es mehr Daten als Cluster gibt. Stellt man jedoch fest, dass (1.5) nicht gilt (d.h. es existieren j uneigentliche Cluster mit verschwindender Summe der Zugehörigkeiten aller Daten) so sind diese Cluster zu entfernen und die Analyse mit [Abbildung in dieser Leseprobe nicht enthalten] Clustern erneut zu starten. F¨ur eine possibilistische Clustereinteilung ergibt sich eine einfachere Darstellung der Zugehörigkeiten f(x)(k) als in (1.7) beschrieben ([1]), da eine Nebenbedingung fallen gelassen wird, worauf wir jedoch nicht weiter eingehen, da sie in den weiteren Betrachtungen keine Rolle mehr spielt.

[...]