Unsupervised Discretization by Two-dimensional MDL-based Histogram

Lincen Yang, Mitra Baratchi, Matthijs van Leeuwen

Abstract

Discretization is a fundamental task in data science, yet scaling it to two dimensions often results in rigid, inefficient grids. We present PALM (Partitioning Alternately and Merging), an unsupervised algorithm that discretizes 2D data into flexible, non-rectangular regions using the Minimum Description Length (MDL) principle. By alternating between partitioning and merging, PALM captures complex spatial dependencies more accurately and with fewer bins than traditional grid-based methods or Kernel Density Estimation (KDE).

Introduction

Traditional multivariate discretization methods often treat dimensions independently or rely on fixed Cartesian grids. These approaches struggle to capture dependencies where density changes in one dimension are conditional on another, leading to either overfitting or under-discretization. Furthermore, many existing techniques require manual hyperparameter tuning. This paper introduces a self-adaptive, flexible, and parameter-free method for 2D discretization that "shrink-wraps" around the data's true density.

Methods

The PALM algorithm is grounded in the Minimum Description Length (MDL) principle, specifically using Normalized Maximum Likelihood (NML). A key theoretical contribution is the proof that parametric complexity—the penalty for model complexity—remains independent of the number of dimensions, making it feasible for 2D analysis.

The algorithm operates in two main phases:

  1. Partitioning: The space is recursively split horizontally and vertically using dynamic programming to find optimal "cut lines" that maximize data compression.
  2. Merging: Adjacent rectangular regions are greedily merged if the combined region results in a shorter total code length, allowing for the creation of complex, irregular shapes.
The PALM process: alternating partitions followed by greedy merging to create flexible regions.

Results

PALM was evaluated using synthetic Gaussian mixtures and real-world spatial datasets, including GPS movement data from the DinoFun Amusement Park (9 million records) and Airbnb listings in Amsterdam (20,000 records).

Comparison showing PALM (right) captures the shape of a Gaussian mixture more accurately than standard 1D MDL or IPD methods.

Key findings include:

  • Superior Accuracy: PALM achieved higher log-likelihood on unseen test data compared to KDE, suggesting it captures underlying distributions more accurately without over-smoothing.
  • Efficiency: To reach the same level of error (MISE) as PALM, a standard fixed grid requires five times as many regions.
  • Convergence: Unlike some state-of-the-art multivariate methods, PALM's error consistently converges toward zero as sample size increases.

Conclusion

PALM provides a robust, self-adaptive framework for 2D density estimation. By combining MDL-based partitioning with a flexible merging step, it avoids the "curse of the grid" and captures complex spatial dependencies with minimal manual intervention. Future work will explore extending this framework to supervised discretization and higher-dimensional data spaces.

Summary updated

BibTeX
@article{yang2023unsupervised,
  author = {Lincen Yang and Mitra Baratchi and Matthijs van Leeuwen},
  title = {{Unsupervised Discretization by Two-dimensional MDL-based Histogram}},
  journal = {Machine Learning},
  year = {2023},
  doi = {10.1007/s10994-022-06294-6},
}
Figure