Classes of Association Rules: An Overview - Data Mining: Foundations and Practice - page 321

ψ and ϕ ≈ ψ are association rules can be used at least in the

where ϕ ≈

following ways:

• To decrease the number of actually tested association rules: If the associ-

ation rule ϕ

ϕ≈ψ
ϕ ≈ψ

≈ ψ is true in the analysed data matrix and if is the

correct deduction rule, then it is not necessary to test ϕ ≈ ψ .

• To reduce output of a data mining procedure: If the rule ϕ ψ is included

in a data mining procedure output (thus it is true in an analysed data
matrix) and if

≈

ψ
ϕ ≈ψ is the correct deduction rule then it is not necessary
to put the association rule ϕ ≈

ϕ ≈

ψ into the output. The used deduction
rule must be transparent enough from the point of view of the user of the
data mining procedure. An example of a transparent deduction rule is a
dereduction deduction rule

ϕ⇒ ∗ ψ
ϕ⇒ ∗ ψ∨χ , that is correct for each implicational

⇒ ∗ [2].
Important examples of deduction rules of the form ϕ≈ψ

quantifier

ϕ ≈ψ and their in-
teresting properties are presented in [2, 8, 12]. It is shown in [12] that there
are transparent criteria of correctness of such deduction rules. These criteria
depend on the class of 4ft-quantifier ≈ . The criteria are informally introduced

in this section.
The criteria use the notion saying that the Boolean attribute ψ logically
follows from the Boolean attribute ϕ . Symbolically we write

ϕ ψ .

It is ϕ ψ if for each row o of each data matrix it is true: If ϕ is true in o

then also ψ is true in o . It is shown in [12] that there is a formula Ω ( ϕ,ψ )of
propositional calculus such that ϕ

ψ if and only if Ω ( ϕ,ψ ) is a tautology.
The formula Ω ( ϕ,ψ ) is derived from ϕ and ψ by a given way.
The criteria of correctness of deduction rules of the form

ϕ≈ψ

ϕ ≈ψ for implica-
tion quantifiers concern interesting implication quantifiers . The implicational
quantifier ⇒ ∗ is interesting if it satisfies:

•⇒ ∗ is a-dependent
•⇒ ∗ is b-dependent
•⇒ ∗ (0 , 0) = 0
The 4ft quantifier

≈ is a-dependent if there are non-negative integers a , a ,

b , c , d such that

= ≈ ( a ,b,c,d ) ≈ ( a,b,c,d )

and analogously for b-dependent 4ft-quantifier. The following theorem is
proved in [12]:
If ⇒ ∗ is the interesting implicational quantifier then the deduction rule

⇒ ∗ ψ
ϕ ⇒ ∗ ψ
is correct if and only if at least one of the conditions 1 or 2 are satisfied:

ϕ