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

P₁ ∧ P₂ ⇒_{0.9, 100} P₃    and    P₁ ∨ P₂ ⇔_{0.95, 50} P₃ ∧ ¬P₄.

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.

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

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

A₁(1,2) ∧ A_K(B,G,H) ⇒_{0.9, 100} A₂(4,7,9)    and    A₃(2,3,9) ∨ A₄(1,2,9) ⇔_{0.95, 50} ¬A₅(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.