Learning Vector Quantization

2.4 Die Bildauswertung

Bei der Erzeugung der 2D-Beispiele kam es darauf an, verschiedene Problemfälle auf anschauliche Art vorführen zu können. Die Farbe eines Bildpunktes (Pixel) stellt die Klassenzugehörigkeit dar, die Koordinaten der Position eines Pixels entsprechen den Komponenten des Eingabevektors.
Mit einem beliebigen Bildverarbeitungsprogramm können Bilddaten-Dateien im Bitmap-Format erstellt werden. Das Bildformat BMP läßt sich mit dem Entwicklungssystem DELPHI leicht verarbeiten und kann von fast jedem Bildverarbeitungsprogramm gelesen bzw. geschrieben werden. Abbildung 2.5 zeigt ein solches Bitmap-Bild. Zur Geschwindigkeitssteigerung des LVQ-Simulators habe ich festgelegt, daß die Bildkoordinaten fest definiert sein müssen. Die Bildkoordinaten wurden auf 200x200 Pixel und die Farbtiefe auf 8 bit  festgelegt. Würde jeder dieser Pixel mit seinem Farbwert (Klasse) gespeichert werden, dann wären das insgesamt 40 000 Eingabevektoren.
Ein gesondertes Programm, der BmP-Builder, wurde implementiert um Bitmap-Bilder in Eingabevektoren umzuwandeln. Das Programm liest eine Bitmap-Datei ein und überprüft die allgemeinen Eigenschaften des Bildes.
Danach werden die Pixel mit ihren Farbwerten gezählt. In Abb 2.5 ist zu sehen, daß jedem Bild eine Beschreibung zugeordnet wird, die die Anzahl der Pixelpunkte je Klasse führt. Die weißen Pixel werden nicht beachtet, sie sollen in den 2D-Beispielen nicht als Musterklasse sondern als nicht definierter Bereich bzw. als allgemeine Rückweisungsklasse dienen.
Außerdem lassen sich alle Pixel von Musterklassen in einer Textdatei speichern. Für jeden Pixel wird der Farbwert (Klasse) gespeichert sowie seine X- und Y- Koordinaten (Komponenten des Merkmalsvektors).
weitere Informationen zum BmP-Builder
 

Abb. 2.5 Darstellung eines 2D-Beispiels Zu 
sehen sind 3 kompakte Klassen mit jeweils 
5292 Pixeln, (24124 Pixel sind weiß) 
Abb. 2.6 Bildauswertung
Klassifizierte Eingabevektoren im fest
definierten 2D-Merkmalsraum
 

Nach der Umwandlung der Bitmap in eine für den LVQ-Simulator lesbare Form mittels des BmP-Builders, kann die Quelldatei in den Simulator geladen werden. Wenn die Quelldaten geladen sind, sind dem LVQ-Simulator Eingabevektoren und deren Klassenzugehörigkeit bekannt. Jetzt kann die Anzahl der Neuronen und andere Einstellungen (siehe Abschnitt 2.3) festgelegt werden, und der LVQ-Simulator kann mit dem Training beginnen.
Mit dem Auswertungs- Formular (Abb. 2.4) kann man sich die Erfolgsrate ansehen, die über Timer-Funktionen in zeitlich konstanten Abständen neu berechnet wird. Dazu werden in einem gesondert eingerichteten Prozeß die Gewichtsvektoren aller Neuronen vom Trainingsprozeß übernommen und mit diesen das Netz in der Abrufphase simuliert. Man kann sowohl eine reine Reklassifikation als auch einen Test durchführen. Bei der Reklassifikation werden alle Trainings-Eingabevektoren verwendet und die Reklassifikationsrate als Verhältnis aller richtig klassifizierten Trainings-Eingabevektoren zur Gesamtzahl aller Trainings-Eingabevektoren berechnet. Beim Test wird in jeder Epoche ein fest definierter Anteil, bspw. 80%, der Trainings-Eingabevektoren zum Trainieren des Netzes verwendet, und der restliche Anteil (Testmenge), in diesem Beispiel 20%, wird zum Testen des Netzes verwendet. Die zu berechnende Klassifikationsrate ist das Verhältnis aller richtig klassifizierten Test-Eingabevektoren zur Gesamtzahl aller Test-Eingabevektoren.
Eine speziell für die 2D-Daten entwickelte Auswertung (Klassifikation) stellt die Bildauswertung (Abb. 2.6) dar.

In einem begrenzten Ausschnitt des 2-dimensionalen Merkmalsraums (0..199; 0..199) werden flächendeckend alle ganzzahligen Eingabevektoren ausgewählt und mit dem LVQ-Algorithmus klassifiziert. Dadurch entsteht eine 200x200 Bitmap, diese Bitmap wird auf dem Bildschirm durch das Formular der Bildauswertung ausgegeben.
Um einen direkten Vergleich zwischen den so klassifizierten Daten und den Trainings-Eingabevektoren zu haben, implementierte ich die Möglichkeit die Eingabevektoren des Trainings in das Bitmap der Bildauswertung mit einzublenden. Dabei werden die Pixel der Bildauswertung mit den Eingabevektoren des Trainings logisch verknüpft, um die  Klassenzugehörigkeitsinformationen der klassifizierten Daten bestmöglich zu erhalten. Die Gewichtsvektoren können ebenfalls eingeblendet werden.
!Wichtig: Die Farben der Gewichtsvektoren bzw. Eingabevektoren des Trainings entstehen durch logische Verknüpfungen. Die Farbwerte der klassifizierten Eingabevektoren der Bildauswertung werden mit einer Konstanten an der aktuellen Position des Gewichtsvektors verknüpft, bspw. Neuer Farbwert := Bisheriger Farbwert XOR 3. Diese "Falschfarben" geben somit die Lage der Gewichte und Eingabevektoren des Trainings in den gleichen Koordinaten wie die klassifizierten Eingabevektoren der Bildauswertung an. Aussagen über die Klassenzugehörigkeit der Gewichte und Eingabevektoren des Trainings können nicht direkt abgelesen werden. Diese Aussage verdeutlicht  Abbildung 2.16. Die Überschneidung der falsch klassifizierten Daten mit den Eingabevektoren des Trainings können nur anhand der Abbildung 2.15 erahnt werden.
Exakterweise hätte man die Bildauswertung auch Klassifikation nennen können, da das Netz größtenteils Eingabevektoren erhält, die zur Trainingszeit nicht angelegt wurden. Da jedoch immer die gleichen Daten eines stets konstanten Bereiches verwendet werden, ist die Verwendung des Begriffes Klassifikation Verwirrung stiftend. Außerdem sind in den Klassifikationsdaten sämtliche Trainingsdaten enthalten, so daß die Klassifikation mit einem beachtlichen Anteil auch Reklassifikationen enthält.

Nun folgen 3 Beispiele, die aus dem 2D-Beispiel aus Abb. 2.5 errechnet wurden und verschiedenartig mit den Gewichten, sowie den Eingabevektoren der Trainingsdaten verknüpft worden sind.
 

Abb. 2.7 eingeblendete
Gewichte (Neuronen)
Abb. 2.8 eingeblendete
Eingabevektoren des Trainings
Abb. 2.9 eingeblendete
Neuronen und Eingabevektoren
Im folgenden Abschnitt werde ich nur Bildauswertungen mit den Eigenschaften, die in Abb. 2.9 zu sehen sind verwenden, da diese Form der Bildauswertung den größten Informationsgehalt hat.
 

2.5 2D-Beispiele /4/

Die Musterklassen lassen sich grundsätzlich in drei Gruppen unterteilen: „nicht trennbare Klassen“ (Abb. 2.10), „nicht linear trennbare Klassen“ (Abb. 2.11) und „linear trennbare Klassen“ (Abb. 2.12).
Die „linear trennbaren Klassen“ sind einfache Probleme, die sich anhand einer Geraden, bzw. zweier Gewichtsvektoren trennen lassen könnten siehe Abb. 2.12.
Im n-dimensionalen Merkmalsraum liegt eine lineare Trennbarkeit vor, wenn die Trennfunktion ein (n-1) dimensionaler Unterraum von  ist.
Die schwierigeren Probleme ergeben sich bei „nicht linear trennbaren Klassen“. In diesem Fall umschließt eine Klasse teilweise oder vollständig die andere Klasse. Diese Muster können mit stückweise linearen Gebilden oder mit nichtlinearen Gebilden, bspw. Polynomfunktionen getrennt werden.
Einen schlechten Fall stellen die „nicht trennbaren Klassen“ dar. Diese Klassen lassen sich nur mit nahezu unendlich vielen stückweise linearen Gebilden trennen. Genau gesehen besteht eine Klasse hier aus vielen kleinen Ballungsgebieten von „nicht linear trennbaren Klassen“. Liegen keine solcher Ballungsgebiete vor, die Klassen sind dann feinkörnig vermischt, wird ein Postulat der Mustererkennung /4/ verletzt. Dieses Postulat fordert, daß jede Klasse aus mehr oder weniger kompakten Teilgebieten bestehen muß.
 

Abb. 2.10
nicht trennbare Klassen
Abb. 2.11
nicht linear trennbare Klassen
Abb. 2.12
linear trennbare Klassen
Nun möchte ich anhand von ausgewählten 2D-Beispielen einige Eigenschaften des LVQ- Algorithmus darstellen. Ich habe aus jeder Gruppe ein bis zwei Beispiele vom LVQ-Simulator trainieren und  klassifizieren lassen.
 
Im folgenden soll der Vereinfachung wegen nicht von Klasse 1 und Klasse 2 sondern von roter und blauer Klasse gesprochen werden. Ebenso werden die Gewichtsvektoren der roten bzw. blauen Klasse als rotes bzw. blaues Neuron bezeichnet. In gleicher Weise ist die Verwendung der Begriffe roter und blauer Eingabevektoren zu verstehen.


Linear trennbare Klassen:

Abb. 2.13 Quelle
Abb. 2.14 Bildauswertung
Beschreibung der Musterklassen Abb. 2.13:  Zwei kompakte Klassen mit gleichem Stichprobenumfang (5878 Eingabevektoren je Klasse); großer Abstand zwischen den Klassengrenzen der beiden Teilgebiete;
innerhalb der Teilgebiete sind die Eingabevektoren gleichmäßig verteilt

Einstellung des LVQ-Simulators:  (nur) 2 Neuronen; 1 Neuron je Klasse;
Lernschrittweite 0.1;  100 Epochen

Verhalten des LVQ-Algorithmus: Der LVQ-Algorithmus kann die zwei kompakten Klassen mit nur zwei Neuronen problemlos trennen. Die Gewichtsvektoren werden in das Zentrum ihrer Klassen gezogen. Der Grund dafür ist, daß die Gewichtsvektoren von allen Eingabevektoren ihrer Klasse ständig angezogen werden. Durch die Größe der Lernschrittweite von 0.1 werden die Gewichtsvektoren zum Eingabevektor hingezogen, jedoch nur um 10% ihrer Entfernung vom Eingabevektor. Durch die geringer werdende Lernschrittweite werden die Änderungen des Gewichts immer geringer, und der Gewichtsvektor iteriert zum Klassenzentrum, dem Mittelwert aller Merkmalsvektoren einer Klasse.
 


Linear trennbare Klassen:

 
Abb. 2.15 Quelle
Abb. 2.16 Bildauswertung
Abb. 2.17 Klassifikationsraten
Beschreibung der Musterklassen Abb. 2.15: Zwei kompakte Klassen; geringer Abstand zwischen den Klassengrenzen der einzelnen Teilgebiete; die rote Klasse hat 2 kompakte Teilgebiete; ungleicher Stichprobenumfang (1554 Eingabevektoren der roten Klasse und 12863 Eingabevektoren der blaue Klasse); innerhalb der  kreisförmigen Klassengrenzen liegt eine gleichmäßige Verteilung der Merkmalsvektoren vor

Einstellung des LVQ-Simulators: (nur) 3 Neuronen (2 Neuronen sind der roten Klasse zugeordnet); Lernschrittweite 0.1; 100 Epochen; Initialisierung mit Mittelwert

Verhalten des LVQ-Algorithmus:  Der LVQ-Algorithmus kann die zwei kompakten Klassen mit nur drei Neuronen schon zufriedenstellend trennen. An der blauen Klassengrenze kommt es zur Überschneidung mit der roten Klasse Abb. 2.16. In Abb. 2.17 (Auswertung, Klassifikation) ist zu sehen, daß 10.6% der blauen Eingabevektoren des Trainingsdatensatzes falsch klassifiziert worden sind. Diese Fehlklassifikation wird auch im Bild 2.16 deutlich, da die Klassengrenze in den Bereich der blauen Eingabevektoren hineinlangt.
Das blauen Neuron wird in das Zentrum der blauen Klasse gezogen. Die roten Neuronen werden an die Grenzen ihrer Klasse „gedrückt“. Das hat folgenden Grund. Durch den großen euklidischen Abstand des blauen Neurons zur blauen Klassengrenze und dem relativ geringen Abstand der roten Neuronen zu ihren eigenen und den blauen Klassengrenzen, werden die roten Neuronen des öfteren Gewinnerneuron der blauen Klasse. Da nach Gleichung (4) das Neuron vom Eingabevektor entfernt wird, wenn die Klassenzugehörigkeit von Neuron und Eingabevektor nicht übereinstimmt, wird das Neuron von der blauen Klasse abgestoßen. Jedoch wird das Neuron von der roten Klasse wieder angezogen. Dadurch kann sich das Neuron nicht ganz aus der roten Klasse entfernen.
Der Ausweg aus dieser Fehlklassifikation ist die Verwendung von mehreren Neuronen für die blaue Klasse. Somit können sich die blauen Neuronen Richtung Klassengrenze bewegen, und die roten Neuronen werden seltener Gewinnerneuronen der blauen Klasse. Ein  Problem ist die Initialisierung der Gewichte, da hier die Gefahr besteht, daß zwei rote Neuronen in ein Teilgebiet gezogen werden.


Nicht linear trennbare Klassen:

 
Abb. 2.18 Quelle
Abb. 2.19 Bildauswertung
Abb. 2.20 Bildauswertung
Beschreibung der Musterklassen Abb. 2.18: Zwei kompakte Klassen mit ungleichem Stichprobenumfang (732 Eingabevektoren der roten Klasse und 7243 Eingabevektoren der blaue Klasse); die rote Klasse wird vollständig von der blauen Klasse umschlossen; die Abstände zwischen den Klassengrenzen ist relativ groß; innerhalb der kreisförmigen Klassengrenzen liegt eine gleichmäßige Verteilung der Merkmalsvektoren vor
 

Einstellung des LVQ-Simulators:
für Abb. 2.19:  (nur) 2 Neuronen (1 Neuron je Klasse); Lernschrittweite 0.1;  100 Epochen
für Abb. 2.20 : 11 Neuronen (1 Neuron ist der roten Klasse, 10 Neuronen sind der  blauen  Klasse zugeordnet); Lernschrittweite 0.1; 100 Epochen

Verhalten des LVQ-Algorithmus:
Für Abb. 2.19: Der LVQ-Algorithmus kann die zwei Klassen nicht trennen. Das rote Neuron wird aus dem Bereich der blauen Klasse verdrängt. Das blaue Neuron wird in das Zentrum der blauen Klasse, das ist hier die rote Klasse, gezogen. Das rote Neuron wird anfangs häufig Gewinnerneuron der blauen Klasse, dadurch wird es vom Zentrum weggestoßen, bis es schließlich gar nicht mehr gewinnt („Dead Neuron“). Das rote Neuron ist hier außerhalb des Bildbereichs. Der Ausweg aus der kompletten Misklassifikation der roten Klasse: mehr Neuronen für die blaue Klasse verwenden. Das nächste Beispiel beschreibt diesen Fall.
Für Abb. 2.20: Der LVQ-Algorithmus kann die 2 Klassen ausgezeichnet trennen. Das rote Neuron kann sich im Zentrum seiner Klasse plazieren. Die blauen Neuronen können sich in Ihrer Klasse ausgezeichnet verteilen. Somit wird das rote Neuron kein Gewinnerneuron der blauen Klasse mehr.



Nicht trennbare Klassen:
 
Abb. 2.21 Quelle
Abb. 2.22 Bildauswertung
Abb. 2.23 Klassifikationsraten 
 
Beschreibung der Musterklassen Abb. 2.21: Drei verrauschte Klassen mit etwa gleichem Stichprobenumfang (6140 Eingabevektoren der roten Klasse , 6095 Eingabevektoren der grünen und 5904 der blaue Klasse); die Klassen gehen ineinander über; schwache Ballungsgebiete der einzelnen Klassen sind ausgeprägt

Einstellung des LVQ-Simulators: (nur) 6 Neuronen (2 Neuronen je Klasse); Lernschrittweite 0.001; 100 Epochen

Verhalten des LVQ-Algorithmus:  Der LVQ-Algorithmus versucht die Klassen voneinander zu Trennen. Die Lernschrittweite muß in diesem Fall sehr klein gewählt werden, damit das Verfahren nicht divergiert. Die Neuronen finden ihre zugehörigen Eingabevektor-Ballungsgebiete. Eines der blauen Neuronen hat den Bildbereich verlassen. Trotz der schlechten Struktur der Musterdaten, hat der Algorithmus eine Klassifikation vorgenommen. Etwa 70% (Abb. 2.23) der Eingabevektoren der Trainingsdaten wurden richtig klassifiziert. Auch mit wesentlich mehr Neuronen (>100) können keine wesentlich besseren Ergebnisse erzielt werden.


Resümee: /4/
Der LVQ-Algorithmus ist ein robuster Algorithmus. Nach ausreichend langer Trainingszeit erhält man stationäre Gewichtsvektoren (Neuronen), die der Verteilung der Eingabevektoren des Trainings angepaßt sind. Mit der Anpassung  auf die Verteilung der Eingabevektoren stellt der Algorithmus sicher, daß die Hauptmenge aller Merkmalsvektoren einer Klasse richtig klassifiziert wird. Anderseits besitzt er den Nachteil, daß er nicht auf Einrichtung einer optimalen Trennfunktion im Bereich der Klassengrenze optimiert ist. Die Anzahl und vordefinierte Klassenzugehörigkeit der Neuronen wird je nach Struktur der Eingabevektoren gewählt. Der Einfluß der Anzahl der Epochen spielt keine so maßgebliche Rolle. Die Lernschrittweite kann in manchen Fällen sehr empfindlich auf das Trainingsergebnis reagieren und sollte allgemein nicht zu groß gewählt werden (< 0.1).
Die Auswahl des Verfahrens zur Initialisierung der Gewichte wurde nur kurz erwähnt. Von der Initialisierung hängt das gesamte Training ab. Das größte Problem ist das Vorhandensein von mehreren Ballungszentren der Klasse, wie in Abb. 2.15. Aus diesem Grund ist die Wahl der Initialisierung der Gewichte, der entscheidende Aspekt, um ein erfolgreiches Training zu erzielen. Mit den 2D-Beispielen werden Initialisierungsprobleme gezeigt.
Einen Ausweg aus dem Initialisierungsproblem gewährleistet der SOM, der im nächsten Kapitel beschrieben wird.


Learning Vector Quantization