Fast and space efficient PNN algorithm with delayed distance calculations
Timo Kaukoranta, Pasi Fränti, Olli Nevalainen · 1998
Clustering of a data set can be done by the well-known Pairwise Nearest Neighbor (PNN) algorithm. The algorithm is conceptionally very simple and gives high quality solutions. A drawback of the method is the relatively large running time of the original (exact) implementation. Recently, an efficient version of the exact PNN algorithm has been introduced in literature. In this paper we give a faster implementation of this algorithm. The idea is to postpone the updating of the nearest neighbor information in order to reduce the number of cluster distance calculations. Correctness of the algorithm follows from the monotony of the cluster distances. Practical tests show that the new organization of the algorithm decreases the running time of PNN by ca. 35 per cent.