Chapter 6. 挖掘頻繁模式、關(guān)聯(lián)與相關(guān)

11數(shù)據(jù)倉庫與數(shù)據(jù)挖掘

第6章挖掘頻繁模式、關(guān)聯(lián)和相關(guān)性李成安華南理工大學(xué)經(jīng)濟(jì)與貿(mào)易學(xué)院?201304February2023DataMining:ConceptsandTechniques23第6章:挖掘頻繁模式、關(guān)聯(lián)和相關(guān)性:基本概念和方法基本概念頻繁模式挖掘方法

什么模式是有趣的?—模式評價(jià)方法小結(jié)4什么是頻繁模式挖掘?頻繁模式:頻繁出現(xiàn)在數(shù)據(jù)集中的模式(如項(xiàng)集、子序列或子結(jié)構(gòu))首先由Agrawal,Imielinski,andSwami[AIS93]提出頻繁模式和關(guān)聯(lián)規(guī)則挖掘動機(jī):發(fā)現(xiàn)數(shù)據(jù)中內(nèi)在的規(guī)則什么產(chǎn)品經(jīng)常被一起購買?—啤酒和尿布?!買PC后接下來會買什么?哪種DNA對這種新藥敏感?我們可自動分類web文檔嗎?應(yīng)用購物籃數(shù)據(jù)分析,交叉銷售,顧客購買習(xí)慣分析,Web日志(clickstream)分析,和DNA序列分析等.5為什么頻繁模式挖掘是重要的?頻繁模式:數(shù)據(jù)集內(nèi)在的和重要的特性是許多數(shù)據(jù)挖掘任務(wù)的基礎(chǔ)關(guān)聯(lián),相關(guān)性,和因果性分析序列,結(jié)構(gòu)(如子圖)模式空間時(shí)間、多媒體、時(shí)間序列和流數(shù)據(jù)的模式分析分類:判別,頻繁模式分析聚類分析:基于頻繁模式的聚類數(shù)據(jù)倉庫:立方體和立方體梯度(cube-gradient)語義數(shù)據(jù)壓縮:分冊廣泛的應(yīng)用6關(guān)聯(lián)規(guī)則挖掘形式化定義給定：設(shè)I={i1,i2,…,im}是項(xiàng)(item)的集合。若干項(xiàng)的集合，稱為項(xiàng)集（ItemSets）記D為交易(transaction)T(或事務(wù))的集合，這里交易T是項(xiàng)的集合，并且T?I。對應(yīng)每一個(gè)交易有唯一的標(biāo)識，如交易號，記作TID。設(shè)X是一個(gè)I中項(xiàng)的集合，如果X?T，那么稱交易T包含X。尋找：有趣的關(guān)聯(lián)規(guī)則(強(qiáng)規(guī)則).7關(guān)聯(lián)規(guī)則所有形如X?Y蘊(yùn)涵式的稱為關(guān)聯(lián)規(guī)則，這里X?I,Y?I，并且X∩Y=Φ。關(guān)聯(lián)規(guī)則是有趣的,如果它滿足最小支持度閾值與最小置信度閾值,并稱之為強(qiáng)規(guī)則8置信度與支持度項(xiàng)集X={i1,…,ik}找出所有具有最小置信度和支持度的關(guān)聯(lián)規(guī)則X?Y買尿片的顧客兩者都買的顧客買啤酒的顧客支持度,s,一個(gè)事務(wù)中包含XY的可能性

support(X?Y)=同時(shí)包含項(xiàng)目集X和Y的交易數(shù)/總交易數(shù)用于描述有用性.置信度

c,

一個(gè)事務(wù)中包含X也包含Y的條件概率.confidence(X?Y)=同時(shí)購買商品X和Y的交易數(shù)/購買商品X的交易數(shù)用于描述確定性,即”值得信賴的程度””可靠性”9關(guān)聯(lián)規(guī)則的基本形式關(guān)聯(lián)規(guī)則的基本形式：

前提條件?結(jié)論[支持度,置信度]buys(x,“diapers”)?buys(x,“beers”)[0.5%,60%]major(x,“CS”)takes(x,“DB”)?grade(x,“A”)[1%,75%]包含k個(gè)項(xiàng)目的集合，稱為k-項(xiàng)集項(xiàng)集的出現(xiàn)頻率是包含項(xiàng)集的事務(wù)個(gè)數(shù)，稱為項(xiàng)集的頻率、支持計(jì)數(shù)或者計(jì)數(shù)10基本概念:頻繁模式項(xiàng)集:項(xiàng)的集合k-項(xiàng)集X={x1,…,xk}(絕對)支持度,or,支持計(jì)數(shù)

ofX:項(xiàng)集X出現(xiàn)的頻數(shù)(相對)

支持度,s,X(如一個(gè)交易包含X的概率)出現(xiàn)的百分?jǐn)?shù)項(xiàng)集X是頻繁的，如果X的支持度不小于最小支持度

閾值。CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerTidItemsbought10Beer,Nuts,Diaper20Beer,Coffee,Diaper30Beer,Diaper,Eggs40Nuts,Eggs,Milk50Nuts,Coffee,Diaper,Eggs,Milk11基本概念:關(guān)聯(lián)規(guī)則發(fā)現(xiàn)所有規(guī)則XY

with最小支持度和置信度支持度,s，一個(gè)交易包含XY的概率置信度,c，一個(gè)包含X的交易也包含

Y的條件概率設(shè)minsup=50%,minconf=50%頻繁模式:Beer:3,Nuts:3,Diaper:4,Eggs:3,{Beer,Diaper}:3CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerNuts,Eggs,Milk40Nuts,Coffee,Diaper,Eggs,Milk50Beer,Diaper,Eggs30Beer,Coffee,Diaper20Beer,Nuts,Diaper10ItemsboughtTid關(guān)聯(lián)規(guī)則:(manymore!)BeerDiaper(60%,100%)DiaperBeer(60%,75%)12閉合模式和最大模式長模式包含組合數(shù)量的子模式，即，{a1,…,a100}包含(1001)+(1002)+…+(110000)=2100–1=1.27*1030子模式!解決方法:挖掘閉合模式和最大模式項(xiàng)集X

是閉合的如果X是頻繁的，且不存在超模式

Y?X,有

X同樣的支持度(proposedbyPasquier,etal.@ICDT’99)項(xiàng)集X是最大模式，如果X是頻繁的，且不存在超頻繁模式Y(jié)?X(proposedbyBayardo@SIGMOD’98)閉合模式是頻繁模式的無損壓縮減少模式和規(guī)則的數(shù)量13閉合模式和最大模式例子.DB={<a1,…,a100>,<a1,…,a50>}Min_sup=1.閉合模式集是什么?<a1,…,a100>:1<a1,…,a50>:2最大模式集是什么?<a1,…,a100>:1所有模式集是什么?!!14頻繁模式挖掘的計(jì)算復(fù)雜度在極端情況可能生成多少頻繁項(xiàng)集?頻繁項(xiàng)集的數(shù)量與最小支持度閾值有關(guān)當(dāng)minsup很小時(shí),頻繁項(xiàng)集的數(shù)量指數(shù)性增長最糟糕的情形:MNwhereM:#distinctitems,andN:maxlengthoftransactions極端情形的復(fù)雜度與期望概率例.假設(shè)Walmart有104

種產(chǎn)品選購一種產(chǎn)品的機(jī)會為10-4選購特定10種產(chǎn)品的機(jī)會:~10-40一個(gè)特定10種產(chǎn)品在109交易中出現(xiàn)103次的機(jī)會是多少？

15第6章:挖掘頻繁模式、關(guān)聯(lián)和相關(guān)性:基本概念和方法基本概念頻繁模式挖掘方法

什么模式是有趣的?—模式評價(jià)方法小結(jié)16Apriori方法頻繁項(xiàng)集的定義如果項(xiàng)集滿足最小支持度，則稱之為頻繁項(xiàng)集（高頻項(xiàng)集）頻繁項(xiàng)集的基本特征任何頻繁項(xiàng)集的非空子集均為頻繁項(xiàng)集。例如：ABC是頻繁項(xiàng)集，則AB、AC、BC均為頻繁項(xiàng)集。反之：如AB不是頻繁項(xiàng)集，則ABC不可能是頻繁項(xiàng)集17Apriori方法是一種稱作逐層搜索的迭代方法。用k-項(xiàng)集探求（k+1）-項(xiàng)集。具體地：首先找出頻繁1-項(xiàng)集，該集合記為L1;用L1找出頻繁2-項(xiàng)集的集合L2；如此繼續(xù)下去，直到找到最大頻繁項(xiàng)集該方法，主要有連接和剪枝兩步構(gòu)成。18Apriori算法－例子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}219Apriori算法偽代碼:Ck:大小為k的候選集Lk:大小為k的頻繁項(xiàng)集L1={頻繁項(xiàng)集};for

(k=1;Lk!=;k++)dobegin

Ck+1=從Lk生成的候選集

for數(shù)據(jù)庫中每個(gè)交易

tdo

增加Ck+1

中包含在t的候選項(xiàng)集的計(jì)數(shù)

Lk+1=Ck+1

的候選集withmin_support

endreturn

k

Lk;20Apriori的重要細(xì)節(jié)如何生成候選集?Step1:self-joiningLkStep2:pruning如何計(jì)算候選集的支持度?候選集生成例子L3={abc,abd,acd,ace,bcd}連接步:L3*L3abcdfromabcandabdacdefromacdandace修剪:acdeisremovedbecauseadeisnotinL3C4={abcd}21如何生成候選集?假定Lk-1

的項(xiàng)集被按序排列Step1:連接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-1Step2:修剪forallitemsetscinCk

doforall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk22如何計(jì)算候選集的支持度?為什么計(jì)數(shù)支持度是一個(gè)問題?候選集的數(shù)量非常大一條交易可能包含很多候選項(xiàng)集方法:Candidateitemsetsarestoredinahash-treeLeafnodeofhash-treecontainsalistofitemsetsandcountsInteriornodecontainsahashtable23

Apriori算法足夠的快嗎?

—瓶頸問題的產(chǎn)生2023/2/4數(shù)據(jù)挖掘：概念和技術(shù)24提高Apriori效率的方法1.基于Hash的項(xiàng)集計(jì)數(shù):若

k-項(xiàng)集在hash-tree的路徑上的一個(gè)計(jì)數(shù)值低于閾值，那他本身也不可能是頻繁的。(157頁圖5-6)2.減少交易記錄:不包含任何頻繁k-項(xiàng)集的交易也不可能包含任何大于k的頻繁集，下一步計(jì)算時(shí)刪除這些記錄。3.劃分:

一個(gè)項(xiàng)集要想在整個(gè)數(shù)據(jù)庫中是頻繁的，那么他至少在數(shù)據(jù)庫的一個(gè)分割上是頻繁的。兩次掃描數(shù)據(jù)。(157頁圖5-6)4.抽樣:使用小的支持度+完整性驗(yàn)證方法。在小的抽樣集上找到局部頻繁項(xiàng)集，然后在全部數(shù)據(jù)集找頻繁項(xiàng)集。5.動態(tài)項(xiàng)集計(jì)數(shù):在添加一個(gè)新的候選集之前，先估計(jì)一下是不是他的所有子集都是頻繁的。25挖掘頻繁模式項(xiàng)集的模式增長方法Apriori方法的瓶頸寬度(i.e.,level-wise)優(yōu)先搜索候選集生產(chǎn)與測試經(jīng)常產(chǎn)生巨大數(shù)量的候選集頻繁模式增長方法(J.Han,J.Pei,andY.Yin,SIGMOD’00)深度優(yōu)先搜索避免顯式的候選集生成主要思想:僅僅用局部頻繁項(xiàng)從短項(xiàng)中生成長項(xiàng)“abc”是頻繁模式得到所有包含“abc”的交易,如,projectDBonabc:DB|abc“d”是局部頻繁項(xiàng)inDB|abcabcd是頻繁項(xiàng)26從交易數(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}第一次掃描數(shù)據(jù)庫,發(fā)現(xiàn)頻繁1-項(xiàng)集按降序排列頻繁項(xiàng)f-list第二次掃描數(shù)據(jù)庫，構(gòu)建FP-樹F-list=f-c-a-b-m-p27劃分模式與數(shù)據(jù)庫頻繁模式被劃分成子集，根據(jù)f-listF-list=f-c-a-b-m-p包含p的模式包含m但不包含p的模式…包含c但不包含a,b,m,p的模式模式f完整但不冗余28從P-條件數(shù)據(jù)庫中發(fā)現(xiàn)包含P的模式從FP數(shù)據(jù)的頻繁項(xiàng)頭表開始跟蹤每個(gè)頻繁項(xiàng)P的連接，遍歷FP樹TraversetheFP-treebyfollowingthelinkofeachfrequentitemp累積項(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 329從條件模式庫到條件FP樹

對每個(gè)條件模式庫累計(jì)每個(gè)項(xiàng)的計(jì)數(shù)構(gòu)建FP-treeforthefrequentitemsofthepatternbasem-conditionalpatternbase:fca:2,fcab:1{}f:3c:3a:3m-conditionalFP-treeAllfrequentpatternsrelatetomm,fm,cm,am,fcm,fam,cam,fcam{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1HeaderTableItemfrequencyheadf 4c 4a 3b 3m 3p 330遞歸:挖掘所有條件FP樹{}f:3c:3a:3m-conditionalFP-treeCond.patternbaseof“am”:(fc:3){}f:3c:3am-conditionalFP-treeCond.patternbaseof“cm”:(f:3){}f:3cm-conditionalFP-treeCond.patternbaseof“cam”:(f:3){}f:3cam-conditionalFP-tree31特例:FP樹的單路徑假定(條件)FP-treeT有一個(gè)共享的前綴路徑P挖掘分成兩部分單個(gè)前綴路徑約簡為一個(gè)節(jié)點(diǎn)連接兩個(gè)部分的挖掘結(jié)果a2:n2a3:n3a1:n1{}b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1{}r1=32FP樹結(jié)構(gòu)的優(yōu)勢完整

保留了頻繁模式挖掘的完整信息不破壞任何交易的長模式簡潔壓縮不相關(guān)的非頻繁項(xiàng)降序的項(xiàng)不比原始數(shù)據(jù)庫更長33頻繁模式增長樹挖掘方法思想:頻繁模式增長通過模式和數(shù)據(jù)庫劃分遞歸的增長頻繁模式方法

對每個(gè)頻繁項(xiàng),建立條件模式庫和條件FP樹對每一個(gè)新建立的條件FP樹重復(fù)該過程直到導(dǎo)出的FP樹為空，或者僅包含單路徑。單路徑將生成其子路徑的所有組合，其中每一個(gè)都是頻繁模式34通過數(shù)據(jù)庫投影伸縮FP增長如果FP樹不能置于內(nèi)存，怎么辦?數(shù)據(jù)庫投影首先將數(shù)據(jù)庫劃分成一個(gè)投影數(shù)據(jù)庫的集合然后，在每個(gè)投影數(shù)據(jù)庫上建立和挖掘FP樹并行投影vs.劃分投影技術(shù)并行投影ProjecttheDBinparallelforeachfrequentitemParallelprojectionisspacecostlyAllthepartitionscanbeprocessedinparallel劃分投影PartitiontheDBbasedontheorderedfrequentitemsPassingtheunprocessedpartstothesubsequentpartitions35劃分投影ParallelprojectionneedsalotofdiskspacePartitionprojectionsavesitTran.DBfcampfcabmfbcbpfcampp-projDBfcamcbfcamm-projDBfcabfcafcab-projDBfcb…a-projDBfc…c-projDBf…f-projDB…am-projDBfcfcfccm-projDBfff…36FP-Growthvs.Apriori:基于支持度閾值的伸縮性DatasetT25I20D10KDataMining:ConceptsandTechniques37FP-Growthvs.Tree-Projection:基于支持度閾值的伸縮性DatasetT25I20D100K38模式增長方法的優(yōu)勢分而治之:DecomposeboththeminingtaskandDBaccordingtothefrequentpatternsobtainedsofarLeadtofocusedsearchofsmallerdatabases其他因素Nocandidategeneration,nocandidatetestCompresseddatabase:FP-treestructureNorepeatedscanofentiredatabaseBasicops:countinglocalfreqitemsandbuildingsubFP-tree,nopatternsearchandmatchingAgoodopen-sourceimplementationandrefinementofFPGrowthFPGrowth+(GrahneandJ.Zhu,FIMI'03)39挖掘方法的進(jìn)一步改進(jìn)AFOPT(Liu,etal.@KDD’03)A“push-right”methodforminingcondensedfrequentpattern(CFP)treeCarpenter(Pan,etal.@KDD’03)MinedatasetswithsmallrowsbutnumerouscolumnsConstructarow-enumerationtreeforefficientminingFPgrowth+(GrahneandZhu,FIMI’03)EfficientlyUsingPrefix-TreesinMiningFrequentItemsets,Proc.ICDM'03Int.WorkshoponFrequentItemsetMiningImplementations(FIMI'03),Melbourne,FL,Nov.2003TD-Close(Liu,etal,SDM’06)40頻繁模式挖掘方法的擴(kuò)展挖掘閉合模式和最大模式CLOSET(DMKD’00),FPclose,andFPMax(Grahne&Zhu,Fimi’03)挖掘序列模式PrefixSpan(ICDE’01),CloSpan(SDM’03),BIDE(ICDE’04)挖掘圖模式gSpan(ICDM’02),CloseGraph(KDD’03)基于約束的頻繁模式挖掘Convertibleconstraints(ICDE’01),gPrune(PAKDD’03)基于模式增長的分類Miningfrequentanddiscriminativepatterns(Cheng,etal,ICDE’07)41伸縮性頻繁項(xiàng)集挖掘方法Apriori:ACandidateGeneration-and-TestApproachImprovingtheEfficiencyofAprioriFPGrowth:AFrequentPattern-GrowthApproachECLAT:FrequentPatternMiningwithVerticalDataFormatMiningCloseFrequentPatternsandMaxpatterns42ECLAT:使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集垂直模式:t(AB)={T11,T25,…}tid-list:listoftrans.-idscontaininganitemset基于垂直格式推導(dǎo)頻繁模式t(X)=t(Y):XandYalwayshappentogethert(X)t(Y):transactionhavingXalwayshasY用diffset

來加速挖掘Onlykeeptrackofdifferencesoftidst(X)={T1,T2,T3},t(XY)={T1,T3}Diffset(XY,X)={T2}Eclat(Zakietal.@KDD’97)MiningClosedpatternsusingverticalformat:CHARM(Zaki&Hsiao@SDM’02)挖掘頻繁閉合模式:CLOSETFlist:按支持度升序建立頻繁項(xiàng)集表Flist:d-a-f-e-c分解搜索空間PatternshavingdPatternshavingdbutnoa,etc.遞歸的挖掘頻繁閉合模式每一個(gè)有d的交易也有cfa

cfad

是一個(gè)頻繁閉合模式J.Pei,J.Han&R.Mao.“CLOSET:AnEfficientAlgorithmforMiningFrequentClosedItemsets",DMKD'00.TIDItems10a,c,d,e,f20a,b,e30c,e,f40a,c,d,f50c,e,fMin_sup=2MaxMiner:挖掘最大模式1stscan:findfrequentitemsA,B,C,D,E2ndscan:findsupportforAB,AC,AD,AE,ABCDEBC,BD,BE,BCDECD,CE,CDE,DESinceBCDEisamax-pattern,noneedtocheckBCD,BDE,CDEinlaterscanR.Bayardo.Efficientlymininglongpatternsfromdatabases.SIGMOD’98TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,FPotentialmax-patterns45VisualizationofAssociationRules:PlaneGraph46VisualizationofAssociationRules:RuleGraph47VisualizationofAssociationRules

(SGI/MineSet3.0)48第6章:挖掘頻繁模式、關(guān)聯(lián)和相關(guān)性:基本概念和方法基本概念頻繁模式挖掘方法

什么模式是有趣的?—模式評價(jià)方法小結(jié)49興趣度的度量客觀度量兩個(gè)最為流行的度量:

支持度和置信度（supportandconfidence）主觀度量(Silberschatz&Tuzhilin,KDD95)一個(gè)規(guī)則（模式）是感興趣的，如果沒有想到的(用戶感到驚訝的);可操作的(用戶在得到結(jié)果后，可以在此之上做些什么)50

支持度-置信度方法的不足Example1:(Aggarwal&Yu,PODS98)5000個(gè)學(xué)生中3000喜歡打籃球3750喜歡吃米飯2000同時(shí)喜歡打籃球和吃米飯關(guān)聯(lián)規(guī)則：playbasketball?eatcereal[40%,66.7%]該規(guī)則具有欺騙性，因?yàn)閺恼麄€(gè)學(xué)生情況來看，有75%的學(xué)生喜歡吃米飯，大大高于66.7%。關(guān)聯(lián)規(guī)則：playbasketball?noteatcereal[20%,33.3%]該規(guī)則雖然擁有較低的支持度和置信度，但是比較精確。BasketballNotbasketballSum(row)Cereal200017503750Notcereal10002501250Sum(col.)30002000500051

提升：一種興趣度的度量設(shè)A,B是兩個(gè)項(xiàng)集，P(A∪B)=P(B)*P(A),A和B是獨(dú)立事件A,B的相關(guān)性度量取值小于1，AandB負(fù)相關(guān)取值大于1，AandB正相關(guān)如：上例corr=0.89P(B|A)/P(B)稱為規(guī)則A=>B的“提升”挖掘相關(guān)性關(guān)聯(lián)規(guī)則，X^2檢驗(yàn)是否有統(tǒng)計(jì)意義52Areliftand2GoodMeasuresofCorrelation?“Buywalnutsbuymilk[1%,80%]”ismisleadingif85%ofcustomersbuymilkSupportandconfidencearenotgoodtoindicatecorrelationsOver20interestingnessmeasureshavebeenproposed(seeTan,Kumar,Sritastava@KDD’02)Whicharegoodones?53Null-InvariantMeasures04February2023DataMining:ConceptsandTechniques54興趣度指標(biāo)的比較MilkNoMilkSum(row)Coffeem,c~m,ccNoCoffeem,~c~m,~c~cSum(col.)m~m零不變性(transaction)對相關(guān)分析是關(guān)鍵的Liftand2

arenotnull-invariant5null-invariantmeasuresNull-transactionsw.r.t.mandcNull-invariantSubtle:TheydisagreeKulczynskimeasure(1927)55AnalysisofDBLPCoauthorRelationshipsAdvisor-adviseerelation:Kulc:high,coherence:low,cosine:middleRecentDBconferences,removingbalancedassociations,lowsup,etc.TianyiWu,YuguoChenandJiaweiHan,“AssociationMininginLargeDatabases:ARe-ExaminationofItsMeasures”,Proc.2007Int.Conf.PrinciplesandPracticeofKnowledgeDiscoveryinDatabases(PKDD'07),Sept.2007哪一個(gè)零不變性指標(biāo)更好?IR(不平衡比):評估規(guī)則蘊(yùn)含式中兩個(gè)項(xiàng)集A和B的不平衡程度KulczynskiandImbalanceRatio(IR)togetherpresentaclearpictureforallthethreedatasetsD4throughD6D4isbalanced&neutralD5isimbalanced&neutralD6isveryimbalanced&neutral57第6章:挖掘頻繁模式、關(guān)聯(lián)和相關(guān)性:基本概念和方法基本概念頻繁模式挖掘方法

什么模式是有趣的?—模式評價(jià)方法小結(jié)58小結(jié)基本概念:關(guān)聯(lián),支持度-置信度框架,閉合與最大模式可伸縮頻繁模式挖掘方法Apriori(Candidategeneration&test)基于投影的方法(FPgrowth,CLOSET+,...)垂直數(shù)據(jù)格式(ECLAT,CHARM,...)什么模式是有趣的?模式評估方法59Ref:BasicConceptsofFrequentPatternMining(關(guān)聯(lián)規(guī)則)R.Agrawal,T.Imielinski,andA.Swami.Miningassociationrulesbetweensetsofitemsinlargedatabases.SIGMOD'93.(最大模式)R.J.Bayardo.Efficientlymininglongpatternsfromdatabases.SIGMOD'98.(閉合模式)N.Pasquier,Y.Bastide,R.Taouil,andL.Lakhal.Discoveringfrequentcloseditemsetsforassociationrules.ICDT'99.(序列模式)R.AgrawalandR.Srikant.Miningsequentialpatterns.ICDE'9560Ref:AprioriandItsImprovementsR.AgrawalandR.Srikant.Fastalgorithmsforminingassociationrules.VLDB'94.H.Mannila,H.Toivonen,andA.I.Verkamo.Efficientalgorithmsfordiscoveringassociationrules.KDD'94.A.Savasere,E.Omiecinski,andS.Navathe.Anefficientalgorithmforminingassociationrulesinlargedatabases.VLDB'95.J.S.Park,M.S.Chen,andP.S.Yu.Aneffectivehash-basedalgorithmforminingassociationrules.SIGMOD'95.H.Toivonen.Samplinglargedatabasesforassociationrules.VLDB'96.S.Brin,R.Motwani,J.D.Ullman,andS.Tsur.Dynamicitemsetcountingandimplicationrulesformarketbasketanalysis.SIGMOD'97.S.Sarawagi,S.Thomas,andR.Agrawal.Integratingassociationruleminingwithrelationaldatabasesystems:Alternativesandimplications.SIGMOD'98.61Ref:Depth-First,Projection-BasedFPMiningR.Agarwal,C.Aggarwal,andV.V.V.Prasad.Atreeprojectionalgorithmforgenerationoffrequentitemsets.J.ParallelandDistributedComputing:02.J.Han,J.Pei,andY.Yin.Miningfrequentpatternswithoutcandidategeneration.SIGMOD’00.J.Liu,Y.Pan,K.Wang,andJ.Han.MiningFrequentItemSetsbyOpportunisticProjection.KDD'02.J.Han,J.Wang,Y.Lu,andP.Tzvetkov.MiningTop-KFrequentClosedPatternswithoutMinimumSupport.ICDM'02.J.Wang,J.Han,andJ.Pei.CLOSET+:SearchingfortheBestStrategiesforMiningFrequentClosedItemsets.KDD'03.G.Liu,H.Lu,W.Lou,J.X.Yu.OnComputing,StoringandQueryingFrequentPatterns.KDD'03.G.GrahneandJ.Zhu,EfficientlyUsingPrefix-TreesinMiningFrequentItemsets,Proc.ICDM'03Int.WorkshoponFrequentItemsetMiningImplementations(FIMI'03),Melbourne,FL,Nov.200362Ref:VerticalFormatandRowEnumerationMethodsM.J.Zaki,S.Parthasarathy,M.Ogihara,andW.Li.Parallelalgorithmfordiscoveryofassociationrules.DAMI:97.ZakiandHsiao.CHARM:AnEfficientAlgorithmforClosedItemsetMining,SDM'02.C.Bucila,J.Gehrke,D.Kifer,andW.White.DualMiner:ADual-PruningAlgorithmforItemsetswithConstraints.KDD’02.F.Pan,G.Cong,A.K.H.Tung,J.Yang,andM.Zaki,CARPENTER:FindingClosedPatternsinLongBiologicalDatasets.KDD'03.H.Liu,J.Han,D.Xin,andZ.Shao,MiningInterestingPatternsfromVeryHighDimensionalData:ATop-DownRowEnumerationApproach,SDM'06.63Ref:MiningCorrelationsandInterestingRulesM.Klemettinen,H.Mannila,P.Ronkainen,H.Toivonen,andA.I.Verkamo.Findinginterestingrulesfromlargesetsofdiscoveredassociationrules.CIKM'94.S.Brin,R.Motwani,andC.Silverstein.Bey