Sequential k-Means

Der Algorithmus Sequential k-Means ist eine Implementierung des gleichnamigen unüberwachten Clustering-Algorithmus und stellt eine sequentielle Variante des weit verbreiteten Clustering-Algorithmus k-Means für Streamingdaten dar. Das Ziel des Algorithmus ist es, anhand der Struktur der Daten Cluster zu finden, die jeweils ähnliche Datenpunkte beinhalten und unterschiedliche Datenpunkte voneinander abgrenzen.

Die Anzahl der Eingangskanäle (im Folgenden als n bezeichnet) für diesen Algorithmus kann vom Benutzer frei gewählt werden. Diese Eingänge spannen den n-dimensionalen Merkmalsraum auf, in dem die Cluster zu finden sind. In jedem Analysezyklus liefert der Datenstrom dem Algorithmus einen neuen Merkmalsvektor, der als Datenpunkt in diesem Merkmalsraum interpretiert werden kann. Datenpunkte, die in diesem Merkmalsraum nahe beieinanderliegen, werden dem gleichen Cluster zugewiesen. Die Anzahl der vorhandenen Cluster muss vor Beginn der Analyse vom Anwender gesetzt werden und bleibt fest.

Im Gegensatz zum k-Means Algorithmus für die klassische Batch-Analyse liegen die Daten für den Sequential k-Means zum Zeitpunkt der Analyse nicht vollständig vor. Stattdessen gehen die Datenpunkte in Form von Streamingdaten nach und nach ein und werden hier daher sequentiell verarbeitet und dem entsprechenden am nächsten liegenden Cluster zugeordnet. Aus diesem Vorgehen ergeben sich einige Unterschiede, wobei zwei davon für die Benutzung des Algorithmus sowie die Parametereinstellungen besonders relevant sind.

Zum einen liegen zu Beginn einer Batch-Analyse bereits alle Datenpunkte und damit auch die Wertebereiche der einzelnen Merkmale vor, bei der sequentiellen Analyse ist dies nicht der Fall, sodass die Wertebereiche vorher nicht zwangsläufig feststehen. Es ist jedoch hilfreich, die Wertebereiche der Eingangskanäle bereits vorher zu kennen, auch wenn die Werte erst im Laufe der Analyse eintreffen. Dies spielt insbesondere für die Initialisierung der Cluster-Mittelpunkte eine Rolle. Für die Initialisierung können drei verschiedene Vorgehensweisen gewählt werden. Die Mittelpunkte können mit konkreten Werten über ein Parameter-Array vorgegeben werden (Values). Die Mittelpunkte können aber auch zufällig (Random) oder äquidistant (Equidistant) in einem definierten Wertebereich gesetzt werden. Für die Initialisierungsmodi Random und Equidistant werden die Wertebereiche benötigt und müssen über die Parameter Lower Bounds und Upper Bounds für die einzelnen Eingangskanäle eingestellt werden.

Zum anderen werden in einer Batch-Analyse üblicherweise alle Datenpunkte mehrfach durchlaufen, um die Cluster-Mittelpunkte zu aktualisieren, bis diese sich nur noch minimal verändern. Das ist in der Form im Rahmen der sequentiellen Analyse nicht möglich. Um die Cluster-Mittelpunkte jedoch trotzdem anpassen zu können und Datenpunkte mehrfach zu durchlaufen, verfügt der Algorithmus Sequential k-Means über einen Zwischenspeichermechanismus, den Aggregation Buffer. Mit diesem wird es möglich, eine begrenzte Anzahl von Werten zwischenzuspeichern. Beim Füllen des Buffers, werden alle eintreffenden Datenpunkte dem am nächsten liegenden Cluster zugeordnet. Die Distanz zwischen einem Datenpunkt und den Cluster-Mittelpunkten wird durch die Euklidische Norm bestimmt. Erst wenn der Buffer gefüllt ist, werden die Cluster-Mittelpunkte anhand der neu zugewiesenen Datenpunkte im Buffer aktualisiert. Dabei entspricht der neue Cluster-Mittelpunkt dem Mittelwert aller im Cluster enthaltener Datenpunkte. Dieser kann inkrementell berechnet werden, sodass die alten Datenpunkte nicht für die Berechnung benötigt werden. Die Größe des Buffers wird durch den Parameter Aggregation Buffer Size gesetzt, der Default-Wert ist 10. Durch den Parameter Max Iterations kann zusätzlich angegeben werden, wie oft durch den Buffer iteriert wird. Hier ist der Default-Wert gleich eins. Wird der Wert beispielsweise auf zwei gesetzt, werden nach dem ersten Anpassen der Cluster-Mittelpunkte, die Datenpunkte im Buffer den Clustern neu zugewiesen und anschließend die Cluster-Mittelpunkte erneut angepasst. Aufgrund der Verschiebung der Cluster-Mittelpunkte ist es möglich, dass einzelne Datenpunkte von einer Iteration zur nächsten unterschiedlichen Clustern zugewiesen werden können. Aufgrund der begrenzten Rechenkapazität für die Datenverarbeitung zwischen zwei Zyklen sollten für die Parameter Aggregation Buffer Size und Max Iterations keine zu hohen Werte vergeben werden, da die Aktualisierung der Cluster-Mittelpunkte andernfalls eventuell nicht gewährleistet werden kann. Werden die Cluster-Mittelpunkte bei großen Werten für diese Parameter nicht aktualisiert, bei kleineren Parameterwerten hingegen schon, ist dies ein Indiz dafür, dass die Rechenkapazität für die eingestellten Parameterwerte nicht ausreicht und kleinere Werte gewählt werden sollten.

Optional kann ein boolesches Signal für den Eingang Enable Execution ausgewählt werden, sodass der Algorithmus nur aktiv ist, wenn der Wert des ausgewählten Signals TRUE ist.

Eingangswerte

• Update Cluster Centers: Falls TRUE, werden die Mittelpunkte der einzelnen Cluster durch die eingehenden Daten aktualisiert. Falls FALSE, bleiben die Cluster-Mittelpunkte Cluster unverändert und werden nur verwendet, um den Cluster-Index der eingehenden Datenpunkte zu bestimmen.
• Input 01, …, Input 0n: Diese Eingänge bilden den n-dimensionalen Merkmalsraum, für den das Clustering ausgeführt wird.

Konfigurationsoptionen

• Num Channels: Bestimmt die Anzahl der Eingangskanäle.
• Number of Clusters: Definiert die Anzahl der Cluster.
• Aggregation Buffer Size: Gibt die Größe des Aggregation Buffers und damit die Anzahl an Zyklen an, nach denen die Cluster-Mittelpunkte aktualisiert werden. Die Eingangswerte dieser Zyklen werden intern (im Aggregation Buffer) zwischengespeichert. Der Default-Wert für diesen Parameter ist 10.
• Max Iterations: Gibt an, wie oft über die Werte im Aggregation Buffer iteriert wird. Der Default-Wert für diesen Parameter ist 1.
• Initialization Mode: Gibt an, auf welche Art die Cluster-Mittelpunkte initialisiert werden:
• Random: Die Cluster-Mittelpunkte werden zufällig in den Grenzen gesetzt, die durch Lower Bounds und Upper Bounds gesetzt sind.
• Euqidistant: Die Cluster-Mittelpunkte werden äquidistant in dem Wertebereich verteilt, welcher durch die Grenzen Lower Bounds und Upper Bounds definiert ist.
• Values: Die Cluster-Mittelpunkte werden mit den Werten initialisiert, die durch das Array Initial Cluster Centers gesetzt werden.
• Initial Cluster Centers: Für den Initialisierungsmodus Values werden hier die Werte für die initialen Cluster-Mittelpunkte gesetzt. Die Werte für die einzelnen Cluster werden zeilenweise gesetzt. Das heißt die Anzahl der Zeilen der Matrix entspricht der Anzahl der Cluster (Number of Clusters) und die Anzahl der Spalten der Matrix der Anzahl der Eingangskanäle (Number of Channels). In der ersten Zeile stehen die Werte für das erste Cluster für jeweils jeden Eingangskanal, usw.
• Lower Bounds: Für die Modi Random und Equidistant werden die unteren Grenzen für die einzelnen Eingangskanäle gesetzt.
• Upper Bound: Für die Modi Random und Equidistant werden die oberen Grenzen für die einzelnen Eingangskanäle gesetzt.

Ausgangswerte

• Cluster Index: Gibt den Cluster-Index an, der dem Datenpunkt des letzten Zyklus zugeordnet wurde und zeigt damit das entsprechende zugeordnete Cluster an.
• Distance: Gibt die Euklidische Distanz zwischen dem Datenpunkt und dem zugeordneten Cluster-Mittelpunkt an.
• Cluster Centers: Gibt die Cluster-Mittelpunkte aller Cluster zeilenweise aus. Dies entspricht einer Matrix der Dimension Number of Clusters x Number of Channels.

Standard HMI Controls

Für den Algorithmus Sequential k-Means sind die folgenden HMI Controls für die Generierung eines Analytics Dashboards verfügbar:

1. Das Table Control oder Multivalue Control visualisiert die Ausgangswerte: Lower Bounds, Upper Bounds und Initial Centers.

Alternativ können im Algorithmus Sequential k-Means mit dem Mapping Wizard kundenspezifische HMI Controls gemappt werden.