Clustering bedeutet, daß eine Anzahl von Daten in eine Anzahl von Klassen aufgeteilt wird. Die Daten x kommen aus irgendeinem Raum X, die Klassen sind z.B. durchnummeriert von 1,..,C. In der Regel sind endlich viele Beispiele x vorgegeben und es soll ein Clustering automatisch bestimmt oder gelernt werden, so daß irgendein geeignetes Gütekriteium optimiert wird. So weit klingt das erstmal ziemlich trivial und uninteressant. Warum ist das also häufig hochgradig nichttrivial und außerdem spannend oder zumindest sehr brauchbar?
Es gibt überwachte und unüberwachte Clusteringverfahren.
Bei überwachten Verfahren ist die Anzahl der Klassen C bekannt, die Beispiele bestehen aus Eingabe x und zugehöriger Klasse y. Es soll ein Clusteringverfahren gelernt werden, so daß die Beispiele x auf die korrekten zugehörigen y abgebildet werden. Gütekriterium für ein Clusteringverfahren ist meistens der wirkliche Klassifikationsfehler. Damit können solche Verfahren eingesetzt werden, um irgendwelche Abbildungen mit einem endlichen Bildbereich zu lernen, etwa bei der Fehlstehlendiagnose technischer Systeme, medizinischen Diagnose, Bilderkennung, ... Sogar beliebige stetige Funktionen können so angegangen werden, indem man den Bildbereich hinreichend fein diskretisiert und lernt, in welchem diskreten Stück das jeweilige Bild liegt. D.h. man kann überwachte Verfahren auch in der Zeitreihenprognose, Robotik, Kontrolle, ... einsetzen.
Bei unüberwachten Verfahren ist die Anzahl der Klassen C unbekannt, die Besipiele bestehen nur aus Eingaben x ohne zugehörige Klasse. Ziel ist es, Klassen so zu bestimmen, so daß nur die Information über die Klassenzugehörigkeiten möglichst viel Information über die Daten beinhaltet. Ersetzt man den Raum X der möglichen Eingaben also nur durch die Klassen, dann ist immer noch alles Wesentliche ausgesagt. Was 'alles Wesentliche' heißt, kann unterschiedlich gemessen werden. Durch sogenannte Entropie, Quantisierungsfehler, Topologieerhaltung, .. Das ist von der konkreten Anwendung abhängig. Unüberwachte Verfahren dienen zur Datenkompression, zum Data-Mining, der Datenvisualisierung, ... Konkrete Anwendungen sind also dort, wo viele oder unübersichtliche Daten verarbeitet werden müssen: Web, Datenbanken, Spracherkennungssysteme, Darstellung von medizinischen Daten, Darstellung von Satellitendaten, ...
Es gibt symbolische und subsymbolische Verfahren.
Symbolische Verfahren arbeiten auf symbolischen, insbesondere diskreten Daten und erzeugen leicht für den Menschen einsichtbare Klassifikationen. Sehr häufig angewandt etwa sind Entscheidungsbäume, die rekursiv anhand der Ausprägung eines Merkmals entscheiden, welche Klasse vorliegt. Die Tests sind dabei in einer Baumstruktur gespeichert. Verbreitete Lernalgorithmen sind ID3 und C4.5 von Quinlan. Probleme macht bei symbolischen Verfahren immer, wenn man kontinuierliche Merkmale vorliegen hat, die also diskretisiert werden müssen. Zudem sind die entstehenden Regeln zwar einsichtig, aber häufig nicht die einfachsten möglichen, eine nachträgliche Vereinfachung etwa durch einen genetischen Algorithmus also angebracht.
Subsymbolische Verfahren arbeiten auf reellen Vektorräumen einer festen Dimension. Es gibt verschiedenste statistische, neuronale, und fuzzy-Methoden. Sehr viele Verfahren legen in den Datenraum Propotypen oder Codebooks. Die Zuordnung der Daten zu Klassen erfolgt dann aufgrund ihrer Nähe zu Prototypen. Die Verfahren sind im Gegensatz zu symbolischen Verfahren nicht an logische Formeln gebunden und damit mächtiger. Dafür sind die Ergebnisse nicht so ohne weiteres durch logische Formeln beschreibbar und für den Menschen einsichtig. Die Daten müssen durch reelle Vektoren dargestellt werden, d.h. symbolische Daten müssen irgendwie eingebettet werden.
Subsymbolische Verfahren sind häufig etwa von einer der beiden folgenden Strukturen:
Das Clustering wird durch eine Anzahl von Prototypen gegeben, die zufällig initialisiert werden. Es werden der Reihe nach die Trainingsdaten präsentiert und jeweils der nächste Prototyp ein Stückchen zum Trainingspunkt hingezogen.
Das Clustering wird durch eine Anzahl von zufällig initialisierten Prototypen gegeben. Folgende Schritte wechseln sich ab, bis Konvergenz eintritt: Die Daten werden dem jeweils nächsten Prototypen zugeordnet. Die Prototypen werden neu auf den Mittelpunkt der zu ihnen zugeordneten Daten gesetzt.
Subsymbolische Verfahren unterteilen sich in Verfahren mit cripser und mit softer Zuordnung.
Crispe Verfahren ordnen jeder Eingabe genau eine Klasse zu. Sie können also nicht Clusterverteilungen mit überlappenden Clustern darstellen, Beispiele sind der unüberwachte k-means Algorithmus, unüberwachte oder überwachte Vektorquantisierung oder selbstorganisierende Karten (-> nn-Skript, Kap. 7).
Softe Zuordnungen ordnen jeder Eingabe eine graduelle Zuordnung oder Wahrscheinlichkeit in Bezug auf die einzelnen Klassen zu. Möchte man tatsächlich eine Funktion approximieren, so muß man die Ausgabe also z.B. mit der Berechnung des Maximums kombinieren. Es gibt Möglichkeiten, softe Zuordnungen durch Variieren eines geeigneten Parameters gegen die crispen Zuordnungen konvergieren zu lassen. Das kann von Vorteil sein, wenn die crispen Verfahren nicht gut funktionieren z.B. aufgrund lokaler Minima. Ein Beispiel ist der fuzzy-k-means Algorithmus. Es gibt aber auch soft-Versionen der sogenannten offline-Version von Vektorquantisierung.
Es gibt online und offline Varianten der meisten Verfahren. Das heißt, daß die Trainingsdaten der Reihe nach präsentiert werden und jeder einzelne Trainingspunkt zu einer Änderung der Prototypen führt, etwa LVQ und SOM ( nn-Skript, Kap. 7) oder daß alle Daten gemeinsam angesehen werden und insgesamt zu neuen Prototypen führen, etwa k-means oder fuzzy-k-means.
Neuronale online Verfahren gibt es mit topologischer Struktur der Prototypen, oder ohne topologische Struktur. Bei Vorliegen einer topologischen Struktur werden mit einem einzelnen Prototypen immer auch die topologisch benachbarten geändert, so daß die Prototypen mit ihrer Verbindungsstruktur wie ein Netz über die Daten gestülpt werden, wie etwa bei SOM. Navigation im Netz der Prototypen ist nachher möglich. Liegt keine topologische Struktur/kein Gitter vor, dann werden die Prototypen unabhängig voneinander verändert.
Probleme macht: