Entropic graphs for high-dimensional data analysis

1 hour 9 mins 57 secs, 258.90 MB, iPod Video 480x360, 25.0 fps, 44100 Hz, 505.34 kbits/sec

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/1039/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Hero, A (Michigan) Tuesday 13 May 2008, 11:00-12:00

Created:

2008-05-15 09:16

Collection:

Statistical Theory and Methods for Complex, High-Dimensional Data

Publisher:

Isaac Newton Institute

Hero, A

Language:

eng (English)

Credits:

Author:

Hero, A


Abstract:	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.

Abstract:

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.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	480x360	1.84 Mbits/sec	966.25 MB	View	Download
WebM	480x360	591.2 kbits/sec	298.78 MB	View	Download
Flash Video	480x360	806.86 kbits/sec	413.38 MB	View	Download
iPod Video *	480x360	505.34 kbits/sec	258.90 MB	View	Download
QuickTime	384x288	848.63 kbits/sec	434.78 MB	View	Download
MP3	44100 Hz	125.0 kbits/sec	63.84 MB	Listen	Download
Auto	(Allows browser to choose a format it supports)