Abstract: Natural neighborhood graph can adaptively identify data with different shapes, sizes and dimensions. However, some small clusters cnnot be correctly identified by the algorithm when dealing with data of uneven density and complex structure. To address this issue, a hierarchical clustering algorithm based on natural neighborhood graph partitioning (HC-PNNG) is proposed. The algorithm first constructs a natural sparse graph using the natural neighbor relationship. Subsequently, it completes the hierarchical merging of natural sparse graphs based on the similarity between graphs, thereby achieving more universally applicable hierarchical clustering results. Comparative experiments were conducted on synthetic and real datasets, comparing the proposed algorithm with the latest clustering algorithms. The results demonstrate that the proposed algorithm significantly outperforms other clustering algorithms, verifying its effectiveness. 

Key words: clustering analysis, hierarchical clustering, natural neighborhood graph, graph partition- ing, similarity