Fast agglomerative clustering using information of k-nearest neighbors

In this paper, we develop a method to lower the computational complexity of pairwise nearest neighbor (PNN) algorithm. Our approach determines a set of candidate clusters being updated after each cluster merge. If the updating process is required for some of these clusters, k-nearest neighbors are f...

Full description

Saved in:
Bibliographic Details
Published in:Pattern recognition 2010-12, Vol.43 (12), p.3958-3968
Main Authors: Chang, Chih-Tang, Lai, Jim Z.C., Jeng, M.D.
Format: Article
Language:English
Subjects:
Agglomerative clustering
Algorithms
Applied sciences
Clusters
Coding, codes
Complexity
Computation
Computational efficiency
Computing time
Exact sciences and technology
Information, signal and communications theory
Mathematical analysis
Nearest neighbor
Sampling, quantization
Signal and communications theory
Signal representation. Spectral analysis
Signal, noise
Telecommunications and information theory
Vector quantization
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we develop a method to lower the computational complexity of pairwise nearest neighbor (PNN) algorithm. Our approach determines a set of candidate clusters being updated after each cluster merge. If the updating process is required for some of these clusters, k-nearest neighbors are found for them. The number of distance calculations for our method is O( N 2), where N is the number of data points. To further reduce the computational complexity of the proposed algorithm, some available fast search approaches are used. Compared to available approaches, our proposed algorithm can reduce the computing time and number of distance calculations significantly. Compared to FPNN, our method can reduce the computing time by a factor of about 26.8 for the data set from a real image. Compared with PMLFPNN, our approach can reduce the computing time by a factor of about 3.8 for the same data set.
ISSN:0031-3203
1873-5142
DOI:10.1016/j.patcog.2010.06.021