# Is it possible to partition 2D data into bins such that each bin contains the same number of samples?

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?

• 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? Aug 12 '18 at 5:18

## 2 Answers

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.

• 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?
– Zac
Aug 12 '18 at 16:57
• Nothing on density estimation, but the wikipedia page about kd trees is good: en.wikipedia.org/wiki/K-d_tree Aug 13 '18 at 22:22

Take a look at this library : https://physt.readthedocs.io/

I guess what you need is here : https://physt.readthedocs.io/en/latest/2d_histograms.html

• Welcome to Computational Science! Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference. Oct 15 '21 at 22:56