錄屏2022上半年dbms原理與設(shè)計(jì)課件1frequent pattern

關(guān)聯(lián)規(guī)則Miningvariouskindsofassociationrules本講內(nèi)容MiningVariousKindsofAssociationRulesMiningmulti-levelassociationMimingmulti-dimensionalassociationMiningquantitativeassociationMininginterestingcorrelationpatternsMulti-levelARmining

在多維空間中，由于數(shù)據(jù)通常比較稀疏，很難在較低概念層發(fā)現(xiàn)有用的關(guān)聯(lián)規(guī)則，數(shù)據(jù)項(xiàng)之間的關(guān)系通常出現(xiàn)在相對(duì)高的層中.如: IBMComputer和HPPrinter之間可能找不出什么關(guān)聯(lián),但Computer和Printer之間卻有關(guān)聯(lián) 但是，對(duì)某一個(gè)用戶具有含義的規(guī)則對(duì)另一用戶可能并沒有什么用，所以數(shù)據(jù)挖掘應(yīng)該給用戶提供可以在多個(gè)抽象層挖掘的能力并能在多維空間中漫游。多層挖掘算法自頂向下,逐層挖掘使用統(tǒng)一的minisupp

優(yōu)點(diǎn):簡(jiǎn)單 缺點(diǎn):如果minisupp過大,低層會(huì)丟失很多規(guī)則 如果minisupp過小,高層會(huì)產(chǎn)生很多無用規(guī)則使用不同的minisupp使用不同的minisupp，方法1Levelbylevel ： 每一層獨(dú)立地進(jìn)行挖掘

例如：如果“ComputerFurniture”不頻繁，則大多數(shù)情況下用不著再考察“ComputerChair”。 缺點(diǎn)：效率低，不利用背景知識(shí)，要考察很多不可能頻繁的項(xiàng)目使用不同的minisupp，方法2Level-crossFilteringbyk-itemset： 如果父結(jié)點(diǎn)是頻繁的k-itemset，則進(jìn)一步考察孩子結(jié)點(diǎn)是否是頻繁的k-itemset，否則修剪掉

缺點(diǎn)：丟掉了一些有用的規(guī)則使用不同的minisupp，方法3Level-crossFilteringbysingleitem：

如果父結(jié)點(diǎn)是頻繁項(xiàng)目，則進(jìn)一步考察孩子結(jié)點(diǎn)，否則修剪掉 缺點(diǎn)：由于minisupp不同，父結(jié)點(diǎn)不頻繁，子節(jié)點(diǎn)有可能頻繁，可能丟掉規(guī)則使用不同的minisupp，方法4改進(jìn)Level-crossFilteringbysingleitem：增加一個(gè)“l(fā)evelpassagethreshold”，如果父結(jié)點(diǎn)不頻繁，但滿足passingdown條件，則需要進(jìn)一步考察子結(jié)點(diǎn)?！發(fā)evelpassagethreshold”：一般設(shè)置為當(dāng)前層的minisupp和下一層的minisupp之間的一個(gè)值。去掉冗余的多層規(guī)則例如：DesktopComputer→b/wprinter（support=0.08,confidence=0.7）IBMDesktopComputer→b/wprinter (support=0.02,confidence=0.72)(冗余)如果一條規(guī)則的支持度和可信度接近于它的預(yù)期值，則說它是冗余的。預(yù)期值是由它的祖先規(guī)則和子項(xiàng)目在父項(xiàng)目中所占的比例決定的。例如：上例中IBMDesktopComputer占DesktopComputer比例為0.25的話，則“預(yù)期”支持度為0.02.

MiningMulti-DimensionalAssociationSingle-dimensionalrules:buys(X,“milk”)buys(X,“bread”)Multi-dimensionalrules:

2dimensionsorpredicatesInter-dimensionassoc.rules(norepeatedpredicates)age(X,”19-25”)occupation(X,“student”)buys(X,“coke”)hybrid-dimensionassoc.rules(repeatedpredicates)age(X,”19-25”)buys(X,“popcorn”)buys(X,“coke”)CategoricalAttributes:finitenumberofpossiblevalues,noorderingamongvalues—datacubeapproachQuantitativeAttributes:numeric,implicitorderingamongvalues—discretization,clustering,andgradientapproachesMiningQuantitativeAssociations按照對(duì)待數(shù)值屬性的不同方法,分為:靜態(tài)方法:數(shù)值屬性根據(jù)預(yù)先定義好的概念層次被離散化。離散化發(fā)生在挖掘之前.靜態(tài) 例如：收入被離散化為“0-20k”，“21-30k”,等等動(dòng)態(tài)方法:數(shù)值屬性根據(jù)數(shù)據(jù)的分布被離散到多個(gè)“bins”中。這些“bins”在數(shù)據(jù)挖掘的過程中可以進(jìn)一步結(jié)合起來。動(dòng)態(tài)基于距離的AR:數(shù)值屬性的離散化是為了捕捉數(shù)據(jù)間的語(yǔ)義.動(dòng)態(tài)離散過程考慮數(shù)據(jù)點(diǎn)之間的距離，故稱為基于距離的ARMiningQuantitativeAssociations 數(shù)值屬性在挖掘之前被離散為以區(qū)間段表示的分類屬性，如果需要的話分類屬性還可以用更一般的高層概念取代。從關(guān)系表中挖掘 Apriori算法稍作修改就可以用來找到所有的頻繁謂詞集合（用所有的相關(guān)屬性而不止是buys一個(gè)屬性）?？梢杂胔ashing，partitioning，sampling等策略來提高性能。從cube中挖掘 相關(guān)cube可能已經(jīng)存在，這時(shí)可以使用Apriori中用到的策略，可以用來減少候選謂詞集合的數(shù)目。

當(dāng)相關(guān)的cube不存在的情況下，則必須先構(gòu)建此cube，已經(jīng)有很多快速計(jì)算cube的方法，可以修改一下，在cube構(gòu)建的同時(shí)查找頻繁謂詞集合。MiningQuantitativeAssociations 在挖掘的過程中用動(dòng)態(tài)離散方法來離散數(shù)值屬性以滿足某些挖掘標(biāo)準(zhǔn)，例如挖掘出來的規(guī)則的可信度或緊密度（compactness）最大。 例如：兩維AR，左邊具有兩個(gè)量化屬性，右邊具有一個(gè)分類屬性

age(X,“30-39”)∧e（X,“4000-4900”） →buys（X,“colorTV”）MiningQuantitativeAssociations將屬性對(duì)映射到一個(gè)二維的格子中，然后在該格子中查找點(diǎn)群，再由此點(diǎn)群得到關(guān)聯(lián)規(guī)則。共分三步.

第一步: bining：將數(shù)據(jù)屬性離散化為區(qū)間

等寬：每個(gè)bin的距離間隔一樣。 等深：每個(gè)bin所具有的元組的數(shù)目相等。 等質(zhì)：bin的大小決定后，每一個(gè)bin中的元組是統(tǒng)一分布的 ARCS采用等寬劃分,用所有的bin組合創(chuàng)建一個(gè)二維數(shù)組，數(shù)據(jù)元素為每個(gè)分類進(jìn)行計(jì)數(shù)MiningQuantitativeAssociations第二步:

掃描二維數(shù)組,尋找頻繁謂詞集,產(chǎn)生關(guān)聯(lián)規(guī)則第三步:

借用cluster方法,合并關(guān)聯(lián)規(guī)則 如: age(X,34)∧e（X,“3000-4000”）→buys（X,“colorTV”）

age(X,34)∧e（X,“4000-4900”）→buys（X,“colorTV”）

age(X,35)∧e（X,“3000-4000”）→buys（X,“colorTV”）

age(X,35)∧e（X,“4000-4900”）→buys（X,“colorTV”） 合并為: age(X,“34-35”)∧e（X,“3000-4900”）→buys（X,“colorTV”）MiningQuantitativeAssociationsMiningQuantitativeAssociations前面的方法沒有捕捉到數(shù)據(jù)之間的語(yǔ)義聯(lián)系.基于距離的AR,捕捉數(shù)據(jù)之間的語(yǔ)義并允許近似的數(shù)據(jù)值.如:Item_type(X,“electronic”)∧Manufacturer(X,“foreign”)→Price(X,$200)某個(gè)foreignelectronicitem可以近似于200MiningQuantitativeAssociations基于距離的AR挖掘包括兩個(gè)階段:在每個(gè)維上運(yùn)用cluster方法劃分區(qū)間(離散化)尋找頻繁的clustergroupCorrelationAnalysis

用support+confidence挖掘出的規(guī)則有時(shí)無用，

某些商品是被隨機(jī)放入購(gòu)物籃中的 例如：類似這樣的規(guī)則，{牛奶，黃油}—〉面包，它的可信度非常大，可能是因?yàn)楹芏嗳硕假?gòu)買面包，象這樣的規(guī)則是無用的。前后之間并沒有因果關(guān)系

CorrelationAnalysis相關(guān)分析：根據(jù)項(xiàng)目的相關(guān)性來尋找項(xiàng)目之間的相互關(guān)系相關(guān)性：

如果CorrA,B

<1,A和B負(fù)相關(guān),互相排斥如果CorrA,B

=1,A和B不相關(guān),互相獨(dú)立如果CorrA,B

>1,A和B正相關(guān),互相吸引CorrelationandLiftP(B|A)/P(B)iscalledtheliftofruleA=>BCorrelationAnalysis舉例 P(game)=0.6, P(video)=0.75 P(game,video)=0.4 CorrA,B=P(game,video)/P(game)*P(video) =0.4/(0.6*0.75) =0.89<1,

game和video負(fù)相關(guān),互相排斥gamegameallvideo400035007500video20005002500all6000400010000CorrelationruleMining重要屬性:upwardClosed如果項(xiàng)目集S是相關(guān)的,則S的所有超集都是相關(guān)的.RandomWalkAlgorithm:開始,項(xiàng)目集為空,然后,每次增加一個(gè)項(xiàng)目,看該項(xiàng)目集是否相關(guān),一旦相關(guān),則算法停止Constraint-basedAssociationMining一般來說,給定相關(guān)數(shù)據(jù),從中挖掘出的無用規(guī)則太多,為此由用戶提供一些限制,引導(dǎo)挖掘Knowledgeconstraints:指定要挖掘的知識(shí)的類型,如ARDataconstraints:指定相關(guān)的數(shù)據(jù)Dimension/levelconstraint:指定挖掘時(shí)所用的維或?qū)覫nterestingnessconstraint:指定用來度量規(guī)則是否有用的統(tǒng)計(jì)值,如support和confidenceRuleconstraint:指定要挖掘的規(guī)則的形式,如metaruleMetarule-GuidedMiningofARMetarule是一種規(guī)則模板,用來指定用戶所興趣的規(guī)則的語(yǔ)法形式,進(jìn)而引導(dǎo)挖掘過程,提高挖掘效率例如:某市場(chǎng)推銷人員可能想知道具有哪兩個(gè)特點(diǎn)的人傾向于購(gòu)買教育軟件,為此,設(shè)定如下規(guī)則模板:P1(X,Y)∧P2(X,Y)→buys(X,“educationalsoftware”)與之相匹配的一條規(guī)則如下:P1(X,“30-39”)∧P2(X,“4000-5000”)→buys(X,“educationalsoftware”)Metarule-GuidedMiningofAR假設(shè)需要挖掘如下的關(guān)聯(lián)規(guī)則:P1∧P2∧…∧Pm→Q1∧Q2∧…∧Qn1.找出所有的頻繁謂詞集L(m+n)(滿足最小支持度)2.計(jì)算L(m+n)的子集Lm的支持度(滿足最小可信度)這是典型的多維查詢,但這里只需要使用(m+n)維的cuboid和m維的cuboid,其他的不需要.所以,如果這兩類cuboid沒有實(shí)體化的話,則需要現(xiàn)計(jì)算MiningGuidedbyAdditionalRuleConstraint可以用一個(gè)associationminingquery來設(shè)定更多的限制例如一個(gè)電器商店具有下面的數(shù)據(jù)庫(kù)表:Sales(customer-name,item-name,transaction-id)Lives(customer-name,region,city)Item(item-name,category,price)Transaction(transaction-id,day,month,year)在其上的一個(gè)查詢:MineassociationsasLive(C,_,“Vancouver”)∧Sales(C,?{I},{S})→Sales(C,?{J},{T})FromSalesWhereS.year=1999∧T.year=1999∧I.category=J.categoryGroupbyC,I.categoryHavingsum(I.price)≤100∧min(J.price)≥500Withsupportthreshold=0.01Withconfidencethreshold=0.5MiningGuidedbyAdditionalRuleConstraintKnowledgeconstraintmetaruleDataconstraintruleconstraintruleconstraintinterestingnessconstraintRuleconstraintsclassificationAnti-monotone(Aprioriproperty,generateandtest)MonotoneSuccinctConvertibleInconvertibleQueryOptimizationforConstrainedFPMAMiningfrequentpatternswithconstraintCSound:onlyfindpatternssatisfyingtheconstraintsCComplete:findallpatternssatisfyingtheconstraintsCAna?vesolutionConstrainttestasapost-processingMoreefficientapproachesAnalyzethepropertiesofconstraintscomprehensivelyPushconstraintsasdeeplyaspossibleinsidethefrequentpatternminingAnti-Monotonicity如果某個(gè)項(xiàng)目集不能滿足某個(gè)限制條件,則它的所有超集都不會(huì)滿足如Sum(Price)100,Count(I)10,

Min(sales)≥100等Apriori算法的每一次迭代，都使用了該性質(zhì)，來幫助提高整個(gè)挖掘過程的性能。盡早將那些不滿足條件的候選itemset剪掉。（Apriori算法中用到的那個(gè)公理具有Anti-monotone性質(zhì)）反之，avg(I.price)100則不是Anti-monotone該約束不可以下推進(jìn)到挖掘過程之中，下推并剪枝的話不能保證算法的正確性。Anti-MonotonicityAnti-monotonicityAnitemsetSviolatestheconstraint,sodoesanyofitssupersetsum(S.Profit)visanti-monotonesum(S.Profit)visnotanti-monotoneExampleC:sum(S.Profit)40isanti-monotoneItemsetacviolatesCSodoeseverysupersetofacTIDTransaction10a,b,c,d,f20b,c,d,f,g,h30a,c,d,e,f40c,e,f,gTDB(min_sup=2)ItemProfita40b0c20d10e30f30g20h10Anti-monotonicConstraintsConstraintAntimonotonevSNoSVnoSVyesmin(S)vnomin(S)vyesmax(S)vyesmax(S)vnocount(S)vyescount(S)vnosum(S)v(aS,a0)yessum(S)v(aS,a0)norange(S)vyesrange(S)vnoavg(S)v,{,,}convertiblesupport(S)

yessupport(S)

noMonotonicityMonotonicityAnitemsetSsatisfiestheconstraint,sodoesanyofitssupersetsum(S.Price)vismonotonemin(S.Price)vismonotoneExampleC:min(S.profit)15ItemsetabsatisfiesCSodoeseverysupersetofabTIDTransaction10a,b,c,d,f20b,c,d,f,g,h30a,c,d,e,f40c,e,f,gTDB(min_sup=2)ItemProfita40b0c20d10e30f30g20h10MonotonicConstraintsConstraintMonotonevSyesSVyesSVnomin(S)vyesmin(S)vnomax(S)vnomax(S)vyescount(S)vnocount(S)vyessum(S)v(aS,a0)nosum(S)v(aS,a0)yesrange(S)vnorange(S)vyesavg(S)v,{,,}convertiblesupport(S)

nosupport(S)

yesSuccinctnessSuccinctness:WithoutevengeneratingtheitemsetS,whetheranitemsetSsatisfiesconstraintCcanbedeterminedbasedontheselectionofitemsmin(S.Price)vissuccinctsum(S.Price)visnotsuccinctExample:min(S.Price)<20.Weimmediateknowwhethertheconstraintissatisfiedoncewegeneratethe2-itemsetOptimization:IfCissuccinct,Cispre-countingpushableItemProfita40b0c20d10e30f30g20h10SuccinctConstraintsConstraintSuccinctvSyesSVyesSVyesmin(S)vyesmin(S)vyesmax(S)vyesmax(S)vyescount(S)vweaklycount(S)vweaklysum(S)v(aS,a0)nosum(S)v(aS,a0)norange(S)vnorange(S)vnoavg(S)v,{,,}nosupport(S)

nosupport(S)

noConverting“Tough”ConstraintsConverttoughconstraintsintoanti-monotoneormonotonebyproperlyorderingitemsExamineC:avg(S.profit)25Orderitemsinvalue-descendingorder<a,f,g,d,b,h,c,e>IfanitemsetafbviolatesCSodoesafbh,afb*Itesanti-monotone!TIDTransaction10a,b,c,d,f20b,c,d,f,g,h30a,c,d,e,f40c,e,f,gTDB(min_sup=2)ItemProfita40b0c-20d10e-30f30g20h-10StronglyConvertibleConstraintsavg(X)25isconvertibleanti-monotonew.r.t.itemvaluedes