PAIRWISE NEAREST NEIGHBOR METHOD REVISITED
Olli Virmajoki · 2004
The pairwise nearest neighbor (PNN) method, also known as Ward's method belongs to the class of agglomerative clustering methods. The PNN method generates hierarchical clustering using a sequence of merge operations until the desired number of clusters is obtained. This method selects the cluster pair to be merged so that it increases the given objective function value least. The main drawback of the PNN method is its slowness because the time complexity of the fastest known exact implementation of the PNN method is lower bounded by O(N²), where N is the number of data objects. We consider several speed-up methods for the PNN method in the first publication. These methods maintain the precision of the method. Another method for speeding-up the PNN method is investigated in the second publication, where we utilize a k-neighborhood graph for reducing distance calculations and operations. A remarkable speed-up is achieved at the cost of slight increase in distortion. The PNN method can also be adapted for multilevel thresholding, which can be seen as