Efficiency of random swap clustering
Journal Of Big DataPublished 21 March 2018Open access
Pasi Fränti
Citations82
SJR quartileQ1
SJR score1.98
SNIP4.17
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
The main results are that the expected time complexity of the random swap algorithm has (1) linear dependency on the number of data vectors, (2) quadratic dependency onThe number of clusters, and (3) inverse dependent on the size of neighborhood.
Abstract
Abstract Random swap algorithm aims at solving clustering by a sequence of prototype swaps, and by fine-tuning their exact location by k-means. This randomized search strategy is simple to implement and efficient. It reaches good quality clustering relatively fast, and if iterated longer, it finds the correct clustering with high probability. In this paper, we analyze the expected number of iterations needed to find the correct clustering. Using this result, we derive the expected time complexity of the random swap algorithm. The main results are that the expected time complexity has (1) linear dependency on the number of data vectors, (2) quadratic dependency on the number of clusters, and (3) inverse dependency on the size of neighborhood. Experiments also show that the algorithm is clearly more efficient than k-means and almost never get stuck in inferior local minimum.
Keywords
Computer Science
Journal of the Operational Research SocietyIntroduction to Algorithms
16,942 Citations1991V. J. Rayward‐Smith, Thomas H. Cormen +2 more
ACM Transactions on Mathematical SoftwareThe quickhull algorithm for convex hulls
5,343 Citations1996C. Bradford Barber, David Dobkin +1 more
This article presents a practical convex hull algorithm that combines the two-dimensional Quickhull algorithm with the general-dimension Beneath-Beyond Algorithm, and provides empirical evidence that the algorithm runs faster when the input contains nonextreme points and that it used less memory.
ACM Computing SurveysVoronoi diagrams—a survey of a fundamental geometric data structure
4,317 Citations1991Franz Aurenhammer
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.
Computational Geometry
3,606 Citations1985Franco P. Preparata, Michael Ian Shamos
This book clearly demonstrates that computational geometry in the plane is now a fairly well-understood branch of computer science and mathematics and points the way to the solution of the more challenging problems in dimensions higher than two.
X-means: Extending K-means with Efficient Estimation of the Number of Clusters
2,162 Citations2000Dan Pelleg, Andrew Moore
A new algorithm is introduced that eeciently, searches the space of cluster locations and number of clusters to optimize the Bayesian Information Criterion (BIC) or the Akaike Information Criteria (AIC) measure.
IEEE Transactions on Pattern Analysis and Machine IntelligenceK-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality
1,194 Citations1984Shokri Z. Selim, Mohamed A. Ismail
It is shown that under certain conditions the K-means algorithm may fail to converge to a local minimum, and that it converges under differentiability conditions to a Kuhn-Tucker point.
IEEE Transactions on Knowledge and Data EngineeringCLARANS: a method for clustering objects for spatial data mining
1,184 Citations2002Raymond T. Ng, Jiawei Han
A new clustering method is proposed, called CLARANS, whose aim is to identify spatial structures that may be present in the data, and two spatial data mining algorithms that aim to discover relationships between spatial and nonspatial attributes are developed.
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.
A local search approximation algorithm for k-means clustering
497 Citations2002Tapas Kanungo, David M. Mount +4 more
This work considers the question of whether there exists a simple and practical approximation algorithm for k-means clustering, and presents a local improvement heuristic based on swapping centers in and out that yields a (9+ε)-approximation algorithm.
Pattern RecognitionIterative shrinking method for clustering problems
343 Citations2005Pasi Fränti, Olli Virmajoki
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.
Pattern RecognitionClustering by competitive agglomeration
337 Citations1997Hichem Frigui, Raghu Krishnapuram
A new clustering algorithm called Competitive Agglomeration (CA), which minimizes an objective function that incorporates the advantages of both hierarchical and partitional clustering, is presented.
IEEE Transactions on Pattern Analysis and Machine IntelligenceFast Agglomerative Clustering Using a k-Nearest Neighbor Graph
308 Citations2006Pasi Fränti, Olli Virmajoki +1 more
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.
Computational GeometryA local search approximation algorithm for k-means clustering
291 Citations2004Tapas Kanungo, David M. Mount +4 more
IEEE Transactions on Knowledge and Data EngineeringSet Matching Measures for External Cluster Validity
187 Citations2016Mohammad Rezaei, Pasi Fränti
A new index called Pair Sets Index (PSI) is introduced based on the analytical comparisons of popular external indexes evaluated and compared when applied to clusterings of different data size, cluster size, and number of clusters.
Pattern RecognitionCentroid index: Cluster level similarity measure
121 Citations2014Pasi Fränti, Mohammad Rezaei +1 more
This paper introduces a cluster level index called centroid index, which is intuitive, simple to implement, fast to compute and applicable in case of model mismatch as well as to other clustering models beyond the centroid-based k-means.
Applied Mathematics and ComputationK-harmonic means data clustering with simulated annealing heuristic
113 Citations2006Zülal Güngör, Alper Ünler
A new algorithm for solving clustering problem based on a simulated annealing technique – simulatedAnnealing K-harmonic means clustering (SAKHMC) is developed and the experiment results illustrate the robustness of the SAKHMC clustering algorithm.
Information Processing LettersOn the geometry of similarity search: Dimensionality curse and concentration of measure
112 Citations2000Vladimir Pestov
It is suggested that the curse of dimensionality affecting the similarity-based search in large datasets is a manifestation of the phenomenon of concentration of measure on high-dimensional structures.
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.
Information SciencesA fast minimum spanning tree algorithm based on K-means
108 Citations2014Caiming Zhong, Mikko Malinen +2 more
A fast minimum spanning tree algorithm on the complete graph of N points that employs a divide-and-conquer scheme to produce an approximate MST with theoretical time complexity of O ( N 1.5) and the approximation is close to the exact MST so that in practical applications the performance does not suffer.
Neural Processing LettersThe LBG-U Method for Vector Quantization – an Improvement over LBG Inspired from Neural Networks
86 Citations1997Bernd Fritzke
It can be proved that LBG-U terminates in a finite number of steps, and experiments with artificial data demonstrate significant improvements in terms of RMSE over LBG combined with only modestly higher computational costs.
Pattern RecognitionA fast VQ codebook generation algorithm using codeword displacement
76 Citations2007Jim Z.C. Lai, Yi‐Ching Liaw +1 more
A fast codebook generation algorithm called CGAUCD (Codebook Generation Algorithm Using Codeword Displacement) is presented by making use of the codeword displacement between successive partition processes by implementing a fast search algorithm named MFAUPI for VQ encoding in the partition step of C GAUCD.
Annals of Operations ResearchA fast swap-based local search procedure for location problems
75 Citations2007Maurício G. C. Resende, Renato F. Werneck
This work presents a new implementation of a widely used swap-based local search procedure for the p-median problem, proposed in 1968 by Teitz and Bart, and shows that it can be significantly faster in practice.
BMC BioinformaticsMissing value imputation improves clustering and interpretation of gene expression microarray data
74 Citations2008Johannes Tuikkala, Laura L. Elo +2 more
The results demonstrate that, while missing values are still severely complicating microarray data analysis, their impact on the discovery of biologically meaningful gene groups can be reduced by using readily available and relatively fast imputation methods, such as the Bayesian Principal Components Algorithm (BPCA).
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.
Pattern RecognitionAutomatic clustering and boundary detection algorithm based on adaptive influence function
53 Citations2008Gleb V. Nosovskiy, Dongquan Liu +1 more
A new clustering and boundary detecting algorithm, ADACLUS, is proposed, based on the specially constructed adaptive influence function, and therefore, discovers clusters of arbitrary shapes and diverse densities, adequately captures clusters boundaries, and it is robust to noise.
Pattern RecognitionImprovement of the k-means clustering filtering algorithm
49 Citations2008Jim Z.C. Lai, Yi‐Ching Liaw
A modified filtering algorithm (MFA) by making use of center variations to speed up clustering process and can generate the same clusters as that produced by hard k-means clustering.
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.
Pattern RecognitionTabu search algorithm for codebook generation in vector quantization
40 Citations1998Pasi Fränti, Juha Kivijärvi +1 more
The proposed algorithm first makes non-local changes to the codebook which is then fine-tuned by the generalized Lloyd algorithm, and for a set of gray-scale images, the new algorithm was better than GLA alone, and its results were comparable to simulated annealing.
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 Information TheoryOn convergence of Lloyd's method I
29 Citations1992Xiaolin Wu
This correspondence proves that Lloyd's method I converges for a large class of error measures, if the density function is continuous, positive, and defined on a finite interval.
Lecture notes in computer scienceXNN Graph
22 Citations2016Pasi Fränti, Radu Mariescu-Istodor +1 more
This work introduces an alternative data structure called XNN, which has variable number of neighbors and guarantees connectivity of the graph, and demonstrates that the graph provides improvement over KNN in several applications including clustering, classification and data analysis.
Lecture notes in computer scienceA Comparison of Categorical Attribute Data Clustering Methods
11 Citations2014Ville Hautamäki, Antti Pöllänen +4 more
A novel clustering algorithm is designed based on local search for this objective function and compared against six existing algorithms on well known data sets to provide better clustering quality than the other iterative methods at the cost of higher time complexity.
Statistical Analysis and Data Mining The ASA Data Science JournalA general framework for efficient clustering of large datasets based on activity detection
8 Citations2010Xin Jin, Sang Kyum Kim +3 more
A framework General Activity Detection (GAD) for fast clustering on large‐scale data based on center activity detection is proposed and the proposed algorithms within the framework can achieve very high speed.
BiosystemsMinimizing stochastic complexity using local search and GLA with applications to classification of bacteria
7 Citations2000Pasi Fränti, Helge Gyllenberg +5 more
The two iterative clustering methods produce similar classifications but they merge certain natural classes with microbiological relevance in different ways.
Deterministic and randomized local search algorithms for clustering
5 Citations2008Pasi Fränti, Marko Tuononen +1 more
A local search algorithm for clustering based on deterministic variants of cluster swapping that finds the correct clustering more efficiently than existing ones within a given time limit.
Legend based elevation layers extraction from a color-coded relief scanned map
1 Citations2005Clara Rus, Jaakko Astola
This paper presents an approach to extract the elevation layers from a color-coded relief scanned map having as an input information the colors provided by the map's legend, working in the CIE L*u*v* color space.