Modified global -means algorithm for minimum sum-of-squares clustering problems
Pattern RecognitionPublished 12 April 2008
Adil Bagirov
Citations188
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
A new version of the global k-means algorithm, an incremental algorithm that dynamically adds one cluster center at a time and uses each data point as a candidate for the k-th cluster center, is proposed.
Abstract
k-Means algorithm and its variations are known to be fast clustering algorithms. However, they are sensitive to the choice of starting points and inefficient for solving clustering problems in large data sets. Recently, a new version of the k-means algorithm, the global k-means algorithm has been developed. It is an incremental algorithm that dynamically adds one cluster center at a time and uses each data point as a candidate for the k-th cluster center. Results of numerical experiments show that the global k-means algorithm considerably outperforms the k-means algorithms. In this paper, a new version of the global k-means algorithm is proposed. A starting point for the k-th cluster center in this algorithm is computed by minimizing an auxiliary cluster function. Results of numerical experiments on 14 data sets demonstrate the superiority of the new algorithm, however, it requires more computational time than the global k-means algorithm.
Keywords
Computer Science
Annals of EugenicsTHE USE OF MULTIPLE MEASUREMENTS IN TAXONOMIC PROBLEMS
14,727 Citations1936Ronald Aylmer Fisher
ACM Computing SurveysData clustering
13,184 Citations1999Anil K. Jain, M. Narasimha Murty +1 more
An overview of pattern clustering methods from a statistical pattern recognition perspective is presented, with a goal of providing useful advice and references to fundamental concepts accessible to the broad community of clustering practitioners.
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.
INFORMS Journal on ComputingTSPLIB—A Traveling Salesman Problem Library
2,570 Citations1991Gerhard Reinelt
This paper contains the description of a traveling salesman problem library (TSPLIB) which is meant to provide researchers with a broad set of test problems from various sources and with various properties.
Mathematical ProgrammingCluster analysis and mathematical programming
617 Citations1997Pierre Hansen, Brigitte Jaumard
Algorithms for hierarchical, partitioning, sequential, and additive clustering are studied, and emphasis is on solution methods, i.e., dynamic programming, graph theoretical algorithms, branch-and-bound, cutting planes, column generation and heuristics.
Pattern RecognitionA simulated annealing algorithm for the clustering problem
455 Citations1991Shokri Z. Selim, K. S. Al-Sultan
The simulated annealing approach for solving optimization problems is described and is proposed for solving the clustering problem and the parameters of the algorithm are discussed in detail and it is shown that the algorithm converges to a global solution of the clustered problem.
Pattern RecognitionClustering techniques: The user's dilemma
341 Citations1976Richard C. Dubes, Anil K. Jain
This paper examines eight clustering programs which are representative of the various available techniques and compare their performances from several points of view to set some guidelines for a potential user of a clustering technique.
Pattern RecognitionA Tabu search approach to the clustering problem
301 Citations1995Khaled S. Al‐Sultan
A new algorithm for solving the problem of clustering m objects into c clusters based on a tabu search technique is developed that compares favorably with both the k-means and the simulated annealing algorithms.
Journal of HeuristicsVariable Neighborhood Decomposition Search
291 Citations2001Pierre Hansen, Nenad Mladenović +1 more
The resulting two level VNS, called Variable Neighborhood Decomposition Search (VNDS), is presented and illustrated on the p-median problem and shows VNDS improves notably upon VNS in less computing time, and gives much better results than Fast Interchange (FI), in the same time that FI takes for a single descent.
Pattern RecognitionJ-Means: a new local search heuristic for minimum sum of squares clustering
255 Citations2001Pierre Hansen, Nenad Mladenović
J-M eans outperforms the other local search methods, quite substantially when many entities and clusters are considered, and fits into the variable neighborhood search metaheuristic framework.
IEEE Transactions on ComputersA Branch and Bound Clustering Algorithm
194 Citations1975Warren Koontz, P. M. Narendra +1 more
A clustering algorithm based on the branch and bound method of combinatorial optimization determines the globally optimum classification and is computationally efficient.
Studies in classification, data analysis, and knowledge organizationAdvances in Data Science and Classification
144 Citations1998Alfredo Rizzi, Maurizio Vichi +1 more
European Journal of Operational ResearchA new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems
115 Citations2004Adil Bagirov, John Yearwood
Results of numerical experiments have been presented which demonstrate the effectiveness of the proposed algorithm for solving the minimum sum-of-squares clustering problem based on nonsmooth optimization techniques.
SIAM Journal on Scientific ComputingAn Interior Point Algorithm for Minimum Sum-of-Squares Clustering
114 Citations1999O. du Merle, Pierre Hansen +2 more
An exact algorithm is proposed for minimum sum-of-squares nonhierarchical clustering, i.e., for partitioning a given set of points from a Euclidean m-space into a given number of clusters in order to minimize the sum of squared distances from all points to the centroid of the cluster to which they belong.
European Journal of Operational ResearchA comparison of two dual-based procedures for solving the p-median problem
111 Citations1985Pierre Hanjoul, Dominique Peeters
Two dual-based procedures for solving the p -median problem rely upon alternative Lagrangean relaxations of the problem and describe the algorithms and report on the computational experiments.
Pattern RecognitionA practical application of simulated annealing to clustering
99 Citations1992Donald E. Brown, Christopher L. Huntley
Simulated annealing is used to find a near-optimal partitioning with respect to each of several clustering criteria for a variety of simulated data sets, which can then be used to determine the “best” clustering criterion for the multi-sensor fusion problem with a given fusion operator.
TopUnsupervised and supervised data classification via nonsmooth and global optimization
94 Citations2003Adil Bagirov, A. M. Rubinov +2 more
This work examines various methods for data clustering and data classification that are based on the minimization of the so-called cluster function and its modications, which are nonsmooth and nonconvex.
SIAM Journal on Scientific and Statistical ComputingEvaluation of a Branch and Bound Algorithm for Clustering
60 Citations1985George Diehr
A branch and bound algorithm for optimal clustering is developed and applied to a variety of test problems and concludes that the method is practical for problems of up to 100 or so observations if the number of clusters is about 6 or less and the clusters are reasonably well separated.
Journal of ClassificationAnalysis of Global k-Means, an Incremental Heuristic for Minimum Sum-of-Squares Clustering
56 Citations2005Pierre Hansen, Eric W.T. Ngai +2 more
It is shown that global k-means cannot be guaranteed to find the optimum partition for any M ≥ 2 and d > 1; moreover, the same holds for all M > 3 if the new cluster center is chosen anywhere in R d instead of belonging to X.
Optimization and EngineeringA Global Optimization Approach to Classification
50 Citations2002Adil Bagirov, A. M. Rubinov +1 more
A method based on a combination of the cutting angle method and a local search is applied to the solution of the classification problem and it allows to solve classification problems for databases with an arbitrary number of classes.
Computers & ChemistryCluster analysis by simulated annealing
44 Citations1994Lixian Sun, YuLong Xie +3 more
The results show that the algorithm which guaranteed obtaining a global optimum compared favourably with the traditional hierarchical technique and K-means algorithm.
Studies in classification, data analysis, and knowledge organizationClustering and Neural Networks
43 Citations1998Hans‐Hermann Bock
This paper considers the usage of neural networks for the construction of clusters and classifications from given data and discusses, conversely, the use of clustering methods in neural network algorithms.