The Remarkable Simplicity of Very High Dimensional Data: Application of Model-Based Clustering

Abstract

An ultrametric topology formalizes the notion of hierarchical structure. An ultrametric embedding, referred to here as ultrametricity, is implied by a hierarchical embedding. Such hierarchical structure can be global in the data set, or local. By quantifying extent or degree of ultrametricity in a data set, we show that ultrametricity becomes pervasive as dimensionality and/or spatial sparsity increases. This leads us to assert that very high dimensional data are of simple structure. We exemplify this finding through a range of simulated data cases. We discuss also application to very high frequency time series segmentation and modeling.

36 pages, 18 figures, 36 references

References in corpus (2)

• A Note on Local Ultrametricity in Text
• A Note on Approximate Nearest Neighbor Methods

Cited by in corpus (5)

• High--Dimensional Brain in a High-Dimensional World: Blessing of Dimensionality
• Symmetry in Data Mining and Analysis: A Unifying View based on Hierarchy
• An algorithm for deciding the number of clusters and validation using simulated data with application to exploring crop population structure
• Anytime Hierarchical Clustering
• Discussion of: Treelets--An adaptive multi-Scale basis for sparse unordered data