Unsupervised discretization by two-dimensional MDL-based histogram

DOI10.1007/S10994-022-06294-6MaRDI QIDQ6134323zbMATH OpenOpenAlexFDO

Authors Lincen Yang, Mitra Baratchi, Matthijs van Leeuwen

Publication date 22 August 2023

Published in Machine Learning (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2006.01893

zbMATH Keywords

density estimationexploratory data analysishistogram modelunsupervised discretization

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Abstract: 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.

Recommendations

• Multivariate unsupervised discretization preserving mutual information
• Unsupervised interaction-preserving discretization of multivariate data
• MODL: a Bayes optimal discretization method for continuous attributes
• Multi-relational discretization methods
• Multivariate discretization for set mining

Cites work

• A clustering-based discretization for supervised learning
• A linear-time algorithm for computing the multinomial stochastic complexity
• A plug-in approach to support estimation
• Bayesian density estimation via dirichlet density processes
• Khiops: A statistical discretization method of continuous attributes
• Minimum description length revisited
• Model Selection and the Principle of Minimum Description Length
• Modeling by shortest data description
• MODL: a Bayes optimal discretization method for continuous attributes
• Multivariate density estimation by Bayesian sequential partitioning
• Multivariate density estimation. Theory, practice, and visualization
• Multivariate discretization for set mining
• On Rates of Convergence for Bayesian Density Estimation
• Plug-in bandwidth matrices for bivariate kernel density estimation
• Posterior concentration for Bayesian regression trees and forests
• The minimum description length principle for pattern mining: a survey
• Unsupervised interaction-preserving discretization of multivariate data

This page was built for publication: Unsupervised discretization by two-dimensional MDL-based histogram

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6134323)