Accurate Estimation of the Intrinsic Dimension Using Graph Distances: Unraveling the Geometric Complexity of Datasets.
Accurate Estimation of the Intrinsic Dimension Using Graph Distances: Unraveling the Geometric Complexity of Datasets.
复制标题
DOI：
10.1038/srep31377
复制
发表时间：
2016-08-11
影响因子：
4.6
通讯作者：
Carnevale V
中科院分区：
文献类型：
--
作者：
Granata D;Carnevale V
大量自由度的集体行为通常可以用少数变量来描述。这一观察证明了使用降维方法来模拟复杂系统的合理性，并激发了对一小组相关“集体”变量的搜索。在这里，我们通过关注捕获通用数据集的显着特征所需的最佳变量数量来分析这个问题，并开发一种新颖的内在维度（ID）估计器。通过在图上用最小距离路径逼近测地线，我们分析了最大值周围成对距离的分布，并利用其对维数的依赖性来获得 ID 估计。我们表明，估计器不依赖于固有流形的形状，并且即使对于极小的样本量也是高度准确的。我们将该方法应用于图像识别数据库和蛋白质多序列比对中的几个相关数据集，并根据输入变量之间的相关性和数据集的信息内容讨论估计维度的可能解释。
The collective behavior of a large number of degrees of freedom can be often described by a handful of variables. This observation justifies the use of dimensionality reduction approaches to model complex systems and motivates the search for a small set of relevant “collective” variables. Here, we analyze this issue by focusing on the optimal number of variable needed to capture the salient features of a generic dataset and develop a novel estimator for the intrinsic dimension (ID). By approximating geodesics with minimum distance paths on a graph, we analyze the distribution of pairwise distances around the maximum and exploit its dependency on the dimensionality to obtain an ID estimate. We show that the estimator does not depend on the shape of the intrinsic manifold and is highly accurate, even for exceedingly small sample sizes. We apply the method to several relevant datasets from image recognition databases and protein multiple sequence alignments and discuss possible interpretations for the estimated dimension in light of the correlations among input variables and of the information content of the dataset.