Untersuchung und Vergleich von Ähnlichkeitsmaßen von Fuzzy-cluster-Strukturen

INHALTSVERZEICHNIS

Abbildungsverzeichnis

Tabellenverzeichnis

1 Einleitung
1.1 Das Sandhaufenparadoxon
1.2 Ähnlichkeitsfunktionen für Fuzzy-Cluster-Strukturen
1.3 Gliederung der Arbeit

2 Grundlagen
2.1 Einführung: Fuzzy-Logik
2.1.1 Fuzzifizierung aussagenlogischer Ausdrücke
2.1.2 Verschiedene T-Normen und T-Conormen
2.2 Cluster-Analyse
2.2.1 Daten auswählen
2.2.2 Daten vorbereiten
2.2.3 Auswahl eines Clusteralgorithmus
2.2.4 K-Means
2.2.5 Fuzzy C-Means
2.2.6 Wahl der Clusteranzahl

3 Entwicklung von Ähnlichkeitsmaßen
3.1 Distanzfunktionen und Ähnlichkeitsmaße
3.1.1 Definition
3.1.2 Umwandlung von Distanzfunktionen und Ähnlichkeitsmaße in nor- mierte Ähnlichkeitsmaße
3.2 Vergleich von Cluster-Partitionen
3.2.1 Cluster-Partitionen-Vergleich unter verschiedenen Randbedingungen
3.2.2 Gewinnung von Eigenschaftskoeffizienten von Clusterpaaren
3.3 Ähnlichkeitsfunktionen für Clusterpaare
3.3.1 Distanzfunktionen als normierte Ähnlichkeitsmaße
3.3.2 Skalierung von Ähnlichkeitsmaßen
3.3.3 Eigenschaftsbeschränkungen von Cluster-Partitionen in dieser Arbeit
3.4 S-Distanz
3.4.1 Formale Eigenschaften
3.4.2 Komplexität
3.4.3 Rekursive Anwendung auf Multimengen und Listen
3.5 B-Distanz
3.5.1 Definition
3.5.2 Weitere Implikationsklassen
3.5.3 Ähnlichkeit zur S-Distanz
3.6 M-Distanz
3.6.1 Definition
3.6.2 Formale Eigenschaften
3.6.3 Komplexität
3.7 K-Distanz
3.7.1 Definition
3.7.2 Geometrische Interpretation
3.7.3 Erweiterung der Quadratfehlersummen- ”Nichtnegativenkleinste methode“
3.7.4 Transformation des Abstandproblems
3.7.5 Epsilon-Wahl
3.7.6 Formale Eigenschaften
3.7.7 Komplexität
3.7.8 Varianten

4 Evaluationstests in künstlichen Umgebungen
4.1 Ring-Methode
4.1.1 Auswertung
4.2 Semiverifikation der Dreiecksungleichung
4.3 Vergleich unterschiedlich großer Cluster mittels Datenpunktzuordnungen
4.4 Vergleich unterschiedlich großer Cluster durch Variation der Zugehörig- keitsgrade
4.5 Hierarchische Clustermethoden
4.5.1 Split-Methode
4.5.2 Auswertung

5 Fuzzy-Bildklassifikation
5.1 Klassifikation mittels Ähnlichkeitsmaßen
5.2 Die Bildersammlung
5.3 Extraktion von Eigenschaftvektoren eines Bildes
5.4 Clusterung der Datenpunkte
5.5 Verwendete Ähnlichkeitsmaße
5.6 Klassifikationsraten
5.7 Auswertung
5.7.1 Fest definierte Cluster
5.7.2 Fuzzy C-Means mit euklidischen Abstand
5.7.3 Fuzzy C-Means mit adaptiertem Abstandmaß

6 Bewertung
6.1 Bewertung der Ergebnisse
6.2 Ausblick

Literaturverzeichnis

A Anhang

A.1 Beispiele für die Verletzung der Dreiecksungleichung

Abbildungsverzeichnis

1.1 Sandkornmengen und deren Zugehörigkeit zu verschiedenen Konzepten

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

3.1 Normiertes Kosinus- Ähnlichkeitsmaß in der Ebene zum Vektor (1, 1)T . .

3.2 Jaccard- Ähnlichkeitsmaß in der Ebene zum Vektor (1, 1)T

3.3 Zwei Cluster mit gleichen Zugehörigkeitsvektoren und unterschiedlichen Zentren

3.4 Entropien der einzelnen Teilmengen und deren Verknüpfungen

3.5 K-Distanz: Berechnungszeit in Abhängigkeit von Clusteranzahl und Di mension

4.1 Ringmethode: B-Distanz

4.2 Ringmethode: S-Distanz (.Min) mit Minkowski-Metriken

4.3 Ringmethode: S-Distanz (.Prod) mit Minkowski-Metriken

4.4 Ringmethode: S-Distanz(.Min) mit 51 ”natürlichen“Ähnlichkeitsfunktionen

4.5 Ringmethode: .Prod mit ”natürlichen“Ähnlichkeitsfunktionen [52]

4.6 Ringmethode: K-Distanz [53]

4.7 Clustergrößenvergleich mittels Datenpunktzuordnungen: S-Distanz (.Min) mit Minkowski-Metriken

4.8 Clustergrößenvergleich mittels Datenpunktzuordnungen: S-Distanz (.Min) mit 57 ”natürlichen“Ähnlichlichkeitsfunktionen

4.9 Clustergrößenvergleich mittels Datenpunktzuordnungen: S-Distanz (.Prod) mit Minkowski-Metriken

4.10 Clustergrößenvergleich mittels Datenpunktzuordnungen: S-Distanz (.Prod) mit Ähnlichlichkeitsfunktionen

4.11 Clustergrößenvergleich mittels Datenpunktzuordnungen: K-Distanz

4.12 Fuzzy-Größenvergleich: B-Distanz und S-Distanz mit Minkowski-Metriken

4.13 Cluster-Größenmethode: S-Distanz (.Min) mit Ähnlichkeitsfunktionen

4.14 Clustergrößenmethode: S-Distanz (.Prod) mit Ähnlichkeitsfunktionen

4.15 Fuzzy-Größenvergleich: K-Distanz

5.1 Voll ähnliche Farbverläufe nach Kosinus-Ähnlichkeitsmaß im RGB- Farbraum

2.1 Dreiwertige Logik: die ”Und“-Verknüpfung

4.1 Erfüllung der Dreiecksungleichung diverser Ähnlichkeitsfunktionen für Fuzzy-Cluster-Konfigurationen

4.2 Hierachische Splits: Ähnlichkeit / Distanz zwischen den Nachbarebenen

4.3 Hierachische Splits: Ähnlichkeit / Distanz zwischen Wurzelebene und tieferen Ebenen

5.1 Klassifikationsergebnisse unter Verwendung fixer Cluster

5.2 Klassifikationsergebnisse nach Fuzzy C-Means (Euklidischer Abstand)

5.3 Klassifikationsergebnisse nach FCM-Clustering (Adaptiertes Abstandsmaß)

5.4 Durchschnittliche Klassifikationsraten nach Cluster- und Ähnlichkeits- funktion

Kapitel 1 Einleitung

1.1 Das Sandhaufenparadoxon

Der klassische Begriff der Wahrheit postuliert kontrastreiches und kategorisches Den- ken, welches unsere Welt einerseits leichter erfassbar macht, andererseits aber unsere Wahrnehmungsweise stark abstrahiert und dadurch verfälscht. Die Formalisierung die- ses Denkens führt in die Wissenschaft der Mathematik, in der der Mensch versucht, Wahrheiten in Form von abstrakten Sätzen zu verankern. Speziell die Teildisziplin der

binären Logik ist dazu geeignet, bestimmte Aussagen nach

”Wahr“oder ”Falsch“zu

klassifizieren. Dennoch scheinen damit nicht alle Phänomene erfassbar zu sein.

Als Beispiel sei das Sandkornparadoxon genannt: Die binäre mathematische Definiti- on eines solchen Sandhaufens mittels einer intuitiven Regel erweist sich letztendlich als widersprüchlich. Es sei ein Sandhaufen mit einer definiten Anzahl von Sandkörnern gege- ben. Des weiteren gelte die Regel, dass durch Hinzufügen oder Entfernen eines einzelnen Sandkornes ein Sandhaufen nicht als solcher entartet wird: er bleibt ein Sandhaufen.

Abbildung [1].[1]: Sandkornmengen und deren Zugehörigkeit zu verschiedenen Konzepten Durch Induktion kann gezeigt werden, dass nach diesen Axiomen sowohl ein einzelnes

Sandkorn als auch eine ganze Wüste voller Sandkörner wieder ein Sandhaufen in diesem mathematischen Sinne bildet. Wann hört also ein Sandhaufen auf zu existieren? Die willkürliche Angabe eines Sandkornanzahlbereiches ist vermutlich ungeeignet. Es scheint eher so, dass der Sandhaufen beim Wachsen zu einer Wüste und Schrumpfung zu einem einzelnen Sandkorn schleichend über viele Metazustände sein Dasein als Sandhaufen verliert. Als nächstes kann man sich fragen, wieviele Sandkörnern nötig sind, damit der Sandhaufen den stabilsten Zustand als solchen erreicht.

Letztendlich scheint das imaginäre 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ürlich erscheinen, jedoch reicht in diesem Falle der Glaube an die bloße Existenz eines solchen aus, um das Paradoxon zu lösen.

1.2 Ähnlichkeitsfunktionen für Fuzzy-Cluster- Strukturen

Diese eher philosophische Betrachtung des Sandhaufenparadoxons führt dazu, dass wir in unserer Umwelt weitere ähnliche Probleme identifizieren: Wieviele Bäume benötigt 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önnen sich von Individuum zu Individuum unterscheiden: So würde der Begriff ”reich“wohlvonNaturvölkernandersdefiniertwerdenalsvonVertreternder Industrienationen.

Aber nicht nur der Mensch möchte solche Phänomene in seinem bestimmten Kontext identifizieren können: In Zeiten der massiven Informationsverarbeitung wird es immer wichtiger, dass auch Computer diese Fähigkeit erwerben, zumal häufig die Ein- und Aus- gabe der Daten von Menschenseite bzw. für diesen erfolgt und deren Abstraktionssicht jeweils berücksichtigt werden muss. Dazu ist neben der Prototypenbildung die Definition von Ähnlichkeitsfunktionen zu diesen Prototypen notwendig. Solche Algorithmen fallen unter der sog. Kategorie

”Fuzzy-Clustering“undbildenMetazuständefüreineMenge von Objekten zu einzelnen Konzepten.

Dennoch ist die alleinige Bildung solcher Metazustände uninteressant: Erst der Ver- gleich zweier Objekte und deren Metazustände bezüglich mehreren Konzepten ermöglicht die sinnvolle Verarbeitung dieser generierten Informationen. Die Definition und Evalua- tion formaler und anwendungsbezogener Art dieser Funktionen bilden den Schwerpunkt dieser Diplomarbeit. Sie heißen Ähnlichkeitsfunktionen für Fuzzy-Cluster-Strukturen.

Ziel dieser Diplomarbeit ist es, geeignete Ähnlichkeitsfunktionen für Fuzzy-Cluster- Strukturen unter Beachtung verschiedener Randbedingungen zu kreieren und sie bzw. andere bereits definierte Funktionen auf bestimmten Kontexten hin zu testen. Als Ergeb-nis lassen sich Algorithmen ableiten, welche für Computer die automatische Auswertung solch unscharfer Informationen ermöglicht.

1.3 Gliederung der Arbeit

Nach diesem Einleitungskapitel erfolgt zunächst die Einführung der benötigten Grund- lagen in den Bereichen Fuzzy-Logik und Clusteranalyse. Anschließend wird der Fuzzy C-Means-Algorithmus vorgestellt, der eine unscharfe Clusterung ermöglicht; dieser Al- gorithmus kann viele verschiedenen Parametrisierungen annehmen, was in unterschiedli- chen Fuzzy-Cluster-Partitionen resultiert. Um die Qualität dieser Partitionen zu ermit- teln, wird der Xie-Beni-Index eingeführt, welcher eine Bewertung nach zwei verschiedenen Kriterien vornimmt.

Im dritten und umfangreichsten Kapitel werden insgesamt vier Fuzzy Cluster- Ähnlichkeitsfunktionsklassen entwickelt und der Nachweis ihrer formalen Eigenschaften erbracht. Auch verschiedene Parametrisierungen, Komplexitätsfragen, Normalisierungen und algorithmische Umsetzung zu diesen Funktionen werden behandelt.

Anschließend erfolgen im vierten Kapitel Tests in künstlichen geschaffenen Umgebun- gen: Ziel ist Erarbeitung von charakteristischen Eigenschaften der zuvor vorgestellten Ähnlichkeitsfunktionen bei kontrollierten und verifizierbaren Datensätzen; so ist es bei vielen dieser Experimente möglich, das Resultat mathematisch nachzuvollziehen.

Um sich nicht ausschließlich auf künstliche Tests zu verlassen, wird im fünften Kapitel ein realitätsnäheres Anwendungsszenario vorgestellt: Mittels Bildklassifikation zeigt sich, wie gut die Ähnlichkeitsfunktionen in der Praxis funktionieren können 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

In diesem Kapitel werden ausgewählte Grundlagen in den Bereichen Cluster-Analyse und Fuzzy-Logik erörtert, welche für spätere Kapiteln benötigt werden, in denen u. a. Fuzzy- Ähnlichkeitsfunktionen konstruiert und evaluiert werden.

2.1 Einführung: Fuzzy-Logik

Die binäre Logik umschreibt ausschließlich die beiden Zustände ”Wahr“und ”Falsch“, welche zu absoluten und scharfen Grenzen in Ontologien führen. Diesen grundlegenden Nachteil der binären Logik erkannte bereits Platon, welcher vermutet hat, dass es noch einen dritten Zustand zwischen Wahr und Falsch geben müsste.

Bestimmte Konzepte, wie das in der Einleitung vorgestellte Sandhaufenparadoxon lassen sich mit nur zwei Zuständen nicht darstellen. Auch bei anderen Begriffen, wie bei- spielsweise Farben, welche der Kategorie ”Grün“zugeordnetwerden,trittdiesesPhäno- men auf: Je nachdem wieviel prototypischen Grünanteil eine Farbe hat, desto eher würde man sie auch als ”Grün“bezeichnen.EswerdensomitdeutlichmehrZuständezwischen ”Wahr“und ”Falsch“benötigt.

[1920] führte Lukasiewicz als erstes dreiwertige Logik ein, die die binäre Logik um zumindest einen neuen Zustand erweiterte [Luk[70]]:

Abbildung in dieser Leseprobe nicht enthalten

[1] ”Und“-Verknüpfung Später entwickelte er die fünfwertige und zuletzt die unendlichwertige Logik, welche schließlich alle Wahrheitwerte aus dem Intervall [[0]..[1]] zuläßt. Als Begründer der sog.

Fuzzy-Logik gilt jedoch L. A. Zadeh, der [1965] die ”Fuzzy-Menge“einführteundexplizit ein mathematisches Konzept kreierte, welches in der Lage ist, unscharfe Begriffe wie ”Grün“zubeschreiben.

2.1.1 Fuzzifizierung aussagenlogischer Ausdrücke

Um aussagenlogische Ausdrücke von der binären Logik auf die Fuzzy-Logik zu erwei- tern, ist eine Definition der grundlegenden Operationen ”Nicht“, ”Und“und ”Oder“ notwendig. Dabei ist die Einhaltung verschiedener Randbedingungen notwendig, um zu erreichen, dass die binäre Logik eine Teilmenge der Fuzzy-Logik darstellt.

Die ”Und“-Verknüpfungwirddurcheinesog..-Normrealisiert,welchefolgendeBe- dingungen erfüllen muss:

(2.1)

Abbildung in dieser Leseprobe nicht enthalten

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

(2.2)

Abbildung in dieser Leseprobe nicht enthalten

Neben dieser Form existieren noch weitere Negationsmöglichkeiten, welche aber hier nicht weiter behandelt werden.

Die sog. ⊥-Conorm, welche der

”Oder“-Verknüpfungentspricht,kanndurchAnwen- dung der Demorganschen Gesetze hergeleitet werden; dieses Gesetz soll aufgrund der Teilmengenbeziehung nicht nur in der binären Logik, sondern auch in der Fuzzy-Logik gelten:

(2.3)

Abbildung in dieser Leseprobe nicht enthalten

Übertragen auf die Fuzzy-Logik ist die ⊥-Conorm wie folgt definiert:

(2.4)

Abbildung in dieser Leseprobe nicht enthalten

Die Eigenschaften der T-Norm gelten in gleicher oder ähnlicher Weise auch für die T-Conorm ⊥:

(2.5)

Abbildung in dieser Leseprobe nicht enthalten

Da das Assoziativgesetz sowohl für die T-Norm als auch für die T-Conorm gilt, kann man eine abkürzende Schreibweise für die Verknüpfung von endlich vielen Elementen für diese beiden Funktionen einführen. Sei dazu A = (a1, a2, . . . , an) die Menge der zu verknüpfenden Elemente. Dann gilt:

(2.6)

Abbildung in dieser Leseprobe nicht enthalten

(2.7)

Abbildung in dieser Leseprobe nicht enthalten

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ührte die erste T-Norm ein, welche durch ihre Einfachheit einige Vorteile aufweist:

(2.8)

Abbildung in dieser Leseprobe nicht enthalten

.Min(a, b) = min(a, b) ⊥Min(a, b) = max(a, b)

So lässt sich diese T-Norm bei Verknüpfung 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ür die duale T-Conorm.

Weitere bekannte T-Normen sind .Prod und .Lukasiewicz :

(2.9)

Abbildung in dieser Leseprobe nicht enthalten

(2.10)

Abbildung in dieser Leseprobe nicht enthalten

Bei der Berechnung der T-Norm .Prod fließen beide Elemente in das Ergebnis ein und nicht nur das kleiner bzw. größere Element. Der Steigungsgradient dieser Funktion ändert sich damit weniger abrupt als bei der T-Norm .Min und der Informationsverlust ist geringer. Ein noch stärker Informationsverlust ereignet sich bei der T-Norm .Lukasiewicz: Insbesondere bei Verknüpfung 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ür Anwendungen aufgrund des maximalen Informationsverlustes in der Regel nicht geeignet ist, aber dafür formale Eigenschaften im Grenzbereich von T-Normen zeigt:

Abbildung in dieser Leseprobe nicht enthalten

Neben diesen bekannten T-Normen gibt es parametrisierte, welche eine unendlich große Klasse von T-Normen bilden können. Als Beispiel sei hier die Yager-Familie erwähnt [CB[03]], welche durch geeignete Parameterwahl auch .Prod und .Lukasiewicz erzeugen können. Diese wird jedoch im weiteren nicht betrachtet: Spätere Konzepte benötigen zwar die Wahl einer T-Norm, jedoch beschränkt sich diese Arbeit nur mit den gerade vorgestellten ”klassischen“T-Normen.

2.2 Cluster-Analyse

Mit Hilfe einer Cluster-Analyse lassen sich ähnliche Daten zu sog. Clustern zusammenfas- sen. Diese repräsentieren jeweils eine Klasse, die einen oder mehrere Datensätze enthält. Die Cluster-Analyse ist dabei eine Methode des maschinellen Lernens; der Lernpro-zess ist unüberwacht, da die Clusteralgorithmen keine Rückkopplung 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üssen diese auf Eignung selektiert und anschließend für 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ätere 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ät der Cluster-Analyse.

2.2.1 Daten auswählen

In Datensammlungen existieren zu einem Datensatz häufig 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

lässt; dies senkt den Berechnungsaufwand und erhöht häufig die Genauigkeit der Cluster- Analyse.

Korrelationslose Daten könnten beispielsweise die zufällige Kundennummer und Kontonummer eines Kunden sein, da diese zusammen wohl keine weiteren Rückschlüsse auf andere Attribute wie beispielsweise Einkaufsverhalten zulässt.

2.2.2 Daten vorbereiten

Datensätze bestehen häufig aus unterschiedlichsten Typen von Attributen: So kann beispielsweise einer Person eine Körpergröße, eine Augenfarbe, eine Adresse und ein Kontostand 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öglichst repräsentativ 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ürfel genannt, in dem sich alle Datenvektoren befinden sollten.

Hierbei gibt es je nach Typ mehreren Möglichkeiten:

- Lineare Normalisierung von reellen Attributen (z. B. Körpergröße) auf Basis des größten und kleinsten Datensatzes in der Sammlung
- Nichtlineare Normalisierung (z. B. Kontostand: Ein einzelner sehr hoher Kontostand würde bei linearerer Normalisierung Unterschiede stark verwischen). Hier könnte beispielsweise eine logarithmische Abbildungsfunktion helfen.
- Diskretisierung von Aufzählungsattributen (z. B. Augenfarbe): f (blau) = 0.0, f (gr ün) = 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ät 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ächs- ten Abschnitt vorgestellten K-Means-Algorithmus hingegen ist die Clusterzahl vorher festzulegen; diese sollten möglichst kugelförmig ausfallen bzw. je nach verwendeten Abstandsmaß bestimmten Formen ähneln.

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ässt, dass die Clusterzahl sich verringert. Ausgehend von einem Cluster, der alle Datensätze 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ür die Qualität der Cluster-Analyse. Diese kann durch sog. Qualitätsmaß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ötigt werden, aber der Schwerpunkt dieser Arbeit nicht in der Cluster-Analyse liegt, wird nur ein einzelner Fuzzy-Cluster-Algorithmus vorgestellt. Für 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ällig über den Daten-Vektorraum verteilt; jeder Datenpunkt wird dem nächsten Clusterzentrum zugeordnet. Nun erfolgt eine Neuberechnung der Clusterzentren ci aufgrund der m zugeordneten Punkte tij :

(2.12)

Abbildung in dieser Leseprobe nicht enthalten

Im nächsten Schritt werden die Zugehörigkeitsgrade basierend auf dem Abstand zu den Clusterzentren bestimmt; das Verfahren wird dann iterativ solange fortgesetzt, bis die Änderungen der k Clusterzentren ci einen definiten Schwellenwert ϵref unterschreiten:

(2.13)

Abbildung in dieser Leseprobe nicht enthalten

Zu bemerken ist, dass dieser Algorithmus höchstens k Cluster produziert, da bei der Neuzuordung der Datenpunkte zu Clustern der Fall eintreten kann, das einem Cluster gar keine Datenpunkte zugeordent werden können; dies macht eine Neuberechnung des Clusterzentrums unmöglich und das Cluster wird nicht weiter berücksichtigt.

Abbildung in dieser Leseprobe nicht enthalten

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

Je höher die Clusterzahl und je geringer die Datenpunktanzahl desto höher die Wahrscheinlichkeit, dass Cluster gelöscht werden müssen. Auch eine hohe Dichte in wenigen Clustern erhöht die Wahrscheinlichkeit für diesen Fall.

Die Clusterzahl wird durch diesen Algorithmus reduziert werden, wenn k größer ist, als die Anzahl der Datenpunkte.

2.2.5 Fuzzy C-Means

Eine Fuzzifizierung des K-Means Clusteralgorithmus führt zu dem sog. Fuzzy C-Means- Algorithmus: Er unterscheidet sich darin, dass er die Zugehörigkeitsgrade der Punkte in Abhängigkeit zur Entfernung der Clusterzentren vergibt und dass auch die Neube- rechnung der Clusterzentren durch die Zugehörigkeitsgrade der Punkte gewichtet wird. [Dun73]

Formal ändert sich der Algorithmus wie folgt: Sei uij der Zugehörigkeitsgrad des Datenpunktes xi zu Cluster cj und d(x, y) eine Abstandsfunktion für zwei Vektoren. Nach der zufälligen Cluster-Zentrums-Initalisierung, wird die Zugehörigkeitsmatrix berechnet:

(2.14)

Abbildung in dieser Leseprobe nicht enthalten

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

(2.15)

Abbildung in dieser Leseprobe nicht enthalten

Wie beim K-Means-Algorithmus werden die Clusterzentren iterativ solange verfeinert, bis nur noch marginale Änderungen in der Zugehörigkeitsmatrix bzw. in den Clusterzentrumsvektoren 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önnen Applikationen, die eine bestimmte Anzahl von Clustern für einen Daten- satz generieren müssen, 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ächsten Abschnitt beschrieben.

Deshalb wird in dieser Arbeit auch ausschließlich dieser Algorithmus als

”echter“

Fuzzy-Cluster-Algorithmus genutzt. Andere Möglichkeiten, Fuzzy-Clusterstrukturen zu erzeugen werden später zwar auch genutzt, jedoch bleibt die geometrische Lage der Da- tenpunkte im Raum unberücksichtigt oder die Clusterzentren werden fest vordefiniert.

2.2.6 Wahl der Clusteranzahl

Um für einen gegebenen Datensatz die optimale Clusteranzahl für den Fuzzy C-Means- Algorithmus zu finden, ist es notwendig die Qualität einer dazugehörigen 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ätzlich auch mehrere Durchläufe für eine bestimmte Clusteranzahl von Vorteil: Der Durchlauf mit der besten Qualität repräsentiert dann die Gesamtqualität für eine bestimmte Clusteranzahl.

Im Folgenden verwenden wir den sog. Xie-Beni Index [XB91], der zwei Teilkriterien einer Clusterstruktur nutzt: Ein Cluster sollte möglichst kompakt sein, was bedeutet, dass ein Datenpunkt möglichst dicht am Clusterzentren liegt und somit einen tenden- ziell hohen Zugehörigkeitsgrad 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, cj einer von m Clusterzentren, xi einer von n Datenpunkten, uij der Zugehörigkeitsgrad von Datenpunkt xi zu Cluster cj und d(x, y) eine Abstandsfunktion für zwei Vektoren. Formal wird die Intra-Cluster- Distanz dann nach folgender Funktion berechnet:

Abbildung in dieser Leseprobe nicht enthalten

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ächsten Clusterzentrum:

(2.17)

Abbildung in dieser Leseprobe nicht enthalten

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ücksichtigt, welche die Gesamtqualität einer Clusterkonfiguration repräsentiert:

(2.18)

Abbildung in dieser Leseprobe nicht enthalten

Dieser muss insgesamt möglichst minimiert werden, um eine qualitativ hochwertige Clusterkonfiguration zu erreichen.

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

Abbildung in dieser Leseprobe nicht enthalten

Kapitel 3 Entwicklung von Ähnlichkeitsmaßen

Ähnlichkeitsmaße sind Funktionen, die entscheiden inwieweit zwei Objekte gleich- artig sind. Dabei sind sie für bestimmte Objekttypen spezialisiert: Viele bekann- te Ähnlichkeits- bzw. Abstandsfunktionen gibt es für Punkte bzw. Vektoren im n- dimensionalen Raum wie beispielsweise die euklidische Distanzfunktion. Aber auch für 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änkte Wertebereich von 0 bis 1 der einzelnen Vektorelemente zu berücksichtigen ist. Dafür werden im Folgenden verschiedene Ansätze und Konzepte vorgestellt.

3.1 Distanzfunktionen und Ähnlichkeitsmaße

In diesem Abschnitt werden Distanzfunktionen und Ähnlichkeitsfunktionen 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ände zwischen Objekten zu spezifizieren, werden anhand der Eigenschaften Selbstidentität, Positivität, Symmetrie und Dreiecksungleichung kategorisiert. Die Definition erfolgt nach [Con84] und [DL91]; Sei O eine Menge von Objekten:

(3.1)

Abbildung in dieser Leseprobe nicht enthalten

Definition 1. Eine Funktion D(o, o’) heißt Semi-Pseudo-Distanzfunktion oder SemiPseudo-Metrik, wenn sie die Eigenschaften Selbstidentität 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üllt.

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

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

Die Distanzfunktionen sind meist so spezifiziert, dass das Funktionsergebnis immer größer wird, je unähnlicher die Objekte sind. In unbeschränkten Räumen führt das dazu, dass die Distanz zwischen Objekten beliebig groß werden kann. Im Gegensatz dazu haben sog. Ähnlichkeitsmaße fixe Funktionsergebnisgrenzen:

Definition 5. Eine Funktion S(o, o’) heißt Ähnlichkeitsmaß, wenn sie die Eigenschaften Selbstidentität, Symmetrie aufweist, das Supremum 1 beträgt und ein endliches Infimum b aufweist:

Selbstidentität : ∀o ∈ O : S(o, o) = 1

(3.2)

Abbildung in dieser Leseprobe nicht enthalten

Endliches Inf imum : ∀o, o′ ∈ O : b ≤ S(o, o′) ≤ 1

Für spätere Algorithmen ist die Verwendung von normierten Ähnlichkeitsfunktionen sinnvoll, welche alle ein definiertes Supremum und Infimum haben:

Definition 6. Eine Funktion SNorm(o, o′) heißt normierte Ähnlichkeitsmaß, wenn sie die Eigenschaften eines Ähnlichkeitsmaßes aufweist und das Inifimum 0 beträgt.

3.1.2 Umwandlung von Distanzfunktionen und Ähnlichkeits-

maße in normierte Ähnlichkeitsmaße

Für spätere Konzepte sind normierte Ähnlichkeitsmaße notwendig, welche im Folgenden für Vektoren aus dem n-dimensionalen Einheitskubus betrachtet werden: Als Parameter dienen Clustervektoren, welche sich in diesem begrenzten Raum befinden.

Um ein möglichst breites Spektrum von diesen normierten Ähnlichkeitsmaßen zu generieren, kann man unnormierte Ähnlichkeitsmaße und die meisten Semi-Pseudo- Distanzfunktion in solche umwandeln.

Sei s(u, v) ein Ähnlichkeitsmaß mit dem Inifimum b und Supremum t mit t > b:

Abbildung in dieser Leseprobe nicht enthalten

(3.3)

Dann ist sNorm(x, y) ein normiertes Ähnlichkeitsmaß.

Sei d(u, v) eine Semi-Pseudo-Distanzfunktion, welche für alle Vektoren aus dem n- dimensionalen Einheitskubus ein endliches Supremum t > 0 erreicht.

(3.4)

Abbildung in dieser Leseprobe nicht enthalten

Dann ist sNorm(u, v) ein normiertes Ähnlichkeitsmaß.

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

(3.5)

Abbildung in dieser Leseprobe nicht enthalten

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ätseigenschaft nach Gleichung 3.1 erfüllt.

3.2 Vergleich von Cluster-Partitionen

Der Vergleich zweier Cluster-Partitionen impliziert den Vergleich zweier Mengen bzw. Multimengen; je nach Konfiguration können diese eine Sortierung bzgl. Clustern oder Datenpunkte aufweisen, was den Vergleich erleichtert. Die dazu benötigten Ansätze werden im nächsten Abschnitt vorgestellt.

Im zweiten Abschnitt werden verschiedene Funktionen für den Vergleich zweier Clus- ter vorgestellt. Dazu gibt es zwei Darstellungsformen, die möglichst beide verwendet werden.

3.2.1 Cluster-Partitionen-Vergleich unter verschiedenen Rand- bedingungen

Für die Erstellung von Ähnlichkeitsfunktionen für zwei Cluster-Partitionen ist es entscheidend, welche Voraussetzungen man für diese beiden treffen kann. Je strikter diese sind, desto leichter sind mögliche Algorithmen zu kreieren. Zur Vereinfachung wird zunächst nur der Nicht-Fuzzy-Fall betrachtet.

Folgende Nebenbedingungen können bei zwei Clusterpartitionen auftreten, wobei die zweite Nebenbedingung die erste impliziert bzw. enthält die vierte Nebenbedingung die dritte:

1. Beide Clusterpartitionen haben die gleiche Datenpunktanzahl
2. Zu den beiden Cluster-Konfigurationen ist eine bijektive Abbildung zu den Daten- punkten 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ür die Datenpunkte als auch Cluster gibt, so entsteht eine recht einfache Ähnlichkeitsfunktion durch den Vergleich der bereits feststehenden Clusterpaare und deren enthaltenen Datenpunktpaaren: Alle Unterschiede bzw. Fehler werden verknüpft, was letztendlich das Endergebnis der Ähnlichkeitsfunktion repräsentiert.

In der Literatur [Bor05] [Mei07] ist für diese strikten Voraussetzungen ein Ansatz namens

”CountingPairs“(Paarzählung)bekannt,derimnächstenAbschnittvorgestellt wird und auch auf andere Fälle übertragbar ist. Dieser zählt alle gleiche und unterschiedliche Datenpunktpaare in vier Parametern, aus denen letztendlich eine Gesamtähnlichkeit bestimmt werden kann.

Für die Nebenbedingungen, dass es eine eineindeutige Clusterzuordnung existiert, aber keine Datenpunktzuordnung, sind zwei Fälle zu unterscheiden: Wenn beide Clusterpartitionen zumindest die gleiche Datenpunktanzahl aufweisen, kann man eine Permutation der Datenpunkte durchführen und für jede Konfiguration wieder die Gesamtfehlersumme aller Clusterpaare berechnen; die höchste Ähnlichkeit repräsentiert dann das Ergebnis der Ähnlichkeitsfunktion.

Dieser Ansatz hat eine hohe Komplexität[1] und ist bei großer Datenpunktanzahl so- mit praktisch nicht mehr durchführbar. Ein zweiter Ansatz basiert auf den Vergleich sämtlicher Datenpunktpaare zu beiden Partitionen, welcher auch bei unterschiedlicher Datenpunktanzahl funktioniert. Der Vergleich aller Datenpunktpaare wird equivalent zum

”CountingPairs“-Ansatzdurchgeführt.Zubemerkenist,dassdieseMethodemit linearen Aufwand zur Datenpunktanzahl auch für den Fuzzy-Fall sehr schnell arbeitet. Der letzte Fall betrachtet eine fehlende Clusterzuordnung: Auch hier wäre ein Ansatz wieder eine Permutation, welche die beste Konfiguration herstellt. Wenn die Anzahl der Cluster in beiden Partitionen unterschiedlich ist, scheitert dieser aber.

Für diesen Fall werden später in diesem Kapitel mehrere Ansätze vorgestellt: der eine versucht jedes Cluster aus Partition U mit jedem Cluster aus Partition V zu vergleichen und die Ergebnisse sinnvoll zu verknüpfen, wie beispielsweise das beste Clusterpaar zu bestimmen. Alle Fehlerwerte zusammen werden ausgewertet und aus Symmetriegründen

Ein zweiter Ansatz versucht alle Cluster aus Partition U so zu teilen und zu verschmelzen, dass möglichst alle Cluster aus Partition V hergestellt werden können. Gelingt dies nicht, so ergibt sich ein Fehlerwert, der die Unähnlichkeit repräsentiert. Wie im ersten Ansatz wird auch die Ähnlichkeit von Partition V zu Partition U bestimmt und symmetrisch verknüpft.

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önnen 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 ähnlich zwei unterschied- liche Datensammlungen strukturell sind. Dieses ist nützlich, wenn man viele Prototy- pen von Datensammlungen hat und eine neue klassifizieren möchte. So lassen sich bei- spielsweise über einen bestimmten Zeitraum gesammelte Messwerte mit Messwerten aus früheren Zeiträumen vergleichen und somit eventuell Rückschlüsse auf zukünftige Ent- wicklungen treffen.

3.2.2 Gewinnung von Eigenschaftskoeffizienten von Cluster- paaren

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

In der Literatur bestimmt der genannte ”Counting-Pair“-AnsatzvierParameternn1[1], n00, n10 und n01, welche später in einer Cluster-Ähnlichkeitsfunktion genutzt werden können. Dieser wird in diesem Abschnitt vorgestellt.

Für den Nicht-Fuzzy-Fall zählen diese vier Parameter die Datenpunktpaare, welche equivalent sind (n00 und n11) bzw. unterschiedlich (n01 und n10). Dabei werden jeweils die beiden möglichen Fälle von Equivalenz bzw. Differenz separat gezählt.

Je nach Voraussetungen lassen sich diese Parameter auch durch Vektoroperationen bestimmen. Existiert eine bijektive Abbildung zwischen den Datenpunkten beider Partitionen, so lassen sich diese Parameter wie folgt bestimmen. Seien ui und vj die beiden zu vergleichenden Cluster der Dimension m:

Abbildung in dieser Leseprobe nicht enthalten

(3.6)

Abbildung in dieser Leseprobe nicht enthalten

(3.7)

Abbildung in dieser Leseprobe nicht enthalten

(3.8)

Abbildung in dieser Leseprobe nicht enthalten

(3.9)

Abbildung in dieser Leseprobe nicht enthalten

Dieser vektorielle Ansatz basiert darauf, dass eine Zählung der Datenpunkte, welche beiden Vektor angehören, durch ein Skalarprodukt ermittelt werden kann. Er ist auch auf Fuzzy-Cluster übertragbar.

Fehlt eine bijektive Abbildung der Datenpunkte zu beiden Clustern, so lassen sich die Parameter wie folgt gewinnen: Seien uiT = (ui1, ..., uim) und vjT = (vj1, ..., vjn) die beiden Cluster in vektorieller Darstellung zu denen m bzw. n Datenpunkte angehören:

(3.10)

Abbildung in dieser Leseprobe nicht enthalten

(3.11) √

Abbildung in dieser Leseprobe nicht enthalten

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 Ähnlichkeitsfunktionen für Clusterpaare

Wie im vorherigen Abschnitt gezeigt, lassen sich zwei Clusterpaare durch zwei Vekto- ren bzw. durch die vier Parameter n11, n00, n10 und n01 darstellen. Für diese existieren

Abbildung in dieser Leseprobe nicht enthalten

bereits in der Literatur eine Vielzahl von Ähnlichkeitsfunktionen, wobei hier versucht wird, möglichst beide Darstellungen zu verwenden. Sie werden in folgenden Kapiteln

”natürliche“Ähnlichkeitsfunktionengenannt,dasienichtauseinemDistanzmaßheraus motiviert worden sind und somit ohne weitere Umformung eine normierte Ähnlichkeits- funktion bilden.

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

(3.[4)

Abbildung in dieser Leseprobe nicht enthalten

(3.15)

Abbildung in dieser Leseprobe nicht enthalten

(3.16)

Abbildung in dieser Leseprobe nicht enthalten

(3.17) sNPV

Abbildung in dieser Leseprobe nicht enthalten

(3.18) sCorrect = n[11]+n[00]

Abbildung in dieser Leseprobe nicht enthalten

(3.19) sIncorrect = n[10]+n[01]

(Falschklassifikationsrate)

n11+n10+n01+n00

Wallace [Wal83] hat zwei Maße verwendet, welche den Maßen

”Sensititvität“und

”Relevanz“ausdemInformationRetrievalentsprechen.Siesindbeideasymmetrisch:

(3.20)

Abbildung in dieser Leseprobe nicht enthalten

(3.21)

Abbildung in dieser Leseprobe nicht enthalten

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

(3.22)

Abbildung in dieser Leseprobe nicht enthalten

Dieses Maß entspricht dem sog. Kosinusähnlichkeitsmaß, 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 Ähnlichkeitsmaß in diesem Raum ein normiertes.

Zu bemerken ist noch, dass diese Funktion für den o-Vektor wie für viele andere hier vorgestellten Ähnlichkeitsfunktionen 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ören.

Abbildung in dieser Leseprobe nicht enthalten

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

Das sog. F1-Maß hingegen berechnet das harmonische Mittel dieser beiden Maße und ist auch als

”Dice-Ähnlichkeitsmaß“bekannt: sW (u, v) + sW (u, v) 2·u·v

(3.23)

Abbildung in dieser Leseprobe nicht enthalten

Angenommen, die Vektorelemente der zu vergleichenden Vektoren beschreiben, ob ein Punkt genau zu einem Cluster gehört oder nicht. Dann beschreibt das Dice-Ähnlich- keitsmaß genau den Anteil der Punkte, die beiden Clustern angehören. Naturgemäß kann so ein Anteil nur im Bereich zwischen 0 und 1 bewegen, womit dieses Ähnlichkeitsmaß normiert ist.

(3.24)

Abbildung in dieser Leseprobe nicht enthalten

Das Jaccard- Ähnlichkeitsmaß [Jac01] ähnelt dem Dice-Ähnlichkeitsmaß, jedoch wer- den hier die Randbereiche anders gewichtet: Sowohl sehr kleine als auch große Schnitt- mengen führen zu einer stärkeren Unähnlichkeit verglichen zum Dice-Maß. Es ist auch normiert.

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

Abbildung in dieser Leseprobe nicht enthalten

Des weiteren wurde der Rand-Index [Ran71] vorgeschlagen, welcher der Korrektklas- sifikationsrate aus dem Information Retrieval entspricht. Er gleicht dem quadrierten nor- mierten euklidischen Ähnlichkeitsmaß, welches im nächsten Abschnitt vorgestellt wird:

(3.25)

Abbildung in dieser Leseprobe nicht enthalten

Alle bisherigen vorgestellten Indexe sind normierte Ähnlichkeitsfuntionen gewesen; in [Mir96] wurde der sog. Mirkin-Index vorgeschlagen, der als Metrik fungiert. Er entspricht einer skalierten und quadrierten euklidischen Distanzfunktion:

(3.26)

Abbildung in dieser Leseprobe nicht enthalten

Des weiteren lässt sich ein Ähnlichkeitsmaß aus einem fuzzifiziertem logischen Aus- druck definieren, welches den Vektorenvergleich auf den Vergleich einzelner Vektorele- mente reduziert. Dazu seien u und v zwei Vektoren mit den Elementen u1, u2, . . . , un bzw. v1, v2, . . . , vn. Diese sind gleich, wenn die einzelnen Elemente sich gleichen:

(3.27)

Abbildung in dieser Leseprobe nicht enthalten

Durch die Definition eines elementweisen Vergleichsoperators und einer T-Norm . lässt sich Gleichung 3.27 fuzzyfizieren: Für verschieden Fuzzy-T-Normen sei auf Abschnitt 2.1.2 verwiesen; eine normierte Ähnlichkeitsfunktion für 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:

(3.28)

Abbildung in dieser Leseprobe nicht enthalten

Die Normierung ergibt sich dadurch, das die Elemente x und y entsprechend der Definition des Zugehörigkeitsgrades nur zwischen 0 und 1 liegen können; der Differenzbetrag hat den gleichen Wertebereich genauso wie eine Potenzierung desselben.

Ein weiteres normiertes Ähnlichkeitsmaß erhält man, indem man beide ClusterVektoren u und v als diskrete Fuzzy-Sets interpretiert und dafür Ähnlichkeitsmaße nach [Kun00] bzw. [DP80] verwendet:

(3.29)

Abbildung in dieser Leseprobe nicht enthalten

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

(3.30)

Abbildung in dieser Leseprobe nicht enthalten

Δ erzeugt die Differenzmenge der Vereinigungsmenge mit der Schnittmenge:

(3.31)

Abbildung in dieser Leseprobe nicht enthalten

Als letzte Möglichkeit wird aus der symmetrische Differenz beider Fuzzy-Sets das Supremum bzgl. der Zugehörigkeiten bestimmt:

(3.32)

Abbildung in dieser Leseprobe nicht enthalten

Als letzte Ähnlichkeitsfunktion in diesem Abschnitt sei das drastische Ähnlichkeitsmaß definiert, welche eine Gleichheitsrelation für Vektoren darstellt und für den Nachweis formaler Eigenschaften nützlich ist:

Abbildung in dieser Leseprobe nicht enthalten

(3.33)

Für praktische Anwendungen im Fuzzy-Bereich ist es eher unbrauchbar, da es nur die beiden Ergebnisse

”Eins“und ”Null“liefertundsomitdieFuzzy-Algorithmenzu

Algorithmen der klassischen Logik degeneriert.

3.3.1 Distanzfunktionen als normierte Ähnlichkeitsmaße

Aus Abschnitt 3.1.2 ist bekannt, dass Semi-Pseudo-Metriken in Ähnlichkeitsfunktionen umgewandelt werden können. 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ür p = 1 erhält man die Manhattan-Abstandsfunktion, für p = 2 den euklidischen Abstand und für p → ∞ den Tschebyschow-Abstand der auch Maximum-Abstand genannt wird:

Abbildung in dieser Leseprobe nicht enthalten

(3.34)

Das Supremum s der Minkowski-Abstandsfunktion im n-dimensionalen Einheitshy- perwürfel entsteht unter anderem zwischen dem o-Vektor und dem (1, 1, ..., 1)T -Vektor und beträgt s =p√n. Daraus ergibt sich folgende normierte Ähnlichkeitsfunktion:

Abbildung in dieser Leseprobe nicht enthalten

(3.35)

Abbildung in dieser Leseprobe nicht enthalten

3.3.2 Skalierung von Ähnlichkeitsmaßen

Spätere Anwendungen erzeugen und verknüpfen sehr viele ähnliche Cluster, wie beispielsweise das später in Kapitel 5 vorgestellte Bildklassifikationsszenario: Die Verknüpfung kann beispielsweise durch eine T-Conorm realisiert werden, was auch die im nächsten Kapitel vorgestellte S-Distanz nutzt.

Werden jedoch sehr ähnliche Cluster mit einer ungünstigen T-Norm verknüpft, wird das Ergebnis in Richtung volle Ähnlichkeit streben. Am Beispiel sei dies mit der T- Conorm ⊥prod und einem Zugehörigkeitsgrad a = (1 − t) nahe 1 demonstriert:

(3.36)

Abbildung in dieser Leseprobe nicht enthalten

Kapitel 3. Entwicklung von Ähnlichkeitsmaßen 24

Insbesondere bei der Verknüpfung von vielen Clusterähnlichkeitsergebnissen kann entsprechende Software in numerische Schwierigkeiten gelangen und als Endergebnis ergibt sich volle Ähnlichkeit.

Zur Vermeidung kann man bei den Ähnlichkeitsfunktionen für zwei Clustervektoren ansetzen und deren Unähnlichkeit mit einem Faktor p > 1 betonen. Sei s′(u, v) eine solche Ähnlichkeitsfunktion; die Funktion s(u, v, p) ermittelt dann gleiche oder kleinere Ähnlichkeitgrade als die Funktion s′(u,v):

(3.37)

Abbildung in dieser Leseprobe nicht enthalten

Umgekehrt ist es auch möglich für einen Faktor (0 < p < 1) die Ähnlichkeitsfunktio- nen so zu skalieren, dass deren Ergebnisse ähnlicher werden.

Trotz dieser Skalierungsmöglichkeit bleiben einige T-Normen im praktischen Sinne bei Verknüpfung vieler Parameter unbrauchbar, wie beispielsweise die T-Conorm ⊥luka: Sie summiert alle Ähnlichkeitgrade auf bis 1 erreicht ist; bei einer größeren Anzahl an Clustern müsste der Skalierungfaktor p dann sehr groß gewählt werden. Nebenwirkungen sind dann numerische Ungenauigkeiten im Null-Bereich bei der Ähnlichkeitsfunktions- berechnung für Fuzzy-Cluster-Partitionen: Diese können dann vollkommen unähnlich werden.

3.3.3 Eigenschaftsbeschränkungen von Cluster-Partitionen in dieser Arbeit

Wie in diesem Abschnitt gezeigt, existieren eine Vielzahl von Ansätzen, Ähnlichkeits- funktionen 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 voraus- gesetzt, jedoch ist die Clusterzahl beider Partitionen frei definierbar. Dabei implizieren diese Voraussetzungen auch Funktionen, die diese nicht benötigen: So wird später ein Entropie-basiertes Ähnlichkeitsmaß vorgestellt, welches die genannten bijektive Abbil- dungen ignoriert.

Des weiteren wird von Fuzzy-Clustern ausgegangen, welche natürlich den NichtFuzzy-Fall implizieren. Die Summe aller Zugehörigkeiten eines Datenpunktes zu allen Clustern muss 1 ergeben, wobei leere Cluster und Zugehörigkeiten 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- Ähnlichkeitsfunktionen nicht beachtet.

Dieser beschriebene Fall ist insbesondere interessant, wenn man unterschiedlich Clus- teralgorithmen an einer Datensammlung vergleichen möchte: Die Datenpunkte gleichen sich, während unterschiedliche Clusteralgorithmen unterschiedlich viele Cluster generie- ren können.

3.4 S-Distanz

Aus der Mengenlehre lässt sich ein relationsbasiertes Ähnlichkeitsmaß ableiten: Basierend auf der logischen Teilmengenrelation sind zwei Mengen A und B gleich, wenn folgende Eigenschaft erfüllt ist:

(3.38)

Abbildung in dieser Leseprobe nicht enthalten

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

(3.39)

Abbildung in dieser Leseprobe nicht enthalten

Die Teilmengenrelation der klassischen Logik ⊆ nach 3.39 lässt sich auch als aussagenlogischer Ausdruck definieren. Dazu seien A = {a1, . . . , am} und B = {b1, . . . , bn} zwei endliche Mengen von Objekten. A ist Teilmenge von B, wenn gilt:

Abbildung in dieser Leseprobe nicht enthalten

(3.40)

Die Fuzzy- Ähnlichkeitsfunktion 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(ai, bi), welches eine normierte Ähnlichkeitsfunktion für zwei Objekte ist.

Im Folgenden werden als Objektmengen Fuzzy-Cluster-Konfigurationen und Fuzzy- Cluster-Vektoren als Objekte verwendet; dieses Ähnlichkeitsmaß sei dann als S-Distanz[2] bezeichnet.

Seien U und V die beiden zu vergleichenden Cluster-Partitionen die jeweils n bzw. m Cluster ui bzw. vj enthalten:

Abbildung in dieser Leseprobe nicht enthalten

(3.41)

Abbildung in dieser Leseprobe nicht enthalten

Die im zweiten Schritt erfolgte Fuzzifizierung der Gleichung 3.38 sichert die Symmetrieeigenschaft des endgültigen Ähnlichkeitsmaß für Objektmengen:

(3.42)

Abbildung in dieser Leseprobe nicht enthalten

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

(3.43)

Abbildung in dieser Leseprobe nicht enthalten

3.4.1 Formale Eigenschaften

Die S-Distanz erfüllt für alle T-Normen und alle Ähnlichkeitsfunktionen die Eigenschaft der Selbstidentität: Diese gleiche Eigenschaft der Ähnlichkeitsfunktionen für Clustervektoren sorgt dafür, dass unter den n Parametern, die jede T-Conorm in der S-Distanz- Gleichung miteinander verknüpft, mindestens ein Einselement darunter ist. Sei dazu U eine Clustermenge mit n Elementen ui.

Abbildung in dieser Leseprobe nicht enthalten

(3.44)

Die T-Conorm-Verknüpfung eines Einselementes mit beliebig vielen anderen Elementen ergibt nach Gleichung 2.5 wieder das Einselement. Im nächsten Schritt werden dann die n Einselemente mit einer T-Norm verknüpft, welche wieder aufgrund der NeutraleElement-Eigenschaft nach Gleichungen 2.1 Eins ergibt. Im letzten Schritt der symmetrischen Verknüpfung sichert wieder diese T-Norm-Eigenschaft die volle Ähnlichkeit bzw. Selbstidentität der Fuzzy-Cluster-Partition

Die Symmetrieeigenschaft der S-Distanz ist gegeben, da sie auf der Symmetrieeigen- schaft der T-Norm im letzten Gleichungsschritt 3.42 zurückzuführen ist. Die S-Distanz erfüllt unter keiner Parametrisierung die Positivitätseigenschaft, da zwei Fuzzy-Cluster-Konfigurationen existieren können, 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üssen. Als Beispiel seien U und V zwei Cluster-Konfiguration mit drei bzw. vier Clustern zu nur einem einzigen Datenpunkt:

(3.45)

Abbildung in dieser Leseprobe nicht enthalten

Analog gelten dann die gleichen Überlegungen wie zur Selbstidentitätseigenschaft, um die volle Ähnlichkeit zu erzeugen und die Positivitätseigenschaft zu widerlegen.

Die Entstehung von solchen Multimengen, die einige Elemente mehrfach haben, können beispielsweise bei kugelförmigen Clustern entstehen, wenn zwei Cluster das gleiche Zentrum besitzen. Aber auch bei konstruierten Randfällen ist die Entstehung mit unterschiedlichen Clustermittelpunkten möglich, wie Abbildung 3.3 zeigt.

Abbildung 3.3: Zwei Cluster mit gleichen Zugehörigkeitsvektoren und unterschiedlichen Zentren

Abbildung in dieser Leseprobe nicht enthalten

Zu bemerken ist, dass es je nach eingesetzten Ähnlichkeitsmaß für Clustervektoren noch deutlich mehr Konfigurationen existieren können, in der trotz unterschiedlichen Cluster-Mengen die volle Ähnlichkeit erreicht wird. Als Beispiel sei das Kosinus- Ähnlichkeitsmaß genannt, welches für jeden Vektor nur einen linear abhängigen Clustervektor in der Vergleichsmenge benötigt, da nur die Richtung der Vektoren und nicht deren Länge für die Ähnlichkeitsbestimmung berücksichtigt wird.

Die Wahl der T-Norm und der zugrundeliegenden Ähnlichkeitsfunktion für Clustervektoren ist entscheidend, ob die in eine Abstandsfunktion umgewandelte S-Distanz die Dreiecksungleichung erfüllt. Als Beispiel sei die drastische Ähnlichkeitsfunktion genannt, welche unter allen T-Normen die Dreiecksungleichung erfüllt.

Aufgrund der neutralen Elementeigenschaft und Monotonieeigenschaft der T-Norm und T-Conorm und da die drastische Ähnlichkeitsfunktion nur die beiden Ergebniswerte

”Null“und ”Eins“wiedergibt,existiertnureineinzigeshypothetischenSzenario,indem die Dreiecksungleichung verletzt wird. Seien U , V und W jeweils eine Multimenge an

Clustervektoren, welche für diese S-Distanz folgende Ergebnisse liefert:

(3.46)

Abbildung in dieser Leseprobe nicht enthalten

Dieses Ergebnis kommt ausschließlich zustande, wenn folgende Bedingungen erfüllt sind:

(3.47)

Abbildung in dieser Leseprobe nicht enthalten

(3.48)

Abbildung in dieser Leseprobe nicht enthalten

(3.49)

Abbildung in dieser Leseprobe nicht enthalten

Aufgrund der Transitivität der Gleichheitrelation müsste aber nach Gleichungen 3.47 und 3.48 dann folgende Implikation erfüllt sein:

(3.50)

Abbildung in dieser Leseprobe nicht enthalten

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

Gegenbeispiele, in der bestimmte Parametrisierungen die Dreiecksungleichung ver- letzten, werden im Abschnitt 4.2 erzeugt: So erfüllt beispielsweise die T-Norm .Lukasiewicz in Kombination mit dem Jaccard- Ähnlichkeitsmaß 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ät

Der genaue Aufwand zur Berechnung einer S-Distanz hängt zwar prinzipiell auch von der verwendeten T-Norm und der Ähnlichkeitsfunktion ab, jedoch haben alle in Kapitel 2.1.1 vorgestellten T-Normen konstanten Aufwand bzw. ist der Aufwand der Ähnlichkeitsfunktionen meist linear von der Dimension der Vektoren und somit meist linear von der Punktanzahl n abhängig. Bei Verwendung geeigneter Datenstrukturen kann für einige Parametrisierungen die Komplexität jedoch auch reduziert werden.

Als Beispiel sei das drastische Distanzmaß genannt, welches zwei Vektoren auf Gleich- heit untersucht. Bei Verwendung geeigneter Hashfunktionen während der Vektorgenerie- rung kann der Vergleich in den meisten Fällen auf konstanten Aufwand reduziert werden.

Im Allgemeinen ist es jedoch schwierig, für alle Ähnlichkeitsfunktionen Optimierun- gen zu finden. Unter der Annahme, dass eine T-Norm mit konstanten bzw. eine Ähn-

Abbildung in dieser Leseprobe nicht enthalten

lichkeitsfunktion mit linearen Aufwand verwendet wird und das p und q die Anzahl der Cluster in beiden Clusterpartitionen ist, beträgt die obere Komplexitätsschranke[3] :

(3.51)

Abbildung in dieser Leseprobe nicht enthalten

Die Faktoren p und q fließen in die Komplexitätsberechnung linear ein, da jeder Cluster einer Partition mit jedem Cluster der zweiten Partition mit einer Ähnlichkeitsfunktion 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 Ähnlichkeitsfunktion für zwei Objekte dieser Menge.

Da die S-Distanz ein Ähnlichkeitsmaß für 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äter in Kapitel 5 vorgestellt: Dort wäre solch eine Multimenge eine komplette Bilder- sammlung, zu der dann eine zweite ähnliche Bildersammlung gesucht werden könnte.

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üpft 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 Ähnlichkeitsfunktion für die Blätter des Objekt-baumes benötigt.

3.5 B-Distanz

Die B-Distanz[4] ist ein Abstandsmaß für zwei Fuzzy-Cluster-Konfiguration U und V , welches für jeden Cluster aus Menge U den Cluster aus Menge V bestimmt, der die größte Ähnlichkeit bezüglich einer Fuzzy-Implikationsfunktion aufweist[5].

3.5.1 Definition

Dieses Abstandsmaß wird durch eine sog. Fuzzy-Implikation für Clustervektoren parametrisiert. Diese Funktion lässt sich durch Wahl einer klassischen Fuzzy-Implikation definieren: Seien ui und vi die Elemente der Clustervektoren u und v. Dann sei u → v das arithmetische Mittel der Implikationen:

(3.52)

Abbildung in dieser Leseprobe nicht enthalten

Diese Ähnlichkeitsfunktion ist eine normierte unter Zulassung leerer Cluster: Sie er- reicht ihre höchste Unähnlichkeit bzw. Ähnlichkeit,wenn alle Elemente aus u bzw. v mit vollen Zugehörigkeitsgraden belegt werden. Im Folgenden wird sie jedoch als Abstands- funktion mit Supremum n verwendet. Die benötigte Umwandlung erfolgt nach 3.5 und ergibt:

(3.53)

Abbildung in dieser Leseprobe nicht enthalten

Wie eingangs erwähnt, wird das Clusterpaar mit der größten Ähnlichkeit bzw. nun das mit dem kleinsten Abstand gesucht. Alle so ermittelten Abstände werden additiv verknüpft und das Ergebnis auf das Intervall [0..1] normiert:

(3.54)

Abbildung in dieser Leseprobe nicht enthalten

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

(3.55)

Abbildung in dieser Leseprobe nicht enthalten

Bei Verwendung der T-Conorm ⊥ gilt folgende Gleichung:

(3.56)

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

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

(3.57)

Abbildung in dieser Leseprobe nicht enthalten

Daraus folgt für Gleichung 3.53, dass d(u, v) höchstens die Summe aller Zugehörigkeitsgrade aus Clustervektor u erreichen kann:

(3.58)

Abbildung in dieser Leseprobe nicht enthalten

Die Summierung aller Abstände der Clustervektoren aus Menge U zu entsprechenden Vektoren aus der Menge V nach Gleichung 3.54 ergibt als Gesamtabstand höchstens die Summe aller Zugehörigkeitsgrade 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ür dieses Abstandsmaß herzustellen; dazu wird die normierte Abstandsfunktion mit der T-Conorm ⊥ verknüpft:

(3.59)

Abbildung in dieser Leseprobe nicht enthalten

In späteren Kapiteln werden vergleichende Tests der Ähnlichkeitsfunktionen vollzogen. Um die B-Distanz direkt mit der S-Distanz vergleichen zu können, wird diese in den folgenden Kapiteln als Ähnlichkeitsfunktion genutzt:

(3.60)

Abbildung in dieser Leseprobe nicht enthalten

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üllt. Neben der verwendeten S-Implikation existieren jedoch noch weitere Implikationsklassen, die dafür möglicherweise geeignet sind. Diese werden hier untersucht; für deren Definition sei auf [Low96] verwiesen.

Neben der S-Implikation existiert noch die Klasse der sog. R-Implikationen. Diese

garantiert, dass das Implikationsergebnis

”[1]“ergibtsobaldx≤ygilt:

(3.61)

Abbildung in dieser Leseprobe nicht enthalten

Bei der beispielsweisen Verwendung der T-Norm .Prod ergibt sich für die so parametrisierte R-Implikation die sog. Gaines-Implikation:

(3.62)

Abbildung in dieser Leseprobe nicht enthalten

Für 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üllen.

Die dritte Klasse ist die Klasse der sog. QL-Implikationen:

(3.63)

Abbildung in dieser Leseprobe nicht enthalten

Diese Klasse erfüllt 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 Eigenschaf- ten.

3.5.3 Ähnlichkeit zur S-Distanz

Beim Vergleich der B-Distanz zur S-Distanz fällt auf, dass beide Ähnlichkeitsmaße im Kern sehr ähnlich arbeiten: Alle Cluster aus Partition U werden mit allen Clustern der Partition V verglichen, die Ergebnisse verknüpft und im letzten Schritt eine symmetri- sche Operation vollzogen. Der Hauptunterschied liegt darin, dass die B-Distanz nur mit Distanzmaßen arbeitet und selbst auch eins ist während sich die S-Distanz auf Ähnlich- keitsmaßen basiert.

Wandelt man die B-Distanz nach Gleichung 3.60 in ein Ähnlichkeitsmaß um, so zeigt sich, dass sie tatsächlich eine Teilmenge der S-Distanz ist, wenn man im Fuzzifizierungsschritt eine T-Norm zuläß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üpfungenundumgekehrtdie ”Und“-duch ”Oder“- Verknüpfungen ersetzt werden:

(3.64)

Abbildung in dieser Leseprobe nicht enthalten

Durch die Fuzzifizierung dieser Gleichung werden die normierten Ähnlichkeitsmaße der S-Distanz in normierte Abstandsmaße (1 − s(ai, bj ) = d(ai, bj )) umgewandelt. Die Objektmengen A und B seien wieder die Clusterpartitionen U und V mit den entsprechenden Vektorelementen ui bzw. vj :

Abbildung in dieser Leseprobe nicht enthalten

(3.65)

Für die B-Distanz werden nun die T-Norm .Min und die T-Conorm ⊥Lukasiewicz verwendet. Wie im vorherigen Abschnitt gezeigt, kann bei Verwendung einer Ähnlichkeitsfunktion, welche auf die S-Implikation basiert, bei der Aufaddierung aller Parameter höchstens 1 erreicht werden: Somit kann man diese T-Conorm in diesem speziellen Fall durch eine einfache Summation ersetzen:

Abbildung in dieser Leseprobe nicht enthalten

(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)

Abbildung in dieser Leseprobe nicht enthalten

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 forma- le Eigenschaften und Komplexitätsbetrachtungen. 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üllt, ist jedoch offen.

3.6 M-Distanz

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

Abbildung in dieser Leseprobe nicht enthalten

3.6.1 Definition

Sei aus einer Fuzzy-Partition U zufällig ein Punkt und ein Cluster ui gewählt. Die Wahrscheinlichkeit, dass dieser Punkt diesem Cluster gehört, ist:

(3.68)

Abbildung in dieser Leseprobe nicht enthalten

Für eine Partition ist damit eine diskrete Zufallvariable definiert, für die eine Entropie bestimmt werden kann. Die Entropie dieser Partition ist umso größer, je gleichmäßiger die Datenpunkte über die Cluster der Partition U verteilt sind:

(3.69)

Abbildung in dieser Leseprobe nicht enthalten

Die Entropien der beiden Fuzzy-Cluster-Konfigurationen sind jetzt bereits vergleichbar; hierbei ist es sogar möglich, zwei Fuzzy-Partitionen mit unterschiedlicher Clusterund 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 un- berücksichtigt bleibt. Sei aus Partition U bzw. V ein zufälliger von n Punkten gewählt worden; die Wahrscheinlichkeit, dass dieser zu beiden Clustern ui und vj der jeweiligen Partition gehört, ist:

(3.70)

Abbildung in dieser Leseprobe nicht enthalten

P(ui vj) ist von den jeweiligen Größen der Clusterschnittmengen abhängig.

Hierfür definiert Meilǎ eine Funktion namens

”KorrelierndeInformationsfunktionfür zwei Clusterpartitionen“, welche die durchschnittliche Unsicherheitsreduktion bestimmt, dass zwei Partition voneinander abhängig sind:

(3.71)

Abbildung in dieser Leseprobe nicht enthalten

Um die gesamte Unsicherheit zu bestimmen, ist noch die Bestimmung der additiven

Verknüpfung der jeweiligen Differenzmengen notwendig:

(3.72)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.4: Entropien der einzelnen Teilmengen und deren Verknüpfungen Diese Funktion heißt nach Meilǎ

”VariationderInformationzwischenzweiCluster- partitionen“. V I(U, V ) ist für den Nicht-Fuzzy-Fall eine Metrik, da sie die Eigenschaften Positivität, Symmetrie und Dreiecksungleichung erfüllt: für die entsprechenden Nachweise sei auf [Mei[07]] verwiesen.[6]

Abbildung in dieser Leseprobe nicht enthalten

Leider ist es nicht möglich, diese Funktion auf Fuzzy-Cluster-Partitionen zu übertragen, da die Eigenschaft der Selbstidentität im Allgemeinen nicht gegeben ist. Dies liegt darin begründet, dass für zwei identische Fuzzy-Partitionen im Allgemeinen keine sichere Datenpunktzuordnung zu zwei Clustern möglich ist, da ein Punkt zu einer gewissen Wahrscheinlichkeit fast jedem Cluster angehört. So besteht immer eine Restunsicherheit, dass ein Datenpunkt beispielsweise nicht immer zum Cluster mit dem höchsten Zugehörigkeitsgrad 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ätseigenschaft führt.

Da für 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,welchedieAbsolut differenz der beiden Entropiewerte der Fuzzy-Partitionen darstellt:

(3.73)

Abbildung in dieser Leseprobe nicht enthalten

Diese Funktion ist nicht normiert: Minimal beträgt die Entropie Null, wenn einem Cluster alle Datenpunkte angehören, was in keiner Unsicherheit bzgl. der Datenpunktzuordnung resultiert. Die höchste Unsicherheit hingegen ist bei vielen gleich größen Clustern zu verzeichnen: das Supremum des Distanzmaß ist dann durch die maximale Anzahl der Cluster in beiden Partitionen gegeben und beträgt:

(3.74)

Abbildung in dieser Leseprobe nicht enthalten

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

(3.75)

Abbildung in dieser Leseprobe nicht enthalten

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

3.6.2 Formale Eigenschaften

Die M-Distanz erfüllt die Dreiecksungleichung, da sie auf eine beliebige MinkowskiMetrik im eindimensionalen Raum zurückzuführen ist: Mittels dieser Metrikklasse wird der Abstand der Entropien bestimmt.

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

Abbildung in dieser Leseprobe nicht enthalten

Somit ist diese Abstandsfunktion als Pseudo-Distanzmaß klassifiziert.

3.6.3 Komplexität

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

sich die beiden Komplexitäten der einzelnen Partitionen zur Bestimmung des Gesamtaufwandes. Sei p bzw. q die Anzahl der Cluster und nU bzw. nV die Anzahl der Datenpunkte in Partition U bzw. V und

(3.77)

Abbildung in dieser Leseprobe nicht enthalten

Die M-Distanz hat im Allgemeinen eine geringere Laufzeit als die B-Distanz bzw. S- Distanz; sie eignet sich zur Ähnlichkeitsbestimmung sehr größer Datenmengen und sehr vieler Cluster: Die Komplexität ist genauso groß, wie die Schreiboperation, die benötigt wird um die Clustervektoren zu speichern.

3.7 K-Distanz

Die K-Distanz[7] ist ein Abstandsmaß, welches auf der Idee basiert[8] , dass eine Clustermen- ge genau dann zu einer anderen Clustermenge gleich ist, wenn diese ausschließlich durch Teilung und Vereinigung von Clustern aus der Vergleichsmenge rekonstruieren lässt. Die Teilung und Vereinigung folgt im linearen Sinne, d. h. sie entsteht durch Linearkombi- nation 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ört auch zur Klasse der Abstandsmaße, die eine bijektive Abbildung der Datenpunkte voraussetzen.

3.7.1 Definition

Seien P = {C1, . . . Cp} und Q = {C′[1], ...C′q} zwei Clustermengen mit p bzw. q Clustern, welche verglichen werden sollen.

Ferner seien ai1, ...aip Koeffizienten, die eine Linearkombination repräsentieren. Diese erzeugen einen Cluster

(3.78)

Abbildung in dieser Leseprobe nicht enthalten

ähnlich ist. Ähnlichkeit in diesem Sinne sei die Minimierung der Quadratfehlersumme der elementweisen Zugehörigkeitsdifferenzen.

Abbildung in dieser Leseprobe nicht enthalten

(3.79)

Insgesamt soll versucht werden, die Quadratfehlersumme global über alle rekonstruierten Cluster zu minimieren:

(3.80)

Abbildung in dieser Leseprobe nicht enthalten

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

(3.81)

Abbildung in dieser Leseprobe nicht enthalten

(3.82)

Abbildung in dieser Leseprobe nicht enthalten

Diese beiden Nebenbedingungen implizieren eine weitere Nebenbedingung:

(3.83)

Abbildung in dieser Leseprobe nicht enthalten

Um die Symmetrieeigenschaft der Abstandsfunktion herzustellen, wird nicht nur die Ähnlichkeit von P zu Q berechnet, sondern umgekehrt auch von Q zu P. Der Abstand beträgt letztendlich dann der größere Wert der beiden Ergebnisse:

(3.84)

Abbildung in dieser Leseprobe nicht enthalten

3.7.2 Geometrische Interpretation

Aus diesen Nebenbedingungen lässt sich der Lösungsraum geometrisch charakterisieren: Die Ungleichungen 3.81 und 3.83 spannen einen Hyperwürfel der Dimension p · q auf. Des weiteren schneiden p Teilräume der Dimension q aus Gleichung 3.82 diesen Würfel. Die Schnittmenge aller Teilräume und die des Hyperwürfels bilden einen konvexen Polytop. In diesem wird nun der Punkt gesucht, der die Quadratfehlersumme nach 3.80 minimiert.

Abbildung in dieser Leseprobe nicht enthalten

Dazu kann man dieses Polytop mit Hilfe von 3.78 in den Clusterraum abbilden; die Konvexität des Polytops und die Linearität der Abbildung bewirken, dass dieser wieder einen konvexen Polytop im Clusterraum bilden. Somit ist es für eine vollständige Polytopdefinition ausreichend, die Eckpunkte abzubilden.

Die Minimierung der Quadratfehlersumme eines einzelnen Clusters bzgl. Gleichung

3.79 unter Beachtung aller Nebenbedingungen entspricht der Minimierung des Abstandes zwischen diesem Polytop und des Clusters C′j.DabeiwirdfürjedesClusterCj ein entprechender Punkt Fj auf dem Polytop bestimmt, zu dem der Abstand am geringsten ist: aufgrund der Konvexität des Polytops ist dieser eindeutig. Lässt sich der Cluster durch eine Linearkombination exakt rekonstruieren, so liegt gilt Fj = C′ j.

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

3.7.3 Erweiterung der

”NichtnegativenkleinsteQuadratfehler- summenmethode“

Wie die geometrische Interpretation aus dem vorherigen Abschnitt suggeriert, ist es ein komplexes Problem für diese Abstandsfunktion einen Algorithmus neu zu entwickeln. Aus diesem Grunde wird im nächsten Abschnitt das Problem in ein bekanntes abgebildet, zu dem bereits ein Algorithmus exisiert.

In [CLL96], Kapitel 23 wird ein Algorithmus namens (NNLS)“ beschrieben, zu deutsch

”NonnegativeLeastSquares

”NichtnegativekleinsteQuadratfehlersummenmetho- de“: Sei A eine n · m Matrix und x ein gesuchter Lösungsvektor, welcher dem Zielvektor b im Sinne der kleinsten Quadratfehlersumme möglichst erreichen soll:

(3.85)

Abbildung in dieser Leseprobe nicht enthalten

Alle Elemente des x-Vektors seien nicht negativ:

(3.86)

Abbildung in dieser Leseprobe nicht enthalten

Der NNLS-Algorithmus arbeitet iterativ und kann das globale Minimum der Ziel- funktion [3].[85] beliebig dicht annähern. Für eine genaue Beschreibung sei auf [CLL[96]] verwiesen.

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

[Wan00], [Bra01] und [BT95] genannt, welche in den Bereichen Clustering, dynamische Verkehrsleitsysteme und Bestimmung von Partikelgröß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.

”LeastSquarePro- blems“(LS), welche auch in [CLL[96]] und implementiert in Weka zu finden ist.

Dazu sei C eine Matrix, in der die Koeffizienten für die Nebenbedingungen abgelegt werden; d sei ein Vektor, in dem die Zielwerte der einzelnen Gleichungen kodiert sind. Folgende Nebenbedingung soll der Algorithmus dann erfüllen:

(3.87)

Abbildung in dieser Leseprobe nicht enthalten

Für 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)

Abbildung in dieser Leseprobe nicht enthalten

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 Op- timierungskoeffizienten mit dem Faktor ϵ gewichtet und werden somit erst sekundär optimiert.

(3.89)

Abbildung in dieser Leseprobe nicht enthalten

Der Lösungsvektor x ist nach Ablauf des Algorithmus in zwei Teile zu spalten. Der obere Teil enthält die eigentliche Lösung, die jedoch nur gültig ist, wenn der untere Teil dem d-Vektor gleicht. Beispielsweise ist die Lösung ungültig, wenn das Gleichungssystem aus 3.87 keine Lösung enthält oder ϵ schlecht gewählt 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örigkeitsgerade der Cluster aus P kodiert werden müssen, der aufwendigste Teil: die Matrix hat q · n Zeilen, p · n

Spalten und fällt somit sehr groß aus: Man beachte insbesondere den quadratischen Anstieg zur Dimension der Datenpunkte. Die Matrixelemente werden nun so gewählt, dass die Gleichungen von 3.78 abgebildet werden. mij ist dabei der Zugehörigkeitsgrad des i. Fuzzypunkts zum Cluster Pj .

(3.90)

Abbildung in dieser Leseprobe nicht enthalten

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

(3.91)

Abbildung in dieser Leseprobe nicht enthalten

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örige Matrix C mit n Zeilen und p · n Spalten wird wie folgt aufgebaut:

(3.92)

Abbildung in dieser Leseprobe nicht enthalten

Nach Ablauf des erweiterten NNLS-Algorithmus, enthält der Lösungsvektor x alle Elemente von a11, . . . apq. Mittels der Gleichungen 3.78, 3.80 und 3.84 lässt sich letztendlich der Abstand berechnen.

3.7.5 Epsilon-Wahl

Die Modifikation des NNLS-Algorithmus wirft die Frage auf, ob zu einem gegeben NNLSOptimierungs-Problem ein ϵ existiert, welches geeignet ist, die gesuchte Lösung beliebig genau zu approximieren. Dazu muss man die Quadratfehlersummenbereiche sowohl für die Nebenbedingungen als auch den Optimierungsbedingungen untersuchen:

Seien errcontraints(x) bzw. erroptimize(x) die Funktionen, der die Quadratfehlersumme für die Nebenbedingungen bzw. Optimierungsbedingungen für einen gegeben x-Vektor berechnet; errall(x) sei die Gesamtfehlerfunktion, wobei die ϵ-Gewichtung mit berück- sichtigt wird:

(3.93)

Abbildung in dieser Leseprobe nicht enthalten

(3.94)

Abbildung in dieser Leseprobe nicht enthalten

(3.95)

Abbildung in dieser Leseprobe nicht enthalten

Des weiteren sei P eine Menge, die die Vektoren enthält, die alle Nebenbedingungen nach 3.93 erfüllen. Durch diese Menge und δ sei eine beliebig kleine Umgebung Eδ um diese Lösungspunkte definiert:

(3.96)

Abbildung in dieser Leseprobe nicht enthalten

Zu zeigen: Es existiert für jedes NNLS-Problem ein δ, so dass die Minimierung der Quadratfehlersumme der Gleichung 3.93 einen Vektor in dieser δ-Umgebung ergibt.

Dazu sei xmin der Vektor, welcher die Funktion 3.93 minimiert und sich nicht in der δ-Umgebung befindet:

(3.97)

Abbildung in dieser Leseprobe nicht enthalten

Die Quadratfehlersumme von xmin kann nur dann einen Quadratfehlersummenwert der Nebenbedingungen eines Vektors aus der Menge Eδ unterschreiten, wenn xmin in einem lokalen Minimum liegt. In diesem Fall existiert aber ein δ, welches die Lösung 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)

Abbildung in dieser Leseprobe nicht enthalten

Es existiert somit ein δ, welches einen definiten positiven Wert einnimmt.

Innerhalb dieser Menge Eδ wird nun die höchste Quadratfehlersumme nach Gleichung

3.94 gesucht, um ein passendes ϵ zu bestimmen. Es sei angenommen, dass dieser höchste Quadratfehlersummenwert q endlich ist:

(3.99)

Abbildung in dieser Leseprobe nicht enthalten

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ür ϵ:

(3.100)

Abbildung in dieser Leseprobe nicht enthalten

Durch solch ein ϵ kann die Gesamtfehlersumme eines Vektors aus P nicht die eines Vektors außerhalb der δ-Umgebung überschreiten.

Zu bemerken ist, dass hier zwar die Existenz eines solchen ϵ gezeigt wurde, jedoch ist es schwierig, dieses zu berechnen: Hauptsächlich wird dies durch die Berechnung der ma- ximalen Quadratfehlersummenwert q einer potentiell unendlichen Menge P verhindert.

In der Praxis ist es jedoch in den meisten Fällen ausreichend, nur ein sehr kleines ϵ zu wählen: In der Implementation von Weka [Wek06] wird beispielsweise das Element mit dem kleinsten Absolutbetrag größer Null innerhalb der Matrix gesucht; das ϵ entspricht dann diesem Element multipliziert mit 10−[10].

3.7.6 Formale Eigenschaften

Die Selbstidentität 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üllt, da genau wie beim Entwurf der B- und S-Distanz der letzte Schritt im Berechnungsalgorithmus nach Gleichung 3.84 aus einer symmetrischen Verknüpfung besteht.

Die K-Distanz ist dazu ausgelegt, die beiden Zugehörigkeitsmatrizen bzw. deren Clustervektoren möglichst linear ähnlich aufeinander abzubilden. Dies gelingt aufgrund der Nebenbedingungen jedoch selten vollständig: Notwendige Bedingung ist, dass sowohl das größte als auch kleinste Element jeder Zugehörigkeitsdimension in beiden Clustermengen vorkommt. Sind in diesem Fall die beiden Clustermengen ungleich, so ist die Positivitätseigenschaft widerlegt.

Als entsprechendes Gegenbeispiel können wieder die beiden Mengen nach Gleichun- gen 3.45 dienen, welche auch die Positivitätseigenschaft der B-Distanz und S-Distanz widerlegen. Bei der K-Distanz gibt es jedoch auch Gegenbeispiele, in denen sich nicht alle Cluster in beiden Mengen wiederfinden lassen:

(3.101)

Abbildung in dieser Leseprobe nicht enthalten

Die Dreiecksungleichung gilt für die K-Distanz nicht: Im nächsten 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öhere Distanzen feststellt. Um diese zu normieren ist zunächst die Bestimmung des Supremums der Funktion in Abhängigkeit 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ören; Clusterpartition V hingegen habe dagegen k gleiche Cluster: Jeder Datenpunkt gehört dann mit[1]k zujedemCluster an.

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

(3.102)

Abbildung in dieser Leseprobe nicht enthalten

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)

Abbildung in dieser Leseprobe nicht enthalten

3.7.7 Komplexität

DH(U, V ) n · max(|U|,|V |)

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

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 Konfigu- ration wurden 100 Durchläufe mit jeweils unterschiedlichen mit Zufallsdaten berechnet: das arithmetische Mittel aller Durchläufe[9] repräsentiert dann die Berechnungszeit für eine Konfiguration.

Abbildung 3.5: K-Distanz: Berechnungszeit in Abhängigkeit von Clusteranzahl und Di- mension

Basierend auf diese Beobachtungen, ergibt sich wohl eine Komplexität, die zwischen quadratischen und kubischen Anstieg bzgl. der Datenpunkte liegt. Auch in Abhängigkeit der Cluster steigt die Komplexität etwas stärker an als bei der alleinigen Matrizengene- rierung:

(3.104)

Abbildung in dieser Leseprobe nicht enthalten

Als wichtigster Punkt zur Komplexität ist festzuhalten, dass diese mindestens qua- dratisch zur Datenpunktanzahl steigt, was den Algorithmus für viele praktische Applika- tionen, wie beispielsweise das im späteren Kapitel vorgestellte Bildklassifikationszenario, ungeeignet macht.

[9]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önnen während der Berechnung einzelner Distanzen deren Laufzeit erhöht haben. Erkennbar im Diagramm sind diesbezüglich einzelne Peaks im sonst recht monotonen Verlauf der Graphen.

3.7.8 Varianten

Die grundlegende Idee der K-Distanz ist, dass zwei zu vergleichende FuzzyClusterpartionen durch Teilung und anschließender Vereinigung ihrer Clusters angeglichen werden. Diese Operationen erfolgen ohne dass dieses in der Distanzfunktion selbst berücksichtigt wird, obwohl gerade die exzessive Anwendung dieser Operationen eine Aussage über die Ähnlichkeit zulassen würde.

Daher ist es überlegenswert, für die Teilung und Vereinigung eine Kostenfunktion einzuführen, 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ür eine entsprechende Kostenfunktion wäre:

(3.105)

Abbildung in dieser Leseprobe nicht enthalten

Es ist zu überlegen, diese Transformationskosten entweder mit einer bestimmten Gewichtung auf die Distanz heraufzuschlagen oder nur separat zu betrachten. Letztere Möglichkeit scheint jedoch ungeeignet, da dann der ursprüngliche Aspekt der vollständigen Rekonstruktion weitestgehend unberücksichtigt bleibt.

Eine weitere Variante ist auf die Nebenbedingungen 3.82 zu verzichten: Momentan kann der größ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äre somit in der Lage, diese Skalierungen besser zu berücksichtigen.

Werden sogar die Nebenbedingungen 3.81 ignoriert, so wären noch flexiblere Cluster- rekonstruktionen möglich: So ist das Subtrahieren eines Clustervektors dann auch eine legale Operation um die quadratische Fehlersumme zum Zielcluster zu minimieren.

Eine weitere Möglichkeit ist die K-Distanz nur als Vorstufe zu nutzen, um die zwei Vergleichspartitionen weitestgehenst anzunähern: Dabei entstehen zu den beiden ur- sprünglichen Fuzzy-Cluster-Partitionen dann jeweils eine Zielclusterpartition. Die Feh- lerberechnung erfolgt dann nicht über die Bestimmung der Quadratfehlersumme, son- dern entweder durch eine S-Distanz oder da ja bereits eine bijektive Abbildung so wohl für die Cluster als auch Datenpunkte existiert, direkt mit einer

”Counting-Pairs“-

Clustervergleichsfunktion, wie in Abschnitt [3].[3] beschrieben. Die beiden Ähnlichkeitsergebnisse der beiden Fuzzy-Cluster-Partitionspaare werden letztendlich noch symmetrisch beispielsweise mit einer T-Norm verknüpft.

Des weiteren ist offen, ob die Minimierung der Quadratfehlersumme die geeignets- te Zielfunktion ist, um die beiden Fuzzy-Clusterpartitionen anzunähern. Ebenso könnte man eine möglichst hohe Ähnlichkeit im Sinne einer der im Abschnitt 3.3 vorgestellten Funktionen plädieren. Allerdings ist die Minimierung einer anderen Zielfunktion im ma-

Abbildung in dieser Leseprobe nicht enthalten

thematischen Hinblick häufig wohl deutlich komplexer, da möglicherweise der Bereich der konvexen Optimierung verlassen wird.

Kapitel 4 Evaluationstests in künstlichen Umgebungen

Um Abstandsfunktionen zu evaluieren, müssen Umgebungen geschaffen werden, in der die Ergebnistendenzen von guten Abstandsfunktionen vorhersagen lassen. In diesem Kapitel werden dazu verschiedene Methoden vorgestellt, welche zur Qualitätsbeurteilung der Ähnlichkeitsfunktionen herangezogen werden können.

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äßigen Ring ergeben. Des weiteren wird eine Variante des Fuzzy C-Means Algorithmus einge- setzt, in der die Cluster-Zentren fest vorgegeben sind. Es werden k ≥ 2 Cluster generiert, deren Zentrum auf dem Ringrand liegt, wobei die Abstände zwischen den Zentren ma- ximiert werden.

Die Clusterzentren werden sukzessiv um den Ringmittelpunkt gedreht und der Abstand zur Urkonfiguration bestimmt.

Bei einer guten Ähnlichkeitsfunktion sollte die

360◦

Ähnlichkeit streng monoton fallen,

360◦ 360◦

bis bei 2·k dergrößteAbstanderreichtwordenist.Von 2·k bis k solltenunein 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.

4.1.1 Auswertung

Die Auswertung aller bisher untersuchten Ähnlichkeitsmaße ergibt, dass die geforderten Eigenschaften Monotonie, Maximum bei[360]◦, Minimum bei360◦ k 2·k undPeriodizität 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äherungen sind nicht zu beobachten; insgesamt ähnelt der Verlauf den mit MinkowskiMetriken und der T-Norm .Min instanziierten S-Distanzen.

Abbildung 4.1: Ringmethode: B-Distanz S-Distanz Bei der S-Distanz wurden vier verschiedene Minkowski-Metriken und vier che“ ”natürli- Ähnlichkeitsfunktionen 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-[1], Kosinus-, Dice- und [1]Als Fuzzy-Set- Ähnlichkeitsmaß wird das nach Gleichung 3.29 verwendet.

Jaccard- Ähnlichkeitsmaß unter der T-Norm .Min und .Prod validiert. Diese oder eine sehr ähnliche Konfiguration wird in nachfolgenden Experimenten auch verwendet.

Abbildung 4.2: Ringmethode: S-Distanz (.Min) mit Minkowski-Metriken

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.3: Ringmethode: S-Distanz (.Prod) mit Minkowski-Metriken

Abbildung in dieser Leseprobe nicht enthalten

Bei der Verwendung von Minkowski-Metriken als zugrundeliegende Ähnlichkeitsfunktion für S-Distanzen zeigt sich ein sehr ähnliches Verhalten für alle untersuchten Funktionen dieser Klasse.

Die resultierende Ähnlichkeit scheint nur durch einen Faktor skaliert zu sein, der vom Minkowski-Koeffizienten p abhängt. Je größer dieser ausfällt, desto schwächer wird die Ähnlichkeit zwischen zwei unterschiedlichen Fuzzy-Cluster-Konfigurationen. Dennoch zeigt die auf die Maximum-Distanzfunktion basierende S-Distanz bei beiden T-Normen keine völlige Unähnlichkeit in diesem Experiment, was darauf schließen läß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 .Prod der unähnlichste Punkt im Gegensatz zur T-Norm .Min asymptotisch angenähert wird; auch die absoluten Ähnlichkeitswerte der Funktionsminima fallen unterschiedlich aus: Bei der Nutzung der Maximum-Distanzfunktion ist dieser bei der T-Norm .Min kleiner und bei allen anderen untersuchten Minkowski-Metriken größer, verglichen mit der T- Norm .Prod.

Die Auswertung der ”natürlichen“ Ähnlichkeitsfunktionen für S-Distanzen ergibt, dass das Kosinus- und Dice- Ähnlichkeitsmaß in diesem Fall equivalente Ergebnisse liefern. Das Jaccard- Ähnlichkeitsmaß tendiert insgesamt zu unähnlicheren Werten; das Fuzzy-Set- Ähnlichekitsmaß ähnelt dem Jaccard-Ähnlichkeitsmaß sehr; beides gilt unabhängig von der verwendeten T-Norm.

Abbildung 4.4: Ringmethode: S-Distanz(.Min) mit nen ”natürlichen“ Ähnlichkeitsfunktio-

Dieses Phänomen erklärt sich folgendermaßen: Die Clusterdrehung bewirkt nur eine Neuordnung der alten Zugehörigkeitsgrade; beispielsweise verschieben sich bei Drehung um ein Grad und bei Verwendung von [360] Punkten die Zugehörigkeitsgrade um eine Dimension im Clustervektor bei angenommener Sortierung der Datenpunkte. Allgemein gilt dann für zwei Clustervektoren x und y folgende Neuordnung ihrer Elemente:

Abbildung 4.5: Ringmethode: .Prod mit

”natürlichen“Ähnlichkeitsfunktionen

(4.1)

Abbildung in dieser Leseprobe nicht enthalten

Als Resultat ergibt sich, dass alle Clustervektoren die gleichen Elemente in un- terschiedlicher Reihenfolgen tragen und somit eine equivalente Länge haben: Es gilt |x| = |y|. Das Kosinus- Ähnlichkeitsmaß entspricht in diesem Fall dem Dice- Ähnlich- keitsmaß:

(4.2)

Abbildung in dieser Leseprobe nicht enthalten

Allgemein kann man feststellen, dass das Dice- Ähnlichkeitsmaß neben dem Winkel der beiden Vergleichsvektoren auch deren Länge berücksichtigt. Sind diese gleich, so wird es zum Kosinus- Ähnlichkeitsmaß degeneriert.

Die verwendeten T-Normen .Min und .Prod zeigen unterschiedliche Verläufe: während bei der T-Norm .Min ausschließlich fast lineare Steigungen zu beobachten sind, ist dieses bei der T-Norm .Prod nur nahe der Maxima zu erkennen. Die Minima hingegen werden mit geringen Steigungsgradienten approximiert.

K-Distanz

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

Abbildung 4.6: Ringmethode: K-Distanz

Abbildung in dieser Leseprobe nicht enthalten

M-Distanz

Die Entropie der M-Distanz wird ausschließlich durch die Summe der einzelnen Clustervektoren bestimmt. Wie schon in bei der S-Distanz gezeigt, sind die Vergleichsvektoren aber nur durch eine Anordnung der Vektorelemente verschieden, was keine Änderung auf die Summe dieser Elemente zur Folge hat.

Somit zeigt die M-Distanz volle Ähnlichkeit bei jeder Clusterdrehung. Dieses Resultat bei diesem Test ist notwendige Eigenschaft für alle Ähnlichkeitsmaße, die keine bijektive Abbildung der Datenpunkte voraussetzen.

4.2 Semiverifikation der Dreiecksungleichung

Der mathematische Nachweis einiger formaler Eigenschaften der Ähnlichkeitsfunktionen bzw. Distanzfunktionen kann sich als schwierig erweisen: Hierbei ist insbesondere die Dreiecksungleichung zu nennen. Hingegen kann die Nachweis der Nichterfüllung dieser Eigenschaft durch einfache Gegenbeispielsfindung erbracht werden.

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

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 4.1: Erfüllung der Dreiecksungleichung diverser Ähnlichkeitsfunktionen für

Fuzzy-Cluster-Konfigurationen

Die Testumgebung erstellt für einen Testfall mehrere Clusterpartitionen, welche die gleiche Anzahl an Punkten aufweisen. Im nächsten Schritt wird für jede Clusterpartition eine zufällige Clusterzahl bestimmt. Anschließend erhält jeder Punkt zu jedem Cluster einen zufälligen Zugehörigkeitswert. Diese sind dabei so normalisiert, dass die Summe der Zugehörigkeitsgrade eines Punktes Eins ergibt.

Die Definition der Dimension des Vektorraumes und die geometrische Lage der Punkte ist für diesen Test nicht notwendig, da alle vorgestellten Ähnlichkeitsfunktionen ausschließlich auf die Untersuchung der Clusterzugehörigkeitsgrade beschränken und diese geometrieunabhängig künstlich erzeugt wurden.

Jede getestete Eigenschaft wurde im Folgenden pro (parametrisierte) Ähnlichkeits- funktion an 100.000 Beispiele getestet: Diese enthielten bis zu 10 Cluster und bis zu >1000 Datenpunkten. Eine Ausnahme erfolgte für 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ür viele Ähnlichkeitsfunktionen bzw. deren Parametrisierung Gegenbeispiele zu finden sind. Diese sind im Anhang A dokumentiert.

Zusammengefasst gilt die Dreiecksungleichung im Allgemeinen nicht für die B-Distanz und die H-Distanz; bei der M-Distanz und der S-Distanz mit der drastischen Ähnlichkeitsfunktion hingegen wurde in den jeweiligen Abschnitten bewiesen, dass diese Eigenschaft immer erfüllt 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üllen, sind für effiziente Algorithmen geeignet: diese können einen Minimalabstand zwischen zwei Partitionen zu bestimmen, ohne dass das Distanzmaß explizit berechnet wird.

Gegeben sei beispielsweise eine Menge von Partitionen {U1, . . . , Un}, in der die Abstände zueinander vorberechnet worden sind. Des weiteren sei eine Partition V gege- ben zu der die Partition mit dem geringsten Abstand gesucht werden soll. Es gilt folgende Ungleichung für ein Abstandsmaß d(U, V), welches die Dreiecksungleichung erfüllt:

(4.4)

Abbildung in dieser Leseprobe nicht enthalten

Bei einer Suche nach dem kleinsten Abstand muss somit nicht die Distanz d(Ui, V ) bestimmt werden, wenn d(Ui, Uj ) − d(V, Uj ) den bisher kleinsten Referenzwert übersteigt. Dies ist insbesondere nützlich, wenn die explizite Berechnung von d(Ui, V ) sehr aufwendig im Vergleich zu d(Ui, Uj ) − d(V, Uj ) ist: dies ist bei vielen hier vorgestellten Ähnlichkeitsfunktionen für Fuzzy-Cluster-Konfigurationen der Fall, wenn Ui und V sehr viele und Uj nur wenige Cluster enthalten.

In nächsten Kapitel wird genau dieses Szenario anhand einer Bildklassifikation vorgestellt. Da jedoch nur für wenige Distanzmaße bewiesen werden konnte, dass die Dreiecksungleichung erfüllt 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 Ähnlichkeitsfunktionen für 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ätze.

Abbildung in dieser Leseprobe nicht enthalten

Bei der ersten Möglichkeit 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 Zu- gehörigkeitsgrade von 0,99 und 0,01 umgesetzt. Auf die Verwendung der vollen Zu gehörigkeit

”[1]“wurdeverzichtet,dabeiZuordnungallerPunktezueinemClusterder andere leer sein würde: Dies bringt verhindert die Berechnung einiger Ähnlichkeitsfunk- tionen, die leere Cluster ausschließen.

Es sind alle möglichen Zuordnungen der Datenpunkte zu den beiden Teilmengen A und B berücksichtigt 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ößenvergleich mittels Datenpunktzuordnungen: S-Distanz (.Min) mit Minkowski-Metriken

Abbildung in dieser Leseprobe nicht enthalten

Als ein Ergebnis zeigt sich, dass die B-Distanz und die auf der Manhattan-Distanz basierende S-Distanz unter der T-Norm .Min die gleichen Ergebnisse liefern: Sie zeigen ein linearen Verlauf von der unähnlichsten Konfiguration zum Maximum bei 1.

Alle anderen Minkowski-Metriken scheinen skaliert zu sein: Je höher der exponentielle Koeffizient p, desto stärker ist Steigungsgradient nahe dem Maximum der Funktion ausgeprägt; 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 Ähnlichkeit von 0,02.

Bei Verwendung der ”natürlichen“ÄhnlichkeitsfunktionenfürS-DistanzenzeigtsichÄhnlichkeitsfunktion als überraschendes Ergebnis, dass es zwei lokale Minima in der finden lassen. Je nach verwendeter Ähnlichkeitsfunktion müssen bei 14-17 Datenpunkte einem Cluster zugeordnet werden, um die höchste Unähnlichkeit zu erreichen bzw. 83-86 Datenpunkte im gespiegelten Teil der Funktion.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung (.Min) mit 4.8: Clustergrößenvergleich mittels Datenpunktzuordnungen: S-Distanz ”natürlichen“Ähnlichlichkeitsfunktionen

Dieses Phänomen soll exemplarisch am Beispiel der Kosinus-Ähnlichkeitsfunktion erklärt werden: Die beiden Referenzcluster liegen sehr dicht an zwei Ecken im n- dimensionalen Einheitswürfel, zwischen denen ein Kosinuswinkel nach dem Ähnlichkeits- maß von nahe 90◦ festzustellen ist.

Ebenso befinden sich beide Startcluster nahe zwei Ecken im Einheitshyperwürfel; 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 Linear- kombination 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ächs- ten 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ächst an. Diese beiden Faktoren mit unterschiedlichen Funktionstendenzen werden im Gesamtergebnis berücksichtigt, was die beiden lokalen Minimal insgesamt erzeugt.

Abbildung 4.9: Clustergrößenvergleich mittels Datenpunktzuordnungen: S-Distanz (.Prod) mit Minkowski-Metriken

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.10: Clustergrößenvergleich mittels Datenpunktzuordnungen: S-Distanz (.Prod) mit Ähnlichlichkeitsfunktionen

Abbildung in dieser Leseprobe nicht enthalten

Bei der T-Norm .Prod hingegen zeigen fast alle Funktionsergebnisse monotonen Ver- lauf, wenn man vom fast leeren Cluster der Kosinusähnlichkeitsfunktion absieht. Die bei der T-Norm .Min aufgetretenen lokalen Minima werden offensichtlich durch die Ver- knüpfung des zweiten Kosinusähnlichkeitswert mittels der T-Conorm .Prod elemeniert.

Abbildung 4.11: Clustergrößenvergleich mittels Datenpunktzuordnungen: K-Distanz

Abbildung in dieser Leseprobe nicht enthalten

Die Auswertung der K-Distanz und M-Distanz zeigt, dass sowohl volle Ähnlichkeit als auch Unähnlich bei beiden Ähnlichkeitsfunktionen erreicht wird, was suggeriert, dass die Normierungsfunktion für diese Distanzen optimal gewählt worden sind.

Die M-Distanz zeigt einen fast perfekten Halbkreis als Funktionsverlauf, was eine asymptotische Annäherung beim Maxima der Funktion impliziert. Die K-Distanz hingegen nähert sich asymptotisch bei den Minima der Funktion an.

4.4 Vergleich unterschiedlich großer Cluster durch

Variation der Zugehörigkeitsgrade

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 über die Zugehörigkeitsgrade monotone Größenänderungen erreichen. Dazu sei wieder eine Datenpunktmenge mit zwei Cluster gegeben: Jeder Datenpunkt habe nun zum ersten Cluster einen Zugehörigkeitsgrad u1 > 0.5 und zum zweiten Cluster dementsprechend u2 = 1 − u1. Der erste Cluster sei nun groß, der zweite sei klein.

Im Folgenden Test wurden wieder 100 Datenpunkte erzeugt und der Zugehörigkeits- grad in 0,01-Schritten variiert. In der Referenzpartition wurden zwei Cluster erstellt, zu denen alle Datenpunkte mit einem Zugehörigkeitsgrad von jeweils 0,5 angehören.

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung 4.13: Cluster-Größenmethode: S-Distanz (.Min) mit Ähnlichkeitsfunktionen

Abbildung in dieser Leseprobe nicht enthalten

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

Für diese Minkowskimetriken lässt sich zeigen, dass diese bei zwei Vektoren x und y,

welche jeweils ausschließlich aus den gleichen Elementen x und y bestehen, Ergebnisse unabhängig vom Potenzfaktor p und der Dimension n liefern.

Abbildung in dieser Leseprobe nicht enthalten

(4.5)

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ähnlichkeitsmaß immer volle Ähnlichkeit, da der Winkel zwischen zwei Vektoren, welche jeweils ausschließlich aus gleichen Elementen bestehen, Null beträgt und somit ein Kosinuswert von Eins generiert. Hierbei sei der Nullvektor ausgenommen.

Abbildung 4.14: Clustergrößenmethode: S-Distanz (.Prod) mit Ähnlichkeitsfunktionen

Das Kosinusmaß ist somit ungeeignet, unterschiedlich große Cluster dieser Art zu erkennen; es konzentriert sich auf die Struktur und ignoriert Skalierungen. Bei allen anderen auf ”natürlichen“ Ähnlichkeitsmaßen basierende S-Distanzen sind hingegen in der Lage, Größenveränderungen wahrzunehmen.

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

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.15: Fuzzy-Größenvergleich: K-Distanz

Die Abbildung von den beiden unterschiedlich großen Clustern zur Referenzkonfigu- ration gelingt noch vollständig, so dass beide Clustervektoren exakt hergestellt werden können. Die K-Distanz berücksichtigt jedoch auch die Gegenrichtung: Da beide Cluster- vektoren der Referenzkonfiguration identisch sind, ergibt jede normierte Linearkombina- tion mit beliebigen Koeffizientenpaar genau wieder einer dieser Referenzcluster:

(4.6)

Abbildung in dieser Leseprobe nicht enthalten

Als quadratische Fehlersumme sowohl zu einem fast leeren als auch fast vollen Clus-

terelement ergibt ein Wert nahe 0,25. Insgesamt lässt sich diese Funktion mit Polynom

zweiten Grades beschreiben:

(4.7)

Abbildung in dieser Leseprobe nicht enthalten

Die M-Distanz zeigt bei dieser Versuchsanordnung einen ähnlichen Verlauf; die Funk-

tion ist durch folgenden Gleichung bestimmt:

(4.8)

Abbildung in dieser Leseprobe nicht enthalten

4.5 Hierarchische Clustermethoden

Bei hierarchischen Clustermethoden wird die Eigenschaft genutzt, dass mit zunehmender Zerteilung der Cluster diese intuitiv immer unähnlicher zur ursprünglichen Clusterkonfiguration werden.

Interessant ist außerdem der Abstand zwischen zwei Ebenen, wenn der Teilungsalgorithmus so ausgelegt ist, dass er jeden Cluster ähnlich zerteilt, wie in der vorherigen Ebene. Dieser Abstand ist dann charakteristisch für eine Abstandsfunktion.

4.5.1 Split-Methode

Ausgangspunkt ist ein einziger Cluster c, dem alle Datenpunkte voll angehören. Dieser Cluster wird in zwei Cluster u und v folgendermaßen geteilt: Für jeden Datenpunkt ni wird ein Zufallswert zi zwischen 0..1 generiert, der die Zugehörigkeitsgerade neu verteilt:

(4.9)

Abbildung in dieser Leseprobe nicht enthalten

Es entsteht eine neue Clusterkonfiguration bestehend aus den Clustern u und v. Diese werden im nächsten Schritt nach der gleichen Methode geteilt wieder geteilt, so dass vier neue Cluster entstehen. Es erfolgen weitere Splits, welche ein hierarchisches Clustergebilde kreieren lässt. Der Abstand zwischen allen Nachbarebenen und zur ursprünglichen Ein-Cluster-Konfiguration wird im Folgenden untersucht.

Erwartet wird ein Ergebnis, dass zwei benachbarte Cluster-Konfigurations-Ebenen eine konstante Ähnlichkeit bescheinigt. Hingegen sollten alle Ebenen zur Wurzelkonfigu- ration mit zunehmender Cluster- bzw. Ebenenzahl monoton an Ähnlichkeit verlieren.

Für diesen Versuch wurden insgesamt sieben Ebenen kreiert, so dass in der letzten Ebene 64 Cluster entstanden sind; es sind für alle Clusterkonfiguration 10000 Daten- punkte verwendet worden um Variationsbreite zwischen unterschiedlichen Durchläufen 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äufe gezeigt, dass sich diese nur unwesentlich voneinander unterscheiden. Jedoch konnte kein Vergleich zwischen den letzten beiden Ebenen für dieses Abstandsmaß er- mittelt werden, da der NNLS-Algorithmus nicht genügend Speicher für die Matrizen alloziieren konnte[2] .

4.5.2 Auswertung

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

[2]Die Java Virtual Machine beendete sich für diese Konfiguration mit einer ”Heapoverflowexception“

Abbildung in dieser Leseprobe nicht enthalten

dieses Maß eine sinkende Ähnlichkeit mit steigender Clusterzahl zur Wurzelkonfiguration: pro Ebene halbierte sich die Ähnlichkeit.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 4.2: Hierachische Splits: Ähnlichkeit / Distanz zwischen den Nachbarebenen

Im Gegensatz dazu stellte die K-Distanz zwischen zwei Nachbarebenen mit steigender Clusterzahl einer geringere Ähnlichkeit 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ängig ist, mehr als kompensiert. Im zweiten Test sinkt die Unähnlichkeit 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 Ver- wendung der T-Norm .Prod stieg die Ähnlichkeit zwischen Nachbarebenen mit steigen- der Clusterzahl kontinuierlich an und erreichte in fast allen Fällen nahezu volle Ähn- lichkeit. Bei der .Min-Norm kann man wieder zwischen den Minkowski-Metriken und den ”natürlichen“Ähnlichkeitsfunktionendifferenzieren:BeiersterensteigtdieÄhnlich- keit kontinuierlich an, was durch die monotone Verkleinerung der Clustervektorenlänge und deren Distanzen untereinander begründet ist. Das Fuzzy-Set-, Kosinus-, Dice- und Jaccard- Ähnlichkeitsmaß 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ährend bei Verwendung der .Min-Norm die Ähnlichkeit mit steigender Clusteranzahl noch monoton sinkt, ist es

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 4.3: Hierachische Splits: Ähnlichkeit / Distanz zwischen Wurzelebene und tieferen Ebenen

bei der .Prod-Norm abhängig, welche zugrundeliegende Ähnlichkeitsfunktion verwendet wurde.

Die M-Distanz bescheinigt eine maximale Unähnlichkeit von allen Ebenen zur Wur- zelebene: Dies ist damit zu begründen, dass in der Wurzelebene maximale Ordnung herrscht und die Entropie

”Null“beträgt.HingegenistfürjedeVergleichsebenedieEntro- pie für die jeweilige Clusterzahl maximiert, da die Datenpunkte möglichst gleichmäßig und zufällig über 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 Ähnlichkeit mit zuneh- mender Ebenenanzahl fest. Dies ist damit zu begründen, dass die Entropien der jeweili- gen Partitionen beide ansteigen und das die Referenzebene (die Wurzelebene) sich immer weiter entfernt. Relativ gesehen, nähern sich dann die Entropien der beiden Partitionen auf hohem Niveau an.

Kapitel 5 Fuzzy-Bildklassifikation

5.1 Klassifikation mittels Ähnlichkeitsmaßen

Die bisher vorgestellten Evaluationsmethoden sind nur geeignet, bestimmte erwartete Ei- genschaften für 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ür 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 Ähnlichkeit zu diesem aufweist: Das Bild wird der Klasse des Vergleichsbildes zugeordnet[1] . Dafür können im Prinzip alle Ähnlichkeitsfunktionen für Fuzzy-Cluster- Konfigurationen aus Kapitel 3 getestet werden.

Als Ergebnis kann man für eine Ähnlichkeitsfunktion, 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 de- nen 48 bis 115 Bilder zugeordnet worden sind. Es handelt sich teilweise um Land- schaftsbilder vom Yellowstone-Nationalpark und Green Lake Park (Seattle), von Pflan- zen (Kirschbäume, laublose Bäume und Frühlingsblumen) und teilweise um bestimmte

Alle Bilder wurden von der

”EfficientContent-basedRetrievalGroup“derUniversität von Washington veröffentlicht[2] .

Wie die Thematiken schon suggerieren, gibt es viele ähnliche Bilder in den unter- schiedlichen Sammlungen: So sind auf die im Herbst entstandenen Campusbilder auch laublose Bäume zu finden und umgekehrt befinden sich bei den laublosen Bäumen auf fast allen Fotos im Hintergrund diverse Gebäude. Rosa blühende Pflanzen gibt es in ho- hem Maße auf den Kirschbaum- und Frühlingsblumenbildern. Bilder von Seen befinden sich nicht nur in den beiden Landschaftsfotosammlungen, sondern auch auf den Cam- pusfotos und auf den Bildern aus dem Iran. Selbst ein Mensch bräuchte wohl spezielle Ortskenntnisse bzw. Grundkenntnisse in der Botanik, um alle Fotos korrekt zu klassifi- zieren.

Ziel ist es somit nicht, eine möglichst 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ür 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äume, wie beispielsweise der HSV-, CMYK- oder auch YUVFarbraum; für 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 Pk die Menge der Bildpunkte, die einer n · m großen Kachel q zugeordnet sind.

(5.1)

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

(5.2)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

(5.3) ∅a2′(q) = green(pijq);

Abbildung in dieser Leseprobe nicht enthalten

(5.4) ∅a3′(q) = blue(pijq);

Abbildung in dieser Leseprobe nicht enthalten

(5.5) Δb1′(q) = (red(pijq) − red(p(i+k)(j+l)q ))[2]

Abbildung in dieser Leseprobe nicht enthalten

(5.6)

Abbildung in dieser Leseprobe nicht enthalten

(5.7)

Abbildung in dieser Leseprobe nicht enthalten

Die ersten drei Funktionen ermitteln den durchschnittlichen Farbwert einer Kachel, jeweils für den entsprechenden Farbanteil. Die letzten drei Funktionen hingegen gewich- ten die Kanten innerhalb einer Kachel: Durch die quadratische Funktion werden kon- trastreiche Kanten deutlich stärker gewichtet als beispielweise viele kleine Kanten die in Farbverläufen 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ür eine Kachel q spezifiziert. Die Normalisierung erfolgt nach:

(5.8)

Abbildung in dieser Leseprobe nicht enthalten

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ür 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ört 6 Datenpunkten mit einem bestimmten Zugehörigkeitsgrad an, welche

Abbildung in dieser Leseprobe nicht enthalten

die einzelnen Attribute einer Kachel darstellen. Eine weitere Transformation der extra- hierten Bildvektoren aus Abschnitt 5.3 für 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ätzlicher Aufwand betrieben werden muss. Interessant ist diese Methode auch bei sich schnell ändernden Daten, da es nur linearen Aufwand pro Cluster bedarf, die Zugehörigkeitsgrade an einen neuen Datensatz anzupassen. Dieses ist beispielsweise beim kontinuierlichen Clustern von Datenströmen nützlich [JB06]. Auch ist die Anzahl der entstehenden Cluster bekannt, so dass bei vielen Algorithmen die Laufzeit der im zweiten Schritt angewendeten Ähnlichkeitsfunktionen im Vorfeld bekannt ist, was in einer Echtzeitfähigkeit dieses Algorithmus mündet.

Auch ist es im Prinzip hier möglich, eine bijektive Abbildung zu den Clustern zu schaffen, so dass die sehr einfache Variante der

”CountingPair“-Ähnlichkeitsmaßean- wendbar ist. Auf die Auswertung dieser Abbildung wurde jedoch verzichtet, um die Ergebnisse mit anderen Clustermethoden vergleichbar zu halten.

Insgesamt läßt sich diese Clustermethode jedoch aufgrund der begrenzten Kachelanzahl kritisieren, da jede zusätzliche Kachel pro Partition einen weiteren Cluster entstehen läßt, was bei Verwendung der B-Distanz oder S-Distanz einen quadratischem Komplexitätsanstieg verursacht. Deshalb wurde ein Bild in nur [4] · [4] Kacheln unterteilt, so dass nur [16] Cluster pro Bild entstanden sind.

Des weiteren läßt sich die statische Positionierung der Cluster kritisieren: Realitätsnäher wäre die Anwendung eines klassischen Clusteralgorithmus. Auch dass es in den meisten Fällen mehr Cluster als Datenpunkte gibt, wirkt unnatürlich verglichen mit Clusterkonfigurationen aus den meisten anderen Applikationen.

Der letzte Kritikpunkt würde theoretisch durch die eine Matrixdrehung beseitigt wer- den, in welcher dann die Kacheln zu Datenpunkten werden bzw. umgekehrt die RGB- Attribute der einzelnen Kacheln zu Clustervektoren würden. Darauf wurde angesichts des Anwendungsfalles verzichtet, da die bijektive Abbildung der Kacheln bei einer Bilddre- hung oder Spiegelung eine Neuzuordnung verhindert und somit keine volle Ähnlichkeit mehr im Allgemeinen garantiert ist. Noch schwerer wirkt die beliebige Zuordnung der Farbzugehörigkeiten, so dass beispielsweise der Clustervektor für den Rotanteil mit dem Clustervektor des Blauanteiles verglichen werden könnte, was die Ähnlichkeitsfunktionen relativ farbenblind machen würde.

Aus diesem Grunde werden die Datenpunkte zusätzlich nach einer zweiten und wohl bekanntesten Methode geclustert: Der in Abschnitt [2].[2].[5] vorgestellte Fuzzy C-Means Algorithmus mit automatischer Clusteranzahladaption basierend auf dem Xie-Beni-Index wird auf die extrahierten Bilddaten angewendet.

Nachteile dieser Methode sind eine höhere Komplexität, Nichtdeterminiertheit des Algorithmus und ein weiterer Informationsverlust, welcher durch die nicht eindeutig um- kehrbare Abbildung der Bildvektordaten auf die Clusterzugehörigkeitswerte begründet ist. So enstehen beispielsweise bei einem schwarz-weißes Schachbrettmuster zwei gleiche

Cluster; die erste Methode hingegen ist in der Lage, den weißen Kacheln entsprechend ihrem RGB-Anteil am Gesamtbild höhere Zugehörigkeitsgrade zuzuordnen. Dennoch sind diese genannten Kritikpunkte zu beiden Verfahren unerheblich, wenn man nur faire Ausgangsbedingungen für Vergleichszwecke der Ähnlichkeitsfunktion 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äßig der euklidische Abstand verwendet wird: Dadurch könnte die mit dem euklidischen Abstand instanziierte S-Distanz einen Vorteil haben. Ob dies der Fall ist, wird in zwei Testreihen geklärt: In der ersten wird beim Clustern ausschließlich der euklidische Abstand genutzt; in der zweiten Testreihe wird das verwendete Ähnlichkeitsmaß in ein Distanzmaß umgewandelt und anschließend zum Clustern genutzt.

Auch die B-Distanz erhält so adaptierte Cluster: Dieses Abstandsmaß wird auf den Vergleich zweier Vektoren mittels der Lukasiewicz-Implikation und der symmetrischen Verknüpfung mittel der T-Conorm ⊥Min reduziert. Da alle Datenpunkte sich im n- dimensionalen Einheitskubus befinden, liegt der gleiche Wertebereich vor, wie bei FuzzyCluster-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üben.

5.5 Verwendete Ähnlichkeitsmaße

Angewendet auf dieses Evaluationsmethode wurden die B-Distanz und die S-Distanz mit diversen T-Normen und Ähnlichkeitsmaßen für 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ätsmultiplikatoren, welche den Algorithmus insgesamt nur für sehr wenig Kacheln pro Bild praktikabel machen würde.

Die M-Distanz wurde nur bei den fest definierten Clustern getestet, da ein Ähnlichkeitsmaß für zwei Vektoren aus diesem Abstandsmaß nicht bestimmbar ist und somit das letzte Experiment mit diesem Maß nicht möglich ist.

5.6 Klassifikationsraten

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

Ansonsten würde eine Bildersammlung, die deutlich mehr Bilder enthält als die Ver- gleichssammlung, selbst durch eine Zufallsabstandsfunktion viel mehr Bilder sich zu- ordnen, da es mehr Vergleichswerte gibt und somit die Chance steigt, ein passendes Vergleichbild zu finden. Durch die unterschiedliche Anzahl von Bildern ergibt sich eine ”natürliche“Klassifi- kationsrate, die durch solch eine Zufallsabstandsfunktion hervorgerufen würde. Seien A und B die beiden Bildmengen und sei sRandom durch folgende Zufallsähnlichkeitsfunktion definiert:

Abbildung in dieser Leseprobe nicht enthalten

(5.9)

⊕ ist ein symmetrischer Operator und Random(a) eine Funktion, die eine Pseudo- zufallszahl basierend auf ihr Argument liefert. Dann erreicht ein

”[1]-Nearest-Neighbour“- Klassifikator mit dieser Zufallsähnlichkeitsfunktion ein durchschnittliches Klassifikationsergebnis von:

(5.10)

Abbildung in dieser Leseprobe nicht enthalten

Jede ernsthafte Ähnlichkeitsfunktion sollte diesen Wert verbessern können. Um bei verschieden großen Bildersammlungen die realen Klassifikationsraten bei verschiedenen Ähnlichkeitsmaßen zu ermitteln, ist die Einführung einer normalisierten Klassifikationsrate notwendig, die den oben genannten Effekt kompensiert. Sei dazu c die Anzahl der korrekt klassifizierten Bilder:

(5.11)

Abbildung in dieser Leseprobe nicht enthalten

Im folgenden Kapitel 6 wird ausschließlich die normalisierte Klassifikationsrate be- trachtet.

5.7 Auswertung

Die Bildklassifikation in diesem Kapitel ist mit Abstand das rechenaufwendigste Experi- ment dieser Diplomarbeit: Insgesamt wurden pro 16 Ähnlichkeitsfunktion und 16 Cluster- methoden jeweils getestet. Pro Parametrisierung wurden 585.636 Bilderpaare verglichen, was insgesamt ca. 150 Mio. Anwendungen von Ähnlichkeitsfunktionen für 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 zur Semi-Pseudo-Distanzfunktion umgewandelte Jaccard- Ähnlichkeitsmaß durchschnitt- lich sehr viele Cluster pro Bild während die Manhattandistanzfunktion deutlich weniger generierte.

5.7.1 Fest definierte Cluster

Auch wenn in diesem Experiment im Gegensatz bei der später 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 FuzzyC Means Cluster-Algorithmus der Fall ist: Bei den fest definierten Clustern zählt die absolute und nicht relative Lage der Datenpunkte im Raum.

Abstandsklasse T-Norm Distanz- Exp. Klassifi- Standard- maß Koeff. kationsrate abweichung

Abbildung in dieser Leseprobe nicht enthalten

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- Ähnlichkeitsmaß mit der T-Norm .Prod und exponentiellen Faktor p = 10 hervorzuheben. Aber auch alle anderen Maße erreichten mindestens 69 %.

Eine Ausnahme bildet die M-Distanz: Da bei diesem Ähnlichkeitsmaß die bijektive Abbildung ungenutzt bleibt, kann es nicht die RGB-Attribute zwischen zwei Bildern untereinander differenzieren: Es ist quasi ”farbenblind“undbetrachtetnurdieVertei- lung der summierten Farbintensitäten und Kanten über 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 ähnlichen Bildsammlungen be- gründet: So konnten beispielsweise Footballbilder sehr gut von laublosen Bäumen un- terschieden werden, während Universitätsgebäude von Gebäuden in Barcelona weniger differenzierbar waren.

Die Laufzeit war insgesamt relativ hoch, da pro Bildpaar [512] Clustervergleiche stattfanden, was deutlich über 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ür 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- Ähnlichkeitsmaß dicht gefolgt von der B-Distanz und dem ähnlichen S-Distanzmaß mit Manhattan-Abstandsfunktion die besten Resultate liefern.

Abstandsklasse T-Norm Distanz- Exp. Klassifi- Standard- maß Koeff. kationsrate abweichung

Abbildung in dieser Leseprobe nicht enthalten

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

Auffällig ist die geringe Standardabweichung und eine Klassifikationsrate von nur

knapp über 50 % bei der Maximum-Ähnlichkeitsfunktion, was darauf hindeutet, dass diese Abstandsmaß mit dieser Cluster-Struktur fast nur zufällige Ergebnisse liefert. Die- ses ist der großen Clustervektorlänge von 256 Elementen begründet, in der nur ein Ele- mentpaar entscheidend für die Ähnlichkeit ist, was insgesamt einen sehr hohen Informa- tionsverlust bedeutet.

Des weiteren stellt man fest, dass die T-Norm .Prod bei allen Parametrisierungen schlechtere Klassifikationsraten als die .Min mit Ausnahme der sowieso schon extrem schlecht funktionierenden Maximum- Ähnlichkeitsfunktion.

5.7.3 Fuzzy C-Means mit adaptiertem Abstandmaß

Im letzten Experiment werden alle Ähnlichkeitsfunktionen für zwei Vektoren sowohl zum Clustern als auch beim anschließenden Fuzzy-Cluster-Vergleich genutzt. Hier zeigt sich, inwieweit einzelne Clusteralgorithmen und Ähnlichkeitsfunktionen für eine gute Klassifikationsrate entscheidend sind und ob es sinnvoll ist, dass beide Algorithmentypen auf die gleichen Vektorähnlichkeitsfunktionen basieren.

Abstandsklasse T-Norm Distanz- Exp. Klassifi- Standard- maß Koeff. kationsrate abweichung

Abbildung in dieser Leseprobe nicht enthalten

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

Im Folgenden werden deshalb die Klassifikationsraten für die Ähnlichlichkeitsfunktio- nen 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- Ähnlichkeitsfunktion, welche offensichtlich kugelförmige Cluster bevorzugen.

Abschließend stellt sich die Frage, welche Vektorähnlichkeitsfunktionen für das Clustern mittels Fuzzy C-Means und für die Ähnlichkeitsfunktion für Fuzzy-Cluster- Konfigurationen für diese Anwendung am besten geeignet sind.

Als überraschendes Ergebnis für den Clusterprozess ergibt sich, dass das KosinusÄhnlichkeitsmaß sowohl die besten als auch schlechtesten Werte liefert, je nach verwendetet exponentiellen Skalierungsfaktor p und T-Norm. Bei kleinem p wurden bei der Clusteranalyse deutlich mehr Cluster erzeugt, was in diesem Fall wohl negativ auf die Klassifikationsrate schlägt.

Ähnlichkeitsmaß Exp. Klassifikationsrate Klassifikationsrate Koeff. (Cluster) ( Ähnlichkeitsmaß)

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 5.4: Durchschnittliche Klassifikationsraten nach Cluster- und Ähnlichkeitsfunk- tion

Auf der anderen Seite ist das Kosinus- Ähnlichkeitsmaß noch am ehesten in der Lage, im Clusterprozess Farben im RGB-Raum zu vergleichen: So sind gleiche Farben un- terschiedlicher Intensität im RGB-Raum danach voll ähnlich. Die Minkowski-Metriken hingegen bewerten auch die Intensität, was in diesem Anwendungsfall offensichtlich zu schlechteren Ergebnissen führt: Eine ÄnderungdesFarbraummodellskönnte hierbei evtl. Verbesserungen bringen.

Abbildung 5.1: Voll ähnliche Farbverläufe nach Kosinus-Ähnlichkeitsmaß im RGBFarbraum Umgekehrt scheinen die ”klassischen“ Ähnlichkeitsmaße bei den Ähnlichkeitsfunk-

tionen für Fuzzy-Cluster-Konfigurationen den Minkowski-Metriken mit Ausnahme der Maximum-Distanz ein klein wenig unterlegen zu sein. Insgesamt zeigt die Kombinati- on Kosinus-Clusterung und Manhattan- Ähnlichkeitsfunktion mit jeweils exponentiellen Faktor von 10 und T-Norm .Prod 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 Clusteralgo- rithmus und Ähnlichkeitsfunktion wichtig für die jeweilige Applikation ist. Leider ist dies aufgrund der vielen möglichen 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 Ähnlichkeitsfunktionen können wahrscheinlich noch bes- sere Ergebnisse liefern.

Kapitel 6 Bewertung

6.1 Bewertung der Ergebnisse

In dieser Diplomarbeit wurden insgesamt vier Distanzfunktionen bzw. Ähnlichkeitsfunktionen für 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 Ähnlichkeitsfunktionen sind sehr effizient berechenbar, da die Komplexität pro Partition höchstens linear zur Clusterzahl bzw. Punktanzahl steigt. Besonders erwähnenswert 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ür 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 Ähnlichkeitsfunktionen wurden mehreren synthetischen Tests unterzogen: Clusterdrehungen um einen Mittelpunkt zeigen, wie diese Funktionen bei einer Verschiebung bzw. Permutation der Zugehörigkeitswerte reagieren. Desweiteren wurden zwei verschiedene Vergleichstests zu unterschiedlich großen Clustern durchgeführt: Im ersten Test konnten alle Funktionen die verschiedenen Größ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ähnlicher zum Ursprungscluster wurden. Auch ein Ver- gleich zwischen den Nachbarebenen wurde gezogen, wobei einige Funktionen nicht nur stetige Verläufe bzgl. der Ähnlichkeit und steigendem Teilungsgrad gezeigt haben. Von allen durchgeführten Experiment lieferte dieses insgesamt die meisten nicht erwarteten Ergebnisse.

Abschließend wurden die zwei Funktionen in einer praktische Anwendung auf rich- tigen Daten in Form einer Bildersammlung getestet: Aus einem Bild wurde eine be- stimmte Anzahl von Eigenschaftsvektoren extrahiert und diese anschließend nach meh- reren Methoden geclustert. Danach wurde das Bild mit der höchsten Ähnlichkeit gesucht und somit die Klasse dieses Bildes bestimmt. Es zeigt sich, dass optimales Clustern im Vorfeld eine gute Entscheidungsgrundlage für diese Funktionen herstellt und das vie- le untersuchte Funktionen grundsätzlich geeignet scheinen; eine Ausnahme bildete die Maximumähnlichkeitsfunktion unter Anwendung der Fuzzy-C Means Clusterung.

Insgesamt wurde mit diesem Klassifikationstest erfolgreich der Schritt von der Theo- rie in die Praxis vollzogen; die hier entwickelten Ähnlichkeitsfunktionen 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 Ähnlichkeitsfunktionen gut mit den bereits entwickelten Fuzzy-Cluster-Grundlagen har- monieren.

6.2 Ausblick

Drei der hier behandelten Ähnlichkeitsfunktionen für Fuzzy-Clusterstrukturen setzen zwingend voraus, dass zu beiden vergleichenden Partitionen eine eineindeutige Abbildung der Datenpunkte vorliegt. Eine Erweiterung auf beliebig viele Datenpunkte würde deren Anwendungsbreite deutlich erhöhen, da zwei unterschiedlich große Datensammlungen bzw. Datensammlungen bei denen nicht die gleiche Sortierung hergestellt werden kann, miteinander vergleichbar wären. Ein geeigneter Test ist für diese Funktionen ist hier bereits vorgestellt: Bei der Drehung der Cluster um einen definiten Mittelpunkt beim Ringtest müssen alle verglichenen Partitionen bei solch einer Funktion volle Ähnlichkeit ergeben, wie es bei der M-Distanz der Fall ist.

Die explizite Konstruktion solch einer Funktionen wurde in dieser Diplomarbeit durch das entropiebasierte Ähnlichkeitsmaß M-Distanz realisiert; im Abschnitt 3.2 ist zusätzlich gezeigt worden, wie Ähnlichkeitsfunktionen basierend auf ”CountingPairs“aufgebaut sein könnten, damit sie diese Nebenbedingung nicht mehr voraussetzen müssen und dass diese keine höhere Laufzeit haben müssen im Vergleich zu Partitionen zu denen eine bijektiven Abbildung gegeben ist. Interessant wären dann beispielsweise vergleichende Tests zu Algorithmen, die beide Partitionsarten bewältigen können.

Bisher fehlt auch die Konstruktion einer echten nichttrivialen Distanzfunktion für Fuzzy-Cluster-Partitionen, welche alle entsprechenden Eigenschaften, insbesondere die der Positivität, erfüllt. Grundproblem ist bei vielen Funktionen, dass sie Mengen, jedoch nicht Multimengen von Clustern betrachten: Cluster können in theoretischen Randfällen mehrfach vorkommen. Ob diese dann aber bessere Resultate bei praktischen Anwendun- gen, wie beispielsweise der vorgestellten Bildklassifikation erzielen, ist jedoch offen.

Auch ist es möglich, auf Grundlage der bereits vorgestellten Funktionen diese zu erweitern oder noch variantenreicher zu parametrisieren. So ist es überlegenswert, die K-Distanz mit einer Kostenfunktion zu erweitern, einige Nebenbedingungen nicht zu berücksichtigen, die Distanz über eine andere Fehlerfunktion zu bestimmen oder sogar die Zielfunktion der quadratischen Minimierung zu ändern.

Bei der B-Distanz ist die Untersuchung weiterer Fuzzy-Implikationen möglich: da man diese aus einer T-Norm gewinnen kann, gibt es unendlich viele Parametrisierungen für dieses Maß. Bei der S-Distanz wurden bereits diverse Parameter evaluiert: Dennoch gibt es wie bei der B-Distanz noch sehr viele Möglichkeiten dieses instanziieren und deren Varianten untersuchen.

Die M-Distanz sollte ursprünglich durch Fuzzifizierung der Ähnlichkeitsmaß zu ”VariationofInforma- tion“-Funktion definiert werden, welche idealerweise die Metrik-Eigenschaft der Nicht- Fuzzy-Variante behalten sollte. Dieses ist jedoch durch einfache Erweiterung der Wahr- scheinlichkeitsfunktionen nicht möglich; 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ären, wie beispielsweise zwei Mengen von Fuzzy-Cluster-Partitionen.

Des weiteren ist ein interessanter Aspekt für praktische Anwendungen die richtige Wahl der Ähnlichkeitsfunktion und deren Parameter. Diesen mit einem passenden Clusteralgorithmus zu bestimmen, ist wohl der schwierigste Teil für eine Implementation in praktischen Anwendungen.

Ein interessanter Ansatz für dieses Problem ist aus dem Fuzzy-Clustering zu ent- nehmen: Beispielsweise erzeugt der sog. Gustafson-Kessel-Algorithmus [GK[79]] für jedes Cluster dynamisch eine Parametrisierung einer verallgemeinerten Mahalanobis-Metrik, um die Clusterform an die Punktegeometrie optimal zu adaptieren. Diese könnte man bei der Vergleichsfunktion für Fuzzy-Cluster-Partitionen berücksichtigen bzw. Vergleichs- funktion definieren, welche diese Form der Cluster mit berücksichtigen. Da der Schwer- punkt dieser Diplomarbeit bei den Ähnlichkeitsfunktionen liegt, ist dieser integrierte Ansatz nicht untersucht worden.

Ein weitere Möglichkeit ist die Ähnlichkeitsfunktion für zwei Fuzzy-Cluster- Konfigurationen nicht ausschließlich über die Zugehörigkeitsgrade zu definieren, sondern auch die geometrische Lage der Datenpunkte, die Clusterformen und -zentren mitzuberücksichtigen: So wurde in dieser Diplomarbeit zwar die Qualität einer Clusterung über den Xie-Beni-Index beurteilt, welche die beiden Faktoren

”Kompaktheit“und ”Se- paration“ bewertet; diese könnten jedoch auch für den Vergleich zweier Fuzzy-Cluster- Partitionen herangezogen werden. Es wäre beispielsweise vorstellbar, den Vergleich der beiden Clusterpartionen wieder auf den Vergleich zweier Cluster zu reduzieren: die

”Se- paration“ wird aus der Entfernung zum nächsten Clusterzentrum bestimmt, die Kompaktheit genau wie beim Xie-Beni-Index. Ein Ähnlichkeitsergebnis wäre beispielsweise wieder eine normalisierte Absolutdifferenz dieser beiden Faktoren, welche noch miteinander zu einer Gesamtähnlichkeit verknüpft werden müssen.

Allerdings ist die Definition einer nichttrivialen Metrik für die letzteren Vorschlag noch deutlich schwieriger, da neben den Zugehörigkeitsgraden auch noch andere Attri- bute wie Clusterzentren und Datenpunkte für die entsprechenden Metrik-Eigenschaften Selbstidentität, Positivität, Symmetrie und Dreiecksungleichung mit berücksichtigt wer- den müssen.

Literaturverzeichnis

[Bor05] Christian Borgelt. Prototype-based Classification and Clustering. Fakultät für

Informatik, Otto-von-Guericke-Universität 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 clustering for mining in a data warehousing environment. Proceedings of 24th VLDB Conference, 1998.

[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 quelques régions voisines. Bulletin del la Société Vaudoisedes Sciences Naturelles 37, 37:241-272, 1901.

[JB06] Eyke Hüllermeier J. Beringer. Online Clustering of Parallel Data Streams.

Fakultät für Informatik, Otto-von-Guericke-Universität 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ă. Comparing clusterings - an information based distance. Jour- nal 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- nal Spaces. Department of Computer Science, University of Waikato, New Zealand., 2000.

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

[XB91] L. X. Xie and G. Beni. Validity measure for fuzzy clustering. IEEE Transac- tions 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

A.1 Beispiele für 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

Abbildung in dieser Leseprobe nicht enthalten

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

B-Distanz:

(A.2)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Kosinus- Ähnlichkeitsfunktion und T-Norm .Min:

(A.4)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Dice- Ähnlichkeitsfunktion und T-Norm .Min:

(A.5)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Jaccard- Ähnlichkeitsfunktion und T-Norm .Min: )

(A.6)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Manhattan- Ähnlichkeitsfunktion und T-Norm .Prod:

(A.7)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Euklid- Ähnlichkeitsfunktion und T-Norm .Prod:

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Maximum- Ähnlichkeitsfunktion und T-Norm .Prod:

(A.9)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Fuzzy-Set- Ähnlichkeitsfunktion und T-Norm .Prod:

(A.10)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Kosinus- Ähnlichkeitsfunktion und T-Norm .Prod:

(A.11)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Dice- Ähnlichkeitsfunktion und T-Norm .Prod:

(A.12)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Jaccard- Ähnlichkeitsfunktion und T-Norm .Prod:

(A.13)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Euklid- Ähnlichkeitsfunktion und T-Norm .Lukasiewicz:

(A.14)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Maximum- Ähnlichkeitsfunktion und T-Norm .Lukasiewicz :

(A.15)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Fuzzy-Set- Ähnlichkeitsfunktion und T-Norm .Lukasiewicz :

(A.16)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Kosinus- Ähnlichkeitsfunktion und T-Norm .Lukasiewicz:

(A.17)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Dice- Ähnlichkeitsfunktion und T-Norm .Lukasiewicz:

(A.18)

Abbildung in dieser Leseprobe nicht enthalten

S-Distanz mit Jaccard- Ähnlichkeitsfunktion und T-Norm .Lukasiewicz:

(A.19)

Abbildung in dieser Leseprobe nicht enthalten