高級人工智能

第十二章

關聯規則

AssociationRules2023/7/142內容提要

引言Apriori算法FP-growth算法并行關聯規則挖掘多維關聯規則挖掘相關規則關聯規則改進2023/7/143關聯規則

關聯規則反映一個事物與其他事物之間的相互依存性和關聯性。如果兩個或者多個事物之間存在一定的關聯關系，那么，其中一個事物就能夠通過其他事物預測到。關聯規則表示了項之間的關系。示例:cereal,milkfruit“買谷類食品和牛奶的人也會買水果.”商店可以把牛奶和谷類食品作特價品以使人們買更多的水果.2023/7/14史忠植關聯規則4市場購物籃分析分析事務數據庫表我們是否可假定?Chips=>SalsaLettuce=>SpinachPersonBasketAChips,Salsa,Cookies,Crackers,Coke,BeerBLettuce,Spinach,Oranges,Celery,Apples,GrapesCChips,Salsa,FrozenPizza,FrozenCakeDLettuce,Spinach,Milk,Butter2023/7/145基本概念通常,數據包含:TIDBasket事務ID項的子集2023/7/146

關聯規則挖掘在事務數據庫,關系數據庫和其它信息庫中的項或對象的集合之間,發現頻繁模式,關聯,相關,或因果關系的結構.頻繁模式:數據庫中出現頻繁的模式(項集,序列,等等)2023/7/147基本概念項集事務關聯規則

-事務數據集(例如右圖)事務標識TID

每一個事務關聯著一個標識,稱作TID.Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,F2023/7/148關聯規則的度量支持度sD中包含A和B的事務數與總的事務數的比值規則AB在數據集D中的支持度為s,其中s

表示D中包含AB

(即同時包含A和B)的事務的百分率.2023/7/149關聯規則的度量可信度cD中同時包含A和B的事務數與只包含A的事務數的比值規則AB在數據集D中的可信度為c,

其中c表示D中包含A的事務中也包含B的百分率.即可用條件概率P(B|A)表示.confidence(A

B)=P(B|A)

條件概率P(B|A)表示A發生的條件下B也發生的概率.2023/7/1410關聯規則的度量關聯規則根據以下兩個標準(包含或排除):最小支持度

–

表示規則中的所有項在事務中出現的頻度最小可信度

-表示規則中左邊的項(集)的出現暗示著右邊的項(集)出現的頻度2023/7/14史忠植關聯規則11市場購物籃分析I是什么?事務IDB的T是什么?s(Chips=>Salsa)是什么?c(Chips=>Salsa)是什么?事務ID購物籃AChips,Salsa,Cookies,Crackers,Coke,BeerBLettuce,Spinach,Oranges,Celery,Apples,GrapesCChips,Salsa,FrozenPizza,FrozenCakeDLettuce,Spinach,Milk,Butter,Chips2023/7/1412頻繁項集項集–任意項的集合k-項集–包含k個項的項集頻繁(或大)項集–滿足最小支持度的項集若I包含m個項,那么可以產生多少個項集?2023/7/1413強關聯規則給定一個項集,容易生成關聯規則.項集:{Chips,Salsa,Beer}Beer,Chips=>SalsaBeer,Salsa=>ChipsChips,Salsa=>Beer強規則是有趣的強規則通常定義為那些滿足最小支持度和最小可信度的規則.2023/7/14史忠植關聯規則14關聯規則挖掘兩個基本步驟找出所有的頻繁項集滿足最小支持度找出所有的強關聯規則由頻繁項集生成關聯規則保留滿足最小可信度的規則2023/7/1415內容提要引言Apriori算法FP-growth算法并行關聯規則挖掘多維關聯規則挖掘相關規則關聯規則改進總結2023/7/1416Apriori算法IBM公司Almaden研究中心的R.Agrawal等人在1993年提出的AIS和SETM。在1994年提出Apriori和AprioriTid。Apriori和AprioriTid算法利用前次過程中的數據項目集來生成新的候選數據項目集，減少了中間不必要的數據項目集的生成，提高了效率2023/7/1417生成頻繁項集Na?vealgorithmn<-|D|foreachsubsetsofIdo

l<-0

foreachtransactionTinDdoifsisasubsetofTthenl<-l+1

ifminimumsupport<=l/nthen

addstofrequentsubsets2023/7/14史忠植關聯規則18生成頻繁項集na?vealgorithm的分析I的子集:O(2m)為每一個子集掃描n個事務測試s為T的子集:O(2mn)隨著項的個數呈指數級增長!我們能否做的更好?2023/7/1419Apriori性質定理(Apriori性質):

若A是一個頻繁項集,則A的每一個子集都是一個頻繁項集.證明:設n為事務數.假設A是l個事務的子集,若A’

A

,

則A’

為l’(l’l)個事務的子集.因此,l/n≥s(最小支持度),l’/n≥s也成立.2023/7/14史忠植關聯規則20Apriori算法Apriori算法是一種經典的生成布爾型關聯規則的頻繁項集挖掘算法.算法名字是緣于算法使用了頻繁項集的性質這一先驗知識.思想:Apriori使用了一種稱作level-wise搜索的迭代方法,其中k-項集被用作尋找(k+1)-項集. 首先,找出頻繁1-項集,以L1表示.L1用來尋找L2,即頻繁2-項集的集合.L2用來尋找L3,以此類推,直至沒有新的頻繁k-項集被發現.每個Lk都要求對數據庫作一次完全掃描..2023/7/1421生成頻繁項集中心思想:由頻繁(k-1)-項集構建候選k-項集方法找到所有的頻繁1-項集擴展頻繁(k-1)-項集得到候選k-項集剪除不滿足最小支持度的候選項集2023/7/14史忠植關聯規則22Apriori:一種候選項集生成-測試方法Apriori剪枝原理:若任一項集是不頻繁的,則其超集不應該被生成/測試!方法:由頻繁k-項集生成候選(k+1)-項集,并且在DB中測試候選項集性能研究顯示了Apriori算法是有效的和可伸縮(scalablility)的.2023/7/1423TheApriori算法—一個示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,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}22023/7/14史忠植關聯規則24Apriori算法Algorithm:Apriori輸入:Database,D,oftransactions;minimumsupportthreshold,min_sup.輸出:L,freuqentitemsetsinD.過程:Ck:CandidateitemsetofsizekLk:frequentitemsetofsizekL1=find_frequent_1_itemsets(D);for(k=2;Lk+1!=;k++)dobegin{

Ck=apriori_gen(Lk-1,min_sup);

foreachtransactiontindatabaseDdo{//scanDforcounts

Ct=subset(Ck,t);//getthesubsetsoftthatarecandidatesForeachcandidatecCt

c.count++;}

Lk=candidatesinCkwithmin_support}endreturnL=k

Lk;2023/7/14史忠植關聯規則25Apriori算法Procedureapriori_gen(Lk-1:frequent(k-1)-itemsets;min_sup:minimumsupportthreshold)foreachitemsetl1Lk-1

foreachitemsetl2Lk-1

if(l1[1]=l2[1])(l1[2]=l2[2])…

(l1[k-1]=l2[k-1])

Then{c=join(l1,l2)//joinstep:generatecandidatesifhas_infrequent_subset(c,Lk-1)thendeletec;//prunestep:removeunfruitfulcandidateelseaddctoCk}return

Ck2023/7/14史忠植關聯規則26Apriori算法JoinisgeneratecandidatessetofitemsetsCkfrom2itemsetsinLk-1Procedurejoin(p,q)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-12023/7/14史忠植關聯規則27Apriori算法Procedurehas_infrequent_subset(c:candidatek-itemset;Lk-1:frequent(k-1)-itemsets;)//usepriorknowledge

foreach(k-1)-subsetsofcifs

Lk-1then

returnTRUE;returnFALSE.2023/7/14史忠植關聯規則28Apriori算法如何生成候選項集?步驟1:自連接Lk步驟2:剪枝如何計算候選項集的支持度?候選項庥生成的示例L3={abc,abd,acd,ace,bcd}自連接:L3*L3由abc

和abd

連接得到abcd由acd

和ace

連接得到acde剪枝:因為ade不在L3中acde被剪除C4={abcd}2023/7/1429如何生成候選項集?假定Lk-1中的項以一定順序排列步驟1:自連接Lk-1

insertinto

Ckselectp.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-1步驟2:剪枝forallitemsetscinCk

doforall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk2023/7/14史忠植關聯規則30如何計算候選項集的支持度?為何候選項集的支持度的計算是一個問題?候選項集的總數可能是巨大的

一個事務可能包含多個候選項集方法:候選項集被存儲在一個哈希樹哈希樹的葉子結點包含一個項集和計數的列表內部結點包含一個哈希表子集函數:

找出包含在一個事務中的所有候選項集2023/7/1431頻繁模式挖掘的挑戰挑戰多次掃描事務數據庫巨大數量的候選項集繁重的計算候選項集的支持度工作改進Apriori:大體的思路減少事務數據庫的掃描次數縮減候選項集的數量使候選項集的支持度計算更加方便2023/7/1432AprioriTid算法AprioriTid算法由Apriori算法改進優點：只和數據庫做一次交互，無須頻繁訪問數據庫將Apirori中的Ck

擴展，內容由{c}變為{TID，c}，TID用于唯一標識事務引入Bk，使得Bk

對于事務的項目組織集合，而不是被動的等待Ck

來匹配2023/7/14史忠植關聯規則33AprioriTid算法舉例：minsupp=2數據庫：TID項目1001342002353001235400252023/7/1434AprioriTid算法示例TID項目集100{1}{3}{4}200{2}{3}{5}300{1}{2}{3}{5}400{2}{5}項集支持度{1}2{2}3{3}3{5}32023/7/1435ApioriTid算法示例TID項目集100{{13}}200{{23}{25}{35}}300{{12}{13}{15}{23}{25}{35}}400{{25}}項集支持度{13}2{23}2{25}3{35}22023/7/1436ApioriTid算法示例TID項目集100空200{{235}}300{{235}}400空2023/7/14史忠植關聯規則37ApioriTid算法上面圖中分別為Bk

和Lk，而Ck

和Apriori算法產生的一樣，因此沒有寫出來可以看到Bk

由Bk-1

得到，無須由數據庫取數據缺點：內存要求很大，事務過多的時候資源難以滿足2023/7/1438內容提要引言Apriori算法FP-growth算法并行關聯規則挖掘多維關聯規則挖掘相關規則關聯規則改進總結2023/7/14史忠植關聯規則39頻繁模式挖掘的瓶頸多次掃描數據庫是高代價的長模式的挖掘需要多次掃描數據庫以及生成許多的候選項集找出頻繁項集i1i2…i100掃描次數:100候選項集的數量:(1001)+(1002)+…+(110000)=2100-1=1.27*1030!瓶頸:候選項集-生成-測試我們能否避免生成候選項集?2023/7/1440不生成候選項集的頻繁模式挖掘利用局部頻繁的項由短模式增長為長模式“abc”是一個頻繁模式得到所有包含“abc”的事務:DB|abc“d”是DB|abc的一個局部頻繁的項abcd是一個頻繁模式2023/7/1441FPGrowth算法(Han,Pei,Yin2000)Apriori算法的一個有問題的方面是其候選項集的生成指數級增長的來源另一種方法是使用分而治之的策略(divideandconquer)思想:

將數據庫的信息壓縮成一個描述頻繁項相關信息的頻繁模式樹2023/7/1442利用FP-樹進行頻繁模式挖掘思想:頻繁模式增長遞歸地增長頻繁模式借助模式和數據庫劃分方法對每個頻繁項,構建它的條件模式基,然后構建它的條件FP-樹.對每個新創建的條件FP-樹重復上述過程直至結果FP-樹為空,或者它僅包含一個單一路徑.該路徑將生成其所有的子路徑的組合,每個組合都是一個頻繁模式.2023/7/1443頻繁1-項集最小支持度為20%(計數為2)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3ItemsetSupportcount{I1}6{I2}7{I3}6{I4}2{I5}2{I6}1ItemsetSupportcount{I1}6{I2}7{I3}6{I4}2{I5}2

事務數據庫

支持度計數

頻繁1-項集2023/7/14史忠植關聯規則44FP-樹構建ItemsetSupportcount{I1}6{I2}7{I3}6{I4}2{I5}2ItemsetSupportcount{I2}7{I1}6{I3}6{I4}2{I5}2按支持度降序排列2023/7/1445FP-樹構建創建根結點null掃描數據庫

事務1:I1,I2,I5

排序:I2,I1,I5處理事務

以項的順序增加結點

標注項及其計數(I2,1)(I1,1)(I5,1)1I50I40I31I11I2維護索引表2023/7/1446FP-樹構建null(I2,2)(I1,1)(I5,1)0I51I40I30I12I2(I4,1)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I32023/7/1447FP-樹構建null(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(I4,1)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3(I3,2)(I3,2)(I1,2)(I3,2)(I4,1)(I5,1)2023/7/1448FP-樹構建掃描事務數據庫D一次,得到頻繁項的集合F及它們的支持度.將F按支持度降序排列成L,L是頻繁項的列表.創建FP-樹的根,標注其為NULL.對D中的每個事務進行以下操作:根據L中的次序對事務中的頻繁項進行選擇和排序.設事務中的已排序的頻繁項列表為[p|P],其中p表示第一個元素,P表示剩余的列表.調用insert_Tree([p|P],T).2023/7/1449FP-樹構建Insert_Tree([p|P],T)

IfThasachildNsuchthatN.item-name=p.item-name,

thenincrementN’scountby1;

else

createanewnodeN,andletitscountbe1,itsparentlinkbelinkedtoT,anditsnode-linktothenodeswiththesameitem-nameviathenode-linkstructure.

IfPisnonempty,callinsert_tree(P,N)recursively.2023/7/1450挖掘FP-tree從索引表中的最后一個項開始找到所有包含該項的路徑沿著結點-鏈接(node-links)確定條件模式路徑中符合頻度要求的模式構建FP-treeC添加項至C中所有路徑,生成頻繁模式遞歸地挖掘C(添加項)從索引表和樹中移除項2023/7/1451挖掘FP-Treenull(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(I4,1)(I3,2)(I3,2)(I4,1)(I5,1)(I1,2)(I3,2)前綴路徑(I2I1,1)(I2I1I3,1)條件路徑(I2I1,2)

條件FP-tree(I2I1I5,2),(I2I5,2),(I1I5,2)null(I2,2)(I1,2)2023/7/14史忠植關聯規則52挖掘FP-Tree項條件模式基條件FP-tree生成的頻繁模式I5{(I2I1:1),(I2I1I3:1)}<I2:2,I1:2>I2I5:2,I1I5:2,I2I1I5:2I4{(I2I1:1),(I2:1)}<I2:2>I2I4:2I3{(I2I1:2,(I2:2),(I1:2)}<I2:4,I1:2>,<I1:2>I2I3:4,I1I3:2,I2I1I3:2I1{(I2:4)}<I2:4>I2I1:42023/7/14史忠植關聯規則53挖掘FP-TreeProcedureFP_growth(Tree,)IfTreecontainsasinglepathPthenforeachcombination(denoteas)ofthenodesinthepathPgeneratepatternwithsupport=minisupofnodesin;ElseforeachaiintheheaderofTree{generatepattern=aiwithsupport=ai.support;construct,sconditionalpatternbaseandthen’conditionalFP_treeTree;IFTree?thencallFP_growth(Tree,);}

2023/7/1454由事務數據庫構建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項(單一項模式)按支持度降序對頻繁項排序為F-list再次掃描DB,構建FP-treeF-list=f-c-a-b-m-p2023/7/14史忠植關聯規則55劃分模式和數據庫頻繁模式根據F-list可以被劃分為若干子集F-list=f-c-a-b-m-p包含p的模式包含m但包含p的模式…包含c但不包含a,b,m,p的模式模式f完整性和非冗余性2023/7/1456從P的條件數據庫找出包含P的模式從FP-tree的索引表的頻繁項開始沿著每個頻繁項p的鏈接遍歷FP-tree累積項p的所有轉換前綴路徑來形成的p的條件模式基條件模式基項 條件模式基c 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:1HeaderTableItemfrequencyheadf 4c 4a 3b 3m 3p 32023/7/14史忠植關聯規則57遞歸:挖掘每個條件FP-tree{}f:3c:3a:3m-條件FP-tree“am”的條件模式基:(fc:3){}f:3c:3am-條件FP-tree“cm”的條件模式基:(f:3){}f:3cm-條件FP-tree“cam”的條件模式基:(f:3){}f:3cam-條件FP-tree2023/7/1458一個特例:FP-tree中的單一前綴路徑假定(條件的)FP-treeT有一個共享的單一前綴路徑P挖掘可以分為兩部分將單一前綴路徑約簡為一個結點將兩部分的挖掘結果串聯a2:n2a3:n3a1:n1{}b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1{}r1=2023/7/1459通過DB投影(Projection)使FP-growth可伸縮FP-tree不能全放入內存?—DB投影首先將一個數據庫劃分成一個由若干投影(Projected)數據庫組成的集合然后對每個投影數據庫構建和挖掘FP-treeParallelprojectionvs.Partitionprojection

技術Parallelprojectionisspacecostly2023/7/14史忠植關聯規則60Partition-basedProjectionParallelprojection需要很多磁盤空間Partitionprojection節省磁盤空間Tran.DBfcampfcabmfbcbpfcampp-projDBfcamcbfcamm-projDBfcabfcafcab-projDBfcb…a-projDBfc…c-projDBf…f-projDB…am-projDBfcfcfccm-projDBfff…2023/7/1461改進途徑使用哈希表存儲候選k-項集的支持度計數移除不包含頻繁項集的事務對數據采樣劃分數據若一個項集是頻繁的,則它必定在某個數據分區中是頻繁的.2023/7/1462FP-tree結構的優點完整性保持了頻繁項集挖掘的完整信息沒有打斷任何事務的長模式緊密性減少不相關的信息—不頻繁的項沒有了項按支持度降序排列:越頻繁出現,越可能被共享決不會比原數據庫更大(不計結點鏈接和計數域)對Connect-4數據庫,壓縮比率可以超過1002023/7/1463內容提要

引言Apriori算法FP-growth算法并行關聯規則挖掘多維關聯規則挖掘相關規則關聯規則改進總結Threeparallelalgorithms:CD,DD,CaDbasedonAprioriDiscoveringfrequentitemsets(1)ismuchmoreexpensivethangeneratingrules(2)Phase1:Eachnodegeneratescandidatek-itemsetslocallyfromthefrequent(k-1)-itemsetshowtopartition?

Phase2:Thematchcandidatesitemsetsandtransactionscollectthelocalcountshowtodistribute?Phase3:-determinetheglobalcountsforitemsetshowtofind?findfrequentk-itemsetsandreplicateinallnodes并行關聯規則挖掘2023/7/14史忠植關聯規則64k-itemsetAnitemsethavingkitemsLkSetoffrequentk-itemsets(thosewithminimumsupport)

Eachmemberofthissethas2fields:itemsetandsupportcountCkSetofcandidatek-itemsets(potentiallyfrequentitemsets)

Eachmemberofthissethas2fields:itemsetandsupportcountPiProcessorwithid-iDiThedatasetlocaltotheprocessorPiDRiThedatasetlocaltotheprocessorPiafterrepartitioningCikThecandidatesetmaintainedwiththeprocessorPiduringthekthpass(therearekitemsineachcandidate)并行關聯規則挖掘2023/7/1465Objective:minimizingcommunicationTechniques:-Straight-forwardparallelizationofAprioriCarryoutredundantduplicatecomputationsinparalleltoavoidcommunicationOnlyrequirescommunicatingcountvalues(nodatatuplesareexchanged)Processorscanscanthelocaldataasynchronouslyinparallel計數分布CD2023/7/14史忠植關聯規則66Algorithm:Pass1:EachprocessorPigeneratesitslocalcandidateitemsetCi1dependingontheitemspresentinitslocaldatapartitionDiDevelopandExchangelocalcountsCi1

DevelopglobalsupportcountsC1計數分布CD2023/7/14史忠植關聯規則67Algorithm:Passk>1:PigeneratesthecompleteCkusingthecompleteLk-1createdattheendofpass(k-1).

EachprocessorhastheidenticalLk-1thusgeneratesidenticalCkandputsitscountvaluesinacommonorderintoacountarrayPimakesapassoverdatapartitionDianddeveloplocalsupportcountsforcandidatesinCkPiexchangeslocalCkcountswithallotherprocessorstodevelopglobalCkcounts.Allprocessorsmustsynchronize.PicomputesLkfromCkPiindependentlydecidetoterminateorcontinuetothenextpass計數分布CD2023/7/1468計數分布CD2023/7/14史忠植關聯規則69Disadvantages:CDdoesnotexploittheaggregatememoryofthesystemMustsynchronizeanddevelopglobalcountattheendofeachpass

Mover[Ck]N*|M|NMover[Ck]|M|1UsageofmemoryperprocessorTotalamountofmemoryNumberofprocessor計數分布CD2023/7/1470Objective:

utilizeaggregatemainmemoryofthesystemeffectivelyTechnique:Partitionsthecandidatesintodisjointsets,whichareassignedtodifferentprocessors.Eachprocessorworkswiththeentiredatasetbutonlyportionofthecandidateset.

Eachprocessorcountsmutuallyexclusivecandidates.OnaN-processorconfiguration,DDcancountinasinglepasscandidatesetthatwouldrequireNpassinCD數據分布DD2023/7/14史忠植關聯規則71BasicIdeaCkCk1Ck2Lk1Lk2LkProcessor1Processor2Example:2processors

DataDistributiononlyprocessesasubsetofCktoutilizetheaggregatememory

ExchangedatatodevelopglobalcountsforCkidata數據分布DD2023/7/1472Algorithm:Pass1:SameastheCDalgorithmPassk>1:PigeneratesCkfromLk-1.Itretainsonly1/NoftheitemsetsformingCikPidevelopssupportcountsforitemsetsinCikforALLtransactions(usinglocaldatapagesanddatapagesreceivedfromotherprocessors)Attheendofthedatapass,PicalculatesLikusinglocalCikProcessorsexchangeLiksothateveryprocessorhasthecompleteLkforgeneratingCk+1forthenextpass(requiresprocessorstosynchronize)Picanindependentlydecidewhethertoterminateorcontinueontothenextpass數據分布DD2023/7/14史忠植關聯規則73Lik

Lik

Lik

Lk

數據分布DD2023/7/1474Disadvantages:

heavycommunicationEachprocessormustbroadcasttheirlocaldataandfrequentitemsetstoallotherprocessorsandsynchronizeineverypass.數據分布DD2023/7/14史忠植關聯規則75Problem: CDandDDrequireprocessorstosynchronizeattheendofeachpassBasicIdea:RemovedependenceamongprocessorsDatadependenceCompletetransactionsarerequiredtocomputesupportcount(inCD)FrequentitemsetsdependencyAglobalitemsetLkisneededduringthepruningstepofApioricandidategenerationalgorithm(inDD)候選分布CaD2023/7/1476RemoveDataDependencyEachprocessorPiworksonCki,adisjointsubsetofCkPiderivesglobalsupportcountsforCki

fromlocaldata.ReplicatedataamongstprocessorsinordertoachievetheaboveReduceFrequentitemsetdependencyDoesnotwaitforthecompletepruninginformationtoarrivefromotherprocessors.PrunethecandidatesetasmuchaspossibleLatearrivingpruninginformationisusedinsubsequentpasses.候選分布CaD2023/7/14史忠植關聯規則77Algorithm:Passk<l:UseeithertheCDorDDalgorithmPassk=l:PartitionLk-1amongNprocessorsPigeneratesCiklogicallyusingonlytheLik-1partition(usestandardpruning)PidevelopsglobalcountsforcandidatesinCikandthedatabaseisrepartitionedintoDRiatthesametime(requirescommunicatinglocaldata)PireceiveLjkfromallotherprocessorsneededforpruningCik+1PicomputesLikfromCikandasynchronouslysendittotheotherN-1processorsPassk>l:PicollectsallfrequentitemsetssentbyotherprocessorsPigeneratesCikusinglocalLik-,,takecareofpruning(Ljl-1)PipassesoverDRiandcountsCikPicomputesLikfromCikandasynchronouslysendittotheotherN-1processors候選分布CaD2023/7/1478CountDistribution

attemptstominimizecommunicationbyreplicatingthecandidatesetsineachprocessor’smemoryDataDistribution

maximizestheuseofaggregatememorybyallowingeachprocessorworkswiththeentiredatasetbutonlyportionofthecandidatesetCandidateDistributioneliminatesthesynchronizationcostsattheendofeverypass,maximizestheuseofaggregatememorywhilelimitingheavycommunicationtoasingleredistributionpass并行關聯算法比較2023/7/14史忠植關聯規則79并行關聯算法比較2023/7/1480AdvantagesDisadvantagesCountDistribution(CD)LowcommunicationcostOnlyexchangecounts,notdataDoesn’texploitaggregatememoryMustsynchronizeattheendofeverypassWhenthecandidateitemsetsdoesn’tfitthememoryofeachnode?DataDistribution(DD)BetterutilizationofaggregatesystemmemoryNeedtobroadcastitslocaldatatoeveryotherprocessorateverypassNeedtosynchronizeCandidateDistribution(CaD)ProcessorscanproceedindependentlywithoutsynchronizingattheendofeverypassCommunicationofentiredatasetneededforasingleredistributionpass.Thecommunicationcostishigherthanthesynchronizationcostsavings并行關聯算法比較2023/7/14史忠植關聯規則812023/7/14史忠植關聯規則82關聯規則可視化:方格圖(PaneGraph)2023/7/14史忠植關聯規則83關聯規則可視化:規則圖(RuleGraph)2023/7/14史忠植關聯規則84內容提要

引言Apriori算法FP-growth算法并行關聯規則挖掘多維關聯規則挖掘相關規則關聯規則改進總結2023/7/1485挖掘多種規則或規律多層(Multi-level),量化(quantitative)關聯規則,相關(correlation)和因果(causality),比率(ratio)規則,序列(sequential)模式,浮現(emerging)模式,temporalassociations,局部周期(partialperiodicity)分類(classification),聚類(clustering),冰山立方體(icebergcubes),等等.2023/7/1486多層關聯規則項常常構成層次可伸縮的(flexible)支持度設置:在較低層的項預期有較低的支持度.事務數據庫可以基于維度和層次編碼探尋共享多層挖掘統一支持度Milk[support=10%]2%Milk[support=6%]SkimMilk[support=4%]Level1min_sup=5%Level2min_sup=5%Level1min_sup=5%Level2min_sup=3%減少的支持度2023/7/1487可伸縮的支持度約束的多層/多維(ML/MD)關聯規則為什么設置可伸縮的支持度?實際生活中項的出現頻率變化巨大在一個商店購物籃中的鉆石,手表,鋼筆統一的支持度未必是一個有趣的模型一個可伸縮模型較低層的,較多維的組合以及長模式通常具有較小的支持度總體規則應該要容易說明和理解特殊的項和特殊的項的組合可以特別設定(最小支持度)以及擁有更高的優先級2023/7/14史忠植關聯規則88多維關聯規則單維規則:buys(X,“milk”)buys(X,“bread”)多維規則:

2個維度或謂詞(predicates)跨維度(Inter-dimension)關聯規則(無重復謂詞)age(X,”19-25”)occupation(X,“student”)buys(X,“coke”)混合維度(hybrid-dimension)關聯規則(重復謂詞)age(X,”19-25”)buys(X,“popcorn”)buys(X,“coke”)分類(Categorical)屬性有限的幾個可能值,值之間不可排序數量(Quantitative)屬性數值的,值之間有固有的排序2023/7/14史忠植關聯規則89多層關聯規則:冗余濾除根據項之間的”先輩”(ancestor)關系,一些規則可能是冗余的.示例milkwheatbread[support=8%,confidence=70%]2%milkwheatbread[support=2%,confidence=72%]我們說第1個規則是第2個規則的先輩.一個規則是冗余的,當其支持度接近基于先輩規則的”預期”(expected)值.2023/7/14史忠植關聯規則90多層關聯規則:逐步深化(ProgressiveDeepening)一個自上而下的,逐步深化的方法:

首先挖掘高層的頻繁項:milk(15%),bread(10%)

然后挖掘它們的較低層”較弱”(weaker)頻繁項:2%milk(5%),wheatbread(4%)多層之間不同的最小支持度閾值導致了不同的算法:如果在多個層次間采用了相同的最小支持度,若t的任何一個先輩都是非頻繁的則扔棄(toss)t.如果在較低層采用了減少的最小支持度，則只檢驗那些先輩的支持度是頻繁的／不可忽略的派生（descendents）即可．2023/7/1491多維關聯規則挖掘的技術搜索頻繁k-謂詞集(predicateset):示例:{age,occupation,buys}是一個3-謂詞集以age處理的方式,技術可以如下分類1.利用數量屬性的統計離散(staticdiscretization)方法利用預先確定的概念層次對數量屬性進行統計離散化2.量化關聯規則基于數據的分布,數量屬性被動態地離散化到不同的容器空間(bins)3.基于距離(Distance-based)的關聯規則這是一個動態離散化的過程,該過程考慮數據點之間的距離2023/7/14史忠植關聯規則92數量屬性的統計離散化挖掘之前利用概念層次離散化數值被范圍(ranges)替代.關系數據庫中,找出所有的頻繁k-謂詞(predicate)集要求

k

或k+1次表掃描.數據立方體(datacube)非常適合數據挖掘.N-維立方體的cells與謂詞集(

predicatesets)相對應.通過數據立方體挖掘會非常快速.(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)2023/7/14史忠植關聯規則93量化關聯規則age(X,”30-34”)income(X,”24K-48K”)buys(X,”highresolutionTV”)數值屬性動態離散化這樣挖掘的規則的可信度或緊密度最大化2-維量化關聯規則:Aquan1

Aquan2Acat示例2023/7/14史忠植關聯規則94MiningDistance-basedAssociationRulesBinningmethodsdonotcapturethesemanticsofintervaldataDistance-basedpartitioning,moremeaningfuldiscretizationconsidering:density/numberofpointsinaninterval“closeness”ofpointsinaninterval2023/7/14史忠植關聯規則95InterestingnessMeasure:Correlations(Lift)playbasketball

eatcereal[40%,66.7%]ismisleadingTheoverallpercentageofstudentseatingcerealis75%whichishigherthan66.7%.playbasketball

noteatcereal[20%,33.3%]ismoreaccurate,althoughwithlowersupportandconfidenceMeasureofdependent/correlatedevents:liftBasketballNotbasketballSum(row)Cereal200017503750Notcereal10002501250Sum(col.)3000200050002023/7/1496內容提要

引言Apriori算法FP-growth算法并行關聯規則挖掘多維關聯規則挖掘相關規則關聯規則改進總結2023/7/1497相關規則(CorrelationRules)“BeyondMarketBaskets,”Brinetal.假設執行關聯規則挖掘ccrowt20525t70575col9010100tea=>coffee20%support80%confidencebut90%ofthepeoplebuycoffeeanyway!2023/7/1498相關規則一種度量是計算相關性若兩個隨機變量A和B是統計獨立的對tea和coffee:2023/7/1499相關規則利用2

統計檢驗來測試獨立性設n為購物籃的總數設k為考慮的項的總數設r為一個包含項(ij,ij)的規則設O(r)表示包含規則r的購物籃的數量(即頻率)對單個項ij,設E[ij]=O(ij)(反過來即為n-E[ij])E[r]=n*E[r1]/n*…*E[rk]/n2023/7/14100相關規則2

統計量定義為LookupforsignificancevalueinastatisticaltextbookTherearek-1degreesoffreedomIftestfailscannotrejectindependence,otherwisecontigencytablerepresentsdependence.2023/7/14101示例BacktoteaandcoffeeE[t]=25,E[t]=75,E[c]=90,E[c]=10E[tc]=100*25/100*90/100=22.5O(tc)=20Contrib.to2=(20-22.5)2/22.5=0.278Calculatefortheresttoget2=2.204Notsignificantat95%level(3.84fork=2)Cannotrejectindependenceassumptionccrowt20525t

70575col90101002023/7/14史忠植關聯規則102興趣度（Interest）If2testshowssignificance,thenwanttofindmostinterestingcell(s)intableI(r)=O(r)/E[r]Lookforvaluesfarawayfrom1I(tc)=20/22.5=0.89I(tc)=5/2.5=2I(tc)=70/67.5=1.04I(tc)=5/7.5=0.662023/7/141032

統計量的性質上封閉性(Upwardclosed)若一個k-項集是相關的,則其所有的超集也是相關的.尋找最小的相關的項集沒有子集是相關的能否將a-prioriand2

統計量有效地結合Nogenerateandpruneasinsupport-confidence2023/7/14史忠植關聯規則104其它度量(Measures)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3作用度(Lift)度量項之間的相關性,但沒有檢驗2023/7/14105其它度量(Measures)可信度(Conviction)度量一個規則的強度TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I32023/7/14106內容提要

引言Apriori算法FP-growth算法并行關聯規則挖掘多維關聯規則挖掘相關規則關聯規則改進總結2023/7/14史忠植關聯規則107關聯規則改進Lin等人提出解決規則挖掘算法中的數據傾斜問題，從而使算法具有較好的均衡性。Park等人提出把哈希表結構用于關聯規則挖掘。Agrawal首先提出事務縮減技術，Han和Park等人也分別在減小數據規模上做了一些工作。抽樣的方法是由Toivonen提出的。Brin等人采用動態項集計數方法求解頻繁項集。Aggarwal提出用圖論和格的理論求解頻繁項集的方法。Prutax算法就是用格遍歷的辦法求解頻繁項集。2023/7/14108關聯規則改進關聯規則模型有很多擴展，如順序模型挖掘，在順序時間段上進行挖掘等。還有挖掘空間關聯規則，挖掘周期性關聯規則，挖掘負關聯規則，挖掘交易內部關聯規則等。Guralnik提出順序時間段問題的形式描述語言，以便描述用戶感興趣的時間段，并且構建了有效的數據結構SP樹（順序模式樹）和自底向上的數據挖掘算法。最大模式挖掘是Bayardo等人提出來的。2023/7/14史忠植關聯規則109關聯規則改進隨后人們開始探討頻率接近項集。Pei給出了一種有效的數據挖掘算法。B.?zden等人的周期性關聯規則是針對具有時間屬性的事務數據庫，發現在規律性的時間間隔中滿足最小支持度和信任度的規則。貝爾實驗室的S.Ramaswamy等人進一步發展了周期性關聯規則，提出挖掘符合日歷的關聯規則（CalendricAssociationRules）算法，用以進行市場貨籃分析。2023/7/14110關聯規則改進T.Hannu等人把負邊界引入規則發現算法中，每次挖掘不僅保存頻繁項集，而且同時保存負邊界，達到下次挖掘時減少掃描次數的目的。Srikant等人通過研究關聯規則的上下文，提出規則興趣度尺度用以剔除冗余規則。Zakia還用項集聚類技術求解最大的近似潛在頻繁項集，然后用格遷移思想生成每個聚類中的頻繁項集。CAR，也叫分類關聯規則，是Lin等人提出的一