# Ensemble Clustering in GPS Velocities: A Case Study of Turkey
## 2 Data and Methodology
### Generation Mechanisms
#### 2.3.4 Hierarchical Agglomerative Clustering  
HAC methods aim to combine the objects by taking into account the similarities (velocity vector in this study) in a data set at certain levels (distance measures). Differing from the partitioning clustering methods such as \(k\)-means, there is no need to determine the number of clusters beforehand in the HAC method [15; 38].  
With HAC, each object or each velocity observation is initially considered as a set. In short, if there are \(n\) velocity vectors in the data set, there are initially \(n\) clusters at the first step. Then the two closest clusters (with the smallest \(d_{ij}\) value) are merged and assembled in a new cluster. So, now \(n-1\) clusters are obtained and iterated distances matrix is calculated. The process is repeated \(n-1\) time and finally, the last two clusters are merged to form a single cluster containing all vectors. All these operations are based on grouping objects into tree structures known as a dendrogram. It is used to explore the relationship between each object in a \"bottom-up continuation\" of grouping results. In the dendrogram tree or chart, the distances between merged clusters are shown (Figure 3).  
At this point, the higher the distance between the merged clusters, the clearer the distinction between them [15]. By visual inspection of the dendrogram, it is possible to decide where to cut the cluster tree which results in natural groupings and/or to determine the optimum number of clusters. In Figure 3, the flower chart dendrogram of HAC clustering of GPS velocities (from \(k\) = 2 to 5) is constructed using squared-Euclidean distance and ward linkage.  
At the hierarchical clustering procedure, distance calculations and (dis)similarity between objects in the data set are updated at each iteration. The matrix of calculated  
Figure 3: The dendrogram of the hierarchical agglomerative clustering in the form of a flower chart.  
distance/(dis)similarity values is the basis for using the selected linkage criterion. To decide which objects/clusters should be merged, methods to measure the similarity between them are needed. Several distance metrics such as squared Euclidean, Manhattan, Cosine and Minkowski, etc., are used depending on different data sets and the purpose of the study. Note that the squared Euclidean and Manhattan distances consider both the orientation and magnitude of the velocity vectors in clustering GPS velocities, unlike, e.g., cosine, which treats all velocities as unit vectors. On the other hand, a linkage criterion is used to define the proximities of pairs of objects into clusters based on their similarity. In particular, various linkage criteria are used for this purpose: (1) Single or minimum (nearest neighbor); (2) Average or mean (unweighted pair group method with arithmetic mean); (3) Complete (farthest neighbor); (4) Weighted (weighted pair group method with arithmetic mean); (5) Centroid; (6) Median; and (7) [PERSON]'s minimum variance method [39]. For instance, [PERSON] et al. [10] and [PERSON] et al. [16] used the centroid linkage approach to join GPS velocity clusters. It is important to note that the last three of these criteria as mentioned above require Euclidean distances for geometric precision in the calculation of the centers and it is not appropriate to use the Manhattan distance in combination with these.