数据挖掘-CHAPTER5-挖掘大型数据库中的关联规则-内容多

1第5章：挖掘大型数据库中的关联规则关联规则挖掘事务数据库中(单维布尔)关联规则挖掘的可伸缩算法挖掘各种关联/相关规则基于限制的关联挖掘-顺序模式挖掘小结2关联规则关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。典型的关联规则发现问题是对超市中的货篮数据（MarketBasket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。

3什么是关联规则挖掘关联规则挖掘首先被Agrawal,ImielinskiandSwami在1993年的SIGMOD会议上提出在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构频繁模式:数据库中频繁出现的项集目的:发现数据中的规律超市数据中的什么产品会一起购买？—啤酒和尿布在买了一台PC之后下一步会购买?哪种DNA对这种药物敏感?我们如何自动对Web文档进行分类?4频繁模式挖掘的重要性许多重要数据挖掘任务的基础关联、相关性、因果性序列模式、空间模式、时间模式、多维关联分类、聚类分析更加广泛的用处购物篮分析、交叉销售、直销点击流分析、DNA序列分析等等5关联规则基本模型IBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型，并给出求解算法AIS。随后又出现了SETM和Apriori等算法。其中，Apriori是关联规则模型中的经典算法。给定一组事务产生所有的关联规则满足最小支持度和最小可信度6关联规则基本模型设I={i1,…,im}为所有项目的集合，D为事务数据库，事务T是一个项目子集（T

I）。每一个事务具有唯一的事务标识TID。设A是一个由项目构成的集合，称为项集。事务T包含项集A，当且仅当A

T。如果项集A中包含k个项目，则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。

7关联规则基本模型关联规则是形如X

Y的逻辑蕴含式，其中X

I，Y

I，且X

Y=

。如果事务数据库D中有s%的事务包含X

Y，则称关联规则X

Y的支持度为s%实际上，支持度是一个概率值。是一个相对计数。support(X

Y)=P(X

Y)项集的支持度计数(频率)support_count包含项集的事务数若项集X的支持度记为support(X)，规则的信任度为support(X

Y)／support(X)。是一个条件概率P(Y|X)。confidence(X

Y)=P(Y|X)=support_count(X

Y)／support_count(X)8频繁模式和关联规则ItemsetX={x1,…,xk}找出满足最小支持度和置信度的所规则XY

支持度,s,事务包含XY的概率

置信度,c,

事务含X也包含Y的条件概率.顾客购买尿布顾客购买二者顾客购买啤酒Transaction-idItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F令supmin=50%,confmin=50%Freq.Pat.:{A:3,B:3,D:4,E:3,AD:3}关联规则Associationrules:A

D(60%,100%)D

A(60%,75%)9挖掘关联规则—一个例子规则A

C:支持度=support({A}

{C})=50%置信度=support({A}{C})/support({A})=66.6%最小支持度50%最小置信度50%Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FFrequentpatternSupport{A}75%{B}50%{C}50%{A,C}50%10闭频繁项集and极大频繁项集一个长模式包含子模式的数目,e.g.,{a1,…,a100}contains(1001)+(1002)+…+(110000)=2100–1=1.27*1030sub-patterns!解:Mineclosedpatternsandmax-patternsinstead一个频繁项集X

是闭的，如果X是频繁的，且不存在真超项集nosuper-patternYכX,有相同的支持度计数

(proposedbyPasquier,etal.@ICDT’99)项集X是极大频繁项集

ifXisfrequentandthereexistsnofrequentsuper-patternYכX(proposedbyBayardo@SIGMOD’98)两者有不同，极大频繁项集定义中对真超集要松一些。11闭频繁项集and极大频繁项集Exercise.DB={<a1,…,a100>,<a1,…,a50>}Min_sup=1.Whatisthesetofcloseditemset?<a1,…,a100>:1<a1,…,a50>:2Whatisthesetofmax-pattern?<a1,…,a100>:1Whatisthesetofallpatterns?!!12关联规则基本模型关联规则就是支持度和信任度分别满足用户给定阈值的规则。

发现关联规则需要经历如下两个步骤：找出所有频繁项集。由频繁项集生成满足最小信任度阈值的规则。13第5章：挖掘关联规则关联规则挖掘事务数据库中(单维布尔)关联规则挖掘的可伸缩算法挖掘各种关联/相关规则基于限制的关联挖掘-顺序模式挖掘小结14Apriori算法的步骤Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。Apriori算法将发现关联规则的过程分为两个步骤：通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；利用频繁项集构造出满足用户最小信任度的规则。挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。15频繁项集为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck，频繁k项集的集合记为Lk，m个项目构成的k项集的集合为，则三者之间满足关系Lk

Ck

。构成潜在频繁项集所遵循的原则是“频繁项集的子集必为频繁项集”。16关联规则的性质

性质1：频繁项集的子集必为频繁项集。

性质2：非频繁项集的超集一定是非频繁的。Apriori算法运用性质1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。

17Apriori:一种候选产生-测试方法频繁项集的任何子集必须是频繁的如果{beer,diaper,nuts}是频繁的,{beer,diaper}也是每个包含{beer,diaper,nuts}的事务也包含{beer,diaper}Apriori剪枝原则:如果一个项集不是频繁的,将不产生/测试它的超集!方法:由长度为k的频繁项集产生长度为(k+1)的候选项集,并且根据DB测试这些候选性能研究表明了它的有效性和可伸缩性18Apriori算法—一个例子数据库TDB第1次扫描C1L1L2C2C2第2次扫描C3L3第3次扫描TidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}219Apriori算法(1)L1={频繁1项集};(2)for(k=2;Lk-1

;k++)dobegin(3)Ck=apriori_gen(Lk-1);//新的潜在频繁项集(4)foralltransactions

t

Ddobegin(5)Ct=subset(Ck,t);//找出t中包含的潜在的频繁项(6)forallcandidatesc

Ctdo(7)c.count++;(8)end;(9)Lk={c

Ck|c.count

minsup}(10)end;(11)Answer=20Apriori的重要细节如何产生候选?步骤1:Lk的自连接步骤2:剪枝候选产生的例子L3={abc,abd,acd,ace,bcd}自连接:L3*L3Abcd：由abc

和abdAcde：由acd

和ace剪枝:acde

被删除,因为ade

不在L3C4={abcd}21如何产生候选?假定Lk-1

中的项集已排序(按字典序排序)步骤1:Lk-1自连接insertintoCkselectp.item1,p.item2,…,p.itemk-1,q.itemk-1fromLk-1p,Lk-1qwherep.item1=q.item1,…,p.itemk-2=q.itemk-2,p.itemk-1<q.itemk-1Step2:剪枝forallitemsetscinCk

doforall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk22例子-支持计数=223例子24由频繁项集产生关联规则根据公式产生关联规则对于每个频繁项集l，产生所有的非空子集对于l的每个非空子集s，如果 则输出规则”s(l-s)”25频繁模式挖掘的挑战挑战事务数据库的多遍扫描数量巨大的候选候选支持度计数繁重的工作量改进Apriori:基本思想减少事务数据库的扫描遍数压缩候选数量便于候选计数26提高Apriori算法的方法Hash-baseditemsetcounting（散列项集计数）Transactionreduction（事务压缩）Partitioning（划分）Sampling（采样）27划分:只扫描数据库两次项集在DB中是频繁的,它必须至少在DB的一个划分中是频繁的扫描1:划分数据库,并找出局部频繁模式localfrequentitemset扫描2:求出全局频繁模式A.Savasere,E.Omiecinski,andS.Navathe.Anefficientalgorithmforminingassociationinlargedatabases.InVLDB’95DB1DB2DBk+=DB++sup1(i)<σDB1sup2(i)<σDB2supk(i)<σDBksup(i)<σDB28抽样-频繁模式选取原数据库的一个样本,使用Apriori算法在样本中挖掘频繁模式扫描一次数据库,验证在样本中发现的频繁模式.再次扫描数据库,找出遗漏的频繁模式牺牲一些精度换取有效性。H.Toivonen.Samplinglargedatabasesforassociationrules.InVLDB’9629DHP:压缩候选的数量散列项集到对应的桶中，一个其hash桶的计数小于阈值的k-itemset不可能是频繁的J.Park,M.Chen,andP.Yu.Aneffectivehash-basedalgorithmforminingassociationrules.InSIGMOD’9530DIC(Dynamicitemsetcounting):减少扫描次数ABCDABCABDACDBCDABACBCADBDCDABCD{}Itemsetlattice一旦确定A和D是频繁的,立即开始AD的计数一旦确定BCD的两个长度为2的子集是频繁的,立即开始BCD的计数事务1-itemsets2-itemsets…Apriori1-itemsets2-items3-itemsDICS.BrinR.Motwani,J.Ullman,andS.Tsur.Dynamicitemsetcountingandimplicationrulesformarketbasketdata.InSIGMOD’9731使用垂直数据格式挖掘频繁项集VerticalDataFormat使用tid-list,包含item的事务的标识的集合;M.Zakietal.Newalgorithmsforfastdiscoveryofassociationrules.InKDD’97扫描一次数据集将水平格式数据转化为垂直格式通过频繁k项集的tid-list的交集，计算对应(k+1)项集的tid-list32频繁模式挖掘的瓶颈多遍数据库扫描是昂贵的挖掘长模式需要很多遍扫描,并产生大量候选挖掘频繁模式i1i2…i100扫描次数:100候选个数:(1001)+(1002)+…+(110000)=2100-1=1.27*1030!瓶颈:候选产生-测试能够避免候选产生吗?33挖掘频繁模式而不产生候选使用局部频繁的项,由短模式增长产生长模式“abc”是频繁模式得到包含“abc”的所有事务:DB|abc“d”是DB|abc中的局部频繁项

abcd是频繁模式34由事务数据库构造FP-树{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1HeaderTableItemfrequencyheadf 4c 4a 3b 3m 3p 3min_support=3TID Itemsbought (ordered)frequentitems100 {f,a,c,d,g,i,m,p}

{f,c,a,m,p}200 {a,b,c,f,l,m,o}

{f,c,a,b,m}300

{b,f,h,j,o,w}

{f,b}400

{b,c,k,s,p}

{c,b,p}500

{a,f,c,e,l,p,m,n}

{f,c,a,m,p}扫描DB一次,找出频繁1-itemset(单个项的模式)按频率的降序将频繁项排序,得到f-list再次扫描DB,构造FP-树F-list=f-c-a-b-m-p35划分模式和数据库可以按照f-list将频繁模式划分成子集F-list=f-c-a-b-m-p包含p的模式包含m但不包含p的模式…包含c但不包含a,b,m,p模式f完全性和非冗余性36从p-条件数据库找出含p的模式从FP-树的频繁项头表开始沿着频繁项p的链搜索FP-树收集项p的所有变换的前缀路径形成p的模式基条件模式基item cond.patternbasec f:3a fc:3b fca:1,f:1,c:1m fca:2,fcab:1p fcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf 4c 4a 3b 3m 3p 337EmptyEmptyf{(f:3)}|c{(f:3)}c{(f:3,c:3)}|a{(fc:3)}aEmpty{(fca:1),(f:1),(c:1)}b{(f:3,c:3,a:3)}|m{(fca:2),(fcab:1)}m{(c:3)}|p{(fcam:2),(cb:1)}p条件FP-tree条件模式库项通过建立条件模式库得到频繁集38从条件模式基到条件FP-树对于每个条件模式基累计条件模式基中每个项的计数构造模式基中频繁项的FP-树m-条件模式基:fca:2,fcab:1{}f:3c:3a:3m-条件FP-树m的所有频繁模式m,fm,cm,am,fcm,fam,cam,fcam

{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf 4c 4a 3b 3m 3p 339递归:

挖掘每个条件FP-树{}f:3c:3a:3m-条件FP-树“am”的条件模式基:(fc:3){}f:3c:3am-条件FP-树“cm”的条件模式基:(f:3){}f:3cm-条件FP-树“cam”的条件模式基:(f:3){}f:3cam-条件FP-树40特殊情况:FP-树中的单个前缀路径假定(条件)FP-树T具有单个共享的前缀路径P挖掘可以分解成两步将单个前缀路径归约成一个结点连接两部分的挖掘结果

a2:n2a3:n3a1:n1{}b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1{}r1=41使用FP-树挖掘频繁模式基本思想:频繁模式增长通过模式和数据库划分递归地增长频繁模式方法(1)对于每个频繁项,构造它的条件模式基(2)然后构造它的条件FP-树(3)在新构造的条件FP-树上重复这一过程直到结果条件FP-树为空,或者它只包含一条路径—单个路径将产生其子路径的所有组合,每个子路径是一个频繁模式42FP-树结构的优点完全性保留频繁模式挖掘的完整信息不截断任何事务的长模式压缩性压缩无关信息—非频繁的项被删除项按频率的降序排列:越是频繁出现,越可能被共享绝对不比原来的数据库大(不计结点链和计数字段)43FP-增长的规模化FP-树不能放在内存,怎么办?—数据库投影数据库投影首先将数据库划分成一组投影数据库然后对每个投影数据库构造并挖掘FP-树44FP-增长vs.Apriori:随支持度增长的可伸缩性DatasetT25I20D10K45FP-增长vs.树-投影:随支持度增长的可伸缩性DatasetT25I20D100K46为什么FP-增长是赢家?分治:根据已经得到的频繁模式划分任务和数据库导致较小的数据库的聚焦的搜索其它因素没有候选产生,没有候选测试压缩数据库:FP-树结构不重复地扫描整个数据库基本操作—局部频繁项计数和建立子FP-树,没有模式搜索和匹配47有关的其他方法挖掘频繁闭项集合和最大模式CLOSET(DMKD’00)挖掘序列模式FreeSpan(KDD’00),PrefixSpan(ICDE’01)频繁模式的基于限制的挖掘Convertibleconstraints(KDD’00,ICDE’01)计算具有复杂度量的冰山数据方H-treeandH-cubingalgorithm(SIGMOD’01)48最大模式频繁模式{a1,…,a100}包含(1001)+(1002)+…+(110000)=2100-1=1.27*1030频繁子模式!最大模式:频繁模式,其真超模式都不是频繁的BCDE,ACD是最大模式BCD不是最大模式TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,FMin_sup=249MaxMiner:挖掘最大模式扫描1:找出频繁项A,B,C,D,E扫描2:找出以下项集的支持度AB,AC,AD,AE,ABCDEBC,BD,BE,BCDECD,CE,CDE,DE由于BCDE

是最大模式,

不必在此后的扫描时检查BCD,BDE,CDER.Bayato.Efficientlymininglongpatternsfromdatabases.InSIGMOD’98TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F潜在的最大模式50关联规则的可视化:PaneGraph51第5章：挖掘大型数据库中的关联规则关联规则挖掘事务数据库中(单维布尔)关联规则挖掘的可伸缩算法挖掘各种关联/相关规则基于限制的关联挖掘顺序模式挖掘小结52挖掘各种规则或规律性多层关联规则,多维关联规则，量化关联规则,相关性和因果关系,比率规则,序列模式,显露模式,时间关联,局部周期性53多层关联规则项常常形成层次结构-概念分层多个抽象层次上挖据得到的关联规则-多层关联规则灵活的支持度设定:较低层中的项一般具有较低的支持度.一致的支持度Computer[support=10%]LaptopComputer[support=6%]DesktopComputer[support=4%]层1min_sup=5%层2min_sup=5%Level1min_sup=5%Level2min_sup=3%递减的支持度54多层关联:冗余过滤由于项之间的“祖先”联系,有些规则可能是多余的.例LaptopcomputerHPprinter[support=8%,confidence=70%]IBMlaptopcomputerHPprinter[support=2%,confidence=72%]其中IBMlaptopcomputer占laptopcomputer的1/4我们可以说第一个规则是第二个规则的祖先.如果根据规则的祖先,其支持度和置信度都接近于“期望”值，那么，一个规则是冗余的.55多层挖掘:逐步深入一种自顶向下,逐步深入的方法:

首先挖掘最高层的频繁模式:laptopcomputer(15%),printer(10%)

然后挖掘它们下层“较弱的”频繁模式:IBMlaptopcomputer(5%),HPprinter(4%)多层之间的不同的最小支持度阈值导致不同的算法:如果不同层之间采用相同的min_support

则丢弃t

如果t’的任意祖先是非频繁的.如果在较低层采用递减的min_support

则只考察其祖先为频繁的项集.56多维关联规则单维规则:包括单个谓词（可以多次出现）或单个维buys(X,“laptopcomputer”)buys(X,“printer”)多维规则:维或谓词

2

维间关联规则(不含重复谓词)age(X,”19-25”)

occupation(X,“student”)buys(X,“coke”)混合维关联规则(含重复谓词)age(X,”19-25”)

buys(X,“popcorn”)

buys(X,“coke”)数据的属性可分为两类分类属性有限个不同值,值之间无序量化属性数值的,值之间隐含次序57挖掘多维关联规则的技术搜索频繁k-谓词集:包含k个合取谓词的集合例:{age,occupation,buys}

是一个3-谓词集.可以按如何处理age

对技术分类.使用量化属性的静态离散化使用预先定义的概念分层,对量化属性静态地离散化.量化关联规则根据数据的分布,将量化属性离散化到“箱”.基于距离的关联规则是一种动态的离散化过程,它考虑数据点之间的距离.58量化属性的静态离散化(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)使用概念分层,在挖掘之前离散化.数值用区间值替换.在关系数据库中,找出所有的频繁k-谓词集需要k

或k+1次表扫描.数据立方体非常适合挖掘.n-维方体 对应于谓词集合的方体.从数据立方体挖掘可以快得多.59量化关联规则数值属性动态地离散化使挖出的规则的置信度或紧凑性最大化.2-维量化关联规则:Aquan1

Aquan2Acat（分类属性）ARCS方法：使用2-D栅格,1)对属性进行（等宽）分箱2)找频繁谓词集3)规则聚类：对“相邻的”关联规则聚类形成一般关联规则.例:

age(X,”34-35”)

income(X,”31K-50K”)buys(X,”highresolutionTV”)60挖掘基于距离的关联规则分箱方法不能紧扣区间数据的语义基于距离的划分,更有意义的离散化考虑:区间内点的密度/数量区间内点的“紧密性”61具有灵活的支持度限制的

多层ML/MD多维关联规则为什么?现实中项的出现频率差异很大购物中的钻石,表,笔一致的支持度可能不是一种好的模型灵活的模型通常,层越低,维的组合越多,长模式越长,支持度越小一般规则应当是特指的,易于理解的特殊的项或特殊的项群可能被个别地指定,并具有较高的优先权62兴趣度度量:相关性(Lift)playbasketball

eatcereal[40%,66.7%]是误导吃谷类食品的学生所占的百分比为75%,比66.7%还高.playbasketball

noteatcereal[20%,33.3%]更准确,其支持度和置信度都较低依赖/相关事件的度量:BasketballNotbasketballSum(row)Cereal谷类200017503750Notcereal10002501250Sum(col.)30002000500063WhichMeasuresShouldBeUsed?提升度和

2

不是好的相关度量，对于大的交易数据库all-conforcoherencecouldbegoodmeasures(Omiecinski@TKDE’03)Over20interestingnessmeasureshavebeenproposed(seeTan,Kumar,Sritastava@KDD’02)Whicharegoodones?64第6章：挖掘大型数据库中的关联规则关联规则挖掘事务数据库中(单维布尔)关联规则挖掘的可伸缩算法挖掘各种关联/相关规则基于限制的关联挖掘顺序模式挖掘频繁模式挖掘的应用/扩展小结65基于约束的数据挖掘自动地找出数据库中的所有模式?—不现实!模式可能太多,并不聚焦!数据挖掘应当是一个交互的过程用户使用数据挖掘查询语言(或图形用户界面)指导需要挖掘什么基于约束的挖掘用户灵活性:提供挖掘的约束

系统优化:考察限制,寻找有效的挖掘—基于约束的挖掘66数据挖掘的约束知识类型约束:分类,关联,等.数据约束

（指定任务相关的数据集）—使用类SQL查询找出Vancouver2000年12月份一起销售的产品对维/层约束-指定数据属性/概念分层结构的层次关于region,price,brand,customercategory兴趣度约束强规则:min_support

3%,min_confidence

60%规则(或模式)约束-指定规则形式小额销售(价格<$10)触发大额销售(sum>$200)67元规则制导挖掘Meta-RuleGuidedMining元规则是带有部分约束谓词和常量的规则P1(X,Y)^P2(X,W)=>buys(X,“iPad”)一个导致的规则age(X,“15-25”)^profession(X,“student”)=>buys(X,“iPad”)通常情况,元规则如下形式的规则模板

P1^P2^…^Pl=>Q1^Q2^…^Qr

挖掘过程找出所有的频繁(l+r)谓词集(基于最小支持度阈值)必须保留l子集的支持度/计数（计算规则的置信度）（挖掘过程中）尽可能推进约束(见约束推进技术)尽可能地应用置信度,相关和其他度量68规则约束-剪枝搜索空间规则约束的分类反单调性Anti-monotonic单调性Monotonic简洁性Succinct:可转变的Convertible:不可转变的69规则约束-反单调性反单调性当项集S违反规则约束时,它的任何超集合也违反约束sum(S.Price)

v

是反单调的sum(S.Price)

v

不是反单调的例.C:range(S.profit)

15是反单调的项集ab违反约束Cab的每个超集也违反约束CTIDTransaction10a,b,c,d,f20b,c,d,f,g,h30a,c,d,e,f40c,e,f,gTDB(min_sup=2)ItemProfita40b0c-20d10e-30f30g20h-1070规则约束-单调性单调性当项集S满足约束时,它的任何超集合也满足约束sum(S.Price)

v

是单调的min(S.Price)

v是单调的例.C:range(S.profit)

70项集af满足Caf的每个超集合也满足CTIDTransaction10a,b,c,d,f20b,c,d,f,g,h30a,c,d,e,f40c,e,f,gTDB(min_sup=2)ItemProfita40b0c-20d10e-30f30g20h-1071简洁性简洁性:给定满足约束C的项的集合A1,,则满足C的任意集合S都基于A1,即,S

包含一个属于A1的子集思想:不查看事务数据库,项集S是否满足约束C可以根据选取的项确定

min(S.Price)

v

是简洁的sum(S.Price)v

不是简洁的优化:如果C

是简洁的,C

是预计数可推进的(pre-counting

pushable)72Apriori算法—一个例子DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanD73朴素算法:Apriori+约束DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanD约束:Sum{S.price<5}74受约束的Apriori算法:推进反单调约束DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanD约束:Sum{S.price<5}75转换“强硬的”约束通过将项适当地排序,将强硬的约束转换成反单调的或单调的例C:avg(S.profit)

25将项按profit值的递减序排序<a,f,g,d,b,h,c,e>如果项集afg

违反Cafgd,afg*也违反C约束C成为反单调的!TIDTransaction10a,b,c,d,f20b,c,d,f,g,h30a,c,d,e,f40c,e,f,gTDB(min_sup=2)ItemProfita40b0c-20d10e-30f30g20h-1076可转变的约束设R项集的项以特定次序安排，可转变反单调如果项集S

违反约束C,每个关于R以S为前缀的项集也违反约束C例.avg(S)

v

，如果项值递减序排列可转变单调如果项集S

满足约束C,每个关于R以S为前缀的项集也满足约束C.例.avg(S)

v，如果项值递增序排列77强可转变约束avg(X)

25关于项值的递减序R:<a,f,g,

d,b,h,c,e>是可转变反单调的如果项集af违反约束C,每个以af为前缀的项集也违反C,如afdavg(X)

25关于项值的递增序R-1:<e,c,h,b,d,g,f,a>是可转变单调的如果项集d

满足约束C,df

和dfa

也满足,它们具有前缀d这样,avg(X)

25是强可转变的ItemProfita40b0c-20d10e-30f30g20h-1078约束的性质汇总约束反单调单调简洁v

SnoyesyesSVnoyesyesSVyesnoyesmin(S)vnoyesyesmin(S)vyesnoyesmax(S)vyesnoyesmax(S)vnoyesyescount(S)vyesnoweaklycount(S)vnoyesweaklysum(S)

v(a

S,a

0)yesnonosum(S)

v(a

S,a

0)noyesnorange(S)

vyesnonorange(S)

vnoyesnoavg(S)v,{,,}convertibleconvertiblenosupport(S)

yesnonosupport(S)

noyesno79约束的分类可转变反单调可转变单调强可转变不可转变的简洁反单调单调80Apriori能够处理可转变的约束吗?可转变的,但既不是单调,反单调,也不是简洁的约束不能推进到Apriori挖掘算法的挖掘过程中在逐级的框架下,不能做直接基于该约束的剪枝项集df

违反约束C:avg(X)>=25由于adf

满足C,Apriori需要df

来组装adf,因此不能将df

剪去但是,在模式增长框架下该约束可以推进到挖掘过程中!ItemValuea40b0c-20d10e-30f30g20h-1081具有可转变约束的挖掘C:avg(X)>=25,min_sup=2以值的递减序R:<a,f,g,d,b,h,c,e>列出事务中的每一个项关于R,C是可转变反单调的扫描TDB一次删除非频繁项项h

被删除项a和f是好的,…基于投影的挖掘利用项投影的适当次序许多强硬的约束可以转变成(反)单调的TIDTransaction10a,f,d,b,c20f,g,d,b,c30

a,f,d,c,e40

f,g,h,c,eTDB(min_sup=2)temProfita40f30g20d10b0h-10c-20e-3082讨论—处理多个约束不同的约束需要不同的,甚至相互冲突的项序如果存在序R,

使得约束C1

和C2

关于R是可转变的,则两个可转变的约束之间不存在冲突如果项序存在冲突试图先满足一个约束然后使用另一约束的序,在相应的投影数据库中挖掘频繁项集83第5章：挖掘大型数据库中的关联规则关联规则挖掘事务数据库中(单维布尔)关联规则挖掘的可伸缩算法挖掘各种关联/相关规则基于限制的关联挖掘顺序模式挖掘小结84序列数据库和序列模式挖掘事务数据库,时间序列数据库vs.序列数据库频繁模式vs.(频繁)序列模式序列模式挖掘的应用顾客购物序列:在3个月内,先买计算机,然后买CD-ROM,再后买数字照相机.医疗处治,自然灾害(例如,地震),科学和工程进度,股票和市场等.电话呼叫模式,Web日志点击流DNA序列和基因结构85什么是序列模式挖掘?给定一个序列的集合,找出所有的频繁子序列一个序列数据库

一个序列:<(ef)(ab)(df)cb>一个元素可能包含一个项集.在一个元素中的项是无序的,我们可以用字典序列出它们.

<a(bc)dc>是<a(abc)(ac)d(cf)>的子序列给定支持度阈值min_sup=2,<(ab)c>是一个序列模式SIDsequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>86序列模式挖掘的挑战大量的可能的序列模式隐藏在数据库中挖掘算法应当可能的话,找出满足最小支持度阈值的模式的完全集高度有效的,可伸缩的,仅涉及不多次数的数据库扫描可以与各种用户指定的约束结合87序列模式挖掘研究概念引进和最初的类Apriori算法R.Agrawal&R.Srikant.“Miningsequentialpatterns,”ICDE’95GSP—一种基于Apriori的,有影响的算法(IBMAlmaden开发)R.Srikant&R.Agrawal.“Miningsequentialpatterns:Generalizationsandperformanceimprovements,”EDBT’96由序列模式到episodes(类Apriori+约束)H.Mannila,H.Toivonen&A.I.Verkamo.“Discoveryoffrequentepisodesineventsequences,”DataMiningandKnowledgeDiscovery,1997挖掘具有约束的序列模式M.N.Garofalakis,R.Rastogi,K.Shim:SPIRIT:SequentialPatternMiningwithRegularExpressionConstraints.VLDB199988序列模式的基本性质:Apriori基本性质:Apriori(Agrawal&Sirkant’94)如果序列S不是频繁的则S的任何超序列都不是频繁的例,<hb>是非频繁的

<hab>和<(ah)b>也是非频繁的<a(bd)bcb(ade)>50<(be)(ce)d>40<(ah)(bf)abf>30<(bf)(ce)b(fg)>20<(bd)cb(ac)>10SequenceSeq.ID给定支持度阈值

min_sup=289GSP—一种拓广的序列模式挖掘算法GSP(GeneralizedSequentialPattern)挖掘算法Agrawal和Srikant提出,EDBT’96方法概述初始,数据库中的每个项都是长度为1的候选foreachlevel(即,长度为k的序列)do扫描数据库对每个候选序列收集支持度计数使用Apriori,由长度为k的频繁序列产生长度为(k+1)的候选序列repeatuntil找不到频繁序列或候选主要优点:根据Apriori对后选剪枝90找长度为1的序列模式使用一个例子考查GSP初始候选:所有单元素序列<a>,<b>,<c>,<d>,<e>,<f>,<g>,<h>扫描数据库一次,对候选进行支持度计数<a(bd)bcb(ade)>50<(be)(ce)d>40<(ah)(bf)abf>30<(bf)(ce)b(fg)>20<(bd)cb(ac)>10SequenceSeq.IDmin_sup=2CandSup<a>3<b>5<c>4<d>3<e>3<f>2<g>1<h>191产生长度为2的候选<a><b><c><d><e><f><a><aa><ab><ac><ad><ae><af><b><ba><bb><bc><bd><be><bf><c><ca><cb><cc><cd><ce><cf><d><da><db><dc><dd><de><df><e><ea><eb><ec><ed><ee><ef><f><fa><fb><fc><fd><fe><ff><a><b><c><d><e><f><a><(ab)><(ac)><(ad)><(ae)><(af)><b><(bc)><(bd)><(be)><(bf)><c><(cd)><(ce)><(cf)><d><(de)><(df)><e><(ef)><f>51个长度为2的候选不使用Apriori性质,8*8+8*7/2=92个候选Apriori剪裁掉44.57%的候选92找出长度为2的序列模式再扫描数据库一次,对每个长度为2的候选收集支持度计数有19长度为2的候选,满足最小支持度阈值它们是长度为2的序列模式93产生长度为3的候选并找出长度为3的模式产生长度为3的候选长度为2的序列模式自连接根据Apriori性质<ab>,<aa>和<ba>都是长度为2的序列模式

<aba>是一个长度为3的候选<(bd)>,<bb>和<db>都是长度为2的序列模式

<(bd)b>是一个长度为3的候选产生46个候选找出长度为3的序列模式再次扫描数据库,收集候选的支持度计数46个候选中有19个满足支持度计数94GSP挖掘过程<a><b><c><d><e><f><g><h><aa><ab>…<af><ba><bb>…<ff><(ab)>…<(ef)><abb><aab><aba><baa>

<bab>…<abba><(bd)bc>…<(bd)cba>第1次扫描:8候选.6个长度为1的序列模式第2次扫描:51候选.19个长度为2的序列模式.10候选不在DB第3次扫描:46个候选.19长度为3的序列模式.20个候选不在DB第4次扫描:8个候选.6个长度为4的序列模式.第5次扫描:1个候选.1长度为5的序列模式候选不满足支持度阈值候选不在DB中<a(bd)bcb(ade)>50<(be)(ce)d>40<(ah)(bf)abf>30<(bf)(ce)b(fg)>20<(bd)cb(ac)>10SequenceSeq.IDmin_sup=2

95GSP算法取形如<x>的模式作为长度为1的候选扫描数据库1次,找出F1,长度为1的序列模式的集合令k=1; whileFkisnotemptydo由Fk形成Ck+1,长度为(k+1)的候选的集合;如果Ck+1

非空,扫描一次数据库,找出Fk+1,长度为(k+1)序列模式的集合令k=k+1;96GSP的瓶颈可能产生的候选的集合可能很大1,000长度为1的频繁序列可以产生

长度为2的候选!挖掘中多次扫描数据库实际挑战:挖掘长序列模式指数个数短候选一个长度为100的序列模式需要1030个候选序列!97FreeSpan:频繁模式投影的序列模式挖掘FreeSpan:FrequentPattern-ProjectedSequentialPatternMining一种分治的方法基于当前的频繁模式集,递归地将序列数据库投影到一组较小的数据库挖掘每个较小的数据库,发现它们的模式J.HanJ.Pei,B.Mortazavi-Asi,Q.Chen,U.Dayal,M.C.Hsu,FreeSpan:Frequentpattern-projectedsequentialpatternmining.InKDD’00.f_list:b:5,c:4,a:3,d:3,e:3,f:2所有的序列模式被划分成6个子集合:包含项f

的序列模式包含e

不含f的序列模式包含d

但不含e

和f

包含a

但不含d,e和

f包含c

但不含a,d,e

和f只包含项bSequenceDatabaseSDB<(bd)cb(ac)><(bf)(ce)b(fg)><(ah)(bf)abf><(be)(ce)d><a(bd)bcb(ade)>98由FreeSpan到PrefixSpan:为什么?Freespan:基于投影:不需要产生候选序列但是,投影可能在序列的任意点进行,投影后的序列缩短不多PrefixSpan基于投影但仅基于前缀的投影:较少的投影,并且序列收缩较快99前缀和后缀(投影)<a>,<aa>,<a(ab)>和<a(abc)>是序列<a(abc)(ac)d(cf)>的前缀给定序列<a(abc)(ac)d(cf)>前缀后缀(基于前缀的投影)<a><(abc)(ac)d(cf)><aa><(_bc)(ac)d(cf)><ab><(_c)(ac)d(cf)>100通过前缀投影挖掘序列模式步骤1:找出长度为1的序列模式<a>,<b>,<c>,<d>,<e>,<f>步骤2:划分搜索空间.序列模式的完全集可以划分成6个子集合:具有前缀<a>的模式;具有前缀<b>的模式;…具有前缀<f>的模式SID序列10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>101找出具有前缀<a>的序列模式只需要考虑关于<a>的投影<a>-投影数据库:<(abc)(ac)d(cf)>,<(_d)c(bc)(ae)>,<(_b)(df)cb>,<(_f)cbc>找出所有长度为2的序列模式.具有前缀<a>:<aa>,<ab>,<(ab)>,<ac>,<ad>,<af>进一步划分成6个子集合具有前缀<aa>;…具有前缀<af>SID序列10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>102PrefixSpan的完全性SID序列10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>SDB长度为1的序列模式<a>,<b>,<c>,<d>,<e>,<f><a>-投影数据库<(abc)(ac)d(cf)><(_d)c(bc)(ae)><(_b)(df)cb><(_f)cbc>长度为2的序列模式<aa>,<ab>,<(ab)>,<ac>,<ad>,<af>具有前缀<a>具有前缀<aa><aa>-proj.db…<af>-proj.db具有前缀<af><b>-projecteddatabase…具有前缀<b>具有前缀<c>,…,<f>……103PrefixSpan的有效性不需要产生候选序列投影数据库不断收缩PrefixSpan的主要开销:构造投影数据库可以用两级(bi-level)投影改进104PrefixSpan的优化技术PrefixSpan的优化技术单级vs.两级投影具有3路检验的两级投影可以压缩投影数据库的数量和大小物理投影vs.伪投影当投影数据库可以放在内存时,伪投影可能降低投影的效果并发投影vs.划分投影划分投影可以避免磁盘空间爆炸通过两级投影扩展基于长度为2的序列模式划分搜索空间只形成投影数据库,并在两级投影数据库上进行递归挖掘105使用S-矩阵逐对检查SID序列10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>SDB长度为1的序列模式:<a>,<b>,<c>,<d>,<e>,<f>a2b(4,2,2)1c(4,2,

1)(3,3,2)3d(2,1,1)(2,2,0)(1,3,0)0e(1,2,1)(1,2,0)(1,2,0)(1,1,0)0f(2,1,1)(2,2,0)(1,2,1)(1,1,1)(2,0,1)1abcdefS-矩阵<aa>出现2次<ac>出现4次<ca>出现2次<(ac)>出现1次所有长度为2的序列模式都在S-矩阵中发现106挖掘<ab>-投影数据库SID序列10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>SDB长度为1的序列模式:<a>,<b>,<c>,<d>,<e>,<f>a2b(4,2,2)1c(4,2,1)(3,3,2)3d(2,1,1)(2,2,0)(1,3,0)0e(1,2,1)(1,2,0)(1,2,0)(1,1,0)0f(2,1,1)(2,2,0)(1,2,1)(1,1,1)(2,0,1)1abcdefS-矩阵<ab>-投影数据库<(_c)(ac(cf)><(_c)a><c>局部长度为1的序列模式:<a>,<c>,<(_c)>a0c(1,0,1)1(_c)(

,2,)(,1,)

ac(_c)S-矩阵不希望形成(_ac),因此不必对它计数.导致模式<a(bc)a>107两级投影的好处每次可以发现更多的模式较少的投影在上例中,有53个模式.53个逐级投影22个两级投影108三路Apriori检查a2b(4,2,2)1c(4,2,1)(3,3,2)3d(2,1,1)(2,2,0)(1,3,0)0e(1,2,1)(1,2,0)(1,2,0)(1,1,0)0f(2,1,1)(2,2,0)(1,2,1)(1,1,1)(2,0,1)1abcdeF<acd>不可能是模式!从<ac>-投影数据库排除d使用Apriori启发式方法在投影数据库中剪去项类Apriori算法的优点109通过伪投影加速PrefixSpan的主要开销:投影序列的后缀经常在递归投影数据库中重复地出现当(投影)数据库不能放在内存时,使用指针形成投影指向序列后缀的偏移s=<a(abc)(ac)d(cf)><(abc)(ac)d(cf)><(_c)(ac)d(cf)><a><ab>s|<a>:(,2)s|<ab>:(,4)110伪投影vs.物理投影伪投影避免物理地拷贝后缀当数据库可以放在内存时,运行时间和空间是有效的然而,当数据库不能放在内存时,它不太有效基于磁盘的随即访问开销很大建议的方法:集成物理投影和伪投影当数据集可以放在内存时,切换成伪投影111PrefixSpan比GSP和FreeSpan快112伪投影的影响113文献:频繁模式挖掘方法R.Agarwal,C.Aggarwal,andV.V.V.Prasad.Atreeprojectionalgorithmforgenerationoffrequentitemsets.JournalofParallelandDistributedComputing,2000.R.Agrawal,T.Imielinski,andA.Swami.Miningassociationrulesbetweensetsofitemsinlargedatabases.SIGMOD'93,207-216,Washington,D.C.R.AgrawalandR.Srikant.Fastalgorithmsforminingassociationrules.VLDB'94487-499,Santiago,Chile.J.Han,J.Pei,andY.Yin:“Miningfrequentpatternswithoutcandidategeneration”.InProc.ACM-SIGMOD’2000,pp.1-12,Dallas,TX,May2000.H.Mannila,H.Toivonen,andA.I.Verkamo.Efficientalgorithmsfordiscoveringassociationrules.KDD'94,181-192,Seattle,WA,July1994.114文献:频繁模式挖掘方法A.Savasere,E.Omiecinski,andS.Navathe.Anefficientalgorithmforminingassociationrulesinlargedatabases.VLDB'95,432-443,Zurich,Switzerland.C.Silverstein,S.Brin,R.Motwani,andJ.Ullman.Scalabletechniquesforminingcausalstructures.VLDB'98,594-605,NewYork,NY.R.SrikantandR.Agrawal.Mininggeneralizedassociationrules.VLDB'95,407-419,Zurich,Switzerland,Sept.1995.R.SrikantandR.Agrawal.Miningquantitativeassociationrulesinlargerelationaltables.SIGMOD'96,1-12,Montreal,Canada.H.Toivonen.Samplinglargedatabasesforassociationrules.VLDB'96,134-145,Bombay,India,Sept.1996.M.J.Zaki,S.Parthasarathy,M.Ogihara,andW.Li.Newalgorithmsforfastdiscoveryofassociationrules.KDD’97.August1997.115文献:频繁模式挖掘(性能改进)S.Brin,R.Motwani,J.D.Ullman,andS.Tsur.Dynamicitemsetcountingandimplicationrulesformarketbasketanalysis.SIGMOD'97,Tucson,Arizona,May1997.D.W.Cheung,J.Han,V.Ng,andC.Y.Wong.Maintenanceofd