Fast PNN-based clustering using k-nearest neighbor graph
Pasi Fränti, Olli Virmajoki, Ville Hautamäki · 2004
Search for nearest neighbor is the main source of computation in most clustering algorithms. We propose the use of nearest neighbor graph for reducing the number of candidates. The number of distance calculations per search can be reduced from O(N) to O(k) or where N is the number of clusters, and k is the number of neighbors in the graph. We apply the proposed scheme within agglomerative clustering algorithm known as the PNN algorithm.