5
$\begingroup$

I am currently working on a research project that requires a reliable method for non-parametric kernel density estimation. Some specifics about my problem:

  • I have $N$ sample points $X_1,X_2...X_N$, each of which corresponds to an outcome of an $M$ dimensional random variable $W = (w_1..w_M)$. I would like to assign a density to each of these points in an accurate and consistent way.

  • I am looking for a method that does not assume that the random variables be independent. As in my situation, I know that $f(W) \neq \prod_{i=1}^M {f_m(w_i)}$.

  • In my case, $N \leq 25000$ and $M \leq 5$ but I can generate as much data as needed.

Open to any and all suggestions!

Improve this question
$\endgroup$

4 Answers 4

Reset to default
3
$\begingroup$

For those who are looking for a batch method for bandwidth estimation, I would suggest the multivariate bandwith estimator from [1] -- the approximate calculation in C interfaced to Matlab can be obtained from the following link: http://www.vicos.si/images/2/2e/KDE_bw_Matlab.zip

If you have large amounts of data (e.g., order of 1000), it might not make sense to apply the standard batch method. Instead you can use the online Kernel Density Estimator from [1], of which Matlab implementation can be obtained from this site: http://www.vicos.si/Research/Multivariate_Online_Kernel_Density_Estimation (Also some video examples of the estimation process are included)

[1] Multivariate Online Kernel Density Estimation with Gaussian Kernels Matej Kristan, Aleš Leonardis, and Danijel Skočaj, Pattern Recognition, 2011

Improve this answer
$\endgroup$
1
$\begingroup$

How about putting the points into a Kd tree ? This is fast and easy in 5d (in fact up to 20d, even 128d). Then you can find nearest neighbours of single query points, or a grid; or do data reduction by keeping midpoints of leaves, of 10 or 100 points. (Which of these do you want to do ?)

If you're using scipy.spatial.cKDTree, see also the code snippet forleaves() in a Kd tree.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you for this suggestion. I'm fairly new to KD trees so I'm wondering how exactly they can be applied to density estimation? My understanding is that I can generate an N-dimensional grid, then use the KD tree to count the number of points that are near to each grid point (within delta). The probability of each point on the grid is then the number of points within delta / total number of points at all grid points. Does this sound right? $\endgroup$
    – Berk U.
    Aug 22, 2011 at 23:29
  • $\begingroup$ Berk U, do you really want densities on a uniform grid ? 250k points in a 10x10x10x10x10 grid (5d) gives you on average only 2.5 data point per little box; and 10^5 queries of any data structure will cost. Can you describe what you really want to do ? $\endgroup$
    – denis
    Aug 23, 2011 at 17:15
  • $\begingroup$ Basically: given 10000-1000000 samples in 2-5 dimensions, I would like to attribute a probability to each sample without having to use product kernels. $\endgroup$
    – Berk U.
    Aug 23, 2011 at 23:15
  • $\begingroup$ 100000 probabilities with average .00001 ?? What Kd trees can give you is the nearest few neighbors of all input points or many grid points; if you read Python, see inverse-distance-weighted-idw-interpolation-with-python $\endgroup$
    – denis
    Aug 24, 2011 at 9:04
  • $\begingroup$ Kd trees and grids per se are mostly acceleration techniques, they're not necessary for kernel density estimation if your goal is just accuracy in batch processing. That is, even with grids I suggest using them just to find nearest neighbours and then process those via kernel d.e. or local linear d.e., not using grids as a basis for histograms. For that latter approach at growing dimensions there are more isotropic (= dense and efficient) regular structures, see e.g. sphere packings. $\endgroup$
    – Quartz
    Mar 14, 2013 at 12:23
1
$\begingroup$

The ks package in R can do multivariate kernel density estimation. I guess it depend on how many dimensions you have and whether you want to visualize the multivariate pdf or compute certain expectations. ks can handle up to 6 dimensional data.

Improve this answer
$\endgroup$
1
1
$\begingroup$

I am looking at a similar problem, and although I can't point you to concrete implementations, I found a couple of papers that give multivariate density estimates that are not assumed to be independent a priori, and that also avoid "the curse of dimensionality" at least to some extent. These are:

  1. Forest Density Estimation by Han Liu, Min Xu, Haijie Gu, Anupam Gupta, John Lafferty, Larry Wasserman (CMU)

  2. Density Estimation Trees by Parikshit Ram, Alexander G. Gray (Georgia Tech)

If you do run into a general implementation, please submit an update!

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.