數(shù)據(jù)挖掘-CHAPTER5-挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則-內(nèi)容多

1第5章：挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則挖掘事務(wù)數(shù)據(jù)庫中(單維布爾)關(guān)聯(lián)規(guī)則挖掘的可伸縮算法挖掘各種關(guān)聯(lián)/相關(guān)規(guī)則基于限制的關(guān)聯(lián)挖掘-順序模式挖掘小結(jié)2關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則反映一個(gè)事物與其他事物之間的相互依存性和關(guān)聯(lián)性。如果兩個(gè)或者多個(gè)事物之間存在一定的關(guān)聯(lián)關(guān)系，那么，其中一個(gè)事物就能夠通過其他事物預(yù)測到。典型的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題是對超市中的貨籃數(shù)據(jù)（MarketBasket）進(jìn)行分析。通過發(fā)現(xiàn)顧客放入貨籃中的不同商品之間的關(guān)系來分析顧客的購買習(xí)慣。

3什么是關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘首先被Agrawal,ImielinskiandSwami在1993年的SIGMOD會(huì)議上提出在事務(wù)、關(guān)系數(shù)據(jù)庫中的項(xiàng)集和對象中發(fā)現(xiàn)頻繁模式、關(guān)聯(lián)規(guī)則、相關(guān)性或者因果結(jié)構(gòu)頻繁模式:數(shù)據(jù)庫中頻繁出現(xiàn)的項(xiàng)集目的:發(fā)現(xiàn)數(shù)據(jù)中的規(guī)律超市數(shù)據(jù)中的什么產(chǎn)品會(huì)一起購買？—啤酒和尿布在買了一臺(tái)PC之后下一步會(huì)購買?哪種DNA對這種藥物敏感?我們?nèi)绾巫詣?dòng)對Web文檔進(jìn)行分類?4頻繁模式挖掘的重要性許多重要數(shù)據(jù)挖掘任務(wù)的基礎(chǔ)關(guān)聯(lián)、相關(guān)性、因果性序列模式、空間模式、時(shí)間模式、多維關(guān)聯(lián)分類、聚類分析更加廣泛的用處購物籃分析、交叉銷售、直銷點(diǎn)擊流分析、DNA序列分析等等5關(guān)聯(lián)規(guī)則基本模型IBM公司Almaden研究中心的R.Agrawal首先提出關(guān)聯(lián)規(guī)則模型，并給出求解算法AIS。隨后又出現(xiàn)了SETM和Apriori等算法。其中，Apriori是關(guān)聯(lián)規(guī)則模型中的經(jīng)典算法。給定一組事務(wù)產(chǎn)生所有的關(guān)聯(lián)規(guī)則滿足最小支持度和最小可信度6關(guān)聯(lián)規(guī)則基本模型設(shè)I={i1,…,im}為所有項(xiàng)目的集合，D為事務(wù)數(shù)據(jù)庫，事務(wù)T是一個(gè)項(xiàng)目子集（T

I）。每一個(gè)事務(wù)具有唯一的事務(wù)標(biāo)識(shí)TID。設(shè)A是一個(gè)由項(xiàng)目構(gòu)成的集合，稱為項(xiàng)集。事務(wù)T包含項(xiàng)集A，當(dāng)且僅當(dāng)A

T。如果項(xiàng)集A中包含k個(gè)項(xiàng)目，則稱其為k項(xiàng)集。項(xiàng)集A在事務(wù)數(shù)據(jù)庫D中出現(xiàn)的次數(shù)占D中總事務(wù)的百分比叫做項(xiàng)集的支持度。如果項(xiàng)集的支持度超過用戶給定的最小支持度閾值，就稱該項(xiàng)集是頻繁項(xiàng)集（或大項(xiàng)集）。

7關(guān)聯(lián)規(guī)則基本模型關(guān)聯(lián)規(guī)則是形如X

Y的邏輯蘊(yùn)含式，其中X

I，Y

I，且X

Y=

。如果事務(wù)數(shù)據(jù)庫D中有s%的事務(wù)包含X

Y，則稱關(guān)聯(lián)規(guī)則X

Y的支持度為s%實(shí)際上，支持度是一個(gè)概率值。是一個(gè)相對計(jì)數(shù)。support(X

Y)=P(X

Y)項(xiàng)集的支持度計(jì)數(shù)(頻率)support_count包含項(xiàng)集的事務(wù)數(shù)若項(xiàng)集X的支持度記為support(X)，規(guī)則的信任度為support(X

Y)／support(X)。是一個(gè)條件概率P(Y|X)。confidence(X

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

Y)／support_count(X)8頻繁模式和關(guān)聯(lián)規(guī)則ItemsetX={x1,…,xk}找出滿足最小支持度和置信度的所規(guī)則XY

支持度,s,事務(wù)包含XY的概率

置信度,c,

事務(wù)含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}關(guān)聯(lián)規(guī)則Associationrules:A

D(60%,100%)D

A(60%,75%)9挖掘關(guān)聯(lián)規(guī)則—一個(gè)例子規(guī)則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閉頻繁項(xiàng)集and極大頻繁項(xiàng)集一個(gè)長模式包含子模式的數(shù)目,e.g.,{a1,…,a100}contains(1001)+(1002)+…+(110000)=2100–1=1.27*1030sub-patterns!解:Mineclosedpatternsandmax-patternsinstead一個(gè)頻繁項(xiàng)集X

是閉的，如果X是頻繁的，且不存在真超項(xiàng)集nosuper-patternY?X,有相同的支持度計(jì)數(shù)

(proposedbyPasquier,etal.@ICDT’99)項(xiàng)集X是極大頻繁項(xiàng)集

ifXisfrequentandthereexistsnofrequentsuper-patternY?X(proposedbyBayardo@SIGMOD’98)兩者有不同，極大頻繁項(xiàng)集定義中對真超集要松一些。11閉頻繁項(xiàng)集and極大頻繁項(xiàng)集Exercise.DB={<a1,…,a100>,<a1,…,a50>}Min_sup=1.Whatisthesetofcloseditemset?<a1,…,a100>:1<a1,…,a50>:2Whatisthesetofmax-pattern?<a1,…,a100>:1Whatisthesetofallpatterns?!!12關(guān)聯(lián)規(guī)則基本模型關(guān)聯(lián)規(guī)則就是支持度和信任度分別滿足用戶給定閾值的規(guī)則。

發(fā)現(xiàn)關(guān)聯(lián)規(guī)則需要經(jīng)歷如下兩個(gè)步驟：找出所有頻繁項(xiàng)集。由頻繁項(xiàng)集生成滿足最小信任度閾值的規(guī)則。13第5章：挖掘關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則挖掘事務(wù)數(shù)據(jù)庫中(單維布爾)關(guān)聯(lián)規(guī)則挖掘的可伸縮算法挖掘各種關(guān)聯(lián)/相關(guān)規(guī)則基于限制的關(guān)聯(lián)挖掘-順序模式挖掘小結(jié)14Apriori算法的步驟Apriori算法命名源于算法使用了頻繁項(xiàng)集性質(zhì)的先驗(yàn)（Prior）知識(shí)。Apriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過程分為兩個(gè)步驟：通過迭代，檢索出事務(wù)數(shù)據(jù)庫中的所有頻繁項(xiàng)集，即支持度不低于用戶設(shè)定的閾值的項(xiàng)集；利用頻繁項(xiàng)集構(gòu)造出滿足用戶最小信任度的規(guī)則。挖掘或識(shí)別出所有頻繁項(xiàng)集是該算法的核心，占整個(gè)計(jì)算量的大部分。15頻繁項(xiàng)集為了避免計(jì)算所有項(xiàng)集的支持度（實(shí)際上頻繁項(xiàng)集只占很少一部分），Apriori算法引入潛在頻繁項(xiàng)集的概念。若潛在頻繁k項(xiàng)集的集合記為Ck，頻繁k項(xiàng)集的集合記為Lk，m個(gè)項(xiàng)目構(gòu)成的k項(xiàng)集的集合為，則三者之間滿足關(guān)系Lk

Ck

。構(gòu)成潛在頻繁項(xiàng)集所遵循的原則是“頻繁項(xiàng)集的子集必為頻繁項(xiàng)集”。16關(guān)聯(lián)規(guī)則的性質(zhì)

性質(zhì)1：頻繁項(xiàng)集的子集必為頻繁項(xiàng)集。

性質(zhì)2：非頻繁項(xiàng)集的超集一定是非頻繁的。Apriori算法運(yùn)用性質(zhì)1，通過已知的頻繁項(xiàng)集構(gòu)成長度更大的項(xiàng)集，并將其稱為潛在頻繁項(xiàng)集。潛在頻繁k項(xiàng)集的集合Ck是指由有可能成為頻繁k項(xiàng)集的項(xiàng)集組成的集合。以后只需計(jì)算潛在頻繁項(xiàng)集的支持度，而不必計(jì)算所有不同項(xiàng)集的支持度，因此在一定程度上減少了計(jì)算量。

17Apriori:一種候選產(chǎn)生-測試方法頻繁項(xiàng)集的任何子集必須是頻繁的如果{beer,diaper,nuts}是頻繁的,{beer,diaper}也是每個(gè)包含{beer,diaper,nuts}的事務(wù)也包含{beer,diaper}Apriori剪枝原則:如果一個(gè)項(xiàng)集不是頻繁的,將不產(chǎn)生/測試它的超集!方法:由長度為k的頻繁項(xiàng)集產(chǎn)生長度為(k+1)的候選項(xiàng)集,并且根據(jù)DB測試這些候選性能研究表明了它的有效性和可伸縮性18Apriori算法—一個(gè)例子數(shù)據(jù)庫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項(xiàng)集};(2)for(k=2;Lk-1

;k++)dobegin(3)Ck=apriori_gen(Lk-1);//新的潛在頻繁項(xiàng)集(4)foralltransactions

t

Ddobegin(5)Ct=subset(Ck,t);//找出t中包含的潛在的頻繁項(xiàng)(6)forallcandidatesc

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

Ck|c.count

minsup}(10)end;(11)Answer=20Apriori的重要細(xì)節(jié)如何產(chǎn)生候選?步驟1:Lk的自連接步驟2:剪枝候選產(chǎn)生的例子L3={abc,abd,acd,ace,bcd}自連接:L3*L3Abcd：由abc

和abdAcde：由acd

和ace剪枝:acde

被刪除,因?yàn)閍de

不在L3C4={abcd}21如何產(chǎn)生候選?假定Lk-1

中的項(xiàng)集已排序(按字典序排序)步驟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例子-支持計(jì)數(shù)=223例子24由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則根據(jù)公式產(chǎn)生關(guān)聯(lián)規(guī)則對于每個(gè)頻繁項(xiàng)集l，產(chǎn)生所有的非空子集對于l的每個(gè)非空子集s，如果 則輸出規(guī)則”s(l-s)”25頻繁模式挖掘的挑戰(zhàn)挑戰(zhàn)事務(wù)數(shù)據(jù)庫的多遍掃描數(shù)量巨大的候選候選支持度計(jì)數(shù)繁重的工作量改進(jìn)Apriori:基本思想減少事務(wù)數(shù)據(jù)庫的掃描遍數(shù)壓縮候選數(shù)量便于候選計(jì)數(shù)26提高Apriori算法的方法Hash-baseditemsetcounting（散列項(xiàng)集計(jì)數(shù)）Transactionreduction（事務(wù)壓縮）Partitioning（劃分）Sampling（采樣）27劃分:只掃描數(shù)據(jù)庫兩次項(xiàng)集在DB中是頻繁的,它必須至少在DB的一個(gè)劃分中是頻繁的掃描1:劃分?jǐn)?shù)據(jù)庫,并找出局部頻繁模式localfrequentitemset掃描2:求出全局頻繁模式A.Savasere,E.Omiecinski,andS.Navathe.Anefficientalgorithmforminingassociationinlargedatabases.InVLDB’95DB1DB2DBk+=DB++sup1(i)<σDB1sup2(i)<σDB2supk(i)<σDBksup(i)<σDB28抽樣-頻繁模式選取原數(shù)據(jù)庫的一個(gè)樣本,使用Apriori算法在樣本中挖掘頻繁模式掃描一次數(shù)據(jù)庫,驗(yàn)證在樣本中發(fā)現(xiàn)的頻繁模式.再次掃描數(shù)據(jù)庫,找出遺漏的頻繁模式犧牲一些精度換取有效性。H.Toivonen.Samplinglargedatabasesforassociationrules.InVLDB’9629DHP:壓縮候選的數(shù)量散列項(xiàng)集到對應(yīng)的桶中，一個(gè)其hash桶的計(jì)數(shù)小于閾值的k-itemset不可能是頻繁的J.Park,M.Chen,andP.Yu.Aneffectivehash-basedalgorithmforminingassociationrules.InSIGMOD’9530DIC(Dynamicitemsetcounting):減少掃描次數(shù)ABCDABCABDACDBCDABACBCADBDCDABCD{}Itemsetlattice一旦確定A和D是頻繁的,立即開始AD的計(jì)數(shù)一旦確定BCD的兩個(gè)長度為2的子集是頻繁的,立即開始BCD的計(jì)數(shù)事務(wù)1-itemsets2-itemsets…Apriori1-itemsets2-items3-itemsDICS.BrinR.Motwani,J.Ullman,andS.Tsur.Dynamicitemsetcountingandimplicationrulesformarketbasketdata.InSIGMOD’9731使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集VerticalDataFormat使用tid-list,包含item的事務(wù)的標(biāo)識(shí)的集合;M.Zakietal.Newalgorithmsforfastdiscoveryofassociationrules.InKDD’97掃描一次數(shù)據(jù)集將水平格式數(shù)據(jù)轉(zhuǎn)化為垂直格式通過頻繁k項(xiàng)集的tid-list的交集，計(jì)算對應(yīng)(k+1)項(xiàng)集的tid-list32頻繁模式挖掘的瓶頸多遍數(shù)據(jù)庫掃描是昂貴的挖掘長模式需要很多遍掃描,并產(chǎn)生大量候選挖掘頻繁模式i1i2…i100掃描次數(shù):100候選個(gè)數(shù):(1001)+(1002)+…+(110000)=2100-1=1.27*1030!瓶頸:候選產(chǎn)生-測試能夠避免候選產(chǎn)生嗎?33挖掘頻繁模式而不產(chǎn)生候選使用局部頻繁的項(xiàng),由短模式增長產(chǎn)生長模式“abc”是頻繁模式得到包含“abc”的所有事務(wù):DB|abc“d”是DB|abc中的局部頻繁項(xiàng)

abcd是頻繁模式34由事務(wù)數(shù)據(jù)庫構(gòu)造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(單個(gè)項(xiàng)的模式)按頻率的降序?qū)㈩l繁項(xiàng)排序,得到f-list再次掃描DB,構(gòu)造FP-樹F-list=f-c-a-b-m-p35劃分模式和數(shù)據(jù)庫可以按照f-list將頻繁模式劃分成子集F-list=f-c-a-b-m-p包含p的模式包含m但不包含p的模式…包含c但不包含a,b,m,p模式f完全性和非冗余性36從p-條件數(shù)據(jù)庫找出含p的模式從FP-樹的頻繁項(xiàng)頭表開始沿著頻繁項(xiàng)p的鏈搜索FP-樹收集項(xiàng)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條件模式庫項(xiàng)通過建立條件模式庫得到頻繁集38從條件模式基到條件FP-樹對于每個(gè)條件模式基累計(jì)條件模式基中每個(gè)項(xiàng)的計(jì)數(shù)構(gòu)造模式基中頻繁項(xiàng)的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遞歸:

挖掘每個(gè)條件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-樹中的單個(gè)前綴路徑假定(條件)FP-樹T具有單個(gè)共享的前綴路徑P挖掘可以分解成兩步將單個(gè)前綴路徑歸約成一個(gè)結(jié)點(diǎn)連接兩部分的挖掘結(jié)果

a2:n2a3:n3a1:n1{}b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1{}r1=41使用FP-樹挖掘頻繁模式基本思想:頻繁模式增長通過模式和數(shù)據(jù)庫劃分遞歸地增長頻繁模式方法(1)對于每個(gè)頻繁項(xiàng),構(gòu)造它的條件模式基(2)然后構(gòu)造它的條件FP-樹(3)在新構(gòu)造的條件FP-樹上重復(fù)這一過程直到結(jié)果條件FP-樹為空,或者它只包含一條路徑—單個(gè)路徑將產(chǎn)生其子路徑的所有組合,每個(gè)子路徑是一個(gè)頻繁模式42FP-樹結(jié)構(gòu)的優(yōu)點(diǎn)完全性保留頻繁模式挖掘的完整信息不截?cái)嗳魏问聞?wù)的長模式壓縮性壓縮無關(guān)信息—非頻繁的項(xiàng)被刪除項(xiàng)按頻率的降序排列:越是頻繁出現(xiàn),越可能被共享絕對不比原來的數(shù)據(jù)庫大(不計(jì)結(jié)點(diǎn)鏈和計(jì)數(shù)字段)43FP-增長的規(guī)?；疐P-樹不能放在內(nèi)存,怎么辦?—數(shù)據(jù)庫投影數(shù)據(jù)庫投影首先將數(shù)據(jù)庫劃分成一組投影數(shù)據(jù)庫然后對每個(gè)投影數(shù)據(jù)庫構(gòu)造并挖掘FP-樹44FP-增長vs.Apriori:隨支持度增長的可伸縮性DatasetT25I20D10K45FP-增長vs.樹-投影:隨支持度增長的可伸縮性DatasetT25I20D100K46為什么FP-增長是贏家?分治:根據(jù)已經(jīng)得到的頻繁模式劃分任務(wù)和數(shù)據(jù)庫導(dǎo)致較小的數(shù)據(jù)庫的聚焦的搜索其它因素沒有候選產(chǎn)生,沒有候選測試壓縮數(shù)據(jù)庫:FP-樹結(jié)構(gòu)不重復(fù)地掃描整個(gè)數(shù)據(jù)庫基本操作—局部頻繁項(xiàng)計(jì)數(shù)和建立子FP-樹,沒有模式搜索和匹配47有關(guān)的其他方法挖掘頻繁閉項(xiàng)集合和最大模式CLOSET(DMKD’00)挖掘序列模式FreeSpan(KDD’00),PrefixSpan(ICDE’01)頻繁模式的基于限制的挖掘Convertibleconstraints(KDD’00,ICDE’01)計(jì)算具有復(fù)雜度量的冰山數(shù)據(jù)方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:找出頻繁項(xiàng)A,B,C,D,E掃描2:找出以下項(xiàng)集的支持度AB,AC,AD,AE,ABCDEBC,BD,BE,BCDECD,CE,CDE,DE由于BCDE

是最大模式,

不必在此后的掃描時(shí)檢查BCD,BDE,CDER.Bayato.Efficientlymininglongpatternsfromdatabases.InSIGMOD’98TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F潛在的最大模式50關(guān)聯(lián)規(guī)則的可視化:PaneGraph51第5章：挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則挖掘事務(wù)數(shù)據(jù)庫中(單維布爾)關(guān)聯(lián)規(guī)則挖掘的可伸縮算法挖掘各種關(guān)聯(lián)/相關(guān)規(guī)則基于限制的關(guān)聯(lián)挖掘順序模式挖掘小結(jié)52挖掘各種規(guī)則或規(guī)律性多層關(guān)聯(lián)規(guī)則,多維關(guān)聯(lián)規(guī)則，量化關(guān)聯(lián)規(guī)則,相關(guān)性和因果關(guān)系,比率規(guī)則,序列模式,顯露模式,時(shí)間關(guān)聯(lián),局部周期性53多層關(guān)聯(lián)規(guī)則項(xiàng)常常形成層次結(jié)構(gòu)-概念分層多個(gè)抽象層次上挖據(jù)得到的關(guān)聯(lián)規(guī)則-多層關(guān)聯(lián)規(guī)則靈活的支持度設(shè)定:較低層中的項(xiàng)一般具有較低的支持度.一致的支持度Computer[support=10%]LaptopComputer[support=6%]DesktopComputer[support=4%]層1min_sup=5%層2min_sup=5%Level1min_sup=5%Level2min_sup=3%遞減的支持度54多層關(guān)聯(lián):冗余過濾由于項(xiàng)之間的“祖先”聯(lián)系,有些規(guī)則可能是多余的.例LaptopcomputerHPprinter[support=8%,confidence=70%]IBMlaptopcomputerHPprinter[support=2%,confidence=72%]其中IBMlaptopcomputer占laptopcomputer的1/4我們可以說第一個(gè)規(guī)則是第二個(gè)規(guī)則的祖先.如果根據(jù)規(guī)則的祖先,其支持度和置信度都接近于“期望”值，那么，一個(gè)規(guī)則是冗余的.55多層挖掘:逐步深入一種自頂向下,逐步深入的方法:

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

然后挖掘它們下層“較弱的”頻繁模式:IBMlaptopcomputer(5%),HPprinter(4%)多層之間的不同的最小支持度閾值導(dǎo)致不同的算法:如果不同層之間采用相同的min_support

則丟棄t

如果t’的任意祖先是非頻繁的.如果在較低層采用遞減的min_support

則只考察其祖先為頻繁的項(xiàng)集.56多維關(guān)聯(lián)規(guī)則單維規(guī)則:包括單個(gè)謂詞（可以多次出現(xiàn)）或單個(gè)維buys(X,“l(fā)aptopcomputer”)buys(X,“printer”)多維規(guī)則:維或謂詞

2

維間關(guān)聯(lián)規(guī)則(不含重復(fù)謂詞)age(X,”19-25”)

occupation(X,“student”)buys(X,“coke”)混合維關(guān)聯(lián)規(guī)則(含重復(fù)謂詞)age(X,”19-25”)

buys(X,“popcorn”)

buys(X,“coke”)數(shù)據(jù)的屬性可分為兩類分類屬性有限個(gè)不同值,值之間無序量化屬性數(shù)值的,值之間隱含次序57挖掘多維關(guān)聯(lián)規(guī)則的技術(shù)搜索頻繁k-謂詞集:包含k個(gè)合取謂詞的集合例:{age,occupation,buys}

是一個(gè)3-謂詞集.可以按如何處理age

對技術(shù)分類.使用量化屬性的靜態(tài)離散化使用預(yù)先定義的概念分層,對量化屬性靜態(tài)地離散化.量化關(guān)聯(lián)規(guī)則根據(jù)數(shù)據(jù)的分布,將量化屬性離散化到“箱”.基于距離的關(guān)聯(lián)規(guī)則是一種動(dòng)態(tài)的離散化過程,它考慮數(shù)據(jù)點(diǎn)之間的距離.58量化屬性的靜態(tài)離散化(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)使用概念分層,在挖掘之前離散化.數(shù)值用區(qū)間值替換.在關(guān)系數(shù)據(jù)庫中,找出所有的頻繁k-謂詞集需要k

或k+1次表掃描.數(shù)據(jù)立方體非常適合挖掘.n-維方體 對應(yīng)于謂詞集合的方體.從數(shù)據(jù)立方體挖掘可以快得多.59量化關(guān)聯(lián)規(guī)則數(shù)值屬性動(dòng)態(tài)地離散化使挖出的規(guī)則的置信度或緊湊性最大化.2-維量化關(guān)聯(lián)規(guī)則:Aquan1

Aquan2Acat（分類屬性）ARCS方法：使用2-D柵格,1)對屬性進(jìn)行（等寬）分箱2)找頻繁謂詞集3)規(guī)則聚類：對“相鄰的”關(guān)聯(lián)規(guī)則聚類形成一般關(guān)聯(lián)規(guī)則.例:

age(X,”34-35”)

income(X,”31K-50K”)buys(X,”highresolutionTV”)60挖掘基于距離的關(guān)聯(lián)規(guī)則分箱方法不能緊扣區(qū)間數(shù)據(jù)的語義基于距離的劃分,更有意義的離散化考慮:區(qū)間內(nèi)點(diǎn)的密度/數(shù)量區(qū)間內(nèi)點(diǎn)的“緊密性”61具有靈活的支持度限制的

多層ML/MD多維關(guān)聯(lián)規(guī)則為什么?現(xiàn)實(shí)中項(xiàng)的出現(xiàn)頻率差異很大購物中的鉆石,表,筆一致的支持度可能不是一種好的模型靈活的模型通常,層越低,維的組合越多,長模式越長,支持度越小一般規(guī)則應(yīng)當(dāng)是特指的,易于理解的特殊的項(xiàng)或特殊的項(xiàng)群可能被個(gè)別地指定,并具有較高的優(yōu)先權(quán)62興趣度度量:相關(guān)性(Lift)playbasketball

eatcereal[40%,66.7%]是誤導(dǎo)吃谷類食品的學(xué)生所占的百分比為75%,比66.7%還高.playbasketball

noteatcereal[20%,33.3%]更準(zhǔn)確,其支持度和置信度都較低依賴/相關(guān)事件的度量:BasketballNotbasketballSum(row)Cereal谷類200017503750Notcereal10002501250Sum(col.)30002000500063WhichMeasuresShouldBeUsed?提升度和

2

不是好的相關(guān)度量，對于大的交易數(shù)據(jù)庫all-conforcoherencecouldbegoodmeasures(Omiecinski@TKDE’03)Over20interestingnessmeasureshavebeenproposed(seeTan,Kumar,Sritastava@KDD’02)Whicharegoodones?64第6章：挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則挖掘事務(wù)數(shù)據(jù)庫中(單維布爾)關(guān)聯(lián)規(guī)則挖掘的可伸縮算法挖掘各種關(guān)聯(lián)/相關(guān)規(guī)則基于限制的關(guān)聯(lián)挖掘順序模式挖掘頻繁模式挖掘的應(yīng)用/擴(kuò)展小結(jié)65基于約束的數(shù)據(jù)挖掘自動(dòng)地找出數(shù)據(jù)庫中的所有模式?—不現(xiàn)實(shí)!模式可能太多,并不聚焦!數(shù)據(jù)挖掘應(yīng)當(dāng)是一個(gè)交互的過程用戶使用數(shù)據(jù)挖掘查詢語言(或圖形用戶界面)指導(dǎo)需要挖掘什么基于約束的挖掘用戶靈活性:提供挖掘的約束

系統(tǒng)優(yōu)化:考察限制,尋找有效的挖掘—基于約束的挖掘66數(shù)據(jù)挖掘的約束知識(shí)類型約束:分類,關(guān)聯(lián),等.數(shù)據(jù)約束

（指定任務(wù)相關(guān)的數(shù)據(jù)集）—使用類SQL查詢找出Vancouver2000年12月份一起銷售的產(chǎn)品對維/層約束-指定數(shù)據(jù)屬性/概念分層結(jié)構(gòu)的層次關(guān)于region,price,brand,customercategory興趣度約束強(qiáng)規(guī)則:min_support

3%,min_confidence

60%規(guī)則(或模式)約束-指定規(guī)則形式小額銷售(價(jià)格<$10)觸發(fā)大額銷售(sum>$200)67元規(guī)則制導(dǎo)挖掘Meta-RuleGuidedMining元規(guī)則是帶有部分約束謂詞和常量的規(guī)則P1(X,Y)^P2(X,W)=>buys(X,“iPad”)一個(gè)導(dǎo)致的規(guī)則age(X,“15-25”)^profession(X,“student”)=>buys(X,“iPad”)通常情況,元規(guī)則如下形式的規(guī)則模板

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

挖掘過程找出所有的頻繁(l+r)謂詞集(基于最小支持度閾值)必須保留l子集的支持度/計(jì)數(shù)（計(jì)算規(guī)則的置信度）（挖掘過程中）盡可能推進(jìn)約束(見約束推進(jìn)技術(shù))盡可能地應(yīng)用置信度,相關(guān)和其他度量68規(guī)則約束-剪枝搜索空間規(guī)則約束的分類反單調(diào)性Anti-monotonic單調(diào)性Monotonic簡潔性Succinct:可轉(zhuǎn)變的Convertible:不可轉(zhuǎn)變的69規(guī)則約束-反單調(diào)性反單調(diào)性當(dāng)項(xiàng)集S違反規(guī)則約束時(shí),它的任何超集合也違反約束sum(S.Price)

v

是反單調(diào)的sum(S.Price)

v

不是反單調(diào)的例.C:range(S.profit)

15是反單調(diào)的項(xiàng)集ab違反約束Cab的每個(gè)超集也違反約束CTIDTransaction10a,b,c,d,f20b,c,d,f,g,h30a,c,d,e,f40c,e,f,gTDB(min_sup=2)ItemProfita40b0c-20d10e-30f30g20h-1070規(guī)則約束-單調(diào)性單調(diào)性當(dāng)項(xiàng)集S滿足約束時(shí),它的任何超集合也滿足約束sum(S.Price)

v

是單調(diào)的min(S.Price)

v是單調(diào)的例.C:range(S.profit)

70項(xiàng)集af滿足Caf的每個(gè)超集合也滿足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的項(xiàng)的集合A1,,則滿足C的任意集合S都基于A1,即,S

包含一個(gè)屬于A1的子集思想:不查看事務(wù)數(shù)據(jù)庫,項(xiàng)集S是否滿足約束C可以根據(jù)選取的項(xiàng)確定

min(S.Price)

v

是簡潔的sum(S.Price)v

不是簡潔的優(yōu)化:如果C

是簡潔的,C

是預(yù)計(jì)數(shù)可推進(jìn)的(pre-counting

pushable)72Apriori算法—一個(gè)例子DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanD73樸素算法:Apriori+約束DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanD約束:Sum{S.price<5}74受約束的Apriori算法:推進(jìn)反單調(diào)約束DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanD約束:Sum{S.price<5}75轉(zhuǎn)換“強(qiáng)硬的”約束通過將項(xiàng)適當(dāng)?shù)嘏判?將強(qiáng)硬的約束轉(zhuǎn)換成反單調(diào)的或單調(diào)的例C:avg(S.profit)

25將項(xiàng)按profit值的遞減序排序<a,f,g,d,b,h,c,e>如果項(xiàng)集afg

違反Cafgd,afg*也違反C約束C成為反單調(diào)的!TIDTransaction10a,b,c,d,f20b,c,d,f,g,h30a,c,d,e,f40c,e,f,gTDB(min_sup=2)ItemProfita40b0c-20d10e-30f30g20h-1076可轉(zhuǎn)變的約束設(shè)R項(xiàng)集的項(xiàng)以特定次序安排，可轉(zhuǎn)變反單調(diào)如果項(xiàng)集S

違反約束C,每個(gè)關(guān)于R以S為前綴的項(xiàng)集也違反約束C例.avg(S)

v

，如果項(xiàng)值遞減序排列可轉(zhuǎn)變單調(diào)如果項(xiàng)集S

滿足約束C,每個(gè)關(guān)于R以S為前綴的項(xiàng)集也滿足約束C.例.avg(S)

v，如果項(xiàng)值遞增序排列77強(qiáng)可轉(zhuǎn)變約束avg(X)

25關(guān)于項(xiàng)值的遞減序R:<a,f,g,

d,b,h,c,e>是可轉(zhuǎn)變反單調(diào)的如果項(xiàng)集af違反約束C,每個(gè)以af為前綴的項(xiàng)集也違反C,如afdavg(X)

25關(guān)于項(xiàng)值的遞增序R-1:<e,c,h,b,d,g,f,a>是可轉(zhuǎn)變單調(diào)的如果項(xiàng)集d

滿足約束C,df

和dfa

也滿足,它們具有前綴d這樣,avg(X)

25是強(qiáng)可轉(zhuǎn)變的ItemProfita40b0c-20d10e-30f30g20h-1078約束的性質(zhì)匯總約束反單調(diào)單調(diào)簡潔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約束的分類可轉(zhuǎn)變反單調(diào)可轉(zhuǎn)變單調(diào)強(qiáng)可轉(zhuǎn)變不可轉(zhuǎn)變的簡潔反單調(diào)單調(diào)80Apriori能夠處理可轉(zhuǎn)變的約束嗎?可轉(zhuǎn)變的,但既不是單調(diào),反單調(diào),也不是簡潔的約束不能推進(jìn)到Apriori挖掘算法的挖掘過程中在逐級的框架下,不能做直接基于該約束的剪枝項(xiàng)集df

違反約束C:avg(X)>=25由于adf

滿足C,Apriori需要df

來組裝adf,因此不能將df

剪去但是,在模式增長框架下該約束可以推進(jìn)到挖掘過程中!ItemValuea40b0c-20d10e-30f30g20h-1081具有可轉(zhuǎn)變約束的挖掘C:avg(X)>=25,min_sup=2以值的遞減序R:<a,f,g,d,b,h,c,e>列出事務(wù)中的每一個(gè)項(xiàng)關(guān)于R,C是可轉(zhuǎn)變反單調(diào)的掃描TDB一次刪除非頻繁項(xiàng)項(xiàng)h

被刪除項(xiàng)a和f是好的,…基于投影的挖掘利用項(xiàng)投影的適當(dāng)次序許多強(qiáng)硬的約束可以轉(zhuǎn)變成(反)單調(diào)的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討論—處理多個(gè)約束不同的約束需要不同的,甚至相互沖突的項(xiàng)序如果存在序R,

使得約束C1

和C2

關(guān)于R是可轉(zhuǎn)變的,則兩個(gè)可轉(zhuǎn)變的約束之間不存在沖突如果項(xiàng)序存在沖突試圖先滿足一個(gè)約束然后使用另一約束的序,在相應(yīng)的投影數(shù)據(jù)庫中挖掘頻繁項(xiàng)集83第5章：挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則挖掘事務(wù)數(shù)據(jù)庫中(單維布爾)關(guān)聯(lián)規(guī)則挖掘的可伸縮算法挖掘各種關(guān)聯(lián)/相關(guān)規(guī)則基于限制的關(guān)聯(lián)挖掘順序模式挖掘小結(jié)84序列數(shù)據(jù)庫和序列模式挖掘事務(wù)數(shù)據(jù)庫,時(shí)間序列數(shù)據(jù)庫vs.序列數(shù)據(jù)庫頻繁模式vs.(頻繁)序列模式序列模式挖掘的應(yīng)用顧客購物序列:在3個(gè)月內(nèi),先買計(jì)算機(jī),然后買CD-ROM,再后買數(shù)字照相機(jī).醫(yī)療處治,自然災(zāi)害(例如,地震),科學(xué)和工程進(jìn)度,股票和市場等.電話呼叫模式,Web日志點(diǎn)擊流DNA序列和基因結(jié)構(gòu)85什么是序列模式挖掘?給定一個(gè)序列的集合,找出所有的頻繁子序列一個(gè)序列數(shù)據(jù)庫

一個(gè)序列:<(ef)(ab)(df)cb>一個(gè)元素可能包含一個(gè)項(xiàng)集.在一個(gè)元素中的項(xiàng)是無序的,我們可以用字典序列出它們.

<a(bc)dc>是<a(abc)(ac)d(cf)>的子序列給定支持度閾值min_sup=2,<(ab)c>是一個(gè)序列模式SIDsequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>86序列模式挖掘的挑戰(zhàn)大量的可能的序列模式隱藏在數(shù)據(jù)庫中挖掘算法應(yīng)當(dāng)可能的話,找出滿足最小支持度閾值的模式的完全集高度有效的,可伸縮的,僅涉及不多次數(shù)的數(shù)據(jù)庫掃描可以與各種用戶指定的約束結(jié)合87序列模式挖掘研究概念引進(jìn)和最初的類Apriori算法R.Agrawal&R.Srikant.“Miningsequentialpatterns,”ICDE’95GSP—一種基于Apriori的,有影響的算法(IBMAlmaden開發(fā))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序列模式的基本性質(zhì):Apriori基本性質(zhì):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方法概述初始,數(shù)據(jù)庫中的每個(gè)項(xiàng)都是長度為1的候選foreachlevel(即,長度為k的序列)do掃描數(shù)據(jù)庫對每個(gè)候選序列收集支持度計(jì)數(shù)使用Apriori,由長度為k的頻繁序列產(chǎn)生長度為(k+1)的候選序列repeatuntil找不到頻繁序列或候選主要優(yōu)點(diǎn):根據(jù)Apriori對后選剪枝90找長度為1的序列模式使用一個(gè)例子考查GSP初始候選:所有單元素序列<a>,<b>,<c>,<d>,<e>,<f>,<g>,<h>掃描數(shù)據(jù)庫一次,對候選進(jìn)行支持度計(jì)數(shù)<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產(chǎn)生長度為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個(gè)長度為2的候選不使用Apriori性質(zhì),8*8+8*7/2=92個(gè)候選Apriori剪裁掉44.57%的候選92找出長度為2的序列模式再掃描數(shù)據(jù)庫一次,對每個(gè)長度為2的候選收集支持度計(jì)數(shù)有19長度為2的候選,滿足最小支持度閾值它們是長度為2的序列模式93產(chǎn)生長度為3的候選并找出長度為3的模式產(chǎn)生長度為3的候選長度為2的序列模式自連接根據(jù)Apriori性質(zhì)<ab>,<aa>和<ba>都是長度為2的序列模式

<aba>是一個(gè)長度為3的候選<(bd)>,<bb>和<db>都是長度為2的序列模式

<(bd)b>是一個(gè)長度為3的候選產(chǎn)生46個(gè)候選找出長度為3的序列模式再次掃描數(shù)據(jù)庫,收集候選的支持度計(jì)數(shù)46個(gè)候選中有19個(gè)滿足支持度計(jì)數(shù)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個(gè)長度為1的序列模式第2次掃描:51候選.19個(gè)長度為2的序列模式.10候選不在DB第3次掃描:46個(gè)候選.19長度為3的序列模式.20個(gè)候選不在DB第4次掃描:8個(gè)候選.6個(gè)長度為4的序列模式.第5次掃描:1個(gè)候選.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的候選掃描數(shù)據(jù)庫1次,找出F1,長度為1的序列模式的集合令k=1; whileFkisnotemptydo由Fk形成Ck+1,長度為(k+1)的候選的集合;如果Ck+1

非空,掃描一次數(shù)據(jù)庫,找出Fk+1,長度為(k+1)序列模式的集合令k=k+1;96GSP的瓶頸可能產(chǎn)生的候選的集合可能很大1,000長度為1的頻繁序列可以產(chǎn)生

長度為2的候選!挖掘中多次掃描數(shù)據(jù)庫實(shí)際挑戰(zhàn):挖掘長序列模式指數(shù)個(gè)數(shù)短候選一個(gè)長度為100的序列模式需要1030個(gè)候選序列!97FreeSpan:頻繁模式投影的序列模式挖掘FreeSpan:FrequentPattern-ProjectedSequentialPatternMining一種分治的方法基于當(dāng)前的頻繁模式集,遞歸地將序列數(shù)據(jù)庫投影到一組較小的數(shù)據(jù)庫挖掘每個(gè)較小的數(shù)據(jù)庫,發(fā)現(xiàn)它們的模式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個(gè)子集合:包含項(xiàng)f

的序列模式包含e

不含f的序列模式包含d

但不含e

和f

包含a

但不含d,e和

f包含c

但不含a,d,e

和f只包含項(xiàng)bSequenceDatabaseSDB<(bd)cb(ac)><(bf)(ce)b(fg)><(ah)(bf)abf><(be)(ce)d><a(bd)bcb(ade)>98由FreeSpan到PrefixSpan:為什么?Freespan:基于投影:不需要產(chǎn)生候選序列但是,投影可能在序列的任意點(diǎn)進(jìn)行,投影后的序列縮短不多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個(gè)子集合:具有前綴<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>的序列模式只需要考慮關(guān)于<a>的投影<a>-投影數(shù)據(jù)庫:<(abc)(ac)d(cf)>,<(_d)c(bc)(ae)>,<(_b)(df)cb>,<(_f)cbc>找出所有長度為2的序列模式.具有前綴<a>:<aa>,<ab>,<(ab)>,<ac>,<ad>,<af>進(jìn)一步劃分成6個(gè)子集合具有前綴<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>-投影數(shù)據(jù)庫<(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的有效性不需要產(chǎn)生候選序列投影數(shù)據(jù)庫不斷收縮PrefixSpan的主要開銷:構(gòu)造投影數(shù)據(jù)庫可以用兩級(bi-level)投影改進(jìn)104PrefixSpan的優(yōu)化技術(shù)PrefixSpan的優(yōu)化技術(shù)單級vs.兩級投影具有3路檢驗(yàn)的兩級投影可以壓縮投影數(shù)據(jù)庫的數(shù)量和大小物理投影vs.偽投影當(dāng)投影數(shù)據(jù)庫可以放在內(nèi)存時(shí),偽投影可能降低投影的效果并發(fā)投影vs.劃分投影劃分投影可以避免磁盤空間爆炸通過兩級投影擴(kuò)展基于長度為2的序列模式劃分搜索空間只形成投影數(shù)據(jù)庫,并在兩級投影數(shù)據(jù)庫上進(jìn)行遞歸挖掘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>出現(xiàn)2次<ac>出現(xiàn)4次<ca>出現(xiàn)2次<(ac)>出現(xiàn)1次所有長度為2的序列模式都在S-矩陣中發(fā)現(xiàn)106挖掘<ab>-投影數(shù)據(jù)庫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>-投影數(shù)據(jù)庫<(_c)(ac(cf)><(_c)a><c>局部長度為1的序列模式:<a>,<c>,<(_c)>a0c(1,0,1)1(_c)(

,2,)(,1,)

ac(_c)S-矩陣不希望形成(_ac),因此不必對它計(jì)數(shù).導(dǎo)致模式<a(bc)a>107兩級投影的好處每次可以發(fā)現(xiàn)更多的模式較少的投影在上例中,有53個(gè)模式.53個(gè)逐級投影22個(gè)兩級投影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>-投影數(shù)據(jù)庫排除d使用Apriori啟發(fā)式方法在投影數(shù)據(jù)庫中剪去項(xiàng)類Apriori算法的優(yōu)點(diǎn)109通過偽投影加速PrefixSpan的主要開銷:投影序列的后綴經(jīng)常在遞歸投影數(shù)據(jù)庫中重復(fù)地出現(xiàn)當(dāng)(投影)數(shù)據(jù)庫不能放在內(nèi)存時(shí),使用指針形成投影指向序列后綴的偏移s=<a(abc)(ac)d(cf)><(abc)(ac)d(cf)><(_c)(ac)d(cf)><a><ab>s|<a>:(,2)s|<ab>:(,4)110偽投影vs.物理投影偽投影避免物理地拷貝后綴當(dāng)數(shù)據(jù)庫可以放在內(nèi)存時(shí),運(yùn)行時(shí)間和空間是有效的然而,當(dāng)數(shù)據(jù)庫不能放在內(nèi)存時(shí),它不太有效基于磁盤的隨即訪問開銷很大建議的方法:集成物理投影和偽投影當(dāng)數(shù)據(jù)集可以放在內(nèi)存時(shí),切換成偽投影111PrefixSpan比GSP和FreeSpan快112偽投影的影響113文獻(xiàn):頻繁模式挖掘方法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文獻(xiàn):頻繁模式挖掘方法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文獻(xiàn):頻繁模式挖掘(性能改進(jìn))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