Eliminating Error Accumulation in Hierarchical Clustering Algorithms

Hierarchical agglomerative clustering treats given data as a singleton cluster at the outset and then successively merge (or agglomerate) pairs of clusters until all clusters have been merged into a single cluster that contains all data. However, if two data are merged incorrectly in the beginning, errors will be accumulated and amplified by the following iterations. Thus, we will get a worse cluster. In this paper, we propose an adaptive hierarchical agglomerative clustering algorithm called Agglomerative Network Clustering Algorithm (ANCA) adapted from Newman Rapid Algorithm Based on Heap (NRABH) to eliminate error accumulation in advance. It avoids the errors by re-computing the increment modularity to find the correct nodes that should be merged. The experiments show that the proposed algorithm avoids the accumulation of error and gets a better result.