Python實(shí)現(xiàn) 關(guān)聯(lián)規(guī)則的Apriori 算法-亞馬遜購物零售數(shù)據(jù)挖掘
關(guān)聯(lián)規(guī)則
關(guān)聯(lián)規(guī)則（AssociationRules），無監(jiān)督學(xué)習(xí)方法，用于知識發(fā)現(xiàn)。
其可以用于給數(shù)據(jù)進(jìn)行標(biāo)注，但缺點(diǎn)是其結(jié)果難以進(jìn)行評估。
關(guān)聯(lián)規(guī)則的最經(jīng)典的案例就是購物籃分析。同樣也可用于電影推薦、約會網(wǎng)站或者藥物間的相互副作用。
若X，Y均為項(xiàng)集，且X?I，Y?I，并且X∩Y= ? ，用蘊(yùn)含式X =>Y表示一個關(guān)聯(lián)規(guī)則。它表示某些項(xiàng)（X項(xiàng)集）在一個事務(wù)中的出現(xiàn)，可推導(dǎo)出另一些項(xiàng)（Y項(xiàng)集）在同一事務(wù)中也出現(xiàn) 。這里，“=>”稱為“關(guān)聯(lián)”操作，X稱為關(guān)聯(lián)規(guī)則的前提， Y稱為關(guān)聯(lián)規(guī)則的結(jié)果。
事物和項(xiàng)
數(shù)據(jù)挖掘用到的基本數(shù)據(jù)集記為D，它是由事務(wù)構(gòu)成的，一般多存儲于事務(wù)數(shù)據(jù)庫中。事物數(shù)據(jù)庫表示為D={t1，t2，…，tm，…，tq}， 事務(wù)則表示為tk(k=1，2，…，n)。每一個事務(wù)可再細(xì)分，表示為tk={i1，i2，…，in，…，ip}，im(m=1，2，…，p)稱為項(xiàng)（item）。「所以事務(wù)是由若干個項(xiàng)組成的集合?！?/strong>
每個事務(wù)可以用唯一的標(biāo)識符事務(wù)編號TID來標(biāo)識。設(shè)I={i1，i2，…，ip}是D中全體數(shù)據(jù)項(xiàng)組成的集合，I的任意子集X稱為D中的項(xiàng)集（itemset）。若項(xiàng)集中項(xiàng)的個數(shù)為k，稱為k項(xiàng)集（k-itemset）。「頻繁項(xiàng)集是指出現(xiàn)次數(shù)較多的項(xiàng)集?！?/strong>
支持度
支持度表示該數(shù)據(jù)項(xiàng)在事務(wù)中出現(xiàn)的頻度。數(shù)據(jù)項(xiàng)集X的支持度support(X)是D中包含X的事務(wù)數(shù)量與D的總事務(wù)數(shù)量之比，如下公式所示：
關(guān)聯(lián)規(guī)則X=>Y的支持度等于項(xiàng)集X∪Y的支持度，如下公式所示:
如果support(X)大于等于用戶指定的最小支持度minsup，則稱X為頻繁項(xiàng)目集，否則稱X為非頻繁項(xiàng)目集。
置信度
置信度也稱為可信度，規(guī)則 X=>Y 的置信度表示D中包含X的事務(wù)中有多大可能性也包含Y。表示的是這個規(guī)則確定性的強(qiáng)度，記作confidence(X=>Y)。通常，用戶會根據(jù)自己的挖掘需要來指定最小置信度閾值，記為minconf。
如果數(shù)據(jù)項(xiàng)集X滿足support(X) >= minsup，則X是頻繁數(shù)據(jù)項(xiàng)集。若規(guī)則X=>Y同時滿足confidence(X=>Y)>=minconf，則稱該規(guī)則為強(qiáng)關(guān)聯(lián)規(guī)則，否則稱為弱關(guān)聯(lián)規(guī)則。一般由用戶給定最小置信度閾值和最小支持度閾值。發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的任務(wù)就是從數(shù)據(jù)庫中發(fā)現(xiàn)那些置信度、支持度大于等于給定最小閾值的強(qiáng)關(guān)聯(lián)規(guī)則。
Lift
Lift定義為：
如果一個規(guī)則的lift值等于1，這表示前提和結(jié)論對應(yīng)的事件相互獨(dú)立；如果lift值大于1，指示了兩個事件之間的相互依賴程度，值越大，關(guān)聯(lián)越強(qiáng)；如果lift值小于1，表明一個item的出現(xiàn)對其他item的出現(xiàn)存在消極影響（相斥），反之亦然（其中一個出現(xiàn)另一個一般不會出現(xiàn)）。lift的意義在于其即考慮了置信度也考慮了整個數(shù)據(jù)集中結(jié)論的支持度。
Conviction
Conviction，用來表示規(guī)則預(yù)測出錯的概率，定義為：
在有了這些可計(jì)算的指標(biāo)后，還需要給這些指標(biāo)設(shè)定一個閾值，關(guān)聯(lián)規(guī)則只有滿足最小支持度閾值和最小置信度閾值，這條規(guī)則才能認(rèn)為是有趣的。而且關(guān)聯(lián)規(guī)則的生成可分以下兩個步驟：
利用最小支持度閾值從數(shù)據(jù)庫中找出所有的頻繁項(xiàng)集；
利用最小置信度閾值從這些頻繁項(xiàng)集中生成規(guī)則。
關(guān)聯(lián)規(guī)則的生成規(guī)則的階段是直接的，但尋找頻繁項(xiàng)集卻是非常耗時的，常用的高效的算法有Apriori，F(xiàn)P-growth等。
計(jì)算置信度與支持度
為了更好幫助大家理解置信度與支持度，請看下面這個例子：
生成頻繁項(xiàng)集
生成頻繁項(xiàng)集是Apriori算法的核心，如何更快、更有效的生成頻繁項(xiàng)集是算法的關(guān)鍵。下圖是生成頻繁項(xiàng)集的拓?fù)鋱D：
為了幫助大家理解，在此我用一個虛擬交易數(shù)據(jù)來說明生成頻繁項(xiàng)集的具體過程。設(shè)事務(wù)有一數(shù)據(jù)庫D，其中有四個事務(wù)記錄如表所示：
假設(shè)最小支持度為50%，那么我們要這樣生成頻繁項(xiàng)集嘞？
步驟1：掃描事務(wù)集，「得到候選1項(xiàng)集C1」，然后計(jì)算每一項(xiàng)的支持度，從而構(gòu)建下表：
對C1中的各項(xiàng)集的支持度與預(yù)先設(shè)定的最小支持度閾值進(jìn)行比較，保留大于等于該閾值的項(xiàng)，「得1項(xiàng)頻繁集L1」。
L1與L1做連接得到候選2項(xiàng)集C2，并計(jì)算各項(xiàng)支持度，接下來就是剪枝步，由于C2的每個子集都是頻繁項(xiàng)集，所以沒有項(xiàng)集從C2中剔除。
對C2中的各項(xiàng)集的支持度與預(yù)先設(shè)定的最小支持度閾值進(jìn)行比較，保留大于等于該閾值的項(xiàng)，「得2項(xiàng)頻繁集L2」。
L2與L1連接得候選3項(xiàng)集C3，并計(jì)算每一項(xiàng)的支持度。接下來是剪枝步。L2余L1連接得所有項(xiàng)集為：{I1,I2,I3}，{I1,I3,I5}，{I2,I3,I5}，{I1,I2,I5}。根據(jù)Apriori算法性質(zhì)，頻繁項(xiàng)集的所有非空子集必須是頻繁項(xiàng)集，因?yàn)閧I1,I2}，{I1,I5}不在2項(xiàng)頻繁項(xiàng)集中，所以應(yīng)該剔除。最后三項(xiàng)候選集只剩下{I2,I3,I5}。
對C3中的各項(xiàng)集的支持度與預(yù)先設(shè)定的最小支持度閾值進(jìn)行比較，保留大于等于該閾值的項(xiàng)，「得3項(xiàng)頻繁集L3」。
L3與L1連接得候選4項(xiàng)集C4，剪枝后為空集，所以停止迭代。最后得到最大頻繁項(xiàng)集{I2,I3,I5}。
由以上過程可知L1，L2，L3都是頻繁項(xiàng)集，L3是最大頻繁項(xiàng)集。
?產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則
上面我們已經(jīng)得到了頻繁項(xiàng)集，接下來我們要基于頻繁項(xiàng)集生成關(guān)聯(lián)規(guī)則（假設(shè)最小置信度為50%）。
我們不妨基于最大頻繁項(xiàng)集{I2,I3,I5}來生成規(guī)則：
步驟1：找出最大頻繁項(xiàng)集的所有非空子集：{I2,I3}，{I2,I5}，{I3,I5}，{I2}，{I3}，{I5}。
步驟2：生成所有可能的關(guān)聯(lián)規(guī)則：{I2,I3}=>{I5}，{I2,I5}=>{I3}，{I3,I5}=>{I2}，{I5}=>{I2,I3}，{I3}=>{I2,I5}，{I2}=>{I3,I5}
步驟3：計(jì)算所有規(guī)則的置信度，找出所有大于最小置信度的規(guī)則，它們就是強(qiáng)規(guī)則：
Apriori 算法概述
Apriori 算法是一種機(jī)器學(xué)習(xí)算法，用于深入了解所涉及的不同項(xiàng)目之間的結(jié)構(gòu)化關(guān)系。Apriori算法也是一個經(jīng)典的挖掘規(guī)則算法，也是最常用的挖掘頻繁項(xiàng)集的算法。該算法最突出的實(shí)際應(yīng)用是根據(jù)用戶購物車中已經(jīng)存在的產(chǎn)品推薦產(chǎn)品。沃爾瑪尤其在向其用戶推薦產(chǎn)品時充分利用了該算法。
主要步驟如下
文字描述下算法流程就是:
掃描TDB， 對每個候選項(xiàng)計(jì)算支持度得到表C1
比較C中各個后選項(xiàng)支持度與最小支持度，得到1維的最大項(xiàng)集L1
由L1得到候選集C2
由C2比較支持度得到L2
由L2得到C3
由C3得到3維項(xiàng)集L3
根據(jù)上述流程我們也會發(fā)現(xiàn)，這個算法每一步產(chǎn)生候選集時循環(huán)產(chǎn)生的組合過多，我們可以通過挖掘關(guān)聯(lián)規(guī)則的性質(zhì)來做剪枝。
任何頻繁集的子集必須是頻繁的
Apriori剪裁規(guī)則: 若存在某些項(xiàng)集是不頻繁的，則和這些項(xiàng)集的任何超集都是不頻繁的，因?yàn)闊o需生成和測試
如圖所示，AB是不頻繁的，那么紅色虛線圈出的所有超集也是不頻繁的，因此可以剪掉。所以生成候選集的方法可以這樣總結(jié)：
生成關(guān)聯(lián)規(guī)則
前面說完了如何生成頻繁項(xiàng)集，接下來說說如何生成關(guān)聯(lián)規(guī)則，現(xiàn)有頻繁項(xiàng)集l，生成每個非空子集S，若S滿足最小置信度:
如圖所示，最小置信度minconf=80%，對于頻繁項(xiàng)集BCE,得到如下幾個關(guān)聯(lián)規(guī)則，其中大于80%的為BC->E和CE-<B兩條規(guī)則。
作者用python編程語言完成了在線電子零售公司的跨國交易數(shù)據(jù)集的數(shù)據(jù)分析與可視化、根據(jù)關(guān)聯(lián)規(guī)則原理設(shè)計(jì)實(shí)現(xiàn)了基于Apriori算法的關(guān)聯(lián)規(guī)則挖掘程序并將程序封裝、使用封裝好的關(guān)聯(lián)規(guī)則挖掘程序?qū)?shù)據(jù)集進(jìn)行關(guān)聯(lián)規(guī)則的挖掘，并對挖掘結(jié)果進(jìn)行分析。
Apriori 算法實(shí)戰(zhàn)亞馬遜購物零售數(shù)據(jù)挖掘
數(shù)據(jù)集：亞馬遜購物-雜貨數(shù)據(jù)，共50萬多萬數(shù)據(jù)
?
變量列表如下
探索數(shù)據(jù)
看看前五條數(shù)據(jù)
數(shù)據(jù)匯總?cè)缦?br>
數(shù)據(jù)總共有541909條，其中“Description”、“CustomerID”兩個字段存在數(shù)據(jù)缺失情況。“Quantity”、“UnitPrice”字段最小值為負(fù)數(shù)，產(chǎn)品銷售數(shù)量存在負(fù)數(shù)可能是存在退貨情況，但是這種情況對產(chǎn)生關(guān)聯(lián)規(guī)則存在反向作用（削弱關(guān)聯(lián)強(qiáng)度），產(chǎn)品銷售單價存在負(fù)數(shù)說明該字段存在異常數(shù)據(jù)。
數(shù)據(jù)中國家變量處重后如下：
建立模型并分析結(jié)果
從上面的輸出可以看出，紙杯和紙盤是在法國一起買的。這是因?yàn)榉▏擞幸环N文化，即每周至少與朋友和家人聚會一次。此外，由于法國政府已禁止在該國使用塑料，人們不得不購買紙質(zhì)替代品。?
如果再深入分析一下英國的交易規(guī)則，就會發(fā)現(xiàn)英國人一起購買不同顏色的茶盤。這背后的一個原因可能是因?yàn)橛送ǔ７浅Ｏ矚g喝茶，并且經(jīng)常為不同的場合收集不同顏色的茶盤。
在分析葡萄牙交易的關(guān)聯(lián)規(guī)則時，觀察到 Tiffin 集 (Knick Knack Tins) 和彩色鉛筆。這兩種產(chǎn)品通常屬于小學(xué)生。這兩種產(chǎn)品是學(xué)校的孩子們分別用來攜帶午餐和創(chuàng)造性工作的必需品，因此在邏輯上將它們配對在一起是有意義的。
分析上述規(guī)則，發(fā)現(xiàn)男孩和女孩的餐具是搭配在一起的。這是有實(shí)際意義的，因?yàn)楫?dāng)父母為他/她的孩子購買餐具時，他/她會希望根據(jù)孩子的意愿對產(chǎn)品進(jìn)行一些定制。
Apriori算法就為大家介紹到這里，歡迎各位同學(xué)了解《呆瓜半小時入門python數(shù)據(jù)分析》課程。
如果有論文復(fù)現(xiàn)模型案例需求的學(xué)員，我們提供一對一定制輔導(dǎo)，快速幫你們解決問題。
版權(quán)聲明：文章來自公眾號(python風(fēng)控模型),未經(jīng)許可，不得抄襲。遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
