Database Reference
In-Depth Information
is negative, negative association rules are generated when their confidence is high
enough. The produced rules have either the antecedent or the consequent negated:
(
¬
X
⇒
Y
and
X
⇒¬
Y
), even if the support is not higher than the support threshold.
However, if the correlation is positive, a positive association rule with the classical
support-confidence idea is generated. If the support is not adequate, a negative asso-
ciation rule that negates both the antecedent and the consequent is generated when
its confidence and support are high enough. They define the negative associations as
confined negative association rules
. A confined negative association rule is one of
the following:
Y
, where the entire antecedent or consequent is
treated as an atomic entity and the entire entity is either negated or not. These rules
are a subset of the entire set of generalized negative association rules.
In [
22
], authors extend an existing algorithm for association rule mining, GRD
(generalized rule discovery), to include negative items in the rules discovered. The
algorithm discovers top-k positive and negative rules. GRD does not operate in
the support confidence framework, it uses leverage and the number of rules to be
discovered. The limitation of the algorithm is that it mines rules containing no more
than 5 items (up to 4 items in the left hand side of the rule and 1 item in the right
hand side of the rule).
Cornelis et al. [
10
] proposed a new Apriori-based algorithm (PNAR) that exploits
the upward closure property of negative association rules that if support of
¬
X
⇒
Y
or
X
⇒¬
¬
X
meets the minimum support threshold, then for every
Y
⊆
I
such that
X
∩
Y
=
∅
(
XY
) also meets the support threshold. With this upward closure property,
valid positive and negative association rules are defined in the form of
C
1
,
¬
⇒
C
2
,
C
1
∈{
X
,
¬
X
}
,
C
2
∈{
Y
,
¬
Y
}
,
X
,
Y
⊆
I
,
X
∩
Y
=∅
, if it meets the following
conditions: (1)
s
(
C
1
⇒
C
2
)
≥
minsup
; (2)
s
(
X
)
≥
minsup
,
s
(
Y
)
≥
minsup
; (3)
X
, then there does not exist
X
⊆
conf
(
C
1
⇒
C
2
)
≥
minconf
; (4) If
C
1
=¬
X
such
X
⇒
that
s
(
minsup
(analogously for
C
2
). Then, the algorithm of mining
both positive and negative valid association rules is built up around a partition of the
itemset space by 4 steps: (1) generate all positive frequent itemsets
L
(
P
1
); (2) for all
itemsets
I
in
L
(
P
1
), generate all negative frequent itemsets of the form
¬
C
2
)
≥
¬
(
XY
); (3)
generate all negative frequent itemsets of the form
¬
X
¬
Y
; (4) generate all negative
frequent itemsets of the form
X
XY
. The complete set of valid positive
and negative association rules are derived after frequent itemsets are generated. No
additional interesting measures are required in this support-confidence framework.
Wang et al. [
23
] gave a more intuitive way to express the validity of both positive
and negative association rules, the mining process is very similar to PNAR.
MINR [
15
] is a method that uses Fisher's exact test to identify item sets that do
not occur together by chance, i.e. with a statistical significant probability. Let
X
and
Y
denote the disjoint itemsets in the antecedent and consequent part of a rule,
respectively. The probability that
X
and
Y
occur together with
c
times by chance is:
¬
Y
or
¬
s
(
X
c
n
−
s
(
X
)
c
s
(
Y
)
−
n
s
(
Y
)
Pcc
(
c
|
n
,
s
(
X
),
s
(
Y
))
=
(6.3)
