1、2022-12-22Data Mining:Concepts and Techniques1数据挖掘：概念与技术Jiawei Han and Micheline Kamber著Monrgan Kaufmann Publishers Inc.范明 孟小峰等译机械工业出版社一二请在这里输入您的主要叙述内容整体概述三请在这里输入您的主要叙述内容请在这里输入您的主要叙述内容2022-12-22Data Mining:Concepts and Techniques3第6章挖掘大型数据库中的关联规则英文幻灯片制作：Jiawei Han中文幻灯片编译：范明2022-12-22Data Mining:Conc
2、epts and Techniques4第6章：挖掘大型数据库中的关联规则n关联规则挖掘n事务数据库中(单维布尔)关联规则挖掘的可伸缩算法n挖掘各种关联/相关规则 n基于限制的关联挖掘-n顺序模式挖掘n频繁模式挖掘的应用/扩展n小结2022-12-22Data Mining:Concepts and Techniques5什么是关联规则挖掘?n关联规则挖掘:n发现事务数据库,关系数据,或其它信息库中项或数据对象集合间的频繁模式,关联,相关,或因果关系结构.n频繁模式:在数据库中频繁出现的模式(项集,序列,等)AIS93n动机:发现数据中的规律性n哪些产品更经常一起购买?啤酒 和 尿布?!n购买
3、了PC后,哪些将相继购买?n什么类型的 DNA 对新药敏感?n我们能自动地对Web稳当分类吗?2022-12-22Data Mining:Concepts and Techniques6为什么频繁模式挖掘是数据挖掘的基本任务?n许多基本的数据挖掘任务的基础n关联,相关,因果关系n序列模式,时间或周期关联,局部周期性,空间和多媒体关联n关联分类,聚类分析,冰山方,fascicles(语义数据压缩)n广泛的应用n购物篮数据分析,交叉销售,分类设计,销售活动分析nWeb 日志(点击流)分析,DNA 序列分析,等.2022-12-22Data Mining:Concepts and Technique
4、s7基本概念:频繁模式和关联规则nItemset X=x1,xkn找出满足最先支持度和置信读的所规则 XY n支持度,s,事务包含 X Y 的概率 n置信度,c,事务含 X 也包含 Y 的条件概率.设 min_support=50%,min_conf =50%:A C (50%,66.7%)C A (50%,100%)顾客购买尿布顾客购买二者顾客购买啤酒Transaction-idItems bought10A,B,C20A,C30A,D40B,E,F2022-12-22Data Mining:Concepts and Techniques8挖掘关联规则一个例子规则 A C:支持度=suppo
5、rt(A C)=50%置信度=support(A C)/support(A)=66.6%最小支持度 50%最小置信度 50%Transaction-idItems bought10A,B,C20A,C30A,D40B,E,FFrequent patternSupportA75%B50%C50%A,C50%2022-12-22Data Mining:Concepts and Techniques9第6章：挖掘大型数据库中的关联规则n关联规则挖掘n事务数据库中(单维布尔)关联规则挖掘的可伸缩算法n挖掘各种关联/相关规则 n基于限制的关联挖掘-n顺序模式挖掘n频繁模式挖掘的应用/扩展n小结2022-
6、12-22Data Mining:Concepts and Techniques10Apriori:一种候选产生-测试方法n频繁项集的任何子集必须是频繁的n如果 beer,diaper,nuts 是频繁的,beer,diaper也是n每个包含 beer,diaper,nuts的事务 也包含 beer,diaper nApriori 剪枝原则:n如果一个项集不是频繁的,将不产生/测试它的超集!n方法:n由长度为k的频繁项集产生长度为(k+1)的候选项集,并且n根据 DB测试这些候选n性能研究表明了它的有效性和可伸缩性nAgrawal&Srikant 1994,Mannila,et al.1994
7、2022-12-22Data Mining:Concepts and Techniques11Apriori 算法 一个例子数据库 TDB第1次扫描C1L1L2C2C2第2次扫描C3L3第3次扫描TidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA,BA,CA,EB,CB,EC,EItemsetsupA,B1A,C2A,E1B,C2B,E3C,E2ItemsetsupA,C2B,C2B,E3C,E2ItemsetB,C,EItemsetsupB,C,E22022-12-22Data
8、Mining:Concepts and Techniques12Apriori 算法n算法伪代码:Ck:长度为 k的候选项集Lk:长度为k的频繁项集L1=频繁项;for(k=1;Lk!=;k+)do begin Ck+1=由 Lk产生的候选;for each 数据库中的事务 t do 增加包含在t 中的所有候选Ck+1的计数 Lk+1 =Ck+1 中满足 min_support的候选 endreturn k Lk;2022-12-22Data Mining:Concepts and Techniques13Apriori的重要细节n如何产生候选?n步骤 1:Lk的自连接 n步骤 2:剪枝n入何
9、对候选的支持度计数?n候选产生的例子nL3=abc,abd,acd,ace,bcdn自连接:L3*L3nAbcd：由 abc 和 abdnAcde：由 acd 和 acen剪枝:nacde 被删除,因为 ade 不在 L3nC4=abcd2022-12-22Data Mining:Concepts and Techniques14如何产生候选?n假定 Lk-1 中的项集已排序n步骤 1:Lk-1自连接 insert into Ckselect p.item1,p.item2,p.itemk-1,q.itemk-1from Lk-1 p,Lk-1 qwhere p.item1=q.item1,p
10、.itemk-2=q.itemk-2,p.itemk-1 q.itemk-1nStep 2:剪枝forall itemsets c in Ck doforall(k-1)-subsets s of c doif(s is not in Lk-1)then delete c from Ck2022-12-22Data Mining:Concepts and Techniques15如何对候选的支持度计数?n为什么对候选的支持度计数是一个问题?n候选的总数可能非常大n 一个事务可能包含多个候选n方法:n候选项集存放在一个 hash-树中nhash-树的叶结点 包含一个项集和计数的列表n内部 结点
11、包含一个hash 表n子集函数:找出包含在一个事务中的所有候选2022-12-22Data Mining:Concepts and Techniques16例:候选支持度计数1,4,72,5,83,6,9 子集函数2 3 45 6 71 4 51 3 61 2 44 5 71 2 54 5 81 5 93 4 53 5 63 5 76 8 93 6 73 6 8事务:1 2 3 5 61+2 3 5 61 2+3 5 61 3+5 62022-12-22Data Mining:Concepts and Techniques17Apriori 用 SQL有效实现n仅有基于纯的 SQL(SQL-9
12、2)的方法,很难获得好的性能n使用对象-关系扩展,如UDFs,BLOBs,表函数等.n提高一个数量级nS.Sarawagi,S.Thomas,and R.Agrawal.Integrating association rule mining with relational database systems:Alternatives and implications.In SIGMOD982022-12-22Data Mining:Concepts and Techniques18频繁模式挖掘的挑战n挑战n事务数据库的多遍扫描n数量巨大的候选n候选支持度计数繁重的工作量n改进 Apriori:基
13、本思想n减少事务数据库的扫描遍数n压缩候选数量n便于候选计数2022-12-22Data Mining:Concepts and Techniques19DIC(Dynamic itemset counting):减少扫描次数ABCDABCABDACD BCDABACBCADBDCDABCDItemset latticen一旦确定 A 和 D 是频繁的,立即开始 AD 的计数n一旦确定 BCD 的两个长度为2的子集是频繁的,立即开始BCD 的计数事务1-itemsets2-itemsetsApriori1-itemsets2-items3-itemsDICS.Brin R.Motwani,J.
14、Ullman,and S.Tsur.Dynamic itemset counting and implication rules for market basket data.In SIGMOD972022-12-22Data Mining:Concepts and Techniques20划分:只扫描数据库两次n项集在DB中是频繁的,它必须至少在DB的一个划分中是频繁的n扫描 1:划分数据库,并找出局部频繁模式n扫描 2:求出全局频繁模式nA.Savasere,E.Omiecinski,and S.Navathe.An efficient algorithm for mining assoc
15、iation in large databases.In VLDB952022-12-22Data Mining:Concepts and Techniques21选样计算频繁模式n选取原数据库的一个样本,使用Apriori 算法在样本中挖掘频繁模式n扫描一次数据库,验证在样本中发现的频繁模式.只验证频繁项集闭包的 边界n例如:验证 abcd,而不是验证 ab,ac,etc.n再次扫描数据库,找出遗漏的频繁模式nH.Toivonen.Sampling large databases for association rules.In VLDB962022-12-22Data Mining:Con
16、cepts and Techniques22DHP:压缩候选的数量n一个其hash桶的计数小于阈值的k-itemset 不可能是频繁的n候选:a,b,c,d,enHash 条目:ab,ad,ae bd,be,de n频繁 1-itemset:a,b,d,en如果 ab,ad,ae 的计数和小于支持度阈值,ab 不是候选2-itemset nJ.Park,M.Chen,and P.Yu.An effective hash-based algorithm for mining association rules.In SIGMOD952022-12-22Data Mining:Concepts a
17、nd Techniques23Eclat/MaxEclat and VIPER:Exploring Vertical Data FormatnUse tid-list,the list of transaction-ids containing an itemsetnCompression of tid-listsnItemset A:t1,t2,t3,sup(A)=3nItemset B:t2,t3,t4,sup(B)=3nItemset AB:t2,t3,sup(AB)=2nMajor operation:intersection of tid-listsnM.Zaki et al.New
18、 algorithms for fast discovery of association rules.In KDD97nP.Shenoy et al.Turbo-charging vertical mining of large databases.In SIGMOD002022-12-22Data Mining:Concepts and Techniques24频繁模式挖掘的瓶颈n多遍数据库扫描是 昂贵的n挖掘长模式需要很多遍扫描,并产生大量候选n挖掘频繁模式 i1i2i100n扫描次数:100n候选个数:(1001)+(1002)+(110000)=2100-1=1.27*1030!n瓶
19、颈:候选产生-测试n能够避免候选产生吗?2022-12-22Data Mining:Concepts and Techniques25挖掘频繁模式而不产生候选n使用局部频繁的项,由短模式增长产生长模式n“abc”是频繁模式n得到包含“abc”的所有事务:DB|abcn“d”是 DB|abc 中的局部频繁项 abcd 是频繁模式2022-12-22Data Mining:Concepts and Techniques26由事务数据库构造FP-树f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p3
20、min_support=3TIDItems bought (ordered)frequent items100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300 b,f,h,j,o,wf,b400 b,c,k,s,pc,b,p500 a,f,c,e,l,p,m,nf,c,a,m,p扫描 DB 一次,找出频繁 1-itemset(单个项的模式)按频率的降序将频繁项排序,得到 f-list再次扫描 DB,构造 FP-树F-list=f-c-a-b-m-p2022-12-22Data Mining:Concepts and Techniques2
21、7FP-树结构的优点n完全性 n保留频繁模式挖掘的完整信息n不截断任何事务的长模式n压缩性n压缩无关信息非频繁的项被删除n项按频率的降序排列:越是频繁出现,越可能被共享n绝对不比原来的数据库大(不计结点链和计数字段)n对于Connect-4 DB,压缩率超过 1002022-12-22Data Mining:Concepts and Techniques28划分模式和数据库n可以按照f-list 将频繁模式划分成子集nF-list=f-c-a-b-m-pn包含 p的模式n包含 m 但不包含 p的模式nn包含 c 但不包含 a,b,m,pn模式 fn完全性和非冗余性2022-12-22Data
22、Mining:Concepts and Techniques29从p-条件数据库找出含p的模式n从FP-树的频繁项头表开始n沿着频繁项p 的链搜索FP-树n收集项 p 的所有变换的前缀路径 形成p 的模式基条件 模式基itemcond.pattern basecf:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfcam:2,cb:1f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Item frequency head f4c4a3b3m3p32022-12-22Data Mining:Concepts and Techniques30从条件模式基到条
23、件FP-树 n对于每个条件模式基n累计条件模式基中每个项的计数n构造模式基中频繁项的FP-树m-条件 模式基:fca:2,fcab:1f:3c:3a:3 m-条件 FP-树涉及 m的所有频繁模式m,fm,cm,am,fcm,fam,cam,fcamf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Item frequency head f4c4a3b3m3p32022-12-22Data Mining:Concepts and Techniques31递归:挖掘每个条件 FP-树f:3c:3a:3m-条件 FP-树“am”的条件模式基:(fc:3)f:3c:3am-条件 F
24、P-树“cm”的条件模式基:(f:3)f:3cm-条件 FP-树“cam”的条件模式基:(f:3)f:3cam-条件 FP-树2022-12-22Data Mining:Concepts and Techniques32特殊情况:FP-树中的单个前缀路径n假定(条件)FP-树 T 具有单个共享的前缀路径Pn挖掘可以分解成两步n将单个前缀路径归约成 一个结点n连接两部分的挖掘结果a2:n2a3:n3a1:n1b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1r1=2022-12-22Data Mining:Concepts and
25、 Techniques33使用FP-树挖掘频繁模式n基本思想:频繁模式增长n通过模式和数据库划分递归地增长频繁模式n方法 n对于每个频繁项,构造它的条件模式基,然后构造它的条件 FP-树n在新构造的条件FP-树上重复这一过程n直到结果条件 FP-树为空,或者它只包含一条路径单个路径将产生其子路径的所有组合,每个子路径是一个频繁模式2022-12-22Data Mining:Concepts and Techniques34FP-增长的规模化nFP-树不能放在内存,怎么办?数据库投影n数据库投影n首先将数据库划分成一组投影 数据库n然后对每个投影数据库构造并挖掘FP-树n并行投影 vs.划分投影
26、 技术n并行投影空间花费很大2022-12-22Data Mining:Concepts and Techniques35基于划分的投影n并行 投影 需要大量磁盘空间n划分投影 节省Tran.DB fcampfcabmfbcbpfcampp-proj DB fcamcbfcamm-proj DB fcabfcafcab-proj DB fcba-proj DBfcc-proj DBff-proj DB am-proj DB fcfcfccm-proj DB fff2022-12-22Data Mining:Concepts and Techniques36FP-增长 vs.Apriori:随支
27、持度增长的可伸缩性010203040506070809010000.511.522.53Support threshold(%)Run time(sec.)D1 FP-grow th runtimeD1 Apriori runtimeData set T25I20D10K2022-12-22Data Mining:Concepts and Techniques37FP-增长 vs.树-投影:随支持度增长的可伸缩性02040608010012014000.511.52Support threshold(%)Runtime(sec.)D2 FP-growthD2 TreeProjectionDat
28、a set T25I20D100K2022-12-22Data Mining:Concepts and Techniques38为什么FP-增长是赢家?n分治:n根据已经得到的频繁模式划分任务和数据库n导致较小的数据库的聚焦的搜索n其它因素n没有候选产生,没有候选测试n压缩数据库:FP-树结构n不重复地扫描整个数据库 n基本操作局部频繁项计数和建立子FP-树,没有模式搜索和匹配2022-12-22Data Mining:Concepts and Techniques39关联方法n挖掘频繁闭项集合和最大模式nCLOSET(DMKD00)n挖掘序列模式 nFreeSpan(KDD00),Prefi
29、xSpan(ICDE01)n频繁模式的基于限制的挖掘nConvertible constraints(KDD00,ICDE01)n计算具有复杂度量的冰山数据方nH-tree and H-cubing algorithm(SIGMOD01)2022-12-22Data Mining:Concepts and Techniques40最大模式n频繁模式 a1,a100 包含(1001)+(1002)+(110000)=2100-1=1.27*1030 频繁子模式!n最大模式:频繁模式,其真超模式都不是频繁的nBCDE,ACD 是最大模式nBCD 不是最大模式TidItems10A,B,C,D,E2
30、0B,C,D,E,30A,C,D,FMin_sup=22022-12-22Data Mining:Concepts and Techniques41MaxMiner:挖掘最大模式n扫描1:找出频繁项nA,B,C,D,En扫描2:找出以下项集的支持度 nAB,AC,AD,AE,ABCDEnBC,BD,BE,BCDEnCD,CE,CDE,DEn由于 BCDE 是最大模式,不必在此后的扫描时检查 BCD,BDE,CDEnR.Bayato.Efficiently mining long patterns from databases.In SIGMOD98TidItems10A,B,C,D,E20B,
31、C,D,E,30A,C,D,F潜在的最大模式 2022-12-22Data Mining:Concepts and Techniques42频繁闭模式nConf(acd)=100%record acd onlyn对于频繁项集 X,如果不存在项y 使得每个包含X的事务也包含y,则称 X 是 频繁闭模式/项集n“acd”是一个频繁闭模式n频繁模式的简明表示n压缩频繁模式和规则的数量nN.Pasquier et al.In ICDT99TIDItems10a,c,d,e,f20a,b,e30c,e,f40a,c,d,f50c,e,fMin_sup=22022-12-22Data Mining:Con
32、cepts and Techniques43挖掘频繁闭模式:CLOSET 方法nFlist:所有频繁项按支持度递增序排列nFlist:d-a-f-e-cn划分搜索空间n包含 d 的模式n含 d 但不含 a 的模式,等.n递归地找出频繁闭模式n每个含 d 的事务也含cfa cfad 是一个频繁闭模式nJ.Pei,J.Han&R.Mao.CLOSET:An Efficient Algorithm for Mining Frequent Closed Itemsets,DMKD00.TIDItems10a,c,d,e,f20a,b,e30c,e,f40a,c,d,f50c,e,fMin_sup=22
33、022-12-22Data Mining:Concepts and Techniques44挖掘频繁闭模式:CHARM 方法n使用竖直数据格式:t(AB)=T1,T12,n基于竖直的交导出频繁闭模式nt(X)=t(Y):X 和 Y 总是同时出现nt(X)t(Y):含 X 的事务总是含 Yn使用 diffset 加快挖掘n只保留不同的 tidsnt(X)=T1,T2,T3,t(Xy)=T1,T3 nDiffset(Xy,X)=T2nM.Zaki.CHARM:An Efficient Algorithm for Closed Association Rule Mining,CS-TR99-10,R
34、ensselaer Polytechnic InstitutenM.Zaki,Fast Vertical Mining Using Diffsets,TR01-1,Department of Computer Science,Rensselaer Polytechnic Institute2022-12-22Data Mining:Concepts and Techniques45关联规则的可视化:Pane Graph2022-12-22Data Mining:Concepts and Techniques46关联规则的可视化:Rule Graph2022-12-22Data Mining:C
35、oncepts and Techniques47第6章：挖掘大型数据库中的关联规则n关联规则挖掘n事务数据库中(单维布尔)关联规则挖掘的可伸缩算法n挖掘各种关联/相关规则 n基于限制的关联挖掘n顺序模式挖掘n频繁模式挖掘的应用/扩展n小结2022-12-22Data Mining:Concepts and Techniques48挖掘各种规则或规律性n多层,量化关联规则,相关性和因果关系,比率规则,序列模式,显露模式,时间关联,局部周期性n关联,聚类,冰山方等.2022-12-22Data Mining:Concepts and Techniques49多层关联规则n项常常形成层次结构n灵活的
36、支持度设定:较低层中的项一般具有较低的支持度.n事务数据库可以基于维和层进行编码n探测共享的多层挖掘一致的支持度Milksupport=10%2%Milk support=6%Skim Milk support=4%层 1min_sup=5%层 2min_sup=5%Level 1min_sup=5%Level 2min_sup=3%递减的支持度2022-12-22Data Mining:Concepts and Techniques50具有灵活的支持度限制的ML/MD 关联n为什么?n现实中项的出现频率差异很大n购物中的钻石,表,笔n一致的支持读可能不是一种好的模型n灵活的模型n通常,层越低
37、,维的组合越多,长模式越长,支持度越小n一般规则应当是特指的,易于理解的n特殊的项或特殊的项群可能被个别地指定,并具有较高的优先权2022-12-22Data Mining:Concepts and Techniques51多维关联规则n单维规则:buys(X,“milk”)buys(X,“bread”)n多维规则:维或谓词 2 n维间关联规则(不含重复谓词)age(X,”19-25”)occupation(X,“student”)buys(X,“coke”)n混合维关联规则(含重复谓词)age(X,”19-25”)buys(X,“popcorn”)buys(X,“coke”)n分类属性n有限
38、个不同值,值之间无序n量化属性n数值的,值之间隐含次序2022-12-22Data Mining:Concepts and Techniques52多层关联:冗余过滤n由于项之间的“祖先”联系,有些规则可能是多余的.n例nmilk wheat bread support=8%,confidence=70%n2%milk wheat bread support=2%,confidence=72%n我们可以说第一个规则是第二个规则的祖先.n一个规则是冗余的,如果根据规则的祖先,其支持度接近于“期望”值.2022-12-22Data Mining:Concepts and Techniques53多
39、层挖掘:逐步深入n一种自顶向下,逐步深入的方法:n 首先挖掘最高层的频繁模式:milk(15%),bread(10%)n 然后挖掘它们下层“较弱的”频繁模式:2%milk(5%),wheat bread(4%)n多层之间的不同的最小支持度阈值导致不同的算法:n如果不同层之间采用相同的min_support则丢弃 t 如果 t的任意祖先是非频繁的.n如果在较低层采用递减的 min_support则只考察其祖先为频繁的项集.2022-12-22Data Mining:Concepts and Techniques54挖掘多维关联的技术n搜索频繁 k-谓词集:n例:age,occupation,bu
40、ys 是一个 3-谓词集.n可以按如何处理 age 对技术分类.n使用量化属性的静态离散化n使用预先定义的概念分层,对量化属性静态地离散化.n量化关联规则n根据数据的分布,将量化属性离散化到“箱”.n基于距离的关联规则1.是一种动态的离散化过程,它考虑数据点之间的距离.2022-12-22Data Mining:Concepts and Techniques55量化属性的静态离散化n使用概念分层,在挖掘之前离散化.n数值值用区间值替换.n在关系数据库中,找出所有的频繁 k-谓词集需要k 或 k+1 次表扫描.n数据方非常适合挖掘.nn-维单元 对应于谓词集合的方体.n从数据方挖掘可以快得多.(
41、income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)2022-12-22Data Mining:Concepts and Techniques56量化关联规则n数值属性动态地离散化n使得挖掘的规则的置信度或紧凑性最大化.n2-D 量化关联规则:Aquan1 Aquan2 Acatn使用2-D栅格,对“相邻的”关联规则聚类形成一般关联规则.n例:age(X,”30-34”)income(X,”24K-48K”)buys(X,”high resolution TV”)2022-12-22Data Minin
42、g:Concepts and Techniques57挖掘基于距离的关联规则n分箱方法不能紧扣区间数据的语义 n基于距离的划分,更有意义的离散化考虑:n区间内点的密度/数量n区间内点的“紧密性”Price($)Equi-width(width$10)Equi-depth(depth 2)Distance-based70,107,207,72011,2022,5020,222221,3051,5350,535031,405141,505351,602022-12-22Data Mining:Concepts and Techniques58兴趣度度量:相关性nplay basketball ea
43、t cereal 40%,66.7%是误导n吃谷类食品的学生所占的百分比为75%,比 66.7%还高.nplay basketball not eat cereal 20%,33.3%更准确,其支持度和置信度都较低n依赖/相关事件的度量:BasketballNot basketballSum(row)Cereal200017503750Not cereal10002501250Sum(col.)300020005000)()()(,BPAPBAPcorrBA2022-12-22Data Mining:Concepts and Techniques59第6章：挖掘大型数据库中的关联规则n关联规则
44、挖掘n事务数据库中(单维布尔)关联规则挖掘的可伸缩算法n挖掘各种关联/相关规则 n基于限制的关联挖掘n顺序模式挖掘n频繁模式挖掘的应用/扩展n小结2022-12-22Data Mining:Concepts and Techniques60基于约束的数据挖掘n自动地找出数据库中的所有模式?不现实!n模式可能太多,并不聚焦!n数据挖掘应当是一个 交互的 过程 n用户使用数据挖掘查询语言(或图形用户界面)指导需要挖掘什么n基于约束的挖掘n用户灵活性:提供挖掘的 约束 n系统优化:考察限制,寻找有效的挖掘基于约束的挖掘2022-12-22Data Mining:Concepts and Techni
45、ques61数据挖掘的约束n知识类型约束:n分类,关联,等.n数据约束 使用类 SQL查询n找出 Vancouver 2000年12月份一起销售的产品对n维/层约束n关于 region,price,brand,customer categoryn规则(或模式)约束n小额销售(价格$200)n兴趣度约束n强规则:min_support 3%,min_confidence 60%2022-12-22Data Mining:Concepts and Techniques62受约束的挖掘 vs.基于约束的搜索n受约束的挖掘 vs.基于约束的搜索/推理n二者都旨在减小搜索空间n找出满足约束的 所有模式
46、vs.AI中基于约束的搜索,找出 某些(或某个)解n约束推进 vs.启发式搜索n如何将二者集成,是一个有趣的研究问题n受约束的挖掘 vs.DBMS的查询处理n数据库查询需要找出所有的n受约束的模式挖掘与查询处理的推进选择的思想类似2022-12-22Data Mining:Concepts and Techniques63受约束的挖掘:挖掘查询优化问题n给定频繁模式挖掘查询,和约束集C,算法应当n可靠的:仅发现满足给定约束C的频繁模式n完全的:发现满足给定约束C的所有频繁模式 n一种朴素的方法n首先找出所有的频繁模式,然后检查它们是否满足约束n更有效的方法:n分析约束的性质n尽可能推进约束 到
47、频繁模式的计算中.2022-12-22Data Mining:Concepts and Techniques64基于约束挖掘的反单调性n反单调性n当项集 S 违反约束时,它的任何超集合也违反约束nsum(S.Price)v 是反单调的nsum(S.Price)v 不是反单调的n例.C:range(S.profit)15是反单调的n项集 ab 违反约束 CnAb的每个超集也违反约束CTIDTransaction10a,b,c,d,f20b,c,d,f,g,h30a,c,d,e,f40c,e,f,gTDB(min_sup=2)ItemProfita40b0c-20d10e-30f30g20h-10
48、2022-12-22Data Mining:Concepts and Techniques65哪些约束是反单调的?约束反单调性v SNoS VnoS Vyesmin(S)vnomin(S)vyesmax(S)vyesmax(S)vnocount(S)vyes count(S)vnosum(S)v(a S,a 0)yessum(S)v(a S,a 0)norange(S)vyesrange(S)vnoavg(S)v,convertiblesupport(S)yessupport(S)no2022-12-22Data Mining:Concepts and Techniques66基于约束挖掘的单
49、调性n单调性n当项集 S 满足约束时,它的任何超集合也满足约束nsum(S.Price)v 是单调的nmin(S.Price)v 是单调的n例.C:range(S.profit)15n项集 ab 满足 Cnab的每个超集合也满足CTIDTransaction10a,b,c,d,f20b,c,d,f,g,h30a,c,d,e,f40c,e,f,gTDB(min_sup=2)ItemProfita40b0c-20d10e-30f30g20h-102022-12-22Data Mining:Concepts and Techniques67哪些约束是单调的?约束单调性v SyesS VyesS Vn
50、omin(S)vyesmin(S)vnomax(S)vnomax(S)vyescount(S)vnocount(S)vyessum(S)v(a S,a 0)nosum(S)v(a S,a 0)yesrange(S)vnorange(S)vyesavg(S)v,convertiblesupport(S)nosupport(S)yes2022-12-22Data Mining:Concepts and Techniques68简洁性n简洁性:n给定满足约束C 的项的集合 A1,则满足C 的任意集合S 都基于 A1,即,S 包含一个属于A1 的子集 n思想:不查看事务数据库,项集S 是否满足约束C可
