數(shù)據(jù)挖掘?qū)д撝l繁模式及關(guān)聯(lián)規(guī)則挖掘技術(shù)(一)

《數(shù)據(jù)挖掘?qū)д撝l繁模式及關(guān)聯(lián)規(guī)則挖掘技術(shù)(一)》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)挖掘?qū)д撝l繁模式及關(guān)聯(lián)規(guī)則挖掘技術(shù)(一)（44頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,*,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,第3課,頻繁模式及關(guān)聯(lián)規(guī)則挖掘技術(shù),徐從富，,副教授,浙江大學(xué)人工智能研究所,浙江大學(xué)本科生數(shù)據(jù)挖掘?qū)д撜n件,內(nèi)容提綱,關(guān)聯(lián)規(guī)則挖掘簡介,關(guān)聯(lián)規(guī)則基本模型,關(guān)聯(lián)規(guī)則價值衡量與發(fā)展,參考文獻(xiàn),關(guān)聯(lián)規(guī)則簡介,關(guān)聯(lián)規(guī)則反映一個事物與其他事物之間的相互依存性和關(guān)聯(lián)性。如果兩個

2、或者多個事物之間存在一定的關(guān)聯(lián)關(guān)系，那么，其中一個事物就能夠通過其他事物預(yù)測到。,典型的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題是對超市中的貨籃數(shù)據(jù)（Market Basket）進(jìn)行分析。通過發(fā)現(xiàn)顧客放入貨籃中的不同商品之間的關(guān)系來分析顧客的購買習(xí)慣。,什么是關(guān)聯(lián)規(guī)則挖掘,關(guān)聯(lián)規(guī)則挖掘,首先被Agrawal,Imielinski and Swami在1993年的SIGMOD會議上提出,在事務(wù)、關(guān)系數(shù)據(jù)庫中的項集和對象中發(fā)現(xiàn)頻繁模式、關(guān)聯(lián)規(guī)則、相關(guān)性或者因果結(jié)構(gòu),頻繁模式,:數(shù)據(jù)庫中頻繁出現(xiàn)的項集,目的:發(fā)現(xiàn)數(shù)據(jù)中的規(guī)律,超市數(shù)據(jù)中的什么產(chǎn)品會一起購買？啤酒和尿布,在買了一臺PC之后下一步會購買?,哪種DNA對這種藥物

3、敏感?,我們?nèi)绾巫詣訉eb文檔進(jìn)行分類?,頻繁模式挖掘的重要性,許多重要數(shù)據(jù)挖掘任務(wù)的基礎(chǔ),關(guān)聯(lián)、相關(guān)性、因果性,序列模式、空間模式、時間模式、多維,關(guān)聯(lián)分類、聚類分析,更加廣泛的用處,購物籃分析、交叉銷售、直銷,點擊流分析、DNA序列分析等等,關(guān)聯(lián)規(guī)則基本模型,關(guān)聯(lián)規(guī)則基本模型,Apriori算法,Fp-Tree算法,關(guān)聯(lián)規(guī)則基本模型,IBM公司Almaden研究中心的R.Agrawal首先提出關(guān)聯(lián)規(guī)則模型，并給出求解算法AIS。隨后又出現(xiàn)了SETM和Apriori等算法。其中，Apriori是關(guān)聯(lián)規(guī)則模型中的經(jīng)典算法。,給定一組事務(wù),產(chǎn)生所有的關(guān)聯(lián)規(guī)則,滿足最小支持度和最小可信度,關(guān)聯(lián)規(guī)

4、則基本模型（續(xù)）,設(shè),I,=,i,1,i,2,i,m,為所有項目的集合，,D,為事務(wù)數(shù)據(jù)庫，事務(wù),T,是一個項目子集（,T,I,）。每一個事務(wù)具有唯一的事務(wù)標(biāo)識,TID,。設(shè),A,是一個由項目構(gòu)成的集合，稱為項集。事務(wù),T,包含項集,A,，當(dāng)且僅當(dāng),A,T,。如果項集,A,中包含,k,個項目，則稱其為,k,項集。項集,A,在事務(wù)數(shù)據(jù)庫,D,中出現(xiàn)的次數(shù)占,D,中總事務(wù)的百分比叫做項集的支持度。如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集（或大項集）。,關(guān)聯(lián)規(guī)則基本模型（續(xù)）,關(guān)聯(lián)規(guī)則是形如,X,Y,的邏輯蘊含式，其中,X,I,，,Y,I,，且,X,Y,=,。如果事務(wù)數(shù)據(jù)庫

5、,D,中有,s,%的事務(wù)包含,X,Y,，則稱關(guān)聯(lián)規(guī)則,X,Y,的支持度為,s,%，實際上，支持度是一個概率值。若項集,X,的支持度記為,support,(,X,)，規(guī)則的信任度為,support,(,X,Y,),support,(,X,)。這是一個條件概率,P,(,Y,|,X,)。,也就是：,support,(,X,Y,)=,P,(,X,Y,),confidence,(,X,Y,)=,P,(,Y,|,X,),規(guī)則,度,度量,：,：支,持,持度,與,與可,信,信度,查找,所,所有,的,的規(guī),則,則,X&Y,Z,具有,最,最小,支,支持,度,度和,可,可信,度,度,支持,度,度,s,一,一次,交,

6、交易,中,中包,含,含X,、,、Y,、,、Z,的,的可能,性,性,可信,度,度,c,包含X,、,、Y的,交,交易,中,中也,包,包含,Z,的條件,概,概率,設(shè)最,小,小支,持,持度,為,為50%,最,最小,可,可信,度,度為50%,則,則可,得,得到,A,C,(50%,66.6%),C,A,(50%,100%),買尿,布,布的,客,客戶,二者,都,都買,的,的客,戶,戶,買啤,酒,酒的,客,客戶,關(guān)聯(lián),規(guī),規(guī)則,基,基本,模,模型,（,（續(xù),）,）,關(guān)聯(lián),規(guī),規(guī)則,就,就是,支,支持,度,度和,信,信任,度,度分,別,別滿,足,足用,戶,戶給,定,定閾,值,值的,規(guī),規(guī)則,。,。,發(fā)現(xiàn),關(guān),關(guān)

7、聯(lián),規(guī),規(guī)則,需,需要,經(jīng),經(jīng)歷,如,如下,兩,兩個,步,步驟,：,：,找出,所,所有,頻,頻繁,項,項集,。,。,由頻,繁,繁項,集,集生,成,成滿,足,足最,小,小信,任,任度,閾,閾值,的,的規(guī),則,則。,Letmin_support=50%,min_conf=50%:,A,C,(50%,66.7%),C,A,(50%,100%),Customer,buys diaper,Customer,buys both,Customer,buys beer,Transaction-id,Items bought,10,A,B,C,20,A,C,30,A,D,40,B,E,F,Forrule,A,C

8、,:,support=support(,A,C,)=50%,confidence=support(,A,C,)/support(,A,)=66.6%,Min.support50%,Min.confidence50%,Transaction-id,Items bought,10,A,B,C,20,A,C,30,A,D,40,B,E,F,Frequent pattern,Support,A,75%,B,50%,C,50%,A,C,50%,Apriori算,法,法的,步,步驟,Apriori算,法,法命,名,名源,于,于算,法,法使,用,用了,頻,頻繁,項,項集,性,性質(zhì),的,的先,驗,驗（Prio

9、r）,知,知識,。,。,Apriori算,法,法將,發(fā),發(fā)現(xiàn),關(guān),關(guān)聯(lián),規(guī),規(guī)則,的,的過,程,程分,為,為兩,個,個步,驟,驟：,通過,迭,迭代,，,，檢,索,索出,事,事務(wù),數(shù),數(shù)據(jù),庫,庫中,的,的所,有,有頻,繁,繁項,集,集，,即,即支,持,持度,不,不低,于,于用,戶,戶設(shè),定,定的,閾,閾值,的,的項,集,集；,利用,頻,頻繁,項,項集,構(gòu),構(gòu)造,出,出滿,足,足用,戶,戶最,小,小信,任,任度,的,的規(guī),則,則。,挖掘,或,或識,別,別出,所,所有,頻,頻繁,項,項集,是,是該,算,算法,的,的核,心,心，,占,占整,個,個計,算,算量,的,的大,部,部分,。,。,頻,繁,繁,

10、項,項,集,集,為,了,了,避,避,免,免,計,計,算,算,所,所,有,有,項,項,集,集,的,的,支,支,持,持,度,度,（,（,實,實,際,際,上,上,頻,頻,繁,繁,項,項,集,集,只,只,占,占,很,很,少,少,一,一,部,部,分,分,）,）,，,，Apriori,算,算,法,法,引,引,入,入,潛,潛,在,在,頻,頻,繁,繁,項,項,集,集,的,的,概,概,念,念,。,。,若,若,潛,潛,在,在,頻,頻,繁,繁,k,項,集,集,的,的,集,集,合,合,記,記,為,為,C,k,，,頻,頻,繁,繁,k,項,集,集,的,的,集,集,合,合,記,記,為,為,L,k,，,m,個,項,項,目,目

11、,構(gòu),構(gòu),成,成,的,的,k,項,集,集,的,的,集,集,合,合,為,為,，,，,則,則,三,三,者,者,之,之,間,間,滿,滿,足,足,關(guān),關(guān),系,系,L,k,C,k,。,構(gòu),構(gòu),成,成,潛,潛,在,在,頻,頻,繁,繁,項,項,集,集,所,所,遵,遵,循,循,的,的,原,原,則,則,是,是,“,“,頻,頻,繁,繁,項,項,集,集,的,的,子,子,集,集,必,必,為,為,頻,頻,繁,繁,項,項,集,集,”,”,。,。,關(guān),聯(lián),聯(lián),規(guī),規(guī),則,則,的,的,性,性,質(zhì),質(zhì),：,：,性,質(zhì),質(zhì)1,：,：,頻,頻,繁,繁,項,項,集,集,的,的,子,子,集,集,必,必,為,為,頻,頻,繁,繁,項,項,

12、集,集,。,。,性,質(zhì),質(zhì)2,：,：,非,非,頻,頻,繁,繁,項,項,集,集,的,的,超,超,集,集,一,一,定,定,是,是,非,非,頻,頻,繁,繁,的,的。,Apriori,算,算,法,法,運,運,用,用,性,性,質(zhì),質(zhì)1,，,，,通,通,過,過,已,已,知,知,的,的,頻,頻,繁,繁,項,項,集,集,構(gòu),構(gòu),成,成,長,長,度,度,更,更,大,大,的,的,項,項,集,集,，,，,并,并,將,將,其,其,稱,稱,為,為,潛,潛,在,在,頻,頻,繁,繁,項,項,集,集,。,。,潛,潛,在,在,頻,頻,繁,繁,k,項,集,集,的,的,集,集,合,合,C,k,是,指,指,由,由,有,有,可,可,能

13、,能,成,成,為,為,頻,頻,繁,繁,k,項,集,集,的,的,項,項,集,集,組,組,成,成,的,的,集,集,合,合,。,。,以,以,后,后,只,只,需,需,計,計,算,算,潛,潛,在,在,頻,頻,繁,繁,項,項,集,集,的,的,支,支,持,持,度,度,，,，,而,而,不,不,必,必,計,計,算,算,所,所,有,有,不,不,同,同,項,項,集,集,的,的,支,支,持,持,度,度,，,，,因,因,此,此,在,在,一,一,定,定,程,程,度,度,上,上,減,減,少,少,了,了,計,計,算,算,量,量,。,。,Apriori,算,算,法,法,(1),L,1,=,頻,頻,繁,繁1,項,項,集,集;,(

14、2)for(,k,=2;,L,k,-1,;,k,+)dobegin,(3),C,k,=apriori_gen(,L,k,-1,);/,新,新,的,的,潛,潛,在,在,頻,頻,繁,繁,項,項,集,集,(4)forall,transactionst,D,dobegin,(5),C,t,=subset(,C,k,t,);/t,中,中,包,包,含,含,的,的,潛,潛,在,在,頻,頻,繁,繁,項,項,集,集,(6)forall,candidatesc,C,t,do,(7),c,.,count,+;,(8)end;,(9)L,k,=c,C,k,|c.count,minsup,(10)end;,(11)An

15、swer=,實,例,例,DatabaseTDB,1,st,scan,C,1,L,1,L,2,C,2,C,2,2,nd,scan,C,3,L,3,3,rd,scan,Tid,Items,10,A,C,D,20,B,C,E,30,A,B,C,E,40,B,E,Itemset,sup,A,2,B,3,C,3,D,1,E,3,Itemset,sup,A,2,B,3,C,3,E,3,Itemset,A,B,A,C,A,E,B,C,B,E,C,E,Itemset,sup,A,B,1,A,C,2,A,E,1,B,C,2,B,E,3,C,E,2,Itemset,sup,A,C,2,B,C,2,B,E,3,C,

16、E,2,Itemset,B,C,E,Itemset,sup,B,C,E,2,VisualizationofAssociationRules:PaneGraph,VisualizationofAssociationRules:RuleGraph,提,高,高Apriori,算,算,法,法,的,的,方,方,法,法,Hash-baseditemsetcounting,（,（,散,散,列,列,項,項,集,集,計,計,數(shù),數(shù),）,）,Transactionreduction,（,（,事,事,務(wù),務(wù),壓,壓,縮,縮,）,）,Partitioning,（,（,劃,劃,分,分,）,）,Sampling,（,（,采,采,樣,樣,）,）,關(guān),聯(lián),聯(lián),規(guī),規(guī),則,則,挖,挖,掘,掘,算,算,法,法,Agrawal,等,等,人,人,提,提,出,出,的,的AIS,，,，Apriori,和,和AprioriTid,Cumulate,和,和Stratify,，,，Houstsma,等,等,人,人,提,提,出,出,的,的SETM,Park,等,等,人,人,提,提,出,出,的,的DHP,Savasere,等,等,人,人,