
## 5.2.3 The Compression Ratio Of A Tile As Interestingness Measure

The interestingness of a tile can now be quantified as the ratio with which information is compressed in the tile pattern:

 $\mathrm{CompressionRatio}(\tau)\quad=\quad\dfrac{\mathrm{SelfInformation}(\tau)}{\mathrm{DescriptionLength}(\tau)}.\qquad\qquad(21)$ . 
This ratio expresses the number of bits of information received by the data miner (with respect to the MaxEnt model), per bit received to describe the tile τ**. Tiles that have the largest compression ratio are thus most efficient at**
communicating aspects of the data the data miner did not expect a priori.

## 5.2.4 Finding Interesting Sets Of Tiles

It is well-known that the set of individually most interesting patterns **is often** not the most interesting set of patterns, regardless of which interestingness measure is used (see e.g. De Raedt and Zimmermann (2007)). This is due to redundancies between the patterns that are individually interesting. So the question arises if we can also use the above tools to define the interestingness of a set of tiles T = {τ1, . . . , τN }**. It turns out the approach generalizes easily.**
Furthermore, it yields an additional formal argument in favour of using the ratio of the self-information and description length as interestingness measure for an individual tile.

Describing a set of tiles requires one to describe each of the tiles in the set. Hence, the description length of a set of tiles is quantified by the sum of the description lengths of each of the tiles individually. Slightly overloading notation, for a set of tiles T = {τ1**, . . . , τ**N }:

$$\begin{array}{r c l}{{\mathrm{DescriptionLength}(\mathcal{T})}}&{{=}}&{{\sum_{i=1:N}\mathrm{DescriptionLength}(\tau_{i}).}}\end{array}$$

The self-information of a set of tiles is generalized as the negative logprobability that all tiles in the set are present in the database. Due to the independence of the database entries under the MaxEnt distribution, this is equal to the sum of the negative log-probabilities that D(i, j**) = 1 for all the**
database entries (i, j) belonging to some tile τ ∈ T **. Formally:**

$$\begin{array}{r c l}{{\mathrm{SelfInformation}(\mathcal{T})}}&{{=}}&{{-\sum_{(i,j):\exists\tau\in\mathcal{T}{\mathrm{~with~}}(i,j)\in\tau}\log(p_{i j}),}}\\ {{}}&{{}}&{{}}\end{array}$$

with pij **as defined in Eq. (19).**
In practice, we argue that a data miner has a bounded capacity of taking in and processing patterns. Given this capacity, the data miner would like to receive as much information as possible. In this setting, tile set mining **can be** formalized by the following optimization problem:

 $\frac{\text{In}\Delta\lambda}{T}$ . 
$$\mathbf{s.t.}$$
max
T
SelfInformation(T ),
$${\mathrm{DescriptionLength}}(T)\leq u$$
$\nu$ $J$ . 