  Unsupervised discretization is a crucial step in many knowledge discovery
tasks. The state-of-the-art method for one-dimensional data infers locally
adaptive histograms using the minimum description length (MDL) principle, but
the multi-dimensional case is far less studied: current methods consider the
dimensions one at a time (if not independently), which result in
discretizations based on rectangular cells of adaptive size. Unfortunately,
this approach is unable to adequately characterize dependencies among
dimensions and/or results in discretizations consisting of more cells (or bins)
than is desirable.
  To address this problem, we propose an expressive model class that allows for
far more flexible partitions of two-dimensional data. We extend the state of
the art for the one-dimensional case to obtain a model selection problem based
on the normalized maximum likelihood, a form of refined MDL. As the flexibility
of our model class comes at the cost of a vast search space, we introduce a
heuristic algorithm, named PALM, which Partitions each dimension ALternately
and then Merges neighboring regions, all using the MDL principle. Experiments
on synthetic data show that PALM 1) accurately reveals ground truth partitions
that are within the model class (i.e., the search space), given a large enough
sample size; 2) approximates well a wide range of partitions outside the model
class; 3) converges, in contrast to the state-of-the-art multivariate
discretization method IPD. Finally, we apply our algorithm to three spatial
datasets, and we demonstrate that, compared to kernel density estimation (KDE),
our algorithm not only reveals more detailed density changes, but also fits
unseen data better, as measured by the log-likelihood.
