8002824271

20 Bartosz Bielski, Przemysław Klęsk

4.1. Greedy induction of decision rules

Say we want to find all possible rules with the length of premise equal to p, i.e. in the premise there are exactly p terms connected with ‘and’. For example, when p = 3 a possible rule is:

if (*3 = 2) and (x₅ = 3) and (x₆ = 1) then (y = 2).

p=3

The algorithm to find all such rules can be named as greedy - meaning that we will iterate over all J combinations of input variables Xj and for each single combination

we will also iterate over all possible settings of values for these variables.

The exact total number of iterations in such an algorithm (and in the same time the

total number of rules) can be calculated as follows. Let C_{n p} be the set of all |"J combinations of indices of variables. E.g.: C₄₂ = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}. The exact number of iterations is then equal to

(1)

And if we wanted to find all rules with premises of length equal to p or less than p then the number of iterations (and rules) is

X X    (2)

^k='u_vj₂,...,j_k^C_nk

For a single fixed premise what should be the value chosen as the decision? Let X be a generał notation for the premise and Y for the decision, e.g.:

if (jc₃ = 2) and (.x₅ = 3) and (*₆ =1) then (y = 2).

X^x    Y=y

Then, for a fixed premise X = x we deal with a certain conditional probability dis-tribution of decisions P(Y I X = x). In other words, from the whole data set we take the subset containing only the cases where X = x and within this subset we look at the distribution of different decisions y e {l,2,...,m_v}. As the decision value we choose such y for which P(Y = y I X = jc) is maximal.

4.2. Rule assessment measures

Each rule should be assigned a certain number assessing how interesting this rule is and how statistically relevant it is for the decision. The most basie and common meas-