Improvement of the fast exact pairwise-nearest-neighbor algorithm
Improvement of the fast exact pairwise-nearest-neighbor algorithm
复制标题
DOI：
10.1016/j.patcog.2008.10.001
复制
发表时间：
2009-05-01
影响因子：
8
通讯作者：
Liaw, Yi-Ching
中科院分区：
文献类型：
--
作者：
Liaw, Yi-Ching
成对最近邻（PNN）是一种有效的数据聚类方法，它总是能产生良好的聚类结果，但计算复杂度较高。Franti等人提出的快速精确概率神经网络（FPNN）算法是一种有效的提高概率神经网络（PNN）速度的方法，并且可以产生与概率神经网络（PNN）相同的聚类结果。本文提出了一种改进FPNN算法的新方法。我们的算法使用的属性，簇的距离增加的聚类合并过程中进行，并采用快速搜索算法拒绝不可能的候选簇。实验结果表明，该方法能有效减少FPNN算法的距离计算次数和计算时间。与FPNN相比，我们提出的方法可以减少计算时间和距离计算的数量分别由一个因素的24.8和146.4，从三个真实的图像的数据集。值得注意的是，我们的方法产生相同的聚类结果所产生的PNN和FPNN。(C)2008爱思唯尔有限公司保留所有权利。
Pairwise-nearest-neighbor (PNN) is an effective method of data clustering, which can always generate good clustering results, but with high computational complexity. Fast exact PNN (FPNN) algorithm proposed by Franti et al. is an effective method to speed up PNN and generates the same Clustering results as those generated by PNN. In this paper, We present a novel method to improve the FPNN algorithm. Our algorithm uses the property that the cluster distance increases as the cluster merge process proceeds and adopts a fast search algorithm to reject impossible candidate clusters. Experimental results show that Our proposed method can effectively reduce the number of distance calculations and computation time of FPNN algorithm. Compared with FPNN, Our proposed approach can reduce the computation time and number of distance calculations by a factor of 24.8 and 146.4, respectively, for the data set from three real images. It is noted that our method generates the same clustering results as those produced by PNN and FPNN. (C) 2008 Elsevier Ltd. All rights reserved.