Variable kernel density estimation

<h2 id="rationale">Rationale</h2>
Given a set of samples, 
 
 
 
 {
 
 
 
 
 x
 →
 
 
 
 
 i
 
 
 }
 
 
 {\displaystyle \lbrace {\vec {x}}_{i}\rbrace }
 
, we wish to estimate the
density, 
 
 
 
 P
 (
 
 
 
 x
 →
 
 
 
 )
 
 
 {\displaystyle P({\vec {x}})}
 
, at a test point, 
 
 
 
 
 
 
 x
 →
 
 
 
 
 
 {\displaystyle {\vec {x}}}
 
:

P
        (
        
          
            
              x
              →
            
          
        
        )
        ≈
        
          
            W
            
              n
              
                h
                
                  D
                
              
            
          
        
      
    
    {\displaystyle P({\vec {x}})\approx {\frac {W}{nh^{D}}}}

W
        =
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          w
          
            i
          
        
      
    
    {\displaystyle W=\sum _{i=1}^{n}w_{i}}

w
          
            i
          
        
        =
        K
        
          (
          
            
              
                
                  
                    
                      x
                      →
                    
                  
                
                −
                
                  
                    
                      
                        x
                        →
                      
                    
                  
                  
                    i
                  
                
              
              h
            
          
          )
        
      
    
    {\displaystyle w_{i}=K\left({\frac {{\vec {x}}-{\vec {x}}_{i}}{h}}\right)}

where n is the number of samples, K is the 
<a href="/facts/Kernel_(statistics)/otWLlBbA">"kernel"</a>, h is its width and D is the number of dimensions in 
 
 
 
 
 
 
 x
 →
 
 
 
 
 
 {\displaystyle {\vec {x}}}
 
.
The kernel can be thought of as a simple, <a href="/facts/Linear_filter/3W5oDlVq">linear filter</a>.
Using a fixed filter width may mean that in regions of low density, all samples
will fall in the tails of the filter with very low weighting, while regions of high
density will find an excessive number of samples in the central region with weighting
close to unity. To fix this problem, we vary the width of the kernel in different
regions of the sample space. 
There are two methods of doing this: balloon and pointwise estimation.
In a balloon estimator, the kernel width is varied depending on the location 
of the test point. In a pointwise estimator, the kernel width is varied depending
on the location of the sample.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
For multivariate estimators, the parameter, h, can be generalized to
vary not just the size, but also the shape of the kernel. This more complicated approach
will not be covered here.

<h2 id="balloon-estimators">Balloon estimators</h2>
A common method of varying the kernel width is to make it inversely proportional to the density at the test point:

h
        =
        
          
            k
            
              
                [
                
                  n
                  P
                  (
                  
                    
                      
                        x
                        →
                      
                    
                  
                  )
                
                ]
              
              
                1
                
                  /
                
                D
              
            
          
        
      
    
    {\displaystyle h={\frac {k}{\left[nP({\vec {x}})\right]^{1/D}}}}

where k is a constant. 
If we back-substitute the estimated PDF, and assuming a Gaussian <a href="/facts/Kernel_(statistics)/otWLlBbA">kernel function</a>,
we can show that W is a constant:<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

W
        =
        
          k
          
            D
          
        
        (
        2
        π
        
          )
          
            D
            
              /
            
            2
          
        
      
    
    {\displaystyle W=k^{D}(2\pi )^{D/2}}

A similar derivation holds for any kernel whose normalising function is of the order hD, although with a different constant factor in place of the (2 π)D/2 term. This produces a generalization of the <a href="/facts/K-nearest_neighbour_algorithm/Bs1UaAmE">k-nearest neighbour algorithm</a>.
That is, a uniform <a href="/facts/Kernel_(statistics)/otWLlBbA">kernel function</a> will return the 
KNN technique.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
There are two components to the error: a variance term and a bias term. The variance term is given as:<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

e
 
 1
 
 
 =
 
 
 
 P
 ∫
 
 K
 
 2
 
 
 
 
 n
 
 h
 
 D
 
 
 
 
 
 
 
 {\displaystyle e_{1}={\frac {P\int K^{2}}{nh^{D}}}}
 
.
The bias term is found by evaluating the approximated function in the limit as the kernel
width becomes much larger than the sample spacing. By using a Taylor expansion for the real function, the bias term drops out:

e
          
            2
          
        
        =
        
          
            
              h
              
                2
              
            
            n
          
        
        
          ∇
          
            2
          
        
        P
      
    
    {\displaystyle e_{2}={\frac {h^{2}}{n}}\nabla ^{2}P}

An optimal kernel width that minimizes the error of each estimate can thus be derived.

<h2 id="use-for-statistical-classification">Use for statistical classification</h2>
The method is particularly effective when applied to <a href="/facts/Statistical_classification/jXXHRkXR">statistical classification</a>.
There are two ways we can proceed: the first is to compute the PDFs of
each class separately, using different bandwidth parameters, 
and then compare them as in Taylor.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
Alternatively, we can divide up the sum based on the class of each sample:

P
        (
        j
        ,
        
          
            
              x
              →
            
          
        
        )
        ≈
        
          
            1
            n
          
        
        
          ∑
          
            i
            =
            1
            ,
            
              c
              
                i
              
            
            =
            j
          
          
            n
          
        
        
          w
          
            i
          
        
      
    
    {\displaystyle P(j,{\vec {x}})\approx {\frac {1}{n}}\sum _{i=1,c_{i}=j}^{n}w_{i}}

where ci is the class of the ith sample.
The class of the test point may be estimated through <a href="/facts/Maximum_likelihood/0Yq2dpQD">maximum likelihood</a>.

<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.mathworks.com/matlabcentral/fileexchange/58309-adaptive-kernel-density-estimation-in-one-dimension">akde1d.m</a> - <a href="/facts/Matlab/qPjLISCk">Matlab</a> m-file for one-dimensional adaptive kernel density estimation.</li>
<li><a href="http://libagf.sf.net">libAGF</a> - A <a href="/facts/C%2B%2B/Et0F2qn9">C++</a> library for multivariate adaptive kernel density estimation.</li>
<li><a href="http://www.mathworks.com/matlabcentral/fileexchange/58312-kernel-density-estimator-for-high-dimensions">akde.m</a> - <a href="/facts/Matlab/qPjLISCk">Matlab</a> function for multivariate (high-dimensional) variable kernel density estimation.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">D. G. Terrell; D. W. Scott (1992). "Variable kernel density estimation". Annals of Statistics. 20 (3): 1236–1265. doi:10.1214/aos/1176348768. <a href="https://doi.org/10.1214%2Faos%2F1176348768" target="_blank">https://doi.org/10.1214%2Faos%2F1176348768</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">D. G. Terrell; D. W. Scott (1992). "Variable kernel density estimation". Annals of Statistics. 20 (3): 1236–1265. doi:10.1214/aos/1176348768. <a href="https://doi.org/10.1214%2Faos%2F1176348768" target="_blank">https://doi.org/10.1214%2Faos%2F1176348768</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Mills, Peter (2011). "Efficient statistical classification of satellite measurements". International Journal of Remote Sensing. 32 (21): 6109–6132. arXiv:1202.2194. Bibcode:2011IJRS...32.6109M. doi:10.1080/01431161.2010.507795. S2CID 88518570. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Mills, Peter (2011). "Efficient statistical classification of satellite measurements". International Journal of Remote Sensing. 32 (21): 6109–6132. arXiv:1202.2194. Bibcode:2011IJRS...32.6109M. doi:10.1080/01431161.2010.507795. S2CID 88518570. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">D. G. Terrell; D. W. Scott (1992). "Variable kernel density estimation". Annals of Statistics. 20 (3): 1236–1265. doi:10.1214/aos/1176348768. <a href="https://doi.org/10.1214%2Faos%2F1176348768" target="_blank">https://doi.org/10.1214%2Faos%2F1176348768</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Taylor, Charles (1997). "Classification and kernel density estimation". Vistas in Astronomy. 41 (3): 411–417. Bibcode:1997VA.....41..411T. doi:10.1016/s0083-6656(97)00046-9. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Variable kernel density estimation open-in-new

Variable kernel density estimation