1、沃爾瑪，沃爾瑪，請把蛋撻與颶風(fēng)用品擺在請把蛋撻與颶風(fēng)用品擺在一起一起通過對通過對歷史交易記錄這個龐大數(shù)據(jù)庫進行歷史交易記錄這個龐大數(shù)據(jù)庫進行觀察，沃爾瑪注意到，每當季節(jié)性颶風(fēng)來觀察，沃爾瑪注意到，每當季節(jié)性颶風(fēng)來臨之前，不僅手電筒銷量增加，而且美式臨之前，不僅手電筒銷量增加，而且美式早餐含糖零食蛋撻銷量也增加早餐含糖零食蛋撻銷量也增加了。了。因此每當季節(jié)性颶風(fēng)來臨時因此每當季節(jié)性颶風(fēng)來臨時，沃爾瑪就會，沃爾瑪就會把蛋撻與颶風(fēng)用品擺放在一起，從而增加把蛋撻與颶風(fēng)用品擺放在一起，從而增加銷量。銷量。2案例回顧案例回顧尿不濕和啤酒尿不濕和啤酒超級商業(yè)零售連鎖巨無霸沃爾瑪公司超級商業(yè)零售連鎖巨無霸沃爾

2、瑪公司(Wal Mart)擁有世上最大的數(shù)據(jù)倉庫系統(tǒng)之一。為擁有世上最大的數(shù)據(jù)倉庫系統(tǒng)之一。為了能夠準確了解顧客在其門店的購買習(xí)慣，沃了能夠準確了解顧客在其門店的購買習(xí)慣，沃爾瑪對其顧客的購物行為進行了購物籃關(guān)聯(lián)規(guī)爾瑪對其顧客的購物行為進行了購物籃關(guān)聯(lián)規(guī)則分析，從而知道顧客經(jīng)常一起購買的商品有則分析，從而知道顧客經(jīng)常一起購買的商品有哪些。哪些。跟尿不濕一起購買最多的商品竟是啤酒跟尿不濕一起購買最多的商品竟是啤酒”!這這是數(shù)據(jù)挖掘技術(shù)對歷史數(shù)據(jù)進行分析的結(jié)果，是數(shù)據(jù)挖掘技術(shù)對歷史數(shù)據(jù)進行分析的結(jié)果，反映的是數(shù)據(jù)的內(nèi)在規(guī)律。反映的是數(shù)據(jù)的內(nèi)在規(guī)律。那么這個結(jié)果符合現(xiàn)實情況嗎那么這個結(jié)果符合現(xiàn)實情況

3、嗎?是否是一個有是否是一個有用的知識？是否有利用價值？用的知識？是否有利用價值？3尿不濕和啤酒尿不濕和啤酒經(jīng)過大量實際調(diào)查和分析，他們揭示了一個隱藏在經(jīng)過大量實際調(diào)查和分析，他們揭示了一個隱藏在“尿不濕與啤酒尿不濕與啤酒”背后的美國消費者的一種行為模式：背后的美國消費者的一種行為模式：在美國，到超市去買嬰兒尿不濕是一些年輕的父親下班后的日常工在美國，到超市去買嬰兒尿不濕是一些年輕的父親下班后的日常工作，而他們中有作，而他們中有30%40%的人同時也會為自己買一些啤酒。產(chǎn)生的人同時也會為自己買一些啤酒。產(chǎn)生這一現(xiàn)象的原因是：美國的太太們常叮囑她們的丈夫不要忘了下班這一現(xiàn)象的原因是：美國的太太們常

4、叮囑她們的丈夫不要忘了下班后為小孩買尿不濕，而丈夫們在買尿不濕后又隨手帶回了他們喜歡后為小孩買尿不濕，而丈夫們在買尿不濕后又隨手帶回了他們喜歡的啤酒。另一種情況是丈夫們在買啤酒時突然記起他們的責(zé)任，又的啤酒。另一種情況是丈夫們在買啤酒時突然記起他們的責(zé)任，又去買了尿不濕。既然尿不濕與啤酒一起被購買的機會很多，那么沃去買了尿不濕。既然尿不濕與啤酒一起被購買的機會很多，那么沃爾瑪就在他們所有的門店里將尿不濕與啤酒并排擺放在一起，結(jié)果爾瑪就在他們所有的門店里將尿不濕與啤酒并排擺放在一起，結(jié)果是得到了尿不濕與啤酒的銷售量雙雙增長。是得到了尿不濕與啤酒的銷售量雙雙增長。按常規(guī)思維，尿不濕與啤酒風(fēng)馬牛不相

5、及，若不是借助數(shù)據(jù)挖掘技按常規(guī)思維，尿不濕與啤酒風(fēng)馬牛不相及，若不是借助數(shù)據(jù)挖掘技術(shù)對大量交易數(shù)據(jù)進行挖掘分析，沃爾瑪是不可能發(fā)現(xiàn)數(shù)據(jù)內(nèi)這一術(shù)對大量交易數(shù)據(jù)進行挖掘分析，沃爾瑪是不可能發(fā)現(xiàn)數(shù)據(jù)內(nèi)這一有價值的規(guī)律的。有價值的規(guī)律的。4美國一名男子闖入他家附近的一家美國一名男子闖入他家附近的一家美國零售連鎖超市美國零售連鎖超市Target店鋪店鋪(美國美國第三大零售商塔吉特第三大零售商塔吉特)進行抗議：進行抗議：“你們竟然給我你們竟然給我17歲的女兒發(fā)嬰兒尿歲的女兒發(fā)嬰兒尿片和童車的優(yōu)惠券。片和童車的優(yōu)惠券。”店鋪經(jīng)理立刻向來者承認錯誤，但店鋪經(jīng)理立刻向來者承認錯誤，但是其實該經(jīng)理并不知道這一行為

6、是是其實該經(jīng)理并不知道這一行為是總公司運行數(shù)據(jù)挖掘的結(jié)果。如圖總公司運行數(shù)據(jù)挖掘的結(jié)果。如圖所示。一個月后，這位父親來道歉，所示。一個月后，這位父親來道歉，因為這時他才知道他的女兒的確懷因為這時他才知道他的女兒的確懷孕了。孕了。Target比這位父親知道他女兒比這位父親知道他女兒懷孕的時間足足早了一個月。懷孕的時間足足早了一個月。5美國折扣零售商塔吉特與懷孕預(yù)測美國折扣零售商塔吉特與懷孕預(yù)測美國折扣零售商塔吉特與懷孕預(yù)測美國折扣零售商塔吉特與懷孕預(yù)測塔吉特公司塔吉特公司能能在在不被清楚告知的情況下預(yù)測出一個女性不被清楚告知的情況下預(yù)測出一個女性的懷孕的懷孕情況情況該公司找出了大概該公司找出了大

7、概20多種與懷孕的關(guān)聯(lián)多種與懷孕的關(guān)聯(lián)物，給顧客進行物，給顧客進行“懷孕趨勢懷孕趨勢”評分評分這些這些數(shù)據(jù)甚至使得零售商能夠比較準確地預(yù)測預(yù)產(chǎn)期，數(shù)據(jù)甚至使得零售商能夠比較準確地預(yù)測預(yù)產(chǎn)期，這樣就能夠在孕期的每個階段給客戶寄送相應(yīng)的優(yōu)惠券這樣就能夠在孕期的每個階段給客戶寄送相應(yīng)的優(yōu)惠券Target能夠通過分析女性客戶購買記錄，能夠通過分析女性客戶購買記錄，“猜出猜出”哪些哪些是孕婦。他們從是孕婦。他們從Target的數(shù)據(jù)倉庫中挖掘出的數(shù)據(jù)倉庫中挖掘出25項與懷孕項與懷孕高度相關(guān)的商品，制作高度相關(guān)的商品，制作“懷孕預(yù)測懷孕預(yù)測”指數(shù)。比如他們發(fā)指數(shù)。比如他們發(fā)現(xiàn)女性會在懷孕四個月左右，大量購買

8、無香味乳液。以現(xiàn)女性會在懷孕四個月左右，大量購買無香味乳液。以此為依據(jù)推算出預(yù)產(chǎn)期后，就搶先一步將孕婦裝、嬰兒此為依據(jù)推算出預(yù)產(chǎn)期后，就搶先一步將孕婦裝、嬰兒床等折扣券寄給客戶來吸引客戶購買。床等折扣券寄給客戶來吸引客戶購買。6大數(shù)據(jù)分析核心手段、技術(shù)數(shù)據(jù)處理數(shù)據(jù)挖掘模型預(yù)測概念概念數(shù)據(jù)挖掘數(shù)據(jù)挖掘(Data Mining) (Data Mining) 是通過分析每個數(shù)據(jù)，從大量是通過分析每個數(shù)據(jù)，從大量數(shù)據(jù)中尋找其規(guī)律的技術(shù)，主要有數(shù)據(jù)準備、規(guī)律尋找數(shù)據(jù)中尋找其規(guī)律的技術(shù)，主要有數(shù)據(jù)準備、規(guī)律尋找和規(guī)律表示和規(guī)律表示3 3個步驟。個步驟。 數(shù)據(jù)挖掘的任務(wù)數(shù)據(jù)挖掘的任務(wù)有關(guān)聯(lián)分析、聚類分析、分

9、類分析、異有關(guān)聯(lián)分析、聚類分析、分類分析、異常分析、特異群組分析和演變分析等。常分析、特異群組分析和演變分析等。關(guān)聯(lián)分析關(guān)聯(lián)分析是指如果兩個或多個事物之間存在一定的關(guān)聯(lián)是指如果兩個或多個事物之間存在一定的關(guān)聯(lián), ,那么其中一個事物就能通過其他事物進行預(yù)測那么其中一個事物就能通過其他事物進行預(yù)測. .它的目的它的目的是為了挖掘隱藏在數(shù)據(jù)間的相互關(guān)系是為了挖掘隱藏在數(shù)據(jù)間的相互關(guān)系 。典型的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題是對超市中的貨典型的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題是對超市中的貨籃數(shù)據(jù)（籃數(shù)據(jù)（Market Basket）進行分析。通過）進行分析。通過發(fā)現(xiàn)顧客放入貨籃中的不同商品之間的關(guān)發(fā)現(xiàn)顧客放入貨籃中的不同商品之間的

10、關(guān)系來分析顧客的購買習(xí)慣。系來分析顧客的購買習(xí)慣。數(shù)據(jù)關(guān)聯(lián)數(shù)據(jù)關(guān)聯(lián) 經(jīng)典案例：經(jīng)典案例：沃爾瑪?shù)钠【坪湍虿嫉墓适挛譅柆數(shù)钠【坪湍虿嫉墓适玛P(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則購物籃分析購物籃分析“啤酒和尿布啤酒和尿布”的故事是營銷屆的神話，的故事是營銷屆的神話，“啤酒啤酒”和和“尿布尿布”兩個看上去沒有關(guān)系的兩個看上去沒有關(guān)系的商品擺放在一起進行銷售、并獲得了很好的商品擺放在一起進行銷售、并獲得了很好的銷售收益，這種現(xiàn)象就是賣場中商品之間的銷售收益，這種現(xiàn)象就是賣場中商品之間的關(guān)聯(lián)性。關(guān)聯(lián)性。 研究研究“啤酒與尿布啤酒與尿布”關(guān)聯(lián)的方法就是購物關(guān)聯(lián)的方法就是購物籃分析，購物籃分析是沃爾瑪秘而不宣的獨籃分析，購物籃分

11、析是沃爾瑪秘而不宣的獨門武器，購物籃分析可以幫助我們在門店的門武器，購物籃分析可以幫助我們在門店的銷售過程中找到具有銷售過程中找到具有關(guān)聯(lián)關(guān)系關(guān)聯(lián)關(guān)系的商品，并以的商品，并以此獲得銷售收益的增長！此獲得銷售收益的增長！ 關(guān)聯(lián)規(guī)則挖掘（Association Rule）在數(shù)據(jù)挖掘的知識模式中，關(guān)聯(lián)規(guī)則模式是比較重要的一種。關(guān)聯(lián)規(guī)則的概念由Agrawal、Imielinski、Swami 提出，是數(shù)據(jù)中一種簡單但很實用的規(guī)則。在數(shù)據(jù)庫的知識發(fā)現(xiàn)中，關(guān)聯(lián)規(guī)則就是描述這種在一個事務(wù)中物品之間同時出現(xiàn)的規(guī)律的知識模式。更確切的說，關(guān)聯(lián)規(guī)則通過量化的數(shù)字描述物品甲的出現(xiàn)對物品乙的出現(xiàn)有多大的影響現(xiàn)實中，這

12、樣的例子很多。l例如超級市場利用前端收款機收集存儲了大量的售貨數(shù)據(jù)，這些數(shù)據(jù)是一條條的購買事務(wù)記錄，每條記錄存儲了l事務(wù)處理時間，l顧客購買的物品、l物品的數(shù)量及金額等。l 這些數(shù)據(jù)中常常隱含形式如下的關(guān)聯(lián)規(guī)則：在購買鐵錘的顧客當中，有70 的人同時購買了鐵釘。l 這些關(guān)聯(lián)規(guī)則很有價值，商場管理人員可以根據(jù)這些關(guān)聯(lián)規(guī)則更好地規(guī)劃商場，如把鐵錘和鐵釘這樣的商品擺放在一起，能夠促進銷售。關(guān)聯(lián)規(guī)則分析拓展1）商業(yè)銷售商業(yè)銷售上，如何通過交叉銷售得到更大的收入？2）保險方面保險方面，如何分析索賠要求發(fā)現(xiàn)潛在的欺詐行為？3）銀行方面銀行方面，如何分析顧客消費行業(yè)，以便有針對性地向其推薦感興趣的服務(wù)？4）

13、哪些制造零件和設(shè)備設(shè)置與故障事件故障事件關(guān)聯(lián)？5）哪些病人和藥物藥物屬性與結(jié)果關(guān)聯(lián)？6）哪些商品商品是已經(jīng)購買商品A的人最有可能購買的？l如何從交易記錄數(shù)據(jù)庫或關(guān)系數(shù)據(jù)庫的大量數(shù)如何從交易記錄數(shù)據(jù)庫或關(guān)系數(shù)據(jù)庫的大量數(shù)據(jù)中挖掘出關(guān)聯(lián)規(guī)則知識據(jù)中挖掘出關(guān)聯(lián)規(guī)則知識？l什么樣的關(guān)聯(lián)規(guī)則才是最有意義的什么樣的關(guān)聯(lián)規(guī)則才是最有意義的？l如何才能幫助挖掘過程盡快發(fā)現(xiàn)有價值的關(guān)聯(lián)如何才能幫助挖掘過程盡快發(fā)現(xiàn)有價值的關(guān)聯(lián)知識知識？問題問題關(guān)聯(lián)規(guī)則基本概念項目（item）：其中的B C M T 都稱作item。項集（itemset）:item的集合，例如B C、C M T等，每個顧客購買的都是一個項集。其中，

14、項集中item的個數(shù)稱為項集的長度，含有k個item的項集成為K-itemset.交易（transaction）：定義I為所有商品的集合，在這個例子中I=B C M T。每個非空的I子集都成為一個交易。所有交易構(gòu)成交易數(shù)據(jù)庫D。交易ID（TID）購買商品（Items）B：bread C:cream M:milk T:teaT01 B C M TT02 B C MT03 C MT04 M TT05 B C MT06 B TT07 B M TT08 B TT09 B C M TT10 B M T關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則設(shè)I=i1,i2,im是項（Item）的集合。記D為事務(wù)（Transaction）的集合

15、（事務(wù)數(shù)據(jù)庫），事務(wù)T是項的集合，并且T I。設(shè)A是I中一個項集，如果A T，那么稱事務(wù)T包含A。定義1：關(guān)聯(lián)規(guī)則是形如AB的蘊涵式，這里A I，B I，并且A B= 。度量規(guī)則的指標支持度（）可信度（）作用度/興趣度（）支持度定義2：規(guī)則的支持度。支持度描述了A 和B 這兩個物品集在所有的事務(wù)中同時出現(xiàn)的概率有多大。規(guī)則AB在數(shù)據(jù)庫D中具有支持度S，即概率P(AB)，即： 其中|D|表示事務(wù)數(shù)據(jù)庫D的個數(shù)，表示A、B兩個項集同時發(fā)生的事務(wù)個數(shù)。|D|AB| P(AB)B) (A SCustomerbuys diaperCustomerbuys bothCustomerbuys beer可信度

16、定義3：規(guī)則的可信度可信度就是指在出現(xiàn)了物品集A 的事務(wù)T 中，物品集B 也同時出現(xiàn)的概率規(guī)則AB具有可信度C，表示C是條件概率P(B|A)，即： 其中 表示數(shù)據(jù)庫中包含項集A的事務(wù)個數(shù)。 |A|AB|)|()BA(ABPC|A|小結(jié)可信度是對關(guān)聯(lián)規(guī)則的準確度準確度的衡量，支持度是對關(guān)聯(lián)規(guī)則重要性重要性的衡量。支持度說明了這條規(guī)則在所有事務(wù)中有多大的代表性。顯然支持度越大，關(guān)聯(lián)規(guī)則越重要。有些關(guān)聯(lián)規(guī)則可信度雖然很高，但支持度卻很低，說明該關(guān)聯(lián)規(guī)則實用的機會很小，因此也不重要。 理解：關(guān)聯(lián)分析中的三個重要的概念理解：關(guān)聯(lián)分析中的三個重要的概念 舉例：舉例：1000010000個人購買了產(chǎn)品，其中

17、購買個人購買了產(chǎn)品，其中購買A A產(chǎn)品的人是產(chǎn)品的人是10001000個，購個，購買買B B產(chǎn)品的人是產(chǎn)品的人是20002000個，個，ABAB同時購買的人是同時購買的人是800800個。個。支持度支持度指的是關(guān)聯(lián)的產(chǎn)品（假定指的是關(guān)聯(lián)的產(chǎn)品（假定A A產(chǎn)品和產(chǎn)品和B B產(chǎn)品關(guān)聯(lián)）同時購產(chǎn)品關(guān)聯(lián)）同時購買的人數(shù)占總?cè)藬?shù)的比例，即買的人數(shù)占總?cè)藬?shù)的比例，即800/10000=8%800/10000=8%，有，有8%8%的用戶的用戶同時購買了同時購買了A A和和B B兩個產(chǎn)品；兩個產(chǎn)品； 可信度可信度指的是在購買了一個產(chǎn)品之后購買另外一個產(chǎn)品的可能指的是在購買了一個產(chǎn)品之后購買另外一個產(chǎn)品的可能性

18、，如購買了性，如購買了A A產(chǎn)品之后購買產(chǎn)品之后購買B B產(chǎn)品的可信度產(chǎn)品的可信度=800/1000=80% =800/1000=80% 支持度支持度可信度可信度作用度（興趣度）討論兩種事務(wù)的比較關(guān)系 AB作用度是兩種可能性的比較，描述物品集A 的出現(xiàn)對物品集B 的出現(xiàn)有多大的影響。定義定義4：興趣度：興趣度： 公式反映了項集公式反映了項集A與項集與項集B的相關(guān)程度。的相關(guān)程度。若若 即即 表示表示項集項集A出現(xiàn)和項集出現(xiàn)和項集B是相互獨立的。是相互獨立的。若若 表示表示A出現(xiàn)和出現(xiàn)和B出現(xiàn)是負相關(guān)的。出現(xiàn)是負相關(guān)的。若若 表示表示A出現(xiàn)和出現(xiàn)和B出現(xiàn)是正相關(guān)的。意味著出現(xiàn)是正相關(guān)的。意味著A

19、的出現(xiàn)的出現(xiàn)蘊含蘊含B的出現(xiàn)。的出現(xiàn)。()()( ) ( )P ABI ABP A P B () 1I AB )()()(BPAPABPI(A) 1B一條規(guī)則的興趣度越大于1說明我們對這條規(guī)則越感興趣（即其實際利用價值越大）；一條規(guī)則的興趣度越小于1說明我們對這條規(guī)則的反面規(guī)則越感興趣（即其反面規(guī)則的實際利用價值越大）；興趣度I不小于0。 例設(shè)交易集D，經(jīng)過對D的分析，得到表格:買咖啡買咖啡不買咖啡不買咖啡合計合計買牛奶買牛奶20525不買牛奶不買牛奶70575合計合計9010100所有可能的關(guān)聯(lián)規(guī)則 Rules SCI1 買牛奶買咖啡0.20.80.89 2買咖啡買牛奶 0.20.220.8

20、9 3買牛奶不買咖啡0.050.224不買咖啡買牛奶0.050.525不買牛奶買咖啡0.70.931.0376買咖啡不買牛奶0.70.781.0377不買牛奶不買咖啡0.050.0670.678不買咖啡不買牛奶0.050.20.87討論討論I1I2I3I6共共4條規(guī)則：條規(guī)則：由于由于I1,I21,規(guī)則才有價值。規(guī)則才有價值。興趣度也稱為作用度（興趣度也稱為作用度（Lift）,表示關(guān)聯(lián)規(guī)表示關(guān)聯(lián)規(guī)則則AB的的“提升提升”。如果作用度（興趣度）。如果作用度（興趣度）不大于不大于1，則此關(guān)聯(lián)規(guī)則就沒有意義了。，則此關(guān)聯(lián)規(guī)則就沒有意義了。 小結(jié)作用度描述了物品集A 對物品集B 的影響力的大小。作用度

21、越大，說明物品集B 受物品集A 的影響越大。一般情況，有用的關(guān)聯(lián)規(guī)則的作用度都應(yīng)該大于1，說明A 的出現(xiàn)對B 的出現(xiàn)有促進作用，也說明了它們之間某種程度的相關(guān)性，如果作用度不大于1，則此關(guān)聯(lián)規(guī)則也就沒有意義了。關(guān)聯(lián)規(guī)則挖掘在關(guān)聯(lián)規(guī)則的三個屬性中，支持度和可信度能夠比較直接形容關(guān)聯(lián)規(guī)則的性質(zhì)事實上，人們一般只對滿足一定的支持度和可信度的關(guān)聯(lián)規(guī)則感興趣。因此，為了發(fā)現(xiàn)有意義的關(guān)聯(lián)規(guī)則，需要由用戶給定兩個閾值： 最小支持度（min_sup）和最小可信度（min_conf）頻繁項集如果項集滿足最小支持度，則它稱之為頻繁項集（Frequent Itemset）。 強規(guī)則定義定義5：強關(guān)聯(lián)規(guī)則。同時滿足最

22、小支持度（min_sup）和最小可信度（min_conf）的規(guī)則稱之為強關(guān)聯(lián)規(guī)則，即成立時，規(guī)則稱之為強關(guān)聯(lián)強關(guān)聯(lián)規(guī)則規(guī)則，否則稱為弱關(guān)聯(lián)弱關(guān)聯(lián)規(guī)則規(guī)則。數(shù)據(jù)挖掘主要就是對強規(guī)則的挖掘數(shù)據(jù)挖掘主要就是對強規(guī)則的挖掘。min_confB) (A min_supB) (A CS且3. 關(guān)聯(lián)規(guī)則挖掘過程關(guān)聯(lián)規(guī)則挖掘過程關(guān)聯(lián)規(guī)則的挖掘一般分為兩個過程：（1）找出所有的頻繁項集）找出所有的頻繁項集：找出支持度大于最小支持度的項集，即頻繁項集。（2）由頻繁項集）由頻繁項集產(chǎn)生（強）關(guān)聯(lián)產(chǎn)生（強）關(guān)聯(lián)規(guī)則規(guī)則：根據(jù)定義，這些規(guī)則必須滿足最小支持度和最小可信度。35Step one: 頻繁項集項集項集 - 任

23、意項的集合任意項的集合k-項集項集 - 包含包含k個項的項集個項的項集頻繁項集頻繁項集 - 滿足最小支持度的項集滿足最小支持度的項集若若I包含包含m個項個項,那么可以產(chǎn)生多少個項集那么可以產(chǎn)生多少個項集?36Step two:強關(guān)聯(lián)規(guī)則給定一個項集給定一個項集,容易生成關(guān)聯(lián)規(guī)則容易生成關(guān)聯(lián)規(guī)則.項集項集: Chips, Salsa, Beer Beer, Chips = Salsa Beer, Salsa = Chips Chips, Salsa = Beer強強規(guī)則規(guī)則強規(guī)則通常定義為那些滿足最小支持度和最小可信強規(guī)則通常定義為那些滿足最小支持度和最小可信度的規(guī)則度的規(guī)則.保留滿足最小可信度

24、的規(guī)則保留滿足最小可信度的規(guī)則4 Apriori算法基本思想算法基本思想Apriori是挖掘關(guān)聯(lián)規(guī)則的一個重要方法。算法分為兩個子問題：1、找到所有支持度大于最小支持度的項集（Itemset），這些項集稱為頻繁集（Frequent Itemset）。2、使用第1步找到的頻繁集產(chǎn)生規(guī)則。 Apriori 使用一種稱作逐層搜索的迭代方法，使用一種稱作逐層搜索的迭代方法，“K-項集項集”用于探索用于探索“K+1-項集項集”。首先，找出頻繁首先，找出頻繁“1-項集項集”的集合。該集的集合。該集合記作合記作L1。L1用于找頻繁用于找頻繁“2-項集項集”的集的集合合L2，而，而L2用于找用于找L3，如此下

25、去，直到不能找到如此下去，直到不能找到“K-項集項集”。找。找每個每個LK需要一次數(shù)據(jù)庫掃描。需要一次數(shù)據(jù)庫掃描。Apriori 算法中候選項集算法中候選項集 與頻繁項集的產(chǎn)生實例與頻繁項集的產(chǎn)生實例事務(wù)ID事務(wù)的項目集T1A,B,ET2B,DT3B,CT4A,B,DT5A,CT6B,CT7A,CT8A,B,C,ET9A,B,C1) 在算法的第一次迭代，每個項都是候選1-項集的集合C1的成員。算法掃描所有的事務(wù)，對每個項的出現(xiàn)次數(shù)計數(shù)。見圖中第1列。2) 假定最小事務(wù)支持計數(shù)為2（即min-sup=2/9=22%），可以確定頻繁1-項集的集合L1。它由具有最小支持度的候選1-項集組成。見圖中第2列。3) 為發(fā)現(xiàn)頻繁2-項集的集合L2，算法使用L1*L1來產(chǎn)生候選集C2。見圖中第3列。4) 掃描D中事務(wù)，計算C2中每個候選項集的支持度計數(shù)，如圖中的