數據挖掘與關聯規(guī)則

1、大數據時代算法-關聯規(guī)則簡介關聯規(guī)則（Association Rules）反映一個事物與其他事物之間的相互依存性和關聯性。如果兩個或者多個事物之間存在一定的關聯關系，那么，其中一個事物就能夠通過其他事物預測到。首先被Agrawal, Imielinski and Swami在1993年的SIGMOD會議上提出. 關聯規(guī)則挖掘是數據挖掘中最活躍的研究方法之一。典型的關聯規(guī)則發(fā)現問題是對超市中的購物籃數據（Market Basket）進行分析。通過發(fā)現顧客放入購物籃中的不同商品之間的關系來分析顧客的購買習慣。 “尿布與啤酒”的故事。美國的沃爾瑪超市對一年多的原始交易數據進行了詳細的分析，得到一個意

2、外發(fā)現：與尿布一起被購買最多的商品竟然是啤酒。借助于數據倉庫和關聯規(guī)則，商家發(fā)現了這個隱藏在背后的事實：美國的婦女們經常會囑咐她們的丈夫下班以后要為孩子買尿布，而30%40%的丈夫在買完尿布之后又要順便購買自己愛喝的啤酒。有了這個發(fā)現后，超市調整了貨架的設置，把尿布和啤酒擺放在一起銷售，從而大大增加了銷售額。70%購買了牛奶的顧客將傾向于同時購買面包。某網上書店向用戶推薦相關書籍。在買了一臺PC之后下一步會購買？在保險業(yè)務方面，如果出現了不常見的索賠要求組合，則可能為欺詐，需要作進一步的調查；在醫(yī)療方面，可找出可能的治療組合；在銀行方面，對顧客進行分析，可以推薦感興趣的服務等等。什么是規(guī)則？規(guī)

3、則形如如果那么(IfThen),前者為條件，后者為結果。例如一個顧客，如果買了可樂，那么他也會購買果汁。如何來度量一個規(guī)則是否夠好？有兩個量，置信度(Confidence)和支持度(Support)。假設有如下表的購買記錄。 置信度置信度表示了這條規(guī)則有多大程度上值得可信。設條件的項的集合為A,結果的集合為B。置信度計算在A中，同時也含有B的概率(即：if A ,then B的概率)。即 Confidence(AB)=P(B|A)。例如計算“如果Orange則Coke”的置信度。由于在含有“橙汁”的4條交易中，僅有2條交易含有“可樂”。其置信度為0.5。支持度支持度計算在所有的交易集中，既有A

4、又有B的概率。例如在5條記錄中，既有橙汁又有可樂的記錄有2條。則此條規(guī)則的支持度為 2/5=0.4，即Support(AB)=P(AB)?，F在這條規(guī)則可表述為，如果一個顧客購買了橙汁,則有50%(置信度)的可能購買可樂。而這樣的情況（即買了橙汁會再買可樂）會有40%(支持度)的可能發(fā)生。 定義1 項目與項集設I=i1,i2,im是m個不同項目的集合，每個ik(k=1，2，m)稱為一個項目(Item)。項目的集合 I 稱為項目集合(Itemset)，簡稱為項集。其元素個數稱為項集的長度，長度為k的項集稱為k-項集(k-Itemset)。l定義2 交易l每筆交易T(Transaction)是項集I

5、上的一個子集，即TI，但通常TI。l對應每一個交易有一個唯一的標識交易號，記作TIDl交易的全體構成了交易數據庫D，或稱交易記錄集D，簡稱交易集D。l交易集D中包含交易的個數記為|D|。 l定義3 項集的支持度l對于項集X，XI，設定count(XT)為交易集D中包含X的交易的數量l項集X的支持度support(X)就是項集X出現的概率，從而描述了X的重要性。 |D|T)count(Xsupport(X)定義4 項集的最小支持度與頻繁集發(fā)現關聯規(guī)則要求項集必須滿足的最小支持閾值，稱為項集的最小支持度(Minimum Support)，記為supmin。支持度大于或等于supmin的項集稱為頻繁

6、項集，簡稱頻繁集，反之則稱為非頻繁集。通常k-項集如果滿足supmin，稱為k-頻繁集，記作Lk。定義5 關聯規(guī)則關聯規(guī)則(Association Rule)可以表示為一個蘊含式： R：XY 其中：XI，YI，并且XY= 。例如：R：牛奶面包定義6 關聯規(guī)則的支持度對于關聯規(guī)則R：XY，其中XI，YI，并且XY=。規(guī)則R的的支持度(Support)是交易集中同時包含X和Y的交易數與所有交易數之比。 |D|Y)count(XY)support(X定義7 關聯規(guī)則的置信度對于關聯規(guī)則R：XY，其中XI,YI，并且XY=。規(guī)則R的置信度(Confidence)是指包含X和Y的交易數與包含X的交易數之

7、比 support(X)Y)support(XY)(X confidence一般來說，只有支持度和置信度均較高的關聯規(guī)則才是用戶感興趣的、有用的關聯規(guī)則。定義8 關聯規(guī)則的最小支持度和最小置信度關聯規(guī)則的最小支持度也就是衡量頻繁集的最小支持度(Minimum Support)，記為supmin，它用于衡量規(guī)則需要滿足的最低重要性。關聯規(guī)則的最小置信度(Minimum Confidence)記為confmin，它表示關聯規(guī)則需要滿足的最低可靠性。定義9 強關聯規(guī)則如果規(guī)則R:XY滿足support(XY)supmin且confidence(XY)confmin，稱關聯規(guī)則XY為強關聯規(guī)則，否則稱

8、關聯規(guī)則XY為弱關聯規(guī)則。在挖掘關聯規(guī)則時，產生的關聯規(guī)則要經過supmin和confmin的衡量，篩選出來的強關聯規(guī)則才能用于指導商家的決策。對于規(guī)則 AC：支持度 = support(A,C ) = 50%置信度 = support(A,C )/support(A) = 66.6%交易ID購買商品2000A,B,C1000A,C4000A,D5000B,E,F假設最小值支持度為假設最小值支持度為50%，最小置信度為，最小置信度為50%規(guī)則規(guī)則AC滿足最小支持度和最小置信滿足最小支持度和最小置信度，所以它是度，所以它是強關聯規(guī)則強關聯規(guī)則l關聯規(guī)則挖掘是一個兩步的過程：關聯規(guī)則挖掘是一個兩步

9、的過程：l找出所有找出所有頻繁項集頻繁項集l由頻繁項集產生由頻繁項集產生強關聯規(guī)則強關聯規(guī)則，這些規(guī)則必須大于，這些規(guī)則必須大于或者等于最小支持度和最小置信度或者等于最小支持度和最小置信度大于或者等于最小支持度大于或者等于最小支持度的項集的項集AprioriApriori算法算法Apriori算法是一種經典的生成布爾型關聯規(guī)則的頻繁項集挖掘算法。Apriori算法將發(fā)現關聯規(guī)則的過程分為兩個步驟：通過迭代，檢索出事務數據庫中的所有頻繁項集，即支持度不低于用戶設定的閾值的項集；利用頻繁項集構造出滿足用戶最小置信度的規(guī)則。挖掘或識別出所有頻繁項集是該算法的核心，占整個計算量的大部分。 Aprior

10、iApriori算法的重要性質算法的重要性質性質1：頻繁項集的子集必為頻繁項集性質2：非頻繁項集的超集一定是非頻繁的假設項集假設項集A,CA,C是頻繁項集，則是頻繁項集，則AA和和CC也為頻繁項集也為頻繁項集假設項集假設項集DD不是頻繁項集，則不是頻繁項集，則A,DA,D和和C,DC,D也不是頻繁項集也不是頻繁項集AprioriApriori算法舉例算法舉例現有A、B、C、D、E五種商品的交易記錄表，找出所有頻繁項集，假設最小支持度=50%,最小置信度=50%AprioriApriori算法舉例算法舉例_ _產生頻繁項集產生頻繁項集K=1支持度50A50%50%B75%75%C75%75%E7

11、5%75%L1項集項集支持度支持度A,B25%25%A,C50%50%A,EA,E25%25%B,C50%50%B,E75%75%C,E50%50%C2 2K=2支持度50支持度50A,C50%50%B,C50%50%B,E75%75%C,E50%50%L2AprioriApriori算法舉例算法舉例_ _產生頻繁項集產生頻繁項集A,C50%50%B,C50%50%B,E75%75%C,E50%50%L2支持度50支持度50AprioriApriori算法舉例算法舉例_ _產生關聯規(guī)則產生關聯規(guī)則對于頻繁項集B,C,E,它的非空子集有B、C、E、B,C、B,E、C,E。以下就是據此獲得的關聯規(guī)

12、則及其置信度。規(guī)則規(guī)則置信度置信度ConfidenceConfidenceBCE66.7%CBE66.7%EBC66.7%CEB1BEC66.7%BCE1置信度50%(最小置信度)，都是強關聯規(guī)則AprioriApriori算法弊端算法弊端需要多次掃描數據表如果頻繁集最多包含10個項，那么就需要掃描交易數據表10遍，這需要很大的I/O負載產生大量頻繁集若有100個項目，可能產生候選項數目1210030100100100.1.27*10CCCFP-growthFP-growth算法算法Jiawei Han等人在2000年提出了一種基于FP-樹的關聯規(guī)則挖掘算法FP_growth，它采取“分而治之

13、”的策略，將提供頻繁項目集的數據庫壓縮成一棵頻繁模式樹（FP-樹）。僅兩次掃描數據庫。理論和實驗表明該算法優(yōu)于Apriori算法。FP-growthFP-growth算法算法其他關聯規(guī)則挖掘算法其他關聯規(guī)則挖掘算法約束性關聯規(guī)則挖掘算法僅設置支持度和置信度閾值，缺乏用戶控制，可能產生過多的規(guī)則，實際效果可能并不好。用戶關心的是某些特定的關聯規(guī)則，這需要把一些約束條件引入到挖掘算法中，從而篩選出符合約束條件的有用規(guī)則，提高算法的運行效率和用戶滿意度。增量式關聯規(guī)則挖掘算法數據集不斷增長，有新的數據加入后，重新挖掘很費時。增量式關聯規(guī)則挖掘算法是當數據庫變化后，在原挖掘結果的基礎上生成新的關聯規(guī)則

14、，刪除過時的關聯規(guī)則。多層關聯規(guī)則挖掘關聯規(guī)則的價值衡量關聯規(guī)則的價值衡量客觀上，使用“支持度和置信度”框架可能會產生一些不正確的規(guī)則。只憑支持度和置信度閾值未必總能找出符合實際的規(guī)則。例：歌曲A、歌曲C為小眾歌曲，歌曲B為口水歌，共有10萬個用戶，有200個人聽過歌曲A，這200個人里面有60個聽過口水歌B，有40個人聽過歌曲C。聽過歌曲C的人數是300，聽過口水歌B的人為50000。Confidence(AB) = 0.3，Confidence(AC) = 0.2但是10W人里面有5W聽過歌曲B，有一半的用戶都喜歡歌曲B，但聽過歌曲A的人里面只有30%的人喜歡歌曲 B聽過歌曲A的人不喜歡歌

15、曲B貌似A和B更相關矛盾的規(guī)則，如何評價？關聯規(guī)則價值衡量關聯規(guī)則價值衡量Lift(AB)=Confidence(AB)/Support(B)=()( ) ( )p ABp A p B引入提升度Lift，以度量此規(guī)則是否可用。它描述的是：相對于不用規(guī)則，使用規(guī)則可以提高多少。Lift(AB) =Confidence(AB)/Support(B)=0.3/0.5=0.6Lift(AC)=Confidence(AC)/Support(C)=0.2/(300/100000)=66.7歌曲A與B負相關，A與C正相關。Lift大于1，表示使用這條規(guī)則進行推薦能提升用戶聽歌曲C的概率。Lift小于1，則表

16、示使用這條規(guī)則來進行推薦，還不如不推薦，讓顧客自行選擇好了。Confidence(AB) = 0.3Confidence(AC) = 0.2Support(B)=0.5Support(C)=300/100000關聯規(guī)則的價值衡量關聯規(guī)則的價值衡量主觀上，一個規(guī)則的有用與否最終取決于用戶的感覺，只有用戶才能決定規(guī)則的有效性、可行性。所以，應該將需求和關聯規(guī)則挖掘方法緊密地結合起來。例如使用“約束性關聯規(guī)則挖掘算法”，將約束條件與算法緊密結合，既能提高數據挖掘效率，又能明確數據挖掘的目標。參考文獻：1高明 . 關聯規(guī)則挖掘算法的研究及其應用D.山東師范大學. 20062李彥偉 . 基于關聯規(guī)則的數據挖掘方法研究D.江南大學