在大型數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則

在大型數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則第一頁，共22頁。6.6.1基于約束的挖掘使用約束的必要性在數(shù)據(jù)挖掘中常使用的幾種約束：知識類型約束：指定要挖掘的知識類型如關(guān)聯(lián)規(guī)則數(shù)據(jù)約束：指定與任務(wù)相關(guān)的數(shù)據(jù)集FindproductpairssoldtogetherinVancouverinDec.’98.維/層次約束:指定所用的維或概念結(jié)構(gòu)中的層inrelevancetoregion,price,brand,customercategory.規(guī)則約束：指定要挖掘的規(guī)則形式(如規(guī)則模板)單價(jià)(price<$10)的交易項(xiàng)目可能引發(fā)購買總額(sum>$200).興趣度約束：指定規(guī)則興趣度閾值或統(tǒng)計(jì)度量如(min_support3%,min_confidence60%).第二頁，共22頁。假定AllElectronics的一個(gè)銷售多維數(shù)據(jù)庫有如下關(guān)系：Sales(customer_name,item_name,transaction_id)Lives(customer_name,region,city)Items(item_name,category，price)Transaction(transaction_id,day,month,year)(1)mineassociationsas(2)lives(C,_,”Pudong”)^sales(C,{I},{S})=>sales(C,{J}{T})(3)fromsales(4)whereS.year=1999&&T.year=1999&&I.category=J.category(5)groupbyC,I.category(6)havingsum(I.price<=100)&&min(J.price)>=500(7)withsupportthreshold=1%(8)withconfidencethreshold=50%Lives(C,_,”Pudong”)^Sales(C,”Census_CD”,_)^Sales(C,”MS/Office”,_)=>Sales(C,”MS/SQLSever”,_)[1.5%,65%]第三頁，共22頁。6.6.2約束的分類單調(diào)性約束(monotoneconstraint)反單調(diào)性約束(anti-monotoneconstraint)可轉(zhuǎn)變的約束(convertibaleconstraint)簡潔性約束(succinctconstraint)第四頁，共22頁。約束的有關(guān)概念項(xiàng)目集：I={i1,i2,……,im},交易：T=<tid,It>模式S是項(xiàng)目集的子集，S={ij1,ij2,…,ijk}模式S包含與T,T=<tid,It>,iffS<=It;S’是S的子模式(subpattern)且S是S’的超模式(superpattern)，if有S’<=S.第五頁，共22頁。約束的有關(guān)概念（續(xù)）定義約束:C是作用于項(xiàng)目集I的冪集(powerset)上的謂詞,C(S)=True/False;滿意模式集(satisfyingpatternset)SATc(I)是指那些完全滿足約束C的項(xiàng)目集的全體將約束條件用于頻繁集的查詢無非是找出那些滿足C的頻繁集

第六頁，共22頁。單調(diào)和反單調(diào)的規(guī)則約束規(guī)則Ca是反單調(diào)的(anti-monotone)iff對于任給的不滿足Ca的項(xiàng)集(模式)S,不存在S的超集能夠滿足Cae.g:Ca:min(S)>=v，v是S的一個(gè)項(xiàng)集約束Cm是單調(diào)的iff.對于任給的滿足Cm的項(xiàng)集(模式)S,每一個(gè)S的超集都能夠滿足Cme.g:Cm:min(S)<=v,v是S的一個(gè)項(xiàng)集第七頁，共22頁。單調(diào)/反單調(diào)性約束描述vSSVSVSVmin(S)vmin(S)vmin(S)vmax(S)vmax(S)vmax(S)vcount(S)vcount(S)vcount(S)vsum(S)vsum(S)vsum(S)vavg(S)v,{,,}(frequentconstraint)yesyesnopartlyyesnopartlynoyespartlynoyespartlynoyespartlyconvertible(no)nonoyespartlynoyespartlyyesnopartlyyesnopartlyyesnopartlyconvertible(yes)反單調(diào)單調(diào)約束規(guī)則第八頁，共22頁。可轉(zhuǎn)變的約束1反單調(diào)可轉(zhuǎn)變的1.C(S)既不是單調(diào)性約束，也不是反單調(diào)性約束；2.若存在順序R,使得經(jīng)R排序后的I具有如下性質(zhì)：任給S’∈{suffix_S},ifC(S)=>C(S’)則C(S)是反單調(diào)可轉(zhuǎn)變的第九頁，共22頁?？赊D(zhuǎn)變性約束的例子1:

Avg(S)V令I(lǐng)為一組以升序排列數(shù)值的項(xiàng)目集E.g.I={1，3，4，6，8，9,}，R意指升續(xù)Avg(S)>=v是反單調(diào)可轉(zhuǎn)變的如果S’是S的一個(gè)后綴,那么avg(S’)>=avg(S){6,8,9}isasuffixof{3,4,6,8,9}avg({6,8,9})=23/3avg({3,4,6,8,9})=6如果S滿足約束avg(S)v,則S’也滿足第十頁，共22頁?？赊D(zhuǎn)變的約束2單調(diào)可轉(zhuǎn)變的1.C(S)既不是單調(diào)性約束，也不是反單調(diào)性約束；2.若存在順序R,使得經(jīng)R排序后的I具有如下性質(zhì)：任給S’∈{suffix_S},ifC(S’)=>C(S)則C(S)是單調(diào)可轉(zhuǎn)變的第十一頁，共22頁?？赊D(zhuǎn)變性約束的例子2

Avg(S)V令I(lǐng)為一組以降序排列數(shù)值的項(xiàng)目集E.g.I={9,8,6,4,3,1}，R意指降續(xù)Avg(S)v是單調(diào)可轉(zhuǎn)變的如果S’是S的一個(gè)后綴,那么avg(S)avg(S’){8,4,3}isasuffixof{9,8,4,3}avg({9,8,4,3})=6avg({8,4,3})=5如果S’滿足約束avg(S’)v,則S也滿足{8,4,3}satisfiesconstraintavg(S)4,sodoes{9,8,4,3}第十二頁，共22頁。簡潔性約束一個(gè)項(xiàng)目子集Is是一個(gè)簡潔集(succinctset),如果對于某些選擇性謂詞p,該項(xiàng)目子集能夠表示為p(I)，此處，是一個(gè)選擇符SP2I是一個(gè)強(qiáng)簡潔集(succinctpowerset),如果有一個(gè)數(shù)目不變的簡潔集I1,…,IkI,SP能夠用I1,…,Ik的并、差運(yùn)算表示出來beexpressedintermsofthestrictpowersetsofI1,…,Ikusingunionandminus約束Cs是簡潔的假如SATCs(I)是一個(gè)強(qiáng)簡潔集第十三頁，共22頁。簡潔性約束的舉例約束規(guī)則vSSVSVSVmin(S)vmin(S)vmin(S)vmax(S)vmax(S)vmax(S)vcount(S)vcount(S)vcount(S)vsum(S)vsum(S)vsum(S)vavg(S)v,{,,}(frequentconstraint)簡潔性yesyesyesyesyesyesyesyesyesyesweaklyweaklyweaklynononono(no)第十四頁，共22頁。幾種約束之間的關(guān)系SuccinctnessAnti-monotonicityMonotonicityConvertibleconstraintsInconvertibleconstraints第十五頁，共22頁。頻繁數(shù)據(jù)集應(yīng)用舉例交易數(shù)據(jù)庫TDB如下所示，支持度為3頻繁項(xiàng)目按照降續(xù)排列：a:5;e:4;b:3;c:3;d:3;f:3Transaction_IDItemsInTransaction100a,e,c,d,,f200a,b300a,e,c,f400a,e,b,c,d,f500a,e,b,d第十六頁，共22頁。頻繁數(shù)據(jù)集應(yīng)用舉例(續(xù))將排序后的每次交易的項(xiàng)目列表的前綴項(xiàng)目映射到條件數(shù)據(jù)庫TDB|f;TDB|d;TDB|c;TDB|b;TDB|e第十七頁，共22頁。頻繁集的生長過程性質(zhì):如果模式α在TDB|f中是頻繁的，則α∪f在TDB|f中也一定是頻繁的頻繁集的生長過程

1.在TDB|f中找到相應(yīng)的頻繁項(xiàng)目集β,β被稱為f的條件頻繁項(xiàng)目集

2.對于每一個(gè)在β中的頻繁項(xiàng)目e，找出TDB|ef中相應(yīng)的頻繁項(xiàng)目集，這是一個(gè)遞歸的過程第十八頁，共22頁。將約束用于頻繁集的生成Ca≡Sum(S)<=180使用圖表2的交易數(shù)據(jù)庫:support=3{a,s,b,c,d,e,f}={50,150,10,200,20,80}

Transaction_IDItemsInTransaction100a,e,c,d,,f200a,b300a,e,c,f400a,e,b,c,d,f500a,e,b,d第十九頁，共22頁。將約束用于挖掘的幾種策略去除不滿足約束的單個(gè)項(xiàng)目Exam1:Sum(d)=200>180如果α不滿足約束，則不必產(chǎn)生α的條件項(xiàng)目集,也不必產(chǎn)生α的條件數(shù)據(jù)庫TDB|αExam2:Sum({a,b})=200如果α∪β滿足約束，則不必對條件數(shù)據(jù)庫TDB|α中的其余部分用Ca進(jìn)行約束檢查