数据挖掘6章关联3

数据挖掘6章关联3null第六章在大型数据库中挖掘关联规则第六章在大型数据库中挖掘关联规则报告人：张荣祖 2001/11/28 6.6.1 基于约束的挖掘6.6.1 基于约束的挖掘使用约束的必要性在数据挖掘中常使用的几种约束：知识类型约束：指定要挖掘的知识类型如关联规则数据约束：指定与任务相关的数据集 Find product pairs sold together in Vancouver in Dec.’98. 维/层次约束:指定所用的维或概念结构中的层 in relevance to reg...

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) ，此处， 是一个选择符 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)几种约束之间的关系几种约束之间的关系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算法及其改进

                    本文档为【数据挖掘6章关联3】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

数据挖掘6章关联3

你可能还喜欢