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

第9章

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