Fast Agglomerative Clustering Using a k-Nearest Neighbor Graph
IEEE Transactions on Pattern Analysis and Machine IntelligencePublished 29 September 2006
Pasi Fränti, Olli Virmajoki, Ville Hautamäki
Citations308
SJR quartileQ1
SJR score3.91
SNIP5.99
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A fast agglomerative clustering method using an approximate nearest neighbor graph for reducing the number of distance calculations and a relatively small neighborhood size is sufficient to maintain the quality close to that of the full search.
Abstract
We propose a fast agglomerative clustering method using an approximate nearest neighbor graph for reducing the number of distance calculations. The time complexity of the algorithm is improved from O(tauN2) to O(tauNlogN) at the cost of a slight increase in distortion; here, tau denotes the number of nearest neighbor updates required at each iteration. According to the experiments, a relatively small neighborhood size is sufficient to maintain the quality close to that of the full search.
Keywords
Computer Science
Journal of the American Statistical AssociationHierarchical Grouping to Optimize an Objective Function
19,236 Citations1963Joe H. Ward
Journal of the Operational Research SocietyIntroduction to Algorithms
16,942 Citations1991V. J. Rayward‐Smith, Thomas H. Cormen +2 more
IEEE Transactions on CommunicationsAn Algorithm for Vector Quantizer Design
7,183 Citations1980Y. Linde, A. Buzo +1 more
An efficient and intuitive algorithm is presented for the design of vector quantizers based either on a known probabilistic model or on a long training sequence of data.
American Mathematical MonthlySphere Packings, Lattices and Groups.
3,443 Citations1989H. S. M. Coxeter, J. H. Conway +1 more
Journal of the American Statistical AssociationHierarchical Grouping to Optimize an Objective Function
3,231 Citations1963Joe H. Ward
ACM Transactions on Mathematical SoftwareAn Algorithm for Finding Best Matches in Logarithmic Expected Time
2,765 Citations1977Jerome H. Friedman, Jon Bentley +1 more
Grundlehren der mathematischen WissenschaftenSphere Packings, Lattices and Groups
2,137 Citations1999J. H. Conway, N. J. A. Sloane
ComputerChameleon: hierarchical clustering using dynamic modeling
2,102 Citations1999George Karypis, Eui-Hong Han +1 more
Chameleon's key feature is that it accounts for both interconnectivity and closeness in identifying the most similar pair of clusters, which is important for dealing with highly variable clusters.
Journal of the Royal Statistical Society Series C (Applied Statistics)Minimum Spanning Trees and Single Linkage Cluster Analysis
1,233 Citations1969J. C. Gower, G. J. Ross
Minimum spanning trees (MST) and single linkage cluster analysis (SLCA) are explained and it is shown that all the information required for the SLCA of a set of points is contained in their MST.
MicrobiologyThe Application of Computers to Taxonomy
936 Citations1957P. H. A. Sneath
A method is described for handling large quantities of taxonomic data by an electronic computer so as to yield the outline of a classification based on equally weighted features that enables Similarity to be expressed numerically, and would allow taxonomic rank to be measured in terms of it.
Data Mining and Knowledge DiscoveryBIRCH: A New Data Clustering Algorithm and Its Applications
882 Citations1997Tian Zhang, Raghu Ramakrishnan +1 more
An efficient and scalable data clustering method is proposed, based on a new in-memory data structure called CF-tree, which serves as an in- memory summary of the data distribution, and implemented in a system called BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies), and compared with other available methods.
IEEE Transactions on Acoustics Speech and Signal ProcessingA new vector quantization clustering algorithm
405 Citations1989W. Equitz
The pairwise nearest neighbor (PNN) algorithm is presented as an alternative to the Linde-Buzo-Gray (1980, LBG) (generalized Lloyd, 1982) algorithm for vector quantization clustering.
AlgorithmicaRefinements to nearest-neighbor searching ink-dimensional trees
348 Citations1991Robert F. Sproull
This note presents a simplification and generalization of an algorithm for searchingk-dimensional trees for nearest neighbors reported by Friedmanet al [3], which can be generalized to allow a partition plane to have an arbitrary orientation, rather than insisting that it be perpendicular to a coordinate axis, as in the original algorithm.
Journal of the ACMSeparators for sphere-packings and nearest neighbor graphs
223 Citations1997Gary L. Miller, Shang‐Hua Teng +2 more
This result implies that every triangulated planar graph is isomorphic to the intersection graph of a disk-packing, which gives a new geometric proof of the planar separator theorem of Lipton and Tarjan, but also generalizes it to higher dimensions.
IEEE Transactions on Circuits and Systems II Analog and Digital Signal ProcessingA fast mean-distance-ordered partial codebook search algorithm for image vector quantization
179 Citations1993Sung-Woong Ra, J.-K. Kim
A new fast search algorithm for vector quantization using the mean of image vectors is proposed, showing that the number of calculations can be reduced to as low as a fourth the number achievable by an algorithm known as the partial distance method.
Pattern RecognitionAn efficient agglomerative clustering algorithm using a heap
122 Citations1991Takio Kurita
An efficient algorithm for agglomerative clustering using a heap in which distances of all pairs of clusters are stored and updating the heap at each stage of the hierarchy is easily implemented.
Clustering spatial data using random walks
76 Citations2001David Harel, Yehuda Koren
IEEE Transactions on Image ProcessingA fast exact GLA based on code vector activity detection
68 Citations2000Timo Kaukoranta, Pasi Fränti +1 more
A new method for reducing the number of distance calculations in the generalized Lloyd algorithm (GLA), which is a widely used method to construct a codebook in vector quantization, that utilizes reduced comparison search and calculates distances only to the active code vectors.
IEEE Transactions on Image ProcessingFast and memory efficient implementation of the exact PNN
64 Citations2000Pasi Fränti, Timo Kaukoranta +2 more
This paper proposes a fast O(tauN2) time implementation of the exact PNN, where tau is shown to be significantly smaller than N, and gives the time complexity of the algorithm both in the best case and in the worst case.
IEEE Transactions on Image ProcessingOn the computational complexity of the LBG and PNN algorithms
42 Citations1997Jamshid Shanbehzadeh, Philip Ogunbona
It is shown that for a practical codebook size and training vector sequence, the Linde-Buzo-Gray algorithm is indeed more computationally efficient than the PNN algorithm.
Pattern RecognitionAn automatic shape independent clustering technique
26 Citations2003Sanghamitra Bandyopadhyay
A clustering technique that can automatically detect any number of well-separated clusters which may be of any shape, convex and/or non-convex, and is able to indicate the inherent hierarchical nature of the clusters present in a data set is described.
Journal of Electronic ImagingFast pairwise nearest neighbor based algorithm for multilevel thresholding
23 Citations2003Olli Virmajoki
A fast pairwise nearest neighbor (PNN)- based O(N log N) time algorithm for multilevel nonparametric thresh- olding, where N denotes the size of the image histogram, which is applicable in real-time image processing applications.
Fast PNN-based clustering using k-nearest neighbor graph
18 Citations2004Pasi Fränti, Olli Virmajoki +1 more
This work proposes the use of nearest neighbor graph for reducing the number of candidates within agglomerative clustering algorithm known as the PNN algorithm.
Optical EngineeringVector quantization by lazy pairwise nearest neighbor method
17 Citations1999Timo Kaukoranta
A faster implementation of the Pairwise Nearest Neighbor (PNN) algorithm to postpone the updating of the nearest neighbor information in order to reduce the number of cluster distance calculations.
Optical EngineeringPractical methods for speeding-up the pairwise nearest neighbor method
12 Citations2001Olli Virmajoki
It is shown that the run time of the pairwise nearest neighbor method can be reduced to 10 to 15% that of the original method for data sets in color quantization and in spatial vector quantization.
Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004.Divide-and-conquer algorithm for creating neighborhood graph for clustering
5 Citations2004Olli Virmajoki, Pasi Fränti
A fast divide-and-conquer method for graph creation based on the algorithm previously used in the closest pair problem is developed and applied to agglomerative clustering, in which it outperforms previous projection-based algorithm for high dimensional spatial data sets.