Identifying the Intrinsic Dimensionality Using the Minimum Spanning Tree

• Activity Number: 673
• Type: Contributed
• Date/Time: Thursday, August 4, 2011 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Adam Petrie*+
• Companies: University of Tennessee
• Keywords: spanning tree ; intrinsic dimension ; dimension reduction ; dimension identification ; node degree

Abstract

In dimension reduction algorithms such as principal components, multidimensional scaling, ISOMAP, etc., it is desired to project the originally high dimensional dataset onto a lower dimensional subspace. These algorithms have the requirement that the target dimension must be chosen in advance, but they do not necessarily give an estimate of the target dimension themselves. If the data lie on some lower dimensional manifold it seems logical to choose its intrinsic dimension as the target. We explore using the node degree frequencies of the minimum spanning tree of the dataset as an estimator of the intrinsic dimension. Asymptotically, there are independent of the underlying density and will provide a consistent estimator of the intrinsic dimension. We provide improved estimates of these asymptotic frequencies and introduce new estimators of the intrinsic dimension based on the node