Ultrametric distance

In the previous discussion we have broadly compared trees generated from widely differing character sets. For each tree, a matrix of ultrametric distance values has been computed in order to test the goodness of fit of the cluster analyses to the data (Rohlf and Sokal, 1981). The resultant coefficients of cophenetic correlation indicated very good fits (r > 0.9) for all tested trees with the exception of the tree based on body... 

Figure 2. An illustration of the ultrametric tree formed by locally optimal paths from the apex to the base of a 1 + 1 dimensionaJ delta. Three non-intersecting paths are drawn to schematically represent the directed optim ll paths from O to the sites A, A2 and A3. The ultrametric distances between these three sites on the base have the relation U(Ai,A2) = U(A3,Ai) > U(A2, A3) which is the same as the relation in Eq. (22).

The reason stratified hierarchies are so interesting is the flexibility they offer in hierarchy generation and segmentation. In particular, the combined use of stratified hierarchies and ultrametric distances, enables efficient generation of hierarchies based on any properties of interest. 

For a stratified hierarchy A, with stratification index value 0 for its finest partition, the following represents an ultrametric distance index. 

This is where the stratified hierarchy, with its ultrametric distance comes into play. If we are able to define a dissimilarity measure based on the attributes of interest, that respects the features of interest, we will be able to generate a hierarchy. Hence, we now have the means to generate tailor made hierarchies, and thus segmentations, respecting the important properties of the data. 

Two popular distance metrics are the Manhattan distance metric (r = 1), which represents the sum of the absolute descriptor differences, and the ultrametric (r = °o), which represents the maximum absolute descriptor difference. Both the Manhattan and Euclidean distance metrics obey all four metric properties. 

The following constitutes the definition of the distance between two points in an ultrametric space. The points in an ultrametric space on a given hierarchical level are the ends of the Cayley tree branches (Fig. 13). The number of points on the rath level of the Cayley tree is equal to Nn = j". Each point on the nth level can be numbered ... 

The distance between two points in the ultrametric space is defined by the number of steps from these points to the common limit. For example, the distance between points 00 and 03 equals 1, and the distance between points 02 and 12 equals 2 (Fig. 13). Thus, the distance between two points in the ultrametric space with coordinates given by w-digit numbers in the /-digit system of calculation only depends on which digit these numbers first differ and does not depend on the specific values of this difference. 

The points of the discrete ultrametric space (Cayley tree junctions) on the nth level, namely, N , are divided into clusters (groups). Each cluster contains j points the distance between which is / = 1 and has its progenitor on the (.n — l)th level. The number of such clusters is N /j = jn l ... 

The unity of clusters corresponds to an arbitrary distance l between points in the ultrametric space. All points are united in j subclusters with distance l — 1 and having/ points. Thus, the group of clusters formed on the hierarchical level n — 1 corresponds to an arbitrary distance l. If the limit transition is made when n —> oo, then the number of the points attaining level n approaches infinity (Nn —y oo) that is, the intervals between points Ax = 1/Nn become infinitely small, and the ultrametric space itself becomes continuous. On the Cayley free, the transition to a continuous ultrametric space indicates a condensation of the hierarchical levels. 

The distance between two points in an ultrametric space in the conventional Euclidean sense can be defined as... 

The hierarchical chain of changes from the initial state (t = 0) to the final one (t —> oo) can be compared to a Cayley tree [25,26] (see Fig. 64). Here, the knots of the Cayley tree will correspond to static ensembles a and p which correspond to the dots in ultrametric space divided by the distance lap. 

The value of lap is defined by the number of steps over the levels of the Cayley tree up to the mutual knot in Fig. 64 and it yields the extent of a hierarchical link. Therefore, both the barrier height, Qap, and the relaxation time, xap, are connected with functions of the distance lap in ultrametric space, that is,... 

---