Kernel density estimation

Summary

In statistics, kernel density estimation (KDE) is the application of kernel smoothing for probability density estimation, i.e., a non-parametric method to estimate the probability density function of a random variable based on kernels as weights. KDE answers a fundamental data smoothing problem where inferences about the population are made, based on a finite data sample. In some fields such as signal processing and econometrics it is also termed the Parzen–Rosenblatt window method, after Emanuel Parzen and Murray Rosenblatt, who are usually credited with independently creating it in its current form. One of the famous applications of kernel density estimation is in estimating the class-conditional marginal densities of data when using a naive Bayes classifier, which can improve its prediction accuracy. Definition Let (x1, x2, ..., xn) be independent and identically distributed samples drawn from some univariate distribution with an unknown density ƒ at an

Official source

https://en.wikipedia.org/wiki/Kernel_density_estimation

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (95)

Related publications

Related people (5)

Related people

Related units (7)

Related units

Related concepts (11)

Related concepts

Related courses (41)

Related courses

Related lectures (84)

Related lectures

Sketches, metrics and fast algorithms

Navid Nouri

As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in most applications, even storing datasets as acquired has become extremely costly and inefficient, which motivates the study of sublinear algorithms. This thesis focuses on studying two fundamental graph problems in the sublinear regime. Furthermore, it presents a fast kernel density estimation algorithm and data structure. The first part of this thesis focuses on graph spectral sparsification in dynamic streams. Our algorithm achieves almost optimal runtime and space simultaneously in a single pass. Our method is based on a novel bucketing scheme that enables us to recover high effective resistance edges faster. This contribution presents a novel approach to the effective resistance embedding of the graph, using locality-sensitive hash functions, with possible further future applications.The second part of this thesis presents spanner construction results in the dynamic streams and the simultaneous communication models. First, we show how one can construct a

\tilde{O}(n^{2/3})

-spanner using the above-mentioned almost-optimal single-pass spectral sparsifier, resulting in the first single-pass algorithm for non-trivial spanner construction in the literature. Then, we generalize this result to constructing

\tilde{O}(n^{2/3(1-\alpha)})

-spanners using

\tilde{O}(n^{1+\alpha})

space for any

\alpha \in [0,1]

, providing a smooth trade-off between distortion and memory complexity. Moreover, we study the simultaneous communication model and propose a novel protocol with low per player information. Also, we show how one can leverage more rounds of communication in this setting to achieve better distortion guarantees. Finally, in the third part of this thesis, we study the kernel density estimation problem. In this problem, given a kernel function, an input dataset imposes a kernel density on the space. The goal is to design fast and memory-efficient data structures that can output approximations to the kernel density at queried points. This thesis presents a data structure based on the classical near neighbor search and locality-sensitive hashing techniques that improves or matches the query time and space complexity for radial kernels considered in the literature. The approach is based on an implementation of (approximate) importance sampling for each distance range and then using near neighbor search algorithms to recover points from these distance ranges. Later, we show how to improve the runtime, using recent advances in the data-dependent near neighbor search data structures, for a class of radial kernels that includes the Gaussian kernel.

EPFL2022

Traditionally, spatial analysis of point pattern has been mostly focused on Euclidean space. As many human related phenomena take place on a network, the assumption of a continuous isotropic space fails to describe events which actually occur on a one-dimensional subset of this space. Thus, recently, researchers have begun integrating network structure constraints to study point patterns. The focus of this report is primarily aimed at the integration of the network structure constraints in studying the first order property of point processes with Kernel Density Estimation (KDE). Two different approaches and the computational methods used to calculate network based kernel density estimation (NetKDE) are described, and are then compared to each other as well as to KDE. An original approach which aim is to replace the conventional search area in flat disk through Euclidean space is introduced. In urban context, polygons of various shapes can be generated and used over the network as an approximation of the potential accessible area for a given distance. As a first case-study, network based density values for various types of economic activities are generated for each building in Geneva. The integration of urban structures in the characterization of neighborhood attributes is an innovative approach which possesses many advantages. A classification based on the attributes generated with this method is performed, and a detailed analysis of the results is carried out. In a second case-study in urban environment, time is considered as an additional dimension in kernel density estimates. A three dimensional KDE approach is used in an attempt to monitor the risk associated with the explosions of improvised explosive devices (IED) in Baghdad through space and time. An animation of the simulations is presented as a visualization technique to detect sensitive areas.

2011

Supervised Classification with Variable Kernel Estimators

1995

Sketches, metrics and fast algorithms

Navid Nouri

\tilde{O}(n^{2/3})

\tilde{O}(n^{2/3(1-\alpha)})

-spanners using

\tilde{O}(n^{1+\alpha})

space for any

\alpha \in [0,1]

EPFL2022