Tree preserving embedding

Proc Natl Acad Sci U S A. 2011 Oct 11;108(41):16916-21. doi: 10.1073/pnas.1018393108. Epub 2011 Sep 26.

Abstract

The goal of dimensionality reduction is to embed high-dimensional data in a low-dimensional space while preserving structure in the data relevant to exploratory data analysis such as clusters. However, existing dimensionality reduction methods often either fail to separate clusters due to the crowding problem or can only separate clusters at a single resolution. We develop a new approach to dimensionality reduction: tree preserving embedding. Our approach uses the topological notion of connectedness to separate clusters at all resolutions. We provide a formal guarantee of cluster separation for our approach that holds for finite samples. Our approach requires no parameters and can handle general types of data, making it easy to use in practice and suggesting new strategies for robust data visualization.

Publication types

  • Evaluation Study
  • Research Support, N.I.H., Extramural
  • Research Support, U.S. Gov't, Non-P.H.S.

MeSH terms

  • Algorithms
  • Cluster Analysis
  • Data Interpretation, Statistical*
  • Handwriting
  • Models, Statistical
  • Radar
  • Sequence Analysis, Protein / statistics & numerical data