# Estimating Road Segments Using Kernelized Averaging of GPS Trajectories
## 4 Experimentation  
The experimentation was carried out using the training dataset provided by the Averaging GPS segments competition setup [14] at University of Eastern Finland ([[https://cs.uef.fi/sipu/segments/](https://cs.uef.fi/sipu/segments/)]([https://cs.uef.fi/sipu/segments/](https://cs.uef.fi/sipu/segments/))). It consisted in estimating a cleaned GPS trajectory segment given a set of GPS trajectories corresponding to the same segment. Only training data corresponding to a set of road segments were delivered along with ground truth trajectory for each considered road segments. Figure 5: iTEKA centroid estimate (in red) before pruning (**left**) and after pruning (**right**). The blue lines represent trained data, i.e. measured GPS trajectories corresponding to a street segment. The x,y coordinates are latitude and longitude converted in UTM coordinates then normalized in \([0;1]\). It is important to note that the assessment measure used to evaluate the competing approaches was not explicitly provided. However, on the training data, the challenge site makes it possible to obtain the average value of the assessment measure obtained by a given method by submitting the set of solution trajectories produced by this method. We show below that this unknown assessment measure used to rank the competing methods is not strongly correlated to a RMSE measure between an estimated trajectory and the corresponding ground truth trajectory. The assessment measure (as we learned once the challenge was closed) is referred to as HC-SIM, a hierarchical version of the C-SIM measures described in [2]. The C-SIM measure is based on the notion of grid which partition the 2D space in contiguous cells of 25 m\({}^{2}\). To compare two trajectories, the Jaccard index was evaluated by performing the ratio of the common cells shared by the two trajectories with the union of the cells traversed by the two trajectories. To avoid the effect of the discretization of the grid, the trajectories were slightly dilated, which had the effect of enlarging a bit of the trajectories by adding some of the adjacent cells. The HC-SIM (H for hierarchical) measurement was derived from the C-SIM measure by varying the size of the cells and providing a weighted average as output. The details of this measure have not yet been published by the authors. However, as mentioned above, an evaluation program allowed producing the results presented below. The HC-SIM measure gives a percentage of similarity between two trajectories (hence, it varies in \([0,100\%]\)). We evaluated eight approaches: (i) four medoid based models, namely Euclidean, DTW, \(\mathcal{K}_{\text{rdtw}}\) and soft-DTW with medoid; and (ii) four centroid based models, namely Euclidean, DBA, soft-DTW and iTEKA centroid methods. All approaches shares the \(T\) meta parameter, which defines the size of the resample trajectories. In addition, \(\mathcal{K}_{\text{rdtw}}\), iTEKA as well as the soft-DTW medoid and centroid methods require the set-up of two meta parameters, \(\
u\) and \(\gamma\), respectively, the bandwidth of the local kernel parameter (Equation (4)) and \(T\), the length of the trajectories, once they have been resampled after the second preprocessing step. For all methods, these meta parameters were varied for all training sets of trajectories simultaneously, such as maximizing the HC-SIM measure obtained by the centroid estimates. We first selected \(\
u\) and \(\gamma\) in the discrete set \(\{.1.,\)\(5\), \(1\), \(2\), \(3\), \(4\), \(5\), \(6\), \(7\), \(8\), \(9\), \(10\), \(11\), \(12\), \(13\), \(14\), \(15\), \(16\), \(17\), \(18\), \(19\), \(20\}\) while \(T\) value was selected within \(\{100,200,300\}\). According to Figure 6, the meta parameters \(\
u\) and \(T\) are correlated for the iTEKA algorithm. On the training data, a simple grid search led to selecting \(\
u=6\) and \(T=200\), which allowed reaching a HC-SIM of 68.5%. Similarly, according to Figure 7, the meta parameters \(\gamma\) and \(T\) are correlated for the soft-DTW centroid.