文档介绍：第六章在大型数据库中挖掘关联规则
基于约束的挖掘
使用约束的必要性
在数据挖掘中常使用的几种约束：
知识类型约束：指定要挖掘的知识类型
如关联规则
数据约束：指定与任务相关的数据集
Find pro)
no
no
yes
partly
no
yes
partly
yes
no
partly
yes
no
partly
yes
no
partly
convertible
(yes)
反单调
单调
约束规则
可转变的约束 1
反单调可转变的
1. C(S)既不是单调性约束，也不是反单调性约束；
,使得经R排序后的I具有如下性质：
任给 S’∈{suffix_S}, if C(S)=>C(S’)
则C(S)是反单调可转变的
可转变性约束的例子1: Avg(S)  V
令I为一组以升序排列数值的项目集
. I={1，3，4，6，8，9, }， R意指升续
Avg(S) >= v 是反单调可转变的
如果 S ’ 是S的一个后缀, 那么avg(S’) >= avg(S)
{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
如果 S满足约束 avg(S) v, 则 S’也满足
可转变的约束 2
单调可转变的
1. C(S)既不是单调性约束，也不是反单调性约束；
,使得经R排序后的I具有如下性质：
任给 S’∈{suffix_S}, if C(S’)=>C(S)
则C(S)是单调可转变的
可转变性约束的例子 2 Avg(S)  V
令I为一组以降序排列数值的项目集
. I={9, 8, 6, 4, 3, 1}， R意指降续
Avg(S)  v 是单调可转变的
如果 S ’ 是S的一个后缀, 那么avg(S)  avg(S’)
{8, 4, 3} is a suffix of {9, 8, 4, 3}
avg({9, 8, 4, 3})=6  avg({8, 4, 3})=5
如果 S’满足约束 avg(S’) v, 则 S也满足
{8, 4, 3} satisfies constraint avg(S)  4, so does {9, 8, 4, 3}
简洁性约束
一个项目子集Is 是一个简洁集(succinct set), 如果对于某些选择性谓词p,该项目子集能够表示为p(I) ，此处， 是一个选择符
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
约束 Cs 是简洁的假如 SATCs(I)是一个强简洁集
简洁性约束的举例
约束规则
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
频繁数据集应用举例
交易数据库TDB如下所示，支持度为 3
频繁项目按照降续排列： a:5; e:4; b:3; c:3; d:3; f:3
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
频繁数据集应用举例(续)
将排序后的每次交易的项目列表的前缀项目映射到条件数据库TDB|f; TDB|