This paper presents two approaches to quantifying and visualizing variation in datasets of trees. The first approach localizes subtrees in which significant population differences are found through hypothesis testing and sparse classifiers on subtree features. The second approach visualizes the global metric structure of datasets through low-distortion embedding into hyperbolic planes in the style of multidimensional scaling. A case study is made on a dataset of airway trees in relation to Chronic Obstructive Pulmonary Disease.
All of these methods approach visualization through embedding into a Euclidean space in a low-distortion way. However, embedding spaces need not be restricted to only Euclidean spaces. For instance, low-distortion embedding of a general metric into a tree has been considered for various measures of distortion @cite_28 @cite_2 . Low-distortion embedding of general metrics into hyperbolic spaces has also been considered by @cite_35 @cite_37 and Cvetkovski and Crovella @cite_8 . In this paper, we use hyperbolic MDS for more truthful visualizations of tree variation.
@cite_35 @cite_37 @cite_8 @cite_28 @cite_2
2020141201 2169504875 1834815371 2009861473
We introduce a novel projection-based visualization method for high-dimensional data sets by combining concepts from MDS and the geometry of the hyperbolic spaces. This approach hyperbolic multi-dimensional scaling (H-MDS) is a synthesis of two important concepts for explorative data analysis and visualization: (i) multi-dimensional scaling uses proximity or pair distance data to generate a low-dimensional, spatial presentation of the data; (ii) previous work on the "hyperbolic tree browser" demonstrated the extraordinary advantages for an interactive display of graph-like data in the two-dimensional hyperbolic space (H2).In the new approach, H-MDS maps proximity data directly into the H2. This removes the restriction to "quasihierarchical", graph-based data--a major limitation of (ii). Since a suitable distance function can convert all kinds of data to proximity (or distance-based) data, this type of data can be considered the most general.We review important properties of the hyperbolic space and, in particular, the circular Poincare model of the H2. It enables effective human-computer interaction: by mouse dragging the "focus", the user can navigate in the data without loosing the context. In H2 the "fish-eye" behavior originates not simply by a non-linear view transformation but rather by extraordinary, non-Euclidean properties of the H2. Especially, the exponential growth of length and area of the underlying space makes the H2 a prime target for mapping hierarchical and (now also) high-dimensional data.Several high-dimensional mapping examples including synthetic and real-world data are presented. Since high-dimensional data produce "ring"-shaped displays, we present methods to enhance the display by modulating the dissimilarity contrast. This is demonstrated for an application for unstructured text: i.e., by using multiple film critiques from news:rec.art.movies.reviews and www.imdb.com, each movie is placed within the H2--creating a "space of movies" for interactive exploration. We propose a novel projection based visualization method for high-dimensional datasets by combining concepts from MDS and the geometry of the hyperbolic spaces. Our approach Hyperbolic Multi-Dimensional Scaling (H-MDS) extends earlier work [7] using hyperbolic spaces for visualization of tree structures data ( "hyperbolic tree browser" ).By borrowing concepts from multi-dimensional scaling we map proximity data directly into the 2-dimensional hyperbolic space (H2). This removes the restriction to "quasihierarchical", graph-based data -- limiting previous work. Since a suitable distance function can convert all kinds of data to proximity (or distance-based) data this type of data can be considered the most general.We used the circular Poincare model of the H2 which allows effective human-computer interaction: by moving the "focus" via mouse the user can navigate in the data without loosing the "context". In H2 the "fish-eye" behavior originates not simply by a non-linear view transformation but rather by extraordinary, non-Euclidean properties of the H2. Especially, the exponential growth of length and area of the underlying space makes the H2 a prime target for mapping hierarchical and (now also) high-dimensional data.We present several high-dimensional mapping examples including synthetic and real world data and a successful application for unstructured text. By analyzing and integrating multiple film critiques from news:rec.art.movies.reviews and the internet movie database, each movie becomes placed within the H2. Here the idea is, that related films share more words in their reviews than unrelated. Their semantic proximity leads to a closer arrangement. The result is a kind of high-level content structured display allowing the user to explore the "space of movies". Multidimensional scaling (MDS) is a class of projective algorithms traditionally used in Euclidean space to produce two- or three-dimensional visualizations of datasets of multidimensional points or point distances. More recently however, several authors have pointed out that for certain datasets, hyperbolic target space may provide a better fit than Euclidean space. In this paper we develop PD-MDS, a metric MDS algorithm designed specifically for the Poincare disk (PD) model of the hyperbolic plane. Emphasizing the importance of proceeding from first principles in spite of the availability of various black box optimizers, our construction is based on an elementary hyperbolic line search and reveals numerous particulars that need to be carefully addressed when implementing this as well as more sophisticated iterative optimization methods in a hyperbolic space model. We consider the problem of embedding general metrics into trees. We give the first non-trivial approximation algorithm for minimizing the multiplicative distortion. Our algorithm produces an embedding with distortion (c log n)O(√log Δ), where c is the optimal distortion, and Δ is the spread of the metric (i.e. the ratio of the diameter over the minimum distance). We give an improved O(1)-approximation algorithm for the case where the input is the shortest path metric over an unweighted graph. Moreover, we show that by composing our approximation algorithm for embedding general metrics into trees, with the approximation algorithm of [BCIS05] for embedding trees into the line, we obtain an improved approximation algorithm for embedding general metrics into the line. We also provide almost tight bounds for the relation between embedding into trees and embedding into spanning subtrees. We show that for any unweighted graph G, the ratio of the distortion required to embed G into a spanning subtree, over the distortion of an optimal tree embedding of G, is at most O(log n). We complement this bound by exhibiting a family of graphs for which the ratio is Ω(log n log log n).