Modified K-Means Clustering Algorithm
Published 1 January 2008
Wei Li
Citations32
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 paper proposes an effective algorithm to compute new cluster centers for each iterative step for K-means clustering based on the optimization formulation of the problem and a novel iterative method.
Abstract
Performance of iterative clustering algorithms depends highly on the choice of cluster centers in each step. In this paper we propose an effective algorithm to compute new cluster centers for each iterative step for K-means clustering. This algorithm is based on the optimization formulation of the problem and a novel iterative method. The cluster centers computed using this methodology are found to be very close to the desired cluster centers, for iterative clustering algorithms. The experimental results using the proposed algorithm with a group of randomly constructed data sets are very promising.
Keywords
Computer Science
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 classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
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.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAn efficient k-means clustering algorithm: analysis and implementation
5,568 Citations2002Tapas Kanungo, David M. Mount +4 more
This work presents a simple and efficient implementation of Lloyd's k-means clustering algorithm, which it calls the filtering algorithm, and establishes the practical efficiency of the algorithm's running time.
Journal of the Royal Statistical Society Series A (General)Pattern Classification and Scene Analysis.
3,240 Citations1974Mairi Clarke, Richard O. Duda +1 more
Efficient and Effective Clustering Methods for Spatial Data Mining
1,788 Citations1994Raymond T. Ng, Jiawei Han
The analysis and experiments show that with the assistance of CLAHANS, these two algorithms are very effective and can lead to discoveries that are difficult to find with current spatial data mining algorithms.
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.
Refining Initial Points for K-Means Clustering
999 Citations1998Paul S. Bradley, Usama M. Fayyad
A procedure for computing a refined starting condition from a given initial one that is based on an efficient technique for estimating the modes of a distribution that allows the iterative algorithm to converge to a “better” local minimum.
Pattern Recognition LettersAn empirical comparison of four initialization methods for the K-Means algorithm
859 Citations1999José M. Peña, José A. Lozano +1 more
The results suggest that the Kaufman initialization method induces to the K-Means algorithm a more desirable behaviour with respect to the convergence speed than the random initialization method.
Journal of the American Statistical AssociationFinding the Number of Clusters in a Dataset
819 Citations2003Catherine A. Sugar, Gareth James
A simple, yet powerful nonparametric method for choosing the number of clusters based on distortion, a quantity that measures the average distance, per dimension, between each observation and its closest cluster center, is developed.
Pattern Recognition LettersCluster center initialization algorithm for K-means clustering
678 Citations2004Shehroz S. Khan, Amir Ahmad
An algorithm to compute initial cluster centers for K-means clustering based on two observations that some of the patterns are very similar to each other and that is why they have same cluster membership irrespective to the choice of initial cluster center.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA modified version of the K-means algorithm with a distance based on cluster symmetry
389 Citations2001Mu‐Chun Su, Chien-Hsing Chou
A modified version of the K-means algorithm is proposed that adopts a novel nonmetric distance measure based on the idea of "point symmetry" that can be applied in data clustering and human face detection.
Fuzzy Sets and SystemsFuzzy clustering with squared Minkowski distances
93 Citations2001Patrick J. F. Groenen, Krzysztof Jajuga
A new fuzzy clustering model based on a root of the squared Minkowski distance which includes squared and unsquared Euclidean distances and the L 1 -distance is presented and an algorithm is presented that is based on iterative majorization and yields a convergent series of monotone nonincreasing loss function values.
European Journal of Operational ResearchA mixed-integer programming approach to the clustering problem with an application in customer segmentation
91 Citations2005Burcu Sağlam, F. Sibel Salman +2 more
A heuristic approach is developed that improves computational times dramatically without compromising from optimality in most of the cases that were tested and indicates that this approach is computationally efficient and creates meaningful segmentation of data.
European Journal of Operational ResearchGreedy random adaptive memory programming search for the capacitated clustering problem
74 Citations2004Samad Ahmadi, Ibrahim H. Osman
The results show that GRAMPS has an efficient learning mechanism and is competitive with the existing methods in the literature.
Pattern Recognition LettersImage segmentation by unsupervised sparse clustering
27 Citations2006Byoung-Ki Jeon, Yun-Beom Jung +1 more
A novel solution of image segmentation based on positiveness by regarding the segmentation as one of the graph-theoretic clustering problems and obtaining sparsely clustered results which are closely related to human perception and thus the method is called sparse clustering.
Pattern RecognitionA novel approach to fuzzy clustering based on a dissimilarity relation extracted from data using a TS system
22 Citations2006Mario G. C. A. Cimino, Beatrice Lazzerini +1 more
This work proposes to exploit very few pairs of patterns with known Dissimilarity to build a TS system which models the dissimilarity relation, and shows that combining the TS system and the ARCA algorithm allows us to achieve high classification performance on a synthetic data set and on two real data sets.
Journal of Structural BiologyThe Kohonen self-organizing map: a tool for the clustering and alignment of single particles imaged using random conical tilt
17 Citations2004L. M. Zampighi, Christopher Kavanau +1 more
The Kohonen self-organizing map is used to align and classify images of channels obtained by random conical geometry into more homogeneous subsets and showed that both methods converged to stable classes exhibiting the same overall shapes for the cytoplasmic and external views of the channel.
Pattern Recognition LettersAn efficient line symmetry-based K-means algorithm
17 Citations2006Kuo‐Liang Chung, Keng-Sheng Lin
This paper presents a novel line symmetry-based K-means algorithm for clustering the data set with line symmetry property and based on some real data sets, experimental results demonstrate that this algorithm is rather encouraging.
Pattern Recognition LettersMaximum likelihood combination of multiple clusterings
15 Citations2006Tianming Hu, Ying Yu +2 more
Two combining methods based on the new similarity determined by the whole candidate set are presented and it is shown that they not only lead to a closer distance to the candidate set, but also achieve a smaller or comparable Distance to the true clustering.
European Journal of Operational ResearchTASC: Two-attribute-set clustering through decision tree construction
12 Citations2005Yen‐Liang Chen, Wu-Hsien Hsu +1 more
A new clustering algorithm is introduced, which partitions data space by constructing a decision tree using one attribute set, and measures the degree of similarity using another, and three different partitioning methods are presented.