Hierarchical Agglomerative Clustering Algorithm with Equilateral Orthogonal Grid

The process of the typical algorithm of hierarchical agglomerative clustering (HAC) reflects the multi-scale property of studying data, which is crucial in the research of Geography, Cartography and Remote Sensing. However, the typical algorithm is inefficient and costs too much memory space. In this paper, considering the transitivity of distances among points, the studying data are divided into equilateral orthogonal grids to avoid redundant computation; moreover, the feasibility of the proposed algorithm is proved in theory and extended to N-dimensional space. The proposed algorithm follows the same single-link clustering rule as the typical algorithm; and therefore, it generates the same multi-scale clustering series as the typical algorithm. Since there is no distance-matrix, the proposed algorithm costs much less memory space. Experimental results show that although without any manual intervention and distance-matrix, the proposed algorithm obviously improves the efficiency of HAC. However, the advantage decreases as the extending of the dimension number.