Statistical tests on two characteristics of the shapes of cluster diagrams

A cluster diagram is a rooted planar tree that depicts the hierarchical agglomeration of objects into groups of increasing size. On the null hypothesis that at each stage of the clustering procedure all possible joins are equally probable, we derive the probability distributions for two properties of these diagrams: (1)S, the number of single objects previously ungrouped that are joined in the final stages of clustering, and (2)m _k, the number of groups ofk+1 objects that are formed during the process. Ecological applications of statistical tests for these properties are described and illustrated with data from weed communities of Saskatchewan fields.This work was supported by the Natural Sciences and Engineering Research Council of Canada.     

飞蝗五个自然种群的遗传分化研究

采用随机扩增多态性DNA（RAPD）技术检测飞蝗Locusta migratoria（Linnaeus）2个亚种5个种群的遗传多样性，11个随机引物扩增共产生了163条带，其中多态性片段为156条．Shannon信息指数和Nei’S指数对RAPD数据的分析表明：东亚飞蝗Locusta migratoria manilensis（Meyen）不同种群存在较高的遗传多样性；同时，东亚飞蝗种群间出现一定程度的遗传分化，遗传分化系数分别为36．09％和33．85％．用UPGMA对Nei’S遗传距离作聚类分析，结果表明：东亚飞蝗不同种群的亲缘关系较近，而它们与亚洲飞蝗Locusta migratoria migratoria（Linnaeus）关系较远．由Nei’S遗传一致度和遗传距离可以看出，东亚飞蝗不同种群间的遗传距离均小于东亚飞蝗与亚洲飞蝗之间的遗传距离．由Mantel软件检验得出地理距离和遗传距离的相关性系数r〈0．7，表明这5个种群亲缘关系的远近与地理距离无相关性．同时，还结合等位酶种群遗传结构研究结果综合分析了上述东亚飞蝗4种群的遗传多样性及其分化，表明RAPD可检测出更高水平的遗传多样性．     

On lattice consensus methods

We investigate the consensus problem for classifications of three types: partitions, dendrograms, and n-trees For partitions or dendrograms, lattice polynomials define natural consensus functions We extend these lattice methods to n-trees, introducing a general class of consensus functions that includes the intersection consensus functions in current use These lattice consensus methods have a number of desirable mathematical properties We prove that they all satisfy the Pareto Axiom For each of the three classification types, we determine which lattice consensus functions satisfy the Betweenness AxiomAuthor partially supported by a research grant from the Faculty Research Committee, Bowling State University     

Comparison tests for dendrograms: A comparative evaluation

Classifications are generally pictured in the form of hierarchical trees, also called dendrograms. A dendrogram is the graphical representation of an ultrametric (=cophenetic) matrix; so dendrograms can be compared to one another by comparing their cophenetic matrices. Three methods used in testing the correlation between matrices corresponding to dendrograms are evaluated. The three permutational procedures make use of different aspects of the information to compare dendrograms: the Mantel procedure permutes label positions only; the binary tree methods randomize the topology as well; the double-permutation procedure is based on all the information included in a dendrogram, that is: topology, label positions, and cluster heights. Theoretical and empirical investigations of these methods are carried out to evaluate their relative performance. Simulations show that the Mantel test is too conservative when applied to the comparison of dendrograms; the methods of binary tree comparisons do slightly better; only the doublepermutation test provides unbiased type I error. Les arbres utilisés pour illustrés les groupements sont généralement représentés sous la forme de classifications hiérarchiques ou dendrogrammes. Un dendrogramme représente graphiquement l’information contenue dans la matrice ultramétrique (=cophénétique) correspondant à la classification. Dès ultramétriques correspondantes. Nous comparons trois méthodes permettant d’évaluer la signification statistique du coefficient de correlation mesuré entre deux matrices ultramétriques. Ces trois tests par permutations tiennent compte d’aspects différents pour comparer des dendrogrammes: le test de Mantel permute les feuilles de l’arbre, les méthodes pour arbres binaires permutent les feuilles et la topologie, alors que la procédure à double permutation permute les feuilles, la topologie et les niveaux de fusion des dendrogrammes comparés. L’efficacité relative des trois méthodes est évaluée empiriquement et théoriquement. Nos résultats suggèrent l’utilisation préférentielle du test à double permutation pour la comparaison de dendrogrammes: le test de Mantel s’avère trop conservateur, tandis que les méthodes pour arbres binaires ne sont pas toujours adéquates.

---

This work was supported by NSERC grant no. A7738 to Pierre Legendre and by a NSERC scholarship to F.-J. Lapointe.     

Maximum sum-of-splits clustering

ConsiderN entities to be classified, and a matrix of dissimilarities between pairs of them. The split of a cluster is the smallest dissimilarity between an entity of this cluster and an entity outside it. The single-linkage algorithm provides partitions intoM clusters for which the smallest split is maximum. We study here the average split of the clusters or, equivalently, the sum of splits. A (N ²) algorithm is provided to determine maximum sum-of-splits partitions intoM clusters for allM betweenN – 1 and 2, using the dual graph of the single-linkage dendrogram.

---

Résumé SoientN objets à classifier et une matrice de dissimilarit és entre paires de ces objets. L'écart d'une classe est la plus petite dissimilarité entre un objet de cette classe et un objet en dehors d'elle. L'algorithme du lien simple fournit des partitions enM classes dont le plus petit écart est maximum. On étudie l'écart moyen des classes, ou, ce qui est équivalent, la somme des écarts. On propose un algorithme en (N ²) pour déterminer des partitions enM classes dont la somme des écarts est maximum pourM allant deN – 1 à 2, basé sur le graphe dual du dendrogramme de la méthode du lien simple.

     

Espaliers: A generalization of dendrograms

Dendrograms are widely used to represent graphically the clusters and partitions obtained with hierarchical clustering schemes. Espaliers are generalized dendrograms in which the length of horizontal lines is used in addition to their level in order to display the values of two characteristics of each cluster (e.g., the split and the diameter) instead of only one. An algorithm is first presented to transform a dendrogram into an espalier without rotation of any part of the former. This is done by stretching some of the horizontal lines to obtain a diagram with vertical and horizontal lines only, the cutting off by diagonal lines the parts of the horizontal lines exceeding their prescribed length. The problem of finding if, allowing rotations, no diagonal lines are needed is solved by anO(N ²) algorithm whereN is the number of entities to be classified. This algorithm is the generalized to obtain espaliers with minimum width and, possibly, some diagonal lines.Work of the first and second authors has been supported by FCAR (Fonds pour la Formation de Chercheurs et l'Aide à la Recherche) grant 92EQ1048, and grant N00014-92-J-1194 from the Office of Naval Research. Work of the first author has also been supported by NSERC (Natural Sciences and Engineering Research Council of Canada) grant to École des Hautes Études Commerciales, Montréal and by NSERC grant GP0105574. Work of the second author has been supported by NSERC grant GP0036426, by FCAR grant 90NC0305, and by an NSF Professorship for Women in Science at Princeton University from September 1990 until December 1991. Work of the third author was done in part during a visit to GERAD, Montréal.