Unsupervised interaction-preserving discretization of multivariate data

Discretization is the transformation of continuous data into discrete bins. It is an important and general pre-processing technique, and a critical element of many data mining and data management tasks. The general goal is to obtain data that retains as much information in the continuous original as...

Full description

Saved in:
Bibliographic Details
Published in:Data mining and knowledge discovery 2014-09, Vol.28 (5-6), p.1366-1397
Main Authors: Nguyen, Hoang-Vu, Müller, Emmanuel, Vreeken, Jilles, Böhm, Klemens
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Artificial Intelligence
Chemistry and Earth Sciences
Computer Science
Data mining
Data Mining and Knowledge Discovery
Discretization
Dynamic programming
Encoding
Exact solutions
Information Storage and Retrieval
Methods
Physics
Preserving
Statistics for Engineering
Tasks
Transformations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Discretization is the transformation of continuous data into discrete bins. It is an important and general pre-processing technique, and a critical element of many data mining and data management tasks. The general goal is to obtain data that retains as much information in the continuous original as possible. In general, but in particular for exploratory tasks, a key open question is how to discretize multivariate data such that significant associations and patterns are preserved. That is exactly the problem we study in this paper. We propose IPD , an information-theoretic method for unsupervised discretization that focuses on preserving multivariate interactions. To this end, when discretizing a dimension, we consider the distribution of the data over all other dimensions. In particular, our method examines consecutive multivariate regions and combines them if (a) their multivariate data distributions are statistically similar, and (b) this merge reduces the MDL encoding cost. To assess the similarities, we propose I D , a novel interaction distance that does not require assuming a distribution and permits computation in closed form. We give an efficient algorithm for finding the optimal bin merge, as well as a fast well-performing heuristic. Empirical evaluation through pattern-based compression, outlier mining, and classification shows that by preserving interactions we consistently outperform the state of the art in both quality and speed.
ISSN:1384-5810
1573-756X
DOI:10.1007/s10618-014-0350-5