Research activities

# Logical calculi of association rules

We deal with logical calculi of associational rules. Formulae of these calculi correspond to association rules. Formula – association rules concern data matrices. Association rule can be true or false in a data matrix M.

We deal with association rules that are generalization of rules mined by the procedure 4ft-Miner. We do not deal here with conditional associational rules. The association rule have the form of φ ψ where φ and ψ are the Boolean attributes.

The meaning of the association rule φ ψ is that the Boolean attributes φ and ψ are associated in the way given by the symbol . The symbol is called 4ft-quantifier.

There are predicate calculi of association rules. Examples of predicate association rules are

P1 P2 0.9, 100 P3    and    P1 P2 0.95, 50 P3 ¬P4.

Here 0.9, 100 is the 4ft-quantifier of founded implication and 0.95, 50 is the 4ft-quantifier of double founded implication.

Predicate calculi of association rules correspond to four-fold table predicate calculi [Ra 98A] and they are special case of monadic observational predicate calculi [Ha 78].

The calculi of association rules concern rules φ ψ where φ and ψ can be any correct combination of some basic Boolean attributes and Boolean connectives , ¬.

Examples of basic Boolean attributes and theirs values in data matrix M are in Fig. 1.

 Rows of M Attributes of M Examples of basic Boolean attributes A1 A2 … AK A1(1,2) A1(3) A1(4) o1 1 6 … B 1 0 0 o2 2 4 … C 1 0 0 o3 4 7 … G 0 0 1 … … … … … … … … on - 1 4 9 … F 0 0 1 on 3 8 … H 0 1 0

Examples of association rules are

A1(1,2) AK(B,G,H) 0.9, 100 A2(4,7,9)    and    A3(2,3,9) A4(1,2,9) 0.95, 50 ¬A5(3,6,8).

Calculi of association rules are defined and studied e.g. in [Ra 98C], see also [Ra 01B]. These calculi are special case of monadic predicate calculi defined [Ha 78].

The value of association rule φ ψ in data matrix M can be true or false. The true value of φ ψ in M depends on four-fold contingency table 4ft(φ, ψ, M) of φ and ψ in M, see Tab. 1.

Tab. 1 Four-fold contingency table 4ft(φ, ψ, M ) of φ and ψ in M
M ψ ¬ψ
φ a b
¬φ c d

Here a is the number of objects satisfying both φ and ψ, b is the number of objects satisfying φ and not satisfying ψ, c is the number of objects not satisfying φ and satisfying ψ, and d is the number of objects satisfying neither φ nor ψ.

There is a {0,1} function F associated to each 4ft-quantifier . The function F is defined for all quadruples a,b,c,d of integer non-negative numbers such that a + b + c + d > 0.

The association rule φ ψ is true in data matrix M if it is

F(a,b,c,d) = 1 where a,b,c,d = 4ft(φ, ψ, M).

We usually write only (a,b,c,d) instead of F(a,b,c,d).

Examples of 4ft quantifiers and their associated functions are 4ft quantifiers implemented in the procedure 4ft-Miner.