Fast Agglomerative Clustering Using a k-Nearest Neighbor Graph

By Pasi Fränti, Olli Virmajoki, Ville Hautamäki. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006

307 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors (2016, methodology): “The synthetic datasets used come from research published in [3,10,11,13,14,27] and are commonl used benchmark datasets to test the performance of clustering algorithms.”
DBSVEC: Density-Based Clustering Using Support Vector Expansion (2019, methodology): “Next, we examine the accuracy of DBSVEC on other open datasets from different domains including Seeds [33], Dim32 and Dim64 [34], Map-Joensuu and MapFinland5, D31 [35], Breast-Cancer [33], Miss-America [36], House [36], t4.”
How much can k-means be improved by using better initialization and repeats? (2019, background): “A faster O( N log N ) time variant also exists [47] but it is significantly more complex to implement and requires to calculate k-near neighbors (KNN).”
Fast Approximate kNN Graph Construction for High Dimensional Data via Recursive Lanczos Bisection (2009, background): “Fränti et al. (2006) proposed, at each iteration, to maintain the kNN graph of the clusters, and merge two clusters that are the nearest neighbors in the graph.”
Balanced K-Means for Clustering (2014, background): “To get better results than in k-means, slower agglomerative algorithms [10,13,12] or more complex k-means variants [3,11,21,18] are sometimes used.”