for the transactions to formalize background knowledge. They then use this model to compute the difference between the expected frequency of an itemset and its observed frequency in the data as a subjective measure of **interestingness.**
Despite its potential, this approach suffers from a few limitations. First, it may not always be clear how the Bayesian network needs to be designed to accord with the prior information. The approach is particularly impractical for data mining practitioners unfamiliar with Bayesian networks. Second, it treats transactions as i.i.d. random variables. And third and probably most seriously, the variables in the Bayesian network are the items (or attribute-values), such that prior information on individual transactions cannot be taken into account.

An approach that resolves all three these problems, albeit for particular types of data and prior information, is presented in Gionis et al (2007). In **this work,** the authors show how one can assess the significance of data mining **results** in binary databases with respect to prior information on the row and **column** sums. Their methodology relies on swap randomizations, which leave the row and column sums invariant. By iteratively applying swap randomizations they show how one can approximately sample from the uniform distribution **over** all databases with row and column sums as specified by the prior information.

This can be used by computationally intensive approaches (e.g. Gentle, 2005) for estimating the significance of data mining results as quantified by the **empirical** p-value. Later this work was extended to real-valued data (Ojala et al, 2008) and to more complex constraints besides row and column sums (Hanhijarvi et al, 2009).

The statistical assessment of data mining results using the randomization methods from Gionis et al (2007), Ojala et al (2008), Mannila (2008), and Hanhijarvi et al (2009) is extremely useful and deserves a central place in data mining practice. However, it would be even more useful if a model for prior information could be used to directly guide data mining algorithms toward the subjectively more interesting patterns. Unfortunately, from a practical point of view, the use of models that are defined implicitly in terms of invariants seems limited to posthoc **analyses. Indeed, it seems hard to scale algorithms that need to explore an**
entire search space of possible patterns if they need to assess each candidate by means of a randomization test or by referring to a large number of randomized data sets. Thus it is unclear if and how they could be used to define practical measures of interestingness other than empirical p-values. A further and at least as serious disadvantage of randomization methods is that their resolution is limited by the inverse of the number of randomized data sets considered. This is a problem in the highly relevant region of small p-values where a high resolution is important.

In contrast to this, an explicit analytical model capable of formalizing important types of prior information would enable one to assess patterns in an analytical way rather than in a computationally intensive way. Interestingness could then be quantified using exact hypothesis testing as in Gallo et al (2007, 2009), where a relatively simple independence model for items and transactions was used as a null model formalizing prior information. Alternatively, **information theoretic principles could be applied to quantify the information content**