Zusammenfassung

In der vorliegenden Arbeit soll mit der Fuzzy-Clusteranalyse eine verallgemeinerte Methode zur Auffindung von Strukturen und Gruppierungen in Daten und somit zur Datenreduktion vorgestellt werden, die gegebene Daten in zusammengeh¨ orige Bereiche - sogenannte Cluster - einteilt. Die Verallgemeinerung zur klassischen Clusteranalyse besteht darin, basierend auf dem von Zadeh 1965 eingef¨ uhrten Begriff der Fuzzy-Menge das System der eindeutigen Zugeh¨ origkeit zu einer Menge bzw. zu einem Cluster dahingehend aufzuweichen, dass auch graduelle Zugeh¨ origkeiten zugelassen und somit fehlerhafte Klassifikationen aufgrund von Unsicherheit in den Daten (St¨ oreffekte/Rauschen) oder nicht eindeutiger Zuordnungsm¨ oglichkeit weitestgehend ausgeschlossen sind. Es werden Methoden zur Bestimmung der Form, Gr¨ oße und Anzahl der aufgrund hochdimensionaler Datenstruktur ex ante meist nicht eindeutig festzulegenden Cluster anhand verschiedener Algorithmen basierend auf der Technik der Bewertungsfunktionen und globaler/lokaler G¨ utemaße besprochen und kritisch evaluiert. Im Kapitel Anwendungen werden diverse Einsatzgebiete der Fuzzy-Clusteranalyse von der digitalen Bild- und Handschrifterkennung bis hin zu strategischem Controlling und Marktsegmentierungs- systemen aufgezeigt und besprochen.

Inhaltsverzeichnis

1  Fuzzy-Clusteranalyse  4

1.1  Grundlagen der Fuzzy-Set-Theorie und Datenanalyse  4

1.2  Clusteranalyse mit Bewertungsfunktion  5

1.3  Der Fuzzy c-Means Algorithmus  9

1.4  Algorithmen h oherer Komplexit at  11

1.5  Cluster-G utemaße  14

1.6  Qualit at der Algorithmen  17

2  Anwendungen  19

2.1  Digitale Bilderkennung  19

2.2  Fuzzy-Szenarienauswahl im strategischen Controlling  20

2.3  Fuzzy-Kundensegmentierung im Finance-Sektor  21

2.4  Handschrifterkennung auf Fuzzy-Regelbasis  23

Literaturverzeichnis   25

3

Kapitel 1

Fuzzy-Clusteranalyse

1.1 Grundlagen der Fuzzy-Set-Theorie und Datenanalyse

Trotz des m¨ achtigen Werkzeugapparates der Wahrscheinlichkeitstheorie konnte man bis weit in die zweite H¨ alfte des 20.Jahrhunderts bei der Formulierung von Modellkonzepten nur gewisse - stochastische - Unsicherheiten ber¨ ucksichtigen, w¨ ahrend Ungenauigkeiten nicht-stochastischen Charakters (intrinsische bzw. informationale Unsch¨ arfe wie z.B. in den Ausdr¨ ucken ‘sportliches Auto‘, ‘vertretbare Kosten‘ oder ‘kreditw¨ urdig‘ 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¨ ur ein beliebiges Objekt x und eine Menge M gilt stets auf der Basis des Cantorschen Mengenbegriffs x ∈ M oder x ∈ M - durchbrochen. Anstatt die Zugeh¨ origkeit scharf festzulegen (’0’ f¨ ur x ∈ M und ’1’ f¨ ur x ∈ M ), wird der Grad der Zugeh¨ origkeit zu der nun unscharf beschriebenen Menge M mit Hilfe einer charakteristischen Funktion µ M geregelt ([5]): µ M : X −→ [0, 1] x −→ µ M (x) ∈ [0, 1] ∀x ∈ X

Je n¨ aher der Wert dieser Funktion bei 1 liegt, desto ausgepr¨ agter der Grad der Zugeh¨ origkeit dieses Elements zu der betrachteten Menge. Damit wird M = {(x, µ M (x)) | x ∈ X}

zu einer unscharfen Menge auf X. Oftmals wird die charakteristische Funktion einer Menge selbst schon als Fuzzy-Menge dieser Menge bezeichnet. Wir ¨ ubernehmen diese

Sprechweise von nun an. Die Menge aller Fuzzy-Mengen von X wird mit F (X) := {µ X | µ X : X −→ [0, 1]}

bezeichnet ([1]). Die Zugeh¨ origkeitswerte h¨ angen stark von der subjektiven Einsch¨ atzung von Individuen sowie der Struktur der Grundmenge X ab. Mit Hilfe dieser Darstellung k¨ onnen nun unscharfe linguistische Beschreibungen der obigen Art in einen mathematisch bearbeitbaren Rahmen eingebettet werden. Eine klassische (scharfe) Menge ˆ M

mit der charakteristischen Funktion

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 Daten- und speziell der Clusteranalyse eingesetzt, mit der wir uns im folgenden besch¨ aftigen werden. Die klassische Datenanalyse vollzieht sich in vier Stufen steigender Komplexit¨ at ([1]): Nach einer einfachen H¨ aufigkeitsanalyse mit Eliminierung von Ausreißern folgt eine qualitative Mustererkennung mit Datengruppierung auf Basis eines ¨ Ahnlichkeitsbegriffs

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. Be-vor wir im n¨ achsten Abschnitt zur Modellierung des Analyseraums ¨ ubergehen, sei an

dieser Stelle noch auf eine wichtige Abgrenzung hingewiesen ([1]): Es k¨ onnen 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¨ uber der klassischen scharfen Clusteranalyse), je gr¨ ober und unzuverl¨ assiger die Daten sind. Wir werden uns im folgenden auf die Analyse scharfer Daten beschr¨ anken.

1.2 Clusteranalyse mit Bewertungsfunktion

Allgemein dient eine Clusteranalyse vorrangig dem Ziel, ein gegebenes Set von Daten in zusammengeh¨ orige Gruppierungen - Cluster - mit folgenden elementaren Eigenschaften einzuteilen ([3]): Homogenit¨ at innerhalb der Cluster und Heterogenit¨ at zwischen den Clustern, d.h. der Grad der ¨ Ahnlichkeit zwischen Daten eines Clusters soll m¨ oglichst

hoch und zwischen Daten verschiedener Cluster m¨ oglichst niedrig sein, wobei dem Begriff der ¨ Ahnlichkeit hier eine entscheidende Bedeutung zukommt. W¨ ahrend intuitiv der euklidische Abstand zwischen zwei vektorwertigen Daten als ¨ Ahnlichkeitsmaß einleuchtend erscheint, muss jedoch auch ber¨ ucksichtigt 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¨ ussen. Dies l¨ aßt den Begriff der ¨ Ahnlichkeit schon in

einem weitaus komplexeren Licht erscheinen als das zun¨ achst der Fall zu sein schien. Aus der Vielzahl von klassischen Verfahren von z.B. der unvollst¨ andigen, ¨ uberlappenden, hierarchischen und Objective-Function-Clusteranalyse widmen wir uns hier der letztgenannten, in der jeder m¨ oglichen Clustereinteilung mit Hilfe einer Bewertungsfunktion (Objective Function) ein G¨ utewert 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¨ onnen, bedarf es noch der Kl¨ arung einiger wesentlicher Grundbegriffe ([1]):

5

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 = 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 A(D, E) := {f | f : X −→ K, X ⊆ D, X = 0, K ⊆ E}

Interpretieren l¨ aßt sich diese formale Darstellung der Datenanalyse wie folgt: Die Be-antwortung einer Fragestellung entspricht der Zuordnung einer Menge gegebener Daten (X) aus einer Grundmenge (D) zu einer Antwort (K) aus der Menge der m¨ oglichen Antworten (E). Einem Ergebnis einer Datenanalyse entspricht allgemein gesprochen somit ein f ∈ A(D, E). Um diese Ergebnisse vergleichen zu k¨ onnen, f¨ uhren wir anhand der Bewertungsfunktion b : A(D, E) −→ IR

eine Maßzahl ein. Ferner sei f¨ ur eine Abbildung W : A(D, E) −→ B

die einem Ergebnis f ∈ A(D, E) einer Datenanalyse einen booleschen Wahrheitswert {wahr, f alsch} zuordnet, die Analysefunktion A : P(D) −→ A(D, E)

zu W definiert, falls gilt

• A(X) : X −→ K, K ∈ E

• W (A(X)) = wahr

wobei P(D) die Potenzmenge von D (die Menge aller Teilmengen von D mit der M¨ achtigkeit | P(D) |= 2 |D| ) bezeichne. Zu einem Datenset X ⊆ D heißt A(X) Analyseergebnis, das durch einen Algorithmus wie wir sp¨ ater 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¨ aten 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¨ uglich W . Beispielsweise kann dies dadurch geschehen, dasjenige Element x ∈ X zu ermitteln, f¨ ur das eine spezielle Bewertungsfunktion den gr¨ oßten bzw. kleinsten Wert annimmt.

Der Vorteil dieser funktionalen Definition des Analyseergebnisses liegt nun in der Aufteilung 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 A k := f −1 (k), k ∈ K {A k | k ∈ K} f¨ ur

eine Klasseneinteilung von X ist, d.h. die (A k ) k∈K bilden eine echte, disjunkte Zerlegung von X der Form

6

Eine Abbildung f : X −→ K ist somit eine Clustereinteilung genau dann, wenn f surjektiv ist (f (X) = K, d.h. f f¨ ullt 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¨ origkeiten, weshalb eine sogenannte Fuzzifizierung (Verrauschung) des Analyseergebnisses bzw. der Menge K, also der ¨ Ubergang von f : X −→ K zu f : X −→ F (K)

betrachtet wird. Analog definiert man dazu mit A F (D, E) := A(D, {F (K) | K ∈ E})

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

und interpretieren f (x)(k) (das doppelte Argument der Funktion r¨ uhrt 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¨ origkeit 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 ¨ ahnlich einem Wahrscheinlichkeitsmaß die Summe der Zugeh¨ origkeiten eines Datums zu allen Clustern auf Eins, w¨ ahrend Bedingung (1.5) verlangt, dass kein leeres Cluster existieren darf. Die Bedingungen (1.4) und (1.5) stellen dabei eine Abschw¨ achung 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¨ origkeiten nicht mehr haltbar ist. Jede probabilistische Clustereinteilung ist damit ¨ ubrigens auch eine possibilistische

Clustereinteilung aber nicht umgekehrt. Letztgenannte Einteilung ist oft dann von Vorteil, wenn es (St¨ or-)Daten gibt, die sich keinem der Cluster eindeutig zuordnen lassen. Damit wird vermieden, dass dennoch einem Datum aufgrund der Normierung (1.4) f¨ alschlicherweise ein hoher Zugeh¨ origkeitswert zu einem der Cluster zugewiesen wird ([3]).

Als G¨ utewert der Zuweisung solcher Zugeh¨ origkeitswerte bzw. des Analyseergebnisses f : X −→ F (K) haben sich Bewertungsfunktionen der folgenden Struktur bew¨ ahrt ([2]):

7