6. Additive Trees for Symmetric Proximity Data
Society for Industrial and Applied Mathematics eBooks · 2006
A currently popular alternative to the use of a simple ultrametric in classification, and one which might be considered a natural extension of the notion of an ultrametric, is that of an additive tree; comprehensive discussions can be found in Mirkin (1996, Chapter 7) or throughout Barthélemy and Guénoche (1991). Generalizing the earlier characterization of an ultrametric, an n × n matrix A = {aij} can be called an additive tree (metric or matrix) if the three-object (or three-point) ultrametric condition is replaced by a four-object (or four-point) condition: aij+akl ≤ max{aik+ajl, ail+ajk} for 1 ≤ i, j, k,l ≤n; equivalently, for any object quadruple Oi, Oj, Ok, and Ol, the largest two values among the sums aij + akl, aik + ajl, and ail + ajk must be equal. Any additive tree matrix A can be represented (in many ways) as a sum of two matrices, say U = {uij} and C = {cij}, where U is an ultrametric matrix, and cij = gi + gj for 1 ≤ i ≠ j ≤ n and cii = 0 for 1 ≤ i ≤ n, based on some set of values g1,… ,gn (Carroll, Clark, and DeSarbo, 1984, pp. 71–72). The multiplicity of such possible decompositions results from the choice of where essentially to place the root in the type of graphical tree representation we will use. Generally, for us, the root will be placed halfway along the longest path in the tree, generating a decomposition of the matrix A using a procedure from Barthélemy and Guénoche (1991, Section 3.3.3): (a) Given A, let Oi*, Oj* ∈ S denote the two objects between which the longest path is defined in the tree; i.e., the pair of objects Oi* and Oj* is associated with the largest entry in A, say ai*j*. (b) Define U by letting uij = aij − ( gi + gj ), where gi =max { aii* , ajj* }−M , with M chosen so that uij > 0 for i ≠ j. The matrix C = {cij} is then constructed by letting cii = 0 for 1 ≤ i ≤ n, and cij = gi + gj for 1 ≤ i ≠ j ≤ n. (If M is set equal to the largest entry ai*j*, the values in U would have to be positive, and two values among g1,…, gn would be zero with the remainder less than or equal to zero. Thus, a value for M less than ai*j* is usually found by trial and error that will give positive entries within U and as many positive values as possible for g1,…, gn.)