skip to content

Entropic graphs for high-dimensional data analysis

Presented by: 
A Hero [Michigan]
Tuesday 13th May 2008 - 11:00 to 12:00
INI Seminar Room 1

A minimal spanning tree (MST) spanning random points has total spanning length that converges to the entropy of the underlying density generating the points. This celebrated result was first established by Beardwood, Halton and Hammersley (1958) and has since been extended to other random Euclidean and non-Euclidean graphs, such as the geodesic MST (GMST) and the k-nearest neighbor graph (kNNG) over a random set of point. Using the BHH theory of random graphs one can construct graph-based estimates of topological properties of a high dimensional distribution of a data sample. This leads, for example, to a model-free consistent estimator of intrinsic dimension of a data manifold and a high performance non-parametric anomaly detector. We will illustrate this entropic graph approach for applications including: anomaly detection in Internet traffic; activity detection in a MICA2 wireless network; and intrinsic dimension estimation of image databases.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons