The DOI matches its Crossref record; 33 of the 33 references it cites were found in a registry or an index.
Finding the Number of Clusters in a Dataset: An Information-Theoretic Approach
Abstract
One of the most difficult problems in cluster analysis is identifying the number of groups in a dataset. Most previously suggested approaches to this problem are either somewhat ad hoc or require parametric assumptions and complicated calculations. In this article we develop 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. Our technique is computationally efficient and straightforward to implement. We demonstrate empirically its effectiveness, not only for choosing the number of clusters, but also for identifying underlying structure, on a wide range of simulated and real world datasets. In addition, we give a rigorous theoretical justification for the method based on information-theoretic ideas. Specifically, results from the subfield of electrical engineering known as rate distortion theory allow us to describe the behavior of the distortion in both the presence and absence of clustering. Finally, we note that these ideas potentially can be extended to a wide range of other statistical model selection problems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb01338.x · Cited by 88,486
Estimating the Dimension of a Model
Schwarz, G. (1978) · The Annals of Statistics · doi:10.1214/aos/1176344136 · Cited by 47,033
An Introduction to the Bootstrap
Efron, B., & Tibshirani, R. J. (1994) · doi:10.1201/9780429246593 · Cited by 40,500
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
On Information and Sufficiency
Kullback, S., & Leibler, R. A. (1951) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729694 · Cited by 20,193
Information Theory and an Extension of the Maximum Likelihood Principle
Akaike, H. (1998) · Springer Series in Statistics · doi:10.1007/978-1-4612-1694-0_15 · Cited by 17,781
THE USE OF MULTIPLE MEASUREMENTS IN TAXONOMIC PROBLEMS
FISHER, R. A. (1936) · Annals of Eugenics · doi:10.1111/j.1469-1809.1936.tb02137.x · Cited by 15,227
Finding groups in data: an introduction to cluster analysis
(1991) · Choice Reviews Online · doi:10.5860/choice.28-4558 · Cited by 10,474
Vector Quantization and Signal Compression
Gersho, A., & Gray, R. M. (1992) · Springer eBooks · doi:10.1007/978-1-4615-3626-0 · Cited by 7,003
Estimating the Number of Clusters in a Data Set Via the Gap Statistic
Tibshirani, R., Walther, G., & Hastie, T. (2001) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/1467-9868.00293 · Cited by 6,205
(1975) · CERN Document Server (European Organization for Nuclear Research) · Cited by 5,958
Information Theory and Reliable Communication.
Lee, P. M., & Gallager, R. T. (1970) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2344305 · Cited by 5,399
A dendrite method for cluster analysis
Caliński, T., & Harabasz, J. (1974) · Communications in Statistics · doi:10.1080/03610927408827101 · Cited by 4,480
An Examination of Procedures for Determining the Number of Clusters in a Data Set
Milligan, G. W., & Cooper, M. C. (1985) · Psychometrika · doi:10.1007/bf02294245 · Cited by 3,868
Information Theory: Coding Theorems for Discrete Memoryless Systems
Csiszár, I., & Körner, J. (2014) · REAL-EOD (Library of the Hungarian Academy of Sciences and the Information Center Oriental Collection) · Cited by 3,246
How Many Clusters? Which Clustering Method? Answers Via Model-Based Cluster Analysis
Fraley, C. (1998) · The Computer Journal · doi:10.1093/comjnl/41.8.578 · Cited by 2,549
Assessing a mixture model for clustering with the integrated completed likelihood
Biernacki, C., Celeux, G., & Govaert, G. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.865189 · Cited by 1,535
On a measure of the information provided by an experiment
Lindley, D. V. (1956) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177728069 · Cited by 1,509
Multisurface method of pattern separation for medical diagnosis applied to breast cytology.
Wolberg, W. H., & Mangasarian, O. L. (1990) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.87.23.9193 · Cited by 1,037
Principles and practice of information theory
Blahut, R. E. (1987) · Medical Entomology and Zoology · Cited by 1,008
Rate distortion theory : a mathematical basis for data compression
Berger, T. (1971) · Prentice Hall eBooks · Cited by 953
Combining Instance-Based and Model-Based Learning
Quinlan, J. R. (1993) · Elsevier eBooks · doi:10.1016/b978-1-55860-307-3.50037-x · Cited by 773
A Criterion for Determining the Number of Groups in a Data Set Using Sum-of-Squares Clustering
Krzanowski, W. J., & Lai, Y. T. (1988) · Biometrics · doi:10.2307/2531893 · Cited by 711
Expected Information as Expected Utility
Bernardo, J. M. (1979) · The Annals of Statistics · doi:10.1214/aos/1176344689 · Cited by 568
Clustering for Sparsely Sampled Functional Data
James, G. M., & Sugar, C. A. (2003) · Journal of the American Statistical Association · doi:10.1198/016214503000189 · Cited by 502
Self-citationA robust competitive clustering algorithm with applications in computer vision
Frigui, H., & Krishnapuram, R. (1999) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.765656 · Cited by 487
Relative Entropy Measures of Multivariate Dependence
Joe, H. (1989) · Journal of the American Statistical Association · doi:10.1080/01621459.1989.10478751 · Cited by 324
Bayesian approaches to Gaussian mixture modeling
Roberts, S. J., Husmeier, D., Rezek, I., & Penny, W. (1998) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.730550 · Cited by 317
Information theoretic clustering
Gokcay, E., & Principe, J. C. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.982897 · Cited by 293
Capturing the Intangible Concept of Information
Soofi, E. S. (1994) · Journal of the American Statistical Association · doi:10.1080/01621459.1994.10476865 · Cited by 196
(2021) · Technometrics · doi:10.1080/00401706.2021.1982286 · Cited by 111
American Statistical Association
Leone, F. C. (2005) · Wiley eBooks · doi:10.1002/0471667196.ess0036.pub2 · Cited by 71
An information criterion for likelihood selection
Yuan, A., & Clarke, B. S. (1999) · IEEE Transactions on Information Theory · doi:10.1109/18.749003 · Cited by 15
Cited by
An extensive comparative study of cluster validity indices
Arbelaitz, O., Gurrutxaga, I., Muguerza, J., Pérez, J. M., & Perona, I. (2013) · Pattern Recognition · doi:10.1016/j.patcog.2012.07.021 · Cited by 1,383
A framework for feature selection in clustering
Witten, D. M., & Tibshirani, R. (2010) · Journal of the American Statistical Association · doi:10.1198/jasa.2010.tm09415 · Cited by 696
“…scope of this paper, and has been discussed extensively in the literature for standard K -means clustering; we refer the interested reader to Milligan and Cooper (1985), Kaufman and Rousseeuw (1990), Tibshirani, Walther, and Hastie (2001), Sugar and James (2003), and Tibshirani and Walther (2005).”
Discovering Activities to Recognize and Track in a Smart Environment
Rashidi, P., Cook, D. J., Holder, L. B., & Schmitter-Edgecombe, M. (2011) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.148 · Cited by 462
Shi, C., Wei, B., Wei, S., Wang, W., Liu, H., & Liu, J. (2021) · EURASIP Journal on Wireless Communications and Networking · doi:10.1186/s13638-021-01910-w · Cited by 441
Functional data clustering: a survey
Jacques, J., & Preda, C. (2014) · Advances in Data Analysis and Classification · doi:10.1007/s11634-013-0158-y · Cited by 406
Metadata
- Authors
- Sugar, C. A., & James, G. M.
- Venue
- Journal of the American Statistical Association
- Publisher
- Informa UK Limited
- Published
- 2003-09
- Volume
- 98
- Issue
- 463
- Pages
- 750-763
- ISSN
- 0162-1459 (ISSN-L)
- 1537-274X
- OpenAlex
- W1973041621
- Cited by
- 811
- References
- 33
- FWCI
- 9.89
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.