I am trying to sort data following a bivariate distribution into a numpy histogramdd, where each bin should contain the same number of data points (to the nearest whole sample).

I expect that some kind of quantile-approach is required, and have tried scipy.stats.mstats.mquantiles, which according to the documentation takes up to 2D data. However, it seems to take the dimensions independently, splitting each dimension into to equal marginal probabilities, which doesn't achieve the desired result of equal-probability bins in 2D.

Is there a built-in way in scipy/numpy or another package to achieve this (in 2D or higher)? If not, are there algorithms designed to achieve this which I can implement myself directly?

  • 1
    $\begingroup$ I suspect that you omitted an important consideration. Besides having the same "number of data points" as nearly as possible, what other properties does the partition need to have? Were you thinking about clustering the nearest points to each other in one part? $\endgroup$
    – hardmath
    Aug 12 '18 at 5:18

You obviously can't do this if you want the bins to be separated at the same $x_i$ and $y_i$ values. This is easy to see if you want to have, say, 4 bins and have 10 data points at $(0,0)$ and 10 points at $(1,1)$.

But you can use a $kd$ tree data structure in which you recursively subdivide each bin so that it contains the same number of points.

  • $\begingroup$ Thanks - that's right; I am not expecting to have bins going across each dimension like a chessboard. Instead, I was imagining a sort of tetris-style puzzle where square/rectangular/L-shape bins would slot around eachother, to encompass near-equal numbers of samples, over some more-or-less coarse grid. It seemed like a cool optimisation problem; but the recursive division sounds like the way to achieve it - I'd not heard nor thought of that before. Do you happen to have any papers/links showing this approach being used for density estimation purposes? $\endgroup$
    – Zac
    Aug 12 '18 at 16:57
  • $\begingroup$ Nothing on density estimation, but the wikipedia page about kd trees is good: en.wikipedia.org/wiki/K-d_tree $\endgroup$ Aug 13 '18 at 22:22

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.