Abstract
A least-squares algorithm for fitting ultrametric and path length or additive trees to two-way, two-mode proximity data is presented. The algorithm utilizes a penalty function to enforce the ultrametric inequality generalized for asymmetric, and generally rectangular (rather than square) proximity matrices in estimating an ultrametric tree. This stage is used in an alternating least-squares fashion with closed-form formulas for estimating path length constants for deriving path length trees. The algorithm is evaluated via two Monte Carlo studies. Examples of fitting ultrametric and path length trees are presented.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Addelman, S. (1962). Orthogonal main-effect plans for asymmetrical factorial experiments.Technometrics, 4, 21–46.
Carroll, J. D. (1976). Spatial, non-spatial and hybrid models for scaling.Psychometrika, 41, 439–463.
Carroll, J. D. and Chang, J. J. (1973). A method for fitting a class of hierarchical tree structure models to dissimilarities data, and its application to some body parts data of Miller's. InProceedings of the 81st Annual Convention of the American Psychological Association, Vol. 8, 1097–1098.
Carroll, J. D., Clark, L. A., and DeSarbo, W. S. (1984). The representation of three-way proximities data by single and multiple tree structure models.Journal of Classification, (in press).
Carroll, J. D. and Pruzansky, S. (1975). Fitting of hierarchical tree structure (HTS) models, mixtures of HTS models, and hybrid models, via mathematical programming and alternating least squares.Paper presented at the U.S.-Japan Seminar on Multidimensional Scaling, University of California at San Diego, La Jolla, California.
Carroll, J. D. and Pruzansky, S. (1980). Discrete and hybrid scaling models. In E. D. Lantermann and H. Feger (Eds.),Similarity and Choice. Bern: Hans Huber.
Coombs, C. H. (1964).A theory of data. New York: Wiley.
Courant, R. (1965).Differential and integral calculus (2nd edition), Vol. 1. New York: Wiley.
Cunningham, J. P. (1974). Finding the optimal tree realization of a proximity matrix.Paper presented at the Mathematical Psychology Meetings, Ann Arbor Michigan.
Cunningham, J. P. (1978). Free trees and bidirectional trees as a representations of psychological distance.Journal of Mathematical Psychology, 17, 165–188.
DeSarbo, W. S. (1982). GENNCLUS: New models for general nonhierarchical clustering analysis.Psychometrika, 47, 449–475.
DeSoete, G. (1983). A least squares algorithm for fitting additive trees to proximity data.Psychometrika, 48, 621–626.
Dobson, A. G. (1974). Unrooted trees for numerical taxonomy.Journal of Applied Probability, 11, 32–42.
Farris, J. S. (1972). Estimating phylogenetic trees from distance matrices.American Naturalist, 106, 645–668.
Furnas, G. W. (1980). Objects and their features: The metric representation of two class data.Unpublished Doctoral Dissertation, Stanford University.
Furnas, G. W. (1984). The construction of random, terminally labeled, binary trees.Journal of Classification, (in press).
Green, P. E. and Tull, D. S. (1978).Research for marketing decisions, 4th ed., Englewood, Cliffs, N.J.: Prentice-Hall.
Harshman, R. (1978). Models for analysis of asymmetrical relationships amongN objects or stimuli.Unpublished Paper, University of Western Ontario, Canada.
Hartigan, J. A. (1975).Clustering algorithms, New York: Wiley.
Hartigan, J. A. (1976). Model blocks in definition of west coast mammals.Systematic Zoology, 25, 149–160.
Hartigan, J. A. (1967). Representation of similarity matrices by trees.Journal of the American Statistical Association, 62, 1140–1158.
Johnson, S. C. (1967). Hierarchical clustering schemes.Psychometrika, 32, 241–254.
McCormick, W. T., Schweitzer, P. J., and White, T. W. (1972). Problem decomposition and data reorganization by a clustering technique,Operations Research, 20, 993–1009.
Miller, G. A., and Nicely, P. E. (1955). An analysis of perceptual confusions among some English consonants.Journal of the Acoustical Society of America, 27, 338–352.
Powell, M. J. D. (1977). Restart procedures for the conjugate gradient method.Mathematical Programming, 12, 241–254.
Pruzansky, S., Tversky, A., and Carroll, J. D. (1982). Spatial versus tree representations of proximity data.Psychometrika, 47, 3–24.
Rao, S. S. (1979).Optimization theory and applications. New York: Wiley.
Sattath, S. and Tversky, A. (1977). Additive similarity trees.Psychometrika, 42, 319–345.
Shepard, R. N. (1972). Psychological representation of speech sounds. In E. E. David and P. B. Denes (eds.),Human communication: A unified view. New York: McGraw Hill.
Shepard, R. N. and Arabie, P. (1979). Additive clustering: Representation of similarities as combination of discrete overlapping properties.Psychological Review, 86, 87–123.
Snedecor, G. W. and Cochran, W. G. (1981).Statistical methods, 7th edition, Ames, Iowa: Iowa State University Press.
Sonquist, J. A. (1971).Multivariate model building: the validation of a search strategy. Institute for Social Research, University of Michigan, Ann Arbor, Michigan.
Tryon, R. C. and Bailey, D. E. (1970).Cluster analysis. New York: McGraw Hill.
Wold, H., (1966). Estimation of principal components and related models by iterative least squares. In P. R. Krishnaiah (Ed.),Multivariate analysis. New York: Academic Press.
Author information
Authors and Affiliations
Additional information
G. De Soete is “Aspirant” of the Belgian “Nationaal Fonds voor Wetenschappelijk Onderzoek” at the University of Ghent, Belgium. W. S. DeSarbo and J. D. Carroll are Members of Technical Staff at AT&T Bell Laboratories, Murray Hill, N.J. G. W. Furnas is Member of Technical Staff at Bell Communications Research, Murray Hill, N.J.
Rights and permissions
About this article
Cite this article
De Soete, G., DeSarbo, W.S., Furnas, G.W. et al. The estimation of ultrametric and path length trees from rectangular proximity data. Psychometrika 49, 289–310 (1984). https://doi.org/10.1007/BF02306021
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02306021