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:
- Partitioning: The space is recursively split horizontally and vertically using dynamic programming to find optimal "cut lines" that maximize data compression.
- 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.
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).
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