A novel travel-time based similarity measure for hierarchical clustering

• Using the travel-time based similarity measure can improve both the robustness and the quality of hierarchical clustering.
• Using the travel-time based similarity measure results in a more narrow similarity distribution within a cluster.
• Compared to other hierarchical clustering methods, the proposed TTHC method produces competitive and promising clustering results.

The similarity measure plays an important role in agglomerative hierarchical clustering. Following the idea of gravitational clustering which treats all the data points as mass points under a hypothetical gravitational force field, we propose a novel similarity measure for hierarchical clustering. The similarity measure is based on the estimated travel time between data points under the gravitational force field: the shorter the travel time from one point to another, the larger the similarity between the two data points. To simplify the computation, the travel time between a pair of data points is estimated using the potential field produced by all the data points. Based on the new similarity measure, we also propose a new hierarchical clustering method called Travel-Time based Hierarchical Clustering (TTHC). In the TTHC method, an edge-weighted tree of all the data points is first built using the travel-time based similarity measure, and then the clustering results are derived from the edge-weighted tree directly. To evaluate the proposed TTHC method, it is compared with four other hierarchical clustering methods on six real datasets and two synthetic dataset families composed of 200 datasets. The experiments show that using the travel-time based similarity measure can improve both the robustness and the quality of hierarchical clustering.