QFINCH: Quick hierarchical clustering using k-means and first neighbor relations
Jiajun Zhang, Geping Yang, Yiyang Yang, Juan Lu · 2024
This paper introduces QFINCH, a fast hierarchical clustering framework that leverages k-means and first neighbor relations of samples. QFINCH achieves a computational complexity of $\mathcal{O}(N\log (N))$ without the use of any index technology. We efficiently utilize k-means to construct an initial coarsened partition and employ the centers of the partitions as input for the first nearest neighbor merging. Additionally, we assign the true labels to samples in the coarse partition. Through experimental validation, we demonstrate the effectiveness of our algorithm and show that it significantly reduces time consumption. Finally, we assess the algorithm’s performance in various real-world large-scale datasets.