K-Means-Clustering und Vektorquantisierung (scipy.cluster.vq)#
Bietet Routinen für K-Means-Clustering, das Erzeugen von Codebüchern aus K-Means-Modellen und das Quantisieren von Vektoren durch Vergleichen mit Zentroiden in einem Codebuch.
|
Normalisiert eine Gruppe von Beobachtungen pro Merkmal. |
|
Weist Beobachtungen Codes aus einem Codebuch zu. |
|
Führt K-Means für eine Menge von Beobachtungsvektoren durch, die k Cluster bilden. |
|
Klassifiziert eine Menge von Beobachtungen in k Cluster mithilfe des K-Means-Algorithmus. |
Hintergrundinformationen#
Der K-Means-Algorithmus nimmt als Eingabe die Anzahl der zu generierenden Cluster, k, und eine Menge von Beobachtungsvektoren zum Clustern. Er gibt eine Menge von Zentroiden zurück, einen für jeden der k Cluster. Ein Beobachtungsvektor wird dem Cluster oder dem Zentroidenindex des ihm am nächsten liegenden Zentroiden zugeordnet.
Ein Vektor v gehört zum Cluster i, wenn er näher an Zentroid i als an jedem anderen Zentroiden liegt. Wenn v zu i gehört, sagen wir, Zentroid i ist der dominierende Zentroid von v. Der K-Means-Algorithmus versucht, die Verzerrung zu minimieren, die als Summe der quadrierten Abstände zwischen jedem Beobachtungsvektor und seinem dominierenden Zentroiden definiert ist. Die Minimierung wird durch iteratives Neuzuordnen der Beobachtungen zu Clustern und Neuberechnen der Zentroiden erreicht, bis eine Konfiguration erreicht ist, in der die Zentroiden stabil sind. Man kann auch eine maximale Anzahl von Iterationen definieren.
Da Vektorquantisierung eine natürliche Anwendung für K-Means ist, wird oft Terminologie aus der Informationstheorie verwendet. Der Zentroidenindex oder Clusterindex wird auch als "Code" bezeichnet und die Tabelle, die Codes zu Zentroiden und umgekehrt abbildet, wird oft als "Codebuch" bezeichnet. Das Ergebnis von K-Means, eine Menge von Zentroiden, kann zur Quantisierung von Vektoren verwendet werden. Quantisierung zielt darauf ab, eine Codierung von Vektoren zu finden, die die erwartete Verzerrung reduziert.
Alle Routinen erwarten, dass obs ein M x N-Array ist, wobei die Zeilen die Beobachtungsvektoren sind. Das Codebuch ist ein k x N-Array, wobei die i-te Zeile der Zentroid des Code-Wortes i ist. Die Beobachtungsvektoren und Zentroiden haben dieselbe Merkmalsdimension.
Als Beispiel nehmen wir an, wir möchten ein 24-Bit-Farbbild (jeder Pixel wird durch ein Byte für Rot, eins für Blau und eins für Grün dargestellt) komprimieren, bevor wir es über das Web senden. Durch die Verwendung einer kleineren 8-Bit-Codierung können wir die Datenmenge um zwei Drittel reduzieren. Idealerweise sollten die Farben für jeden der 256 möglichen 8-Bit-Codierungswerte so gewählt werden, dass die Verzerrung der Farbe minimiert wird. Das Ausführen von K-Means mit k=256 erzeugt ein Codebuch von 256 Codes, die alle möglichen 8-Bit-Sequenzen abdecken. Anstatt einen 3-Byte-Wert für jeden Pixel zu senden, wird der 8-Bit-Zentroidenindex (oder Code-Wort) des dominierenden Zentroiden übertragen. Das Codebuch wird ebenfalls über die Leitung gesendet, damit jeder 8-Bit-Code wieder in eine 24-Bit-Pixelwertdarstellung übersetzt werden kann. Wenn das interessierende Bild ein Ozean war, würden wir erwarten, dass viele 24-Bit-Blautöne durch 8-Bit-Codes dargestellt werden. Wenn es ein Bild eines menschlichen Gesichts war, würden mehr Hauttöne im Codebuch repräsentiert werden.