next up previous
Nächste Seite: Definition von Objektbeschreibungen Aufwärts: Vorbereitung der Lookup-Tabelle Vorherige Seite: Farbraum

Trainingsalgorithmus

Zum Training wird hier ein Clustering-Algorithmus verwendet. Und zwar handelt es sich um eine Generalisierung des k-means Algorithmus [11] für Klassifizierungszwecke.

Beim Clustern werden im allgemeinen repräsentative Vektoren für eine Menge von multidimensionalen Datenvektoren gesucht. Die Vektoren sind in folgendem Sinne repräsentativ: Seien $N$ Vektoren $X=\{x_i,1,\dots,N\}$ in einem $D$-dimensionalen Raum gegeben. Dann partitioniert eine Menge von $M$ Zentren $\{m_1,\dots,m_M\},\,m_k \in R^D,\,k=1,\dots,M$ die Daten $X$ in $M$ Mengen $\{S_1\,,\,\dots,$ $S_M\}$, wobei jede Menge $S_k$ die Punkte aus X beinhaltet, die innerhalb des Voronoi Polyeders des Zentrums $m_k$ liegen:

\begin{displaymath} S_k=\{x_i\vert\:\Vert x_i-m_k\Vert\leq\Vert x_i-m_j\Vert,j\neq k\} \end{displaymath} (26)

Hierbei handelt es sich um eine ``Nächster-Nachbar''-Zugehörigkeit.

Abbildung: Nächster-Nachbar-Zuordnung einiger Punktmengen. Eingezeichnet sind die Grenzen der durch die drei Zentren repräsentierten Cluster. Die Grenzen liegen senkrecht mittig auf den Verbindunglinien zwischen den Zentren.
\resizebox {1\columnwidth}{!}{\includegraphics{cluster.eps}}

Der k-means Algorithmus findet iterativ eine lokal-optimale Menge von $M$ Zentren, ausgehend von einer Menge $m^0$ von $M$ zufällig positionierten Zentren, mit Hilfe der Anpassungsregel:

\begin{displaymath} m_k^{t+1}=\frac{\sum_{i=1}^{N}x_i\vec{1}_{S_k^t}(x_i)} {\sum_{i=1}^{N}\vec{1}_{S-k^t}(x_i)} \end{displaymath} (27)

wobei
\begin{displaymath} S_k^t=\{x_i\vert\:\Vert x_i-m_k^t\Vert\leq\Vert x_i-m_j^t\Vert,\,j\neq k\} \end{displaymath} (28)

und $\vec{1}_{S_k^t}(x_i)$ die Indikatorfunktion der Menge $S_k^t$ ist. Ein Zentrum $m_k$ wird hierbei bei einem Updateschritt zu $t+1$ auf das gravitatorische Zentrum der gleichschweren Vektoren, die zum Zeitpunkg $t$ in $S_k$ waren, bewegt.

Um nun diesen Algorithmus für die vorliegende Klassifizierungsaufgabe zu verwenden, werden zusätzlich Klassen eingeführt. Hierbei erhält jeder Datenvektor $x_i$ eine Klasse $C(x_i)\in\{c_1,\dots,c_L\}$ zugeordnet. Nun werden für jede einzelne Klasse $c_j$ $M_j$ optimale Zentren $\{m_{jk},\,j=1,\dots,L,\,k=1,\dots,M_j\}$ gesucht Die Menge der im Voronoi-Polyeder liegenden Datenpunkte und die zugehörige, in Regel (3.3) benötigte Indikatorfunktion müssen dabei folgendermaßen angepaßt werden:

$\displaystyle S_{jk}^t=\{x_i$ $\textstyle \vert$ $\displaystyle C(x_i)=c_j \;\land$  
    $\displaystyle \Vert x_i-m_{jk}\Vert<\Vert x_i-m_{jl}\Vert,\,l\leq k\}$ (29)

und
\begin{displaymath} \vec{1}_{S_{jk}^t}(x_i)= \left\{\begin{array}{ll} 1 & \textr... ...} x_i \in S_{jk}^t \\ 0 & \textrm{sonst } \end{array} \right. \end{displaymath} (30)

Damit üben die Datenvektoren $x_i$ mit der Klasse $C(x_i)$ nur noch Einfluß auf Zentren $m_{jk}^t$ der gleichen Klasse $j$ aus.

Dieser Algorithmus hat aber zwei wesentliche Probleme beim Finden von Klassengrenzen: Zum einen befinden sich relativ viele Zentren in der Mitte der Klassen, obwohl nur die Zentren am Rand der Cluster die Grenzen und damit die Klassifizierung bestimmen. Schlimmer wiegt aber noch das Initialisierungsproblem. Es ist nicht bekannt, wieviele Zentren jeder Klasse für eine gute Klassifizierung benötigt werden und wo sie positioniert werden müssen.

Diesen Problemen wird mit einer Erweiterung der Zustandsbeschreibungen der Zentren begegnet, wie es von Marroquin und Girosi beschrieben wird [11]. Neben der Position eines Zentrums werden zusätzlich Daten über das dynamische Verhalten in die Zustandsbeschreibung aufgenommen. Zum einen wird die Anzahl der Datenpunkte innerhalb des Voronoi-Polyeders unabhängig von der Klassenzugehörigkeit gezählt (Gleichung 3.7), zum anderen nur solche Datenpunkte gleicher Klasse (Gleichung 3.8). Ein erweiterter Zustand ist dann $(m_{jk}^t, h_{jk}^t, \hat{h}_{jk}^t)$ mit

\begin{displaymath} h_{jk}^t=\sum_{i=1}^N \vec(1)_{S_{k}^t}x_i \end{displaymath} (31)

und
\begin{displaymath} \hat{h}_{jk}^t=\sum_{i=1}^N \vec(1)_{S_{jk}^t}x_i \end{displaymath} (32)

Anhand dieser Daten, wie oft ein Zentrum über die anderen Zentren gewonnen hat und wie viele der Datenpunkte in seinem Einflußbereich die gleiche Klasse haben, kann die Zahl der Zentren dynamisch angepaßt werden. Es wird mit einer beliebigen Menge Zentren beliebiger Klasse gestartet. Prinzipiell ist es auch möglich, wenn man eine längere Laufzeit in Kauf nimmt, mit nur einem einzigen Zentrum zu beginnen. Anschließend wird nach jeder Iteration des k-means Algorithmus jedes Zentrum $m_{jk}$ nach der ersten zutreffenden der folgenden Regeln angepaßt:

$\hat{h}_{jk}^t < \theta_j N$
Unterschreitet die Anzahl der Datenpunkte, die einen Einfluß auf das Zentrum $m_{jk}$ ausgeübt haben, einen unteren Schwellwert für diese Klasse $j$, wird das Zentrum gelöscht.
$\hat{h}_{jk}^t / h_{jk}^t < \omega $
Unterschreitet der Prozentsatz der Datenpunkte der gleichen Klasse $j$ im Voronoi Polyeder des Zentrum $m_{jk}$ eine vorgegebene Schwelle -- ist die Klassifizierung also zu ungenau, dann wird das Zentrum aufgeteilt. Ein neues Zentrum wird zufällig in der näheren Umgebung platziert und erhält die Klasse, der neben der Klasse $j$ am häufigsten auftretenden Datenpunkte.
$h_{jk}^t > \Theta_j N$
Überschreitet die Anzahl aller Datenpunkte im Voronoi-Polyeder des Zentrums einen oberen Schwellwert für die Klasse $j$, wird das Zentrum aufgeteilt. Ein neues Zentrum der gleichen Klasse wird zufällig in der näheren Umgebung platziert.
Nach einer bestimmten Anzahl von Iterationen werden die vorhanden Zentren nicht weiter aufgeteilt, ihre Position aber weiterhin angepaßt, um die Konvergenz sicherzustellen.

Nachdem die Parameter $\omega$, $\theta_j$ und $\Theta_j$ bei der Implementierung des Algorithmus entsprechend angepaßt wurden, zeigt dieses Training eine sehr gute Konvergenz innerhalb weniger Iterationen. Dem Benutzer wird damit ein Werkzeug zur Verfügung gestellt, mit dem er das System innerhalb weniger Sekunden auf neue Lichtverhältnisse oder neue Farbmarker einrichten kann. Bei den vorgenommenen Tests erweist sich das Training im UV-Raum gegenüber wechselnden Lichtverhältnissen als wesentlich robuster. Es lassen sich ohne großes ``Herumspielen'' Segmentierungen mit erstaunlich niedrigen Fehlern trainieren. Um den Benutzer ein wenig in das Trainings- und Generalisierungsverhalten eingreifen zu lassen, kann er die durchschnittliche Anzahl der Zentren pro Klasse mit Hilfe eines Schiebereglers anpassen. Je nach Stellung werden $\theta_j$ und $\Theta_j$ um den gleichen Faktor erhöht oder erniedrigt.

next up previous
Nächste Seite: Definition von Objektbeschreibungen Aufwärts: Vorbereitung der Lookup-Tabelle Vorherige Seite: Farbraum

2001-12-05