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.

     

Fitting an extended INDSCAL model to three-way proximity data

The INDSCAL individual differences scaling model is extended by assuming dimensions specific to each stimulus or other object, as well as dimensions common to all stimuli or objects. An alternating maximum likelihood procedure is used to seek maximum likelihood estimates of all parameters of this EXSCAL (Extended INDSCAL) model, including parameters of monotone splines assumed in a quasi-nonmetric approach. The rationale for and numerical details of this approach are described and discussed, and the resulting EXSCAL method is illustrated on some data on perception of musical timbres.     

The weighted sum of split and diameter clustering

In this paper, we propose a bicriterion objective function for clustering a given set ofN entities, which minimizes [d–(1–)s], where 01, andd ands are the diameter and the split of the clustering, respectively. When =1, the problem reduces to minimum diameter clustering, and when =0, maximum split clustering. We show that this objective provides an effective way to compromise between the two often conflicting criteria. While the problem is NP-hard in general, a polynomial algorithm with the worst-case time complexityO(N ²) is devised to solve the bipartition version. This algorithm actually gives all the Pareto optimal bipartitions with respect to diameter and split, and it can be extended to yield an efficient divisive hierarchical scheme. An extension of the approach to the objective [(d ₁+d ₂)–2(1–)s] is also proposed, whered ₁ andd ₂ are diameters of the two clusters of a bipartition.This research was supported in part by the National Science and Engineering Research Council of Canada (Grant OGP 0104900). The authors wish to thank two anonymous referees, whose detailed comments on earlier drafts improved the paper.     

Additive clustering and qualitative factor analysis methods for similarity matrices

We review methods of qualitative factor analysis (QFA) developed by the author and his collaborators over the last decade and discuss the use of QFA methods for the additive clustering problem. The QFA method includes, first, finding a square Boolean matrix in a fixed set of Boolean matrices with simple structures to approximate a given similarity matrix, and, second, repeating this process again and again using residual similarity matrices. We present convergence properties for three versions of the method, provide cluster interpretations for results obtained from the algorithms, and give formulas for the evaluation of factor shares of the initial similarities variance.I am indebted to Professor P. Arabie and the referees for valuable comments and editing of the text.     

Least squares algorithms for constructing constrained ultrametric and additive tree representations of symmetric proximity data

A mathematical programming algorithm is developed for fitting ultrametric or additive trees to proximity data where external constraints are imposed on the topology of the tree. The two procedures minimize a least squares loss function. The method is illustrated on both synthetic and real data. A constrained ultrametric tree analysis was performed on similarities between 32 subjects based on preferences for ten odors, while a constrained additive tree analysis was carried out on some proximity data between kinship terms. Finally, some extensions of the methodology to other tree fitting procedures are mentioned.The first author is supported as Bevoegdverklaard Navorser of the Belgian Nationaal Fonds voor Wetenschappelijk Onderzoek.     

Ultrametric tree representations of incomplete dissimilarity data

The least squares algorithm for fitting ultrametric trees to proximity data originally proposed by Carroll and Pruzansky and further elaborated by De Soete is extended to handle missing data. A Monte Carlo evaluation reveals that the algorithm is capable of recovering an ultrametric tree underlying an incomplete set of error-perturbed dissimilarities quite well.Geert De Soete is Aangesteld Navorser of the Belgian National Fonds voor Wetenschappelijk Onderzoek.     

Comments on “aggregation of equivalence relations” by P. C. Fishburn and A. Rubinstein

The theorem of the paper Aggregation of Equivalence Relations, by Fishburn and Rubinstein, states a result already known. This theorem improves a result from Mirkin (1975) and appears as a corollary occurring in Leclerc (1984).

---

Resume L'unique théorème de l'article Aggregation of Equivalence Relations de Fishburn et Rubinstein est déja connu. Il améliore, en fait, un résultat de Mirkin (1975) et apparait en tant que corollaire dans Leclerc (1984).

     

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     

Algebraic Self-Dualityc as the ”Ultimate Explanation”

Shahn Majids philosophy of physics is critically presented. In his view the postulate that the universe should be self-explaining implies that no fundamental theory of physics is complete unless it is self-dual. Majid shows that bicrossproduct Hopf algebras have this property. His philosophy is compared with other approaches to the ultimate explanation and briefly analyzed.     

Optimal variable weighting for hierarchical clustering: An alternating least-squares algorithm

This paper presents the development of a new methodology which simultaneously estimates in a least-squares fashion both an ultrametric tree and respective variable weightings for profile data that have been converted into (weighted) Euclidean distances. We first review the relevant classification literature on this topic. The new methodology is presented including the alternating least-squares algorithm used to estimate the parameters. The method is applied to a synthetic data set with known structure as a test of its operation. An application of this new methodology to ethnic group rating data is also discussed. Finally, extensions of the procedure to model additive, multiple, and three-way trees are mentioned.The first author is supported as Bevoegdverklaard Navorser of the Belgian Nationaal Fonds voor Wetenschappelijk Onderzoek.     

OVWTRE: A program for optimal variable weighting for ultrametric and additive tree fitting

The author is supported as Bevoegdverklaard Navorser of the Belgian National Fonds voor Wetenschappelijk Onderzoek.     

An evaluation of five algorithms for generating an initial configuration for SINDSCAL

Five different methods for obtaining a rational initial estimate of the stimulus space in the INDSCAL model were compared using the SINDSCAL program for fitting INDSCAL. The effect of the number of stimuli, the number of subjects, the dimensionality, and the amount of error on the quality and efficiency of the final SINDSCAL solution were investigated in a Monte Carlo study. We found that the quality of the final solution was not affected by the choice of the initialization method, suggesting that SINDSCAL finds a global optimum regardless of the initialization method used. The most efficient procedures were the methods proposed by by de Leeuw and Pruzansky (1978) and by Flury and Gautschi (1986) for the simultaneous diagonalization of several positive definite symmetric matrices, and a method based on linearly constraining the stimulus space using the CANDELINC approach developed by Carroll, Pruzansky, and Kruskal (1980).Geert De Soete is supported as Bevoegdverklaard Navorser of the Belgian Nationaal Fonds voor Wetenschappelijk Onderzoek. The authors gratefully acknowledge the helpful comments and suggestions of the reviewers.     

Clustering the rows and columns of a contingency table

A number of ways of investigating heterogeneity in a two-way contingency table are reviewed. In particular, we consider chi-square decompositions of the Pearson chi-square statistic with respect to the nodes of a hierarchical clustering of the rows and/or the columns of the table. A cut-off point which indicates significant clustering may be defined on the binary trees associated with the respective row and column cluster analyses. This approach provides a simple graphical procedure which is useful in interpreting a significant chi-square statistic of a contingency table.The author gratefully acknowledges the constructive comments of the referees and the editor.     

Weighting and selection of variables for cluster analysis

One of the thorniest aspects of cluster analysis continues to be the weighting and selection of variables. This paper reports on the performance of nine methods on eight leading case simulated and real sets of data. The results demonstrate shortcomings of weighting based on the standard deviation or range as well as other more complex schemes in the literature. Weighting schemes based upon carefully chosen estimates of within-cluster and between-cluster variability are generally more effective. These estimates do not require knowledge of the cluster structure. Additional research is essential: worry-free approaches do not yet exist.     

On The Impossibility Of Empirical Controls Of Scientific Theories – From The Point Of View Of A Psychologist

Standard considerations of philosophy of science are reformulated in psychological terms and arguments, suggesting a fundamental change in life perspective: subjective experiences or introspective data are subject to motivational biases and therefore not admitted as objective empirical facts in science, However, we never experience objects or events of the external world, i.e., so called objective facts, but exclusively subjective percepts or mental events. They are merely assumed to, but may or may not be accurate or distorted mental representations of objects or events of an external world. Accordingly, the latter are theoretical constructs, i.e., constructs of the fictitious but most successful predictive (implicit) theory, called external world, which seems to be constructed from regularities observed in mental events and serves as a reference fiction for, erroneously called empirical, tests of predictions of scientific theories.Relevant Publication: Micko, H.C.: 2001, Psychologie: Von der Geistes – zur Naturwissenschaft – und weiter wohin? Erkenntnistheoretische Erwägungen vor und nach dem Aufkommen des philosophischen Konstruktivismus. Ztschr. f. Psychologie, 209: 54–68.     

Metric unidimensional scaling and global optimization

For the problem of metric unidimensional scaling, the number of local minima is estimated. For locating the globally optimal solution we develop an approach, called the smoothing technique. Although not guaranteed inevitably to locate the global optimum, the smoothing technique did so in all computational experiments where the global optimum was known.     

A test for spatial homogeneity in cluster analysis

This paper proposes a measure of spatial homogeneity for sets of d-dimensional points based on nearest neighbor distances. Tests for spatial uniformity are examined which assess the tendency of the entire data set to aggregate and evaluate the character of individual clusters. The sizes and powers of three statistical tests of uniformity against aggregation, regularity, and unimodality are studied to determine robustness. The paper also studies the effects of normalization and incorrect prior information. A percentile frame sampling procedure is proposed that does not require a sampling window but is superior to a toroidal frame and to buffer zone sampling in particular situations. Examples test two data sets for homogeneity and search the results of a hierarchical clustering for homogeneous clusters.This work was partially supported by NSF Grant ECS-8300204.     

The Social Construction of Mind and the Future of Cognitive Science

Cognitive activity, which essentially consistsof the use of signs, does not only depend onthe internal (mental, or brain) processes. Thefirst part of the paper presents severalversions of the idea of the external andcultural organization of individual's mentalprocesses. The second part of the paperconsiders a future development of cognitivescience as a science of the extended andsocially constructed mind. KazimierzTwardowski's theory of intentionality and histheory of actions and products provide theconceptual framework of the undertaken analysis.