FB_ALY_SequentialKMeans

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.

Syntax

Definition:

FUNCTION_BLOCK FB_ALY_SequentialKMeans
VAR_OUTPUT
    ipResultMessage: Tc3_EventLogger.I_TcMessage;
    bError: BOOL;
    bNewResult: BOOL;
    bConfigured: BOOL;
    nClusterIdx: DINT;
    fDistance: LREAL;
END_VAR

Ausgänge

Beispiel

VAR
    fbSequentialKMeans : FB_ALY_SequentialKMeans(nNumChannels := 2, nNumClusters := 3, nAggBufferSize := 10);
    
    nMaxIterations : UDINT :=1;
    eInitMode : E_ALY_KMeansInitMode := E_ALY_KMeansInitMode.Values;
    aInitialClusterCenters : ARRAY[1..3] OF ARRAY[1..2] OF LREAL := [[-30, 0], [10, 2], [30, 4]];    
    bConfigure : BOOL := TRUE;

    nInputCh1 : UDINT;
    fInputCh2 : LREAL; 
    bUpdateClusterCenters : BOOL := TRUE;

    aClusterCenters : ARRAY[1..3] OF ARRAY[1..2] OF LREAL;
END_VAR

// Configure algorithm
IF bConfigure THEN
    bConfigure := FALSE;

    fbSequentialKMeans.Configure(nMaxIterations := nMaxIterations, eInitMode := eInitMode);
    fbSequentialKMeans.SetInitialClusterCenters(ADR(aInitialClusterCenters), SIZEOF(aInitialClusterCenters));
END_IF

// Call algorithm
fbSequentialKMeans.SetChannelValue(1, nInputCh1);
fbSequentialKMeans.SetChannelValue(2, fInputCh2);
fbSequentialKMeans.Call(bUpdateClusterCenters, ADR(aClusterCenters), SIZEOF(aClusterCenters));

Voraussetzungen

Methoden