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

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

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

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

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

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

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

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

8、商品擺放在一起進(jìn)行銷售、并獲得了很好的銷售收益，這種現(xiàn)象就是賣場(chǎng)中商品之間的關(guān)聯(lián)性。 研究“啤酒與尿布”關(guān)聯(lián)的方法就是購(gòu)物籃分析，購(gòu)物籃分析是沃爾瑪秘而不宣的獨(dú)門武器，購(gòu)物籃分析可以幫助我們?cè)陂T店的銷售過程中找到具有關(guān)聯(lián)關(guān)系的商品，并以此獲得銷售收益的增長(zhǎng)！,,關(guān)聯(lián)規(guī)則挖掘（Association Rule）,在數(shù)據(jù)挖掘的知識(shí)模式中，關(guān)聯(lián)規(guī)則模式是比較重要的一種。關(guān)聯(lián)規(guī)則的概念由Agrawal、Imielinski、Swami

9、 提出，是數(shù)據(jù)中一種簡(jiǎn)單但很實(shí)用的規(guī)則。在數(shù)據(jù)庫(kù)的知識(shí)發(fā)現(xiàn)中，關(guān)聯(lián)規(guī)則就是描述這種在一個(gè)事務(wù)中物品之間同時(shí)出現(xiàn)的規(guī)律的知識(shí)模式。更確切的說，關(guān)聯(lián)規(guī)則通過量化的數(shù)字描述物品甲的出現(xiàn)對(duì)物品乙的出現(xiàn)有多大的影響,現(xiàn)實(shí)中，這樣的例子很多。,例如超級(jí)市場(chǎng)利用前端收款機(jī)收集存儲(chǔ)了大量的售貨數(shù)據(jù)，這些數(shù)據(jù)是一條條的購(gòu)買事務(wù)記錄，每條記錄存儲(chǔ)了事務(wù)處理時(shí)間，顧客購(gòu)買的物品、物品的數(shù)量及金額等。 這些數(shù)據(jù)中常常隱含形式如下的關(guān)聯(lián)規(guī)則：

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

11、屬性與結(jié)果關(guān)聯(lián)？6）哪些商品是已經(jīng)購(gòu)買商品A的人最有可能購(gòu)買的？,如何從交易記錄數(shù)據(jù)庫(kù)或關(guān)系數(shù)據(jù)庫(kù)的大量數(shù)據(jù)中挖掘出關(guān)聯(lián)規(guī)則知識(shí)？什么樣的關(guān)聯(lián)規(guī)則才是最有意義的？如何才能幫助挖掘過程盡快發(fā)現(xiàn)有價(jià)值的關(guān)聯(lián)知識(shí)？,問題,１關(guān)聯(lián)規(guī)則基本概念,項(xiàng)目（item）：其中的B C M T 都稱作item。項(xiàng)集（itemset）:item的集合，例如{B C}、{C M T}等，每個(gè)顧客購(gòu)買的都是一個(gè)項(xiàng)集。其中，項(xiàng)集中item的個(gè)數(shù)稱為項(xiàng)集的長(zhǎng)

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

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

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

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

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

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

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

19、性，如果作用度不大于1，則此關(guān)聯(lián)規(guī)則也就沒有意義了。,２關(guān)聯(lián)規(guī)則挖掘,在關(guān)聯(lián)規(guī)則的三個(gè)屬性中，支持度和可信度能夠比較直接形容關(guān)聯(lián)規(guī)則的性質(zhì)事實(shí)上，人們一般只對(duì)滿足一定的支持度和可信度的關(guān)聯(lián)規(guī)則感興趣。因此，為了發(fā)現(xiàn)有意義的關(guān)聯(lián)規(guī)則，需要由用戶給定兩個(gè)閾值： 最小支持度（min_sup）和最小可信度（min_conf）,頻繁項(xiàng)集,如果項(xiàng)集滿足最小支持度，則它稱之為頻繁項(xiàng)集（Frequent Itemset）。,強(qiáng)規(guī)則,定義5：

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

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

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

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

24、集的集合L1。它由具有最小支持度的候選1-項(xiàng)集組成。見圖中第2列。3) 為發(fā)現(xiàn)頻繁2-項(xiàng)集的集合L2，算法使用L1*L1來產(chǎn)生候選集C2。見圖中第3列。4) 掃描D中事務(wù)，計(jì)算C2中每個(gè)候選項(xiàng)集的支持度計(jì)數(shù)，如圖中的第4列。5) 確定頻繁2-項(xiàng)集的集合L2，它由具有最小支持度的C2中的候選2-項(xiàng)集組成。見圖第5列。,,6) 候選3-項(xiàng)集的集合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ì)，頻繁項(xiàng)集的所有子集必須是頻繁的。由于{A，D}，{C，D}，{C，E}，{D，E}不是頻繁項(xiàng)集，故C3中后4個(gè)候選不可能是頻繁的，在C3中刪除它們。見圖第6列。掃描D中事務(wù)，對(duì)C3中的候選項(xiàng)集計(jì)算支持度計(jì)數(shù)，見圖第7列。7) 確定L3，它由具有最小支持度的C3中候選3－項(xiàng)集組成，見圖第8列。8）按公式產(chǎn)生候選4－項(xiàng)集的集合C4，產(chǎn)生結(jié)果{A,B,C,E},這個(gè)項(xiàng)集被

26、剪去，因?yàn)樗淖蛹鸅,C,E｝不是頻繁的。這樣L4=Ф。此算法終止。L3是最大的頻繁項(xiàng)集，即：｛A,B,C｝和｛A,B,E｝。,具體產(chǎn)生過程用圖表示,候選集與頻繁項(xiàng)集的產(chǎn)生,,在事務(wù)數(shù)據(jù)庫(kù)中，頻繁項(xiàng)集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%對(duì)于頻繁項(xiàng)集{A，B，C}，同樣可得其它