An Examination of Procedures for Determining the Number of Clusters in a Data Set
PsychometrikaPublished 1 June 1985
Glenn W. Milligan, Martha C. Cooper
Citations3,870
SJR quartileQ1
SJR score1.90
SNIP2.06
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 Monte Carlo evaluation of 30 procedures for determining the number of clusters was conducted on artificial data sets which contained either 2, 3, 4, or 5 distinct nonoverlapping clusters to provide a variety of clustering solutions.
Abstract
A Monte Carlo evaluation of 30 procedures for determining the number of clusters was conducted on artificial data sets which contained either 2, 3, 4, or 5 distinct nonoverlapping clusters. To provide a variety of clustering solutions, the data sets were analyzed by four hierarchical clustering methods. External criterion measures indicated excellent recovery of the true cluster structure by the methods at the correct hierarchy level. Thus, the clustering present in the data was quite strong. The simulation results for the stopping rules revealed a wide range in their ability to determine the correct number of clusters in the data. Several procedures worked fairly well, whereas others performed rather poorly. Thus, the latter group of rules would appear to have little validity, particularly for data sets containing distinct clusters. Applied researchers are urged to select one or more of the better criteria. However, users are cautioned that the performance of some of the criteria may be data dependent.
Keywords
Computer Science
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
Cluster Analysis
9,195 Citations1974Barry J. Everitt, Sabine Landau +1 more
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.
Communications in StatisticsA dendrite method for cluster analysis
6,686 Citations1974T. Calinski, J. Harabasz
A method for identifying clusters of points in a multidimensional Euclidean space is described and its application to taxonomy considered and an informal indicator of the "best number" of clusters is suggested.
PsychometrikaHierarchical Clustering Schemes
4,891 Citations1967S. C. Johnson
A useful correspondence is developed between any hierarchical system of such clusters, and a particular type of distance measure, that gives rise to two methods of clustering that are computationally rapid and invariant under monotonic transformations of the data.
Journal of the Royal Statistical Society Series A (General)Pattern Classification and Scene Analysis.
3,240 Citations1974Mairi Clarke, Richard O. Duda +1 more
Principles of Numerical Taxonomy
3,005 Citations2013
PsychometrikaWho Belongs in the Family?
2,003 Citations1953Robert L. Thorndike
I was sitting before my TV set, a while back, watching Captain Video and pondering the organizational problems of psychologists, psychometricians, psychodiagnosticians, psycho-somatists, psychosomnabulists, and psychoceramics, and decided to enlist Captain Video's help to bring me from the Black Planet that superogalactian hypermetrician, Dr. Idnozs HcahscrorTenib, cosmos-famous disc
PsychometrikaAn Examination of the Effect of Six Types of Error Perturbation on Fifteen Clustering Algorithms
1,170 Citations1980Glenn W. Milligan
An evaluation of several clustering methods indicated that the hierarchical methods were differentially sensitive to the type of error perturbation and two alternative starting procedures for the nonhierarchical methods produced greatly enhanced cluster recovery and were found to be robust to all of the types of error examined.
The Computer JournalHierarchical grouping methods and stopping rules: an evaluation
952 Citations1977Richard Mojena
Journal of MammalogyPrinciples of Numerical Taxonomy
937 Citations1965Charles A. Long, Robert R. Sokal +1 more
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)ISODATA, A NOVEL METHOD OF DATA ANALYSIS AND PATTERN CLASSIFICATION
923 Citations1965Geoffrey H. Ball, David J. Hall
ISODATA, a novel method of data analysis and pattern classification, is described in verbal and pictorial terms, in terms of a two-dimensional example, and by giving the mathematical calculations that the method uses.
Multivariate Behavioral ResearchPATTERN CLUSTERING BY MULTIVARIATE MIXTURE ANALYSIS
604 Citations1970J. H. Wolfe
The maximum-likelihood theory and numerical solution techniques are developed for a fairly general class of distributions and the feasibility of the procedures is demonstrated by two examples of computer solutions for normal mixture models of the Fisher Iris data and of artify generated clusters with unequal covariance matrices.
BiometricsA Method for Cluster Analysis
577 Citations1965A. W. F. Edwards, L. L. Cavalli‐Sforza
A method for investigating the relation of points in multidimensional space using an analysis of variance technique, and the pTocess repeated sequentially so that a tree diagram is formed.
Journal of the American Statistical AssociationOn Some Invariant Criteria for Grouping Data
571 Citations1967Herman Friedman, Jerrold Rubin
This paper attacks the problem of exploring the structure of multivariate data in search of “clusters” by using a computer procedure to obtain the “best” partition of n objects into g groups.
PsychometrikaA Monte Carlo Study of Thirty Internal Criterion Measures for Cluster Analysis
410 Citations1981Glenn W. Milligan
Results indicated that a subset of internal criterion measures could be identified which appear to be valid indices of correct cluster recovery and could form the basis of a permutation test for the existence of cluster structure or a clustering algorithm.
Pattern RecognitionValidity studies in clustering methodologies
300 Citations1979Richard C. Dubes, Anil K. Jain
This paper provides a semi-tutorial review of the state-of-the-art in cluster validity, or the verification of results from clustering algorithms, and covers ways of measuring clustering tendency, the fit of hierarchical and partitional structures and indices of compactness and isolation for individual clusters.
BiometrikaBayesian cluster analysis
287 Citations1978David A. Binder
A model-dependent definition of a similarity inatrix is proposed and estimates based on this matrix are justified in a decision-theoretic framework.
Journal of the American Statistical AssociationMeasuring the Power of Hierarchical Cluster Analysis
247 Citations1975Frank B. Baker, Lawrence J. Hubert
The results indicate that the power of a particular hierarchical clustering procedure is a function of the type of partition.
Multivariate Behavioral ResearchA Review Of Monte Carlo Tests Of Cluster Analysis
240 Citations1981Glenn W. Milligan
A review of Monte Carlo validation studies of clustering algorithms indicates that other algorithms may provide better recovery under a variety of conditions than Ward's minimum variance hierarchical method.
BiometricsPractical Problems in a Method of Cluster Analysis
221 Citations1971F. H. C. Marriott
The method of classification based on minimizing the determinant of the within-group dispersion matrix is discussed from the viewpoint of the practical user and it is shown that these can be resolved to give a satisfactory answer to the question of the number of natural clusters and their bounds.
Australian Journal of BotanyMultidimensional group analysis
191 Citations1966RC Jancey
A quantitative taxonomic method is described, based on the calculation of distance functions in multidimensional space, and provides objective discrimination and characterization of taxa.
IEEE Transactions on Pattern Analysis and Machine IntelligenceThe Effect of Cluster Size, Dimensionality, and the Number of Clusters on Recovery of True Cluster Structure
170 Citations1983Glenn W. Milligan, Shih Chung Soon +1 more
An evaluation of four clustering methods and four external criterion measures was conducted with respect to the effect of the number of clusters, dimensionality, and relative cluster sizes on the recovery of true cluster structure, and results indicated that the four criterion measures were generally consistent with each other.
Annual Review of Ecology and SystematicsMethods of Comparing Classifications
166 Citations1974F. James Rohlf
Educational and Psychological MeasurementA Two-Stage Clustering Algorithm with Robust Recovery Characteristics
159 Citations1980Glenn W. Milligan, Lisa M. Sokol
Two FORTRAN IV computer programs for a two-stage clustering algorithm with robust recovery characteristics are described and a hypothesis test procedure which can be used to determine whether significant cluster structure exists in the data is described.
Educational and Psychological MeasurementThe Measurement of Classification Agreement: An Adjustment to the Rand Statistic for Chance Agreement
157 Citations1984Leslie C. Morey, Alan Agresti
Journal of Theoretical BiologyOptimal classification into groups: An approach for solving the taxonomy problem
148 Citations1967Jerrold Rubin
A general hill-climbing algorithm which can be used with any measure of structure to attempt to climb to the optimum partition, and a decision as to which of two partitions is more highly structured, or more valuable is presented.
Journal of the American Statistical AssociationPercentage Points of a Test for Clusters
144 Citations1969Laszlo Engelman, J. A. Hartigan
Multivariate Behavioral ResearchON THE METHODS AND THEORY OF CLUSTERING
142 Citations1969Joseph L. Fleiss, Joseph Zubin
The key defect in almost all clustering procedures seems to be the absence of a statistical model, and the suggestion is made that the clustering problem be stated as a mixture problem.
The Annals of StatisticsAsymptotic Distributions for Clustering Criteria
129 Citations1978J. A. Hartigan
Pattern RecognitionOn the optimal number of features in the classification of multivariate Gaussian data
119 Citations1978Anil K. Jain, W.G. Waller
This work considers the classification problem in the context of two equiprobable multivariate Gaussian densities with a common covariance matrix and provides expressions which relate p opt to the number of available training samples and the Mahalanobis distance between the two populations.
Journal of the American Statistical AssociationA Hybrid Clustering Method for Identifying High-Density Clusters
114 Citations1982M. Anthony Wong
A hybrid method for clustering multivariate observations is proposed, which combines elements of the k-means and the single-linkage clustering techniques, and is shown to be consistent, under certain regularity conditions, in one dimension.
Mathematical GeologyA method for testing the distinctness of clusters: A test of the disjunction of two clusters in Euclidean space as measured by their overlap
106 Citations1977P. H. A. Sneath
A conservative test of whether the observed disjunction is significantly greater than a chosen figure is equivalent to testing whether the overlap of the clusters is significantly less than a corresponding value of VG.
Multivariate Behavioral ResearchA Monte Carlo Investigation Of The Likelihood Ratio Test For The Number Of Components In A Mixture Of Normal Distributions
102 Citations1981B. S. Everitt
The results show that the proposed sampling distribution of the test appears to be appropriate only for sample sizes above fifty, and for data where the sample size is ten times the number of variables.
Elsevier eBooksDistribution Problems in Clustering
101 Citations1977J. A. Hartigan
A statistical problem that is encountered in deciding which of the many clusters presented by algorithms are real is discussed, which requires the asymptotic theory to be validated by Monte Carlo experiments.
Communication in Statistics- Theory and MethodsCommunications in statistics
82 Citations1984Raj S. Chhikara
IEEE Transactions on ComputersA Criterion and an Algorithm for Grouping Data
73 Citations1970Keinosuke Fukunaga, Warren Koontz
This work states two basic requirements that criteria for grouping data without supervision should meet and discusses several criteria in terms of these requirements and introduces a linear transformation of the data.
Journal of Mathematical PsychologyThe comparison and fitting of given classification schemes
62 Citations1977Lawrence J. Hubert, Frank B. Baker
A permutation procedure is described for statistically comparing a given classification scheme, characterized as a hierarchically organized collection of subsets, to either a proximity matrix or a second classification scheme defined on the same basic set of objects.
TechnometricsPower Comparison of Two Tests of Non-Random Clustering
59 Citations1966Joseph Naus
This paper presents two definitions of maximum cluster, that have sometimes been used to test for non-random clustering, and shows that when the clustering interval is sufficiently small, one of the tests is more powerful for a wide class of alternative hypotheses.
Journal of the American Statistical AssociationMultivariate Tests for Clusters
43 Citations1979Kerry L. Lee
Applied Psychological MeasurementA Comparison of Four Clustering Methods Using MMPI Monte Carlo Data
38 Citations1980Roger K. Blashfield, Leslie C. Morey
Botanical GazetteA Stopping Rule for Partitioning Dendrograms
35 Citations1980Robert S. Hill
A modification of that criterion, described in this paper, maintains the advantages of the original criterion and overcomes the problems of the invalid use of phenon lines and lack of objectivity.
NatureHypothesis-testing in Classification
19 Citations1966David W. Goodall
In limiting themselves to probabilities associated with sampling, however, they seem to ignore an important part which probabilistic considerations can and should play in classification.
Characteristics of Four External Criterion Measures
9 Citations1983Glenn W. Milligan
Development of New Pattern-Recognition Methods.
8 Citations1973Daniela Hall, Richard O. Duda +2 more
Several improved clustering methods are developed for general pattern recognition: a new approximate procedure for computing the minimal-spanning tree, a new application of the Kolmogorov-Smirnov test for cluster validity, and anew application of relativistic principles in measures of relationship.