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 l1, l2, 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:
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:
| Wiederauffinden von Informationen bezüglich Einzelbilddaten; Clusteranalyse; Klassifizierung | G06F 16/55 |
| Wiederauffinden von Informationen bezüglich Videodaten; Clusteranalyse; Klassifizierung | G06F 16/75 |
| Erkennen oder Verstehen von Bildern oder Videos mittels Clustering, z.B. von ähnlichen Gesichtern in sozialen Netzwerken | G06V 10/762 |
Techniques of grouping patterns together in order to reveal a certain structure or a meaning. These techniques aim at identifying different groups of similar entities by assigning them to a group (cluster) according to a measure of their similarity or, on the opposite, identify dissimilar items to split them into different groups. Separability is determined by measuring the similarity/dissimilarity, mostly to minimise the intra-cluster variations while maximising the inter-cluster ones. This is usually performed in a high-dimensional feature space constructed by extracting features, but can also be performed in the original domain.
Any pattern may belong exclusively to a single cluster (hard clustering) or it may belong simultaneously to more than one cluster up to a certain degree (fuzzy clustering) according to a proximity measure that may determine similarity or dissimilarity. Depending on the clustering method used, proximity may be defined (a) between vectors, (b) between a vector and a set of vectors (or a cluster), and (c) between sets of vectors (or different clusters).
Examples of proximity measures are: dissimilarity measures (based on l1, l2, and l∞ norms), similarity measures (inner product, cosine, Pearson’s correlation coefficient, Tanimoto distance, etc.).
Different clustering algorithms include:
a) clustering based on statistical measures (which mainly employ numerical data) which adopt a cost function J related to possible groupings which is subject to a global or local optimisation criterion, and return a clustering that optimises J. Examples of algorithms are:
b) graph-based clustering, e.g. minimum spanning tree (MST) clustering, clustering based on directed trees, spectral clustering or graph-cut optimisation;
c) Competitive learning algorithms for clustering in which a set of representatives is selected and the goal is to move each of them to regions of the vector space that are “dense” in terms of other vectors. Examples are leaky learning algorithm, Self-Organizing Maps (SOM) or Learning Vector Quantization (LVQ).
Hierarchical clustering is one of the popular techniques from the class of graph-based clustering, with its agglomerative or divisive variants. Various criteria can be used for determining the groupings, such as those based on matrix theory involving dissimilarity matrices. Algorithms included in this scheme are:
| Information retrieval of still images; Clustering; Classification | G06F 16/55 |
| Information retrieval of video data; Clustering; Classification | G06F 16/75 |
| Image or video recognition or understanding using clustering, e.g. of similar faces in social networks | G06V 10/762 |