A Structure Function for Transaction Data
Arno P. J. M. Siebes, René Kersten · 2011
The ultimate goal of descriptive data mining – in fact of descriptive data analysis in general – is to gain insight in the structure of the data. While the best model may reflect all important structure of D, this is not true for a good model and algorithms often only return a good model rather than the best. Data sets, however, have many models. Different models of the same data set D highlight different aspects of the structure of D. Hence, it makes sense to consider multiple good models of D. The question is: which good models? In this paper we propose a solution for the case were the data is a transaction database [2] and the models are code tables [8]. More in particular, we introduce a structure function, based on the Minimum Description Length (MDL) principle [6]. This is a partial function from the set of natural numbers to the set of code tables for D; higher natural numbers are mapped to more complex code tables. Computing the structure function exactly is, unfortunately, too complex. Therefore we introduce the heuristic Groei algorithm, which approximates the true structure function. Through experiments we show that Groei produces a set of good code tables that together provide more insight than any of them alone.