11數據倉庫與數據挖掘

第6章挖掘頻繁模式、關聯和相關性李成安華南理工大學經濟與貿易學院?201304February2023DataMining:ConceptsandTechniques23第6章:挖掘頻繁模式、關聯和相關性:基本概念和方法基本概念頻繁模式挖掘方法

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

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

c,

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

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

ofX:項集X出現的頻數(相對)

支持度,s,X(如一個交易包含X的概率)出現的百分數項集X是頻繁的，如果X的支持度不小于最小支持度

閾值。CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerTidItemsbought10Beer,Nuts,Diaper20Beer,Coffee,Diaper30Beer,Diaper,Eggs40Nuts,Eggs,Milk50Nuts,Coffee,Diaper,Eggs,Milk11基本概念:關聯規則發現所有規則XY

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

Y的條件概率設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關聯規則:(manymore!)BeerDiaper(60%,100%)DiaperBeer(60%,75%)12閉合模式和最大模式長模式包含組合數量的子模式，即，{a1,…,a100}包含(1001)+(1002)+…+(110000)=2100–1=1.27*1030子模式!解決方法:挖掘閉合模式和最大模式項集X

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

Y?X,有

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

種產品選購一種產品的機會為10-4選購特定10種產品的機會:~10-40一個特定10種產品在109交易中出現103次的機會是多少？

15第6章:挖掘頻繁模式、關聯和相關性:基本概念和方法基本概念頻繁模式挖掘方法

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

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

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

for數據庫中每個交易

tdo

增加Ck+1

中包含在t的候選項集的計數

Lk+1=Ck+1

的候選集withmin_support

endreturn

k

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

的項集被按序排列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如何計算候選集的支持度?為什么計數支持度是一個問題?候選集的數量非常大一條交易可能包含很多候選項集方法:Candidateitemsetsarestoredinahash-treeLeafnodeofhash-treecontainsalistofitemsetsandcountsInteriornodecontainsahashtable23

Apriori算法足夠的快嗎?

—瓶頸問題的產生2023/2/4數據挖掘：概念和技術24提高Apriori效率的方法1.基于Hash的項集計數:若

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

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

對每個條件模式庫累計每個項的計數構建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有一個共享的前綴路徑P挖掘分成兩部分單個前綴路徑約簡為一個節點連接兩個部分的挖掘結果a2:n2a3:n3a1:n1{}b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1{}r1=32FP樹結構的優勢完整

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

對每個頻繁項,建立條件模式庫和條件FP樹對每一個新建立的條件FP樹重復該過程直到導出的FP樹為空，或者僅包含單路徑。單路徑將生成其子路徑的所有組合，其中每一個都是頻繁模式34通過數據庫投影伸縮FP增長如果FP樹不能置于內存，怎么辦?數據庫投影首先將數據庫劃分成一個投影數據庫的集合然后，在每個投影數據庫上建立和挖掘FP樹并行投影vs.劃分投影技術并行投影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模式增長方法的優勢分而治之:DecomposeboththeminingtaskandDBaccordingtothefrequentpatternsobtainedsofarLeadtofocusedsearchofsmallerdatabases其他因素Nocandidategeneration,nocandidatetestCompresseddatabase:FP-treestructureNorepeatedscanofentiredatabaseBasicops:countinglocalfreqitemsandbuildingsubFP-tree,nopatternsearchandmatchingAgoodopen-sourceimplementationandrefinementofFPGrowthFPGrowth+(GrahneandJ.Zhu,FIMI'03)39挖掘方法的進一步改進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頻繁模式挖掘方法的擴展挖掘閉合模式和最大模式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伸縮性頻繁項集挖掘方法Apriori:ACandidateGeneration-and-TestApproachImprovingtheEfficiencyofAprioriFPGrowth:AFrequentPattern-GrowthApproachECLAT:FrequentPatternMiningwithVerticalDataFormatMiningCloseFrequentPatternsandMaxpatterns42ECLAT:使用垂直數據格式挖掘頻繁項集垂直模式:t(AB)={T11,T25,…}tid-list:listoftrans.-idscontaininganitemset基于垂直格式推導頻繁模式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:按支持度升序建立頻繁項集表Flist:d-a-f-e-c分解搜索空間PatternshavingdPatternshavingdbutnoa,etc.遞歸的挖掘頻繁閉合模式每一個有d的交易也有cfa

cfad

是一個頻繁閉合模式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章:挖掘頻繁模式、關聯和相關性:基本概念和方法基本概念頻繁模式挖掘方法

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

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

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

提升：一種興趣度的度量設A,B是兩個項集，P(A∪B)=P(B)*P(A),A和B是獨立事件A,B的相關性度量取值小于1，AandB負相關取值大于1，AandB正相關如：上例corr=0.89P(B|A)/P(B)稱為規則A=>B的“提升”挖掘相關性關聯規則，X^2檢驗是否有統計意義52Areliftand2GoodMeasuresofCorrelation?“Buywalnutsbuymilk[1%,80%]”ismisleadingif85%ofcustomersbuymilkSupportandconfidencearenotgoodtoindicatecorrelationsOver20interestingnessmeasureshavebeenproposed(seeTan,Kumar,Sritastava@KDD’02)Whicharegoodones?53Null-InvariantMeasures04February2023DataMining:ConceptsandTechniques54興趣度指標的比較MilkNoMilkSum(row)Coffeem,c~m,ccNoCoffeem,~c~m,~c~cSum(col.)m~m零不變性(transaction)對相關分析是關鍵的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哪一個零不變性指標更好?IR(不平衡比):評估規則蘊含式中兩個項集A和B的不平衡程度KulczynskiandImbalanceRatio(IR)togetherpresentaclearpictureforallthethreedatasetsD4throughD6D4isbalanced&neutralD5isimbalanced&neutralD6isveryimbalanced&neutral57第6章:挖掘頻繁模式、關聯和相關性:基本概念和方法基本概念頻繁模式挖掘方法

什么模式是有趣的?—模式評價方法小結58小結基本概念:關聯,支持度-置信度框架,閉合與最大模式可伸縮頻繁模式挖掘方法Apriori(Candidategeneration&test)基于投影的方法(FPgrowth,CLOSET+,...)垂直數據格式(ECLAT,CHARM,...)什么模式是有趣的?模式評估方法59Ref:BasicConceptsofFrequentPatternMining(關聯規則)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