On probability distributions of single-linkage dendrograms
- 1 February 1981
- journal article
- research article
- Published by Taylor & Francis in Journal of Statistical Computation and Simulation
- Vol. 12 (2) , 121-131
- https://doi.org/10.1080/00949658108810439
Abstract
There are ways to order the pairwise similarities between N objects, assuming no ties. According to single linkage (SL) clustering, each such order determines a dendrogram for the N objects. We give an algorithm for calculating the number of different SL-dendrograms on N objects. We also give an algorithm for calculating the probability distribution of the SL-dendrograms under pure randomness, i.e. assuming that all the similarity orders are equally probable. The results are used to illustrate the statistical risks for small values of N,. when SL-dendrograms are used to test cluster structure hypotheses.Keywords
This publication has 5 references indexed in Scilit:
- Estimating a graph from triad countsJournal of Statistical Computation and Simulation, 1979
- Probability Tables for Cluster Analysis Based on a Theory of Random GraphsJournal of the American Statistical Association, 1976
- A Probability Theory of Cluster AnalysisJournal of the American Statistical Association, 1973
- A Review of ClassificationJournal of the Royal Statistical Society. Series A (General), 1971
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969