9 Tracking
In this section, it is the pursuit to explain the third step, tracking, by initially answering the following questions. What is tracking, why is it regarded to be complex and why is it important? In the subsection 9.0.1 the final workflow will be elaborated . Furthermore, a brief discussion on the advancements in tracking of CNMccontrol-oriented Cluster-based Network Modeling to first CNMc shall be given. Since the data and workflow of tracking are extensive, for the sake of a better comprehension the steps are visually separated with two horizontal lines in the upcoming subsection. The lines introduce new tracking subtasks, which are intended to provide clear guidance to orient readers within the workflow. Note, the tracking results will be presented in subsection 12.
To define the term tracking some explanations from subsection 4.0.1 shall be revisited . Through the clustering step, each centroid is defined with a label. The label allocation is performed randomly as showed in subsection 8.0.1. Thus, matching centroid labels from one model parameter value \(\beta_i\) to another model parameter value \(\beta_j\), where \(i \neq j\), becomes an issue. In order first, to understand the term tracking, figure 9.1 shall be considered. The centroids of the Lorenz system 7.1 for two \(\beta\) values \(\beta_i = 31.333\) in green and \(\beta_j = 32.167\) in yellow are plotted next to each other. The objective is to match each centroid of \(\beta_i\) with one corresponding centroid of \(\beta _j\). It is important to understand that the matching must be done across the two \(\beta\) values \(\beta_i\) and \(\beta_j\) and not within the same \(\beta\).
By inspecting the depicted figure closer it can be observed that each green centroid \(\beta_i\) has been connected with a corresponding yellow centroid \(\beta_j\) with an orange line. The centroids which are connected through the orange lines shall be referred to as inter \(\beta\) connected centroids. Determining the inter \(\beta\) connected centroids is the outcome of tracking. Thus, it is matching centroids across different model parameter values \(\beta\) based on their corresponding distance to each other. The closer two inter \(\beta\) centroids are, the more likely they are to be matched. The norm for measuring distance can be chosen from one of the 23 possible norms defined in SciPy (Virtanen et al. 2020). However, the default metric is the euclidean norm which is defined as equation 9.1 .
\[ \begin{equation} \label{eq_16} d(\vec x, \vec y) = \sqrt[]{\sum_{i=1}^n \left(\vec{x}_i - \vec{y}_i\right)^2} \end{equation} \tag{9.1}\]
The orange legend on the right side of figure 9.1 outlines the tracked results. In this rare and not the general case, the inter \(\beta\) labeling is straightforward in two ways. First, the closest centroids from \(\beta_i\) to \(\beta_j\) have the same label. Generally, this is not the case, since the centroid labeling is assigned randomly. Second, the inter \(\beta\) centroid positions can be matched easily visually. Ambiguous regions, where visually tracking is not possible, are not present. To help understand what ambiguous regions could look like, figure 9.2 shall be viewed. It illustrates the outcome of the Lorenz system 7.1 with \(\beta_i=39.004,\, \beta_j = 39.987\) and with a number of centroids of \(K= 50\). Overall, the tracking seems to be fairly obvious, but paying attention to the centroids in the center, matching the centroids becomes more difficult. This is a byproduct of the higher number of centroids \(K\). With more available centroids, more centroids can fill a small area. As a consequence, multiple possible reasonable matchings are allowed. Note, that due to spacing limitations, not all tracking results are listed in the right orange legend of figure 9.2 . The emergence of such ambiguous regions is the main driver why tracking is considered to be complex.
In general, it can be stated that the occurrence of ambiguous regions can be regulated well with the number of centroids \(K\). \(K\) itself depends on the underlying dynamical system. Thus, \(K\) should be only as high as required to capture the complexity of the dynamical system. Going above that generates unnecessary many centroids in the state space. Each of them increases the risk of enabling ambiguous regions to appear. Consequently, incorrect tracking results can arise.
In figure 9.3 a second example of tracked outcome for the Lorenz system 7.1 with \(\beta_i=30.5,\, \beta_j=31.333, \, K = 10\) is given. Here it can be inspected that the immediate inter \(\beta\) centroid neighbors do not adhere to the same label. Hence, it is representative of a more general encountered case. The latter is only true when the \(K\) is chosen in a reasonable magnitude. The reason why centroids are tracked by employing distance measurements is grounded in the following. If the clustering parameter n_init is chosen appropriately (see 8.0.1), the position of the centroids are expected to change only slightly when \(\beta\) is changed . In simpler terms, a change in \(\beta\) should not move a centroid much, if the clustering step was performed satisfactorily in the first place.
The next point is to answer the question, of why tracking is of such importance to CNMccontrol-oriented Cluster-based Network Modeling. The main idea of CNMccontrol-oriented Cluster-based Network Modeling is to approximate dynamical systems and allow prediction trajectories for unseen \(\beta_{unseen}\). The motion, i.e., the trajectory, is replicated by the movement from one centroid to another centroid. Now, if the centroids are labeled wrong, the imitation of the motion is wrong as well. For instance, the considered dynamical system is only one movement from left to right. For instance, imagining a dynamical system, where the trajectory is comprised of solely one movement. Namely, moving from left to right. Following that, labeling the left centroid \(c_l\) to be the right centroid \(c_r\), would fully change the direction of the movement, i.e. \((c_l \rightarrow c_r) \neq (c_r \rightarrow c_l)\). In one sentence, the proper tracking is vital because otherwise CNMccontrol-oriented Cluster-based Network Modeling cannot provide reliably predicted trajectories.
9.0.1 Tracking workflow
In this subsection, the main objective is to go through the designed tracking workflow. As side remarks, other attempted approaches to tracking and the reason for their failure will be mentioned briefly.
To recapitulate on the term tracking, it is a method to match centroids across a set of different model parameter values \(\vec{\beta}\) based on their respective distances. One obvious method for handling this task could be KNNKNearest Neighbor. However, having implemented it, undesired results were encountered. Namely, one centroid label could be assigned to multiple centroids within the same \(\beta\). The demand for tracking, on the hand, is that, e.g., with \(K=10\), each of the 10 available labels is found exactly once for one \(\beta\). Therefore, it can be stated that KNNKNearest Neighbor is not suitable for tracking, as it might not be possible to impose KNNKNearest Neighbor to comply with the tracking demand.
The second approach was by applying DTWDynamical Time Warping. The conclusion is that DTW’s tracking results highly depended on the order in which the inter \(\beta\) distances are calculated. Further, it can be stated that DTW needs some initial wrong matching before the properly tracked outcomes are provided. The initial incorrect matching can be seen as the reason, why DTW is mostly used when very long signals, as in speech recognition, are provided. In these cases, some mismatching is tolerated. For CNMccontrol-oriented Cluster-based Network Modeling, where only a few \(K\) centroids are available, a mismatch is strongly unwelcome.
The third method was based on the sequence of the labels. The idea was that the order of the movement from one centroid to another centroid is known. In other terms, if the current position is at centroid \(c_i\) and the next position for centroid \(c_{i+1}\) is known. Assuming that the sequences across the \(\vec{\beta}\) should be very similar to each other, a majority vote should return the correct tracking results. It can be recorded that this was not the case and the approach was dismissed.
After having explained 3 methods, which did not lead to a satisfactory outcome, the data and workflow of the final successful approach shall be presented. First very concisely, followed by an in-depth account. For that, figure 9.4 shall be analyzed. The initial input is obtained through settings.py, where execution, storage and plotting attributes are defined. For the further sub-steps, it shall be noted that the index big O stands for output of the respective sub-step. The clustered results from step two, described in section 8 are used as input for the so-called ordering step. The ordered state can be stored and plotted if desired and exploited to calculate a cost matrix \(\boldsymbol A (\vec{\beta})\).
The tracking demand is applied on \(\boldsymbol A (\vec{\beta})\), e.g., each row element must be matched to exactly one column element with the constraint that their additive sum is minimized. It will return a suggested best path, i.e., the proposed optimized tracking path. It is possible that the proposed optimized tracking path may not be feasible concerning a linking condition, it undergoes a validity check. If required the suggested path will be chopped off and replaced such that the linking condition is met. The final path is then imposed to a transition such that the centroid labeling across all available \(\vec{\beta}\) matches. The transformed final paths are designated as the tracked outcome and can be saved and plotted.
Since the fast description leaves some open questions, the in-depth explanation shall be tackled. Defining settings.py is analogously done to the two previous steps, i.e. data generation 7 and clustering 8. Therefore, accounts regarding the sub-tasks settings.py and the clustered data are not repeated.
1. Ordering \(\,(\vec{\boldsymbol{\beta}})\)
The ordering of the clustered data can be understood by viewing figures 9.5 and 9.6 . Both depict the clustered Lorenz system 7.1 for \(\beta = 30.5\). The difference between the two figures is that figure 9.5 shows the clustering as it is obtained from the clustering step. It shall be referred to as the initial state. Figure 9.6 on the other shows the ordered state, i.e. the state after applying the ordering sub-step. The labeling of the ordered step represents to some degree the actual movement of the trajectory. It can be observed that moving from label \(1\) up to \(6\) in a consecutive manner the resulting trajectory is generating the left ear of the Lorenz system. Analogously, moving from label \(7\) up to \(10\) produces the right ear of the Lorenz system. Furthermore, the transition from centroid \(6\) to \(7\) captures the transition from one ear to the other.
The way the ordered state is retrieved is as follows. The entire sequence of the motion along the centroids is available. In simpler terms, the first centroid from where the trajectory will start, all the upcoming centroids and the order in which they will be visited are known. Therefore, the initial centroid can be labeled as \(1\), the second as \(2\) and so on. However, it is important to note that with modifying one label of the trajectory sequence, the same label needs to be found in the entire sequence and modified as well. Otherwise, the ordered-state is true for one turn and a wrong initial-ordered-state mixture is kept for the remaining turns. Such an approach would also falsify the trajectory. The labeling in the ordered state provides information about the trajectory. Further, the original motion of the trajectory is untouched. Labeling the characteristic centroids with different numbers or with Greek letters does not impose any change on the original dynamics. For that to be fully true, the newly introduced labeling must be consistent across the entire sequence. Although it is obvious, nevertheless CNMccontrol-oriented Cluster-based Network Modeling performs a sanity check, i.e., it is verified, whether the resulting trajectory in the ordered state is the same as the original trajectory. Note, that all the same 4 types of plots stated in section 8 are also available for visualizing the ordered state .
2. Calculating \(\boldsymbol A \, (\vec{\boldsymbol{\beta}})\) & best path \(\,(\vec{\boldsymbol{\beta}})\)
In the next sub-task the cost or similarity matrix \(\boldsymbol A(\vec{\beta})\) is calculated. First, the assignment problem shall be elaborated. Let \(\beta_1\) and \(\beta_2\) be two different model parameter values \(\beta_1 \neq \beta_2\) and both shall consist of \(K\) centroids. Each centroid is not only associated with a label but described fully with a position. The goal is to match each centroid from \(\beta_1\) to exactly one corresponding centroid from \(\beta_2\) such that the overall spatial distance is minimized. This idea was given as part of the definition of the term tracking itself. The difference between tracking and the assignment problem is that first, tracking solves the assignment problem multiple times and thus the assignment problem is only a part of tracking. Second, the tracked results are also feasible and transformed, which will be covered later in this subsection.
For construction an illustrative cost matrix \(\boldsymbol A(\vec{\beta})\), 3 pairwise different \(\beta\) values, \(\beta_1, \, \beta_2, \beta_3\) with \((\beta_1,\neq \beta_2) \neq \beta_3\) shall be considered. Again, each \(\beta_i\), where \(i = \{1,2,3\}\), consists of \(K\) centroid positions. The assignment problem is solved by exploiting SciPy (Virtanen et al. 2020). Its solution, e.g., for \(\beta_1\) and \(\beta_2\) only matches the centroids from the two different \(\beta\) such that the overall spatial distance is minimized. The addition of the spatial distances of \(\beta_1\) and \(\beta_2\) shall be designated as the cost value \(\beta_{i=1,j=2}\). With this level of understanding, the similarity matrix given in equation 9.2 can be read. \[ \begin{equation} \boldsymbol A_{3\times 3}\,(\vec{\beta}) = \begin{bmatrix} \beta_{1,1} & \beta_{1,2} & \beta_{1,3}\\ \beta_{2,1} &\beta_{2,2} & \beta_{2,3}\\ \beta_{3,1} & \beta_{3,2} &\beta_{3,3} \end{bmatrix} \label{eq_17_Dist_A} \end{equation} \tag{9.2}\]
Considering equation 9.3, if the assignment problem is solved for equal \(\beta \Rightarrow \beta_i = \beta_j\), the centroid positions overlap exactly. As a consequence, the distance between all the centroids across the two same \(\beta\) is zero. Further, adding up the zero spatial distances yields a cost of zero \(\beta_{i,i} = 0\). \[ \begin{equation} \begin{aligned} i &= j \\ \Rightarrow \beta_i &= \beta_j \\ \Rightarrow \beta_{i,j} &= \beta_{i,i} = 0 \end{aligned} \label{eq_18_Expl} \end{equation} \tag{9.3}\]
The cost matrix \(\boldsymbol A\,(\vec{\beta})\) compares each \(\beta_i\) with all the remaining \(\beta_j\), where \(i = \{1, \,2, \cdots, n_{\beta}\}, \; j = \{1, \,2, \cdots, n_{\beta}\}\) and \(n_{\beta}\) denotes the number of the pairwise different \(\vec{\beta}\). The outcome of each possible comparison \(\beta_i\) with \(\beta_j\) is a cost value representing a similarity between \(\beta_i\) and \(\beta_j\). Obviously, in the case trivial as described above \(\beta_i = \beta_j\), the similarity is maximized and the cost is minimized. To find the best path, i.e., proposed tracking results, the trivial entries on the diagonal entries must be prohibited. Obeying that the cost matrix \(\boldsymbol A\,(\vec{\beta})\) can be reformulated as equation 9.4 . Moreover, \(\boldsymbol A\,(\vec{\beta})\) is symmetrical, therefore computing one triangular part of the cost matrix is sufficient. The triangular part can be filled by mirroring along with the diagonal entries \(\beta_{i,i}\) as outlined for the lower triangular matrix in equation 9.4 . \[ \begin{equation} \boldsymbol A_{3\times 3}\,(\vec{\beta}) = \begin{bmatrix} \infty & \beta_{1,2} & \beta_{1,3}\\ \beta_{2,1} = \beta_{1,2} & \infty & \beta_{2,3}\\ \beta_{3,1} = \beta_{1,3} & \beta_{3,2} =\beta_{2,3} & \infty\\ \end{bmatrix} \label{eq_19} \end{equation} \tag{9.4}\]
The objective behind exploiting symmetry is to reduce computation time. Having defined the cost matrix \(\boldsymbol A\,(\vec{\beta})\) as given in equation 9.4, it can be used to again solve the assignment problem. Its output is denoted as path\(_O\,(\vec{\beta })\) in figure 9.4 .
3. Validity check
The sdfvalidity check can also be regarded as a feasibility investigation. To grasp what the feasibility constraint is table 9.1 (a) shall be analyzed .
| \(\boldsymbol{\beta_i}\) | \(\boldsymbol{\beta_j}\) |
|---|---|
| 1 | 2 |
| 2 | 3 |
| 3 | 4 |
| 4 | 5 |
| 5 | 6 |
| 6 | 7 |
| \(\boldsymbol{\beta_i}\) | \(\boldsymbol{\beta_j}\) |
|---|---|
| 1 | 2 |
| 2 | 3 |
| 3 | 6 |
| 4 | 7 |
| 5 | 4 |
| 6 | 5 |
| \(\boldsymbol{\beta_i}\) | \(\boldsymbol{\beta_j}\) |
|---|---|
| 1 | 2 |
| 2 | 1 |
| 3 | 5 |
| 4 | 6 |
| 5 | 7 |
| 6 | 3 |
Table 9.1— Examples for feasible and infeasible best tracking paths
It can be observed that in total the 7 model parameter values \((\vec{\beta}, \, n_{\beta}=7)\) were chosen. The overall goal is to provide one centroid label and get its corresponding centroid positions across all the 7 model parameter values \(\vec{\beta }\). Therefore, a feasible linking path, which allows the linking of all centroids of all \(\beta_i\) to all the other \(\beta_{\vec{j}}\) centroids, is required. The latter description shall be elaborated step-wise in the following. For instance, if the first \(\beta_i = 1\), a linking to the remaining \(\beta_{\vec{j}} = \{2, \, 3, \, 4, \, 5, \, 6, \, 7 \}\) is mandatory. The first item of table 9.1 (a) outlines that the centroids from \(\beta_i = 1\) are tracked with the centroids \(\beta_j=2\) . In other words, a clear relationship between the centroids across \(\beta_i = 1\) and \(\beta_j=2\) is established. Leveraging this relationship, the proper tracked centroid position across the two \(\beta = 1\) and \(\beta= 2\), are returned.
Because the centroid labels of \(\beta_i = 1\) are used as the reference to match the centroid labels of \(\beta_j=2\), the known linked path can be stated as \(L_{known}= \{1,\, 2\}\). The next model parameter value \(\beta_j = 3\) and it is tracked with \(\beta_i =2\). Since \(\beta_i =2\) is already incorporated in the known linked path, the known linking path can be extended to \(L_{known}= \{1,\, 2, \, 3\}\). The next model parameter value \(\beta_j = 4\) and its corresponding tracked counterpart is \(\beta_i =3\). Again, \(\beta_i =3\) is found in the known linked path, therefore the known linking path can be extended to \(L_{known}= \{1,\, 2, \, 3, \, 4\}\). The next model parameter value \(\beta_j = 5\) and its corresponding tracked \(\beta_i =4\) and so this procedure can be performed until the last \(\beta_j = 7\). Having completed the scheme, the known linking path is of full rank, i.e. with \(n_{\beta}= 7\) all the 7 pairwise different model parameter values \(\vec{\beta}\) are captured in the known linking path \(L_{known}\). The information gained through a full ranked \(L_{known, full}\) is that all centroids of all \(\beta_i\) are linked to all the other \(\beta_{\vec{j}}\) centroids.
After having introduced the full rank \(L_{known, full}\), the more straightforward definition for feasible linking path can be stated as follows. A feasible linking path is given when \(L_{known}\) has full rank \(L_{known, full}\). Direct feasible cases as shown in table 9.1 (a) are one way of feasible linking paths . Another, more general feasible case is provided in table 9.1 (b) . Here, up to \(\beta_i = 2\) and \(\beta_j = 3\) the scheme of the direct feasible linking path is followed. However, with \(\beta_i = 4\) and \(\beta_j = 7\) the obstacle that \(\beta_j = 7\) is not present in the current \(L_{known}= \{1,\, 2,\, 3,\, 6\}\), occurs. This issue can be circumvented by viewing \(\beta_i = 6\) and \(\beta_j = 5\). Since \(\beta_i = 6\) is in the current state of \(L_{known}= \{1,\, 2,\, 3,\, 6\}\), \(L_{known}\) can be extended with \(\beta_j = 5\), i.e., \(L_{known}= \{1,\, 2,\, 3,\, 5, \, 6\}\). Note, having acquired the relationship between \(\beta_i\) to \(\beta_j\) is the same as knowing the relationship between \(\beta_j\) to \(\beta_i\). Applying the newly added linking perspective, it can be seen that table 9.1 (b) also demonstrates a fulled ranked \(L_{known, full}\) or a feasible linking path .
In table 9.1 (c) an example for an incomplete linking path or an infeasible linking path is provided, where \(L_{known}\) has no full rank . The aim of the sub-task, validity, is to determine, whether the proposed optimized tracking path is feasible by extracting information about the rank of the final \(L_{known}\). Internally in CNMccontrol-oriented Cluster-based Network Modeling, this is achieved through logical queries utilizing mainly if statements. One major advantage which was not mentioned when the examples above were worked out is the following. \(\beta_{i,ref} = 1\) is not necessarily the best choice for being the reference. The reference \(\beta_{i,ref}\) is chosen such that it has the overall highest similarity or least cost to all the other \((n_{\beta} -1)\) available \(\vec{\beta}\). Hence, a feasible linking path with a lower sum of cost sum is generated.
This feature of a flexible reference is only providing better feasible linking paths, when the proposed optimized tracking path is infeasible, which in general is the case. Therefore, in most cases, it is advantageous to leverage the flexible reference. One of the outputs of CNMccontrol-oriented Cluster-based Network Modeling is the percentage cost savings that could be achieved with the flexible approach. In others, by what percentage could the costs be decreased when the flexible approach is compared with the rigid approach. In the rigid approach, \(\beta_{i,ref} = 1\) is chosen as the reference. Further, in the rigid approach, the \(\vec{\beta}\) are linked in increasing order, i.e. \(\beta_1\) with \(\beta_1\), \(\beta_2\) with \(\beta_2\), \(\beta_3\) with \(\beta_4\) and so on. Exploiting the flexible approach yields cost savings of around \(20\%\) to \(50\%\) An example of coping with a flexible reference is provided in the description of the following sub-step.
4. Truncate, final path
If the proposed optimized tracking path is feasible (feasible linking path), i.e. \(L_{known}\) has full rank \(L_{known, full}\), the truncation can be skipped. Consequently, the final path is the same as the proposed optimized tracking path. However, as mentioned, in general, this is not the expected case. Therefore, an example with an incomplete \(L_{known}\) shall be portrayed to explain the workflow with active truncation.
First, the final incomplete \(L_{known}\) will be used as the starting point. It will be filled until full rank is reached. Allowing a flexible reference \(\beta_{i,ref}\) the incomplete known linked path could be, e.g., \(L_{known} = \{3, \, 4, \, 5\}\). To get full rank, the remaining \(L_{missing} = \{1, \, 2, \, 6, \, 7\}\) are inferred through the following concept. The cost \(\beta_{i,j}\) between all \(L_{known}\) and \(L_{missing}\) are known through the cost matrix \(\boldsymbol A\,(\vec{\beta })\). The one \(\beta_j\) entry from \(L_{missing}\) which has the highest similarity or lowest cost \(\beta_{i,j}\) to the one entry \(\beta_j\) of the \(L_{known}\), is removed from \(L_{missing}\) and added to \(L_{known}\). Now, the same procedure can be applied to the modified \(L_{known}\) and \(L_{missing}\) until \(L_{missing}\) is empty and \(L_{known}\) has reached full rank. The inferred \(L_{known, full}\) is then used as the final path and sent to the next sub-task.
5. Transform
Once the final path is determined, it is known which \(\beta_i\) is linked to which \(\beta_j\). For all the \(\beta_{i},\, \beta_j\) matches in the final path, the linear sum assignment problem is solved again. Two illustrative solutions are provided in section 12. For further explanation, table 9.1 (b) shall be revisited . The first \(\beta_{i},\, \beta_j\) link is defined as \(\beta_i = 1\) and \(\beta_j = 2\). Moreover, for this scenario, it is assumed that \(\beta_i = \beta_{ref} = 1\). Therefore, the \(\beta_{i} = 1,\, \beta_j= 2\) is denoted as a direct match. In simpler terms, a direct pairwise \(\beta_{i},\, \beta_j\) relation, is obtained when \(\beta_i\) or \(\beta_j\) is directly traced back to the reference. For a pairwise direct \(\beta_{i},\, \beta_j\) link the transformation, i.e., relabeling without changing the dynamics of the system, as explained for the ordering sub-step, is applied directly and only once.
Now, considering the next \(\beta_{i},\, \beta_j\) match, i.e., \(\beta_i = 2\) and \(\beta_j = 3\). Linking the centroids from \(\beta_j = 3\) to \(\beta_i = 2\) directly would have no connection to the reference \(\beta_{ref} = 1\). Therefore, the solution to its linear sum assignment problem must experience the same transformations as \(\beta_i = 2\) did. In this case it is only the transformation caused by the \((\beta_i = 1,\,\beta_j = 2)\) match. The idea behind the transformation stays the same, however, if no direct relation is seen, respective multiple transformations must be performed. Once the final path has undergone all required transformations, the output is the desired tracked state. The output can be stored and plotted if desired. Some types of plots, which can be generated, will be shown in the section 12.
Finally, in short, the difference between first CNMc and this CNMccontrol-oriented Cluster-based Network Modeling version shall be mentioned. The proposed tracking algorithm is neither restricted to any dimension nor to a specific dynamical system. Thus, two major limitations of first CNMc could be removed in the current CNMccontrol-oriented Cluster-based Network Modeling version. Also, the flexible approach yields a better feasible linking path.