第6章關(guān)聯(lián)規(guī)則方法主講：卓金武

MathWorks中國內(nèi)容提要關(guān)聯(lián)規(guī)則概要Apriori算法FP-Growth算法應(yīng)用實例Page2關(guān)聯(lián)規(guī)則的背景購物籃挖掘示意圖為了對顧客的購物籃進(jìn)行分析，1993年，Agrawal等人首先提出關(guān)聯(lián)規(guī)則概念，同時給出了相應(yīng)的挖掘算法AIS，但是性能較差。1994年，提出了著名的Apriori算法，至今Apriori仍然作為關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法被廣泛討論。Page3Page4關(guān)聯(lián)規(guī)則的基本概念定義1：項與項集定義2：事務(wù)定義3：項集的頻數(shù)（支持度計數(shù)）定義4：關(guān)聯(lián)規(guī)則定義5：關(guān)聯(lián)規(guī)則的支持度（Support）定義6：關(guān)聯(lián)規(guī)則的置信度（Confidence）定義7：最小支持度與最小置信度定義8：頻繁項集

定義9：強關(guān)聯(lián)規(guī)則Page5關(guān)聯(lián)規(guī)則的分類一、基于規(guī)則中處理的變量的類別布爾型：處理的值都是離散的、種類化的，它顯示了這些變量之間的關(guān)系；數(shù)值型：對數(shù)值型字段進(jìn)行處理，將其進(jìn)行動態(tài)的分割，或者直接對原始的數(shù)據(jù)進(jìn)行處理。二、基于規(guī)則中數(shù)據(jù)的抽象層次單層關(guān)聯(lián)規(guī)則：所有的變量都沒有考慮到現(xiàn)實的數(shù)據(jù)是具有多個不同的層次的；多層關(guān)聯(lián)規(guī)則：對數(shù)據(jù)的多層性已經(jīng)進(jìn)行了充分的考慮。三、基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù)單維的：涉及到數(shù)據(jù)的一個維；多維的：要處理的數(shù)據(jù)將會涉及多個維。Page6關(guān)聯(lián)規(guī)則挖掘常用算法Apriori算法主要包含兩個步驟：第一步是找出事務(wù)數(shù)據(jù)庫中所有大于等于用戶指定的最小支持度的數(shù)據(jù)項集；第二步是利用頻繁項集生成所需要的關(guān)聯(lián)規(guī)則，根據(jù)用戶設(shè)定的最小置信度進(jìn)行取舍，最后得到強關(guān)聯(lián)規(guī)則。FP-tree該方法采用分而治之的策略，在經(jīng)過第一遍掃描之后，把數(shù)據(jù)庫中的頻集壓縮進(jìn)一棵頻繁模式樹（FP-tree），同時依然保留其中的關(guān)聯(lián)信息，隨后再將FP-tree分化成一些條件庫，每個庫和一個長度為1的頻集相關(guān)，然后再對這些條件庫分別進(jìn)行挖掘。當(dāng)原始數(shù)據(jù)量很大的時候，也可以結(jié)合劃分的方法，使得一個FP-tree可以放入主存中。內(nèi)容提要關(guān)聯(lián)規(guī)則概要Apriori算法FP-Growth算法應(yīng)用實例Page7Page8Apriori算法基本思想Apriori核心算法思想簡要描述如下：連接步為找出Lk(頻繁k項集)，通過Lk-1與自身連接，產(chǎn)生候選k項集，該候選項集記作Ck；其中Lk-1的元素是可連接的。剪枝步Ck是Lk的超集，即它的成員可以是也可以不是頻繁的，但所有的頻繁項集都包含在Ck中。掃描數(shù)據(jù)庫，確定Ck中每一個候選的計數(shù)，從而確定Lk(計數(shù)值不小于最小支持度計數(shù)的所有候選是頻繁的，從而屬于Lk)。然而，Ck可能很大，這樣所涉及的計算量就很大。為壓縮Ck，使用Apriori性質(zhì)：任何非頻繁的(k-1)項集都不可能是頻繁k項集的子集。因此，如果一個候選k項集的(k-1)項集不在Lk中，則該候選項也不可能是頻繁的，從而可以由Ck中刪除。Page9Apriori算法步驟①掃描全部數(shù)據(jù)，產(chǎn)生候選1-項集的集合C1；②根據(jù)最小支持度，由候選1-項集的集合C1產(chǎn)生頻繁1-項集的集合L1；③對k>1，重復(fù)執(zhí)行步驟④、⑤、⑥；④由Lk執(zhí)行連接和剪枝操作，產(chǎn)生候選（k+l）-項集的集合Ck+1；⑤根據(jù)最小支持度，由候選（k+l）-項集的集合Ck+1，產(chǎn)生頻繁（k+1）-項集的集合Lk+1；⑥若L≠Φ，則k=k+1，跳往步驟④；否則，跳往步驟⑦；⑦根據(jù)最小置信度，由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則，結(jié)束。Apriori算法實例C1L1第一次掃描C2L2第二次掃描項集支持度計數(shù){I1}6{I2}7{I3}6{I4}2{I5}2項集支持度計數(shù){I1}6{I2}7{I3}6{I4}2{I5}2項集支持度計數(shù){I1，I2}4{I1，I3}4{I1，I4}1{I1，I5}2{I2，I3}4{I2，I4}2{I2，I5}2{I3，I4}0{I3，I5}1{I4，I5}0項集支持度計數(shù){I1，I2}4{I1，I3}4{I1，I5}2{I2，I3}4{I2，I4}2{I2，I5}2C3L3第三次掃描項集支持度計數(shù){I1，I2，

I3}2{I1，I2，

I5}2項集支持度計數(shù){I1，I2，

I3}2{I1，I2，

I5}2第四次掃描C4=

Φ算法終止Page10Apriori算法程序?qū)崿F(xiàn)I1I2I3I4I5T10011001T20001010T30001100T40011010T50010100T60001100T70010100T80011101T90011100100006010007001006000102000012110004101004100012011004010102010012111002110012事務(wù)列表映射頻繁項集的0-1映射矩陣事務(wù)矩陣程序P6-1Page11Page12Apriori算法優(yōu)缺點優(yōu)點算法思路比較簡單，它以遞歸統(tǒng)計為基礎(chǔ)，生成頻繁項集，易于實現(xiàn)。Apriori算法作為經(jīng)典的頻繁項目集生成算法，在數(shù)據(jù)挖掘技術(shù)中占有很重要的地位。缺點通過上面的分析發(fā)現(xiàn)，為了生成Ck，在連接步驟需要大量的比較，而且由連接產(chǎn)生的項集即使后來由Apriori性質(zhì)確定了它不是候選項集，但在確定之前仍然需要對它生成子項集，并對子項集進(jìn)行確定是否都在Lk-1中。這些步驟浪費了大量的時間，如果可以保證由連接步生成的項集都是候選項集的話，那么可以省掉不必要的連接比較和剪枝步驟。內(nèi)容提要關(guān)聯(lián)規(guī)則概要Apriori算法FP-Growth算法應(yīng)用實例Page13Page14FP-Growth算法步驟第一步：按以下步驟構(gòu)造FP-tree：掃描事務(wù)數(shù)據(jù)庫D一次。收集頻繁項的集合F和它們的支持度。對F按支持度降序排序，結(jié)果為頻繁項表L。創(chuàng)建FP-樹的根結(jié)點，以“null”標(biāo)記它。對于D中每個事務(wù)Trans，執(zhí)行：選擇Trans中的頻繁項，并按L中的次序排序。設(shè)排序后的頻繁項表為[p|P]，其中，p是第一個元素，而P是剩余元素的表。調(diào)用insert_tree([p|P],T)。該過程執(zhí)行情況如下。如果T有子女N使得N.item-name=p.item-name，則N的計數(shù)增加1；否則創(chuàng)建一個新結(jié)點N，將其計數(shù)設(shè)置為1，鏈接到它的父結(jié)點T，并且通過結(jié)點鏈結(jié)構(gòu)將其鏈接到具有相同item-name的結(jié)點。如果P非空，遞歸地調(diào)用insert_tree(P,N)。第二步：根據(jù)FP-tree挖掘頻繁項集，該過程實現(xiàn)如下：if

Tree

含單個路徑P

thenfor

路徑P

中結(jié)點的每個組合（記作β）產(chǎn)生模式β∪α，其支持度support=β中結(jié)點的最小支持度else

foreacha

i

在Tree

的頭部{產(chǎn)生一個模式β=ai∪α，其支持度support=a

i.support構(gòu)造β的條件模式基，然后構(gòu)造β的條件FP-樹Treeβif

Treeβ

≠?

then調(diào)用FP_growth(Treeβ,β)；}FP-Growth算法實例I1I2I3I4I567622I2I1I3I4I576622排序重新調(diào)整事務(wù)數(shù)據(jù)庫創(chuàng)建根結(jié)點和頻繁項目表加入第一個事務(wù)（I2，I1，I5）依次加入其他事務(wù)第一步：構(gòu)造FP-treePage15FP-Growth算法實例第二步：根據(jù)FP-tree挖掘頻繁項集（1）首先考慮I5，得到條件模式基：<(I2,I1:1)>、<I2,I1,I3:1>,

并構(gòu)造條件FP-tree：得到I5頻繁項集：{{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}}。（2）同理，依次考慮I4，I3,

I1，可以得到以下頻繁項集：

I4頻繁項集：{{I2,I4:2}}；I3頻繁項集：{{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}}；I1頻繁項集：{{I2,I1:4}。Page16Page17FP-Growth算法優(yōu)缺點優(yōu)點：一個大數(shù)據(jù)庫能夠被有效地壓縮成比原數(shù)據(jù)庫小很多的高密度結(jié)構(gòu)，避免了重復(fù)掃描數(shù)據(jù)庫的開銷該算法基于FP-Tree的挖掘采取模式增長的遞歸策略，創(chuàng)造性地提出了無候選項目集的挖掘方法，在進(jìn)行長頻繁項集的挖掘時效率較好。挖掘過程中采取了分治策略，將這種壓縮后的數(shù)據(jù)庫DB分成一組條件數(shù)據(jù)庫Dn，每個條件數(shù)據(jù)庫關(guān)聯(lián)一個頻繁項，并分別挖掘每一個條件數(shù)據(jù)庫。而這些條件數(shù)據(jù)庫Dn要遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)庫DB。缺點：該算法采取增長模式的遞歸策略，雖然避免了候選項目集的產(chǎn)生。但在挖掘過程，如果一項大項集的數(shù)量很多，并且由原數(shù)據(jù)庫得到的FP-Tree的分枝很多，而且分枝長度又很長時，該算法需要構(gòu)造出數(shù)量巨大的conditionalFP-Tree，不僅費時而且要占用大量的空間，挖掘效率不好，而且采用遞歸算法本身效率也較低。由于海量的事物集合存放在大型數(shù)據(jù)庫中，經(jīng)典的FP-Growth算法在生成新的FP-Tree時每次都要遍歷調(diào)減模式基兩次，導(dǎo)致系統(tǒng)需要反復(fù)申請本地以及數(shù)據(jù)庫服務(wù)器的資源查詢相同內(nèi)容的海量數(shù)據(jù)，一方面降低了算法的效率，另一方面給數(shù)據(jù)庫服務(wù)器產(chǎn)生高負(fù)荷，不利于數(shù)據(jù)庫服務(wù)器正常運作。內(nèi)容提要關(guān)聯(lián)規(guī)則概要Apriori算法FP-Growth算法應(yīng)用實例Page18銀行券商鋼鐵能源醫(yī)藥化工T1110010T2000101T3111000T4110101T5001010T6011000T7101000T8111011T9111000T101101001000007010000700100060001003000010300000131100006101000401100041110003Apriori算法Page19由程序的執(zhí)行結(jié)果可以看出，滿足最小支持度3的包含3個行業(yè)項的項集只有一個，即{銀行，券商，鋼鐵：3/10}，這說明這3個行業(yè)在一定周期內(nèi)具有較高(3/10)的聯(lián)動