null第六章
在大型数据库中
挖掘关联规则第六章
在大型数据库中
挖掘关联规则
报告人:张荣祖
2001/11/28
6.6.1 基于约束的挖掘6.6.1 基于约束的挖掘使用约束的必要性
在数据挖掘中常使用的几种约束:
知识类型约束:指定要挖掘的知识类型
如关联规则
数据约束: 指定与任务相关的数据集
Find product pairs sold together in Vancouver in Dec.’98.
维/层次约束:指定所用的维或概念结构中的层
in relevance to region, price, brand, customer category.
规则约束:指定要挖掘的规则形式(如规则
)
单价 (price < $10)的交易项目可能引发购买总额 (sum > $200).
兴趣度约束:指定规则兴趣度阈值或统计度量
如 (min_support 3%, min_confidence 60%).null假定AllElectronics的一个销售多维数据库有如下关系:
Sales(customer_name,item_name,transaction_id)
Lives(customer_name,region,city)
Items(item_name,category,price)
Transaction(transaction_id,day,month,year)
(1) mine associations as
(2)lives(C,_,”Pudong”)^sales(C,{I},{S})=>sales(C,{J}{T})
(3) from sales
(4)where S.year=1999 &&T.year=1999
&&I.category=J.category
(5)group by C,I.category
(6)having sum(I.price<=100)&&min(J.price)>=500
(7)with support threshold=1%
(8)with confidence threshold=50%
Lives(C,_,”Pudong”)^Sales(C,”Census_CD”,_)^Sales(C,”MS/Office”,_)=>Sales(C,”MS/SQLSever”,_) [1.5%,65%]6.6.2 约束的分类6.6.2 约束的分类单调性约束(monotone constraint)
反单调性约束(anti-monotone constraint)
可转变的约束(convertibale constraint)
简洁性约束(succinct constraint)约束的有关概念约束的有关概念项目集:I={i1,i2,……,im},
交易:T=
模式S是项目集的子集,S={ij1,ij2,…,ijk}
模式S包含与T,T=,iff S<=It;
S’是S的子模式(subpattern)且S 是S’的超模式(superpattern),if 有S’<=S.约束的有关概念(续)约束的有关概念(续)定义约束: C是作用于项目集I的幂集(powerset)上的谓词,C(S)=True/False;
满意模式集(satisfying pattern set)
SATc(I)是指那些完全满足约束C的项目集的全体
将约束条件用于频繁集的查询无非是找出那些满足C的频繁集
单调和反单调的规则约束单调和反单调的规则约束规则 Ca 是 反单调的(anti-monotone) iff
对于任给的不满足Ca的项集(模式) S, 不存在S的超集能够满足 Ca
e.g: Ca : min(S)>=v , v是S的一个项集
约束Cm 是单调的iff.对于任给的满足Cm的项集(模式) S, 每一个S的超集都能够满足 Cm
e.g: Cm : min(S)<=v, v是S的一个项集
单调/反单调性约束描述单调/反单调性约束描述
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
no
partly
yes
no
partly
no
yes
partly
no
yes
partly
no
yes
partly
convertible
(no)
no
no
yes
partly
no
yes
partly
yes
no
partly
yes
no
partly
yes
no
partly
convertible
(yes)反单调单调约束规则可转变的约束 1可转变的约束 1反单调可转变的
1. C(S)既不是单调性约束,也不是反单调性约束;
2.若存在顺序R,使得经R排序后的I具有如下性质:
任给 S’∈{suffix_S}, if C(S)=>C(S’)
则C(S)是反单调可转变的可转变性约束的例子1:
Avg(S) V可转变性约束的例子1:
Avg(S) V令I为一组以升序排列数值的项目集
E.g. 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可转变的约束 2单调可转变的
1. C(S)既不是单调性约束,也不是反单调性约束;
2.若存在顺序R,使得经R排序后的I具有如下性质:
任给 S’∈{suffix_S}, if C(S’)=>C(S)
则C(S)是单调可转变的可转变性约束的例子 2
Avg(S) V可转变性约束的例子 2
Avg(S) V令I为一组以降序排列数值的项目集
E.g. 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) ,此处, 是一个选择符
SP2I 是一个强简洁集( 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)几种约束之间的关系几种约束之间的关系SuccinctnessAnti-monotonicityMonotonicityConvertible constraintsInconvertible constraints频繁数据集应用举例频繁数据集应用举例交易数据库TDB如下所示,支持度为 3
频繁项目按照降续排列 : a:5; e:4; b:3; c:3; d:3; f:3频繁数据集应用举例(续)频繁数据集应用举例(续)将排序后的每次交易的项目列表的前缀项目映射到条件数据库TDB|f; TDB|d; TDB|c; TDB|b; TDB|e频繁集的生长过程频繁集的生长过程性质:如果模式α在 TDB|f 中是频繁的,则α ∪f 在TDB|f中也一定是频繁的
频繁集的生长过程
1.在 TDB|f 中找到相应的频繁项目集β, β被称为f的条件频繁项目集
2.对于每一个在β中的频繁项目e,找出TDB|ef 中相应的频繁项目集,这是一个递归的过程将约束用于频繁集的生成将约束用于频繁集的生成Ca≡Sum(S)<=180
使用图表2的交易数据库:support=3
{a,s,b,c,d,e,f}={50,150,10,200,20,80}
将约束用于挖掘的几种策略将约束用于挖掘的几种策略去除不满足约束的单个项目
Exam1: Sum(d)=200>180
如果α不满足约束,则不必产生α的条件项目集,也不必产生α的条件数据库TDB | α
Exam2: Sum({a,b})=200
如果α ∪ β满足约束,则不必对条件数据库TDB| α 中的其余部分用Ca进行约束检查,此处β是在TDB | α 中 的频繁项目集
(No constraint checking in the remaining conditional database TDB| α, if α ∪ β satisfies the constraint.)小结小结常见的4种约束类型
规则约束的分类及其性质
I. 单调/反单调
ii. 可转变的
iii.简洁的
CFG算法及其改进