基于約束的挖掘(上課)

1、中南大學(xué)信息科學(xué)與工程學(xué)院2004.3l 使用約束的必要性 - 基于約束的關(guān)聯(lián)規(guī)則挖掘可以促進(jìn)交互式探查與分析。 - 在實(shí)際的挖掘過程中，用戶往往希望參與到挖掘的全過程中，以便對(duì)挖掘過程進(jìn)行指導(dǎo)和控制；用戶所關(guān)心的通常只是關(guān)聯(lián)規(guī)則的某個(gè)子集，而不是泛泛地發(fā)現(xiàn)全部規(guī)則，這就需要有效地利用約束條件縮減數(shù)據(jù)庫中事務(wù)的數(shù)量，提高挖掘效率。 l在數(shù)據(jù)挖掘中常使用的幾種約束：知識(shí)類型約束：指定要挖掘的知識(shí)類型 如關(guān)聯(lián)規(guī)則數(shù)據(jù)約束： 指定與任務(wù)相關(guān)的數(shù)據(jù)集 lFind product pairs sold together in Vancouver in Dec.98.維/層次約束:指定所用的維或概念結(jié)構(gòu)中

2、的層lin relevance to region, price, brand, customer category.規(guī)則約束：指定要挖掘的規(guī)則形式(如規(guī)則模板)l單價(jià) (price $200).興趣度約束：指定規(guī)則興趣度閾值或統(tǒng)計(jì)度量l如 (min_support 3%, min_confidence 60%).l假定AllElectronics的一個(gè)銷售多維數(shù)據(jù)庫有如下關(guān)系：lSales(customer_name,item_name,transaction_id)lLives(customer_name,region,city)lItems(item_name,category，pric

3、e)lTransaction(transaction_id,day,month,year) (1) mine associations as (2)lives(C,_,”Pudong”)sales(C,I,S)=sales(C,JT) (3) from sales (4)where S.year=1999 &T.year=1999 &I.category=J.category (5)group by C,I.category (6)having sum(I.price=500 (7)with support threshold=1% (8)with confidence thr

4、eshold=50%Lives(C,_,”Pudong”)Sales(C,”Census_CD”,_)Sales(C,”MS/Office”,_)=Sales(C,”MS/SQLSever”,_) 1.5%,65%l單調(diào)性約束(monotone constraint)l反單調(diào)性約束(anti-monotone constraint)l可轉(zhuǎn)變的約束(convertible constraint)l簡(jiǎn)潔性約束(succinct constraint)l不可轉(zhuǎn)變的約束(inconvertible constraint) 設(shè)Ii1，i2，im是項(xiàng)的集合。設(shè)X是一個(gè)項(xiàng)集，關(guān)聯(lián)規(guī)則是形如XY的蘊(yùn)含式，其中

5、XI，YI，XY。支持度s是DB中事務(wù)包含XY（即X和Y二者）的百分比。置信度c是DB中包含X的事務(wù)也包含Y的百分比。滿足最小支持度閾值min_sup的項(xiàng)集稱為頻繁項(xiàng)集。挖掘關(guān)聯(lián)規(guī)則就是在給定的交易集合中產(chǎn)生所有滿足最小支持度閾值和最小置信度的強(qiáng)規(guī)則。 關(guān)聯(lián)規(guī)則的挖掘是一個(gè)兩步的過程：（1）找出所有頻繁項(xiàng)集；（2）由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。第二步相對(duì)來說比較簡(jiǎn)單。挖掘關(guān)聯(lián)規(guī)則的總體性能由第一步?jīng)Q定。l項(xiàng)目集：I = i1，i2，iml交易：T = l模式S是項(xiàng)目集的子集，S = ij1,ij2,ijkl模式S約束于T，T = ，if and only if S It; S是S的子模式(subp

6、attern)且S 是S的超模式(superpattern)， if and only if有SS。l定義約束: C是作用于項(xiàng)目集I的冪集(powerset)上的謂詞,C(S)=True/False;l滿意模式集(satisfying pattern set) SATc(I)是指那些完全滿足約束C的項(xiàng)目集的全體l將約束條件用于頻繁集的查詢無非是找出那些滿足C的頻繁集l規(guī)則 Ca 是 反單調(diào)的(：如果對(duì)于任給的不滿足Ca的項(xiàng)集(模式) S，不存在S的任何超集能夠滿足 Ca。 - e.g: Ca : min(S)=v ， v是S的一個(gè)項(xiàng)集 諸如“min(J.Price) =500”的約束，對(duì)于一個(gè)

7、不滿足該約束的項(xiàng)集，無論添加多少項(xiàng)得到的超集都不可能滿足該約束。 - Apriori性質(zhì)（頻繁項(xiàng)集的任何非空子集也必然是頻繁的）也是反單調(diào)的。l約束Cm 是單調(diào)的(monotone )：如果對(duì)于任給的滿足Cm的項(xiàng)集(模式) S, 每一個(gè)S的超集都能夠滿足 Cm。 - e.g: Cm : min(S)=v, v是S的一個(gè)項(xiàng)集 諸如“min(J.Price) C(S) 則C(S)是反單調(diào)可轉(zhuǎn)變的l令I(lǐng)為一組以升序排列數(shù)值的項(xiàng)目集E.g. I=1，3，4，6，8，9 ， R指升序lAvg(S) = v 是反單調(diào)可轉(zhuǎn)變的如果 S 是S的一個(gè)后綴, 那么avg(S) = avg(S)l6,8,9 is

8、a suffix of 3,4,6,8,9lavg(6,8,9)=23/3 avg(3,4,6,8,9)=6如果 S滿足約束 avg(S) v, 則 S也滿足l單調(diào)可轉(zhuǎn)變的 1. C(S)既不是單調(diào)性約束，也不是反單調(diào)性約束； 2. 若存在順序R,使得經(jīng)R排序后的I具有如下性質(zhì)： 任給 Ssuffix_S, if C(S)=C(S) 則C(S)是單調(diào)可轉(zhuǎn)變的l令I(lǐng)為一組以降序排列數(shù)值的項(xiàng)目集E.g. I=9, 8, 6, 4, 3, 1， R指降序lAvg(S) v 是單調(diào)可轉(zhuǎn)變的如果 S 是S的一個(gè)后綴, 那么avg(S) avg(S)l8, 4, 3 is a suffix of 9, 8

9、, 4, 3lavg(9, 8, 4, 3)=6 avg(8, 4, 3)=5如果 S滿足約束 avg(S) v, 則 S也滿足l8, 4, 3 satisfies constraint avg(S) 4, so does 9, 8, 4, 3l一個(gè)項(xiàng)目子集Is 是一個(gè) 簡(jiǎn)潔集(, 如果對(duì)于某些選擇性謂詞p,該項(xiàng)目子集能夠表示為p(I) ，此處， 是一個(gè)選擇符lSP2I 是一個(gè)強(qiáng)簡(jiǎn)潔集( succinct ,如果有一個(gè)數(shù)目不變的簡(jiǎn)潔集 I1, , Ik I, SP 能夠用I1, , Ik 的并、差運(yùn)算表示出來 be expressed in terms of the strict power

10、sets of I1, , Ik using union and minusl約束 Cs 是 假如 SATCs(I)是一個(gè)強(qiáng)簡(jiǎn)潔集l如果一個(gè)約束是簡(jiǎn)潔的，我們可以直接精確地產(chǎn)生滿足它的集合，甚至在支持計(jì)數(shù)之前。即這種約束是計(jì)數(shù)前可剪枝的。l例如“min(J.Price) =500”是簡(jiǎn)潔的。我們能夠準(zhǔn)確無誤地產(chǎn)生滿足該約束的所有項(xiàng)集。在挖掘過程中不必迭代地檢驗(yàn)規(guī)則約束。約束規(guī)則約束規(guī)則v SS VS VS Vmin(S) vmin(S) vmin(S) vmax(S) vmax(S) vmax(S) vcount(S) vcount(S) vcount(S) vsum(S) vsum(S) v

11、sum(S) vavg(S) v, , , (frequent constraint)簡(jiǎn)潔性簡(jiǎn)潔性yesyesyesyesyesyesyesyesyesyesweaklyweaklyweakly nononono(no)2004年12月14日星期二Data Mining: Concepts and Techniques77Classification of ConstraintsConvertibleanti-monotoneConvertiblemonotoneStronglyconvertibleInconvertibleSuccinctAntimonotoneMonotonel CFG(

12、Constrained Frequent pattern Growth)算法： - 基于FP-Growth算法， 針對(duì)可轉(zhuǎn)變約束條件 - Can we push more constraints into frequent pattern mining? (J.Pei, J.Han KDD00)l MultipleJoins、Reorder和Direct算法： - 約束條件為布爾表達(dá)式形式 - Mining Association Rules with Item Constraints(Srikant, Vu&Agrawal 1997) Transaction_ID Items In

13、Transaction 100 a,e,c,d,f 200 a,b 300 a,e,c,f 400 a,e,b,c,d,f 500 a,e,b,d l交易數(shù)據(jù)庫TDB如下所示，支持度為 3 頻繁項(xiàng)目按照降續(xù)排列 ：a:5; e:4; b:3; c:3; d:3; f:3l將排序后的每次交易的項(xiàng)目列表的前綴項(xiàng)目映射到條件數(shù)據(jù)庫TDB|f; TDB|d; TDB|c; TDB|b; TDB|e中l(wèi)例如：對(duì)于交易號(hào)為100的交易(a,e,c,d,f)。將f的前綴a,e,c,d插入f的條件數(shù)據(jù)庫TDB|f中；將d的前綴a,e,c插入d的條件數(shù)據(jù)庫TDB|d中；將c的前綴a,e插入c的條件數(shù)據(jù)庫TDB|

14、c中；將e的前綴a插入e的條件數(shù)據(jù)庫TDB|e中。TD Baecdf,ab,aecf,aebcdf,aebd Frequent items: a,e,b,c,d,f f-Conditional database TD B |f aecd,aec,aebcd frequent items:a,e,c TDB|d TDB|c TDB|e TDB|b l條件數(shù)據(jù)庫的性質(zhì):如果模式在 TDB|f 中是頻繁的，則f 在TDB|f中也一定是頻繁的l頻繁集的生長過程 1. 在 TDB|f 中找到相應(yīng)的頻繁項(xiàng)目集, 被稱為f的條件頻繁項(xiàng)目集 2. 對(duì)于每一個(gè)在中的頻繁項(xiàng)目e，找出TDB|ef 中相應(yīng)的頻繁項(xiàng)目

15、集，這是一個(gè)遞歸的過程lCaSum(S)180，所以可以不必考慮項(xiàng)集d。l如果不滿足約束，則不必產(chǎn)生的條件項(xiàng)目集,也不必產(chǎn)生的條件數(shù)據(jù)庫TDB | 例如： Sum(a,b)=200 180 ，不滿足約束條件Ca ，項(xiàng)集a,b的任何超集都不滿足約束，因此不必產(chǎn)生a,b的條件數(shù)據(jù)庫。l如果滿足約束，則不必對(duì)條件數(shù)據(jù)庫TDB| 中的其余部分用Ca進(jìn)行約束檢查，此處是在TDB | 中的頻繁項(xiàng)目集。 (No constraint checking in the remaining conditional database TDB| , if satisfies the constraint.) 例如：對(duì)

16、于條件數(shù)據(jù)庫TDB| f，只存在3個(gè)頻繁1-項(xiàng)集a, e, c，sum(a, c, e, f)160 180。顯然，項(xiàng)集a, c, e, f的任何子集均滿足約束條件Ca ，因此在對(duì)這個(gè)條件數(shù)據(jù)庫的挖掘過程中，就不必進(jìn)行約束條件檢查了。TDB aecdf,ab,aecf,aebcdf,aebd Frequent items: a,e,b,c,d,fC(a)=true; C(e)=true; C(b)=true; C(c)=true; C(f)=true; C(d)=false TDB|f aecd,aec,aebcd Frequent items: a,e,c因?yàn)镃(aecf)=true;所以C

17、(af)=true; C(ef)=true; C(cf)=true; C(aef)=true; C(acf)=true; TDB|c ae,ae,aeb Frequent items: a,e因?yàn)镃(aec)=true;所以C(ac)=true; C(ec)=true; TDB|b a,ae,ae Frequent items: a,e因?yàn)镃(ab)=false;所以ab的所有超集均不滿足約束條件C TDB|e a,a,a,a Frequent items: aC(ae)=true;l我們所討論的約束條件為項(xiàng)約束條件，即要求關(guān)聯(lián)規(guī)則中至少包含用戶定義的一個(gè)項(xiàng)集中的某個(gè)項(xiàng)。設(shè)給定項(xiàng)約束條件B，B

18、為I上的一個(gè)布爾 表 達(dá) 式 。 假 設(shè) B 已 經(jīng) 轉(zhuǎn) 變 為 D N F 形 式 ：d1 d2 dm， 其 中 每 個(gè) di形 如 ：ai1ai2ain。l定義1 如果aij為i或i，其中iI，那么分別稱為項(xiàng)包含條件或項(xiàng)不包含條件。如果項(xiàng)集X包含di中所有項(xiàng)包含條件，而且不包含di中所有項(xiàng)不包含條件，那么稱項(xiàng)集X滿足約束條件項(xiàng)di。如果X滿足約束條件B中某個(gè)約束條件項(xiàng)di，那么稱X滿足約束條件B。 lDirect算法能直接從約束條件B中產(chǎn)生候選項(xiàng)集。l候選項(xiàng)集產(chǎn)生方法： 11kBkBkDFLC具體步驟：1. 2. Delete all candidates in that do not satisfy B3. Delete all candidates in with a k-subset that satisfies B but does not have minimum support4. For each disjunct di=ai1ai2ain，in B with exactly k+1 non-negated elements ,add the itemset to if all the are fre