Kernel density estimation
≈ 18 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
random numbers using different smoothing bandwidths. 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.
random numbers using different smoothing bandwidths.]] 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 \mathbf{x} = \left ( x_1, x_2, x_3, ... \right ) be independent and identically distributed samples drawn from some univariate distribution with an unknown density at any given point . We are interested in estimating the shape of this function . Its kernel density estimator is \hat{f}_h(x) = \frac{1}{n}\sum_{i=1}^n K_h (x - x_i) = \frac{1}{nh} \sum_{i=1}^n K{\left(\frac{x-x_i}{h}\right)}, where is the kernel — a non-negative function — and is a smoothing parameter called the bandwidth or simply width. A kernel with subscript is called the scaled kernel and defined as . Intuitively one wants to choose as small as the data will allow; however, there is always a trade-off between the bias of the estimator and its variance. The choice of bandwidth is discussed in more detail below. A range of kernel functions are commonly used: uniform, triangular, biweight, triweight, Epanechnikov (parabolic), normal, and others. The Epanechnikov kernel is optimal in a mean square error sense, though the loss of efficiency is small for the kernels listed previously. Due to its convenient mathematical properties, the normal kernel is often used, which means , where is the standard normal density function. The kernel density estimator then becomes \hat{f}_h(x) = \frac{1}{n} \sum_{i=1}^n \frac{1}{h\sqrt{2\pi}} \exp\left(\frac{-(x-x_i)^2}{2h^2}\right), where h is the standard deviation of the sample \mathbf{x} . The construction of a kernel density estimate finds interpretations in fields outside of density estimation. For example, in thermodynamics, this is equivalent to the amount of heat generated when heat kernels (the fundamental solution to the heat equation) are placed at each data point locations . Similar methods are used to construct discrete Laplace operators on point clouds for manifold learning (e.g. diffusion map).
Example
Kernel density estimates are closely related to histograms, but can be endowed with properties such as smoothness or continuity by using a suitable kernel. The diagram below based on these 6 data points illustrates this relationship: For the histogram, first, the horizontal axis is divided into sub-intervals or bins which cover the range of the data: In this case, six bins each of width 2. Whenever a data point falls inside this interval, a box of height 1/12 is placed there. If more than one data point falls inside the same bin, the boxes are stacked on top of each other. For the kernel density estimate, normal kernels with a standard deviation of 1.5 (indicated by the red dashed lines) are placed on each of the data points x i . The kernels are summed to make the kernel density estimate (solid blue curve). The smoothness of the kernel density estimate (compared to the discreteness of the histogram) illustrates how kernel density estimates converge faster to the true underlying density for continuous random variables. on the horizontal axis.]]
Bandwidth selection
The bandwidth of the kernel is a free parameter which exhibits a strong influence on the resulting estimate. To illustrate its effect, we take a simulated random sample from the standard normal distribution (plotted at the blue spikes in the rug plot on the horizontal axis). The grey curve is the true density (a normal density with mean 0 and variance 1). In comparison, the red curve is undersmoothed since it contains too many spurious data artifacts arising from using a bandwidth h = 0.05, which is too small. The green curve is oversmoothed since using the bandwidth obscures much of the underlying structure. The black curve with a bandwidth of h = 0.337 is considered to be optimally smoothed since its density estimate is close to the true density. An extreme situation is encountered in the limit h \to 0 (no smoothing), where the estimate is a sum of delta functions centered at the coordinates of analyzed samples. In the other extreme limit h \to \infty the estimate retains the shape of the used kernel, centered on the mean of the samples (completely smooth). The most common optimality criterion used to select this parameter is the expected L 2 risk function, also termed the mean integrated squared error: \operatorname{MISE} (h) = \operatorname{E}\!\left[ \int\! {\left(\hat{f}\!_h(x) - f(x)\right)}^2 dx \right] Under weak assumptions on and , ( is the, generally unknown, real density function), \operatorname{MISE}(h) = \operatorname{AMISE}(h) + \mathcal{o}{\left((nh)^{-1} + h^4\right)} where is the little o notation, and the sample size (as above). The AMISE is the asymptotic MISE, i. e. the two leading terms, \operatorname{AMISE}(h) = \frac{R(K)}{nh} + \frac{1}{4} m_2(K)^2 h^4 R(f) where R(g) = \int g(x)^2 \, dx for a function , m_2(K) = \int x^2 K(x) \, dx and f is the second derivative of f and K is the kernel. The minimum of this AMISE is the solution to this differential equation \frac{\partial}{\partial h} \operatorname{AMISE}(h) = -\frac{R(K)}{nh^2} + m_2(K)^2 h^3 R(f) = 0 or h_{\operatorname{AMISE}} = \frac{ R(K)^{1/5}}{m_2(K)^{2/5}R(f)^{1/5} } n^{-1/5} = C n^{-1/5} Neither the AMISE nor the h AMISE formulas can be used directly since they involve the unknown density function f or its second derivative f . To overcome that difficulty, a variety of automatic, data-based methods have been developed to select the bandwidth. Several review studies have been undertaken to compare their efficacies, with the general consensus that the plug-in selectors and cross validation selectors are the most useful over a wide range of data sets. Substituting any bandwidth which has the same asymptotic order as into the AMISE gives that , where is the big O notation. It can be shown that, under weak assumptions, there cannot exist a non-parametric estimator that converges at a faster rate than the kernel estimator. Note that the rate is slower than the typical convergence rate of parametric methods. If the bandwidth is not held fixed, but is varied depending upon the location of either the estimate (balloon estimator) or the samples (pointwise estimator), this produces a particularly powerful method termed adaptive or variable bandwidth kernel density estimation. Bandwidth selection for kernel density estimation of heavy-tailed distributions is relatively difficult.
A rule-of-thumb bandwidth estimator
If Gaussian basis functions are used to approximate univariate data, and the underlying density being estimated is Gaussian, the optimal choice for h (that is, the bandwidth that minimises the mean integrated squared error) is: h = {\left(\frac{4\hat{\sigma}^5}{3n}\right)}^{1/5} \approx 1.06 \, \hat{\sigma} \, n^{-1/5}, An h value is considered more robust when it improves the fit for long-tailed and skewed distributions or for bimodal mixture distributions. This is often done empirically by replacing the standard deviation \hat{\sigma} by the parameter A below: A = \min\left(\hat{\sigma}, \frac{\mathrm{IQR}}{1.34}\right) where IQR is the interquartile range. Another modification that will improve the model is to reduce the factor from 1.06 to 0.9. Then the final formula would be: h = 0.9\, \min\left(\hat{\sigma}, \frac{\mathrm{IQR}}{1.34}\right)\, n^{-1/5} where n is the sample size. This approximation is termed the normal distribution approximation, Gaussian approximation, or Silverman's rule of thumb. While this rule of thumb is easy to compute, it should be used with caution as it can yield widely inaccurate estimates when the density is not close to being normal. For example, when estimating the bimodal Gaussian mixture model \frac{1}{2\sqrt{2\pi}} e^{-\frac{1}{2}(x-10)^2} + \frac{1}{2\sqrt{2\pi}}e^{-\frac{1}{2}(x+10)^2} from a sample of 200 points, the figure on the right shows the true density and two kernel density estimates — one using the rule-of-thumb bandwidth, and the other using a solve-the-equation bandwidth. The estimate based on the rule-of-thumb bandwidth is significantly oversmoothed.
Relation to the characteristic function density estimator
Given the sample , it is natural to estimate the characteristic function as \hat\varphi(t) = \frac{1}{n} \sum_{j=1}^n e^{i t x_j} Knowing the characteristic function, it is possible to find the corresponding probability density function through the Fourier transform formula. One difficulty with applying this inversion formula is that it leads to a diverging integral, since the estimate \hat\varphi(t) is unreliable for large 's. To circumvent this problem, the estimator \hat\varphi(t) is multiplied by a damping function , which is equal to 1 at the origin and then falls to 0 at infinity. The "bandwidth parameter" controls how fast we try to dampen the function \hat\varphi(t) . In particular when is small, then will be approximately one for a large range of 's, which means that \hat\varphi(t) remains practically unaltered in the most important region of 's. The most common choice for function is either the uniform function , which effectively means truncating the interval of integration in the inversion formula to , or the Gaussian function . Once the function has been chosen, the inversion formula may be applied, and the density estimator will be \begin{align} \hat{f}(x) &= \frac{1}{2\pi} \int_{-\infty}^{+\infty} \hat\varphi(t) \psi_h(t) e^{-itx} \, dt \\[1ex] &= \frac{1}{2\pi} \int_{-\infty}^{+\infty} \frac{1}{n} \sum_{j=1}^n e^{it(x_j-x)} \psi(ht) \, dt \\[1ex] &= \frac{1}{nh} \sum_{j=1}^n \frac{1}{2\pi} \int_{-\infty}^{+\infty} e^{-i(ht)\frac{x-x_j}{h}} \psi(ht) \, d(ht) \\[1ex] &= \frac{1}{nh} \sum_{j=1}^n K{\left(\frac{x-x_j}{h}\right)}, \end{align} where is the Fourier transform of the damping function . Thus the kernel density estimator coincides with the characteristic function density estimator. X_{\mu,\nu}=\mu q+\nu p. Its measurement outcomes follow an ordinary probability density \mathcal{W}(x\mid\mu,\nu) , known as a symplectic tomogram. The collection of tomograms over different measurement settings is informationally complete and therefore provides an alternative representation of the quantum state. For independent quadrature measurements X_{1,\mu,\nu},\ldots,X_{n,\mu,\nu} obtained at a fixed setting, the tomogram can be estimated by \widehat{\mathcal{W}}_{n,h}(x\mid\mu,\nu) =\frac{1}{nh} \sum_{j=1}^{n} K_{\mu,\nu}\left( \frac{x-X_{j,\mu,\nu}}{h} \right), where K_{\mu,\nu} is a kernel and h is the bandwidth. This treatment does not require the quadrature density to belong to a predetermined parametric family and can therefore accommodate multimodal and non-Gaussian measurement distributions. The characteristic function of a tomogram is its Fourier transform, \varphi(t;\mu,\nu) = \int_{-\infty}^\infty \mathcal{W}(x\mid\mu,\nu)e^{itx}\,dx. For every fixed (\mu,\nu) , this is the characteristic function of the measured random variable X_{\mu,\nu} . It always exists and satisfies the standard conditions \varphi(0;\mu,\nu)=1 , |\varphi(t;\mu,\nu)|\leq 1 , and \varphi(-t;\mu,\nu)=\varphi(t;\mu,\nu)^{*} . In the tomographic representation, the values \varphi(1;\mu,\nu) over phase space also coincide, up to the adopted conventions, with the characteristic function associated with the Wigner representation of the state. Taking the Fourier transform of the kernel density estimator gives a kernel estimator of the characteristic function, \widehat{\varphi}_{n,h}(t;\mu,\nu) = \widehat{\varphi}_{X,n}(t;\mu,\nu) \varphi_K(th;\mu,\nu), where \widehat{\varphi}_{X,n}(t;\mu,\nu) = \frac{1}{n} \sum_{j=1}^n e^{itX_{j,\mu,\nu}} is the empirical characteristic function and \varphi_K(th;\mu,\nu) = \int_{-\infty}^\infty K_{\mu,\nu}(z)e^{ithz}\,dz is the known characteristic function of the rescaled kernel. Thus, the estimator separates into a data-dependent empirical factor and a deterministic smoothing factor controlled by the kernel and bandwidth. The kernel factor suppresses high-frequency contributions, providing a regularized version of the empirical characteristic function. The characteristic-function representation can be used directly for quantum-state reconstruction. For example, the density matrix in the coordinate basis can be recovered from \rho(y,y') The characteristic-function formulation also permits correction for some measurement-noise models. If the observed quadrature is modeled as Z=\kappa X+(1-\kappa)Y , where Y is independent noise with a known nonvanishing characteristic function, then the signal characteristic function can be obtained through a deconvolution, \varphi_X(t) = \frac{\varphi_Z(t/\kappa)}{\varphi_Y((1-\kappa)t/\kappa)}. A kernel factor can subsequently be included to regularize the resulting estimate. This correction requires the noise characteristic function not to vanish at the frequencies used in the reconstruction. The bias and variance of the KCFE are \operatorname{Bias}\!\left[ \widehat{\varphi}_{n,h}(t;\mu,\nu) \right] = \left[\varphi_K(th;\mu,\nu)-1\right] \varphi(t;\mu,\nu) and \operatorname{Var}\!\left[ \widehat{\varphi}_{n,h}(t;\mu,\nu) \right] =\frac{|\varphi_K(th;\mu,\nu)|^{2}}{n} \left[1-|\varphi(t;\mu,\nu)|^{2}\right]. Thus its pointwise mean squared error is \begin{aligned} \operatorname{MSE}\!\left[ \widehat{\varphi}_{n,h}(t;\mu,\nu) \right] ={}& |\varphi_K(th;\mu,\nu)-1|^{2} |\varphi(t;\mu,\nu)|^{2} \\ &+ \frac{|\varphi_K(th;\mu,\nu)|^2}{n} \left[1-|\varphi(t;\mu,\nu)|^2\right]. \end{aligned} For the Gaussian kernel \varphi_K(th;\mu,\nu) = \exp\left[ -\frac{t^2 h^2(\mu^2+\nu^2)}{4} \right]. The resulting error is \begin{aligned} \operatorname{MSE}\!\left[ \widehat{\varphi}^{\,G}_{n,h}(t;\mu,\nu) \right] ={}& \left( \exp\left[ -\frac{t^2 h^2(\mu^2+\nu^2)}{4} \right]-1 \right)^2 |\varphi(t;\mu,\nu)|^2 \\ &+ \frac{1}{n} \exp\left[ -\frac{t^2h^2(\mu^2+\nu^2)}{4} \right] \left[1-|\varphi(t;\mu,\nu)|^2\right]. \end{aligned} For 0 , minimizing this expression gives a characteristic-function bandwidth of order h_{\varphi}=O(n^{-1/2}), and the minimized error satisfies \operatorname{MSE}\!\left[ \widehat{\varphi}^{\,G}_{n,h_{\varphi}}(t;\mu,\nu) \right] = \frac{1-|\varphi(t;\mu,\nu)|^2}{n} - \frac{\left[1-|\varphi(t;\mu,\nu)|^2 \right]^2} {4n^{2}|\varphi(t;\mu,\nu)|^2} = O(n^{-1}). The characteristic-function estimator therefore converges pointwise at the parametric n^{-1} mean squared error rate, although the underlying tomogram is estimated nonparametrically. Collections of characteristic-function estimates at several measurement settings form the input to the kernel quantum state estimation procedure. If n measurements are taken at each setting and N_{\mu}=N_{\nu}=(\log n)^2 , the numbers of state preparations used for density-matrix and two-dimensional trace estimation are T_{\mu}=nN_\mu, \qquad T_{\mu,\nu}=nN_\mu N_\nu. For the coordinate-space density matrix, the reported uniform pointwise risk is \sup_{y,y'} \mathbb E\left[ \left| \widehat{\rho}(y,y')-\rho(y,y') \right|^2 \right] = \widetilde{O}\!\left(T_\mu^{-1}\right). For the overlap of two quantum states, the reported mean squared error is \mathbb E\left[ \left| \widehat{\operatorname{tr}(\rho_1\rho_2)} - \operatorname{tr}(\rho_1\rho_2) \right|^2 \right] = \widetilde{O}\!\left(T_{\mu,\nu}^{-1}\right), where \widetilde{O} suppresses logarithmic factors arising from the number of measurement settings. M = \{ x:g(x) = 0 \mid \lambda_1(x) Namely, M is the collection of points for which the density function is locally maximized. A natural estimator of M is a plug-in from KDE, where g(x) and \lambda_1(x) are KDE version of g(x) and \lambda_1(x) . Under mild assumptions, M_c is a consistent estimator of M . Note that one can use the mean shift algorithm to compute the estimator M_c numerically. In Origin, 2D kernel density plot can be made from its user interface, and two functions, Ksdensity for 1D and Ks2density for 2D can be used from its LabTalk , Python, or C code. In Perl, an implementation can be found in the Statistics-KernelEstimation module In PHP, an implementation can be found in the MathPHP library In Python, many implementations exist: pyqt_fit.kde Module in the PyQt-Fit package, SciPy ( scipy.stats.gaussian_kde ), Statsmodels ( KDEUnivariate and KDEMultivariate ), and scikit-learn ( KernelDensity ) (see comparison ). KDEpy supports weighted data and its FFT implementation is orders of magnitude faster than the other implementations. The commonly used pandas library offers support for kde plotting through the plot method ( df.plot(kind='kde') [https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.DataFrame.plot.kde.html). The getdist package for weighted and correlated MCMC samples supports optimized bandwidth, boundary correction and higher-order methods for 1D and 2D distributions. One newly used package for kernel density estimation is seaborn ( import seaborn as sns , sns.kdeplot() ). A GPU implementation of KDE also exists. In R, it is implemented through density in the base distribution, and bw.nrd0 function is used in stats package, this function uses the optimized formula in Silverman's book. bkde in the KernSmooth library, ParetoDensityEstimation in the DataVisualizations library (for pareto distribution density estimation), kde in the ks library, dkden and dbckden in the evmix library (latter for boundary corrected kernel density estimation for bounded support), npudens in the np library (numeric and categorical data), sm.density in the sm library. For an implementation of the kde.R function, which does not require installing any packages or libraries, see kde.R. The btb library, dedicated to urban analysis, implements kernel density estimation through kernel_smoothing . In SAS, proc kde can be used to estimate univariate and bivariate kernel densities. In Apache Spark, the KernelDensity() class In Stata, it is implemented through kdensity ; for example histogram x, kdensity . Alternatively a free Stata module KDENS is available allowing a user to estimate 1D or 2D density functions. In Swift, it is implemented through SwiftStats.KernelDensityEstimation in the open-source statistics library SwiftStats.
See also
Kernel (statistics) Kernel smoothing Kernel regression Density estimation (with presentation of other examples) Mean-shift Scale space: The triplets {(x, h, KDE with bandwidth h evaluated at x: all x, h > 0} form a scale space representation of the data. Multivariate kernel density estimation Variable kernel density estimation Head/tail breaks
Further reading
References
External links
Introduction to kernel density estimation A short tutorial which motivates kernel density estimators as an improvement over histograms. Kernel Bandwidth Optimization A free online tool that generates an optimized kernel density estimate. Free Online Software (Calculator) computes the Kernel Density Estimation for a data series according to the following Kernels: Gaussian, Epanechnikov, Rectangular, Triangular, Biweight, Cosine, and Optcosine. Kernel Density Estimation Applet An online interactive example of kernel density estimation. Requires .NET 3.0 or later.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1375918779 under CC BY-SA 4.0; modifications have been made.