Database Reference
In-Depth Information
For instance, in itemset mining, the subset relation is usually used as generality
relation as well: an itemset
π
1
is more general than an itemset
π
2
iff
π
1
⊆
π
2
.
Based on the generality relationship, we can define the
anti-monotonicity
property
of constraints
1
. A constraint
ϕ
(
π
,
D
) is called anti-monotonic iff it holds for all
patterns
π
1
,
π
2
that
if
π
1
π
2
and
ϕ
(
π
1
,
D
) is false, then
ϕ
(
π
2
,
D
) is false.
Minimum support is the most well-known constraint that is anti-monotonic, but
several other constraints are also anti-monotonic [
11
,
20
]. Assuming that we use
the subset relation to determine the generality relation, the following constraints on
itemsets are anti-monotonic:
the maximum length constraint
|
π
|≤
θ
forafixed
θ
;
the maximum sum of costs constraint
c
(
π
)
θ
is anti-monotonic, where
c
(
π
)
sums up the costs of the items in the itemset,
c
(
π
)
≤
=
i
∈
π
c
(
i
), and
c
(
i
)
≤
0is
a cost that is associated to each item;
a generalization constraint, which for a given set
I
requires that all itemsets found
satisfy
π
⊆
I
;
conjunctions or disjunctions of other anti-monotonic constraints.
These constraints can be generalized to other types of patterns as well.
Monotonocity
Closely related to anti-monotonicity is monotonicity. A constraint
is called
monotonic
iff for all patterns
π
1
,
π
2
:
if
π
1
π
2
and
ϕ
(
π
1
,
D
) is true, then
ϕ
(
π
2
,
D
) is true.
In other words, monotonicity is the “reverse” of anti-monotonicity; if a constraint
ϕ
(
π
) is anti-monotonic, its negation
¬
ϕ
(
π
) is monotonic. This includes constraints
such as:
the maximum support constraint
|{
d
∈
D
|
π
⊆
d
}| ≤
θ
;
the minimum size constraint
|
π
|≥
θ
;
≥
the minimum sum of costs constraint
c
(
π
)
θ
;
⊆
a negated generalization constraint
π
I
;
a specialization constraint
π
⊇
I
.
This relationship between monotonic and anti-monotonic constraints, one of reversal
and negation, already hints at the difficulty in using both types of constraints at the
same time for efficient pattern enumeration.
Convertible (anti)-monotonicity
Whether a constraint is (anti)-monotonic depends
on the generality relation chosen. One of the most well-known examples is that of
the maximum
average cost
of an itemset,
c
(
π
)
=
i
∈
π
c
(
i
)
/
θ
. If we use the
subset relation to define the generality, this constraint is not anti-monotonic. Consider
the following two items with their corresponding costs:
c
(1)
|
π
|≥
=
1 and
c
(2)
=
3. If
our cost threshold is 2, the average cost of
{
1, 2
}
is 2 and satisfies the requirement;
however, itemset
{
2
}
, while a subset, does not satisfy the constraint.
1
Note that in some publications, anti-monotonic constraints are called monotonic, and monotonic
constraints anti-monotonic [
20
].
