Hostname: page-component-5f745c7db-96s6r Total loading time: 0 Render date: 2025-01-06T07:44:17.026Z Has data issue: true hasContentIssue false
  • English
  • Français

A Parametric Procedure for Ultrametric Tree Estimation from Conditional Rank Order Proximity Data

Published online by Cambridge University Press:  01 January 2025

Martin R. Young  and
Wayne S. DeSarbo
Martin R. Young*
Affiliation:
Statistics Department, School of Business Administration, University of Michigan
Wayne S. DeSarbo
Affiliation:
Marketing and Statistics Departments School of Business Administration, University of Michigan
*
Requests for reprints should be sent to Martin R. Young, Statistics Department, School of Business Administration, University of Michigan, Ann Arbor, MI 48109-1234.
Get access Rights & Permissions [Opens in a new window]

Abstract

The psychometric and classification literatures have illustrated the fact that a wide class of discrete or network models (e.g., hierarchical or ultrametric trees) for the analysis of ordinal proximity data are plagued by potential degenerate solutions if estimated using traditional nonmetric procedures (i.e., procedures which optimize a STRESS-based criteria of fit and whose solutions are invariant under a monotone transformation of the input data). This paper proposes a new parametric, maximum likelihood based procedure for estimating ultrametric trees for the analysis of conditional rank order proximity data. We present the technical aspects of the model and the estimation algorithm. Some preliminary Monte Carlo results are discussed. A consumer psychology application is provided examining the similarity of fifteen types of snack/breakfast items. Finally, some directions for future research are provided.

Keywords

hierarchical clusteringproximity dataconditional rank ordersmaximum likelihood estimationconsumer psychology
Type
Original Paper
Information
Psychometrika , Volume 60 , Issue 1 , March 1995 , pp. 47 - 75
Copyright
Copyright © 1995 The Psychometric Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abe, M. (1993). Issues in maximum likelihood multidimensional scaling, Chicago, IL: University of Illinois.Google Scholar
Barthélemy, J. P., Guénoche, A. (1991). Trees and proximity representations, New York: John Wiley & Sons.Google Scholar
Bozdogan, H. (1987). Model selection and Akaike's information criterion (AIC): The general theory and its analytical extensions. Psychometrika, 52, 345–370.CrossRefGoogle Scholar
Carroll, J. D. (1976). Spatial, non-spatial and hybrid models for scaling. Psychometrika, 41, 439–463.CrossRefGoogle Scholar
Carroll, J. D. (1989). Degenerate solutions in the non-metric fitting of a wide class of models for proximity data (Technical Memorandum), Murray Hill, NJ: Bell Laboratories.Google Scholar
Carroll, J. D., Arabie, P. (1980). Multidimensional scaling. Annual Review of Psychology, 31, 607–649.CrossRefGoogle ScholarPubMed
Carroll, J. D., Chang, J. J. (1970). Analysis of individual differences in multidimensional scaling via an N-way generalization of “Eckart-Young” decomposition. Psychometrika, 35, 285–319.CrossRefGoogle Scholar
Carroll, J. D., Clark, L., DeSarbo, W. S. (1984). The representation of three-way proximities data by single and multiple tree structure models. Journal of Classification, 1, 25–74.CrossRefGoogle Scholar
Carroll, J. D., & Pruzansky, S. (1975, August). Fitting of hierarchical tree structure (HTS) models, mixtures of HTS models, and hybrid models, via mathematical programming and alternating least squares. Paper presented at U.S.-Japan Seminar of Multidimensional Scaling, University of California at San Diego, La Jolla, California.Google Scholar
Carroll, J. D., Pruzansky, S. (1980). Discrete and hybrid scaling models. In Lantermann, E. D., Feger, H. (Eds.), Similarity and choice (pp. 48–69). Bern: Hans Huber.Google Scholar
Chandon, J. L., Lemaire, J., Pouget, J. (1980). Construction de l'ultramétrique la plus proche d'une dissimilarité au sens des moindres carrés [The construction of ultrametric trees from dissimilarity matrices]. R.A.I.R.O., Recherche Operationelle, 14, 157–170.Google Scholar
Chapman, R., Staelin, R. (1982). Exploiting rank ordered choice set data within the stochastic utility model. Journal of Marketing Research, 19, 288–301.CrossRefGoogle Scholar
Coombs, C. H. (1964). A theory of data, New York: John Wiley & Sons.Google Scholar
Corter, J. E., Tversky, A. (1986). Extended similarity trees. Psychometrika, 51, 429–451.CrossRefGoogle Scholar
Cox, D. R. (1972). Regression models and life tables (with discussion). Journal of the Royal Statistical Society, Series B, 34, 187–202.CrossRefGoogle Scholar
Critchlow, D. E., Filgner, M. A., & Verducci, J. S. Probability models on rankings. Journal of Mathematical Psychology, 35, 294–318.CrossRefGoogle Scholar
Cunningham, J. P. (1974, August). Finding the optimal tree realization of a proximity matrix. Paper presented at the Mathematical Psychology Meetings, Ann Arbor, MI.Google Scholar
Cunningham, J. P. (1978). Free trees and bidirectional trees as a representation of psychological distance. Journal of Mathematical Psychology, 17, 165–188.CrossRefGoogle Scholar
DeSarbo, W. S., De Soete, G., Carroll, J. D., Ramaswamy, V. (1988). A new stochastic ultrametric tree unfolding methodology for assessing competitive market structure and deriving market segments. Applied Stochastic Models & Data Analysis, 4, 185–204.CrossRefGoogle Scholar
DeSarbo, W. S., Manrai, A. K., Burke, R. (1990). A non-spatial methodology for the analysis of a two-way proximity data incorporating the distance-density hypothesis. Psychometrika, 55, 229–253.CrossRefGoogle Scholar
DeSarbo, W. S., Manrai, A., & Manrai, L. (in press). Mathematical programming approaches for the nonspatial assessment of competitive market structure: An integrated review of the marketing and psychometric literature. In Lilien, G. & Eliashberg, J. (Eds.), Marketing models. New York: Kluwer Pub.Google Scholar
De Soete, G. (1983). Are nonmetric additive-tree representations of numerical proximity data meaningful?. Quality and Quantity, 13, 475–478.CrossRefGoogle Scholar
De Soete, G. (1983). A least-squares algorithm for fitting trees to proximity data. Psychometrika, 48, 621–626.CrossRefGoogle Scholar
De Soete, G. (1984). A least-squares algorithm for fitting an ultrametric tree to a dissimilarity matrix. Pattern Recognition Letters, 2, 133–137.CrossRefGoogle Scholar
De Soete, G., Carroll, J. D., DeSarbo, W. S. (1987). Least squares algorithms for constructing constrained ultrametric and additive tree representations of symmetric proximity data. Journal of Classification, 4, 155–174.CrossRefGoogle Scholar
De Soete, G., DeSarbo, W. S., Furnas, G. W., Carroll, J. D. (1984). Tree representations of rectangular proximity matrices. In Degreef, E., Van Buggenhaut, J. (Eds.), Trends in mathematical psychology, Amsterdam: North-Holland.Google Scholar
De Soete, G., DeSarbo, W. S., Furnas, G. W., Carroll, J. D. (1984). The estimation of ultrametric and path length trees from rectangular proximity data. Psychometrika, 49, 289–310.CrossRefGoogle Scholar
Dobson, J. (1974). Unrooted trees for numerical taxonomy. Journal of Applied Probability, 11, 32–42.CrossRefGoogle Scholar
Dubes, R., Jain, A. K. (1979). Validity studies in clustering methodologies. Pattern Recognition, 11, 235–254.CrossRefGoogle Scholar
Farris, J. S. (1972). Estimating phylogenetic trees from distance matrices. American Naturalist, 106, 645–668.CrossRefGoogle Scholar
Fiacco, A. V., McCormick, G. P. (1968). Nonlinear programming, New York: John Wiley & Sons.Google Scholar
Fletcher, R. (1987). Practical methods of optimization 2nd. ed.,, New York: John Wiley & Sons.Google Scholar
Fligner, M. S., Verducci, J. S. (1988). Multistage ranking models. Journal of the American Statistical Association, 83, 892–901.CrossRefGoogle Scholar
Fligner, M. A., Verducci, J. S. (1993). Probability models and statistical analyses for ranking data, New York: Springer-Verlag.CrossRefGoogle Scholar
Furnas, G. W. (1980). Objects and their features: The metric representation of two class data. Unpublished doctoral dissertation, Stanford University.Google Scholar
Green, P. E., Rao, V. R. (1972). Multidimensional scaling, Hinsdale, IL: Dryden Press.Google Scholar
Guttman, L. A. (1968). A general nonmetric technique for finding the smallest coordinate space for a configuration of points. Psychometrika, 33, 469–506.CrossRefGoogle Scholar
Hartigan, J. A. (1967). Representation of similarity matrices by trees. Journal of the American Statistical Association, 62, 1140–1156.CrossRefGoogle Scholar
Hartigan, J. A. (1975). Clustering algorithms, New York: John Wiley & Sons.Google Scholar
Hausman, J. A., Ruud, P.A. (1987). Specifying and testing econometric models for rank-ordered data. Journal of Econometrics, 34, 83–104.CrossRefGoogle Scholar
Holman, E. W. (1972). The relation between hierarchical and Euclidean models for psychological distances. Psychometrika, 37, 417–423.CrossRefGoogle Scholar
Jardine, C. J., Jardine, N., Sibson, R. (1967). The structure and construction of taxonomic hierarchies. Mathematical BioScience, 1, 173–179.CrossRefGoogle Scholar
Johnson, S. C. (1967). Hierarchical clustering schemes. Psychometrika, 32, 241–254.CrossRefGoogle ScholarPubMed
Kalbfleisch, J. D., Prentice, R. L. (1973). Marginal likelihoods based on Cox's regression and life model. Biometrika, 60, 267–279.CrossRefGoogle Scholar
Katahira, H. (1990). Perceptual mapping using ordered logit analysis. Marketing Science, 9, 1–17.CrossRefGoogle Scholar
Keener, R. W., Waldman, D. M. (1985). Maximum likelihood regression of rank censored data. Journal of the American Statistical Association, 80, 385–392.CrossRefGoogle Scholar
Kruskal, J. B. (1964). Nonmetric multidimensional scaling: A numerical method. Psychometrika, 29, 115–129.CrossRefGoogle Scholar
Lawless, J. F. (1982). Statistical models and methods for lifetime data, New York: John Wiley & Sons.Google Scholar
Lehmann, E. L. (1975). Nonparametrics: Statistical methods based on ranks, San Francisco, CA: Holden-Day.Google Scholar
Panier, E. R., Tits, A. L. (1993). On combining feasibility, descent, and superlinear convergence in inequality constrained optimization. Mathematical Programming, 59, 261–276.CrossRefGoogle Scholar
Peto, R. (1972). Discussion of paper by D. R. Cox. Journal of the Royal Statistical Society, Series B, 34, 205–207.Google Scholar
Powell, M. J. D. (1977). Restart procedures for the conjugate gradient method. Mathematical Programming, 12, 241–254.CrossRefGoogle Scholar
Powell, M. J. D. (1983). ZQPCVX, A FORTRAN subroutine for convex programming (Report DAMTP/1983/NA17), Cambridge: University of Cambridge, England.Google Scholar
Press, W. H., Flannery, B. P., Teukolsky, S. A., Vetterling, W. T. (1992). Numerical recipes in C, New York: Cambridge University Press.Google Scholar
Pruzansky, S., Tversky, A., Carroll, J. D. (1982). Spatial versus tree representations of proximity data. Psychometrika, 47, 3–24.CrossRefGoogle Scholar
Ramaswamy, V., DeSarbo, W. S. (1990). SCULPTRE: A new methodology for deriving and analyzing hierarchical product-market structures from panel data. Journal of Marketing Research, 27, 418–427.CrossRefGoogle Scholar
Ramsay, J. O. (1977). Maximum likelihood estimation in multidimensional scaling. Psychometrika, 42, 241–266.CrossRefGoogle Scholar
Ramsay, J. O. (1982). Some statistical approaches to multidimensional scaling (with discussion). Journal of the Royal Statistical Society, Series A, 145, 285–312.CrossRefGoogle Scholar
Roskam, E. E. (1970). The methods of triads for multidimensional scaling. Nederlands Tijdschrift Voor de Psychologie en haar grensgebieden, 25, 404–417.Google Scholar
Ryan, D. M. (1974). Penalty and barrier functions. In Gill, P. E., Murray, W. (Eds.), Numerical methods for constrained optimization (pp. 175–190). New York: Academic Press.Google Scholar
Schittkowski, (1986). QLD—A FORTRAN code for quadratic programming, User's Guide, Bayreuth, Germany: Universität of Bayreuth, Mathematisches Institut.Google Scholar
Schwartz, G. (1978). Estimating the dimension of a model. Annals of Statistics, 6, 461–464.Google Scholar
Shepard, R. N. (1962). The analysis of proximities: Multidimensional scaling with an unknown distance function, I and II. Psychometrika, 27, 125–140.CrossRefGoogle Scholar
Shepard, R. N. (1980). Multidimensional scaling, tree-fitting, and clustering. Science, 210, 390–398.CrossRefGoogle ScholarPubMed
Takane, Y., Carroll, J. D. (1981). Nonmetric maximum likelihood multidimensional scaling from directional rankings of similarities. Psychometrika, 46, 389–405.CrossRefGoogle Scholar
Torgerson, W. W. (1952). Multidimensional scaling: Theory and method. Psychometrika, 17, 401–419.CrossRefGoogle Scholar
Tversky, A., Sattath, S. (1979). Preference trees. Psychological Review, 84, 327–352.CrossRefGoogle Scholar
Ward, J. H. (1963). Hierarchical groupings to optimize an objective function. Journal of American Statistical Association, 58, 236–244.CrossRefGoogle Scholar
Winsberg, S., Carroll, J. D. (1989). A quasi-nonmetric method for multidimensional scaling via a restricted case of an extended INDSCAL model. In Coppi, R., Bolasco, S. (Eds.), Multiway data analysis (pp. 405–414). Amsterdam: North Holland.Google Scholar
Young, F. W. (1975). Scaling replicated conditional rank-order data. Sociological Methodology, 12, 129–170.CrossRefGoogle Scholar
Young, F. W. (1987). Data theory. In Hamer, R. M. (Eds.), Multi-dimensional Scaling: History, theory and applications (pp. 43–66). Hillsdale, NJ: Lawrence Erlbaum Associates.Google Scholar
Young, F. W., Torgerson, W. S. (1967). TORSCA: A FORTRAN IV program for Shepard-Kruskal multidimensional scaling analysis. Behavioral Science, 12, 498–498.Google Scholar
Zhou, J. L., & Tits, A. L. (1993). User's guide for FSQP Version 3.3: A FORTRAN code for solving constrained nonlinear (minimax) optimization problems, generating iterates satisfying all inequality and linear constraints (Tech. Rep.). College Park, MD: University of Maryland, Department of Electrical Engineering.Google Scholar