Steinmeyer, Simon: Untersuchung und Vergleich von ¨ Ahnlichkeitsmaßen von Fuzzy-Cluster-Strukturen Diplomarbeit, Otto-von-Guericke-Universit¨ at Magdeburg, 2007.

INHALTSVERZEICHNIS i

Inhaltsverzeichnis   

Abbildungsverzeichnis   v

Tabellenverzeichnis vi   

1  Einleitung  1

1.1  Das Sandhaufenparadoxon  1

1.2   

Ahnlichkeitsfunktionen  f ur Fuzzy-Cluster-Strukturen  2

1.3  Gliederung der Arbeit  3

2  Grundlagen  4

2.1  Einf uhrung: Fuzzy-Logik  4

2.1.1  Fuzzifizierung aussagenlogischer Ausdr ucke  5

2.1.2  Verschiedene T-Normen und T-Conormen  6

2.2  Cluster-Analyse  7

2.2.1  Daten ausw ahlen  7

2.2.2  Daten vorbereiten  8

2.2.3  Auswahl eines Clusteralgorithmus  8

2.2.4  K-Means  9

2.2.5  Fuzzy C-Means  10

2.2.6  Wahl der Clusteranzahl  11

3  Entwicklung von  

Ahnlichkeitsma  ßen  13

3.1  Distanzfunktionen und  

Ahnlichkeitsma  ße  13

3.1.1  Definition  13

INHALTSVERZEICHNIS ii

3.1.2  Umwandlung von Distanzfunktionen und  

Ahnlichkeitsma  ße in nor-  

mierte   

Ahnlichkeitsma  ße  14

3.2  Vergleich von Cluster-Partitionen  15

3.2.1  Cluster-Partitionen-Vergleich unter verschiedenen Randbedingungen  15

3.2.2  Gewinnung von Eigenschaftskoeffizienten von Clusterpaaren  17

3.3   

Ahnlichkeitsfunktionen  f ur Clusterpaare  18

3.3.1  Distanzfunktionen als normierte  

Ahnlichkeitsma  ße  23

3.3.2  Skalierung von  

Ahnlichkeitsma  ßen  23

3.3.3  Eigenschaftsbeschr ankungen von Cluster-Partitionen in dieser Arbeit  24

3.4  S-Distanz  25

3.4.1  Formale Eigenschaften  26

3.4.2  Komplexit at  28

3.4.3  Rekursive Anwendung auf Multimengen und Listen  29

3.5  B-Distanz  29

3.5.1  Definition  30

3.5.2  Weitere Implikationsklassen  31

3.5.3   

Ahnlichkeit  zur S-Distanz  32

3.6  -MDistanz  33

3.6.1  Definition  34

3.6.2  Formale Eigenschaften  36

3.6.3  Komplexit at  36

3.7  K-Distanz  37

3.7.1  Definition  37

3.7.2  Geometrische Interpretation  38

3.7.3  Erweiterung der Nichtnegativen kleinste Quadratfehlersummen-  

methode  “  39

3.7.4  Transformation des Abstandproblems  40

3.7.5  Epsilon-Wahl  42

3.7.6  Formale Eigenschaften  43

3.7.7  Komplexit at  44

3.7.8  Varianten  46

INHALTSVERZEICHNIS iii

4  Evaluationstests in k unstlichen Umgebungen  48

4.1  Ring-Methode  48

4.1.1  Auswertung  49

4.2  Semiverifikation der Dreiecksungleichung  53

4.3  Vergleich unterschiedlich großer Cluster mittels Datenpunktzuordnungen  55

4.4  Vergleich unterschiedlich großer Cluster durch Variation der Zugeh orig-  

keitsgrade   59

4.5  Hierarchische Clustermethoden  63

4.5.1  Split-Methode  63

4.5.2  Auswertung  63

5  Fuzzy-Bildklassifikation  66

5.1  Klassifikation mittels  

Ahnlichkeitsma  ßen  66

5.2  Die Bildersammlung  66

5.3  Extraktion von Eigenschaftvektoren eines Bildes  67

5.4  Clusterung der Datenpunkte  68

5.5  Verwendete  

Ahnlichkeitsma  ße  70

5.6  Klassifikationsraten  70

5.7  Auswertung  71

5.7.1  Fest definierte Cluster  72

5.7.2  Fuzzy C-Means mit euklidischen Abstand  73

5.7.3  Fuzzy C-Means mit adaptiertem Abstandmaß  74

6  Bewertung  77

6.1  Bewertung der Ergebnisse  77

6.2  Ausblick  78

Literaturverzeichnis   81

A  Anhang  84

A  1 Beispiele f ur die Verletzung der Dreiecksungleichung  84

Abbildungsverzeichnis

1.1 Sandkornmengen und deren Zugeh¨ origkeit zu verschiedenen Konzepten . 1

2.1 K-Means nach Initialisierung (links) und nach Konvergenz (rechts) . . . . 10

Ahnlichkeitsmaß in der Ebene zum Vektor (1, 1) ^T . . 20 3.1 Normiertes Kosinus- ¨

3.2 Jaccard- ¨ Ahnlichkeitsmaß in der Ebene zum Vektor (1, 1) ^T . . . . . . . . 21

3.3 Zwei Cluster mit gleichen Zugeh¨ origkeitsvektoren und unterschiedlichen Zentren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.4 Entropien der einzelnen Teilmengen und deren Verkn¨ upfungen . . . . . . 35

3.5 K-Distanz: Berechnungszeit in Abh¨ angigkeit von Clusteranzahl und Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.1 Ringmethode: B-Distanz . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.2 Ringmethode: S-Distanz ( M in ) mit Minkowski-Metriken . . . . . . . . . 50

4.3 Ringmethode: S-Distanz ( P rod ) mit Minkowski-Metriken . . . . . . . . . 50

4.4 Ringmethode: S-Distanz( M in ) mit ”

nat¨ urlichen“ ¨ 4.5 Ringmethode: P rod mit ”

4.6 Ringmethode: K-Distanz . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.7 Clustergr¨ oßenvergleich mittels Datenpunktzuordnungen: S-Distanz ( M in ) mit Minkowski-Metriken . . . . . . . . . . . . . . . . . . . . . . . 56

4.8 Clustergr¨ oßenvergleich mittels Datenpunktzuordnungen: S-Distanz nat¨ urlichen“ ¨ ( M in ) mit ” Ahnlichlichkeitsfunktionen . . . . . . . . . . . 57

4.9 Clustergr¨ oßenvergleich mittels Datenpunktzuordnungen: S-Distanz ( P rod ) mit Minkowski-Metriken . . . . . . . . . . . . . . . . . . . . . . . 58

4.10 Clustergr¨ oßenvergleich mittels Datenpunktzuordnungen: S-Distanz ( P rod ) mit ¨ Ahnlichlichkeitsfunktionen . . . . . . . . . . . . . . . . . . . 58

4.11 Clustergr¨ oßenvergleich mittels Datenpunktzuordnungen: K-Distanz . . . 59

4.12 Fuzzy-Gr¨ oßenvergleich: B-Distanz und S-Distanz mit Minkowski-Metriken 60

4.13 Cluster-Gr¨ oßenmethode: S-Distanz ( M in ) mit ¨ Ahnlichkeitsfunktionen . . 60

4.14 Clustergr¨ oßenmethode: S-Distanz ( P rod ) mit ¨ Ahnlichkeitsfunktionen . . 61

4.15 Fuzzy-Gr¨ oßenvergleich: K-Distanz . . . . . . . . . . . . . . . . . . . . . . 62

5.1 Voll ¨ ahnliche Farbverl¨ aufe nach Kosinus- ¨ Ahnlichkeitsmaß im RGB-

Farbraum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Tabellenverzeichnis

2.1 Dreiwertige Logik: die ” Und“-Verkn¨ upfung . . . . . . . . . . . . . . . . . 4

4.1 Erf¨ ullung der Dreiecksungleichung diverser ¨ Ahnlichkeitsfunktionen f¨ ur

Fuzzy-Cluster-Konfigurationen . . . . . . . . . . . . . . . . . . . . . . . . 54

4.2 Hierachische Splits: ¨ Ahnlichkeit / Distanz zwischen den Nachbarebenen . 64

4.3 Hierachische Splits: ¨ Ahnlichkeit / Distanz zwischen Wurzelebene und

tieferen Ebenen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.1 Klassifikationsergebnisse unter Verwendung fixer Cluster . . . . . . . . . 72

5.2 Klassifikationsergebnisse nach Fuzzy C-Means (Euklidischer Abstand) . . 73

5.3 Klassifikationsergebnisse nach FCM-Clustering (Adaptiertes Abstandsmaß) 74

5.4 Durchschnittliche Klassifikationsraten nach Cluster- und ¨ Ahnlichkeits-

funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Kapitel 1. Einleitung

Kapitel 1

Einleitung

1.1 Das Sandhaufenparadoxon

Der klassische Begriff der Wahrheit postuliert kontrastreiches und kategorisches Denken, welches unsere Welt einerseits leichter erfassbar macht, andererseits aber unsere Wahrnehmungsweise stark abstrahiert und dadurch verf¨ alscht. Die Formalisierung dieses Denkens f¨ uhrt in die Wissenschaft der Mathematik, in der der Mensch versucht, Wahrheiten in Form von abstrakten S¨ atzen zu verankern. Speziell die Teildisziplin der bin¨ aren Logik ist dazu geeignet, bestimmte Aussagen nach ” Wahr“ oder ” Falsch“ zu

klassifizieren. Dennoch scheinen damit nicht alle Ph¨ anomene erfassbar zu sein. Als Beispiel sei das Sandkornparadoxon genannt: Die bin¨ are mathematische Definition eines solchen Sandhaufens mittels einer intuitiven Regel erweist sich letztendlich als widerspr¨ uchlich. Es sei ein Sandhaufen mit einer definiten Anzahl von Sandk¨ ornern gegeben. Des weiteren gelte die Regel, dass durch Hinzuf¨ ugen oder Entfernen eines einzelnen Sandkornes ein Sandhaufen nicht als solcher entartet wird: er bleibt ein Sandhaufen.

Abbildung 1.1: Sandkornmengen und deren Zugeh¨ origkeit zu verschiedenen Konzepten

Durch Induktion kann gezeigt werden, dass nach diesen Axiomen sowohl ein einzelnes

Kapitel 1. Einleitung

Sandkorn als auch eine ganze W¨ uste voller Sandk¨ orner wieder ein Sandhaufen in diesem mathematischen Sinne bildet. Wann h¨ ort also ein Sandhaufen auf zu existieren? Die willk¨ urliche Angabe eines Sandkornanzahlbereiches ist vermutlich ungeeignet. Es scheint eher so, dass der Sandhaufen beim Wachsen zu einer W¨ uste und Schrumpfung zu einem einzelnen Sandkorn schleichend ¨ uber viele Metazust¨ ande sein Dasein als Sandhaufen

verliert. Als n¨ achstes kann man sich fragen, wieviele Sandk¨ ornern n¨ otig sind, damit der Sandhaufen den stabilsten Zustand als solchen erreicht.

Letztendlich scheint das imagin¨ are Konstrukt eines optimalen Sandhaufensprototyps geeignet zu sein, um andere Sandhaufen als solche zu klassifizieren: Ein Sandhaufen ist genau dann ein Sandhaufen wenn er exakt diesem Prototypen entspricht; andernfalls befindet er sich in einem mehr oder weniger starken Metazustand. Die reale Konstruktion eines solchen Prototypen mag genauso willk¨ urlich erscheinen, jedoch reicht in diesem Falle der Glaube an die bloße Existenz eines solchen aus, um das Paradoxon zu l¨ osen.

1.2 ¨ Ahnlichkeitsfunktionen f¨ ur Fuzzy-Cluster-Strukturen

Diese eher philosophische Betrachtung des Sandhaufenparadoxons f¨ uhrt dazu, dass wir in unserer Umwelt weitere ¨ ahnliche Probleme identifizieren: Wieviele B¨ aume ben¨ otigt ein Wald, wieviel Geld ein reicher Mensch und wann ist ein fließender Strom ein Rinnsal, Bach oder Fluss?

Der Mensch klassifiziert diese intuitiv mit Hilfe von Prototypen aus seiner Kultur und Umwelt. Diese k¨ onnen sich von Individuum zu Individuum unterscheiden: So w¨ urde der Begriff ” reich“ wohl von Naturv¨ olkern anders definiert werden als von Vertretern der Industrienationen.

Aber nicht nur der Mensch m¨ ochte solche Ph¨ anomene in seinem bestimmten Kontext identifizieren k¨ onnen: In Zeiten der massiven Informationsverarbeitung wird es immer wichtiger, dass auch Computer diese F¨ ahigkeit erwerben, zumal h¨ aufig die Ein- und Ausgabe der Daten von Menschenseite bzw. f¨ ur diesen erfolgt und deren Abstraktionssicht jeweils ber¨ ucksichtigt werden muss. Dazu ist neben der Prototypenbildung die Definition von ¨ Ahnlichkeitsfunktionen zu diesen Prototypen notwendig. Solche Algorithmen fallen unter der sog. Kategorie ” Fuzzy-Clustering“ und bilden Metazust¨ ande f¨ ur eine Menge von Objekten zu einzelnen Konzepten.

Dennoch ist die alleinige Bildung solcher Metazust¨ ande uninteressant: Erst der Vergleich zweier Objekte und deren Metazust¨ ande bez¨ uglich mehreren Konzepten erm¨ oglicht die sinnvolle Verarbeitung dieser generierten Informationen. Die Definition und Evaluation formaler und anwendungsbezogener Art dieser Funktionen bilden den Schwerpunkt dieser Diplomarbeit. Sie heißen ¨ Ahnlichkeitsfunktionen f¨ ur Fuzzy-Cluster-Strukturen. Ziel dieser Diplomarbeit ist es, geeignete ¨ Ahnlichkeitsfunktionen f¨ ur Fuzzy-Cluster-Strukturen unter Beachtung verschiedener Randbedingungen zu kreieren und sie bzw. andere bereits definierte Funktionen auf bestimmten Kontexten hin zu testen. Als Ergeb-

3 Kapitel 1. Einleitung

nis lassen sich Algorithmen ableiten, welche f¨ ur Computer die automatische Auswertung solch unscharfer Informationen erm¨ oglicht.

1.3 Gliederung der Arbeit

Nach diesem Einleitungskapitel erfolgt zun¨ achst die Einf¨ uhrung der ben¨ otigten Grundlagen in den Bereichen Fuzzy-Logik und Clusteranalyse. Anschließend wird der Fuzzy C-Means-Algorithmus vorgestellt, der eine unscharfe Clusterung erm¨ oglicht; dieser Al-gorithmus kann viele verschiedenen Parametrisierungen annehmen, was in unterschiedlichen Fuzzy-Cluster-Partitionen resultiert. Um die Qualit¨ at dieser Partitionen zu ermitteln, wird der Xie-Beni-Index eingef¨ uhrt, welcher eine Bewertung nach zwei verschiedenen Kriterien vornimmt.

Im dritten und umfangreichsten Kapitel werden insgesamt vier Fuzzy Cluster- ¨ Ahnlichkeitsfunktionsklassen entwickelt und der Nachweis ihrer formalen Eigenschaften erbracht. Auch verschiedene Parametrisierungen, Komplexit¨ atsfragen, Normalisierungen und algorithmische Umsetzung zu diesen Funktionen werden behandelt. Anschließend erfolgen im vierten Kapitel Tests in k¨ unstlichen geschaffenen Umgebungen: Ziel ist Erarbeitung von charakteristischen Eigenschaften der zuvor vorgestellten ¨ Ahnlichkeitsfunktionen bei kontrollierten und verifizierbaren Datens¨ atzen; so ist es bei vielen dieser Experimente m¨ oglich, das Resultat mathematisch nachzuvollziehen. Um sich nicht ausschließlich auf k¨ unstliche Tests zu verlassen, wird im f¨ unften Kapitel ein realit¨ atsn¨ aheres Anwendungsszenario vorgestellt: Mittels Bildklassifikation zeigt sich, wie gut die ¨ Ahnlichkeitsfunktionen in der Praxis funktionieren k¨ onnen und wie diese mit bestimmten Clusteralgorithmen harmonieren.

Im letzten Kapitel werden die erarbeiteten Ergebnisse bewertet und ein Ausblick auf noch offene und verwandte Themen gegeben.

Kapitel 2. Grundlagen

Kapitel 2

Grundlagen

In diesem Kapitel werden ausgew¨ ahlte Grundlagen in den Bereichen Cluster-Analyse und Fuzzy-Logik er¨ ortert, welche f¨ ur sp¨ atere Kapiteln ben¨ otigt werden, in denen u. a. Fuzzy- ¨ Ahnlichkeitsfunktionen konstruiert und evaluiert werden.

2.1 Einf¨ uhrung: Fuzzy-Logik

Die bin¨ are Logik umschreibt ausschließlich die beiden Zust¨ ande ” Wahr“ und ” Falsch“,

welche zu absoluten und scharfen Grenzen in Ontologien f¨ uhren. Diesen grundlegenden Nachteil der bin¨ aren Logik erkannte bereits Platon, welcher vermutet hat, dass es noch einen dritten Zustand zwischen Wahr und Falsch geben m¨ usste. Bestimmte Konzepte, wie das in der Einleitung vorgestellte Sandhaufenparadoxon lassen sich mit nur zwei Zust¨ anden nicht darstellen. Auch bei anderen Begriffen, wie beispielsweise Farben, welche der Kategorie ” Gr¨ un“ zugeordnet werden, tritt dieses Ph¨ ano-

men auf: Je nachdem wieviel prototypischen Gr¨ unanteil eine Farbe hat, desto eher w¨ urde man sie auch als ” Gr¨ un“ bezeichnen. Es werden somit deutlich mehr Zust¨ ande zwischen Wahr“ und ” Falsch“ ben¨ otigt.

”

1920 f¨ uhrte Lukasiewicz als erstes dreiwertige Logik ein, die die bin¨ are Logik um zumindest einen neuen Zustand erweiterte [Luk70]:

Sp¨ ater entwickelte er die f¨ unfwertige und zuletzt die unendlichwertige Logik, welche schließlich alle Wahrheitwerte aus dem Intervall [0..1] zul¨ aßt. Als Begr¨ under der sog. Fuzzy-Logik gilt jedoch L. A. Zadeh, der 1965 die ” Fuzzy-Menge“ einf¨ uhrte und explizit

5 Kapitel 2. Grundlagen

ein mathematisches Konzept kreierte, welches in der Lage ist, unscharfe Begriffe wie Gr¨ un“ zu beschreiben.

”

2.1.1 Fuzzifizierung aussagenlogischer Ausdr¨ ucke

Um aussagenlogische Ausdr¨ ucke von der bin¨ aren Logik auf die Fuzzy-Logik zu erweitern, ist eine Definition der grundlegenden Operationen ” Nicht“, ” Und“ und ” Oder“

notwendig. Dabei ist die Einhaltung verschiedener Randbedingungen notwendig, um zu erreichen, dass die bin¨ are Logik eine Teilmenge der Fuzzy-Logik darstellt. Die ” Und“-Verkn¨ upfung wird durch eine sog. -Norm realisiert, welche folgende Bedingungen erf¨ ullen muss:

(2.1)

Die Negation eines Elements ist als additives Komplement zu diesem definiert:

(2.2) neg(x) + x = 1

Neben dieser Form existieren noch weitere Negationsm¨ oglichkeiten, welche aber hier nicht weiter behandelt werden. Die sog. ⊥-Conorm, welche der ” Oder“-Verkn¨ upfung entspricht, kann durch Anwen-

dung der Demorganschen Gesetze hergeleitet werden; dieses Gesetz soll aufgrund der Teilmengenbeziehung nicht nur in der bin¨ aren Logik, sondern auch in der Fuzzy-Logik gelten:

(2.3) (a ∧ b) = ¬(¬a ∨ ¬b)

¨ Ubertragen auf die Fuzzy-Logik ist die ⊥-Conorm wie folgt definiert:

(2.4) ⊥(a, b) = 1 − ((1 − a), (1 − b))

Die Eigenschaften der T-Norm gelten in gleicher oder ¨ ahnlicher Weise auch f¨ ur die T-Conorm ⊥:

(2.5)

Kapitel 2. Grundlagen 6

Da das Assoziativgesetz sowohl f¨ ur die T-Norm als auch f¨ ur die T-Conorm gilt, kann man eine abk¨ urzende Schreibweise f¨ ur die Verkn¨ upfung von endlich vielen Elementen f¨ ur diese beiden Funktionen einf¨ uhren. Sei dazu A = (a 1 , a 2 , . . . , a n ) die Menge der zu verkn¨ upfenden Elemente. Dann gilt:

(a 1 , a 2 , . . . , a n ) = (. . . ((a 1 , a 2 ), . . . ), a n ) (2.6)

⊥(a 1 , a 2 , . . . , a n ) = ⊥(. . . (⊥(a 1 , a 2 ), . . . ), a n ) (2.7)

2.1.2 Verschiedene T-Normen und T-Conormen

Es gibt sehr viele Funktionen, welche die im vorherigen Abschnitt definierten Eigenschaften aufweisen. L. A. Zadeh f¨ uhrte die erste T-Norm ein, welche durch ihre Einfachheit einige Vorteile aufweist:

(2.8)

So l¨ asst sich diese T-Norm bei Verkn¨ upfung vieler Elemente und bei Verwendung geeigneter Datenstrukturen sehr performant implementieren, da aus einer gegebenen Menge nur das kleinste Element gefunden werden muss. Entsprechendes gilt f¨ ur die duale T-Conorm.

Weitere bekannte T-Normen sind P rod und Lukasiewicz :

(2.9)

(2.10)

Bei der Berechnung der T-Norm P rod fließen beide Elemente in das Ergebnis ein und nicht nur das kleiner bzw. gr¨ oßere Element. Der Steigungsgradient dieser Funktion ¨ andert sich damit weniger abrupt als bei der T-Norm M in und der Informationsverlust ist geringer. Ein noch st¨ arker Informationsverlust ereignet sich bei der T-Norm Lukasiewicz : Insbesondere bei Verkn¨ upfung sehr vieler Elemente wird schnell das Minimum von Null bzw. bei der T-Conorm das Maximum von Eins erreicht.

Des weiteren sei noch die drastische T-Norm −1 genannt, welche zwar f¨ ur Anwendungen aufgrund des maximalen Informationsverlustes in der Regel nicht geeignet ist, aber daf¨ ur formale Eigenschaften im Grenzbereich von T-Normen zeigt:

Kapitel 2. Grundlagen 7



(2.11)

Neben diesen bekannten T-Normen gibt es parametrisierte, welche eine unendlich große Klasse von T-Normen bilden k¨ onnen. Als Beispiel sei hier die Yager-Familie erw¨ ahnt [CB03], welche durch geeignete Parameterwahl auch P rod und ^Lukasiewicz erzeugen k¨ onnen. Diese wird jedoch im weiteren nicht betrachtet: Sp¨ atere Konzepte ben¨ otigen zwar die Wahl einer T-Norm, jedoch beschr¨ ankt sich diese Arbeit nur mit den gerade vorgestellten ” klassischen“ T-Normen.

2.2 Cluster-Analyse

Mit Hilfe einer Cluster-Analyse lassen sich ¨ ahnliche Daten zu sog. Clustern zusammenfassen. Diese repr¨ asentieren jeweils eine Klasse, die einen oder mehrere Datens¨ atze enth¨ alt. Die Cluster-Analyse ist dabei eine Methode des maschinellen Lernens; der Lernprozess ist un¨ uberwacht, da die Clusteralgorithmen keine R¨ uckkopplung bekommen wie gut die Clustereinteilung aus Sicht eines Experten gelungen ist. Dies erfolgt meist erst im zweiten Schritt, beispielsweise durch Interpretation eines solchen Experten. Bevor man Daten clustern kann, m¨ ussen diese auf Eignung selektiert und anschließend f¨ ur den Clusteralgorithmus aufbereitet werden. Dieser Prozess ist fehlerbehaftet, wenn die falschen Daten selektiert werden oder wenn die Aufbereitung, die einer Abbildungsfunktion entspricht, Informationen so verwischt, dass sie der sp¨ atere Clusteralgorithmus nicht mehr bewerten kann.

Eine weitere Fehlerquelle liegt im Clusteralgorithmus selber: Diese lassen sich meist parametrisieren, so dass die Anzahl der Cluster unterschiedlich ausfallen kann. Die Wahl der Parameter ist wichtig, um einen Informationsgewinn zu verwirklichen; so ist es beispielsweise nicht sinnvoll, alle Datenpunkte in einem Cluster zusammenzufassen als auch jedem Datenpunkt seinen eigenen Cluster zuzuweisen.

Letztendlich hat auch die Auswahl des Clusteralgorithmus Einfluss auf die Qualit¨ at der Cluster-Analyse.

2.2.1 Daten ausw¨ ahlen

In Datensammlungen existieren zu einem Datensatz h¨ aufig unterschiedlichste Datentypen. Bevor man sie der Cluster-Analyse unterzieht, sollte man diese auf sol- che Attribute reduzieren, die eine kausale Korrelation zu anderen Attributen vermuten

Kapitel 2. Grundlagen 8

l¨ asst; dies senkt den Berechnungsaufwand und erh¨ oht h¨ aufig die Genauigkeit der Cluster-Analyse.

Korrelationslose Daten k¨ onnten beispielsweise die zuf¨ allige Kundennummer und Kontonummer eines Kunden sein, da diese zusammen wohl keine weiteren R¨ uckschl¨ usse auf andere Attribute wie beispielsweise Einkaufsverhalten zul¨ asst.

2.2.2 Daten vorbereiten

Datens¨ atze bestehen h¨ aufig aus unterschiedlichsten Typen von Attributen: So kann beispielsweise einer Person eine K¨ orpergr¨ oße, eine Augenfarbe, eine Adresse und ein Kon-tostand zugeordnet werden. Viele Clusteralgorithmen arbeiten jedoch nur mit reellen Werten, die pro Datensatz zu einem Vektor zusammengefasst werden. Um einen Datensatz bestehend aus n Attributen in den n-dimensionalen Raum abzubilden, ist eine geeignete Abbildungsfunktion anzuwenden, die das entsprechende Attribut m¨ oglichst repr¨ asentativ auf diesen Raum abbildet. Eine Begrenzung und Normierung des Funktionsraumes ist auch anzustreben, was eine Skalierung der Attribute nach sich zieht. Beispielsweise sei der n-dimensionale Einheitshyperw¨ urfel genannt, in dem sich alle Datenvektoren befinden sollten. Hierbei gibt es je nach Typ mehreren M¨ oglichkeiten:

• Lineare Normalisierung von reellen Attributen (z. B. K¨ orpergr¨ oße) auf Basis des gr¨ oßten und kleinsten Datensatzes in der Sammlung

• Nichtlineare Normalisierung (z. B. Kontostand: Ein einzelner sehr hoher Konto-stand w¨ urde bei linearerer Normalisierung Unterschiede stark verwischen). Hier k¨ onnte beispielsweise eine logarithmische Abbildungsfunktion helfen.

• Diskretisierung von Aufz¨ ahlungsattributen (z. B. Augenfarbe): f (blau) = 0.0, f (gr¨ un) = 0.33, f (grau) = 0.67, f (braun) = 1.0

• Vereinfachung (z. B. Adresse): Aus der Adresse wird nur die (normaliserte) Postleitzahl als Attribut verwendet.

2.2.3 Auswahl eines Clusteralgorithmus

Nach der erfolgreichen Abbildung der selektierten Daten in einen Vektorraum erfolgt die Cluster-Analyse durch einen Clusteralgorithmus, der homogene Daten in einem Cluster zusammenfassen soll. Hierbei existiert eine Vielzahl von Algorithmen, die das Kriterium Homogenit¨ at jeweils anders interpretieren:

So ist der DBSCAN-Algorithmus [EKS ⁺ 98] in der Lage, eine vorher unbestimmte Zahl von Clustern aufgrund lokaler Punktdichten zu bestimmen. Bei dem im n¨ achs- ten Abschnitt vorgestellten K-Means-Algorithmus hingegen ist die Clusterzahl vorher

Kapitel 2. Grundlagen

festzulegen; diese sollten m¨ oglichst kugelf¨ ormig ausfallen bzw. je nach verwendeten Ab-standsmaß bestimmten Formen ¨ ahneln.

Des weiteren existieren noch hierarchische Clusterverfahren, welche ein gegebenes Cluster in neue Cluster zerteilen kann oder umgekehrt eine Menge von gegebenen Clustern miteinander so verschmelzen l¨ asst, dass die Clusterzahl sich verringert. Ausgehend von einem Cluster, der alle Datens¨ atze in sich vereint bzw. ausgehend von n Clustern, zu denen jeweils nur einen Datensatz zugeordnet ist, kann man eine durch Teilung und Vereinigung eine sinnvolle Clusterkonfiguration erreichen. Als ein Vertreter dieser Algorithmenklasse sei BIRCH genannt [ZRL96].

Je nach Struktur der Daten im Vektorraum ist die Wahl des Algorithmus und seiner Parameter entscheidend f¨ ur die Qualit¨ at der Cluster-Analyse. Diese kann durch sog. Qualit¨ atsmaße bestimmt werden: Als Beispiel sei auf den Xie-Beni-Index verwiesen, welcher beim K-Means-Algorithmus und seiner fuzzifizierten Modifikation (Fuzzy C-Means) anwendbar ist; der Index wird am Ende dieses Kapitels vorgestellt. Da im Folgenden Kapiteln zwar Fuzzy-Cluster-Konfigurationen ben¨ otigt werden, aber der Schwerpunkt dieser Arbeit nicht in der Cluster-Analyse liegt, wird nur ein einzelner Fuzzy-Cluster-Algorithmus vorgestellt. F¨ ur eine optimale Cluster-Analyse einer gegebenen Datenmenge sei aber noch auf die anderen Algorithmen verwiesen.

2.2.4 K-Means

K-Means [Dun03] ist ein nichtdeterministischer Cluster-Algorithmus, der versucht k Clusterzentren zu optimieren. Der Ablauf ist folgender: Anfangs werden die k Clusterzentren zuf¨ allig ¨ uber den Daten-Vektorraum verteilt; jeder Datenpunkt wird dem n¨ achsten Clusterzentrum zugeordnet. Nun erfolgt eine Neuberechnung der Clusterzentren c i auf-grund der m zugeordneten Punkte t ij :

(2.12)

Im n¨ achsten Schritt werden die Zugeh¨ origkeitsgrade basierend auf dem Abstand zu den Clusterzentren bestimmt; das Verfahren wird dann iterativ solange fortgesetzt, bis die ¨ Anderungen der k Clusterzentren c i einen definiten Schwellenwert ref unterschreiten:

(2.13)

Zu bemerken ist, dass dieser Algorithmus h¨ ochstens k Cluster produziert, da bei der Neuzuordung der Datenpunkte zu Clustern der Fall eintreten kann, das einem Cluster gar keine Datenpunkte zugeordent werden k¨ onnen; dies macht eine Neuberechnung des Clusterzentrums unm¨ oglich und das Cluster wird nicht weiter ber¨ ucksichtigt.

10 Kapitel 2. Grundlagen

Abbildung 2.1: K-Means nach Initialisierung (links) und nach Konvergenz (rechts)

Je h¨ oher die Clusterzahl und je geringer die Datenpunktanzahl desto h¨ oher die Wahrscheinlichkeit, dass Cluster gel¨ oscht werden m¨ ussen. Auch eine hohe Dichte in wenigen Clustern erh¨ oht die Wahrscheinlichkeit f¨ ur diesen Fall. Die Clusterzahl wird durch diesen Algorithmus reduziert werden, wenn k gr¨ oßer ist, als die Anzahl der Datenpunkte.

2.2.5 Fuzzy C-Means

Eine Fuzzifizierung des K-Means Clusteralgorithmus f¨ uhrt zu dem sog. Fuzzy C-Means-Algorithmus: Er unterscheidet sich darin, dass er die Zugeh¨ origkeitsgrade der Punkte in Abh¨ angigkeit zur Entfernung der Clusterzentren vergibt und dass auch die Neuberechnung der Clusterzentren durch die Zugeh¨ origkeitsgrade der Punkte gewichtet wird. [Dun73]

Formal ¨ andert sich der Algorithmus wie folgt: Sei u ij der Zugeh¨ origkeitsgrad des Datenpunktes x i zu Cluster c j und d(x, y) eine Abstandsfunktion f¨ ur zwei Vektoren. Nach der zuf¨ alligen Cluster-Zentrums-Initalisierung, wird die Zugeh¨ origkeitsmatrix berechnet:

(2.14)

Die verwendete Abstandsfunktion d(x, y) ist h¨ aufig der euklidische Abstand. Im n¨ achsten Schritt werden die Clusterzentren neu berechnet:

Kapitel 2. Grundlagen

n

(2.15)

Wie beim K-Means-Algorithmus werden die Clusterzentren iterativ solange verfeinert, bis nur noch marginale ¨ Anderungen in der Zugeh¨ origkeitsmatrix bzw. in den Clus-terzentrumsvektoren zu verzeichnen sind.

Ein wichtiger Unterschied zum K-Means Algorithmus ist, dass die Entstehung leerer Cluster auszuschließen ist, sofern man mindestens so viele Datenpunkte wie Cluster hat. Somit k¨ onnen Applikationen, die eine bestimmte Anzahl von Clustern f¨ ur einen Datensatz generieren m¨ ussen, diese Anzahl mit dem Fuzzy C-Means-Algorithmus garantieren. Der Fuzzy C-Means-Algorithmus und seine Varianten sind die mit Abstand wohl die bekannteste Fuzzy-Clusteralgorithmen. Bestimmte Variationen spezifizieren beispielsweise eine variable Abstandsfunktion oder passen die Clusteranzahl automatisch an, wie im n¨ achsten Abschnitt beschrieben.

Deshalb wird in dieser Arbeit auch ausschließlich dieser Algorithmus als ” echter“

Fuzzy-Cluster-Algorithmus genutzt. Andere M¨ oglichkeiten, Fuzzy-Clusterstrukturen zu erzeugen werden sp¨ ater zwar auch genutzt, jedoch bleibt die geometrische Lage der Datenpunkte im Raum unber¨ ucksichtigt oder die Clusterzentren werden fest vordefiniert.

2.2.6 Wahl der Clusteranzahl

Um f¨ ur einen gegebenen Datensatz die optimale Clusteranzahl f¨ ur den Fuzzy C-Means-Algorithmus zu finden, ist es notwendig die Qualit¨ at einer dazugeh¨ origen Clusterkonfiguration zu bewerten. Existiert eine solche Funktion, kann man beispielsweise durch sukzessive Steigerung der Clusterzahl versuchen, diese zu optimieren. Da Fuzzy C-Means ein nichtdeterministischer Algorithmus ist, sind zus¨ atzlich auch mehrere Durchl¨ aufe f¨ ur eine bestimmte Clusteranzahl von Vorteil: Der Durchlauf mit der besten Qualit¨ at repr¨ asentiert dann die Gesamtqualit¨ at f¨ ur eine bestimmte Clusteranzahl. Im Folgenden verwenden wir den sog. Xie-Beni Index [XB91], der zwei Teilkriterien einer Clusterstruktur nutzt: Ein Cluster sollte m¨ oglichst kompakt sein, was bedeutet, dass ein Datenpunkt m¨ oglichst dicht am Clusterzentren liegt und somit einen tendenziell hohen Zugeh¨ origkeitsgrad zu diesem aufweist. Dieses Kriterium nennt sich ” Intra-Cluster-Distanz“ und entspricht einer gewichteten Varianzberechnung der Datenpunkte zum Mittelpunkt des Clusters.

Seien dazu C eine Fuzzy-Cluster-Konfiguration, c j einer von m Clusterzentren, x ⁱ einer von n Datenpunkten, u ij der Zugeh¨ origkeitsgrad von Datenpunkt x i zu Cluster c j und d(x, y) eine Abstandsfunktion f¨ ur zwei Vektoren. Formal wird die Intra-Cluster-

Distanz dann nach folgender Funktion berechnet:

Kapitel 2. Grundlagen

(2.16)

Die Intra-Cluster-Distanz sollte minimiert werden, damit kompakte Cluster entstehen. Tendenziell steigt die Kompaktheit mit der Clusteranzahl. Das zweite Kriterium ist die sog. Inter-Cluster-Distanz, welche maximiert werden muss, damit die Daten gut separiert werden. Diese ergibt sich dann als Abstand eines Clusterzentrums zum n¨ achsten Clusterzentrum:

(2.17) sep(C) = min {d(c i , c j )} , ∀(i = j)

Dieses Kriterium sollte maximiert werden um eine gute Separation zu erreichen. Im Gegensatz zu der Intra-Cluster-Distanz wird dieses Kriterium tendenziell mit abnehmender Clusteranzahl optimaler. Beide Kriterien werden durch einen Quotienten ber¨ ucksichtigt, welche die Gesamtqualit¨ at einer Clusterkonfiguration repr¨ asentiert:

(2.18)

Dieser muss insgesamt m¨ oglichst minimiert werden, um eine qualitativ hochwertige Clusterkonfiguration zu erreichen.

Zu bemerken ist noch, dass beim Xie-Beni Index als Abstandsfunktion h¨ aufig die euklidische Distanzfunktion genutzt wird. Diese kann jedoch je nach Anwendung variiert werden: Eine Anwendung so gewonnener verschiedener Qualit¨ atsfunktionen wird in Kapitel 5 in einem Bildklassifikationsszenario vorgenommen.

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 13

Kapitel 3

Entwicklung von ¨

Ahnlichkeitsmaßen

¨ Ahnlichkeitsmaße sind Funktionen, die entscheiden inwieweit zwei Objekte gleichartig sind. Dabei sind sie f¨ ur bestimmte Objekttypen spezialisiert: Viele bekannte ¨ Ahnlichkeits- bzw. Abstandsfunktionen gibt es f¨ ur Punkte bzw. Vektoren im ndimensionalen Raum wie beispielsweise die euklidische Distanzfunktion. Aber auch f¨ ur Fuzzy-Cluster-Konfigurationen spezialisierte Abstandsmaße sind denkbar; diese werden in diesem Kapitel entwickelt.

Grundproblem dabei ist, zwei Mengen von Vektoren zu vergleichen, wobei der eingeschr¨ ankte Wertebereich von 0 bis 1 der einzelnen Vektorelemente zu ber¨ ucksichtigen ist. Daf¨ ur werden im Folgenden verschiedene Ans¨ atze und Konzepte vorgestellt.

3.1 Distanzfunktionen und ¨ Ahnlichkeitsmaße

In diesem Abschnitt werden Distanzfunktionen und ¨ Ahnlichkeitsfunktionen definiert und

je nach Eigenschaften genauer spezifiziert. Auch die Verwandtschaft beider Konzepte wird betrachtet.

3.1.1 Definition

Die Definition von Funktionen, welche geeignet sind, Abst¨ ande zwischen Objekten zu spezifizieren, werden anhand der Eigenschaften Selbstidentit¨ at, Positivit¨ at, Symmetrie und Dreiecksungleichung kategorisiert. Die Definition erfolgt nach [Con84] und [DL91]; Sei O eine Menge von Objekten:

Selbstidentit¨ at :

Symmetrie :

(3.1)

P ositivit¨ at :

Dreiecksungleichung : ∀o, o , o ∈ O : D(o, o ) + D(o , o ) ≥ D(o, o )

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 14

Definition 1. Eine Funktion D(o, o’) heißt Semi-Pseudo-Distanzfunktion oder Semi-Pseudo-Metrik, wenn sie die Eigenschaften Selbstidentit¨ at und Symmetrie zu allen Objekten der Menge O aufweist.

Definition 2. Eine Semi-Pseudo-Distanzfunktion D(o, o’) heißt Pseudo-Distanzfunktion oder Pseudo-Metrik, wenn sie die Dreiecksungleichung erf¨ ullt.

Definition 3. Eine Semi-Pseudo-Distanzfunktion D(o, o’) heißt Semi-Distanzfunktion oder Semi-Metrik, wenn f¨ ur sie die Eigenschaft der Positivit¨ at gilt.

Definition 4. Eine Semi-Distanzfunktion D(o, o’) heißt Distanzfunktion oder Metrik, wenn sie die Dreiecksungleichung erf¨ ullt.

Die Distanzfunktionen sind meist so spezifiziert, dass das Funktionsergebnis immer gr¨ oßer wird, je un¨ ahnlicher die Objekte sind. In unbeschr¨ ankten R¨ aumen f¨ uhrt das dazu, dass die Distanz zwischen Objekten beliebig groß werden kann. Im Gegensatz dazu haben sog. ¨ Ahnlichkeitsmaße fixe Funktionsergebnisgrenzen:

Definition 5. Eine Funktion S(o, o’) heißt ¨ Ahnlichkeitsmaß, wenn sie die Eigenschaften

Selbstidentit¨ at, Symmetrie aufweist, das Supremum 1 betr¨ agt und ein endliches Infimum b aufweist:

(3.2)

F¨ ur sp¨ atere Algorithmen ist die Verwendung von normierten ¨ Ahnlichkeitsfunktionen

sinnvoll, welche alle ein definiertes Supremum und Infimum haben:

Definition 6. Eine Funktion S N orm (o, o ) heißt normierte ¨

die Eigenschaften eines ¨ Ahnlichkeitsmaßes aufweist und das Inifimum 0 betr¨ agt. 3.1.2 Umwandlung von Distanzfunktionen und ¨ Ahnlichkeitsmaße in normierte ¨ Ahnlichkeitsmaße

F¨ ur sp¨ atere Konzepte sind normierte ¨ Ahnlichkeitsmaße notwendig, welche im Folgenden

f¨ ur Vektoren aus dem n-dimensionalen Einheitskubus betrachtet werden: Als Parameter dienen Clustervektoren, welche sich in diesem begrenzten Raum befinden. Um ein m¨ oglichst breites Spektrum von diesen normierten ¨ Ahnlichkeitsmaßen zu generieren, kann man unnormierte ¨ Ahnlichkeitsmaße und die meisten Semi-Pseudo-Distanzfunktion in solche umwandeln. Sei s( u, v) ein ¨ Ahnlichkeitsmaß mit dem Inifimum b und Supremum t mit t > b:

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 15

(3.3)

Dann ist s N orm ( x, y) ein normiertes ¨ Ahnlichkeitsmaß.

Sei d( u, v) eine Semi-Pseudo-Distanzfunktion, welche f¨ ur alle Vektoren aus dem ndimensionalen Einheitskubus ein endliches Supremum t > 0 erreicht.

(3.4)

Dann ist s N orm ( u, v) ein normiertes ¨ Ahnlichkeitsmaß.

Die umgekehrte Umwandlung eines normierten ¨ Ahnlichkeitsmaß in eine Semi-Pseudo-Distanzfunktion mit Supremum t erfolgt nach:

(3.5) d( u, v) = [1 − s N orm ( u, v)] · t

Nach dieser Umwandlung muss noch im Einzelnen nachgewiesen werden, ob diese Funktion nur eine Semi-Pseudo-Distanzfunktion ist oder ob sie noch die Dreiecksungleichung bzw. Posititvit¨ atseigenschaft nach Gleichung 3.1 erf¨ ullt.

3.2 Vergleich von Cluster-Partitionen

Der Vergleich zweier Cluster-Partitionen impliziert den Vergleich zweier Mengen bzw. Multimengen; je nach Konfiguration k¨ onnen diese eine Sortierung bzgl. Clustern oder Datenpunkte aufweisen, was den Vergleich erleichtert. Die dazu ben¨ otigten Ans¨ atze werden im n¨ achsten Abschnitt vorgestellt.

Im zweiten Abschnitt werden verschiedene Funktionen f¨ ur den Vergleich zweier Cluster vorgestellt. Dazu gibt es zwei Darstellungsformen, die m¨ oglichst beide verwendet werden.

3.2.1 Cluster-Partitionen-Vergleich unter verschiedenen Randbedingungen

F¨ ur die Erstellung von ¨ Ahnlichkeitsfunktionen f¨ ur zwei Cluster-Partitionen ist es entscheidend, welche Voraussetzungen man f¨ ur diese beiden treffen kann. Je strikter diese sind, desto leichter sind m¨ ogliche Algorithmen zu kreieren. Zur Vereinfachung wird zun¨ achst nur der Nicht-Fuzzy-Fall betrachtet.

Folgende Nebenbedingungen k¨ onnen bei zwei Clusterpartitionen auftreten, wobei die zweite Nebenbedingung die erste impliziert bzw. enth¨ alt die vierte Nebenbedingung die dritte:

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 16

1. Beide Clusterpartitionen haben die gleiche Datenpunktanzahl

2. Zu den beiden Cluster-Konfigurationen ist eine bijektive Abbildung zu den Datenpunkten gegeben

3. Beide Clusterpartitionen haben die gleiche Clusteranzahl

4. Zu den beiden Cluster-Konfigurationen ist eine bijektive Abbildung zu den Clustern gegeben

Wenn man alle Nebenbedingungen voraussetzen kann, es also eine bijektive Abbildung sowohl f¨ ur die Datenpunkte als auch Cluster gibt, so entsteht eine recht einfache ¨ Ahnlichkeitsfunktion durch den Vergleich der bereits feststehenden Clusterpaare und deren enthaltenen Datenpunktpaaren: Alle Unterschiede bzw. Fehler werden verkn¨ upft, was letztendlich das Endergebnis der ¨ Ahnlichkeitsfunktion repr¨ asentiert.

In der Literatur [Bor05] [Mei07] ist f¨ ur diese strikten Voraussetzungen ein Ansatz namens ” Counting Pairs“ (Paarz¨ ahlung) bekannt, der im n¨ achsten Abschnitt vorgestellt wird und auch auf andere F¨ alle ¨ ubertragbar ist. Dieser z¨ ahlt alle gleiche und unterschiedliche Datenpunktpaare in vier Parametern, aus denen letztendlich eine Gesamt¨ ahnlichkeit bestimmt werden kann.

F¨ ur die Nebenbedingungen, dass es eine eineindeutige Clusterzuordnung existiert, aber keine Datenpunktzuordnung, sind zwei F¨ alle zu unterscheiden: Wenn beide Clusterpartitionen zumindest die gleiche Datenpunktanzahl aufweisen, kann man eine Permutation der Datenpunkte durchf¨ uhren und f¨ ur jede Konfiguration wieder die Gesamtfehlersumme aller Clusterpaare berechnen; die h¨ ochste ¨ Ahnlichkeit repr¨ asentiert dann das Ergebnis der ¨ Ahnlichkeitsfunktion.

Dieser Ansatz hat eine hohe Komplexit¨ at ¹ und ist bei großer Datenpunktanzahl somit praktisch nicht mehr durchf¨ uhrbar. Ein zweiter Ansatz basiert auf den Vergleich s¨ amtlicher Datenpunktpaare zu beiden Partitionen, welcher auch bei unterschiedlicher Datenpunktanzahl funktioniert. Der Vergleich aller Datenpunktpaare wird equivalent zum ” Counting Pairs“-Ansatz durchgef¨ uhrt. Zu bemerken ist, dass diese Methode mit linearen Aufwand zur Datenpunktanzahl auch f¨ ur den Fuzzy-Fall sehr schnell arbeitet. Der letzte Fall betrachtet eine fehlende Clusterzuordnung: Auch hier w¨ are ein Ansatz wieder eine Permutation, welche die beste Konfiguration herstellt. Wenn die Anzahl der Cluster in beiden Partitionen unterschiedlich ist, scheitert dieser aber. F¨ ur diesen Fall werden sp¨ ater in diesem Kapitel mehrere Ans¨ atze vorgestellt: der eine versucht jedes Cluster aus Partition U mit jedem Cluster aus Partition V zu vergleichen und die Ergebnisse sinnvoll zu verkn¨ upfen, wie beispielsweise das beste Clusterpaar zu bestimmen. Alle Fehlerwerte zusammen werden ausgewertet und aus Symmetriegr¨ unden

¹ Es handelt sich um ein allgemeines Zuordnungsproblem, f¨ ur das keine weiteren Einschr¨ ankungen

gemacht werden k¨ onnen, da die ¨ Ahnlichkeitsfunktion nicht weiter spezifiziert ist und somit die Komple- xit¨ at von O(n!) besitzt

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 17

erfolgt die ganze Prozedur noch aus Sicht von Partition V ; beide Teilergebnisse werden als letztes symmetrisch verkn¨ upft.

Ein zweiter Ansatz versucht alle Cluster aus Partition U so zu teilen und zu verschmelzen, dass m¨ oglichst alle Cluster aus Partition V hergestellt werden k¨ onnen. Gelingt dies nicht, so ergibt sich ein Fehlerwert, der die Un¨ ahnlichkeit repr¨ asentiert. Wie im ersten Ansatz wird auch die ¨ Ahnlichkeit von Partition V zu Partition U bestimmt und symmetrisch verkn¨ upft.

In der Literatur wurde auch ein entropiebasiertes Distanzmaß vorgestellt [Mei07], welches pro Partition einen Entropiewert ermittelt; der Vergleich zweier Partitionen wird somit auf den Vergleich zweier reeller Werte reduziert, was somit weder Cluster- noch Datenpunktzuordnung notwendig macht.

Die vorgestellten Randbedingungen k¨ onnen in verschiedenen Szenarien auftreten: Wenn man beispielsweise zwei Clusteralgorithmen mit einer Datensammlung vergleichen will, so ist die bijektive Abbildung der Datenpunkte gegeben. Jedoch ist die Anzahl und Zuordnung der entstandenen Cluster im Allgemeinen nicht gegeben. Der allgemeinste Fall, in dem eine unterschiedliche Anzahl von Datenpunkten und Clustern gegeben ist, tritt auf, wenn man bestimmen will, wie ¨ ahnlich zwei unterschiedliche Datensammlungen strukturell sind. Dieses ist n¨ utzlich, wenn man viele Prototypen von Datensammlungen hat und eine neue klassifizieren m¨ ochte. So lassen sich beispielsweise ¨ uber einen bestimmten Zeitraum gesammelte Messwerte mit Messwerten aus fr¨ uheren Zeitr¨ aumen vergleichen und somit eventuell R¨ uckschl¨ usse auf zuk¨ unftige Entwicklungen treffen.

3.2.2 Gewinnung von Eigenschaftskoeffizienten von Clusterpaaren

Einige im vorherigen Abschnitt vorgestellten Konzepte basieren auf den Vergleich zweier Cluster bzw. auf den Vergleich, wie die Datenpunkte zu den beiden Clustern angeh¨ oren.

In der Literatur bestimmt der genannte ” n 00 , n 10 und n 01 , welche sp¨ ater in einer Cluster- ¨ k¨ onnen. Dieser wird in diesem Abschnitt vorgestellt.

F¨ ur den Nicht-Fuzzy-Fall z¨ ahlen diese vier Parameter die Datenpunktpaare, welche equivalent sind (n 00 und n 11 ) bzw. unterschiedlich (n 01 und n 10 ). Dabei werden jeweils die beiden m¨ oglichen F¨ alle von Equivalenz bzw. Differenz separat gez¨ ahlt. Je nach Voraussetungen lassen sich diese Parameter auch durch Vektoroperationen bestimmen. Existiert eine bijektive Abbildung zwischen den Datenpunkten beider Par- v j diebeiden

zu vergleichenden Cluster der Dimension m:

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 18

(3.6)

(3.7) (3.8) (3.9)

Dieser vektorielle Ansatz basiert darauf, dass eine Z¨ ahlung der Datenpunkte, welche beiden Vektor angeh¨ oren, durch ein Skalarprodukt ermittelt werden kann. Er ist auch auf Fuzzy-Cluster ¨ ubertragbar.

Fehlt eine bijektive Abbildung der Datenpunkte zu beiden Clustern, so lassen sich ^T = (u i1 , ..., u im ) und ^T = (v j1 , ..., v jn ) die die Parameter wie folgt gewinnen: Seien u i v j

beiden Cluster in vektorieller Darstellung zu denen m bzw. n Datenpunkte angeh¨ oren:

(3.10)

(3.11)

(3.12)

(3.13)

Dieser Ansatz bestimmt einen zur Clusterdimension gewichtetes arithmetisches Mittel, welches dann mit dem o. g. vektoriellen Konzept vergleichbar ist. Wie die equivalente Umformung zeigt, lassen sich alle Parameter mit linearen Aufwand zu der Datenpunktanzahl (m + n) bestimmen.

3.3 ¨ Ahnlichkeitsfunktionen f¨ ur Clusterpaare

Wie im vorherigen Abschnitt gezeigt, lassen sich zwei Clusterpaare durch zwei Vekto- ren bzw. durch die vier Parameter n 11 , n 00 , n 10 und n 01 darstellen. F¨ ur diese existieren

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 19

bereits in der Literatur eine Vielzahl von ¨ Ahnlichkeitsfunktionen, wobei hier versucht

wird, m¨ oglichst beide Darstellungen zu verwenden. Sie werden in folgenden Kapiteln nat¨ urliche“ ¨ Ahnlichkeitsfunktionen genannt, da sie nicht aus einem Distanzmaß heraus

”

motiviert worden sind und somit ohne weitere Umformung eine normierte ¨ funktion bilden.

Aus dem Information Retrieval (Klassifikation) [vR79] sind folgende Maße bekannt:

(3.14)

(3.15) (3.16) (3.17)

(3.18)

(3.19)

Wallace [Wal83] hat zwei Maße verwendet, welche den Maßen ” Sensititvit¨ at“ und

Relevanz“ aus dem Information Retrieval entsprechen. Sie sind beide asymmetrisch:

”

(3.20)

(3.21)

Fowlkes und Mallows [FM83] vereinten diese beiden Maße durch die Bildung des geometrischen Mittels, was gleichzeitig die Symmetrieeigenschaft sicherte:

(3.22)

Dieses Maß entspricht dem sog. Kosinus¨ ahnlichkeitsmaß, welches den Kosinus des Winkels beider gegebener Vektoren berechnet. Da nur Vektoren aus dem n-dimensionalen Einheitskubus betrachtet werden, kann der Winkel minimal 0 ^◦ und maximal 90 ^◦ werden, was einem Kosinus von 1 bzw. 0 entspricht: Somit ist dieses ¨ Ahnlichkeitsmaß in diesem Raum ein normiertes.

Zu bemerken ist noch, dass diese Funktion f¨ ur den o-Vektor wie f¨ ur viele andere hier vorgestellten ¨ Ahnlichkeitsfunktionen undefiniert ist; dieses ist aber in der Praxis unerheblich, wenn man leere Cluster ausschließt: Jedem Cluster sollte mindestens ein Datenpunkt zu einem gewissen Grad angeh¨ oren.

Kapitel 3. Entwicklung von ¨

Abbildung 3.1: Normiertes Kosinus- ¨ Ahnlichkeitsmaß in der Ebene zum Vektor (1, 1) T

Das sog. F 1 -Maß hingegen berechnet das harmonische Mittel dieser beiden Maße und Dice- ¨ ist auch als ” Ahnlichkeitsmaß“ bekannt:

(3.23)

Angenommen, die Vektorelemente der zu vergleichenden Vektoren beschreiben, ob ein Punkt genau zu einem Cluster geh¨ ort oder nicht. Dann beschreibt das Dice- ¨ Ahnlichkeitsmaß genau den Anteil der Punkte, die beiden Clustern angeh¨ oren. Naturgem¨ aß kann so ein Anteil nur im Bereich zwischen 0 und 1 bewegen, womit dieses ¨ Ahnlichkeitsmaß normiert ist.

(3.24)

Das Jaccard- ¨ Ahnlichkeitsmaß [Jac01] ¨ ahnelt dem Dice- ¨ Ahnlichkeitsmaß, jedoch werden hier die Randbereiche anders gewichtet: Sowohl sehr kleine als auch große Schnittmengen f¨ uhren zu einer st¨ arkeren Un¨ ahnlichkeit verglichen zum Dice-Maß. Es ist auch normiert.

Kapitel 3. Entwicklung von ¨

Abbildung 3.2: Jaccard- ¨ Ahnlichkeitsmaß in der Ebene zum Vektor (1, 1) T

Des weiteren wurde der Rand-Index [Ran71] vorgeschlagen, welcher der Korrektklassifikationsrate aus dem Information Retrieval entspricht. Er gleicht dem quadrierten normierten euklidischen ¨ Ahnlichkeitsmaß, welches im n¨ achsten Abschnitt vorgestellt wird:

(3.25)

Alle bisherigen vorgestellten Indexe sind normierte ¨ Ahnlichkeitsfuntionen gewesen; in

[Mir96] wurde der sog. Mirkin-Index vorgeschlagen, der als Metrik fungiert. Er entspricht einer skalierten und quadrierten euklidischen Distanzfunktion:

d M irkin ( u, v) = 2 · (n 01 + n 10 ) = 2 · ( u − v) ² (3.26)

Des weiteren l¨ asst sich ein ¨ Ahnlichkeitsmaß aus einem fuzzifiziertem logischen Ausdruck definieren, welches den Vektorenvergleich auf den Vergleich einzelner Vektorelemente reduziert. Dazu seien u und v zwei Vektoren mit den Elementen u 1 , u 2 , . . . , u ⁿ bzw. v 1 , v 2 , . . . , v n . Diese sind gleich, wenn die einzelnen Elemente sich gleichen:

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 22

(3.27) ( u = v) ↔ (u 1 = v 1 ) ∧ (u 2 = v 2 ) ∧ . . . ∧ (u n = v n )

l¨ asst sich Gleichung 3.27 fuzzyfizieren: F¨ ur verschieden Fuzzy-T-Normen sei auf Abschnitt 2.1.2 verwiesen; eine normierte ¨ Ahnlichkeitsfunktion f¨ ur den Vergleichsoperator

ist im einfachsten Falle der Differenzbetrag der beiden Elemente. Aber es ist auch eine Verallgemeinerung dieser Funktion durch einen Parameter p = 0 denkbar:

s ^{F uzzy} L ogic (u i , v i ) = 1 − |u i − v i | ^p (3.28)

Die Normierung ergibt sich dadurch, das die Elemente x und y entsprechend der Definition des Zugeh¨ origkeitsgrades nur zwischen 0 und 1 liegen k¨ onnen; der Differenzbetrag hat den gleichen Wertebereich genauso wie eine Potenzierung desselben. Ein weiteres normiertes ¨ Ahnlichkeitsmaß erh¨ alt man, indem man beide Cluster-Vektoren u und v als diskrete Fuzzy-Sets interpretiert und daf¨ ur ¨ Ahnlichkeitsmaße nach [Kun00] bzw. [DP80] verwendet:

(3.29)

Der Operator symbolisiert die symmetrische Differenz der beiden Fuzzy-Sets:

(3.30)

∆ erzeugt die Differenzmenge der Vereinigungsmenge mit der Schnittmenge:

(3.31)

Als letzte M¨ oglichkeit wird aus der symmetrische Differenz beider Fuzzy-Sets das Supremum bzgl. der Zugeh¨ origkeiten bestimmt:

(3.32) s F uzzy−Set4 ( u, v) = 1 − sup (|u i − v i |) ^u i ∈ ^u,v i ∈ v

Als letzte ¨ Ahnlichkeitsfunktion in diesem Abschnitt sei das drastische ¨ Ahnlichkeitsmaß definiert, welche eine Gleichheitsrelation f¨ ur Vektoren darstellt und f¨ ur den Nachweis formaler Eigenschaften n¨ utzlich ist:

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 23

(3.33)

F¨ ur praktische Anwendungen im Fuzzy-Bereich ist es eher unbrauchbar, da es nur die beiden Ergebnisse ” Eins“ und ” Null“ liefert und somit die Fuzzy-Algorithmen zu Algorithmen der klassischen Logik degeneriert.

3.3.1 Distanzfunktionen als normierte ¨ Ahnlichkeitsmaße

Aus Abschnitt 3.1.2 ist bekannt, dass Semi-Pseudo-Metriken in ¨ Ahnlichkeitsfunktionen

umgewandelt werden k¨ onnen. Deshalb werden im Folgenden einige dieser Funktionen und deren Supremum s im n-dimensionalen Einheitshyperkubus betrachtet: Die Minkowski-Metrik wird durch einen Parameter p spezifiziert; f¨ ur p = 1 erh¨ alt man die Manhattan-Abstandsfunktion, f¨ ur p = 2 den euklidischen Abstand und f¨ ur p → ∞ den Tschebyschow-Abstand der auch Maximum-Abstand genannt wird:

(3.34)

Das Supremum s der Minkowski-Abstandsfunktion im n-dimensionalen Einheitshyperw¨ urfel entsteht unter anderem zwischen dem o-Vektor und dem (1, 1, ..., 1) ^T -Vektor

√

n. Daraus ergibt sich folgende normierte ¨ und betr¨ agt s = ^p Ahnlichkeitsfunktion:

(3.35)

3.3.2 Skalierung von ¨ Ahnlichkeitsmaßen

Sp¨ atere Anwendungen erzeugen und verkn¨ upfen sehr viele ¨ ahnliche Cluster, wie beispielsweise das sp¨ ater in Kapitel 5 vorgestellte Bildklassifikationsszenario: Die Verkn¨ upfung kann beispielsweise durch eine T-Conorm realisiert werden, was auch die im n¨ achsten Kapitel vorgestellte S-Distanz nutzt.

Werden jedoch sehr ¨ ahnliche Cluster mit einer ung¨ unstigen T-Norm verkn¨ upft, wird das Ergebnis in Richtung volle ¨ Ahnlichkeit streben. Am Beispiel sei dies mit der T-Conorm ⊥ prod und einem Zugeh¨ origkeitsgrad a = (1 − t) nahe 1 demonstriert:

⊥ prod (a, a) = ⊥ prod (1 − t, 1 − t) = 1 − t ² (3.36)

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 24

Insbesondere bei der Verkn¨ upfung von vielen Cluster¨ ahnlichkeitsergebnissen kann entsprechende Software in numerische Schwierigkeiten gelangen und als Endergebnis ergibt sich volle ¨ Ahnlichkeit. Zur Vermeidung kann man bei den ¨ Ahnlichkeitsfunktionen f¨ ur zwei Clustervektoren

ansetzen und deren Un¨ ahnlichkeit mit einem Faktor p > 1 betonen. Sei s ( u, v) eine solche ¨ Ahnlichkeitsfunktion; die Funktion s( u, v, p) ermittelt dann gleiche oder kleinere ¨ Ahnlichkeitgrade als die Funktion s ( u, v):

s(x, y, p) = s ( u, v) ^p (3.37)

Umgekehrt ist es auch m¨ oglich f¨ ur einen Faktor (0 < p < 1) die ¨ Ahnlichkeitsfunktionen so zu skalieren, dass deren Ergebnisse ¨ ahnlicher werden. Trotz dieser Skalierungsm¨ oglichkeit bleiben einige T-Normen im praktischen Sinne bei Verkn¨ upfung vieler Parameter unbrauchbar, wie beispielsweise die T-Conorm ⊥ luka : Sie summiert alle ¨ Ahnlichkeitgrade auf bis 1 erreicht ist; bei einer gr¨ oßeren Anzahl an Clustern m¨ usste der Skalierungfaktor p dann sehr groß gew¨ ahlt werden. Nebenwirkungen sind dann numerische Ungenauigkeiten im Null-Bereich bei der ¨ Ahnlichkeitsfunktionsberechnung f¨ ur Fuzzy-Cluster-Partitionen: Diese k¨ onnen dann vollkommen un¨ ahnlich werden.

3.3.3 Eigenschaftsbeschr¨ ankungen von Cluster-Partitionen in dieser Arbeit

Wie in diesem Abschnitt gezeigt, existieren eine Vielzahl von Ans¨ atzen, ¨ Ahnlichkeitsfunktionen zu entwerfen und definieren. Im Folgenden wird sich diese Arbeit aber nur auf bestimmte Partitionen konzentrieren: Es wird eine bijektive Abbildung endlich vieler Datenpunkte im n-dimensionalen Einheitskubus zwischen den beiden Partitionen vorausgesetzt, jedoch ist die Clusterzahl beider Partitionen frei definierbar. Dabei implizieren diese Voraussetzungen auch Funktionen, die diese nicht ben¨ otigen: So wird sp¨ ater ein Entropie-basiertes ¨ Ahnlichkeitsmaß vorgestellt, welches die genannten bijektive Abbildungen ignoriert.

Des weiteren wird von Fuzzy-Clustern ausgegangen, welche nat¨ urlich den Nicht-Fuzzy-Fall implizieren. Die Summe aller Zugeh¨ origkeiten eines Datenpunktes zu allen Clustern muss 1 ergeben, wobei leere Cluster und Zugeh¨ origkeiten kleiner 0 ausgeschlossen sind. Alle Cluster sind als Vektoren im n-dimensionalen Einheitskubus darstellbar; die geometrische Lage der Datenpunkte im Raum wird hingegen bei den Cluster- ¨ Ahnlichkeitsfunktionen nicht beachtet.

Dieser beschriebene Fall ist insbesondere interessant, wenn man unterschiedlich Clus-teralgorithmen an einer Datensammlung vergleichen m¨ ochte: Die Datenpunkte gleichen sich, w¨ ahrend unterschiedliche Clusteralgorithmen unterschiedlich viele Cluster generie- ren k¨ onnen.

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 25

3.4 S-Distanz

Aus der Mengenlehre l¨ asst sich ein relationsbasiertes ¨ Ahnlichkeitsmaß ableiten: Basierend

auf der logischen Teilmengenrelation sind zwei Mengen A und B gleich, wenn folgende Eigenschaft erf¨ ullt ist:

(3.38) (A = B) ↔ (A ⊆ B) ∧ (B ⊆ A)

Die Teilmengenrelation ⊆ ist in der klassischen Logik so definiert, dass in einer Obermenge B alle Objekte ihrer Teilmenge A enthalten sein m¨ ussen:

(3.39) (A ⊆ B) ↔ (∀a ∈ A|∃ b ∈ B|a = b)

Die Teilmengenrelation der klassischen Logik ⊆ nach 3.39 l¨ asst sich auch als aussagenlogischer Ausdruck definieren. Dazu seien A = {a 1 , . . . , a m } und B = {b 1 , . . . , b n } zwei endliche Mengen von Objekten. A ist Teilmenge von B, wenn gilt:

(3.40)

Die Fuzzy- ¨ Ahnlichkeitsfunktion ergibt sich durch Fuzzifizierung der Gleichungen 3.38 und 3.40, durch die Bestimmung eine T-Norm bzw. deren dualer T-Conorm ⊥ und durch Definition eines Vergleichsoperators s(a i , b i ), welches eine normierte ¨ Ahnlichkeitsfunktion f¨ ur zwei Objekte ist.

Im Folgenden werden als Objektmengen Fuzzy-Cluster-Konfigurationen und Fuzzy-Cluster-Vektoren als Objekte verwendet; dieses ¨ Ahnlichkeitsmaß sei dann als S-Distanz ² bezeichnet.

Seien U und V die beiden zu vergleichenden Cluster-Partitionen die jeweils n bzw. v j enthalten:

(3.41)

² Die S-Distanz kann sowohl als ¨ Ahnlichkeitsmaß als auch als Semi-Pseudo-Distanzfunktion fungieren.

Um eine einheitliche Form zu wahren, wird sie in beiden Auspr¨ agungen im Folgenden kurz S-Distanz genannt; sie ist jedoch keine Distanzfunktion oder Metrik nach Definition 4.

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 26

Die im zweiten Schritt erfolgte Fuzzifizierung der Gleichung 3.38 sichert die Symmetrieeigenschaft des endg¨ ultigen ¨ Ahnlichkeitsmaß f¨ ur Objektmengen:

(3.42) S (V, U ))

Als umgewandelte Semi-Pseudo-Abstandsfunktion hat sie folgende Form:

(3.43) D S (U, V ) = 1 − S S (U, V )

3.4.1 Formale Eigenschaften

Die S-Distanz erf¨ ullt f¨ ur alle T-Normen und alle ¨ Ahnlichkeitsfunktionen die Eigenschaft der Selbstidentit¨ at: Diese gleiche Eigenschaft der ¨ Ahnlichkeitsfunktionen f¨ ur Clustervek-toren sorgt daf¨ ur, dass unter den n Parametern, die jede T-Conorm in der S-Distanz-Gleichung miteinander verkn¨ upft, mindestens ein Einselement darunter ist. Sei dazu U eine Clustermenge mit n Elementen u i .

(3.44)

Die T-Conorm-Verkn¨ upfung eines Einselementes mit beliebig vielen anderen Elementen ergibt nach Gleichung 2.5 wieder das Einselement. Im n¨ achsten Schritt werden dann die n Einselemente mit einer T-Norm verkn¨ upft, welche wieder aufgrund der Neutrale-Element-Eigenschaft nach Gleichungen 2.1 Eins ergibt. Im letzten Schritt der symmetrischen Verkn¨ upfung sichert wieder diese T-Norm-Eigenschaft die volle ¨ Ahnlichkeit bzw.

Selbstidentit¨ at der Fuzzy-Cluster-Partition

Die Symmetrieeigenschaft der S-Distanz ist gegeben, da sie auf der Symmetrieeigenschaft der T-Norm im letzten Gleichungsschritt 3.42 zur¨ uckzuf¨ uhren ist. Die S-Distanz erf¨ ullt unter keiner Parametrisierung die Positivit¨ atseigenschaft, da zwei Fuzzy-Cluster-Konfigurationen existieren k¨ onnen, in der zu jedem Cluster aus einer Multimenge genau der gleiche Cluster in der Vergleichsmenge gefunden werden kann, ohne dass diese beiden Clustermultimengen gleich sein m¨ ussen. Als Beispiel seien U und V zwei Cluster-Konfiguration mit drei bzw. vier Clustern zu nur einem einzigen Datenpunkt:

(3.45)

Kapitel 3. Entwicklung von ¨

Analog gelten dann die gleichen ¨

um die volle ¨

Die Entstehung von solchen Multimengen, die einige Elemente mehrfach haben, k¨ onnen beispielsweise bei kugelf¨ ormigen Clustern entstehen, wenn zwei Cluster das gleiche Zentrum besitzen. Aber auch bei konstruierten Randf¨ allen ist die Entstehung mit unterschiedlichen Clustermittelpunkten m¨ oglich, wie Abbildung 3.3 zeigt.

Abbildung 3.3: Zwei Cluster mit gleichen Zugeh¨ origkeitsvektoren und unterschiedlichen Zentren

Zu bemerken ist, dass es je nach eingesetzten ¨ Ahnlichkeitsmaß f¨ ur Clustervektoren

noch deutlich mehr Konfigurationen existieren k¨ onnen, in der trotz unterschiedlichen Cluster-Mengen die volle ¨ Ahnlichkeit erreicht wird. Als Beispiel sei das Kosinus- ¨ Ahnlichkeitsmaß genannt, welches f¨ ur jeden Vektor nur einen linear abh¨ angigen Clustervektor in der Vergleichsmenge ben¨ otigt, da nur die Richtung der Vektoren und nicht deren L¨ ange f¨ ur die ¨ Ahnlichkeitsbestimmung ber¨ ucksichtigt wird. Die Wahl der T-Norm und der zugrundeliegenden ¨ Ahnlichkeitsfunktion f¨ ur Cluster-vektoren ist entscheidend, ob die in eine Abstandsfunktion umgewandelte S-Distanz die Dreiecksungleichung erf¨ ullt. Als Beispiel sei die drastische ¨ Ahnlichkeitsfunktion genannt,

welche unter allen T-Normen die Dreiecksungleichung erf¨ ullt. Aufgrund der neutralen Elementeigenschaft und Monotonieeigenschaft der T-Norm und T-Conorm und da die drastische ¨

Null“ und ” Eins“ wiedergibt, existiert nur ein einziges hypothetischen Szenario, in dem ”

die Dreiecksungleichung verletzt wird. Seien U , V und W jeweils eine Multimenge an Clustervektoren, welche f¨ ur diese S-Distanz folgende Ergebnisse liefert:

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 28

(3.46)

Dieses Ergebnis kommt ausschließlich zustande, wenn folgende Bedingungen erf¨ ullt sind:

(3.47)

(3.48) (3.49)

Aufgrund der Transitivit¨ at der Gleichheitrelation m¨ usste aber nach Gleichungen 3.47 und 3.48 dann folgende Implikation erf¨ ullt sein:

(3.50)

Dieses widerspricht jedoch Annahme nach Gleichung 3.49. Somit gilt die Dreiecksungleichung f¨ ur diese S-Distanz-Parametrisierung.

Gegenbeispiele, in der bestimmte Parametrisierungen die Dreiecksungleichung verletzten, werden im Abschnitt 4.2 erzeugt: So erf¨ ullt beispielsweise die T-Norm ^Lukasiewicz in Kombination mit dem Jaccard- ¨ Ahnlichkeitsmaß die Dreiecksungleichung nicht.

Somit ist die S-Distanz mit speziellen Parametrisierungen ein Pseudo-Distanzmaß und im Allgemeinen sogar nur ein Semi-Pseudo-Distanzmaß.

3.4.2 Komplexit¨ at

Der genaue Aufwand zur Berechnung einer S-Distanz h¨ angt zwar prinzipiell auch von der verwendeten T-Norm und der ¨ Ahnlichkeitsfunktion ab, jedoch haben alle in Kapitel 2.1.1 vorgestellten T-Normen konstanten Aufwand bzw. ist der Aufwand der ¨ Ahnlichkeitsfunktionen meist linear von der Dimension der Vektoren und somit meist linear von der Punktanzahl n abh¨ angig. Bei Verwendung geeigneter Datenstrukturen kann f¨ ur einige Parametrisierungen die Komplexit¨ at jedoch auch reduziert werden. Als Beispiel sei das drastische Distanzmaß genannt, welches zwei Vektoren auf Gleichheit untersucht. Bei Verwendung geeigneter Hashfunktionen w¨ ahrend der Vektorgenerierung kann der Vergleich in den meisten F¨ allen auf konstanten Aufwand reduziert werden. Im Allgemeinen ist es jedoch schwierig, f¨ ur alle ¨ Ahnlichkeitsfunktionen Optimierungen zu finden. Unter der Annahme, dass eine T-Norm mit konstanten bzw. eine ¨ Ahn-

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 29

lichkeitsfunktion mit linearen Aufwand verwendet wird und das p und q die Anzahl der Cluster in beiden Clusterpartitionen ist, betr¨ agt die obere Komplexit¨ atsschranke ³ :

(3.51) S S ∈ O(p · q · n)

Die Faktoren p und q fließen in die Komplexit¨ atsberechnung linear ein, da jeder Cluster einer Partition mit jedem Cluster der zweiten Partition mit einer ¨ Ahnlichkeitsfunktion verglichen werden muss.

3.4.3 Rekursive Anwendung auf Multimengen und Listen

Das S-Distanzmaß ist geeignet, jegliche Mengen zu vergleichen: Hauptparameter ist eine definierte ¨ Ahnlichkeitsfunktion f¨ ur zwei Objekte dieser Menge. Da die S-Distanz ein ¨ Ahnlichkeitsmaß f¨ ur zwei Objektmengen ist, kann es auch selbst als Funktionsparameter fungieren: So lassen sich beispielsweise zwei Multimengen von Fuzzy-Cluster-Konfigurationen vergleichen. Ein Beispiel einer solchen Multimenge wird sp¨ ater in Kapitel 5 vorgestellt: Dort w¨ are solch eine Multimenge eine komplette Bildersammlung, zu der dann eine zweite ¨ ahnliche Bildersammlung gesucht werden k¨ onnte. In einigen Anwendungen ist es jedoch nicht sinnvoll, zwei geordnete Mengen bzw. Listen ungeordnet zu vergleichen: Genau wie bei dem Vektorenvergleich nach Gleichung 3.27, sollte in so einem Fall nur ein Element mit dem korrespondierenden Element aus der zweiten Liste verglichen werden und alle Ergebnisse per T-Norm verkn¨ upft werden. Mit diesen beiden Konzepten lassen sich dann beliebig komplex aggregierte Fuzzy-Objektstrukturen vergleichen, da sie beide rekursiv anwendbar sind. Als Parameter wird nur eine T-Norm und eine normierte ¨ Ahnlichkeitsfunktion f¨ ur die Bl¨ atter des Objektbaumes ben¨ otigt.

3.5 B-Distanz

Die B-Distanz ⁴ ist ein Abstandsmaß f¨ ur zwei Fuzzy-Cluster-Konfiguration U und V , welches f¨ ur jeden Cluster aus Menge U den Cluster aus Menge V bestimmt, der die gr¨ oßte ¨ Ahnlichkeit bez¨ uglich einer Fuzzy-Implikationsfunktion aufweist ⁵ .

³ Zur Beschreibung der Komplexit¨ aten wird die O-Notation verwendet. Hierbei sei auf [Knu76] verwiesen.

⁴ Die B-Distanz wird im Folgenden auch als umgewandeltes ¨ Ahnlichkeitsfunktion als B-Distanz bezeichnet. Da sie die u. a. Positivit¨ atseigenschaft nicht erf¨ ullt, ist sie trotz dieser Bezeichnung keine Distanzfunktion oder Metrik nach Definition 4.

⁵ Dieses Maß wurde von Dipl.-Inf. J¨ urgen Beringer entwickelt ohne dass es bisher publiziert worden ist

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 30

3.5.1 Definition

Dieses Abstandsmaß wird durch eine sog. Fuzzy-Implikation f¨ ur Clustervektoren parametrisiert. Diese Funktion l¨ asst sich durch Wahl einer klassischen Fuzzy-Implikation definieren: Seien u i und v i die Elemente der Clustervektoren u und v. Dann sei u → v das arithmetische Mittel der Implikationen:

(3.52)

Diese ¨ Ahnlichkeitsfunktion ist eine normierte unter Zulassung leerer Cluster: Sie erreicht ihre h¨ ochste Un¨ ahnlichkeit bzw. ¨ Ahnlichkeit, wenn alle Elemente aus u bzw. v mit

vollen Zugeh¨ origkeitsgraden belegt werden. Im Folgenden wird sie jedoch als Abstandsfunktion mit Supremum n verwendet. Die ben¨ otigte Umwandlung erfolgt nach 3.5 und ergibt:

(3.53)

Wie eingangs erw¨ ahnt, wird das Clusterpaar mit der gr¨ oßten ¨ Ahnlichkeit bzw. nun

das mit dem kleinsten Abstand gesucht. Alle so ermittelten Abst¨ ande werden additiv verkn¨ upft und das Ergebnis auf das Intervall [0..1] normiert:

(3.54)

Die Normierung dieser Abstandsfunktion gelingt dadurch, dass die Summierung aller Abst¨ ande h¨ ochstens n ergibt: Dazu betrachten wir die Fuzzy-Implikation n¨ aher: Insgesamt gibt es drei Klassen von solchen Implikationen: Die sog. S-Implikation wird durch Fuzzifizierung des entsprechenden aussagenlogischen Ausdrucks generiert:

(3.55) (x → y) = ¬(x ∧ ¬y) = (¬x ∨ y)

Bei Verwendung der T-Conorm ⊥ gilt folgende Gleichung:

(3.56) (x → y) = ⊥(1 − x, y)

Die Monotonieeigenschaft einer T-Conorm nach 2.5 kombiniert mit der Eigenschaft des neutralen Elementes ergibt, dass nach der Verkn¨ upfung zweier Elemente mit der

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 31

T-Conorm das Ergebnis mindestens so groß sein muss wie der erste Parameter. Daraus resultiert folgende Ungleichung:

(3.57) (x → y) ≥ 1 − x

Daraus folgt f¨ ur Gleichung 3.53, dass d( u, v) h¨ ochstens die Summe aller Zugeh¨ origkeitsgrade aus Clustervektor u erreichen kann:

(3.58)

Die Summierung aller Abst¨ ande der Clustervektoren aus Menge U zu entsprechenden Vektoren aus der Menge V nach Gleichung 3.54 ergibt als Gesamtabstand h¨ ochstens die Summe aller Zugeh¨ origkeitsgrade aller Cluster aus der Menge U : diese ist per Definition genau die Dimension n der einzelnen Clustervektoren. Die anschließende Skalierung durch den Quotienten n ergibt dann die angestrebte Normierung.

Im letzten Schritt gilt es noch, die Symmetrieeigenschaft f¨ ur dieses Abstandsmaß herzustellen; dazu wird die normierte Abstandsfunktion mit der T-Conorm ⊥ verkn¨ upft:

(3.59) B (V, U ))

In sp¨ ateren Kapiteln werden vergleichende Tests der ¨ Ahnlichkeitsfunktionen vollzogen. Um die B-Distanz direkt mit der S-Distanz vergleichen zu k¨ onnen, wird diese in den folgenden Kapiteln als ¨ Ahnlichkeitsfunktion genutzt:

(3.60) S B (U, V ) = 1 − D B (U, V )

3.5.2 Weitere Implikationsklassen

Bei der Definition der B-Distanz ist die Normierungseigenschaft dadurch garantiert, dass die Fuzzy-Implikation die Ungleichung 3.57 erf¨ ullt. Neben der verwendeten S-Implikation existieren jedoch noch weitere Implikationsklassen, die daf¨ ur m¨ oglicherweise geeignet sind. Diese werden hier untersucht; f¨ ur deren Definition sei auf [Low96] verwiesen. Neben der S-Implikation existiert noch die Klasse der sog. R-Implikationen. Diese garantiert, dass das Implikationsergebnis ” 1“ ergibt sobald x ≤ y gilt:

(3.61) (x → y) = sup{z||(x, z) ≤ y}

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 32

Bei der beispielsweisen Verwendung der T-Norm P rod ergibt sich f¨ ur die so parametrisierte R-Implikation die sog. Gaines-Implikation:

(3.62)

F¨ ur gilt die Ungleichung 3.57 nicht, was beispielsweise die beiden Parameter x = 0.5 und y = 0 zeigen. Dadurch ist diese Implikationsklasse im Allgemeinen ungeeignet, die angestrebte Normierungseigenschaft zu erf¨ ullen. Die dritte Klasse ist die Klasse der sog. QL-Implikationen:

(3.63) (x → y) = ⊥(1 − x, (x, y))

Diese Klasse erf¨ ullt im Allgemeinen die Ungleichung 3.57, da das Funktionsergebnis einer T-Conorm mindestens den Wert ihrer verwendeteten Parameter erreichen muss. Somit erreicht diese Implikation mindestens (1 − x).

Im Folgenden wird die B-Distanz mit der Lukasiewicz-Implikation parametrisiert, welche durch Anwendung der T-Conorm ⊥ Lukasiewicz auf die Gleichung 3.56 erzeugt wird: Diese ist sowohl eine S- als auch eine R-Implikation und vereint somit beide Eigenschaften.

3.5.3 ¨ Ahnlichkeit zur S-Distanz

Beim Vergleich der B-Distanz zur S-Distanz f¨ allt auf, dass beide ¨ Ahnlichkeitsmaße im

Kern sehr ¨ ahnlich arbeiten: Alle Cluster aus Partition U werden mit allen Clustern der Partition V verglichen, die Ergebnisse verkn¨ upft und im letzten Schritt eine symmetrische Operation vollzogen. Der Hauptunterschied liegt darin, dass die B-Distanz nur mit Distanzmaßen arbeitet und selbst auch eins ist w¨ ahrend sich die S-Distanz auf ¨ Ahnlichkeitsmaßen basiert.

Wandelt man die B-Distanz nach Gleichung 3.60 in ein ¨ Ahnlichkeitsmaß um, so zeigt

sich, dass sie tats¨ achlich eine Teilmenge der S-Distanz ist, wenn man im Fuzzifizierungsschritt eine T-Norm zul¨ aßt, welche nicht dual zur verwendeten T-Conorm ist. Um dies zu zeigen, sei die aussagenlogischen Teilmengenbeziehung nach Gleichung 3.40 auf die die S-Distanz basiert, mit Hilfe der Demorganschen Gesetze so dargestellt, dass die ” Oder“- durch ” Und“-Verkn¨ upfungen und umgekehrt die ” Und“- duch ” Oder“-Verkn¨ upfungen ersetzt werden:

A ⊆ B ↔ ¬( ¬¬(¬(a 1 = b 1 ) ∧ ¬(a 1 = b 2 ) ∧ . . . ∧ ¬(a 1 = b n )) ∨

(3.64)

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 33

Durch die Fuzzifizierung dieser Gleichung werden die normierten ¨ Ahnlichkeitsmaße

der S-Distanz in normierte Abstandsmaße (1 − s(a i , b j ) = d(a i , b j )) umgewandelt. Die Objektmengen A und B seien wieder die Clusterpartitionen U und V mit den entspre- v j :

(3.65)

F¨ ur die B-Distanz werden nun die T-Norm M in und die T-Conorm ⊥ ^Lukasiewicz verwendet. Wie im vorherigen Abschnitt gezeigt, kann bei Verwendung einer ¨ Ahnlichkeitsfunktion, welche auf die S-Implikation basiert, bei der Aufaddierung aller Parameter h¨ ochstens 1 erreicht werden: Somit kann man diese T-Conorm in diesem speziellen Fall durch eine einfache Summation ersetzen:

(3.66)

Im letzten Schritt muss noch die Symmetrieeigenschaft gesichert werden. Auch hier finden die Demorganschen Gesetzte Anwendung, um die B-Distanz als S-Distanz darzustellen. Verwendet wird die T-Norm min

(3.67)

Da die B-Distanz bei Verwendung einer S-Implikation und Tolerierung nicht dualer T-Normen bzw. T-Conormen eine Teilmenge der S-Distanz ist, gelten auch deren formale Eigenschaften und Komplexit¨ atsbetrachtungen. Sie ist somit mindestens eine Semi-Pseudo-Distanz. Der im Abschnitt 4.2 verwendete Semi-Algorithmus zeigt, dass die mit der Lukasiewicz-Implikation parametrisierte B-Distanz die Dreiecksungleichung verletzt; ob es auch S-Implikationen gibt mit denen die B-Distanz diese Eigenschaft erf¨ ullt, ist jedoch offen.

3.6 M-Distanz

Aus der Informationstheorie existiert ein Entropie-basierter Ansatz, welcher in [Mei07] f¨ ur Nicht-Fuzzy-Cluster erarbeitet wird.

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 34

3.6.1 Definition

u i gew¨ ahlt. Die Wahrscheinlichkeit, dass dieser Punkt diesem Cluster geh¨ ort, ist:

n

(3.68)

F¨ ur eine Partition ist damit eine diskrete Zufallvariable definiert, f¨ ur die eine Entropie bestimmt werden kann. Die Entropie dieser Partition ist umso gr¨ oßer, je gleichm¨ aßiger die Datenpunkte ¨ uber die Cluster der Partition U verteilt sind:

(3.69)

Die Entropien der beiden Fuzzy-Cluster-Konfigurationen sind jetzt bereits vergleichbar; hierbei ist es sogar m¨ oglich, zwei Fuzzy-Partitionen mit unterschiedlicher Cluster-und unterschiedlicher Datenpunktanzahl zu verwenden.

Dennoch ist es sinnvoller, den Ansatz auf Clusterpaare in beiden Partitionen zu erweitern, da ansonsten die vorausgesetzte bijektive Abbildung der Datenpunkte unber¨ ucksichtigt bleibt. Sei aus Partition U bzw. V ein zuf¨ alliger von n Punkten gew¨ ahlt v j der jeweiligen Partition geh¨ ort, ist:

(3.70)

v j ) ist von den jeweiligen Gr¨ oßen der Clusterschnittmengen abh¨ angig. Hierf¨ ur definiert Meilˇ a eine Funktion namens ” Korreliernde Informationsfunktion f¨ ur

zwei Clusterpartitionen“, welche die durchschnittliche Unsicherheitsreduktion bestimmt, dass zwei Partition voneinander abh¨ angig sind:

(3.71)

Um die gesamte Unsicherheit zu bestimmen, ist noch die Bestimmung der additiven Verkn¨ upfung der jeweiligen Differenzmengen notwendig:

(3.72) V I(U, V ) = [H(U ) − I(U, V )] + [H(V ) − I(V, U )]

Kapitel 3. Entwicklung von ¨

Abbildung 3.4: Entropien der einzelnen Teilmengen und deren Verkn¨ upfungen

Diese Funktion heißt nach Meilˇ a ” Variation der Information zwischen zwei Cluster-

partitionen“. V I(U, V ) ist f¨ ur den Nicht-Fuzzy-Fall eine Metrik, da sie die Eigenschaften Positivit¨ at, Symmetrie und Dreiecksungleichung erf¨ ullt: f¨ ur die entsprechenden Nachweise sei auf [Mei07] verwiesen. 6

Leider ist es nicht m¨ oglich, diese Funktion auf Fuzzy-Cluster-Partitionen zu ¨ ubertragen, da die Eigenschaft der Selbstidentit¨ at im Allgemeinen nicht gegeben ist. Dies liegt darin begr¨ undet, dass f¨ ur zwei identische Fuzzy-Partitionen im Allgemeinen keine sichere Datenpunktzuordnung zu zwei Clustern m¨ oglich ist, da ein Punkt zu einer gewissen Wahrscheinlichkeit fast jedem Cluster angeh¨ ort. So besteht immer eine Restunsicherheit, dass ein Datenpunkt beispielsweise nicht immer zum Cluster mit dem h¨ ochsten Zugeh¨ origkeitsgrad zugeordnet werden kann.

Dieses impliziert jedoch, dass I(U, V ) nur im Nicht-Fuzzy-Fall die komplette Unsicherheit beseitigen kann, so dass immer H(U ) > I(U, U ) gilt, was zur Verletzung der Selbstidentit¨ atseigenschaft f¨ uhrt.

Da f¨ ur ein Semi-Pseudo-Distanzmaß diese Eigenschaft nach Definition 1 wesentlich ist und der Schwerpunkt dieser Arbeit auf Fuzzy-Cluster-Partitionen liegt, wird im Folgenden auf die Untersuchung dieser Funktion verzichtet. Um dennoch ein Entropie-basiertes Distanzmaß zu nutzen, sei eine vereinfachte ” M-Distanz“ definiert, welche die Absolutdifferenz der beiden Entropiewerte der Fuzzy-Partitionen darstellt:

(3.73) M (U, V ) = |H(U ) − H(V )|

⁶ In einem fr¨ uheren Paper von Meilˇ a ist eine vermeintlich funktionierende Erweiterung dieser Metrik auf Fuzzy-Cluster noch beschrieben. Die beschriebene Begr¨ undung, warum diese nicht funktioniert, stammt nach Korrespondenz auch von ihr.

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 36

Diese Funktion ist nicht normiert: Minimal betr¨ agt die Entropie Null, wenn einem Cluster alle Datenpunkte angeh¨ oren, was in keiner Unsicherheit bzgl. der Datenpunktzu-ordnung resultiert. Die h¨ ochste Unsicherheit hingegen ist bei vielen gleich gr¨ oßen Clustern zu verzeichnen: das Supremum des Distanzmaß ist dann durch die maximale Anzahl der Cluster in beiden Partitionen gegeben und betr¨ agt:

(3.74) M (U, V )) = log(max(|U |, |V |))

Die Normierung des ¨ Ahnlichkeitsmaßes impliziert die Spezifizierung der Basis des Logarithmus, welcher in der Entropieberechnung genutzt wird:

(3.75)

Der Normierung wurde noch insoweit modifiziert, dass bei zwei Ein-Cluster-Partitionen keine Division durch Null stattfindet, sondern letztendlich die volle ¨ Ahnlichkeit erzeugt wird.

3.6.2 Formale Eigenschaften

Die M-Distanz erf¨ ullt die Dreiecksungleichung, da sie auf eine beliebige Minkowski-Metrik im eindimensionalen Raum zur¨ uckzuf¨ uhren ist: Mittels dieser Metrikklasse wird der Abstand der Entropien bestimmt.

Hingegen ist die Eigenschaft der Positivit¨ at im Allgemeinen nicht gegeben, da bei der Berechnung der Entropie nur die Summe der Clustervektorelemente eines Clusters ber¨ ucksichtigt wird, jedoch nicht genau die einzelnen Elemente; als Gegenbeispiel sei folgende Partition genannt:

(3.76)

Somit ist diese Abstandsfunktion als Pseudo-Distanzmaß klassifiziert.

3.6.3 Komplexit¨ at

Dieses ¨ Ahnlichkeitsmaß vergleicht nicht direkt die Datenpunkte und Cluster der beiden Partitionen, sondern bestimmt nur deren Entropie und verkn¨ upft diese mittels des Diffe- renzbetrages, welche eine Operation mit konstanten Aufwand darstellt. Somit addieren

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 37

sich die beiden Komplexit¨ aten der einzelnen Partitionen zur Bestimmung des Gesamtauf-wandes. Sei p bzw. q die Anzahl der Cluster und n U bzw. n V die Anzahl der Datenpunkte in Partition U bzw. V und

(3.77) D M (U, V ) ∈ O(p · n U + q · n V )

Die M-Distanz hat im Allgemeinen eine geringere Laufzeit als die B-Distanz bzw. S-Distanz; sie eignet sich zur ¨ Ahnlichkeitsbestimmung sehr gr¨ oßer Datenmengen und sehr

vieler Cluster: Die Komplexit¨ at ist genauso groß, wie die Schreiboperation, die ben¨ otigt wird um die Clustervektoren zu speichern.

3.7 K-Distanz

Die K-Distanz ⁷ ist ein Abstandsmaß, welches auf der Idee basiert ⁸ , dass eine Clustermenge genau dann zu einer anderen Clustermenge gleich ist, wenn diese ausschließlich durch Teilung und Vereinigung von Clustern aus der Vergleichsmenge rekonstruieren l¨ asst. Die Teilung und Vereinigung folgt im linearen Sinne, d. h. sie entsteht durch Linearkombination der Cluster.

Sie ist das erste hier vorgestellte Distanzmaß, welches beide Clustermengen global betrachtet und nicht versucht, die Distanzberechnung auf den Vergleich vieler Clusterpaare zu reduzieren. Es geh¨ ort auch zur Klasse der Abstandsmaße, die eine bijektive Abbildung der Datenpunkte voraussetzen.

3.7.1 Definition

q } zwei Clustermengen mit p bzw. q Clustern,

welche verglichen werden sollen.

Ferner seien a i1 , ...a ip Koeffizienten, die eine Linearkombination repr¨ asentieren. Diese erzeugen einen Cluster ˜ C j :

(3.78)

Es soll der Cluster ˜ j ¨ ahnlich ist. ¨ Ahnlichkeit

in diesem Sinne sei die Minimierung der Quadratfehlersumme der elementweisen Zugeh¨ origkeitsdifferenzen.

⁷ Die K-Distanz wird im Folgenden auch als umgewandelte ¨ Ahnlichkeitsfunktion als K-Distanz bezeichnet. Da sie eine Semi-Pseudo-Distanzfunktion ist, ist sie trotz dieser Bezeichnung keine Distanzfunktion oder Metrik nach Definition 4.

⁸ Dieses Abstandsmaß ist von Prof. Dr. Frank Klawonn entwickelt worden ohne dass es bisher publi- ziert wurde

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 38

(3.79)

Insgesamt soll versucht werden, die Quadratfehlersumme global ¨ uber alle rekonstruierten Cluster zu minimieren:

(3.80)

Die Vereinigung aller aufgesplitteten Clusterfraktionen eines Clusters muss diesen wieder komplett rekonstruieren; eine Clusterfraktion darf dabei nicht negativ auf in die Zugeh¨ origkeitswerte auswirken k¨ onnen, d. h. sie darf nicht subtrahiert werden; dies stellen folgende Nebenbedingungen sicher:

(3.81) a ij ≥ 0

(3.82)

Diese beiden Nebenbedingungen implizieren eine weitere Nebenbedingung:

(3.83) a ij ≤ 1

Um die Symmetrieeigenschaft der Abstandsfunktion herzustellen, wird nicht nur die ¨ Ahnlichkeit von P zu Q berechnet, sondern umgekehrt auch von Q zu P. Der Abstand betr¨ agt letztendlich dann der gr¨ oßere Wert der beiden Ergebnisse:

(3.84) H (Q, P ))

3.7.2 Geometrische Interpretation

Aus diesen Nebenbedingungen l¨ asst sich der L¨ osungsraum geometrisch charakterisieren: Die Ungleichungen 3.81 und 3.83 spannen einen Hyperw¨ urfel der Dimension p · q auf. Des weiteren schneiden p Teilr¨ aume der Dimension q aus Gleichung 3.82 diesen W¨ urfel. Die Schnittmenge aller Teilr¨ aume und die des Hyperw¨ urfels bilden einen konvexen Polytop. In diesem wird nun der Punkt gesucht, der die Quadratfehlersumme nach 3.80 minimiert.

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 39

Dazu kann man dieses Polytop mit Hilfe von 3.78 in den Clusterraum abbilden; die Konvexit¨ at des Polytops und die Linearit¨ at der Abbildung bewirken, dass dieser wieder einen konvexen Polytop im Clusterraum bilden. Somit ist es f¨ ur eine vollst¨ andige Polytopdefinition ausreichend, die Eckpunkte abzubilden. Die Minimierung der Quadratfehlersumme eines einzelnen Clusters bzgl. Gleichung 3.79 unter Beachtung aller Nebenbedingungen entspricht der Minimierung des Abstan- j ein

entprechender Punkt F j auf dem Polytop bestimmt, zu dem der Abstand am geringsten ist: aufgrund der Konvexit¨ at des Polytops ist dieser eindeutig. L¨ asst sich der Cluster j .

Innerhalb des Polytops erfolgt ein Gradientenabstiegsverfahren, in der das Minimum der globalen Quadratfehlersummenfunktion nach Gleichung 3.80 gesucht wird. Startpunkte sind alle Punkte aus F . Es muss darauf geachtet werden, dass beim Gradientenabstiegsverfahren das Polytop nicht verlassen wird. Impliziert dies ein Richtungsvektor, so wird der neue Startwert dahingehend korrigiert, dass er auf der Polytoph¨ ulle gesetzt wird.

3.7.3 Erweiterung der ” Nichtnegativen kleinste Quadratfehlersummenmethode“

Wie die geometrische Interpretation aus dem vorherigen Abschnitt suggeriert, ist es ein komplexes Problem f¨ ur diese Abstandsfunktion einen Algorithmus neu zu entwickeln. Aus diesem Grunde wird im n¨ achsten Abschnitt das Problem in ein bekanntes abgebildet, zu dem bereits ein Algorithmus exisiert. In [CLL96], Kapitel 23 wird ein Algorithmus namens ” Nonnegative Least Squares (NNLS)“ beschrieben, zu deutsch ” Nichtnegative kleinste Quadratfehlersummenmethode“: Sei A eine n · m Matrix und x ein gesuchter L¨ osungsvektor, welcher dem Zielvektor b im Sinne der kleinsten Quadratfehlersumme m¨ oglichst erreichen soll:

(3.85) A · x ≈ b

Alle Elemente des x-Vektors seien nicht negativ:

(3.86) x ≥ 0

Der NNLS-Algorithmus arbeitet iterativ und kann das globale Minimum der Zielfunktion 3.85 beliebig dicht ann¨ ahern. F¨ ur eine genaue Beschreibung sei auf [CLL96] verwiesen.

Dieser Standardalgorithmus f¨ ur die Bestimmung der kleinsten Quadratfehlersum- me ist bereits in vielen anderen Arbeiten verwendet worden; hierbei sei beispielsweise

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 40

[Wan00], [Bra01] und [BT95] genannt, welche in den Bereichen Clustering, dynamische Verkehrsleitsysteme und Bestimmung von Partikelgr¨ oßen den Algorithmus zum Teil mit der im Folgenden beschriebenen -Erweiterung nutzten.

Des Weiteren existieren diverse Implementationen: im Mathematikprogramm Matlab, in Fortran und im Data Mining Packet Weka [Wek06] ist der NNLS-Algorithmus zu finden.

Der Algorithmus wird jetzt noch so erweitert, dass er lineare Nebenbedingungen akzeptiert. Die Erweiterung erfolgt analog der Erweiterung des sog. ” Least Square Problems“(LS), welche auch in [CLL96] und implementiert in Weka zu finden ist. Dazu sei C eine Matrix, in der die Koeffizienten f¨ ur die Nebenbedingungen abgelegt werden; d sei ein Vektor, in dem die Zielwerte der einzelnen Gleichungen kodiert sind. Folgende Nebenbedingung soll der Algorithmus dann erf¨ ullen:

(3.87) C · x = d

F¨ ur die Erweiterung ist die Definition eines neuen Operators notwendig: Sei ◦ ein Operator, der 2 Matrizen gleicher Spaltenanzahl oder 2 Vektoren zeilenweise zu einem neuer Matrix konkateniert. Die ersten n Zeilen entsprechen der Matrix A, die letzten m Zeilen der Matrix B:

(3.88) Q ⁽ⁿ A ⁺ⁿ B )·m = A ⁿ A ·m ◦ B ⁿ B ·m

C sei eine n · m Matrix und d ein Vektor der Dimension n. Ferner sei ein positiver Faktor nahe Null. Die Integration der Nebenbedingungen folgt durch stark gewichtete Faktoren in der Quadratfehlersummenberechnung. Dazu werden die eigentlichen Optimierungskoeffizienten mit dem Faktor gewichtet und werden somit erst sekund¨ ar optimiert.

(3.89) C ◦ (A · )x − d ◦ (b · ) → min

Der L¨ osungsvektor x ist nach Ablauf des Algorithmus in zwei Teile zu spalten. Der obere Teil enth¨ alt die eigentliche L¨ osung, die jedoch nur g¨ ultig ist, wenn der untere Teil dem d-Vektor gleicht. Beispielsweise ist die L¨ osung ung¨ ultig, wenn das Gleichungssystem aus 3.87 keine L¨ osung enth¨ alt oder schlecht gew¨ ahlt worden ist.

3.7.4 Transformation des Abstandproblems

Nun gilt es, die Abstandsfunktion auf den erweiterten NNLS-Algorithmus abzubilden. Dabei ist die Konstruktion der Matrix A, in der die Zugeh¨ origkeitsgerade der Cluster aus P kodiert werden m¨ ussen, der aufwendigste Teil: die Matrix hat q · n Zeilen, p · n

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 41

Spalten und f¨ allt somit sehr groß aus: Man beachte insbesondere den quadratischen Anstieg zur Dimension der Datenpunkte. Die Matrixelemente werden nun so gew¨ ahlt, dass die Gleichungen von 3.78 abgebildet werden. m ij ist dabei der Zugeh¨ origkeitsgrad des i. Fuzzypunkts zum Cluster P j .

(3.90)

 

























A = 























Der Zielvektor b, zu dem die Quadratfehlersumme der L¨ osung minimal werden soll, entsteht durch Konkatenation der einzelnen Zielcluster-Vektoren:

b = C 2 ◦ · · · ◦ C (3.91)

q

Dieser Vektor hat die Dimension q · n wobei n die Anzahl der Fuzzypunkte in P bzw. Q ist.

Im zweiten Schritt werden die Nebenbedingungen aus Gleichung 3.82 integriert: Der Zielvektor d der Dimension n besteht ausschließlich aus Eins-Elementen; die zugeh¨ orige Matrix C mit n Zeilen und p · n Spalten wird wie folgt aufgebaut:

 

(3.92)

Nach Ablauf des erweiterten NNLS-Algorithmus, enth¨ alt der L¨ osungsvektor x alle Elemente von a 11 , . . . a pq . Mittels der Gleichungen 3.78, 3.80 und 3.84 l¨ asst sich letztend- lich der Abstand berechnen.

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 42

3.7.5 Epsilon-Wahl

Die Modifikation des NNLS-Algorithmus wirft die Frage auf, ob zu einem gegeben NNLS-Optimierungs-Problem ein existiert, welches geeignet ist, die gesuchte L¨ osung beliebig genau zu approximieren. Dazu muss man die Quadratfehlersummenbereiche sowohl f¨ ur die Nebenbedingungen als auch den Optimierungsbedingungen untersuchen: Seien err contraints (x) bzw. err optimize (x) die Funktionen, der die Quadratfehlersumme f¨ ur die Nebenbedingungen bzw. Optimierungsbedingungen f¨ ur einen gegeben x-Vektor berechnet; err all (x) sei die Gesamtfehlerfunktion, wobei die -Gewichtung mit ber¨ ucksichtigt wird:

(3.93) err contraints (x) = C · x − d

(3.94) err optimize (x) = A · x − b

err all (x) = err contraints + ² · err optimize (x) (3.95)

Des weiteren sei P eine Menge, die die Vektoren enth¨ alt, die alle Nebenbedingungen nach 3.93 erf¨ ullen. Durch diese Menge und δ sei eine beliebig kleine Umgebung E δ um diese L¨ osungspunkte definiert:

(3.96) E δ = {∀x ∈ D | (∃ p ∈ P | (|p − x|) ≤ δ)}

Zu zeigen: Es existiert f¨ ur jedes NNLS-Problem ein δ, so dass die Minimierung der Quadratfehlersumme der Gleichung 3.93 einen Vektor in dieser δ-Umgebung ergibt. Dazu sei x min der Vektor, welcher die Funktion 3.93 minimiert und sich nicht in der δ-Umgebung befindet:

(3.97) x min = inf (err constraints (x))

x∈D \ ^E δ

Die Quadratfehlersumme von x min kann nur dann einen Quadratfehlersummenwert der Nebenbedingungen eines Vektors aus der Menge E δ unterschreiten, wenn x min in einem lokalen Minimum liegt. In diesem Fall existiert aber ein δ, welches die L¨ osung auf dem Rand der δ-Umgebung verschiebt: δ kann beliebig klein werden und somit kann auch die Quadratfehlersumme von den Randpunkten der δ-Umgebung beliebig minimiert werden:

(3.98) ∀e ∈ E δ | lim (err contraints (e)) = 0

δ→0

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 43

Es existiert somit ein δ, welches einen definiten positiven Wert einnimmt. Innerhalb dieser Menge E δ wird nun die h¨ ochste Quadratfehlersumme nach Gleichung 3.94 gesucht, um ein passendes zu bestimmen. Es sei angenommen, dass dieser h¨ ochste Quadratfehlersummenwert q endlich ist:

(3.99)

Des weiteren nehmen wir an, dass der kleinste Quadratfehlersummenwert außerhalb der δ-Umgebung mindestens Null ergibt, was eine Eigenschaft der Quadratfehlersummenfunktion ist. Daraus ergibt sich dann ein Grenzwert f¨ ur :

(3.100)

Durch solch ein kann die Gesamtfehlersumme eines Vektors aus P nicht die eines Vektors außerhalb der δ-Umgebung ¨ uberschreiten.

Zu bemerken ist, dass hier zwar die Existenz eines solchen gezeigt wurde, jedoch ist es schwierig, dieses zu berechnen: Haupts¨ achlich wird dies durch die Berechnung der maximalen Quadratfehlersummenwert q einer potentiell unendlichen Menge P verhindert. In der Praxis ist es jedoch in den meisten F¨ allen ausreichend, nur ein sehr kleines zu w¨ ahlen: In der Implementation von Weka [Wek06] wird beispielsweise das Element mit dem kleinsten Absolutbetrag gr¨ oßer Null innerhalb der Matrix gesucht; das entspricht dann diesem Element multipliziert mit 10 ⁻¹⁰ .

3.7.6 Formale Eigenschaften

Die Selbstidentit¨ at der K-Distanz ist gegeben: Die Konkatenation der Transformationskoeffizienten in vektorieller Darstellung bilden in diesem Fall bei geeigneter Sortierung eine Einheitsmatrix. Die Symmetrieeigenschaft ist erf¨ ullt, da genau wie beim Entwurf der B- und S-Distanz der letzte Schritt im Berechnungsalgorithmus nach Gleichung 3.84 aus einer symmetrischen Verkn¨ upfung besteht.

Die K-Distanz ist dazu ausgelegt, die beiden Zugeh¨ origkeitsmatrizen bzw. deren Clus-tervektoren m¨ oglichst linear ¨ ahnlich aufeinander abzubilden. Dies gelingt aufgrund der Nebenbedingungen jedoch selten vollst¨ andig: Notwendige Bedingung ist, dass sowohl das gr¨ oßte als auch kleinste Element jeder Zugeh¨ origkeitsdimension in beiden Clustermengen vorkommt. Sind in diesem Fall die beiden Clustermengen ungleich, so ist die Positivit¨ atseigenschaft widerlegt.

Als entsprechendes Gegenbeispiel k¨ onnen wieder die beiden Mengen nach Gleichun- gen 3.45 dienen, welche auch die Positivit¨ atseigenschaft der B-Distanz und S-Distanz

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 44

widerlegen. Bei der K-Distanz gibt es jedoch auch Gegenbeispiele, in denen sich nicht alle Cluster in beiden Mengen wiederfinden lassen:

(3.101)

Die Dreiecksungleichung gilt f¨ ur die K-Distanz nicht: Im n¨ achsten Kapitel finden Tests mit Zufallsclustermengen statt, wobei Gegenbeispiele erzeugt werden konnten und welche im Anhang A dokumentiert sind. Somit ist die K-Distanz als Semi-Pseudo-Distanz-Funktion klassifiziert.

Zu bemerken ist, dass diese Distanzfunktion die einzige der drei hier vorgestellten ist, welche mit steigender Punktanzahl tendenziell h¨ ohere Distanzen feststellt. Um diese zu normieren ist zun¨ achst die Bestimmung des Supremums der Funktion in Abh¨ angigkeit der Cluster- und Punktanzahl notwendig:

Seien U und V Clusterpartitionen mit jeweils n Datenpunkten. Die Clusterpartition U habe nur ein Cluster zu dem alle Punkte voll angeh¨ oren; Clusterpartition V hingegen habe dagegen k gleiche Cluster: Jeder Datenpunkt geh¨ ort dann mit ¹ zu jedem Cluster

k

an.

Bei der Zielclusterbildung werden in beiden Partitionen U und V unabh¨ angig von den verwendeten Linearkoeffizienten keine Cluster erzeugt, welche nicht bereits in den Quellpartitionen schon vorzufinden ist. Die Berechnung der Distanz erfolgt somit nach:

2 1 2

(3.102)

Strebt die Clusterzahl k der Clusterpartition V gegen unendlich, so ergibt sich der maximale Abstand von n pro Cluster in der Quellpartition. Die Normierung der K-Distanz erfolgt somit nach:

(3.103)

3.7.7 Komplexit¨ at

Da der NNLS-Algorithmus ein iteratives Verfahren darstellt, ist es schwierig, eine obere Aufwandsgrenze festzuschreiben. Jedoch kann man zumindest die Gr¨ oße der Matrizen, welche als Parameter genutzt werden, untersuchen: So haben Matrix A und C nach der Konkatenation p · q · n ² + n Elemente, was einen zur Punktanzahl quadratischen und zur Clusteranzahl pro Partition linearen Aufwand f¨ ur die alleinige Erstellung der Matrizen bedeutet.

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 45

Zur Evaluation wurde ein Laufzeitexperiment gemacht, in dem sowohl die Anzahl der Datenpunkte als auch die Anzahl der Cluster pro Menge variiert worden ist. Pro Konfiguration wurden 100 Durchl¨ aufe mit jeweils unterschiedlichen mit Zufallsdaten berechnet: das arithmetische Mittel aller Durchl¨ aufe ⁹ repr¨ asentiert dann die Berechnungszeit f¨ ur eine Konfiguration.

Abbildung 3.5: K-Distanz: Berechnungszeit in Abh¨ angigkeit von Clusteranzahl und Dimension

Basierend auf diese Beobachtungen, ergibt sich wohl eine Komplexit¨ at, die zwischen quadratischen und kubischen Anstieg bzgl. der Datenpunkte liegt. Auch in Abh¨ angigkeit der Cluster steigt die Komplexit¨ at etwas st¨ arker an als bei der alleinigen Matrizengenerierung:

(3.104)

Als wichtigster Punkt zur Komplexit¨ at ist festzuhalten, dass diese mindestens quadratisch zur Datenpunktanzahl steigt, was den Algorithmus f¨ ur viele praktische Applikationen, wie beispielsweise das im sp¨ ateren Kapitel vorgestellte Bildklassifikationszenario, ungeeignet macht.

⁹ Die Testsoftware ist in Java geschrieben und lief unter einem Multitasking-Betriebssystem. Sowohl der Garbage-Collektor von der Java Virtual Maschine als auch andere Prozesse k¨ onnen w¨ ahrend der Berechnung einzelner Distanzen deren Laufzeit erh¨ oht haben. Erkennbar im Diagramm sind diesbez¨ uglich einzelne Peaks im sonst recht monotonen Verlauf der Graphen.

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 46

3.7.8 Varianten

Die grundlegende Idee der K-Distanz ist, dass zwei zu vergleichende Fuzzy-Clusterpartionen durch Teilung und anschließender Vereinigung ihrer Clusters angeglichen werden. Diese Operationen erfolgen ohne dass dieses in der Distanzfunktion selbst ber¨ ucksichtigt wird, obwohl gerade die exzessive Anwendung dieser Operationen eine uber die ¨ Aussage ¨ Ahnlichkeit zulassen w¨ urde. Daher ist es ¨ uberlegenswert, f¨ ur die Teilung und Vereinigung eine Kostenfunktion einzuf¨ uhren, um den Entwurf in dieser Hinsicht zu verbessern. Sehr naheliegend ist eine Bewertung der Linearkoeffizienten zu vollziehen. Um bei zwei identischen Clusterpartitionen den Nullabstand weiterhin zu garantieren, ist es notwendig, Koeffizienten mit den Werten 0 und 1 neutral zu gewichten. Beispiel f¨ ur eine entsprechende Kostenfunktion w¨ are:

(3.105)

Es ist zu ¨ uberlegen, diese Transformationskosten entweder mit einer bestimmten Gewichtung auf die Distanz heraufzuschlagen oder nur separat zu betrachten. Letztere M¨ oglichkeit scheint jedoch ungeeignet, da dann der urspr¨ ungliche Aspekt der vollst¨ andigen Rekonstruktion weitestgehend unber¨ ucksichtigt bleibt. Eine weitere Variante ist auf die Nebenbedingungen 3.82 zu verzichten: Momentan kann der gr¨ oßte und kleinste Cluster in beiden Partitionen nicht rekonstruiert werden, auch wenn diese nur eine Skalierung eines Quellclusters darstellt. Eine solche K-Distanz-Variante w¨ are somit in der Lage, diese Skalierungen besser zu ber¨ ucksichtigen. Werden sogar die Nebenbedingungen 3.81 ignoriert, so w¨ aren noch flexiblere Clusterrekonstruktionen m¨ oglich: So ist das Subtrahieren eines Clustervektors dann auch eine legale Operation um die quadratische Fehlersumme zum Zielcluster zu minimieren. Eine weitere M¨ oglichkeit ist die K-Distanz nur als Vorstufe zu nutzen, um die zwei Vergleichspartitionen weitestgehenst anzun¨ ahern: Dabei entstehen zu den beiden urspr¨ unglichen Fuzzy-Cluster-Partitionen dann jeweils eine Zielclusterpartition. Die Fehlerberechnung erfolgt dann nicht ¨ uber die Bestimmung der Quadratfehlersumme, sondern entweder durch eine S-Distanz oder da ja bereits eine bijektive Abbildung sowohl f¨ ur die Cluster als auch Datenpunkte existiert, direkt mit einer ” Counting-Pairs“-Clustervergleichsfunktion, wie in Abschnitt 3.3 beschrieben. Die beiden ¨ Ahnlichkeitsergebnisse der beiden Fuzzy-Cluster-Partitionspaare werden letztendlich noch symmetrisch beispielsweise mit einer T-Norm verkn¨ upft.

Des weiteren ist offen, ob die Minimierung der Quadratfehlersumme die geeignetste Zielfunktion ist, um die beiden Fuzzy-Clusterpartitionen anzun¨ ahern. Ebenso k¨ onnte man eine m¨ oglichst hohe ¨ Ahnlichkeit im Sinne einer der im Abschnitt 3.3 vorgestellten

Funktionen pl¨ adieren. Allerdings ist die Minimierung einer anderen Zielfunktion im ma-

Kapitel 3. Entwicklung von ¨ Ahnlichkeitsmaßen 47

thematischen Hinblick h¨ aufig wohl deutlich komplexer, da m¨ oglicherweise der Bereich der konvexen Optimierung verlassen wird.

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen 48

Kapitel 4

Evaluationstests in k ¨ unstlichen

Umgebungen

Um Abstandsfunktionen zu evaluieren, m¨ ussen Umgebungen geschaffen werden, in der die Ergebnistendenzen von guten Abstandsfunktionen vorhersagen lassen. In diesem Kapitel werden dazu verschiedene Methoden vorgestellt, welche zur Qualit¨ atsbeurteilung der ¨ Ahnlichkeitsfunktionen herangezogen werden k¨ onnen. Im Allgemeinen wird bei den folgenden Experimenten die B-Distanz mit der Lukasiwicz-Implikation, die K-Distanz, die M-Distanz und die S-Distanz mit diversen Parametrisierungen verwendet.

4.1 Ring-Methode

Gegeben seien mehrere Datenpunkte im n-dimensionalen Raum, die einen gleichm¨ aßigen Ring ergeben. Des weiteren wird eine Variante des Fuzzy C-Means Algorithmus eingesetzt, in der die Cluster-Zentren fest vorgegeben sind. Es werden k ≥ 2 Cluster generiert, deren Zentrum auf dem Ringrand liegt, wobei die Abst¨ ande zwischen den Zentren maximiert werden.

Die Clusterzentren werden sukzessiv um den Ringmittelpunkt gedreht und der Ab-stand zur Urkonfiguration bestimmt. Bei einer guten ¨ Ahnlichkeitsfunktion sollte die ¨ Ahnlichkeit streng monoton fallen, bis bei 360 ^◦ der gr¨ oßte Abstand erreicht worden ist. Von 360 ^◦ bis 360 ^◦ sollte nun ein

2·k 2·k k

entsprechend gespiegeltes Funktionsverhalten zu beobachten sein. Erwartet wird, dass sich dieses Verhalten sich periodisch k mal wiederholt, bis die Clusterzentren ihren Ausgangspunkt wieder erreicht haben.

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen 49

4.1.1 Auswertung

Die Auswertung aller bisher untersuchten ¨ Ahnlichkeitsmaße ergibt, dass die geforderten Eigenschaften Monotonie, Maximum bei 360 ^◦

eingehalten werden. Die Auswertung ergibt auch Unterschiede bzgl. Verhalten bei den Maxima und Minima der Funktion und unterschiedliche Skalierungen: So unterscheiden sich viele Funktionen vom erreichten Infimum; das theoretische Minimum von Null wird bei diesen Experiment nie erzeugt.

B-Distanz

Die B-Distanz zeigt einen fast linearen Verlauf zu den Extrempunkten; asymptotische N¨ aherungen sind nicht zu beobachten; insgesamt ¨ ahnelt der Verlauf den mit Minkowski-Metriken und der T-Norm M in instanziierten S-Distanzen.

S-Distanz

Bei der S-Distanz wurden vier verschiedene Minkowski-Metriken und vier ” nat¨ urliche“ ¨ Ahnlichkeitsfunktionen jeweils mit zwei T-Normen getestet: Konkret wurde der Manhattan-Abstand (p = 1), der euklidische Abstand (p = 2), die Minkowski-Metrik mit p = 10, der Maximumabstand (p → ∞) sowie das Fuzzy-Set- ¹ , Kosinus-, Dice- und

¹ Als Fuzzy-Set- ¨ Ahnlichkeitsmaß wird das nach Gleichung 3.29 verwendet.

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen 50

Jaccard- ¨ Ahnlichkeitsmaß unter der T-Norm M in und P rod validiert. Diese oder eine sehr ¨ ahnliche Konfiguration wird in nachfolgenden Experimenten auch verwendet.

Abbildung 4.2: Ringmethode: S-Distanz ( M in ) mit Minkowski-Metriken

Abbildung 4.3: Ringmethode: S-Distanz ( P rod ) mit Minkowski-Metriken

Bei der Verwendung von Minkowski-Metriken als zugrundeliegende ¨ Ahnlichkeitsfunktion f¨ ur S-Distanzen zeigt sich ein sehr ¨ ahnliches Verhalten f¨ ur alle untersuchten Funk- tionen dieser Klasse.

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen 51

Die resultierende ¨ Ahnlichkeit scheint nur durch einen Faktor skaliert zu sein, der vom Minkowski-Koeffizienten p abh¨ angt. Je gr¨ oßer dieser ausf¨ allt, desto schw¨ acher wird die ¨ Ahnlichkeit zwischen zwei unterschiedlichen Fuzzy-Cluster-Konfigurationen. Dennoch zeigt die auf die Maximum-Distanzfunktion basierende S-Distanz bei beiden T-Normen keine v¨ ollige Un¨ ahnlichkeit in diesem Experiment, was darauf schließen l¨ aßt, das die Funktionsergebnisse nicht beliebig durch den exponentiellen Minkowskikoeffizienten p skalierbar sind.

Der Vergleich der beiden verwendeten T-Normen ergibt, dass bei der T-Norm ^{P rod} der un¨ ahnlichste Punkt im Gegensatz zur T-Norm M in asymptotisch angen¨ ahert wird; auch die absoluten ¨ Ahnlichkeitswerte der Funktionsminima fallen unterschiedlich aus: Bei der Nutzung der Maximum-Distanzfunktion ist dieser bei der T-Norm M in kleiner und bei allen anderen untersuchten Minkowski-Metriken gr¨ oßer, verglichen mit der T-Norm P rod .

Die Auswertung der ” dass das Kosinus- und Dice- ¨ fern. Das Jaccard- ¨ Fuzzy-Set- ¨ Ahnlichekitsmaß ¨ ahnelt dem Jaccard- ¨ abh¨ angig von der verwendeten T-Norm.

nat¨ urlichen“ ¨ Abbildung 4.4: Ringmethode: S-Distanz( M in ) mit ” Ahnlichkeitsfunktionen

Dieses Ph¨ anomen erkl¨ art sich folgendermaßen: Die Clusterdrehung bewirkt nur eine Neuordnung der alten Zugeh¨ origkeitsgrade; beispielsweise verschieben sich bei Drehung um ein Grad und bei Verwendung von 360 Punkten die Zugeh¨ origkeitsgrade um eine Dimension im Clustervektor bei angenommener Sortierung der Datenpunkte. Allgemein gilt dann f¨ ur zwei Clustervektoren x und y folgende Neuordnung ihrer Elemente:

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen 52

nat¨ urlichen“ ¨ Abbildung 4.5: Ringmethode: P rod mit ” Ahnlichkeitsfunktionen

(4.1)

Als Resultat ergibt sich, dass alle Clustervektoren die gleichen Elemente in unterschiedlicher Reihenfolgen tragen und somit eine equivalente L¨ ange haben: Es gilt |x| = |y|. Das Kosinus- ¨ Ahnlichkeitsmaß entspricht in diesem Fall dem Dice- ¨ Ahnlichkeitsmaß:

x · y x · y

(4.2)

(4.3)

Allgemein kann man feststellen, dass das Dice- ¨ Ahnlichkeitsmaß neben dem Winkel

der beiden Vergleichsvektoren auch deren L¨ ange ber¨ ucksichtigt. Sind diese gleich, so wird es zum Kosinus- ¨ Ahnlichkeitsmaß degeneriert.

Die verwendeten T-Normen M in und P rod zeigen unterschiedliche Verl¨ aufe: w¨ ahrend bei der T-Norm M in ausschließlich fast lineare Steigungen zu beobachten sind, ist dieses bei der T-Norm P rod nur nahe der Maxima zu erkennen. Die Minima hingegen werden mit geringen Steigungsgradienten approximiert.

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen 53

K-Distanz

Die K-Distanz zeigt einen sinus¨ ahnlichen Kurvenverlauf mit asymptotischen Ann¨ aherungen an den Extrempunkten; ein fast linearer Verlauf wie bei der B-Distanz ist auch aufgrund der quadratischen Fehlerfunktion nicht zu erwarten gewesen.

M-Distanz

Die Entropie der M-Distanz wird ausschließlich durch die Summe der einzelnen Cluster-vektoren bestimmt. Wie schon in bei der S-Distanz gezeigt, sind die Vergleichsvektoren aber nur durch eine Anordnung der Vektorelemente verschieden, was keine ¨ Anderung auf

die Summe dieser Elemente zur Folge hat. Somit zeigt die M-Distanz volle ¨

Ahnlichkeit bei jeder Clusterdrehung. Dieses Resultat bei diesem Test ist notwendige Eigenschaft f¨ ur alle ¨ Abbildung der Datenpunkte voraussetzen. 4.2 Semiverifikation der Dreiecksungleichung

Der mathematische Nachweis einiger formaler Eigenschaften der ¨ Ahnlichkeitsfunktionen

bzw. Distanzfunktionen kann sich als schwierig erweisen: Hierbei ist insbesondere die Dreiecksungleichung zu nennen. Hingegen kann die Nachweis der Nichterf¨ ullung dieser Eigenschaft durch einfache Gegenbeispielsfindung erbracht werden.

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen 54

Um solch ein Beispiel zu finden, ist die Implementation eines entsprechenden Semi-Algorithmus in Software sinnvoll, welche sehr viele zuf¨ allig generierte Beispiele testen kann. Sollte kein Gegenbeispiel gefunden werden, ist es offen, ob diese Eigenschaft erf¨ ullt wird oder nicht.

Tabelle 4.1: Erf¨ ullung der Dreiecksungleichung diverser ¨ Ahnlichkeitsfunktionen f¨ ur Fuzzy-Cluster-Konfigurationen

Die Testumgebung erstellt f¨ ur einen Testfall mehrere Clusterpartitionen, welche die gleiche Anzahl an Punkten aufweisen. Im n¨ achsten Schritt wird f¨ ur jede Clusterpartition eine zuf¨ allige Clusterzahl bestimmt. Anschließend erh¨ alt jeder Punkt zu jedem Cluster einen zuf¨ alligen Zugeh¨ origkeitswert. Diese sind dabei so normalisiert, dass die Summe der Zugeh¨ origkeitsgrade eines Punktes Eins ergibt.

Die Definition der Dimension des Vektorraumes und die geometrische Lage der Punkte ist f¨ ur diesen Test nicht notwendig, da alle vorgestellten ¨ Ahnlichkeitsfunktionen ausschließlich auf die Untersuchung der Clusterzugeh¨ origkeitsgrade beschr¨ anken und diese geometrieunabh¨ angig k¨ unstlich erzeugt wurden. Jede getestete Eigenschaft wurde im Folgenden pro (parametrisierte) ¨ Ahnlichkeits-

funktion an 100.000 Beispiele getestet: Diese enthielten bis zu 10 Cluster und bis zu

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen 55

1000 Datenpunkten. Eine Ausnahme erfolgte f¨ ur die K-Distanz, da der Aufwand zu den Datenpunkten hier mindestens quadratisch ansteigt: Diese wurden auf in diesem Fall auf bis zu 120 Datenpunkte und auf maximal 6 Cluster begrenzt. Die Untersuchung zeigt, das f¨ ur viele ¨ Ahnlichkeitsfunktionen bzw. deren Parametrisierung Gegenbeispiele zu finden sind. Diese sind im Anhang A dokumentiert. Zusammengefasst gilt die Dreiecksungleichung im Allgemeinen nicht f¨ ur die B-Distanz und die H-Distanz; bei der M-Distanz und der S-Distanz mit der drastischen ¨ Ahnlichkeitsfunktion hingegen wurde in den jeweiligen Abschnitten bewiesen, dass diese Eigenschaft immer erf¨ ullt wird. Ansonsten verletzt die S-Distanz in diversen Parametrisierungen die Dreiecksungleichungen, in einigen anderen Parametrisierungen konnte jedoch kein Gegenbeispiel gefunden werden.

Distanzmaße, die die Dreiecksungleichung erf¨ ullen, sind f¨ ur effiziente Algorithmen geeignet: diese k¨ onnen einen Minimalabstand zwischen zwei Partitionen zu bestimmen, ohne dass das Distanzmaß explizit berechnet wird.

Gegeben sei beispielsweise eine Menge von Partitionen {U 1 , . . . , U n }, in der die Abst¨ ande zueinander vorberechnet worden sind. Des weiteren sei eine Partition V gegeben zu der die Partition mit dem geringsten Abstand gesucht werden soll. Es gilt folgende Ungleichung f¨ ur ein Abstandsmaß d(U, V), welches die Dreiecksungleichung erf¨ ullt:

(4.4) d(U i , V ) >= d(U i , U j ) − d(V, U j )

Bei einer Suche nach dem kleinsten Abstand muss somit nicht die Distanz d(U i , V ) bestimmt werden, wenn d(U i , U j ) − d(V, U j ) den bisher kleinsten Referenzwert ¨ ubersteigt. Dies ist insbesondere n¨ utzlich, wenn die explizite Berechnung von d(U i , V ) sehr aufwendig im Vergleich zu d(U i , U j ) − d(V, U j ) ist: dies ist bei vielen hier vorgestellten ¨ Ahnlichkeitsfunktionen f¨ ur Fuzzy-Cluster-Konfigurationen der Fall, wenn U i und V sehr viele und U j nur wenige Cluster enthalten.

In n¨ achsten Kapitel wird genau dieses Szenario anhand einer Bildklassifikation vorgestellt. Da jedoch nur f¨ ur wenige Distanzmaße bewiesen werden konnte, dass die Dreiecksungleichung erf¨ ullt wird, wurde auf eine Implementation, in der diese Eigenschaft ausgenutzt wird, verzichtet.

4.3 Vergleich unterschiedlich großer Cluster mittels

Datenpunktzuordnungen

Bei der Evaluation der ¨ Ahnlichkeitsfunktionen f¨ ur Fuzzy-Cluster-Strukturen stellt sich die Frage, inwiefern diese unterschiedlich große Cluster bewerten. Dazu muss man zuerst definieren, was ein großer bzw. kleiner Cluster ist: Hier gibt es zwei unterschiedliche Ans¨ atze.

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen 56

Bei der ersten M¨ oglichkeit kann man eine Datenpunktmenge in zwei unterschiedlich große Teilmengen A und B teilen. Teilmenge A habe dabei mehr Punkte als Teilmenge B: |A| > |B|.

Dieses wurde im folgenden Test wurde mit 100 Datenpunkte und den beiden Zugeh¨ origkeitsgrade von 0,99 und 0,01 umgesetzt. Auf die Verwendung der vollen Zugeh¨ origkeit ” 1“ wurde verzichtet, da bei Zuordnung aller Punkte zu einem Cluster der andere leer sein w¨ urde: Dies bringt verhindert die Berechnung einiger ¨ Ahnlichkeitsfunktionen, die leere Cluster ausschließen.

Es sind alle m¨ oglichen Zuordnungen der Datenpunkte zu den beiden Teilmengen A und B ber¨ ucksichtigt worden; diese wurden anschließend mit einer Referenzclusterkonfiguration bestehen aus zwei gleich großen Clustern verglichen. Diese entspricht der oben genannten Clusterkonfiguration, wenn |A| = |B| ist.

Abbildung 4.7: Clustergr¨ oßenvergleich mittels Datenpunktzuordnungen: S-Distanz ( M in ) mit Minkowski-Metriken

Als ein Ergebnis zeigt sich, dass die B-Distanz und die auf der Manhattan-Distanz basierende S-Distanz unter der T-Norm M in die gleichen Ergebnisse liefern: Sie zeigen ein linearen Verlauf von der un¨ ahnlichsten Konfiguration zum Maximum bei 1. Alle anderen Minkowski-Metriken scheinen skaliert zu sein: Je h¨ oher der exponentielle Koeffizient p, desto st¨ arker ist Steigungsgradient nahe dem Maximum der Funktion ausgepr¨ agt; bei der Maximum-Distanz tritt der Fall ein, dass nur bei exakt gleichen Clusterkonfigurationen ein Peak erkennbar ist: Geringste Unterschiede ergeben in diesem Experiment eine konstante ¨

nat¨ urlichen“ ¨ Bei Verwendung der ” uberraschendes Ergebnis, dass es zwei lokale Minima in der ¨ als ¨

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen 57

finden lassen. Je nach verwendeter ¨ Ahnlichkeitsfunktion m¨ ussen bei 14-17 Datenpunkte

einem Cluster zugeordnet werden, um die h¨ ochste Un¨ ahnlichkeit zu erreichen bzw. 83-86 Datenpunkte im gespiegelten Teil der Funktion.

Abbildung 4.8: Clustergr¨ oßenvergleich mittels Datenpunktzuordnungen: S-Distanz nat¨ urlichen“ ¨ ( M in ) mit ” Ahnlichlichkeitsfunktionen

Dieses Ph¨ anomen soll exemplarisch am Beispiel der Kosinus- ¨ Ahnlichkeitsfunktion

erkl¨ art werden: Die beiden Referenzcluster liegen sehr dicht an zwei Ecken im ndimensionalen Einheitsw¨ urfel, zwischen denen ein Kosinuswinkel nach dem ¨ Ahnlichkeitsmaß von nahe 90 ^◦ festzustellen ist.

Ebenso befinden sich beide Startcluster nahe zwei Ecken im Einheitshyperw¨ urfel; sie tragen die gleichen Elemente (0,01 bzw. 0,99), welche zu beiden Refernzclustern jeweils einen Winkel von nahe 45 ^◦ impliziert: dies enstprich einem Kosinus von ca. 0,71.

Zu diesem Zeitpunkt liegen noch alle vier Cluster auf einer Ebene: Durch Linearkombination der Startclustervektor lassen sich alle Referenzclustervektoren erzeugen. Wird nun dem einen Startcluster ein neuer Datenpunkt zugeordnet und dem anderen entsprechend entzogen, so steigt die Dimension des kleinsten Teilraumes, in dem noch alle Punkte existieren. Geometrisch werden die Startpunkte von einer Ecke zur n¨ achsten verschoben, so dass der Manhattenabstand zu den Referenzclustern um 1 verringert wird.

Projeziert man nun die Cluster auf die besagte Ebene, so verringert sich zwar der Winkel monoton bis die Referenzcluster erreicht sind. Allerdings steigt der Winkel zwischen Ebene und den zu vergleichenden Clustern zun¨ achst an. Diese beiden Faktoren mit unterschiedlichen Funktionstendenzen werden im Gesamtergebnis ber¨ ucksichtigt, was die beiden lokalen Minimal insgesamt erzeugt.

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen

Abbildung 4.9: Clustergr¨ oßenvergleich mittels Datenpunktzuordnungen: S-Distanz ( P rod ) mit Minkowski-Metriken

Abbildung 4.10: Clustergr¨ oßenvergleich mittels Datenpunktzuordnungen: S-Distanz ( P rod ) mit ¨ Ahnlichlichkeitsfunktionen

Bei der T-Norm P rod hingegen zeigen fast alle Funktionsergebnisse monotonen Verlauf, wenn man vom fast leeren Cluster der Kosinus¨ ahnlichkeitsfunktion absieht. Die bei der T-Norm M in aufgetretenen lokalen Minima werden offensichtlich durch die Ver-

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen 59

kn¨ upfung des zweiten Kosinus¨ ahnlichkeitswert mittels der T-Conorm P rod elemeniert.

Abbildung 4.11: Clustergr¨ oßenvergleich mittels Datenpunktzuordnungen: K-Distanz

Die Auswertung der K-Distanz und M-Distanz zeigt, dass sowohl volle ¨ Ahnlichkeit als auch Un¨ ahnlich bei beiden ¨ Ahnlichkeitsfunktionen erreicht wird, was suggeriert, dass die Normierungsfunktion f¨ ur diese Distanzen optimal gew¨ ahlt worden sind. Die M-Distanz zeigt einen fast perfekten Halbkreis als Funktionsverlauf, was eine asymptotische Ann¨ aherung beim Maxima der Funktion impliziert. Die K-Distanz hingegen n¨ ahert sich asymptotisch bei den Minima der Funktion an.

4.4 Vergleich unterschiedlich großer Cluster durch

Variation der Zugeh¨ origkeitsgrade

Neben der starren Teilung der Datenpunkte in zwei unterschiedlich großen Mengen, welches dem klassischen Clusterverfahren entspricht, kann man bei der Fuzzy Cluster-Analyse auch ¨ uber die Zugeh¨ origkeitsgrade monotone Gr¨ oßen¨ anderungen erreichen. Dazu sei wieder eine Datenpunktmenge mit zwei Cluster gegeben: Jeder Datenpunkt habe nun zum ersten Cluster einen Zugeh¨ origkeitsgrad u 1 > 0.5 und zum zweiten Cluster dementsprechend u 2 = 1 − u 1 . Der erste Cluster sei nun groß, der zweite sei klein. Im Folgenden Test wurden wieder 100 Datenpunkte erzeugt und der Zugeh¨ origkeitsgrad in 0,01-Schritten variiert. In der Referenzpartition wurden zwei Cluster erstellt, zu denen alle Datenpunkte mit einem Zugeh¨ origkeitsgrad von jeweils 0,5 angeh¨ oren.

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen

Abbildung 4.12: Fuzzy-Gr¨ oßenvergleich: B-Distanz und S-Distanz mit Minkowski-Metriken

Abbildung 4.13: Cluster-Gr¨ oßenmethode: S-Distanz ( M in ) mit ¨ Ahnlichkeitsfunktionen

Als interessantes Ergebnis zeigt sich, dass s¨ amtliche S-Distanzen, die auf normalisierten Minkowski-Metriken basieren, exakt das gleiche Ergebnis liefern, unabh¨ angig von der Datenpunktanzahl.

F¨ ur diese Minkowskimetriken l¨ asst sich zeigen, dass diese bei zwei Vektoren x und y,

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen 61

welche jeweils ausschließlich aus den gleichen Elementen y bestehen, Ergebnisse

unabh¨ angig vom Potenzfaktor p und der Dimension n liefern.

√

^{n y} i | p p   i=1 | ^x i −

d( x, y) = √ ¡ ¡

^p √ ⁿ (4.5)

n·|¡ x−¡ y| p p

= = ^p y| √

^p n

Des weiteren zeigt sich, dass die B-Distanz auch das gleiche Ergebnis liefert, da die benutzte Lukasiewicz-Implikation ebenso den Differenzbetrag der Vektorelemente erzeugt.

Im Gegensatz dazu bescheinigt die S-Distanz basierend auf dem Kosinus¨ ahnlichkeitsmaß immer volle ¨ Ahnlichkeit, da der Winkel zwischen zwei Vektoren, welche jeweils ausschließlich aus gleichen Elementen bestehen, Null betr¨ agt und somit ein Kosinuswert von Eins generiert. Hierbei sei der Nullvektor ausgenommen.

Abbildung 4.14: Clustergr¨ oßenmethode: S-Distanz ( P rod ) mit ¨ Ahnlichkeitsfunktionen

Das Kosinusmaß ist somit ungeeignet, unterschiedlich große Cluster dieser Art zu erkennen; es konzentriert sich auf die Struktur und ignoriert Skalierungen. Bei allen nat¨ urlichen“ ¨ anderen auf ” Ahnlichkeitsmaßen basierende S-Distanzen sind hingegen in der Lage, Gr¨ oßenver¨ anderungen wahrzunehmen.

Die K-Distanz zeigt eine quadratische Funktion, deren Scheitelpunkt bei der Refe- renzclusterkonfiguration (u = 0.5) zu finden ist:

62 Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen

Die Abbildung von den beiden unterschiedlich großen Clustern zur Referenzkonfiguration gelingt noch vollst¨ andig, so dass beide Clustervektoren exakt hergestellt werden k¨ onnen. Die K-Distanz ber¨ ucksichtigt jedoch auch die Gegenrichtung: Da beide Cluster-vektoren der Referenzkonfiguration identisch sind, ergibt jede normierte Linearkombination mit beliebigen Koeffizientenpaar genau wieder einer dieser Referenzcluster:

∀(a 1 + a 2 = 1) : ( C Ref = a 1 · C Ref + a 2 · (4.6) C Ref )

Als quadratische Fehlersumme sowohl zu einem fast leeren als auch fast vollen Clusterelement ergibt ein Wert nahe 0,25. Insgesamt l¨ asst sich diese Funktion mit Polynom zweiten Grades beschreiben:

1 2 1 2 1 2 (4.7) S K−Distanz (u) = 1

− Die M-Distanz zeigt bei dieser Versuchsanordnung einen ¨ ahnlichen Verlauf; die Funktion ist durch folgenden Gleichung bestimmt:

(4.8) M S (u) = 1 − |u · log 2 u − (1 − u) · log 2 (1 − u)|

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen

4.5 Hierarchische Clustermethoden

Bei hierarchischen Clustermethoden wird die Eigenschaft genutzt, dass mit zunehmender Zerteilung der Cluster diese intuitiv immer un¨ ahnlicher zur urspr¨ unglichen Clusterkonfiguration werden.

Interessant ist außerdem der Abstand zwischen zwei Ebenen, wenn der Teilungsal-gorithmus so ausgelegt ist, dass er jeden Cluster ¨ ahnlich zerteilt, wie in der vorherigen Ebene. Dieser Abstand ist dann charakteristisch f¨ ur eine Abstandsfunktion.

4.5.1 Split-Methode

Ausgangspunkt ist ein einziger Cluster c, dem alle Datenpunkte voll angeh¨ oren. Dieser Cluster wird in zwei Cluster u und v folgendermaßen geteilt: F¨ ur jeden Datenpunkt n ⁱ wird ein Zufallswert z i zwischen 0..1 generiert, der die Zugeh¨ origkeitsgerade neu verteilt:

(4.9)

Es entsteht eine neue Clusterkonfiguration bestehend aus den Clustern u und v. Diese werden im n¨ achsten Schritt nach der gleichen Methode geteilt wieder geteilt, so dass vier neue Cluster entstehen. Es erfolgen weitere Splits, welche ein hierarchisches Clustergebilde kreieren l¨ asst. Der Abstand zwischen allen Nachbarebenen und zur urspr¨ unglichen Ein-Cluster-Konfiguration wird im Folgenden untersucht. Erwartet wird ein Ergebnis, dass zwei benachbarte Cluster-Konfigurations-Ebenen eine konstante ¨

Ahnlichkeit bescheinigt. Hingegen sollten alle Ebenen zur Wurzelkonfiguration mit zunehmender Cluster- bzw. Ebenenzahl monoton an ¨ F¨ ur diesen Versuch wurden insgesamt sieben Ebenen kreiert, so dass in der letzten Ebene 64 Cluster entstanden sind; es sind f¨ ur alle Clusterkonfiguration 10000 Datenpunkte verwendet worden um Variationsbreite zwischen unterschiedlichen Durchl¨ aufen zu minimieren.

Eine Ausnahme aufgrund ihres hohen Rechenaufwandes stellte die K-Distanz da, so dass hier nur 100 Datenpunkte Verwendung fanden. Doch auch hier haben mehrere Durchl¨ aufe gezeigt, dass sich diese nur unwesentlich voneinander unterscheiden. Jedoch konnte kein Vergleich zwischen den letzten beiden Ebenen f¨ ur dieses Abstandsmaß ermittelt werden, da der NNLS-Algorithmus nicht gen¨ ugend Speicher f¨ ur die Matrizen alloziieren konnte ² .

4.5.2 Auswertung

Die B-Distanz liefert bei den Tests sehr gute Ergebnisse: Im ersten Test zeigt sich eine konstante ¨ Ahnlichkeit zwischen zwei Nachbarebenen von 0,5. Im zweiten Test lieferte

² Die Java Virtual Machine beendete sich f¨ ur diese Konfiguration mit einer ” Heap overflow exception“

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen

dieses Maß eine sinkende ¨ Ahnlichkeit mit steigender Clusterzahl zur Wurzelkonfiguration:

pro Ebene halbierte sich die ¨

Tabelle 4.2: Hierachische Splits: ¨ Ahnlichkeit / Distanz zwischen den Nachbarebenen

Im Gegensatz dazu stellte die K-Distanz zwischen zwei Nachbarebenen mit steigender Clusterzahl einer geringere ¨ Ahnlichkeit fest: Zwar werden die Clustervektorenelemente mit zunehmender Ebenenanzahl immer kleiner werden und somit sinkt tendenziell die Quadratfehlersumme, jedoch wird dieser Effekt durch die Normalisierung, welche Clusterzahlabh¨ angig ist, mehr als kompensiert. Im zweiten Test sinkt die Un¨ ahnlichkeit mit steigender Clusterzahl deutlich schneller zur Wurzelkonfiguration im Vergleich zum ersten Test: Die Quadratfehlersumme steigt rapide zur Ebenenanzahl. Je nach Parametrisierung zeigt die S-Distanz unterschiedliche Eigenschaften: Bei Verwendung der T-Norm P rod stieg die ¨ Ahnlichkeit zwischen Nachbarebenen mit steigender Clusterzahl kontinuierlich an und erreichte in fast allen F¨ allen nahezu volle ¨ Ahnlichkeit. Bei der M in -Norm kann man wieder zwischen den Minkowski-Metriken und nat¨ urlichen“ ¨ Ahnlichkeitsfunktionen differenzieren: Bei ersteren steigt die ¨ den ” Ahnlichkeit kontinuierlich an, was durch die monotone Verkleinerung der Clustervektorenl¨ ange und deren Distanzen untereinander begr¨ undet ist. Das Fuzzy-Set-, Kosinus-, Dice- und Jaccard- ¨ Ahnlichkeitsmaß hingegen zeigen recht konstante Werte.

Im zweiten Test, in dem jede Ebene zur Wurzelkonfiguration verglichen worden ist, zeigt die S-Distanz ein deutlich uneinheitlicheres Bild: W¨ ahrend bei Verwendung der M in -Norm die ¨ Ahnlichkeit mit steigender Clusteranzahl noch monoton sinkt, ist es

Kapitel 4. Evaluationstests in k¨ unstlichen Umgebungen 65

Manhattan 0.504 0.253 0.127 0.064 0.033 0.017

Tabelle 4.3: Hierachische Splits: ¨ Ahnlichkeit / Distanz zwischen Wurzelebene und tieferen Ebenen

bei der P rod -Norm abh¨ angig, welche zugrundeliegende ¨ Ahnlichkeitsfunktion verwendet wurde.

Die M-Distanz bescheinigt eine maximale Un¨ ahnlichkeit von allen Ebenen zur Wurzelebene: Dies ist damit zu begr¨ unden, dass in der Wurzelebene maximale Ordnung herrscht und die Entropie ” Null“ betr¨ agt. Hingegen ist f¨ ur jede Vergleichsebene die Entropie f¨ ur die jeweilige Clusterzahl maximiert, da die Datenpunkte m¨ oglichst gleichm¨ aßig und zuf¨ allig ¨ uber die Cluster verteilt sind, so dass die auf die Clusteranzahl bezogene normalisierte Entropie dieser Partitionen ” Eins“ ergibt.

Beim Vergleich der Nachbarebenen, stellt man eine steigende ¨ Ahnlichkeit mit zunehmender Ebenenanzahl fest. Dies ist damit zu begr¨ unden, dass die Entropien der jeweiligen Partitionen beide ansteigen und das die Referenzebene (die Wurzelebene) sich immer weiter entfernt. Relativ gesehen, n¨ ahern sich dann die Entropien der beiden Partitionen auf hohem Niveau an.

Kapitel 5. Fuzzy-Bildklassifikation 66

Kapitel 5

Fuzzy-Bildklassifikation

5.1 Klassifikation mittels ¨ Ahnlichkeitsmaßen

Die bisher vorgestellten Evaluationsmethoden sind nur geeignet, bestimmte erwartete Eigenschaften f¨ ur Abstandsmethoden zu verifizieren bzw. falsifizieren. In diesem Abschnitt wird deshalb eine Methode vorgestellt, in der die einzelnen Abstandsmaße mittels realen, nicht synthetischen Daten getestet werden, so dass sie untereinander vergleichbar sind. Das Anwendungsszenario liegt bei dieser Evaluationsmethode in der Klassifikation von digitalisierten Bildern. Im ersten Schritt werden dabei Eigenschaftsvektoren f¨ ur jedes einzelne Bild berechnet.

Diese Eigenschaftsvektoren bilden eine Punktmenge im n-dimensionalen Raum welche anschließend geclustert wird. Somit erzeugt ein Bild eine Clustermenge und die komplette Bildersammlung eine Menge von Clustermengen. Zur Klassifikation werden zwei Bildersammlungen vereint: zu jedem einzelnen Bild wird ein zweites gesucht, welches eine maximale ¨ Ahnlichkeit zu diesem aufweist: Das Bild wird der Klasse des Vergleichsbildes zugeordnet ¹ . Daf¨ ur k¨ onnen im Prinzip alle ¨ Ahnlichkeitsfunktionen f¨ ur Fuzzy-Cluster-Konfigurationen aus Kapitel 3 getestet werden. Als Ergebnis kann man f¨ ur eine ¨ Ahnlichkeitsfunktion, eine Clustermethode und zwei

Bildersammlungen eine Klassifikationsrate bestimmen. Um stabile Ergebnisse zu den einzelnen Parametern zu erhalten, werden im Folgenden alle Parameter variiert.

5.2 Die Bildersammlung

Insgesamt wurden zehn Bildersammlungen mit jeweils einem Thema verwendet, zu denen 48 bis 115 Bilder zugeordnet worden sind. Es handelt sich teilweise um Landschaftsbilder vom Yellowstone-Nationalpark und Green Lake Park (Seattle), von Pflanzen (Kirschb¨ aume, laublose B¨ aume und Fr¨ uhlingsblumen) und teilweise um bestimmte

¹ Formal kann man diesen Klassifizierer auch als ” K-Nearest-Neighbour“-Klassifizierer mit K=1 be- zeichnen

Kapitel 5. Fuzzy-Bildklassifikation 67

bebaute Orte (Barcelona, eine Kleinstadt namens Cannon Beach, ein Universit¨ atscampus im Herbst und Iranbilder). Auch eine Fotosammlung zu einem Footballspiel wurde verwendet. Alle Bilder wurden von der ” Efficient Content-based Retrieval Group“ der Universit¨ at von Washington ver¨ offentlicht ² .

Wie die Thematiken schon suggerieren, gibt es viele ¨ ahnliche Bilder in den unterschiedlichen Sammlungen: So sind auf die im Herbst entstandenen Campusbilder auch laublose B¨ aume zu finden und umgekehrt befinden sich bei den laublosen B¨ aumen auf fast allen Fotos im Hintergrund diverse Geb¨ aude. Rosa bl¨ uhende Pflanzen gibt es in hohem Maße auf den Kirschbaum- und Fr¨ uhlingsblumenbildern. Bilder von Seen befinden sich nicht nur in den beiden Landschaftsfotosammlungen, sondern auch auf den Campusfotos und auf den Bildern aus dem Iran. Selbst ein Mensch br¨ auchte wohl spezielle Ortskenntnisse bzw. Grundkenntnisse in der Botanik, um alle Fotos korrekt zu klassifizieren.

Ziel ist es somit nicht, eine m¨ oglichst 100 % Klassifikationsrate zu erreichen, sondern Algorithmen untereinander zu vergleichen und zu untersuchen, wie bestimmte Rahmenbedingungen sich auf sie in diesem Szenario auswirken.

5.3 Extraktion von Eigenschaftvektoren eines Bildes

Gegeben seien zwei Mengen von Bildern, die jeweils charakteristisch f¨ ur ein Thema sind. Aus jedem Bild wird eine ungeordnete Menge von Eigenschaftsvektoren extrahiert, wobei diese im Folgenden nur im RGB-Farbraum betrachtet werden. Es existieren jedoch weitere verwendbare Farbr¨ aume, wie beispielsweise der HSV-, CMYK- oder auch YUV-Farbraum; f¨ ur weitere Details sei auf [Lev97] verwiesen. Konkret wird das Bild in x · y gleich große Kacheln unterteilt. Aus jeder Kachel werden sechs verschiedene Parameter folgendermaßen extrahiert: Sei P k die Menge der Bildpunkte, die einer n · m großen Kachel q zugeordnet sind.

(5.1) P k = {p 11q , p 21q , . . . , p m1q , p 12q , p 22q , . . . , p m2q , . . . , p 1nq , p 2nq , p mnq }

Ferner seien red(p), green(p) und blue(p) Funktionen, die jeweils den Rot-, Gr¨ unbzw. Blauanteil eines Pixels p bestimmen. Die 6 Eigenschaften f¨ ur eine Kachel q werden dann folgendermaßen berechnet:

(5.2)

² Ver¨ offentlichung: http://www.cs.washington.edu/research/imagedatabase/groundtruth/

Kapitel 5. Fuzzy-Bildklassifikation 68

(5.3)

(5.4)

(5.5)

(5.6)

(5.7)

Die ersten drei Funktionen ermitteln den durchschnittlichen Farbwert einer Kachel, jeweils f¨ ur den entsprechenden Farbanteil. Die letzten drei Funktionen hingegen gewichten die Kanten innerhalb einer Kachel: Durch die quadratische Funktion werden kontrastreiche Kanten deutlich st¨ arker gewichtet als beispielweise viele kleine Kanten die in Farbverl¨ aufen auftreten.

Die Eigenschaftswerte einer Kachel werden noch relativ zu den anderen Kacheln normalisiert: Sei e (q) eine der oben genannten Funktionen, welche eine Eigenschaft f¨ ur eine Kachel q spezifiziert. Die Normalisierung erfolgt nach:

(5.8)

Intuitiv bedeutet beispielsweise, dass die Pixel einer Kachel 20 % des Rotanteils eines Bildes auf sich vereinen, wenn der entsprechende Wert der Kachel bei 0,2 liegt. Zu bemerken ist, dass alle Werte relativ zu allen anderen Kacheln des Bildes ausgelegt sind und nicht relativ zu allen Kacheln der Bildersammlung.

5.4 Clusterung der Datenpunkte

In dem vorherigen Abschnitt wurden x · y Kacheln erzeugt, welche nun als Parameter f¨ ur einen Clusteralgorithmus genutzt werden. Zwei verschiedene Typen sind angewendet worden:

Im ersten Fall wurden fixe Cluster definiert: Die Kacheln werden als Cluster interpre- tiert: Jede geh¨ ort 6 Datenpunkten mit einem bestimmten Zugeh¨ origkeitsgrad an, welche

Kapitel 5. Fuzzy-Bildklassifikation 69

die einzelnen Attribute einer Kachel darstellen. Eine weitere Transformation der extrahierten Bildvektoren aus Abschnitt 5.3 f¨ ur eine Clusterdarstellung ist nicht notwendig, da die erfolgte Normalisierung alle notwendigen Eigenschaften bereits sicherstellt. Diese Clusterung ist extrem schnell, da der Abbildungsschritt des digitalen Bildes in den n-dimensionalen Vektorraum und die Clusterung zusammen fallen und somit kein zus¨ atzlicher Aufwand betrieben werden muss. Interessant ist diese Methode auch bei sich schnell ¨ andernden Daten, da es nur linearen Aufwand pro Cluster bedarf, die Zugeh¨ origkeitsgrade an einen neuen Datensatz anzupassen. Dieses ist beispielsweise beim kontinuierlichen Clustern von Datenstr¨ omen n¨ utzlich [JB06]. Auch ist die Anzahl der entstehenden Cluster bekannt, so dass bei vielen Algorithmen die Laufzeit der im zweiten Schritt angewendeten ¨ Ahnlichkeitsfunktionen im Vorfeld bekannt ist, was in einer Echtzeitf¨ ahigkeit dieses Algorithmus m¨ undet.

Auch ist es im Prinzip hier m¨ oglich, eine bijektive Abbildung zu den Clustern zu Counting Pair“- ¨ schaffen, so dass die sehr einfache Variante der ” Ahnlichkeitsmaße anwendbar ist. Auf die Auswertung dieser Abbildung wurde jedoch verzichtet, um die Ergebnisse mit anderen Clustermethoden vergleichbar zu halten. Insgesamt l¨ aßt sich diese Clustermethode jedoch aufgrund der begrenzten Kachelanzahl kritisieren, da jede zus¨ atzliche Kachel pro Partition einen weiteren Cluster entstehen l¨ aßt, was bei Verwendung der B-Distanz oder S-Distanz einen quadratischem Komplexit¨ atsanstieg verursacht. Deshalb wurde ein Bild in nur 4 · 4 Kacheln unterteilt, so dass nur 16 Cluster pro Bild entstanden sind.

Des weiteren l¨ aßt sich die statische Positionierung der Cluster kritisieren: Realit¨ atsn¨ aher w¨ are die Anwendung eines klassischen Clusteralgorithmus. Auch dass es in den meisten F¨ allen mehr Cluster als Datenpunkte gibt, wirkt unnat¨ urlich verglichen mit Clusterkonfigurationen aus den meisten anderen Applikationen.

Der letzte Kritikpunkt w¨ urde theoretisch durch die eine Matrixdrehung beseitigt werden, in welcher dann die Kacheln zu Datenpunkten werden bzw. umgekehrt die RGB-Attribute der einzelnen Kacheln zu Clustervektoren w¨ urden. Darauf wurde angesichts des Anwendungsfalles verzichtet, da die bijektive Abbildung der Kacheln bei einer Bilddrehung oder Spiegelung eine Neuzuordnung verhindert und somit keine volle ¨ Ahnlichkeit

mehr im Allgemeinen garantiert ist. Noch schwerer wirkt die beliebige Zuordnung der Farbzugeh¨ origkeiten, so dass beispielsweise der Clustervektor f¨ ur den Rotanteil mit dem Clustervektor des Blauanteiles verglichen werden k¨ onnte, was die ¨ Ahnlichkeitsfunktionen relativ farbenblind machen w¨ urde.

Aus diesem Grunde werden die Datenpunkte zus¨ atzlich nach einer zweiten und wohl bekanntesten Methode geclustert: Der in Abschnitt 2.2.5 vorgestellte Fuzzy C-Means Al-gorithmus mit automatischer Clusteranzahladaption basierend auf dem Xie-Beni-Index wird auf die extrahierten Bilddaten angewendet.

Nachteile dieser Methode sind eine h¨ ohere Komplexit¨ at, Nichtdeterminiertheit des Algorithmus und ein weiterer Informationsverlust, welcher durch die nicht eindeutig umkehrbare Abbildung der Bildvektordaten auf die Clusterzugeh¨ origkeitswerte begr¨ undet ist. So enstehen beispielsweise bei einem schwarz-weißes Schachbrettmuster zwei gleiche

Kapitel 5. Fuzzy-Bildklassifikation 70

Cluster; die erste Methode hingegen ist in der Lage, den weißen Kacheln entsprechend ihrem RGB-Anteil am Gesamtbild h¨ ohere Zugeh¨ origkeitsgrade zuzuordnen. Dennoch sind diese genannten Kritikpunkte zu beiden Verfahren unerheblich, wenn man nur faire Ausgangsbedingungen f¨ ur Vergleichszwecke der ¨ Ahnlichkeitsfunktion schaffen will.

Schwerer wiegt die Kritik, dass sowohl beim Clustern des Fuzzy C-Means Algorithmus als auch bei der Autoadaption der Clusteranzahl mittels des Xie-Beni-Indexes standardm¨ aßig der euklidische Abstand verwendet wird: Dadurch k¨ onnte die mit dem euklidischen Abstand instanziierte S-Distanz einen Vorteil haben. Ob dies der Fall ist, wird in zwei Testreihen gekl¨ art: In der ersten wird beim Clustern ausschließlich der euklidische Abstand genutzt; in der zweiten Testreihe wird das verwendete ¨ Ahnlichkeitsmaß in ein

Distanzmaß umgewandelt und anschließend zum Clustern genutzt. Auch die B-Distanz erh¨ alt so adaptierte Cluster: Dieses Abstandsmaß wird auf den Vergleich zweier Vektoren mittels der Lukasiewicz-Implikation und der symmetrischen Verkn¨ upfung mittel der T-Conorm ⊥ M in reduziert. Da alle Datenpunkte sich im ndimensionalen Einheitskubus befinden, liegt der gleiche Wertebereich vor, wie bei Fuzzy-Cluster-Vektoren mit Ausnahme des Null-Vektor.

Als Ergebnis zeigt sich dann auch, inwieweit die Cluster- bzw. Klassifikationsalgorithmen in Bezug auf das Klassifikationsergebnis korrelieren und inwieweit bestimmte Rahmenbedingungen Einfluss aus¨ uben.

5.5 Verwendete ¨ Ahnlichkeitsmaße

Angewendet auf dieses Evaluationsmethode wurden die B-Distanz und die S-Distanz mit diversen T-Normen und ¨ Ahnlichkeitsmaßen f¨ ur Vektorpaare, teilweise mit einem Faktor p entsprechend Kapitel 3.3.2 skaliert.

Nicht getestet wurde die K-Distanz, da die Laufzeit dieses Algorithmus leider zu groß ist: Des weiteren sind zwei große zu vergleichende Bildersammlungen weitere Komplexit¨ atsmultiplikatoren, welche den Algorithmus insgesamt nur f¨ ur sehr wenig Kacheln pro Bild praktikabel machen w¨ urde.

Die M-Distanz wurde nur bei den fest definierten Clustern getestet, da ein ¨ Ahnlichkeitsmaß f¨ ur zwei Vektoren aus diesem Abstandsmaß nicht bestimmbar ist und somit das letzte Experiment mit diesem Maß nicht m¨ oglich ist.

5.6 Klassifikationsraten

F¨ ur einen objektiven Vergleich der Klassifikationsraten bei unterschiedlich großen Bildersammlungen ist es notwendig, diese zu normalisieren.

Ansonsten w¨ urde eine Bildersammlung, die deutlich mehr Bilder enth¨ alt als die Vergleichssammlung, selbst durch eine Zufallsabstandsfunktion viel mehr Bilder sich zu- ordnen, da es mehr Vergleichswerte gibt und somit die Chance steigt, ein passendes

Kapitel 5. Fuzzy-Bildklassifikation 71

Vergleichbild zu finden.

Durch die unterschiedliche Anzahl von Bildern ergibt sich eine ” nat¨ urliche“ Klassifikationsrate, die durch solch eine Zufallsabstandsfunktion hervorgerufen w¨ urde. Seien A und B die beiden Bildmengen und sei s Random durch folgende Zufalls¨ ahnlichkeitsfunktion definiert:

(5.9)

⊕ ist ein symmetrischer Operator und Random(a) eine Funktion, die eine Pseudozufallszahl basierend auf ihr Argument liefert. Dann erreicht ein ” 1-Nearest-Neighbour“-

Klassifikator mit dieser Zufalls¨ ahnlichkeitsfunktion ein durchschnittliches Klassifikationsergebnis von:

(5.10)

Jede ernsthafte ¨ Ahnlichkeitsfunktion sollte diesen Wert verbessern k¨ onnen. Um bei verschieden großen Bildersammlungen die realen Klassifikationsraten bei verschiedenen ¨ Ahnlichkeitsmaßen zu ermitteln, ist die Einf¨ uhrung einer normalisierten Klassifikationsrate notwendig, die den oben genannten Effekt kompensiert. Sei dazu c die Anzahl der korrekt klassifizierten Bilder:

 

(5.11)

Im folgenden Kapitel 6 wird ausschließlich die normalisierte Klassifikationsrate betrachtet.

5.7 Auswertung

Die Bildklassifikation in diesem Kapitel ist mit Abstand das rechenaufwendigste Experiment dieser Diplomarbeit: Insgesamt wurden pro 16 ¨ Ahnlichkeitsfunktion und 16 Cluster-

methoden jeweils getestet. Pro Parametrisierung wurden 585.636 Bilderpaare verglichen, was insgesamt ca. 150 Mio. Anwendungen von ¨ Ahnlichkeitsfunktionen f¨ ur Fuzzy-Cluster-Strukturen bedeutete.

Etwas weniger aufwendig war die Clusterung der Bilder mittels des Fuzzy C-Means-Algorithmus inklusive der Adaption der Clusterzahl. Hier zeigte sich eine sehr unter- schiedliche Laufzeit bei Verwendung unterschiedlicher Abstandsmaße: So erzeugte das

Kapitel 5. Fuzzy-Bildklassifikation

zur Semi-Pseudo-Distanzfunktion umgewandelte Jaccard- ¨ Ahnlichkeitsmaß durchschnittlich sehr viele Cluster pro Bild w¨ ahrend die Manhattandistanzfunktion deutlich weniger generierte.

5.7.1 Fest definierte Cluster

Auch wenn in diesem Experiment im Gegensatz bei der sp¨ ater genutzten Fuzzy C-Means Clusteranalyse nur 16 statt 256 Kacheln verwendet worden sind, hat diese Clusterung den Vorteil, dass die Farbinformationen nicht so verwischt werden, wie es beim Fuzzy-C Means Cluster-Algorithmus der Fall ist: Bei den fest definierten Clustern z¨ ahlt die absolute und nicht relative Lage der Datenpunkte im Raum.

Tabelle 5.1: Klassifikationsergebnisse unter Verwendung fixer Cluster

Somit zeigte sich insgesamt, dass die Clusterung mittels der fest definierten Cluster die besten Ergebnisse liefert. Hier ist insbesondere das potenzierte Jaccard- ¨ Ahnlichkeitsmaß mit der T-Norm P rod und exponentiellen Faktor p = 10 hervorzuheben. Aber auch alle anderen Maße erreichten mindestens 69 %. Eine Ausnahme bildet die M-Distanz: Da bei diesem ¨ Ahnlichkeitsmaß die bijektive

Abbildung ungenutzt bleibt, kann es nicht die RGB-Attribute zwischen zwei Bildern

73 Kapitel 5. Fuzzy-Bildklassifikation

untereinander differenzieren: Es ist quasi ” farbenblind“ und betrachtet nur die Verteilung der summierten Farbintensit¨ aten und Kanten ¨ uber die einzelnen Kacheln. Dennoch

erreicht es trotz dieser deutlich schlechteren Voraussetzung immerhin noch eine Klassifikationsrate von ca. 60 %.

Des weiteren ist bei fast allen Experimenten eine hohe Standardabweichung bzw. Varianz zu verzeichnen. Dies liegt in den unterschiedlich ¨ ahnlichen Bildsammlungen begr¨ undet: So konnten beispielsweise Footballbilder sehr gut von laublosen B¨ aumen unterschieden werden, w¨ ahrend Universit¨ atsgeb¨ aude von Geb¨ auden in Barcelona weniger differenzierbar waren.

Die Laufzeit war insgesamt relativ hoch, da pro Bildpaar 512 Clustervergleiche statt-fanden, was deutlich ¨ uber dem Durchschnitt der im folgenden Abschnitt genutzen Fuzzy C-Means-Methode lag. Im Gegensatz dazu war aber der Clusterprozess extrem schnell, da nur Farbinformationen daf¨ ur umwandeln werden mussten.

5.7.2 Fuzzy C-Means mit euklidischen Abstand

Im zweiten Experiment wurde ausschließlich der euklidische Abstand beim Fuzzy C-Means-Algorithmus und dem Xie-Beni-Index verwendet. Als Ergebnis zeigt sich, dass die S-Distanz mit Fuzzy-Set- ¨ Ahnlichkeitsmaß dicht gefolgt von der B-Distanz und dem

¨ ahnlichen S-Distanzmaß mit Manhattan-Abstandsfunktion die besten Resultate liefern.

Tabelle 5.2: Klassifikationsergebnisse nach Fuzzy C-Means (Euklidischer Abstand)

Auff¨ allig ist die geringe Standardabweichung und eine Klassifikationsrate von nur

Kapitel 5. Fuzzy-Bildklassifikation 74

uber 50 % bei der Maximum- ¨ knapp ¨ Ahnlichkeitsfunktion, was darauf hindeutet, dass

diese Abstandsmaß mit dieser Cluster-Struktur fast nur zuf¨ allige Ergebnisse liefert. Dieses ist der großen Clustervektorl¨ ange von 256 Elementen begr¨ undet, in der nur ein Elementpaar entscheidend f¨ ur die ¨ Ahnlichkeit ist, was insgesamt einen sehr hohen Informationsverlust bedeutet.

Des weiteren stellt man fest, dass die T-Norm P rod bei allen Parametrisierungen schlechtere Klassifikationsraten als die M in mit Ausnahme der sowieso schon extrem schlecht funktionierenden Maximum- ¨ Ahnlichkeitsfunktion.

5.7.3 Fuzzy C-Means mit adaptiertem Abstandmaß

Im letzten Experiment werden alle ¨ Ahnlichkeitsfunktionen f¨ ur zwei Vektoren sowohl

zum Clustern als auch beim anschließenden Fuzzy-Cluster-Vergleich genutzt. Hier zeigt sich, inwieweit einzelne Clusteralgorithmen und ¨ Ahnlichkeitsfunktionen f¨ ur eine gute

Klassifikationsrate entscheidend sind und ob es sinnvoll ist, dass beide Algorithmentypen auf die gleichen Vektor¨ ahnlichkeitsfunktionen basieren.

Tabelle 5.3: Klassifikationsergebnisse nach FCM-Clustering (Adaptiertes Abstandsmaß)

Im Folgenden werden deshalb die Klassifikationsraten f¨ ur die ¨ Ahnlichlichkeitsfunktionen der adaptierten Fuzzy C-Means-Clusterpartitionen untersucht. Es zeigt sich, dass es durchgehend bessere oder gleiche Klassifikationsergebnisse als beim euklidischen Abstand sich ergeben, mit Ausnahme der Manhattan-Abstandsfunktion und der Fuzzy-Set- ¨ Ahn-

lichkeitsfunktion, welche offensichtlich kugelf¨ ormige Cluster bevorzugen.

Abbildung 5.1: Voll ¨ ahnliche Farbverl¨ aufe nach Kosinus- ¨ Ahnlichkeitsmaß im RGB-Farbraum

klassischen“ ¨ Ahnlichkeitsmaße bei den ¨ Umgekehrt scheinen die ” Ahnlichkeitsfunk-

Kapitel 5. Fuzzy-Bildklassifikation 76

tionen f¨ ur Fuzzy-Cluster-Konfigurationen den Minkowski-Metriken mit Ausnahme der Maximum-Distanz ein klein wenig unterlegen zu sein. Insgesamt zeigt die Kombination Kosinus-Clusterung und Manhattan- ¨ Ahnlichkeitsfunktion mit jeweils exponentiellen

Faktor von 10 und T-Norm P rod das beste Klassifikationsergebnis von 75,2 %. Ansonsten gibt es mit Ausnahme der Maximum-Distanzfunktion wenig Abweichungen: Alle sonstigen Parametrisierungen schafften mind. 62 % bei einer durchschnittlichen Quote von 64,6 %.

Als Ergebnis zeigt sich, dass eine harmonische Abstimmung zwischen Clusteralgorithmus und ¨ Ahnlichkeitsfunktion wichtig f¨ ur die jeweilige Applikation ist. Leider ist dies aufgrund der vielen m¨ oglichen Parameter sehr rechenaufwendig herauszufinden. So wurden in diesem Experiment beispielsweise nur zwei exp. Koeffizienten getestet; es liegt die Vermutung nahe, dass es noch einen besseren Skalierungsfaktor p außer 10 gibt. Auch weitere T-Normen oder weitere ¨ Ahnlichkeitsfunktionen k¨ onnen wahrscheinlich noch bes- sere Ergebnisse liefern.

Kapitel 6. Bewertung 77

Kapitel 6

Bewertung

6.1 Bewertung der Ergebnisse

In dieser Diplomarbeit wurden insgesamt vier Distanzfunktionen bzw. ¨ Ahnlichkeitsfunktionen f¨ ur Fuzzy-Clusterstrukturen untersucht bzw. entwickelt, wobei meist eine bijektive Abbildung der Datenpunkte vorausgesetzt worden ist. Leider zeigt die formale Untersuchung, dass es sich bei allen vier nur um Pseudo-Distanzfunktionen oder Semi-Pseudo-Distanzfunktionen handelt. Drei der vier untersuchten ¨ Ahnlichkeitsfunktionen sind sehr effizient berechenbar, da

die Komplexit¨ at pro Partition h¨ ochstens linear zur Clusterzahl bzw. Punktanzahl steigt. Besonders erw¨ ahnenswert ist in diesem Punkt die M-Distanz, welche die Entropie einer Partition bestimmt. Diesen Wert mit anderen Partitionen zu vergleichen, ist extrem schnell zu bewerkstelligen, wenn man beispielsweise alle Partitionen im Vorfeld nach deren Entropien sortiert. Sie ist somit f¨ ur sehr große Datenmengen einsetzbar und setzt auch keine bijektive Abbildung der Datenpunkte voraus. Im Gegensatz dazu hat die K-Distanz jedoch einen komplexen iterativen Berechnungsmechanismus, so dass diese nur bei sehr wenigen´Clustern und Datenpunkten Verwendung finden wird. Alle ¨ Ahnlichkeitsfunktionen wurden mehreren synthetischen Tests unterzogen: Clusterdrehungen um einen Mittelpunkt zeigen, wie diese Funktionen bei einer Verschiebung bzw. Permutation der Zugeh¨ origkeitswerte reagieren. Desweiteren wurden zwei verschiedene Vergleichstests zu unterschiedlich großen Clustern durchgef¨ uhrt: Im ersten Test konnten alle Funktionen die verschiedenen Gr¨ oßen differenzieren; im zweiten Test waren nicht alle Parametrisierungen der S-Distanz dazu in der Lage. Beim sog. hierarchischen Clustern wurde ein Cluster sukzessiv immer geteilt, wobei neue Konfiguration immer un¨ ahnlicher zum Ursprungscluster wurden. Auch ein Vergleich zwischen den Nachbarebenen wurde gezogen, wobei einige Funktionen nicht nur stetige Verl¨ aufe bzgl. der ¨ Ahnlichkeit und steigendem Teilungsgrad gezeigt haben. Von

allen durchgef¨ uhrten Experiment lieferte dieses insgesamt die meisten nicht erwarteten Ergebnisse.

Abschließend wurden die zwei Funktionen in einer praktische Anwendung auf rich-

Kapitel 6. Bewertung 78

tigen Daten in Form einer Bildersammlung getestet: Aus einem Bild wurde eine bestimmte Anzahl von Eigenschaftsvektoren extrahiert und diese anschließend nach mehreren Methoden geclustert. Danach wurde das Bild mit der h¨ ochsten ¨ Ahnlichkeit gesucht

und somit die Klasse dieses Bildes bestimmt. Es zeigt sich, dass optimales Clustern im Vorfeld eine gute Entscheidungsgrundlage f¨ ur diese Funktionen herstellt und das viele untersuchte Funktionen grunds¨ atzlich geeignet scheinen; eine Ausnahme bildete die Maximum¨ ahnlichkeitsfunktion unter Anwendung der Fuzzy-C Means Clusterung. Insgesamt wurde mit diesem Klassifikationstest erfolgreich der Schritt von der Theorie in die Praxis vollzogen; die hier entwickelten ¨ Ahnlichkeitsfunktionen bilden das vor-

erst letzte Glied in der Berechnungskette: Grundlage ist die Abbildung der Bilddaten auf einen Vektorraum und das Clusterns dieses Raumes mit diversen Fuzzy C-Means-Varianten oder fixen Clustern. Als Ergebnis kann man festhalten, das viele vorgestellte ¨ Ahnlichkeitsfunktionen gut mit den bereits entwickelten Fuzzy-Cluster-Grundlagen harmonieren.

6.2 Ausblick

Drei der hier behandelten ¨ Ahnlichkeitsfunktionen f¨ ur Fuzzy-Clusterstrukturen setzen

zwingend voraus, dass zu beiden vergleichenden Partitionen eine eineindeutige Abbildung der Datenpunkte vorliegt. Eine Erweiterung auf beliebig viele Datenpunkte w¨ urde deren Anwendungsbreite deutlich erh¨ ohen, da zwei unterschiedlich große Datensammlungen bzw. Datensammlungen bei denen nicht die gleiche Sortierung hergestellt werden kann, miteinander vergleichbar w¨ aren. Ein geeigneter Test ist f¨ ur diese Funktionen ist hier bereits vorgestellt: Bei der Drehung der Cluster um einen definiten Mittelpunkt beim

Ringtest m¨ ussen alle verglichenen Partitionen bei solch einer Funktion volle ¨ Ahnlichkeit

ergeben, wie es bei der M-Distanz der Fall ist.

Die explizite Konstruktion solch einer Funktionen wurde in dieser Diplomarbeit durch das entropiebasierte ¨

Ahnlichkeitsmaß M-Distanz realisiert; im Abschnitt 3.2 ist zus¨ atzlich gezeigt worden, wie ¨ Ahnlichkeitsfunktionen basierend auf ” sein k¨ onnten, damit sie diese Nebenbedingung nicht mehr voraussetzen m¨ ussen und dass diese keine h¨ ohere Laufzeit haben m¨ ussen im Vergleich zu Partitionen zu denen eine bijektiven Abbildung gegeben ist. Interessant w¨ aren dann beispielsweise vergleichende Tests zu Algorithmen, die beide Partitionsarten bew¨ altigen k¨ onnen. Bisher fehlt auch die Konstruktion einer echten nichttrivialen Distanzfunktion f¨ ur Fuzzy-Cluster-Partitionen, welche alle entsprechenden Eigenschaften, insbesondere die der Positivit¨ at, erf¨ ullt. Grundproblem ist bei vielen Funktionen, dass sie Mengen, jedoch nicht Multimengen von Clustern betrachten: Cluster k¨ onnen in theoretischen Randf¨ allen mehrfach vorkommen. Ob diese dann aber bessere Resultate bei praktischen Anwendungen, wie beispielsweise der vorgestellten Bildklassifikation erzielen, ist jedoch offen. Auch ist es m¨ oglich, auf Grundlage der bereits vorgestellten Funktionen diese zu erweitern oder noch variantenreicher zu parametrisieren. So ist es ¨ uberlegenswert, die

Kapitel 6. Bewertung 79

K-Distanz mit einer Kostenfunktion zu erweitern, einige Nebenbedingungen nicht zu ber¨ ucksichtigen, die Distanz ¨ uber eine andere Fehlerfunktion zu bestimmen oder sogar die Zielfunktion der quadratischen Minimierung zu ¨ andern. Bei der B-Distanz ist die Untersuchung weiterer Fuzzy-Implikationen m¨ oglich: da man diese aus einer T-Norm gewinnen kann, gibt es unendlich viele Parametrisierungen f¨ ur dieses Maß. Bei der S-Distanz wurden bereits diverse Parameter evaluiert: Dennoch gibt es wie bei der B-Distanz noch sehr viele M¨ oglichkeiten dieses ¨ Ahnlichkeitsmaß zu

instanziieren und deren Varianten untersuchen. Die M-Distanz sollte urspr¨ unglich durch Fuzzifizierung der ” Variation of Informa-

tion“-Funktion definiert werden, welche idealerweise die Metrik-Eigenschaft der Nicht-Fuzzy-Variante behalten sollte. Dieses ist jedoch durch einfache Erweiterung der Wahrscheinlichkeitsfunktionen nicht m¨ oglich; die Autorin befasst sich evtl. in Zukunft mit dieser Problematik.

Des weiteren werden momentan nur zwei Fuzzy-Cluster-Partitionen miteinander verglichen. In Abschnitt 3.4.3 ist ein Ansatz vorgeschlagen worden, die S-Distanz (bzw. die B-Distanz als Teilmenge dieser Funktion) rekursiv anzuwenden, so dass beliebig komplex aggregierte Fuzzy-Objektstrukturen vergleichbar w¨ aren, wie beispielsweise zwei Mengen von Fuzzy-Cluster-Partitionen.

Des weiteren ist ein interessanter Aspekt f¨ ur praktische Anwendungen die richtige Wahl der ¨ Ahnlichkeitsfunktion und deren Parameter. Diesen mit einem passenden Clus-teralgorithmus zu bestimmen, ist wohl der schwierigste Teil f¨ ur eine Implementation in praktischen Anwendungen.

Ein interessanter Ansatz f¨ ur dieses Problem ist aus dem Fuzzy-Clustering zu entnehmen: Beispielsweise erzeugt der sog. Gustafson-Kessel-Algorithmus [GK79] f¨ ur jedes Cluster dynamisch eine Parametrisierung einer verallgemeinerten Mahalanobis-Metrik, um die Clusterform an die Punktegeometrie optimal zu adaptieren. Diese k¨ onnte man bei der Vergleichsfunktion f¨ ur Fuzzy-Cluster-Partitionen ber¨ ucksichtigen bzw. Vergleichsfunktion definieren, welche diese Form der Cluster mit ber¨ ucksichtigen. Da der Schwerpunkt dieser Diplomarbeit bei den ¨ Ahnlichkeitsfunktionen liegt, ist dieser integrierte Ansatz nicht untersucht worden. Ein weitere M¨ oglichkeit ist die ¨

Konfigurationen nicht ausschließlich ¨ uber die Zugeh¨ origkeitsgrade zu definieren, sondern

auch die geometrische Lage der Datenpunkte, die Clusterformen und -zentren mitzuber¨ ucksichtigen: So wurde in dieser Diplomarbeit zwar die Qualit¨ at einer Clusterung uber den Xie-Beni-Index beurteilt, welche die beiden Faktoren ” Kompaktheit“ und ” Se¨

paration“ bewertet; diese k¨ onnten jedoch auch f¨ ur den Vergleich zweier Fuzzy-Cluster-Partitionen herangezogen werden. Es w¨ are beispielsweise vorstellbar, den Vergleich der beiden Clusterpartionen wieder auf den Vergleich zweier Cluster zu reduzieren: die ” Separation“ wird aus der Entfernung zum n¨ achsten Clusterzentrum bestimmt, die Kompaktheit genau wie beim Xie-Beni-Index. Ein ¨ Ahnlichkeitsergebnis w¨ are beispielsweise

wieder eine normalisierte Absolutdifferenz dieser beiden Faktoren, welche noch mitein- ander zu einer Gesamt¨ ahnlichkeit verkn¨ upft werden m¨ ussen.

Kapitel 6. Bewertung 80

Allerdings ist die Definition einer nichttrivialen Metrik f¨ ur die letzteren Vorschlag noch deutlich schwieriger, da neben den Zugeh¨ origkeitsgraden auch noch andere Attribute wie Clusterzentren und Datenpunkte f¨ ur die entsprechenden Metrik-Eigenschaften Selbstidentit¨ at, Positivit¨ at, Symmetrie und Dreiecksungleichung mit ber¨ ucksichtigt wer- den m¨ ussen.

Literaturverzeichnis

[Bor05] Christian Borgelt. Prototype-based Classification and Clustering. Fakult¨ at f¨ ur

Informatik, Otto-von-Guericke-Universit¨ at Magdeburg, 2005.

[Bra01] Josef Joshua Brandriss. Estimation of Origin-Destination Flows for Dynamic

Traffic Assignment. Massachusetts Institute of Technology, 2001.

[BT95] Gary Bryant and John C. Thomas. Improved Particle Size Distribution Mea-

surements Using Multiangle Dynamic Light Scattering. Massachusetts Institute of Technology, 1995.

[CB03] R. Kruse et al. C. Borgelt, F.Klawonn. Neuro-Fuzzy-Systeme, 3. Auflage. Vieweg Verlag, 2003.

[CLL96] Richard J. Hanson Charles L. Lawson. Solving Least Squares Problems. Prentice-Hall, 1996.

[Con84] C. Constantinescu. Spaces of Measures. De Gruyter studies in mathematics, 1984.

[DL91] M. M. Deza and M. Laurent. Geometry of Cuts and Metrics. Springer, 1991.

[DP80] D. Dubois and H. Prade. Fuzzy Set and Systems: Theory and Applications.

Academic Press, 1980.

[Dun73] J. C. Dunn. A fuzzy relative of the isodata process and its use in detecting

compact well-separated clusters. Journal of Cybernetics, 3:32-57, 1973.

[Dun03] Margaret H. Dunham. Data Mining, Introductory and Advanced Topics. Pear-

son Education, Inc., 2003.

[EKS ⁺ 98] M. Ester, H.-P. Kriegel, J. Sander, M. Wimmer, and X. Xu. Incremental

[FM83] E. B. Fowlkes and C. L. Mallows. A method for comparing two hierachical

clusterings. Journal of the American Statistical Association, 78:553-569, 1983.

[GK79] E.E. Gustafson and W.C. Kessel. Fuzzy Clustering with a Fuzzy Covariance

Matrix. IEEE Press, 1979.

[Jac01] P. Jaccard. Distribution de la flore alpine dans le bassin des dranses et dans

[JB06] Eyke H¨ ullermeier J. Beringer. Online Clustering of Parallel Data Streams. Fakult¨ at f¨ ur Informatik, Otto-von-Guericke-Universit¨ at Magdeburg, 2006.

[Knu76] Donald E. Knuth. Big omicron and big omega and big theta. SIGACT News, 8(2):18-24, 1976.

[Kun00] Ludmila I. Kuncheva. Fuzzy Classifier Design. Physica-Verlag, 2000.

[Lev97] Haim Levkowitz. Color theory and modeling for computer graphics, visuali-

zation, and multimedia applications. Kuwer Academic Publishers, 1997.

[Low96] R. Lowen. Fuzzy Set Theory - Basic Concepts, Techniques and Bibliography.

Kuwer Academic Publishers, 1996.

[Luk70] J. Lukasiewicz. Selected Works. North-Holland, Amsterdam, Holland, 1970.

[Mei07] Marina Meil˘ a. Comparing clusterings - an information based distance. Journal of Multivariate Analysis, 98(5):873 - 895, 2007.

[Mir96] Boris Mirkin. Mathematical classification and clustering. Kluwer Academic Press, 1996.

[Ran71] W. M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66:846-850, 1971.

[vR79] C.J. van Rijsbergen. Information Retrieval. Butterworth, London, 1979.

[Wal83] David L. Wallace. Comment. Journal of the American Statistical Association, 78:569-576, 1983.

[Wan00] Yong Wang. A New Approach to Fitting Linear Models in High Dimensio-

[Wek06]Weka. Weka Machine Learning Project. The University of Waikato, 2006.

[XB91] L. X. Xie and G. Beni. Validity measure for fuzzy clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8:841 - 847, 1991.

[ZRL96] T. Zhang, R. Ramakrishnman, and M. Linvy. BIRCH: An Efficient Method for Very Large Databases. Montreal, Canada, 1996.

Anhang A. Anhang 84

Anhang A

A.1 Beispiele f¨ ur die Verletzung der Dreiecksunglei-

chung

Im Folgenden sind pro Distanzmaß d(X, Y ) drei Partitionen beschrieben, die folgende Ungleichung verletzten:

(A.1) d(A, B) + d(B, C) − d(A, C) >= 0

Die Partitionen sind dabei mit Hilfe der Clustervektoren beschrieben; es wurde versucht, m¨ oglichst einfache Beispiele zu generieren, wobei in allen bis auf einen Fall pro Partition zwei Cluster und zwei Datenpunkte ausreichten.

B-Distanz:

0.08 0.92 0.46 0.54 0.33 0.67

(A.2) A = B = C = , , ,

0.93 0.07 0.93 0.07 0.31 0.69

K-Distanz:

0.02 0.98 0.81 0.19 0.17 0.83

(A.3) A = B = C = , , ,

0.99 0.01 0.28 0.72 0.35 0.65

S-Distanz mit Kosinus- ¨ Ahnlichkeitsfunktion und T-Norm M in :

0.38 0.62 0.55 0.45 0.93 0.07

(A.4) A = B = C = , , ,

0.37 0.63 0.01 0.99 0.01 0.99

S-Distanz mit Dice- ¨ Ahnlichkeitsfunktion und T-Norm M in :

0.80 0.20 0.11 0.89 0.03 0.97

(A.5) A = B = C = , , ,

0.98 0.02 0.17 0.83 0.26 0.74

Anhang A. Anhang

S-Distanz mit Jaccard- ¨ Ahnlichkeitsfunktion und T-Norm M in :

0.97 0.03 0.86 0.14 0.22 0.78

(A.6) A = B = C = , , ,

0.77 0.23 0.81 0.19 0.10 0.90

S-Distanz mit Manhattan- ¨ Ahnlichkeitsfunktion und T-Norm P rod :

0.45 0.55 0.60 0.40 0.98 0.02

(A.7) A = B = C = , , ,

0.02 0.98 0.43 0.57 0.43 0.57

S-Distanz mit Euklid- ¨ Ahnlichkeitsfunktion und T-Norm P rod :

(A.8)

S-Distanz mit Maximum- ¨ Ahnlichkeitsfunktion und T-Norm P rod :

0.93 0.07 0.37 0.63 0.08 0.92

(A.9) A = B = C = , , ,

0.16 0.84 0.51 0.49 0.13 0.87

S-Distanz mit Fuzzy-Set- ¨ Ahnlichkeitsfunktion und T-Norm P rod :

0.13 0.87 0.51 0.49 0.47 0.53

(A.10) A = B = C = , , ,

0.49 0.51 0.48 0.52 0.91 0.09

S-Distanz mit Kosinus- ¨ Ahnlichkeitsfunktion und T-Norm P rod :

0.95 0.05 0.19 0.81 0.13 0.87

(A.11) A = B = C = , , ,

0.42 0.58 0.40 0.60 0.01 0.99

S-Distanz mit Dice- ¨ Ahnlichkeitsfunktion und T-Norm P rod :

0.40 0.60 0.28 0.72 0.04 0.96

(A.12) A = B = C = , , ,

0.97 0.03 0.53 0.47 0.24 0.76

S-Distanz mit Jaccard- ¨ Ahnlichkeitsfunktion und T-Norm P rod :

0.14 0.86 0.33 0.67 0.58 0.42

(A.13) A = B = C = , , ,

0.93 0.07 0.75 0.25 0.62 0.38

S-Distanz mit Euklid- ¨ Ahnlichkeitsfunktion und T-Norm Lukasiewicz :

0.17 0.83 0.78 0.22 0.98 0.02

(A.14) A = B = C = , , ,

0.42 0.58 0.40 0.60 0.02 0.98

86 Anhang A. Anhang

S-Distanz mit Maximum- ¨ Ahnlichkeitsfunktion und T-Norm Lukasiewicz :

(A.15) A =

S-Distanz mit Fuzzy-Set- ¨ Ahnlichkeitsfunktion und T-Norm Lukasiewicz :

0.46 0.54 0.26 0.74 0.92 0.08

(A.16) A = B = C = , , ,

0.80 0.20 0.69 0.31 0.45 0.55

S-Distanz mit Kosinus- ¨ Ahnlichkeitsfunktion und T-Norm Lukasiewicz :

0.78 0.22 0.91 0.09 0.99 0.01

(A.17) A = B = C = , , ,

0.01 0.99 0.51 0.49 0.66 0.34

S-Distanz mit Dice- ¨ Ahnlichkeitsfunktion und T-Norm Lukasiewicz :

0.97 0.03 0.37 0.63 0.20 0.80

(A.18) A = B = C = , , ,

0.55 0.45 0.34 0.66 0.91 0.09

S-Distanz mit Jaccard- ¨ Ahnlichkeitsfunktion und T-Norm Lukasiewicz :

0.37 0.63 0.68 0.32 0.79 0.21

(A.19) A = B = C = , , ,

0.11 0.89 0.32 0.68 0.25 0.75