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     

TreeOfTrees Method to Evaluate the Congruence Between Gene Trees

A new method, TreeOfTrees, is proposed to compare X-tree structures obtained from several sets of aligned gene sequences of the same taxa. Its aim is to detect genes or sets of genes having different evolutionary histories. The comparison between sets of trees is based on several tree metrics, leading to a unique tree labelled by the gene trees. The robustness values of its edges are estimated by bootstrapping and consensus procedures that allow detecting subsets of genes having differently evolved. Simulations are performed under various evolutionary conditions to test the efficiency of the method and an application on real data is described. Tests of arboricity and various consensus algorithms are also discussed. A corresponding software package is available.     

Comparison of classifications using measures intermediate between metric dissimilarity and consensus similarity

Two fundamental approaches to the comparison of classifications (e g, partitions on the same finite set of objects) can be distinguished One approach is based upon measures of metric dissimilarity while the other is based upon measures of similarity, or consensus These approaches are not necessarily simple complements of each other Instead, each captures different, limited views of comparison of two classifications The properties of these measures are clarified by their relationships to Day's complexity models and to association measures of numerical taxonomy The two approaches to comparison are equated with the use of separation and minimum value sensitive measures, suggesting the potential application of an intermediate sensitive measure to the problem of comparison of classifications Such a measure is a linear combination of separation sensitive and minimum value sensitive components The application of these intermediate measures is contrasted with the two extremes The intermediate measure for the comparison of classifications is applied to a problem of character weighting arising in the analysis of Australian stream basinsWe thank Bill Day, Mike Austin, Peter Minchin and two anonymous referees for many helpful comments We also thank P Arabie for useful discussion of consensus methods and character weighting     

Character and OTU stability in five taxonomic groups

The character and OTU stability of classifications based on UPGMA clustering and maximum parsimony (MP) trees were compared for 5 datasets (families of angiosperms, families of orthopteroid insects, species of the fish genusIctalurus, genera of the salamander family Salamandridae, and genera of the frog family Myobatrachidae). Stability was investigated by taking different sized random subsamples of OTUs or characters, computing UPGMA clusters and an MP tree, and then comparing the resulting trees with those based on the entire dataset. Agreement was measured by two consensus indices, that of Colless, computed from strict consensus trees, and Stinebrickner's 0.5-consensus index. Tests of character stability generally showed a monotone decrease in agreement with the standard as smaller sets of characters are considered. The relative success of the two methods depended upon the dataset. Tests of OTU stability showed a monotone decrease in agreement for UPGMA as smaller sets of OTUs are considered. But for MP, agreement decreased and then increased again on the same scale. The apparent superiority of UPGMA relative to MP with respect to OTU stability depended upon the dataset. Considerations other than stability, such as computer efficiency or accuracy, will also determine the method of choice for classifications.     

Obtaining common pruned trees

Given two or more dendrograms (rooted tree diagrams) based on the same set of objects, ways are presented of defining and obtaining common pruned trees. Bounds on the size of a largest common pruned tree are introduced, as is a categorization of objects according to whether they belong to all, some, or no largest common pruned trees. Also described is a procedure for regrafting pruned branches, yielding trees for which one can assess the reliability of the depicted relationships. The tree obtained by regrafting branches on to a largest common pruned tree is shown to contain all the classes present in the strict consensus tree. The theory is illustrated by application to two classifications of a set of forty-nine stratigraphical pollen spectra.This work was supported by the Science and Engineering Research Council. The authors are grateful to the referees for constructive criticisms of an earlier version of the paper, and to Dr. J.T. Henderson for advice on PASCAL.     

A Characterization of Majority Rule for Hierarchies

The majority rule has been a popular method for producing a consensus classification from several different classifications, when the classifications are all on the same set of objects and are structured as hierarchies. In this note, a new axiomatic characterization is proved for this consensus method on hierarchies.     

The complexity of reconstructing trees from qualitative characters and subtrees

In taxonomy and other branches of classification it is useful to know when tree-like classifications on overlapping sets of labels can be consistently combined into a parent tree. This paper considers the computation complexity of this problem. Recognizing when a consistent parent tree exists is shown to be intractable (NP-complete) for sets of unrooted trees, even when each tree in the set classifies just four labels. Consequently determining the compatibility of qualitative characters and partial binary characters is, in general, also NP-complete. However for sets of rooted trees an algorithm is described which constructs the “strict consensus tree” of all consistent parent trees (when they exist) in polynomial time. The related question of recognizing when a set of subtrees uniquely defines a parent tree is also considered, and a simple necessary and sufficient condition is described for rooted trees. This work was supproted by the Alexander von Humoldt-Stiftung. I wish to thank Andreas Dress, Hans-Jürgen Bandelt and the referees for their helpful comments.     

Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves

Given two dendrograms (rooted tree diagrams) which have some but not all of their base points in common, a supertree is a dendrogram from which each of the original trees can be regarded as samples The distinction is made between inconsistent and consistent sample trees, defined by whether or not the samples provide contradictory information about the supertree An algorithm for obtaining the strict consensus supertree of two consistent sample trees is presented, as are procedures for merging two inconsistent sample trees Some suggestions for future work are made     

Thresholded consensus for n-trees

A class of (multiple) consensus methods for n-trees (dendroids, hierarchical classifications) is studied. This class constitutes an extension of the so-called median consensus in the sense that we get two numbersm andm such that: If a clusterX occurs ink n-trees of a profileP, withk m, then it occurs in every consensus n-tree ofP. IfX occurs ink n-trees ofP, withm k <m, then it may, or may not, belong to a consensus n-tree ofP. IfX occurs ink n-trees ofP, withk <m then it cannot occur in any consensus n-tree ofP. If these conditions are satisfied, the multiconsensus function is said to be thresholded by the pair (m,m). Two results are obtained. The first one characterizes the pairs of numbers that can be viewed as thresholds for some consensus function. The second one provides a characterization of thresholded consensus methods. As an application a characterization of the quota rules is provided.

---

Resume Cet article traite d'une classe de méthodes de consensus (multiples) entre des classifications hiérarchiques. Cette classe est une généralisation du consensus médian dans las mesure oú elle est constituée des méthodes c pour lesquelles il existe deux nombresm etm tels que: Si une classeX appartient ák hiérarchies d'un profilP, aveck m, alorsX appartient á chaque hiérarchie consensus deP. SiX appartient ák hiérarchies deP, avecm k <m, alorsX, peut, ou non, appartenir à une hiérarchie consensus deP. SiX appartient àk hiérarchies deP, aveck <m, alorsX n'appartient á aucune hiérarchie consensus deP. On dit alors que le couple (m,m) est un seuil pour c. Deux résultats sont obtenus. Le premier caractérise les couples de nombres qui sont des seuils de consensus. Le second caractérise les consensus admettant un seuil. Une caractérisation de la régle des quotas est déduite de ce second résultat.

     

Kappa Coefficients for Circular Classifications

Circular classifications are classification scales with categories that exhibit a certain periodicity. Since linear scales have endpoints, the standard weighted kappas used for linear scales are not appropriate for analyzing agreement between two circular classifications. A family of kappa coefficients for circular classifications is defined. The kappas differ only in one parameter. It is studied how the circular kappas are related and if the values of the circular kappas depend on the number of categories. It turns out that the values of the circular kappas can be strictly ordered in precisely two ways. The orderings suggest that the circular kappas are measuring the same thing, but to a different extent. If one accepts the use of magnitude guidelines, it is recommended to use stricter criteria for circular kappas that tend to produce higher values.     

One-Mode Classification of a Three-Way Data Matrix

X is the automatic hierarchical classification of one mode (units or variables or occasions) of X on the basis of the other two. In this paper the case of OMC of units according to variables and occasions is discussed. OMC is the synthesis of a set of hierarchical classifications Delta obtained from X; e.g., the OMC of units is the consensus (synthesis) among the set of dendograms individually defined by clustering units on the basis of variables, separately for each given occasion of X. However, because Delta is often formed by a large number of classifications, it may be unrealistic that a single synthesis is representative of the entire set. In this case, subsets of similar (homegeneous) dendograms may be found in Delta so that a consensus representative of each subset may be identified. This paper proposes, PARtition and Least Squares Consensus cLassifications Analysis (PARLSCLA) of a set of r hierarchical classifications Delta. PARLSCLA identifies the best least-squares partition of Delta into m (1 <= m <= r) subsets of homogeneous dendograms and simultaneously detects the closest consensus classification (a median classification called Least Squares Consensus Dendogram (LSCD) for each subset. PARLSCLA is a generalization of the problem to find a least-squares consensus dendogram for Delta. PARLSCLA is formalized as a mixed-integer programming problem and solved with an iterative, two-step algorithm. The method proposed is applied to an empirical data set.     

Correspondence Analysis with Linear Constraints of Ordinal Cross-Classifications

Within the non-iterative procedures for performing a correspondence analysis with linear constraints, a strategy is proposed to impose linear constraints in analyzing a contingency table with one or two ordered sets of categories. At the heart of the approach is the partition of the Pearson chi-squared statistics which involves terms that summarize the association between the nominal/ordinal variables using bivariate moments based on orthogonal polynomials. Linear constraints are then included directly in suitable matrices reflecting the most important components, overcoming also the problem of imposing linear constraints based on subjective decisions.     

s-Consensus index method: An additional axiom

A consensus index method is an ordered pair consisting of a consensus method and a consensus index Day and McMorris (1985) have specified two minimal axioms, one which should be satisfied by the consensus method and the other by the consensus index The axiom for consensus indices is not satisfied by the s-consensus index In this paper, an additional axiom, which states that a consensus index equal to one implies profile unanimity, is proposed The s-consensus method together with a modification of the s-consensus index (i e, normalized by the number of distinct nontrivial clusters in the profile) is shown to satisfy the two axioms proposed by Day and McMorris and the new axiom     

科技术语自动提取技术——现状与思考

文章简要介绍了自动术语提取任务的定义、主要方法和评价指标。针对传统的自动术语提取方法,以互信息、t值、tf-idf、C/NC-value为例介绍了单元度和术语度的概念;针对自动术语标注方法,主要介绍了基于序列标注的建模思想。从提取效果来看,现有自动术语提取技术距离期望仍有差距,文章也尝试给出了一些值得探索的方向。     

Tree enumeration modulo a consensus

The number of trees withn labeled terminal vertices grows too rapidly withn to permit exhaustive searches for Steiner trees or other kinds of optima in cladistics and related areas Often, however, structured constraints are known and may be imposed on the set of trees to be scanned These constraints may be formulated in terms of a consensus among the trees to be searched We calculate the reduction in the number of trees to be enumerated as a function of properties of the imposed consensusThis work was supported in part by the Natural Sciences and Engineering Research Council of Canada through operating grant A8867 to D Sankoff and infrastructure grant A3092 to D Sankoff, R J Cedergren and G Lapalme We are grateful to William H E Day for much encouragement and many helpful suggestions     

N-trees as nestings: Complexity,similarity, and consensus

Interpreting a taxonomic tree as a set of objects leads to natural measures of complexity and similarity, and sets natural lower bounds on a consensus tree Interpretations differing as to the kind of objects constituting a tree lead to different measures and consensus Subset nesting is preferred over the clusters (strict consensus) and even the triads interpretations because of its superior expression of shared structure Algorithms for computing the complexity and similarity of trees, as well as a consensus index onto [0,1], are presented for this interpretation The full consensus is defined as the only tree which includes all the nestings shared in a profile of rival trees and whose clusters reflect only nestings shared in the profile The full consensus is proved to exist uniquely for each profile, and to equal the Adams consensusThe author is grateful for the many helpful comments on presentation from Frances McA Adams, William H E Day, and Christopher A Meacham     

A permutation-based algorithm for block clustering

Hartigan (1972) discusses the direct clustering of a matrix of data into homogeneous blocks. He introduces a stepwise divisive method for block clustering within a certain class of block structures which induce clustering trees for both row and column margins. While this class of structures is appealing, the stopping criterion for his method, which is based on asymptotic theory and the assumption that the individual elements of the data matrix are normally distributed, is quite restrictive. In this paper we propose a permutation-based algorithm for block clustering within the same class of block structures. By using permutation arguments to decide where to split and when to stop, our algorithm becomes applicable in a wide variety of cases, including matrices of categorical data and matrices of small-to-moderate size. In addition, our algorithm offers considerable flexibility in how block homogeneity is defined. The algorithm is studied in a series of simulation experiments on matrices of known structure, and illustrated in examples drawn from the fields of taxonomy, political science, and data architecture.     

Preserving consensus hierarchies

In numerical taxonomy we often have the task of finding a consensus hierarchy for a given set of hierarchies. This consensus hierarchy should reflect the substructures which are common to all hierarchies of the set. Because there are several kinds of substructures in a hierarchy, the general axiom to preserve common substructures leads to different axioms for each kind of substructure. In this paper we consider the three substructurescluster, separation, andnesting, and we give several characterizations of hierarchies preserving these substructures. These characterizations facilitate interpretation of axioms for preserving substructures and the examination of properties of consensus methods. Finally some extensions concerning the preserving of qualified substructures are discussed.The author is grateful to the editor and the referees for their helpful suggestions and to H. J. Bandelt for his comments on an earlier version of this paper.     

Metric Models for Random Graphs

Many problems entail the analysis of data that are independent and identically distributed random graphs. Useful inference requires flexible probability models for such random graphs; these models should have interpretable location and scale parameters, and support the establishment of confidence regions, maximum likelihood estimates, goodness-of-fit tests, Bayesian inference, and an appropriate analogue of linear model theory. Banks and Carley (1994) develop a simple probability model and sketch some analyses; this paper extends that work so that analysts are able to choose models that reflect application-specific metrics on the set of graphs. The strategy applies to graphs, directed graphs, hypergraphs, and trees, and often extends to objects in countable metric spaces.