G06F 18/23

Definition

Verfahren zur Gruppierung von Mustern mit dem Ziel, eine bestimmte Struktur oder Bedeutung zu offenbaren. Diese Verfahren zielen darauf ab, verschiedene Gruppen ähnlicher Datenobjekte zu identifizieren, indem sie einer Gruppe (Cluster) nach einem Maß für ihre Ähnlichkeit zugeordnet werden, oder umgekehrt unähnliche Elemente zu identifizieren, um sie in verschiedene Gruppen aufzuteilen. Die Separierbarkeit wird durch Messung der Ähnlichkeit/Unähnlichkeit bestimmt, meist um die Abweichungen innerhalb von Clustern zu minimieren und die zwischen Clustern zu maximieren. In der Regel wird dies in einem hochdimensionalen Merkmalsraum durchgeführt, der durch die Extraktion von Merkmalen konstruiert wird, kann aber auch im ursprünglichen Bereich durchgeführt werden.

Jedes Muster kann ausschließlich zu einem einzigen Cluster gehören (hartes Clustering) oder bis zu einem gewissen Grad gleichzeitig zu mehr als einem Cluster gehören (unscharfes Clustering [Fuzzy Clustering]), und zwar nach einem Abstandsmaß, das Ähnlichkeit oder Unähnlichkeit bestimmen kann. Je nach dem verwendeten Verfahren kann die Nähe (a) zwischen Vektoren, (b) zwischen einem Vektor und einer Gruppe von Vektoren (oder einem Cluster) und (c) zwischen Gruppen von Vektoren (oder verschiedenen Clustern) definiert werden.

Beispiele für Abstandsmaße sind: Unähnlichkeitsmaße (basierend auf l₁, l_2, und l_∞-Normen), Ähnlichkeitsmaße (inneres Produkt, Kosinus, Korrelationskoeffizient nach Pearson, Tanimoto-Abstand usw.).

Zu den verschiedenen Clustering-Algorithmen gehören:

a) Clustering auf der Grundlage statistischer Maße (die hauptsächlich numerische Daten verwenden), die eine Kostenfunktion J in Bezug auf mögliche Gruppierungen anwenden, welche einem globalen oder lokalen Optimierungskriterium unterliegt, und ein Clustering liefern, das J optimiert. Beispiele für Algorithmen sind:

• Harte Clustering-Algorithmen, bei denen ein Vektor ausschließlich zu einem bestimmten Cluster gehört, z.B. k-means, k-medoids, Linde-Buzo-Gray, ISODATA, DBSCAN oder Neural Gas;
• Fuzzy- Clustering-Algorithmen, bei denen ein Vektor bis zu einem gewissen Grad zu einem bestimmten Cluster gehört, z.B. Fuzzy-c-Means, Adaptive Fuzzy C-Shells [AFCS], Fuzzy C Quadric Shells [FCQS] oder Modified Fuzzy C Quadric Shells [MFCQS];
• Probabilistische Clustering-Algorithmen, die bayesschen Klassifizierungsargumenten folgen und bei denen jeder Vektor dem Cluster gemäß einem probabilistischen Konzept zugewiesen wird, z.B. Expectation-Maximization [EM], Gaussian Mixture Model [GMM] oder Mean-Shift;

b) Graphenbasiertes Clustering, z.B. Minimum Spanning Tree [MST] Clustering, Clustering auf der Grundlage gerichteter Bäume, spektrales Clustering oder Graph-Cut-Optimierung;

c) Kompetitive Lernalgorithmen für das Clustering, bei denen eine Gruppe von Repräsentanten ausgewählt wird und das Ziel darin besteht, jeden von ihnen in Regionen des Vektorraums zu verschieben, die in Bezug auf andere Vektoren “dicht” sind. Beispiele sind der Leaky Learning Algorithmus, Self-Organizing Maps [SOM] oder Learning Vector Quantization [ LVQ].

Das hierarchische Clustering ist eine der beliebtesten Verfahren aus der Klasse des graphenbasierten Clustering, mit seinen agglomerativen oder divisiven Varianten. Zur Bestimmung der Gruppierungen können verschiedene Kriterien herangezogen werden, z.B. solche, die auf der Matrixtheorie mit Unähnlichkeitsmatrizen basieren. Die in diesem Schema enthaltenen Algorithmen sind:

• Single-Link-Algorithmus;
• Complete-Link-Algorithmus;
• Weighted Pair Group Method Average [WPGMA];
• Unweighted Pair Group Method Average [UPGMA];
• Weighted Pair Group Method Centroid [WPGMC];
• Ward- oder Minimum-Variance-Algorithmus.
  
  

Querverweise

Nichteinschränkende Querverweise in anwendungsorientierte Klassifikationsstellen

Glossar