Iterative shrinking method for clustering problems
Pattern RecognitionPublished 23 November 2005
Pasi Fränti, Olli Virmajoki
Citations343
SJR quartileQ1
SJR score2.06
SNIP2.67
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
This work proposes an alternative to the merge-based approach to clustering by removing the clusters iteratively one by one until the desired number of clusters is reached, and applies local optimization strategy by always removing the cluster that increases the distortion the least.
Abstract
Agglomerative clustering generates the partition hierarchically by a sequence of merge operations. We propose an alternative to the merge-based approach by removing the clusters iteratively one by one until the desired number of clusters is reached. We apply local optimization strategy by always removing the cluster that increases the distortion the least. Data structures and their update strategies are considered. The proposed algorithm is applied as a crossover method in a genetic algorithm, and compared against the best existing clustering algorithms. The proposed method provides best performance in terms of minimizing intra-cluster variance.
Keywords
Computer Science
Journal of the American Statistical AssociationHierarchical Grouping to Optimize an Objective Function
19,236 Citations1963Joe H. Ward
Choice Reviews OnlineFinding groups in data: an introduction to cluster analysis
10,614 Citations1991
Cluster Analysis
9,195 Citations1974Barry J. Everitt, Sabine Landau +1 more
Springer series in information sciencesSelf-Organization and Associative Memory
8,770 Citations1989Teuvo Kohonen
IEEE Transactions on Pattern Analysis and Machine IntelligenceA Cluster Separation Measure
8,543 Citations1979David L. Davies, Donald W. Bouldin
A measure is presented which indicates the similarity of clusters which are assumed to have a data density which is a decreasing function of distance from a vector characteristic of the cluster which can be used to infer the appropriateness of data partitions.
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.
Vector Quantization and Signal Compression
7,039 Citations1992A. Gersho, Robert M. Gray
The author explains the design and implementation of the Levinson-Durbin Algorithm, which automates the very labor-intensive and therefore time-heavy and expensive process of designing and implementing a Quantizer.
Journal of CyberneticsA Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters
6,548 Citations1973J. C. Dunn
Two fuzzy versions of the k-means optimal, least squared error partitioning problem are formulated for finite subsets X of a general inner product space; in both cases, the extremizing solutions are shown to be fixed points of a certain operator T on the class of fuzzy, k-partitions of X, and simple iteration of T provides an algorithm which has the descent property relative to the least squarederror criterion function.
Springer series in information sciencesSelf-Organization and Associative Memory
3,820 Citations1988Teuvo Kohonen
Pattern RecognitionThe global k-means clustering algorithm
3,687 Citations2002Aristidis Likas, Nikos Vlassis +1 more
The global k-means algorithm is presented which is an incremental approach to clustering that dynamically adds one cluster center at a time through a deterministic global search procedure consisting of N executions of the k-Means algorithm from suitable initial positions.
Journal of the American Statistical AssociationHierarchical Grouping to Optimize an Objective Function
3,231 Citations1963Joe H. Ward
Springer eBooksSelf-organization and associative memory: 3rd edition
1,230 Citations1989T. Kohonen
This work prospectively examined the association between magnesium intake and incidence of Type 2 diabetes in a general Japanese population.
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Some new indexes of cluster validity
1,142 Citations1998James C. Bezdek, Nikhil R. Pal
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.
Pattern Recognition LettersA clustering algorithm using an evolutionary programming-based approach
122 Citations1997Manish Sarkar, B. Yegnanarayana +1 more
The proposed method is applicable for clustering tasks where clusters are crisp and spherical and determines the number of clusters and the cluster centers in such a way that locally optimal solutions are avoided.
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.
Pattern Analysis and ApplicationsRandomised Local Search Algorithm for the Clustering Problem
109 Citations2000Pasi Fränti, Juha Kivijärvi
This work introduces a new randomised local search algorithm for the clustering problem that is easy to implement, sufficiently fast, and competitive with the best clustering methods.
The Computer JournalGenetic Algorithms for Large-Scale Clustering Problems
92 Citations1997Pasi Fränti
This work considers the clustering problem in the case where the distances between elements are metric and both the number of attributes and thenumber of clusters are large, and introduces three new and efficient crossover techniques.
Pattern Recognition LettersGenetic algorithm with deterministic crossover for vector quantization
72 Citations2000Pasi Fränti
A new deterministic crossover method based on the pairwise nearest neighbor method is introduced that shows that high quality codebooks can be obtained within a few minutes instead of several hours as required by the previous GA-based methods.
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.
Journal of HeuristicsSelf-Adaptive Genetic Algorithm for Clustering
57 Citations2003Juha Kivijärvi, Pasi Fränti +1 more
A new self-adaptive GA is introduced that finds the parameter setup on-line during the execution of the algorithm and is able to find the most suitable combination of the available components.
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.
Optical EngineeringOn the splitting method for vector quantization codebook generation
40 Citations1997Pasi Fränti
A new iterative splitting method is proposed, which is applicable to codebook generation without the GLA and outperforms both theGLA and the other existing splitting-based algorithms.
Electronics LettersStochastic relaxation algorithm for improved vector quantiser design
38 Citations1989K. Zeger, A. Gersho
An easily implementable stochastic relaxation algorithm for vector quantisation design is given, which generalises the usual Lloyd iteration in codebook design by perturbing the computed entroids with independent multidimensional noise, whose variance diminishes as the algorithm progresses.
Optical EngineeringIterative split-and-merge algorithm for vector quantization codebook generation
36 Citations1998Pasi Fra ̈nti
Experimental results show that the proposed method performs well in comparison to other tested methods, including the generalized Lloyd algorithm (GLA) and two hier- archical methods.
IEEE Transactions on Circuits and Systems for Video TechnologyA clustering algorithm for entropy-constrained vector quantizer design with applications in coding image pyramids
18 Citations1995D.P. de Garrido, William A. Pearlman +1 more
Through simulations on synthetic sources, it is shown that ECPNN and ECVQ have indistinguishable mean-square-error versus rate performance and that the E CPNN and AECPNN algorithms obtain as close performance by the same measure as theECVQ and AecVQ algorithms.
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 - International Conference on Image ProcessingIterative shrinking method for generating clustering
7 Citations2003Olli Virmajoki, Pasi Fränti +1 more
This work proposes an alternative solution for the merge-based approach to pairwise nearest neighbor method by introducing an iterative shrinking method, which removes the clusters iteratively one by one until the desired number of clusters is reached.
Delta-MSE dissimilarity in GLA based vector quantization
4 Citations2004Mantao Xu
The delta-MSE dissimilarity measurement between training vectors and code vectors, based on the MSE distortion function, is proposed and generally achieves better performance than the L2 distance in constructing the codebook of vector quantization.