關(guān)聯(lián)規(guī)則挖掘

1、大數(shù)據(jù)挖掘の關(guān)聯(lián)分析,沃爾瑪，請把蛋撻與颶風(fēng)用品擺在一起,通過對歷史交易記錄這個龐大數(shù)據(jù)庫進行觀察，沃爾瑪注意到，每當季節(jié)性颶風(fēng)來臨之前，不僅手電筒銷量增加，而且美式早餐含糖零食蛋撻銷量也增加了。因此每當季節(jié)性颶風(fēng)來臨時，沃爾瑪就會把蛋撻與颶風(fēng)用品擺放在一起，從而增加銷量。,2,案例回顧,尿不濕和啤酒,超級商業(yè)零售連鎖巨無霸沃爾瑪公司(Wal Mart)擁有世上最大的數(shù)據(jù)倉庫系統(tǒng)之一。為了能夠準確了解顧客在其門店的購買習(xí)慣，沃爾瑪對

2、其顧客的購物行為進行了購物籃關(guān)聯(lián)規(guī)則分析，從而知道顧客經(jīng)常一起購買的商品有哪些。跟尿不濕一起購買最多的商品竟是啤酒”!這是數(shù)據(jù)挖掘技術(shù)對歷史數(shù)據(jù)進行分析的結(jié)果，反映的是數(shù)據(jù)的內(nèi)在規(guī)律。那么這個結(jié)果符合現(xiàn)實情況嗎?是否是一個有用的知識？是否有利用價值？,3,尿不濕和啤酒,經(jīng)過大量實際調(diào)查和分析，他們揭示了一個隱藏在“尿不濕與啤酒”背后的美國消費者的一種行為模式：在美國，到超市去買嬰兒尿不濕是一些年輕的父親下班后的日常工作，而他們中有

3、30%～40%的人同時也會為自己買一些啤酒。產(chǎn)生這一現(xiàn)象的原因是：美國的太太們常叮囑她們的丈夫不要忘了下班后為小孩買尿不濕，而丈夫們在買尿不濕后又隨手帶回了他們喜歡的啤酒。另一種情況是丈夫們在買啤酒時突然記起他們的責(zé)任，又去買了尿不濕。既然尿不濕與啤酒一起被購買的機會很多，那么沃爾瑪就在他們所有的門店里將尿不濕與啤酒并排擺放在一起，結(jié)果是得到了尿不濕與啤酒的銷售量雙雙增長。按常規(guī)思維，尿不濕與啤酒風(fēng)馬牛不相及，若不是借助數(shù)據(jù)挖掘技術(shù)對

4、大量交易數(shù)據(jù)進行挖掘分析，沃爾瑪是不可能發(fā)現(xiàn)數(shù)據(jù)內(nèi)這一有價值的規(guī)律的。,4,美國一名男子闖入他家附近的一家美國零售連鎖超市Target店鋪(美國第三大零售商塔吉特)進行抗議：“你們竟然給我17歲的女兒發(fā)嬰兒尿片和童車的優(yōu)惠券。”店鋪經(jīng)理立刻向來者承認錯誤，但是其實該經(jīng)理并不知道這一行為是總公司運行數(shù)據(jù)挖掘的結(jié)果。如圖所示。一個月后，這位父親來道歉，因為這時他才知道他的女兒的確懷孕了。Target比這位父親知道他女兒懷孕的時間足足早了一

5、個月。,,5,美國折扣零售商塔吉特與懷孕預(yù)測,美國折扣零售商塔吉特與懷孕預(yù)測,塔吉特公司能在不被清楚告知的情況下預(yù)測出一個女性的懷孕情況該公司找出了大概20多種與懷孕的關(guān)聯(lián)物，給顧客進行“懷孕趨勢”評分這些數(shù)據(jù)甚至使得零售商能夠比較準確地預(yù)測預(yù)產(chǎn)期，這樣就能夠在孕期的每個階段給客戶寄送相應(yīng)的優(yōu)惠券Target能夠通過分析女性客戶購買記錄，“猜出”哪些是孕婦。他們從Target的數(shù)據(jù)倉庫中挖掘出25項與懷孕高度相關(guān)的商品，制作“懷孕

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

7、等。關(guān)聯(lián)分析是指如果兩個或多個事物之間存在一定的關(guān)聯(lián),那么其中一個事物就能通過其他事物進行預(yù)測.它的目的是為了挖掘隱藏在數(shù)據(jù)間的相互關(guān)系 。,,典型的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題是對超市中的貨籃數(shù)據(jù)（Market Basket）進行分析。通過發(fā)現(xiàn)顧客放入貨籃中的不同商品之間的關(guān)系來分析顧客的購買習(xí)慣。,數(shù)據(jù)關(guān)聯(lián),經(jīng)典案例：沃爾瑪?shù)钠【坪湍虿嫉墓适?關(guān)聯(lián)規(guī)則,購物籃分析“啤酒和尿布”的故事是營銷屆的神話，“啤酒”和“尿布”兩個看上去沒有關(guān)系的

8、商品擺放在一起進行銷售、并獲得了很好的銷售收益，這種現(xiàn)象就是賣場中商品之間的關(guān)聯(lián)性。 研究“啤酒與尿布”關(guān)聯(liá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

9、 提出，是數(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)實中，這樣的例子很多。,例如超級市場利用前端收款機收集存儲了大量的售貨數(shù)據(jù)，這些數(shù)據(jù)是一條條的購買事務(wù)記錄，每條記錄存儲了事務(wù)處理時間，顧客購買的物品、物品的數(shù)量及金額等。 這些數(shù)據(jù)中常常隱含形式如下的關(guān)聯(lián)規(guī)則：

10、在購買鐵錘的顧客當中，有70 ％的人同時購買了鐵釘。 這些關(guān)聯(lián)規(guī)則很有價值，商場管理人員可以根據(jù)這些關(guān)聯(lián)規(guī)則更好地規(guī)劃商場，如把鐵錘和鐵釘這樣的商品擺放在一起，能夠促進銷售。,關(guān)聯(lián)規(guī)則分析拓展,1）商業(yè)銷售上，如何通過交叉銷售得到更大的收入？2）保險方面，如何分析索賠要求發(fā)現(xiàn)潛在的欺詐行為？3）銀行方面，如何分析顧客消費行業(yè)，以便有針對性地向其推薦感興趣的服務(wù)？4）哪些制造零件和設(shè)備設(shè)置與故障事件關(guān)聯(lián)？5）哪些病人和藥物

11、屬性與結(jié)果關(guān)聯(lián)？6）哪些商品是已經(jīng)購買商品A的人最有可能購買的？,如何從交易記錄數(shù)據(jù)庫或關(guān)系數(shù)據(jù)庫的大量數(shù)據(jù)中挖掘出關(guān)聯(lián)規(guī)則知識？什么樣的關(guān)聯(lián)規(guī)則才是最有意義的？如何才能幫助挖掘過程盡快發(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}等，每個顧客購買的都是一個項集。其中，項集中item的個數(shù)稱為項集的長

12、度，含有k個item的項集成為K-itemset.交易（transaction）：定義I為所有商品的集合，在這個例子中I={B C M T}。每個非空的I子集都成為一個交易。所有交易構(gòu)成交易數(shù)據(jù)庫D。,關(guān)聯(lián)規(guī)則,設(shè)　I={i1,i2,…,im}是項（Item）的集合。記D為事務(wù)（Transaction）的集合（事務(wù)數(shù)據(jù)庫），事務(wù)T是項的集合，并且T?I。設(shè)A是I中一個項集，如果A?T，那么稱事務(wù)T包含A。定義1：關(guān)聯(lián)規(guī)則是形如A

13、?B的蘊涵式，這里A?I，B?I，并且A?B=?。,度量規(guī)則的指標,,支持度（ｓｕｐｐｏｒｔ）可信度（ｃｏｎｆｉｄｅｎｃｅ）作用度/興趣度（Ｌｉｆｔ）,支持度,定義2：規(guī)則的支持度。支持度描述了A 和B 這兩個物品集在所有的事務(wù)中同時出現(xiàn)的概率有多大。規(guī)則A?B在數(shù)據(jù)庫D中具有支持度S，即概率P(AB)，即： 其中|D|表示事務(wù)數(shù)據(jù)庫D的個數(shù)，表示A、B兩個項集同時發(fā)生的事務(wù)個數(shù)。,可信

14、度,定義3：規(guī)則的可信度可信度就是指在出現(xiàn)了物品集A 的事務(wù)T 中，物品集B 也同時出現(xiàn)的概率規(guī)則A?B具有可信度C，表示C是條件概率P(B|A)，即： 其中 　表示數(shù)據(jù)庫中包含項集A的事務(wù)個數(shù)。,小結(jié),可信度是對關(guān)聯(lián)規(guī)則的準確度的衡量，支持度是對關(guān)聯(lián)規(guī)則重要性的衡量。支持度說明了這條規(guī)則在所有事務(wù)中有多大的代表性。顯然支持度越大，關(guān)聯(lián)規(guī)則越重要。有些關(guān)聯(lián)規(guī)則可信度雖然很高，但支持度卻很

15、低，說明該關(guān)聯(lián)規(guī)則實用的機會很小，因此也不重要。,理解：關(guān)聯(lián)分析中的三個重要的概念 舉例：10000個人購買了產(chǎn)品，其中購買A產(chǎn)品的人是1000個，購買B產(chǎn)品的人是2000個，AB同時購買的人是800個。,支持度指的是關(guān)聯(lián)的產(chǎn)品（假定A產(chǎn)品和B產(chǎn)品關(guān)聯(lián)）同時購買的人數(shù)占總?cè)藬?shù)的比例，即800/10000=8%，有8%的用戶同時購買了A和B兩個產(chǎn)品；,可信度指的是在購買了一個產(chǎn)品之后購買另外一個產(chǎn)品的可能性，如購買了A產(chǎn)品之

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

17、 即 表示項集A出現(xiàn)和項集B是相互獨立的。若 表示A出現(xiàn)和B出現(xiàn)是負相關(guān)的。若 表示A出現(xiàn)和B出現(xiàn)是正相關(guān)的。意味著A的出現(xiàn)蘊含B的出現(xiàn)。,,,,,,,一條規(guī)則的興趣度越大于1說明我們對這條規(guī)則越感興趣（即其實際利用價值越大）；一條規(guī)則的興趣度越小于1說明我們對這條規(guī)則的反面規(guī)則越感興趣（即其反面規(guī)則的實際利用價值越大）；興趣度I不小于0。,例,設(shè)交易集D，經(jīng)過對D的分析，得到表格:,所有

18、可能的關(guān)聯(lián)規(guī)則,,討論I1﹑I2﹑I3﹑I6共4條規(guī)則：由于I1,I21,規(guī)則才有價值。興趣度也稱為作用度（Lift）,表示關(guān)聯(lián)規(guī)則A→B的“提升”。如果作用度（興趣度）不大于1，則此關(guān)聯(lián)規(guī)則就沒有意義了。,,小結(jié),作用度描述了物品集A 對物品集B 的影響力的大小。作用度越大，說明物品集B 受物品集A 的影響越大。一般情況，有用的關(guān)聯(lián)規(guī)則的作用度都應(yīng)該大于1，說明A 的出現(xiàn)對B 的出現(xiàn)有促進作用，也說明了它們之間某種程度的相關(guān)

19、性，如果作用度不大于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：

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

21、e: 頻繁項集,項集 –-- 任意項的集合k-項集 –-- 包含k個項的項集頻繁項集 –-- 滿足最小支持度的項集若I包含m個項,那么可以產(chǎn)生多少個項集?,36,Step two:強關(guān)聯(lián)規(guī)則,給定一個項集,容易生成關(guān)聯(lián)規(guī)則.項集: {Chips, Salsa, Beer}Beer, Chips => SalsaBeer, Salsa => ChipsChips, Salsa => Beer強規(guī)則強規(guī)

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

23、1-項集”的集合。該集合記作L1。L1用于找頻繁“2-項集”的集合L2，而L2用于找L3，如此下去，直到不能找到“K-項集”。找每個LK需要一次數(shù)據(jù)庫掃描。,Apriori 算法中候選項集 與頻繁項集的產(chǎn)生實例,,1) 在算法的第一次迭代，每個項都是候選1-項集的集合C1的成員。算法掃描所有的事務(wù)，對每個項的出現(xiàn)次數(shù)計數(shù)。見圖中第1列。2) 假定最小事務(wù)支持計數(shù)為2（即min-sup=2/9=22%），可以確定頻繁1-項

24、集的集合L1。它由具有最小支持度的候選1-項集組成。見圖中第2列。3) 為發(fā)現(xiàn)頻繁2-項集的集合L2，算法使用L1*L1來產(chǎn)生候選集C2。見圖中第3列。4) 掃描D中事務(wù)，計算C2中每個候選項集的支持度計數(shù)，如圖中的第4列。5) 確定頻繁2-項集的集合L2，它由具有最小支持度的C2中的候選2-項集組成。見圖第5列。,,6) 候選3-項集的集合C3的產(chǎn)生，得到候選集：C3={{A，B，C}，{A，B，E}，{A，C，E}，{B，C

25、，D}，{B，C，E}，{B，D，E}}按Apriori 性質(zhì)，頻繁項集的所有子集必須是頻繁的。由于{A，D}，{C，D}，{C，E}，{D，E}不是頻繁項集，故C3中后4個候選不可能是頻繁的，在C3中刪除它們。見圖第6列。掃描D中事務(wù)，對C3中的候選項集計算支持度計數(shù)，見圖第7列。7) 確定L3，它由具有最小支持度的C3中候選3－項集組成，見圖第8列。8）按公式產(chǎn)生候選4－項集的集合C4，產(chǎn)生結(jié)果{A,B,C,E},這個項集被

26、剪去，因為它的子集｛B,C,E｝不是頻繁的。這樣L4=Ф。此算法終止。L3是最大的頻繁項集，即：｛A,B,C｝和｛A,B,E｝。,具體產(chǎn)生過程用圖表示,候選集與頻繁項集的產(chǎn)生,,在事務(wù)數(shù)據(jù)庫中，頻繁項集L={A，B，E}，可以由L產(chǎn)生哪些關(guān)聯(lián)規(guī)則？L的非空子集S有：{A, B}, {A, E}, {B, E}, {A}, {B},{E}?？傻玫疥P(guān)聯(lián)規(guī)則如下：A ∧ B → E conf=2/4=50%A ∧ E → B

27、conf=2/2=100%B ∧ E → A conf=2/2==100%A → B ∧ E conf=2/6=33%B → A ∧ E conf=2/7=29%E → A ∧ B conf=2/2=100%假設(shè)最小可信度為60％，則最終輸出的關(guān)聯(lián)規(guī)則為：A ∧ E → B 100%B ∧ E → A 100%E → A ∧ B 100%對于頻繁項集{A，B，C}，同樣可得其它