# 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? – 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.