1 / 21

# 数据挖掘教程：在大型数据库中挖掘关联规则.ppt

6.6.1 基于约束的挖掘

Find pro)
no
no
yes
partly
no
yes
partly
yes
no
partly
yes
no
partly
yes
no
partly
convertible
(yes)

1. C(S)既不是单调性约束，也不是反单调性约束；
2.若存在顺序R,使得经R排序后的I具有如下性质：

E.g. I={1，3，4，6，8，9, }， R意指升续
Avg(S) >= v 是反单调可转变的

{6,8,9} is a suffix of {3,4,6,8,9}
avg({6,8,9})=23/3  avg({3,4,6,8,9})=6

1. C(S)既不是单调性约束，也不是反单调性约束；
2.若存在顺序R,使得经R排序后的I具有如下性质：

E.g. I={9, 8, 6, 4, 3, 1}， R意指降续
Avg(S)  v 是单调可转变的

{8, 4, 3} is a suffix of {9, 8, 4, 3}
avg({9, 8, 4, 3})=6  avg({8, 4, 3})=5

{8, 4, 3} satisfies constraint avg(S)  4, so does {9, 8, 4, 3}

SP2I 是一个强简洁集( succinct power set),如果有一个数目不变的简洁集 I1, …, Ik I, SP 能够用I1, …, Ik 的并、差运算表示出来
be expressed in terms of the strict power sets of I1, …, Ik using union and minus

v  S
S V
S  V
S  V
min(S)  v
min(S)  v
min(S)  v
max(S)  v
max(S)  v
max(S)  v
count(S)  v
count(S)  v
count(S)  v
sum(S)  v
sum(S)  v
sum(S)  v
avg(S)  v,   { , ,  }
(frequent constraint)

yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
weakly
weakly
weakly
no
no
no
no
(no)

Succinctness
Anti-monotonicity
Monotonicity
Convertible constraints
Inconvertible constraints

Transaction_ID
Items In Transaction
100
a,e,c,d,,f
200
a,b
300
a,e,c,f
400
a,e,b,c,d,f
500
a,e,b,d