數據挖掘導論之頻繁模式及關聯規(guī)則挖掘技術(一)

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,第3課,頻繁模式及關聯規(guī)則挖掘技術,徐從富，,副教授,浙江大學人工智能研究所,浙江大學本科生數據挖掘導論課件,內容提綱,關聯規(guī)則挖掘簡介,關聯規(guī)則基本模型,關聯規(guī)則價值衡量與發(fā)展,參考文獻,關聯規(guī)則簡介,關聯規(guī)則反映一個事物與其他事物之間的相互依存性和關聯性。如果兩個或者多個事物之間存在一定的關聯關系，那么，其中一個事物就能夠通過其他事物預測到。,典型的關聯規(guī)則發(fā)現問題是對超市中的貨籃數據（Market Basket）進行分析。通過發(fā)現顧客放入貨籃中的不同商品之間的關系來分析顧客的購買習慣。,什么是關聯規(guī)則挖掘,關聯規(guī)則挖掘,首先被Agrawal,Imielinski and Swami在1993年的SIGMOD會議上提出,在事務、關系數據庫中的項集和對象中發(fā)現頻繁模式、關聯規(guī)則、相關性或者因果結構,頻繁模式,:數據庫中頻繁出現的項集,目的:發(fā)現數據中的規(guī)律,超市數據中的什么產品會一起購買？啤酒和尿布,在買了一臺PC之后下一步會購買?,哪種DNA對這種藥物敏感?,我們如何自動對Web文檔進行分類?,頻繁模式挖掘的重要性,許多重要數據挖掘任務的基礎,關聯、相關性、因果性,序列模式、空間模式、時間模式、多維,關聯分類、聚類分析,更加廣泛的用處,購物籃分析、交叉銷售、直銷,點擊流分析、DNA序列分析等等,關聯規(guī)則基本模型,關聯規(guī)則基本模型,Apriori算法,Fp-Tree算法,關聯規(guī)則基本模型,IBM公司Almaden研究中心的R.Agrawal首先提出關聯規(guī)則模型，并給出求解算法AIS。隨后又出現了SETM和Apriori等算法。其中，Apriori是關聯規(guī)則模型中的經典算法。,給定一組事務,產生所有的關聯規(guī)則,滿足最小支持度和最小可信度,關聯規(guī)則基本模型（續(xù)）,設,I,=,i,1,i,2,i,m,為所有項目的集合，,D,為事務數據庫，事務,T,是一個項目子集（,T,I,）。每一個事務具有唯一的事務標識,TID,。設,A,是一個由項目構成的集合，稱為項集。事務,T,包含項集,A,，當且僅當,A,T,。如果項集,A,中包含,k,個項目，則稱其為,k,項集。項集,A,在事務數據庫,D,中出現的次數占,D,中總事務的百分比叫做項集的支持度。如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集（或大項集）。,關聯規(guī)則基本模型（續(xù)）,關聯規(guī)則是形如,X,Y,的邏輯蘊含式，其中,X,I,，,Y,I,，且,X,Y,=,。如果事務數據庫,D,中有,s,%的事務包含,X,Y,，則稱關聯規(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,一,一次,交,交易,中,中包,含,含X,、,、Y,、,、Z,的,的可能,性,性,可信,度,度,c,包含X,、,、Y的,交,交易,中,中也,包,包含,Z,的條件,概,概率,設最,小,小支,持,持度,為,為50%,最,最小,可,可信,度,度為50%,則,則可,得,得到,A,C,(50%,66.6%),C,A,(50%,100%),買尿,布,布的,客,客戶,二者,都,都買,的,的客,戶,戶,買啤,酒,酒的,客,客戶,關聯,規(guī),規(guī)則,基,基本,模,模型,（,（續(xù),）,）,關聯,規(guī),規(guī)則,就,就是,支,支持,度,度和,信,信任,度,度分,別,別滿,足,足用,戶,戶給,定,定閾,值,值的,規(guī),規(guī)則,。,。,發(fā)現,關,關聯,規(guī),規(guī)則,需,需要,經,經歷,如,如下,兩,兩個,步,步驟,：,：,找出,所,所有,頻,頻繁,項,項集,。,。,由頻,繁,繁項,集,集生,成,成滿,足,足最,小,小信,任,任度,閾,閾值,的,的規(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,:,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算,法,法命,名,名源,于,于算,法,法使,用,用了,頻,頻繁,項,項集,性,性質,的,的先,驗,驗（Prior）,知,知識,。,。,Apriori算,法,法將,發(fā),發(fā)現,關,關聯,規(guī),規(guī)則,的,的過,程,程分,為,為兩,個,個步,驟,驟：,通過,迭,迭代,，,，檢,索,索出,事,事務,數,數據,庫,庫中,的,的所,有,有頻,繁,繁項,集,集，,即,即支,持,持度,不,不低,于,于用,戶,戶設,定,定的,閾,閾值,的,的項,集,集；,利用,頻,頻繁,項,項集,構,構造,出,出滿,足,足用,戶,戶最,小,小信,任,任度,的,的規(guī),則,則。,挖掘,或,或識,別,別出,所,所有,頻,頻繁,項,項集,是,是該,算,算法,的,的核,心,心，,占,占整,個,個計,算,算量,的,的大,部,部分,。,。,頻,繁,繁,項,項,集,集,為,了,了,避,避,免,免,計,計,算,算,所,所,有,有,項,項,集,集,的,的,支,支,持,持,度,度,（,（,實,實,際,際,上,上,頻,頻,繁,繁,項,項,集,集,只,只,占,占,很,很,少,少,一,一,部,部,分,分,）,）,，,，Apriori,算,算,法,法,引,引,入,入,潛,潛,在,在,頻,頻,繁,繁,項,項,集,集,的,的,概,概,念,念,。,。,若,若,潛,潛,在,在,頻,頻,繁,繁,k,項,集,集,的,的,集,集,合,合,記,記,為,為,C,k,，,頻,頻,繁,繁,k,項,集,集,的,的,集,集,合,合,記,記,為,為,L,k,，,m,個,項,項,目,目,構,構,成,成,的,的,k,項,集,集,的,的,集,集,合,合,為,為,，,，,則,則,三,三,者,者,之,之,間,間,滿,滿,足,足,關,關,系,系,L,k,C,k,。,構,構,成,成,潛,潛,在,在,頻,頻,繁,繁,項,項,集,集,所,所,遵,遵,循,循,的,的,原,原,則,則,是,是,“,“,頻,頻,繁,繁,項,項,集,集,的,的,子,子,集,集,必,必,為,為,頻,頻,繁,繁,項,項,集,集,”,”,。,。,關,聯,聯,規(guī),規(guī),則,則,的,的,性,性,質,質,：,：,性,質,質1,：,：,頻,頻,繁,繁,項,項,集,集,的,的,子,子,集,集,必,必,為,為,頻,頻,繁,繁,項,項,集,集,。,。,性,質,質2,：,：,非,非,頻,頻,繁,繁,項,項,集,集,的,的,超,超,集,集,一,一,定,定,是,是,非,非,頻,頻,繁,繁,的,的。,Apriori,算,算,法,法,運,運,用,用,性,性,質,質1,，,，,通,通,過,過,已,已,知,知,的,的,頻,頻,繁,繁,項,項,集,集,構,構,成,成,長,長,度,度,更,更,大,大,的,的,項,項,集,集,，,，,并,并,將,將,其,其,稱,稱,為,為,潛,潛,在,在,頻,頻,繁,繁,項,項,集,集,。,。,潛,潛,在,在,頻,頻,繁,繁,k,項,集,集,的,的,集,集,合,合,C,k,是,指,指,由,由,有,有,可,可,能,能,成,成,為,為,頻,頻,繁,繁,k,項,集,集,的,的,項,項,集,集,組,組,成,成,的,的,集,集,合,合,。,。,以,以,后,后,只,只,需,需,計,計,算,算,潛,潛,在,在,頻,頻,繁,繁,項,項,集,集,的,的,支,支,持,持,度,度,，,，,而,而,不,不,必,必,計,計,算,算,所,所,有,有,不,不,同,同,項,項,集,集,的,的,支,支,持,持,度,度,，,，,因,因,此,此,在,在,一,一,定,定,程,程,度,度,上,上,減,減,少,少,了,了,計,計,算,算,量,量,。,。,Apriori,算,算,法,法,(1),L,1,=,頻,頻,繁,繁1,項,項,集,集;,(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)Answer=,實,例,例,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,E,2,Itemset,B,C,E,Itemset,sup,B,C,E,2,VisualizationofAssociationRules:PaneGraph,VisualizationofAssociationRules:RuleGraph,提,高,高Apriori,算,算,法,法,的,的,方,方,法,法,Hash-baseditemsetcounting,（,（,散,散,列,列,項,項,集,集,計,計,數,數,）,）,Transactionreduction,（,（,事,事,務,務,壓,壓,縮,縮,）,）,Partitioning,（,（,劃,劃,分,分,）,）,Sampling,（,（,采,采,樣,樣,）,）,關,聯,聯,規(guī),規(guī),則,則,挖,挖,掘,掘,算,算,法,法,Agrawal,等,等,人,人,提,提,出,出,的,的AIS,，,，Apriori,和,和AprioriTid,Cumulate,和,和Stratify,，,，Houstsma,等,等,人,人,提,提,出,出,的,的SETM,Park,等,等,人,人,提,提,出,出,的,的DHP,Savasere,等,等,人,人,