The Structural Representation of Proximity Matrices with MATLAB ASA-SIAM Series on Statistics and Applied Probability ABA SIAM The ASA-SIAM Series on Statistics and Applied Probability is published SIAM jointly by the American Statistical Association and the Society for Industrial and Applied Mathematics. The series consists of a broad spectrum of books on topics in statistics and applied probability. The purpose of the series is to provide inexpensive, quality publications of interest to the intersecting membership of the two societies. Editorial Board Martin T. Wells Lisa LaVange Cornell University, Editor-in-Chief University of North Carolina H. T. Banks David Madigan North Carolina State University Rutgers University Joseph Gardiner Francoise Seillier-Moiseiwitsch Michigan State University Georgetown University Douglas M. Hawkins Mark van der Laan University of Minnesota University of California, Berkeley Susan Holmes Stanford University Hubert, L, Arabie, P., and Meulman, }., The Structural Representation of Proximity Matrices with MATLAB Nelson, P. R., Wludyka, P. S., and Copeland, K. A. R, The Analysis of Means: A Graphical Method for Comparing Means, Rates, and Proportions Burdick, R. K., Borror, C. M., and Montgomery, D. C, Design and Analysis of Gauge R&R Studies: Making Decisions with Confidence Intervals in Random and Mixed ANOVA Models Albert, )., Bennett, ]., and Cochran, J. ]., eds., Anthology of Statistics in Sports Smith, W. R, Experimental Design for Formulation Baglivo, J. A., Mathematica Laboratories for Mathematical Statistics: Emphasizing Simulation and Computer Intensive Methods Lee, H. K. H., Bayesian Nonparametrics via Neural Networks O'Gorman, T. W., Applied Adaptive Statistical Methods: Tests of Significance and Confidence Intervals Ross, T. j., Booker, J. M., and Parkinson, W. j., eds., Fuzzy Logic and Probability Applications: Bridging the Cap Nelson, W. B., Recurrent Events Data Analysis for Product Repairs, Disease Recurrences, and Other Applications Mason, R. L. and Young, J. C, Multivariate Statistical Process Control with Industrial Applications Smith, P. L., A Primer for Sampling Solids, Liquids, and Cases: Based on the Seven Sampling Errors of Pierre Gy Meyer, M. A. and Booker, J. M., Eliciting and Analyzing Expert judgment: A Practical Guide Latouche, G. and Ramaswami, V., Introduction to Matrix Analytic Methods in Stochastic Modeling Peck, R., Haugh, L., and Goodman, A., Statistical Case Studies: A Collaboration Between Academe and Industry, Student Edition Peck, R., Haugh, L., and Goodman, A., Statistical Case Studies: A Collaboration Between Academe and Industry Barlow, R., Engineering Reliability Czitrom, V. and Spagon, P. D., Statistical Case Studies for Industrial Process Improvement The Structural Representation of Proximity Matrices with MATLAB Lawrence Hubert University of Illinois Champaign, Illinois Phipps Arable Rutgers Business School of Newark and New Brunswick Newark, New Jersey Jacqueline Meulman Leiden University Leiden, The Netherlands slam. Society tor Industrial and Applied Mathematics American Statistical Association Philadelphia, Pennsylvania Alexandria, Virginia The correct bibliographic citation for this book is as follows: Hubert, Lawrence, Phipps Arabie, and Jacque- line Meulman, The Structural Representation of Proximity Matrices with MATLAB, ASA-SIAM Series on Statistics and Applied Probability, SIAM, Philadelphia, ASA, Alexandria, VA, 2006. Copyright © 2006 by the American Statistical Association and the Society for Industrial and Applied Mathematics. 10987654321 All rights reserved. Printed in the United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688. Trademarked names may be used in this book without the inclusion of a trademark symbol. These names are intended in an editorial context only; no infringement of trademark is intended. MATLAB® is a trademark of The MathWorks, Inc. and is used with permission. The MathWorks does not warrant the accuracy of the text or exercises in this book. This book's use or discussion of MATLAB® software or related products does not constitute endorsement or sponsorship by The MathWorks of a particular pedagogical approach or particular use of the MATLAB® software. For MATLAB® product information, please contact: The MathWorks, Inc., 3 Apple Hill Drive, Natick, MA 01760-2098 USA, 508-647-7000, Fax: 508-647-7101, [email protected], www.mathworks.com/ NAG is a registered trademark of the Numerical Algorithms Group. SPSS Categories is a trademark of SPSS, Inc. SYSTAT is a registered trademark of Systat Software, Inc. The research reported in this monograph has been partially supported by the National Science Foundation through grant SES-981407 (to Lawrence Hubert) and by the Netherlands Organization for Scientific Research (NWO) through grant 575-67-053 for the "PIONEER" project "Subject Oriented Multivariate Analysis" (to Jacqueline Meulman). Library of Congress Cataloging-!n-Publication Data Hubert, Lawrence J., 1944- The structural representation of proximity matrices with MATLAB / Lawrence Hubert, Phipps Arabie, Jacqueline Meulman. p. cm. — (ASA-SIAM series on statistics and applied probability) Includes bibliographical references and index. ISBN 0-89871-607-1 (pbk.) 1. Proximity matrices. 2. Functions. 3. Representation of graphs. 4. MATLAB. I. Arabie, Phipps. II. Meulman, Jacqueline. III. Title. IV. Series. QA195.H83 2006 512.9'434-dc22 2006042210 • SIAamM. is ais a registered trademark. Dedicated to Frank B. Baker (by Lawrence Hubert) Richard C Atkinson (by Phipps Arable) John P. Van de Ceer (by Jacqueline Meulman) This page intentionally left blank Contents List of Figures xi List of Tables xiii Preface xv I (Multi- and Unidimensional) City-Block Scaling 1 1 Linear Unidimensional Scaling 3 1.1 LUS hither-Norm 4 1.1.1 A Data Set for Illustrative Purposes 5 1.2 L Optimization Methods 5 2 1.2.1 Iterative Quadratic Assignment 6 1.3 Confirmatory and Nonmetric LUS 11 1.3.1 The Confirmatory Fitting of a Given Order Using linfit.m . . 12 1.3.2 The Monotonic Transformation of a Proximity Matrix Using proxmon.m 13 1.4 The Dykstra-Kaczmarz Method 17 2 Linear Multidimensional Scaling 19 2.1 The Incorporation of Additive Constants in LUS 20 2.1.1 The L Fitting of a Single Unidimensional Scale (with an 2 Additive Constant) 21 2.2 Finding and Fitting Multiple Unidimensional Scales 24 2.3 Incorporating Monotonic Transformations of a Proximity Matrix ... 27 2.4 Confirmatory Extensions to City-Block Individual Differences Scaling 29 3 Circular Scaling 31 3.1 The Mechanics of CUS 32 3.1.1 The Estimation of c and {|x —x|,xo, JCQ — \Xj — x,;\} for a Fixed j i Permutation and Set of Inflection Points 33 3.1.2 Obtaining Object Orderings and Inflection Points around a Closed Continuum 34 vii viii Contents 3.1.3 The CUS Utilities, cirfit.m and cirfitac.m 35 3.2 Circular Multidimensional Scaling 43 4 LUS for Two-Mode Proximity Data 47 4.1 Reordering Two-Mode Proximity Matrices 48 4.2 Fitting a Two-Mode Unidimensional Scale 49 4.3 Multiple LUS Reorderings and Fittings 54 4.4 Some Useful Two-Mode Utilities 58 4.5 Two-Mode Nonmetric Bidimensional Scaling 59 II The Representation of Proximity Matrices by Tree Structures 63 5 Ultrametrics for Symmetric Proximity Data 67 5.1 Fitting a Given Ultrametric in the L -Norm 69 2 5.2 Finding an Ultrametric in the L -Norm 70 2 5.3 Graphically Representing an Ultrametric 72 5.3.1 LATE Code for the Dendrogram of Figure 5.1 76 5.3.2 Plotting the Dendrogram with ultraplot.m 78 6 Additive Trees for Symmetric Proximity Data 81 6.1 Fitting a Given Additive Tree in the L2-Norm 82 6.2 Finding an Additive Tree in the L2-Norm 83 6.3 Decomposing an Additive Tree 85 6.4 Graphically Representing an Additive Tree 87 6.5 An Alternative for Finding an Additive Tree in the L2-Norm (Based on Combining a Centroid Metric and an Ultrametric) 88 7 Fitting Multiple Tree Structures to a Symmetric Proximity Matrix 93 7.1 Multiple Ultrametrics 93 7.2 Multiple Additive Trees 95 8 Ultrametrics and Additive Trees for Two-Mode (Rectangular) Proximity Data 99 8.1 Fitting and Finding Two-Mode Ultrametrics 100 8.2 Finding Two-Mode Additive Trees 102 8.3 Completing a Two-Mode Ultrametric to One Defined on S U S . . . 105 A B 8.3.1 The goldfish_receptor Data 109 III The Representation of Proximity Matrices by Structures Dependent on Order (Only) 111 9 Anti-Robinson Matrices for Symmetric Proximity Data 115 9.0.1 Incorporating Transformations 116 9.0.2 Interpreting the Structure of an AR Matrix 117 9.1 Fitting a Given AR Matrix in the L2-Norm 119 Contents ix 9.1.1 Fitting the (In)equality Constraints Implied by a Given Matrix in the L -Norm 120 2 9.2 Finding an AR Matrix in the L -Norm 121 2 9.3 Fitting and Finding an SAR Matrix in the L2-Norm 124 9.4 The Use of Optimal Transformations and the M-Function proxmon.m 126 9.5 Graphically Representing SAR Structures 131 9.6 Representation Through Multiple (Strongly) AR Matrices 136 10 Circular Anti-Robinson Matrices for Symmetric Proximity Data 143 10.1 Fitting a Given CAR Matrix in the L -Norm 145 2 10.2 Finding a CAR Matrix in the L -Norm 146 2 10.3 Finding a CSAR Matrix in the L -Norm 148 2 10.4 Graphically Representing CSAR Structures 151 10.5 Representation Through Multiple (Strongly) CAR Matrices 151 11 Anti-Robinson Matrices for Two-Mode Proximity Data 159 11.1 Fitting and Finding Two-Mode AR Matrices 159 11.2 Multiple Two-Mode AR Reorderings and Fittings 162 A Header Comments for the M-Files Mentioned in the Text and Given in Alphabetical Order 167 Bibliography 205 Indices 210 Author Index 210 Subject Index 212