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-增長的規?；疐P-樹不能放在內存,怎么辦?—數據庫投影數據庫投影首先將數據庫劃分成一組投影數據庫然后對每個投影數據庫構造并挖掘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