文档介绍：第六章 在大型数据库中 挖掘关联规则
报告人:张荣祖
2001/11/28
基于约束的挖掘
使用约束的必要性
在数据挖掘中常使用的几种约束:
知识类型约束:指定要挖掘的知识类型
如关联规则
数据约束: 指定与任务相关的数据集
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%).
假定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 =1999 &&=1999
&&=
(5)group by C,
(6)having sum(<=100)&&min()>=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”,_) [%,65%]
约束的分类
单调性约束(monotone constraint)
反单调性约束(anti-monotone constraint)
可转变的约束(convertibale constraint)
简洁性约束(inct constraint)
约束的有关概念
项目集:I={i1,i2,……,im},
交易:T=<tid,It>
模式S是项目集的子集,S={ij1,ij2,…,ijk}
模式S包含与T,T=<tid,It>,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
: Ca : min(S)>=v , v是S的一个项集
约束Cm (模式) S, 每一个S的超集都能够满足 Cm
: 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