Source-linked AI summary
Object oriented data analysis: Sets of trees
Haonan Wang, J. S. Marron
TL;DR
The paper addresses statistical analysis for complex objects in strongly non-Euclidean spaces, especially tree-structured data. It develops a rigorous mathematical framework for tree samples and demonstrates the analysis on blood vessel data, while identifying open questions about its population interpretation.
Problem
Object oriented data analysis needs methods for populations of complex objects beyond curves and Euclidean data, including strongly non-Euclidean tree-structured objects.
Method
The paper develops a definition–theorem–proof framework for analyzing samples of trees, including metrics, centerpoints, support trees, and principal structure and attribute treelines.
Results
The framework analyzes a blood vessel data set through principal structure treelines and reveals variation in root length, orientation, and branching.
Takeaways & Limitations
Tree-structured populations can be analyzed using a mathematically defined centerpoint, distance, and principal treeline framework rather than directly applying Euclidean methods.
Takeaways & Limitations
The correspondence between sample centerpoints and variation measures and theoretical population quantities remains an open future-research question.
Abstract
from arXiv · showhide
Object oriented data analysis is the statistical analysis of populations of complex objects. In the special case of functional data analysis, these data objects are curves, where standard Euclidean approaches, such as principal component analysis, have been very successful. Recent developments in medical image analysis motivate the statistical analysis of populations of more complex data objects which are elements of mildly non-Euclidean spaces, such as Lie groups and symmetric spaces, or of strongly non-Euclidean spaces, such as spaces of tree-structured data objects. These new contexts for object oriented data analysis create several potentially large new interfaces between mathematics and statistics. This point is illustrated through the careful development of a novel mathematical framework for statistical analysis of populations of tree-structured objects.
1. Introduction.
Object oriented data analysis extends statistical analysis from numbers, vectors, curves, and images to complex objects, including strongly non-Euclidean tree-structured data. This paper develops a metric-based framework for tree populations, defining centerpoints, variation, and PCA-like structures for medical imaging data.
- Motivation: Object oriented data analysis studies data sets whose statistical atoms are complex objects rather than numbers or vectors.Examples include curves in functional data analysis, images, and shape objects.
- Motivation: Medical image populations create a challenge because their objects may lie in non-Euclidean spaces where standard linear operations and Euclidean analyses are unavailable.Tree spaces lack natural definitions of linear subspaces, projections, addition, and scalar multiplication.
- Tree-space framework: The framework uses carefully chosen metrics and a Fréchet-style approach to define centerpoints for samples of trees.The resulting median-mean tree has median-like properties for the integer part of the metric and mean-like properties for its fractional part.
- Medical imaging applications: For 72 corpus callosa, ordinary PCA of feature vectors visualizes the population’s dominant variation as more versus less overall bending.This example illustrates OODA for mildly non-Euclidean shape representations before the paper turns to tree spaces.
- Medical imaging applications: Tree-structured representations are natural for branching medical structures such as blood vessels, with nodes representing vessels and edges representing connectedness.The paper’s driving application is a sample of human brain blood vessel trees containing topology and nodal attributes.
- Tree-space framework: A tree-space analog of PCA uses treelines to quantify variation, while a tree version of the Pythagorean theorem supports ANOVA-style decomposition of sums of squares.The principal structure treeline is selected to explain as much structure in the data as possible.
2. Tree OODA of a blood vessel data set.
The paper demonstrates statistical analysis of simplified human brain blood vessel trees using a centerpoint and treeline-based analogs of principal component analysis. The analysis represents structural and attribute variation, revealing dominant branching patterns and subgroup-driven variation.
- Data representation: The data comprise 11 simplified blood vessel trees from three people, with two observed three-node structures: seven Type I and four Type II trees.Each tree represents vessel connectivity and simplified branch attributes; radial information is ignored and only subtrees up to three levels and three nodes are analyzed.
- Centerpoint: Each person’s trees are summarized by a median-mean tree that is central in structure, size, and location.Individual trees are shown as thin lines, while the median-mean tree is shown with a thicker line; roots use solid lines and children use dashed lines.
- Tree variation analysis: The paper develops a tree-based analog of PCA using treelines as one-dimensional representations of tree-structured data.Structure treelines capture variation in tree topology, while attribute treelines capture variation within a fixed tree structure.
- Structural variation: The principal structure treeline shows that dominant topological variation proceeds toward adding left-hand child nodes.The treeline is selected among those passing through the median-mean tree to explain as much structural variation as possible.
- Attribute variation: The principal attribute treeline through the median-mean tree depicts marked changes in root length and orientation, including a flip of the root node.The snapshots represent movement along a fixed-structure treeline and provide a visual summary of attribute variation.
- Interpretation: The unusually short overall median-mean root reflects its central position between two subgroups with different blood-flow orientations, which may obscure biologically relevant population features.The subgroup structure dominates total variation in the sample.
3. Development of the tree OODA methodology.
The paper develops a rigorous framework for statistical analysis of binary tree populations, defining tree metrics, centerpoints, and treeline-based analogs of PCA and ANOVA. These constructions support variation analysis while accommodating topology and nodal attributes.
- Notation and preliminaries: Binary trees are represented through level-order node indices, which characterize topology and support subtree, union, intersection, and support-tree operations.A topological subtree satisfies IND(s) ⊆ IND(t); an attribute subtree additionally preserves nodal attributes.
- Central tree: Centerpoints are defined through Fréchet-style minimization, yielding median trees whose node inclusion follows majority patterns and whose attributes can use sample means.A minimizing tree must include nodes appearing in more than half the sample and may choose nodes appearing exactly half; the median-mean tree is recommended for computational speed.
- Tree metrics: The integer tree metric counts nodes present in exactly one of two trees, equivalently measuring the minimum node additions and deletions needed to transform one tree into the other.The attribute-aware metric δ extends this topological metric with a fractional component for nodal attributes and is proven to be a metric.
- Variation analysis: A tree-space Pythagorean theorem decomposes variation into projection and residual components, enabling ANOVA-style analysis and maximal-variation principal structure treelines.The resulting principal structure treeline is the tree-space analog of the first principal component; principal attribute treelines can reveal orientation changes in data.
- Variation analysis: Treelines provide one-dimensional representations of tree space, with structure treelines encoding topology changes and attribute treelines encoding variation within a fixed structure.Under the stated assumption, projection onto a treeline is unique.
4. Derivations of theorems.
The derivations characterize minimizing binary trees by the frequencies of their nodes in the sample. Nodes appearing more than half the time must be included, while nodes appearing less than half the time are terminal and can be removed.
- A minimizing binary tree cannot contain a node that appears less than n/2 times in the sample.Choosing a deepest such node makes it terminal, and removing it preserves or improves the objective, contradicting minimality.
- Nodes appearing exactly n/2 times may be included or omitted without changing the minimizing objective.The proof establishes that removing such a node yields another minimizing tree.
- Every node appearing more than n/2 times in the sample must belong to a minimizing binary tree.The derivation completes the characterization by proving inclusion of all sufficiently frequent nodes.
- The proof proceeds by contradiction, using node frequencies and transformations of the tree's index set.For a node added to the index set, the resulting tree contradicts minimality when that node appears sufficiently often.