The generation of random ultrametric matrices representing dendrograms |
| |
Authors: | François-Joseph Lapointe Pierre Legendre |
| |
Affiliation: | (1) Département de Sciences biologiques, Université de Montréal, Succursale A, C.P. 6128, H3C 3J7 Montréal, Québec, Canada |
| |
Abstract: | Many methods and algorithms to generate random trees of many kinds have been proposed in the literature. No procedure exists however for the generation of dendrograms with randomized fusion levels. Randomized dendrograms can be obtained by randomizing the associated cophenetic matrix. Two algorithms are described. The first one generates completely random dendrograms, i.e., trees with a random topology, random fusion level values, and random assignment of the labels. The second algorithm uses a double-permutation procedure to randomize a given dendrogram; it proceeds by randomization of the fixed fusion levels, instead of using random fusion level values. A proof is presented that the double-permutation procedure is a Uniform Random Generation Algorithmsensu Furnas (1984), and a complete example is given. This work was supported by NSERC Grant No. A7738 to P. Legendre and by a NSERC scholarship to F.-J. Lapointe. |
| |
Keywords: | Random dendrograms Random matrices Uniform sampling Tree algorithm Monte Carlo studies Clustering methodology |
本文献已被 SpringerLink 等数据库收录! |
|