## Binning

Binning, or assigning data to discrete categories, is an effective and
fast method for large data sets (Fan and Marron 1994). When the
sample size *n* is large, direct evaluation of the kernel estimate
at any point would involve *n* kernel evaluations as shown in
the preceding formulas. To evaluate the estimate at each point of a
grid of size *g* would thus require *ng* kernel evaluations. When you
use *g* = 401 in the univariate case or *g* = 60×60 = 3600 in the
bivariate case and , the amount of computation can be
prohibitively large. With binning, however, the computational order
is reduced to *g*, resulting in a much quicker algorithm that is
practically as accurate as direct evaluation.
To bin a set of weighted univariate data *X*_{1},*X*_{2}, ... ,*X*_{n}
to a grid *x*_{1}, *x*_{2}, ... ,*x*_{g}, simply assign each sample
*X*_{i}, together with its weight *W*_{i}, to the nearest grid point
*x*_{j} (also called the bin center). When binning is completed,
each grid point *x*_{i} has an associated number *c*_{i}, which is
the sum total of all the weights that correspond to sample points
that have been assigned to *x*_{i}. These *c*_{i}s are known as
the "bin counts."

This procedure replaces the data (*X*_{i},*W*_{i}), *i* = 1,2, ... ,*n*
with the smaller set (*x*_{i},*c*_{i}), *i* = 1,2, ... ,*g*, and the
estimation is carried out with this new data. This is so-called
"simple binning," as versus the finer "linear binning" described
in Wand (1993). PROC KDE uses simple binning for the sake of faster
and easier implementation. Also, it is assumed that the bin centers
*x*_{1},*x*_{2}, ... ,*x*_{g} are equally spaced and in increasing
order. In addition, assume for notational convenience that
and, therefore, .

If you replace the data (*X*_{i},*W*_{i}), *i* = 1,2, ... ,*n*
with (*x*_{i},*c*_{i}), *i* = 1,2, ... ,*g*, the weighted
estimator then becomes

with the same notation as used previously.
To evaluate this estimator at the *g* points of the same
grid vector *grid* = (*x*_{1},*x*_{2}, ... ,*x*_{g})' is to
calculate

for *i* = 1,2, ... ,*g*. This can be rewritten as

where is the increment of the grid.
The same idea of binning works similarly with bivariate data, where
you estimate over the grid matrix *grid* = *grid*_{X}×*grid*_{Y} as follows.

where **x**_{i,j} = (*x*_{i},*y*_{i}), *i* = 1,2, ... ,*g*_{X}, *j* = 1,2, ... ,*g*_{Y}, and the estimates are

where and
are the
increments of the grid.

Copyright © 1999 by SAS Institute Inc., Cary, NC, USA. All rights reserved.