R語言大數(shù)據(jù)分析與挖掘 課件 第九章 關聯(lián)算法

第9章

關聯(lián)算法內(nèi)容要點1、了解關聯(lián)算法的相關理論。2、掌握R語言中Apriori算法建模的方法。3、掌握R語言中ECLAT算法建模的方法。關聯(lián)算法概述Apriori算法ECLAT算法123關聯(lián)算法概述關聯(lián)是指一個事件和其他事件之間的聯(lián)系，這些聯(lián)系蘊含在交易數(shù)據(jù)、關系數(shù)據(jù)或其他信息載體中。在用戶設定的條件下利用算法查找存在于數(shù)據(jù)中的項目集合或?qū)ο蠹现g的頻繁模式、關聯(lián)、相關性或因果結(jié)構(gòu)就是關聯(lián)分析。不同項集間的聯(lián)系就是關聯(lián)規(guī)則，在設定條件時一般要設定支持度及信任度。關聯(lián)分析的相關概念如圖9-1所示。在用戶設定的條件下利用算法查找存在于數(shù)據(jù)中的項目集合或?qū)ο蠹现g的頻繁模式、關聯(lián)、相關性或因果結(jié)構(gòu)就是關聯(lián)分析。不同項集間的聯(lián)系就是關聯(lián)規(guī)則，在設定條件時一般要設定支持度及信任度。關聯(lián)分析的相關概念如圖9-1所示。關聯(lián)算法概述在一家超市中，人們發(fā)現(xiàn)了一個特別有趣的現(xiàn)象：尿布與啤酒這兩種風馬牛不相及的商品居然擺在一起。但這一奇怪的舉措居然使尿布和啤酒的銷量大幅增加了。這可不是一個笑話，而是一直被商家所津津樂道的發(fā)生在美國沃爾瑪連鎖超市的真實案例。原來，美國的婦女通常在家照顧孩子，所以她們經(jīng)常會囑咐丈夫在下班回家的路上為孩子買尿布，而丈夫在買尿布的同時又會順手購買自己愛喝的啤酒。這個發(fā)現(xiàn)為商家?guī)砹舜罅康睦麧?，但是如何從非常多?shù)據(jù)中，發(fā)現(xiàn)啤酒和尿布銷售之間的聯(lián)系呢？這就需要對數(shù)據(jù)中的啤酒和尿布進行關聯(lián)分析找到它們的關聯(lián)規(guī)則。示例：表9-1是一個超市幾名顧客的交易信息。對此數(shù)據(jù)集進行關聯(lián)分析，可以找出關聯(lián)規(guī)則{Diaper}→{Beer}。它代表的意義是購買了Diaper的顧客會購買Beer。這個關系不是必然的，但是可能性很大。這就已經(jīng)足夠用來輔助商家調(diào)整Diaper和Beer的擺放位置了，如擺放在相近的位置進行捆綁促銷來提高銷售量。關聯(lián)算法概述相關名詞關聯(lián)算法概述關聯(lián)規(guī)則及頻繁項集的產(chǎn)生關聯(lián)規(guī)則：形如X→Y這樣的蘊含關系稱為關聯(lián)規(guī)則，X和Y均是項集。關聯(lián)規(guī)則有兩個屬性：支持度和置信度。（1）關聯(lián)規(guī)則的支持度(見右),N是事務的總數(shù)。（2）關聯(lián)規(guī)則的置信度(見右)。由此可以定義關聯(lián)分析問題：在給定的事務集中，找到（支持度，置信度）大于給定閾值(sS0,C0)的所有關聯(lián)規(guī)則。普通的方法是遍歷所有的關聯(lián)規(guī)則，其復雜度為(見右)。好一點的方法是使用剪枝，因為關聯(lián)規(guī)則的支持度只與項集有關，可以首先篩選出支持度大于閾值s0的所有項集，這樣的項集叫作頻繁項集。給定頻繁項集，可以從中選出置信度大于閾值c0的所有關聯(lián)規(guī)則，這樣的規(guī)則叫作強規(guī)則。關聯(lián)規(guī)則的支持度關聯(lián)規(guī)則的置信度復雜度Apriori算法Apriori算法是常用于挖掘數(shù)據(jù)關聯(lián)規(guī)則的算法，能夠發(fā)現(xiàn)事務數(shù)據(jù)庫中頻繁出現(xiàn)的項集，這些聯(lián)系構(gòu)成的規(guī)則可幫助用戶找出某些行為特征，以便進行企業(yè)決策。Apriori算法概述Apriori算法是一種最有影響的挖掘布爾關聯(lián)規(guī)則（規(guī)則形如X→Y的蘊涵式）頻繁項集的算法，其核心思想是通過候選項集生成和情節(jié)的向下封閉檢測兩個階段來挖掘頻繁項集。而且算法已經(jīng)被廣泛地應用到商業(yè)、網(wǎng)絡安全等各個領域。很多的挖掘算法是在Apriori算法的基礎上進行改進的，如基于散列（Hash）的方法、基于數(shù)據(jù)分割（Partition）的方法及不產(chǎn)生候選項集的FP-growth算法等。因此要了解關聯(lián)規(guī)則算法首先要了解Apriori算法。Apriori算法先驗原理為降低產(chǎn)生頻繁項集的計算復雜度，利用支持度對候選項集進行剪枝，這也是Apriori算法所利用的第一條先驗原理。Apriori定律1：若一個集合是頻繁項集，則它的所有子集都是頻繁項集。例如，假設一個集合{A,B}是頻繁項集，即A、B同時出現(xiàn)在一條記錄的次數(shù)大于或等于最小支持度min_support，則它的子集{A},{B}出現(xiàn)次數(shù)必定大于或等于min_support，即它的子集都是頻繁項集。Apriori定律2：若一個集合不是頻繁項集，則它的所有超集都不是頻繁項集。例如，假設集合{A}不是頻繁項集，即A出現(xiàn)的次數(shù)小于min_support，則它的任何超集如{A,B}出現(xiàn)的次數(shù)必定小于min_support，因此其超集必定也不是頻繁項集。當發(fā)現(xiàn){A,B}是非頻繁項集時，就代表所有包含它的超集也是非頻繁的，即可以將它們都剪除，如圖9-2所示。Apriori算法連接步和剪枝步1．連接步若有兩個(k-1)-項集，每個項集按照“屬性-值”（一般按值）的字母順序進行排序。若兩個(k-1)-項集的前(k-2)個項相同，而最后一個項不同，則證明它們是可連接的，即這個(k-1)-項集可以聯(lián)姻，即可連接生成k-項集。即為找出Lk（所有的頻繁k-項集的集合），通過將Lk-1（所有的頻繁(k-1)-項集的集合）與自身連接產(chǎn)生候選k-項集的集合，候選項集合記作Ck。設l1和l2是Lk-1中的成員。記li[j]表示li中的第j項。假設Apriori算法對事務或項集中的項按字典次序排序，即對于(k-1)-項集li，li[1]<li[2]<…<li[k-1]。將Lk-1與自身連接，如果(l1[1]=l2[1])&&(l1[2]=l2[2])&&…&&(l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])，那認為l1和l2是可連接的。連接l1和l2產(chǎn)生的結(jié)果是{l1[1],l1[2],…,l1[k-1],l2[k-1]}。例如，有兩個3項集｛a,b,c｝和{a,b,d}，這兩個3項集就是可連接的，它們可以連接生成4項集｛a,b,c,d｝。又如兩個3項集｛a,b,c｝｛a,d,e｝，這兩個3項集顯示是不能連接生成3項集的。Apriori算法連接步和剪枝步2．剪枝步Ck是Lk的超集，也就是說，Ck的成員可能是也可能不是頻繁的。通過掃描所有的事務（交易），確定Ck中每個候選的計數(shù)，判斷是否小于最小支持度計數(shù)，如果不是，則認為該候選是頻繁的。若一個項集的子集不是頻繁項集，則該項集肯定也不是頻繁項集。例如，若存在3項集｛a,b,c｝，它的2項子集｛a,b｝的支持度，即同時出現(xiàn)的次數(shù)達不到閾值，則｛a,b,c｝同時出現(xiàn)的次數(shù)顯然也是達不到閾值的。因此，若存在一個項集的子集不是頻繁項集，那么該項集就應該被無情的舍棄。Apriori算法Apriori算法流程Apriori算法流程如下。（1）掃描數(shù)據(jù)庫D，計算出各個1項集的支持度，得到頻繁1項集的集合。（2）從2項集開始循環(huán)，由頻繁(k-1)-項集生成頻繁k-項集。①連接步：先生成頻繁(k-1)-項集，頻繁(k-1)-項集是由兩個只有一個項不同的頻繁項集做一個(k-2)JOIN運算得到的。②剪枝步：由于是超集，所以可能有些元素不是頻繁的。舍棄掉子集不是頻繁項集的(k-1)-項集。③掃描數(shù)據(jù)庫，計算②、③步中過濾后的(k-1)-項集的支持度，舍棄掉支持度小于閾值的項集，生成頻繁k-項集。（3）當前生成的頻繁k-項集中只有一個項集時循環(huán)結(jié)束。假設數(shù)據(jù)庫里有4條交易，分別為{A,C,D}、{B,C,E}、{A,B,C,E}、{B,E}，使用min_support=2作為支持度閾值，最后篩選出來的頻繁項集為{B,C,E}，篩選過程如圖9-3所示。Apriori算法Apriori算法實例arules包的Groceries數(shù)據(jù)集中包含了大量的購物清單數(shù)據(jù)，可用于關聯(lián)分析。安裝并加載R包，代碼如下：加載數(shù)據(jù)集并查看數(shù)據(jù)集Groceries，代碼如下：輸出結(jié)果為：Apriori算法Apriori算法實例（續(xù)）apriori(X,parameter=list(support=0.001,confidence=0.05))可計算所有的規(guī)則，是關聯(lián)規(guī)則分析的核心函數(shù)。parameter是用來設定計算頻率（支持度）和置信度的關聯(lián)規(guī)則。上面即求所有支持度大于0.001和置信度大于0.05的關聯(lián)規(guī)則。代碼如下：Apriori算法Apriori算法實例（續(xù)）查看模型，代碼如下：輸出結(jié)果為：Apriori算法Apriori算法實例（續(xù)）模型共找到了37937個關聯(lián)規(guī)則，查看支持度前10的規(guī)則，代碼如下：輸出結(jié)果為：支持度排名第1的規(guī)則為{othervegetables}=>{wholemilk}，兩者同時被購買的概率約為7%。Apriori算法是通過頻繁(k-1)-項集找到頻繁k-項集的，雖然可以通過Apriori性質(zhì)進行減枝，去掉一部分子集為非頻繁項集的候選項集，但還是需要不斷地掃描數(shù)據(jù)集，不斷地求候選項集的支持度計數(shù)從而判斷它是否是頻繁項集。如果數(shù)據(jù)集足夠大，這種算法就不再具有優(yōu)勢。ECLAT算法ECLAT算法是一種深度優(yōu)先算法，采用垂直數(shù)據(jù)表示形式，在概念格理論的基礎上利用基于前綴的等價關系將搜索空間（概念格）劃分為較小的子空間（子概念格）。ECLAT算法概述ECLAT算法不同于關聯(lián)規(guī)則中的Apriori算法和FP-growth算法，后兩者所采用的是從TID集格式的事物集中挖掘頻繁項集的水平數(shù)據(jù)結(jié)構(gòu)的方式，而ECLAT算法采用了垂直數(shù)1．ECLAT算法優(yōu)缺點（1）優(yōu)點：采用了與傳統(tǒng)挖掘算法不同的垂直數(shù)據(jù)庫結(jié)構(gòu)，由于這樣只要掃描兩次數(shù)據(jù)庫，大大減少了挖掘規(guī)則所需要的時間，從而提高了挖掘關聯(lián)規(guī)則的效率。（2）缺點：該算法沒有對產(chǎn)生的候選項集進行刪減操作，若項目出現(xiàn)的頻率非常高，頻繁項集龐大，進行交集操作時會消耗系統(tǒng)大量的內(nèi)存，影響算法的效率。ECLAT算法2．ECLAT算法原理由兩個頻繁k-項集求并集得到候選(k+1)-項集，對候選(k+1)-項集的事務集做交集操作，生成頻繁(k+1)-項集，以此迭代直到項集歸一，算法結(jié)束。ECLAT算法加入了倒排的思想，具體就是將事務數(shù)據(jù)中的項作為key，每個項對應的事務ID作為value。原輸入數(shù)據(jù)為：轉(zhuǎn)換后為：通過轉(zhuǎn)換后的倒排表可以加快頻繁項集生成速度。根據(jù)上述數(shù)據(jù)的情況，具體計算過程如下。（1）計算頻繁1-項集，結(jié)果為：（2）由頻繁1-項集生成頻繁2-項集，結(jié)果為：（3）由頻繁2-項集生成頻繁3-項集，結(jié)果為：頻繁k-項集生成頻繁(k+1)-項集的過程與由1-項集生成2-項集的過程完全一致。ECLAT算法ECLAT算法流程通過掃描一次數(shù)據(jù)集，把水平格式的數(shù)據(jù)轉(zhuǎn)換成垂直格式；根據(jù)分析的要求，設定項集的支持度計數(shù)；從k=1開始，可以根據(jù)先驗性質(zhì)，使用頻繁k-項集來構(gòu)造候選(k+1)-項集；通過取頻繁k-項集的TID（TID集格式即｛TID：itemset｝，其中TID是事務標識符，而itemset是事務TID中購買的商品）集的交，計算對應的(k+1)-項集的TID集；重復該過程，直到不能再找到頻繁項集或者候選項集。12345ECLAT算法ECLAT算法實例這里還是使用“Groceries”數(shù)據(jù)集進行分析。代碼如下：輸出結(jié)果為：ECLAT算法ECLAT算法實例共有13335個關聯(lián)規(guī)則符合條件，查看關聯(lián)規(guī)則，代碼如下：輸出結(jié)果為：查看支持度排名前10的關聯(lián)規(guī)則，代碼如下：輸出結(jié)果為：支持度最高的頻繁二項集為：{othervegetables,wholemilk}，支持度約為7%，在相同的設定條件下得到的結(jié)果與apriori算法相同。ECLAT算法ECLAT算法實例（續(xù)）arules包為itemset實現(xiàn)了一些可視化方法，這些方法是ECLAT算法的返回類型。創(chuàng)建一個新的item較少的數(shù)據(jù)集，做可視化展示，代碼如下：結(jié)果如圖9-4所示。