An Examination of the Effect of Six Types of Error Perturbation on Fifteen Clustering Algorithms
PsychometrikaPublished 1 September 1980
Glenn W. Milligan
Citations1,170
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
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.
Abstract
An evaluation of several clustering methods was conducted. Artificial clusters which exhibited the properties of internal cohesion and external isolation were constructed. The true cluster structure was subsequently hidden by six types of error-perturbation. The results indicated that the hierarchical methods were differentially sensitive to the type of error perturbation. In addition, generally poor recovery performance was obtained when random seed points were used to start the K -means algorithms. However, two alternative starting procedures for the nonhierarchical methods produced greatly enhanced cluster recovery and were found to be robust with respect to all of the types of error examined.
Keywords
Computer Science
Cluster Analysis
9,195 Citations1974Barry J. Everitt, Sabine Landau +1 more
Journal of the American Statistical AssociationObjective Criteria for the Evaluation of Clustering Methods
5,815 Citations1971Telmo Menezes
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.
IEEE Transactions on ComputersGraph-Theoretical Methods for Detecting and Describing Gestalt Clusters
1,741 Citations1971C. T. Zahn
A family of graph-theoretical algorithms based on the minimal spanning tree are capable of detecting several kinds of cluster structure in arbitrary point sets; description of the detected clusters is possible in some cases by extensions of the method.
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.
PsychometrikaRepresentation of Structure in Similarity Data: Problems and Prospects
484 Citations1974Roger N. Shepard
Biometrics391: A Monte Carlo Comparison of Six Clustering Procedures
262 Citations1975F. Kent Kuiper, Lloyd D. Fisher
Psychometrika<i>r</i><sub><i>p</i></sub> and other Coefficients of Pattern Similarity
241 Citations1949Raymond B. Cattell
The derivation of acoefficient of pattern similarity, rp, is presented and its properties are investigated, both deductively and in terms of actual data on culture patterns.
Annual Review of Ecology and SystematicsMethods of Comparing Classifications
166 Citations1974F. James Rohlf
Multivariate Behavioral ResearchMixture Model Tests Of Hierarchical Clustering Algorithms: The Problem Of Classifying Everybody
161 Citations1979Craig Edelbrock
A subset of high accuracy algorithms, including single, average, and centroid linkage using correlation, and Ward's minimum variance technique, was identified and all of the algorithms were significantly more accurate than a random linkage algorithm, and accuracy was inversely related to coverage.
PsychometrikaU-Statistic Hierarchical Clustering
144 Citations1978Roy G. D’Andrade
The U-statistic method is found to be consistently more effective in recovering the original tree structures than either the single-link or complete-link methods.
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.
Journal of the American Statistical AssociationStability of Two Hierarchical Grouping Techniques Case I: Sensitivity to Data Errors
129 Citations1974Frank B. Baker
Empirical sampling distributions of the gamma coefficients indicated that the single linkage grouping technique was more sensitive to the type of data errors employed than the complete linkage technique.
The Computer JournalEvaluation of hierarchical grouping techniques: a preliminary study
107 Citations1972K. Cunningham
This is an initial enquiry into the evaluation of hierarchical grouping procedures, with seven well-known hierarchical grouping techniques investigated and an arbitrary criterion of quality proposed was goodness of fit of output distances to input distances.
Pattern RecognitionThe validation of four ultrametric clustering algorithms
94 Citations1980Glenn W. Milligan, Paul D. Isaac
The results indicated that theRank order performance of the four methods differed markedly from the rank order generally found in multivariate normal mixture model studies.
PsychometrikaUltrametric Hierarchical Clustering Algorithms
73 Citations1979Glenn W. Milligan
Johnson has shown that the single linkage and the complete linkage hierarchical clustering algorithms induce a metric on the data known as the ultrametric through the use of the Lance and Williams recurrence formula.
Journal of Verbal Learning and Verbal BehaviorEvaluating object set partitions: Free-sort analysis and some generalizations
64 Citations1976Lawrence J. Hubert, Joel R. Levin
A statistical framework is suggested for comparing a single partition of an object set to a second partition posited a priori, or possibly, to a more general proximity matrix.
PsychometrikaNonmetric Grouping: Clusters and Cliques
48 Citations1975Edmund R. Peay
This approach to grouping is shown to provide a useful framework for grouping methods based on ana priori specification of the properties of the desired subsets, and includes a natural generalization for “complete linkage’ and “single linkage” clustering, such as the methods of Johnson [1967].
Naval Postgraduate School Random Number Generator Package LLRANDOM
47 Citations1973Gerard P. Learmonth, Peter W. Lewis
An interim version of a computer program package for random number generation on the IBM System/360 that has the ability (optional) to shuffle the pseudo-random numbers to obtain better statistical properties.
The Computer JournalControversy concerning the criteria for taxonometric strategies
45 Citations1971W. T. Williams
British Journal of Mathematical and Statistical PsychologyRANK ORDER CLUSTER ANALYSIS <sup>1</sup>
10 Citations1966D. B. Bromley
A method of rank order cluster analysis (abbreviated ROCA) is compared and contrasted with factor analysis; it appears to be effective in detecting clusters of functionally similar variables and defining the common function of each cluster.
Behavior Research MethodsCLUSTER: A hierarchical clustering program for large data sets (n>100)
4 Citations1973Jay Levinsohn, Sandra G. Funk
CLUSTER is basically an extension of Veldrnan's (1967) HGROUP program, and utilizes Ward's (1963) hierarchical procedure of successively combining n objects together to form n, n 1, n 2, "', 2 groups by minimizing an objective error function.