II The Representation of Proximity Matrices by Tree Structures
2006
Introduction to Graph-Theoretic Representational Structures Various methods of data representation based on graph-theoretic structures have been developed over the last several decades for explaining the pattern of information potentially present in a single (or possibly in a collection of) numerically given proximity matri(ces), each defined between pairs of objects from a single set or, in some cases, between the objects from several distinct sets (for example, see Carroll, 1976; Carroll, Clark, and De- Sarbo, 1984; Carroll and Pruzansky, 1980; De Soete, 1983, 1984a,b,c; De Soete, Carroll, and DeSarbo, 1987; De Soete et al., 1984; Hutchinson, 1989; Klauer and Carroll, 1989, 1991; Hubert and Arabie, 1995b). Typically, a specific class of graph-theoretic structures is assumed capable of representing the proximity information, and the proposed method seeks a member from the class producing a reconstructed set of proximities that are as close as possible to the original. The most prominent graph-theoretic structures used are those usually referred to as ultrametrics and additive trees, and these will be the primary emphasis here as well. Although a variety of strategies have been proposed for locating good exemplars from whatever class of graph-theoretic structures is being considered, one approach has been to adopt a least-squares criterion in which the class exemplar is identified by attempting to minimize the sum of squared discrepancies between the original proximities and their reconstructions obtained through the use of the particular structure selected by the data analyst. One common implementation of the least-squares optimization strategy has been defined by the usual least-squares criterion but augmented by some collection of penalty functions that seek to impose whatever constraints are mandated by the structural representation being sought. Then, through the use of some unconstrained optimization scheme (e.g., steepest descent, conjugate gradients), an attempt is made to find both (a) the particular constraints that should be imposed to define the specific structure from the class and (b) the reconstructed proximities based on the structure finally identified. The resulting optimization strategy is heuristic in the sense that there is no guarantee of global optimality for the final structural representation identified even within the chosen graph-theoretic class, because the particular constraints defining the selected structure were located by a possibly reasonable but not verifiably optimal search strategy that was (implicitly) implemented in the course of the process of optimization.