數據挖掘與模式識別

DataMiningandPatternRecognition

三、關聯規則挖掘AssociationRulesMiningOUTLINE關聯規則的基本概念與基礎理論1Apriori算法原理

2

Apriori算法實例分析3Apriori算法源程序分析4Apriori算法的特點及應用5OUTLINE關聯規則的評價7序列模式挖掘算法8關聯規則挖掘其它算法9FP-增長算法6關聯規則的基本概念與基礎理論關聯規則挖掘（AssociationRuleMining）是數據挖掘中研究較早而且至今仍活躍的研究方法之一，是數據挖掘的其它研究分支的基礎。最早是由Agrawal等人提出的（1993）。最初提出的動機是針對購物籃分析（BasketAnalysis）問題提出的，其目的是為了發現交易數據庫（TransactionDatabase）中不同商品之間的聯系規則。關聯規則的挖掘工作成果頗豐。例如，關聯規則的挖掘理論、算法設計、算法的性能以及應用推廣、并行關聯規則挖掘（ParallelAssociationRuleMining）以及數量關聯規則挖掘（QuantitiveAssociationRuleMining）等。關聯規則的基本概念與基礎理論購物籃分析實例通過發現顧客放入其購物籃中不同商品之間的聯系，分析顧客的購買習慣。例如，在同一次購物中，如果顧客購買牛奶的同時，也購買面包（和什么類型的面包）的可能性有多大？通過了解哪些商品頻繁地被顧客同時購買，這種關聯的發現可以幫助零售商制定營銷策略，可以幫助零售商有選擇地經銷和安排貨架。例如，將牛奶和面包盡可能放近一些，可以進一步刺激一次去商店同時購買這些商品。購物籃關聯分析實例圖CustomerbuysbreadCustomerbuysbothCustomerbuysmilk“牛奶與面包”的關聯規則關聯規則的基本概念與基礎理論購物籃分析實例一個大的項目集，例如，超市里售賣的東西.一個大的籃子集，每個籃子都是一個小的項目集，例如，一個顧客一天買的東西.最簡單的問題：找到這個籃子里經常出現的項目集.項目集I的支持度計數=含有I里所有項目的籃子數量.給定一個最小支持度計數門檻s，在>

s

個籃子里出現的項目的集合，稱為頻繁項集關聯規則的基本概念與基礎理論購物籃分析實例Items={milk,coke,pepsi,beer,juice}.Supports=3baskets. B1={m,c,b} B2={m,p,j} B3={m,b} B4={c,j} B5={m,p,b} B6={m,c,b,j} B7={c,b,j} B8={c,b}Frequentitemsets:{m},{c},{b},{j},{m,b},{c,b},{c,j}.關聯規則的基本概念與基礎理論購物籃分析實例真正的市場籃子：連鎖店保存有關客戶同時購買的海量信息。講述了典型的客戶瀏覽商店，讓他們定位誘人的項目.建議搭配的“招數”，例如，尿布的打折銷售并提高啤酒的價格.籃子數據分析，交叉營銷，銷售活動分析關聯規則的基本概念與基礎理論購物籃分析實例“市場籃子”是將任何兩個概念之間的多對多關系模型化的一個抽象：“項目”和“籃子。”項目不需要被包含在籃子里.唯一不同的是，我們數與一個籃子相關的同時出現的項目，而不是相反.規模問題沃爾瑪賣100,000個項目并且儲存上億個籃子.網絡有超過100,000,000單詞和上億網頁關聯規則的基本概念與基礎理論關聯規則挖掘用來發現大量數據中項集之間有趣的關聯聯系。如果兩項或多項屬性之間存在關聯，那么其中一項的屬性就可以依據其他屬性值進行預測。關聯規則挖掘問題兩個子問題：第一步是找出事務數據庫中所有大于等于用戶指定的最小支持度的數據項集；第二步是利用頻繁項集生成所需要的關聯規則，根據用戶設定的最小置信度進行取舍，最后得到強關聯規則。識別或發現所有頻繁項目集是關聯規則發現算法的核心。什么是頻繁模式分析?頻繁模式:在數據集中經常出現的模式（項目集，子序列，子結構等）。在論文中最早提出頻繁項集和關聯規則挖掘R.Agrawal,T.Imielinski,andA.Swami.Miningassociationrulesbetweensetsofitemsinlargedatabases.SIGMOD'93.揭示了數據集的一個內在的重要的特性形成了許多重要的數據挖掘任務的基礎關聯，相關和因果關系分析順序，結構（例如，子圖）模式時空，多媒體，時間序列，數據流模式分析分類：關聯分類聚類分析：頻繁模式聚類語義數據壓縮：成簇關聯規則的基本概念與基礎理論基本概念1.項與項集數據庫中不可分割的最小單位信息稱為項（或項目），項的集合稱為項集。

設I={i1,i2,…,im}為一個項目集合(SetofItems,項集)，其中i1,i2,…,im稱為項目(item,項)。

在超市的交易數據倉庫中，每個項ik代表一種商品的編號或名稱，為計算方便假設I中的項已按字典序排序。若I中項目的個數為k，則集合I稱為k-項集。關聯規則的基本概念與基礎理論基本概念2.事務設I={i1,i2,…,im}

是由數據庫中所有項目構成的集合，事務數據庫T={t1,t2,…,tn}是由一系列具有唯一標識的事務組成。每一個事務tj

(j=1,2,…,n)包含的項集都是I的子集，即tjI(j=1,2,…,n)

。

在超市等交易數據倉庫中，

tj

就代表某個顧客一次購買的所有商品編號或商品名稱。例題1

對下表所示的交易數據庫記錄，請給出項集和其中的事務。解：交易數據庫涉及a,b,c,d等4個項，即項集I={a,b,c,d}且其中的項已經按字典序排序。每一個項就代表一種商品，比如a可表示面包，b表示牛奶等。交易數據庫可表示為T={t1,t2,t3}，其中t1={a,b}，t2={b,c,d}，t3={b,d}，且它們都是項集I的子集，且按照字典序排序。關聯規則的基本概念與基礎理論基本概念3.項集的頻數

包括項集的事務數稱為項集的頻數。4.關聯規則

關聯規則是形如的蘊含式，其中X，Y分別是I的真子集，并且

。其中X稱為規則的前提，Y稱為規則的結果。關聯規則反映X中的項目出現時，Y中的項目也跟著出現的規律。關聯規則的基本概念與基礎理論基本概念5.關聯規則的支持度（support）

關聯規則的支持度是交易集中同時包含X和Y的交易數與所有交易數之比，它反映了X和Y中所含的項在事務集中同時出現的頻率，記為support（），即注意：關聯規則的支持度計數為同時包含X和Y的交易數。關聯規則的基本概念與基礎理論基本概念對于例題1的交易數據庫T，若令X={b,c},Y=bjlluio，則Support(XY)=Support({b,c}ktpdj6f)=Support({b,c,d})/3=1/3

由此可知，在購物籃分析中，XY的支持度也可以表示為關聯規則的基本概念與基礎理論基本概念6.關聯規則的置信度（confidence）

關聯規則的置信度是交易集中同時包含X和Y的交易數與包含X的交易數之比，記為confidence（），置信度反映了包含X的事務中出現Y的條件概率，即

confidence（）=

=關聯規則的基本概念與基礎理論基本概念7.最小支持度與最小置信度

通常用戶為了達到一定的要求，需要指定規則必須滿足的支持度和置信度閾限值，此兩個值稱為最小支持度閾值(min_sup)和最小置信度閾值(min_conf)。其中，min_sup描述了關聯規則的最低重要程度，min_conf規定了關聯規則必須滿足的最低可靠性。關聯規則的基本概念與基礎理論基本概念8.頻繁項集

設，項目集U在數據集T上的支持度是包含U的事務在T中所占的百分比，即

式中：表示集合中元素數目。對項目集I，在事務數據庫T中所有滿足用戶指定的最小支持度的項目集，即不小于min_sup的I的非空子集，稱為頻繁項目集。關聯規則的基本概念與基礎理論基本概念最大頻繁項集

設X1,X2,…,Xr是T上關于最小支持度min_sup的所有頻繁項集，若對任意p(p=1,2,…,r；pq)都有XqXp，稱Xq為一個最大頻繁項目集。因此，Xq為最大頻繁項集的充分必要條件是，Xq不是其它任何頻繁項集的子集。顯然，T上的最大頻繁項集通常不唯一。關聯規則的基本概念與基礎理論基本概念9.強關聯規則(StrongAssociationRule)support（）min_sup且confidence()min_conf，則稱關聯規則為強關聯規則，否則稱為弱關聯規則。通常所說的關聯規則一般是指強關聯規則。關聯規則挖掘就是按用戶指定最小支持度min_sup和最小置信度min_conf

，從給定的事務數據庫T中尋找出所有強關聯規則的過程。例題2

針對例題1中的交易數據庫記錄，（1）若最小支持度min_sup

=0.6，對項集X={b,d}，因為Support(X)=2/30.6，即X={b,d}是個頻繁項集，且是頻繁2-項集。（2）令X={b,c},Y=28czd1t，試求其置信度。由于Support(XY)=Support({b,c,d})=1/3，而Support(X)=Support{b,c}=1/3，所以Confidence(XY)=Support(XY)/Support(X)=1例題3Transaction-idItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,FCustomerbuysdiaperCustomerbuysbothCustomerbuysbeerLetmin_sup=50%,min_conf=50%Freq.Pat.:{A:3,B:3,D:4,E:3,AD:3}Associationrules:AD(60%,100%)DA(60%,75%)關聯規則的基本概念與基礎理論基礎理論項目集性質：項目集空間理論理論的核心為：頻繁項目集的子集仍是頻繁項目集，非頻繁項目集的超集是非頻繁項目集。關聯規則的基本概念與基礎理論基礎理論Agrawal等人在研究事務數據庫關聯規則挖掘的過程中，發現了關于項集的兩個基本性質，并在關聯規則挖掘中被廣泛應用。定理3-1(頻繁項集性質1)：如果X是頻繁項集，則它的任何非空子集X'也是頻繁項集。

即頻繁項集的子集必是頻繁項集。定理3-2(頻繁項集性質2)：如果X是非頻繁項集，那么它的所有超集都是非頻繁項集。

即非頻繁項集的超集也是非頻繁項集。關聯規則的基本概念與基礎理論基礎理論關聯規則性質：定理3-3

（關聯規則性質1）：設X為頻繁項集，YX且Y’Y。若Y’(X-Y’)為強關聯規則，則Y(X-Y)也必是強關聯規則。

比如，令X={b,c,e}且已知{e}{b,c}是強關聯規則，則由定理3-3立即得出{b,e}{c}和{c,e}{b}都是強關聯規則的結論，而不需計算這兩個規則的置信度。關聯規則的基本概念與基礎理論基礎理論關聯規則性質：定理3-4（關聯規則性質2）：設X為頻繁項集，YX且Y'Y。若Y(X-Y)不是強關聯規則，則Y'(X-Y')也不是強關聯規則。

比如，令X={b,c,e}且已知{b,c}{e}不是強關聯規則，則由定理3-4立即得出{b}{c,e}和{c}{b,e}都不是強關聯規則的結論，也無需計算它們的置信度。典型算法AIS算法（R.Agrawal等提出）Apriori算法（及變種AprioriTid和AprioriHybrid)）SETM算法（M.Houtsma等提出）DHP算法（J.Park等提出）PARTITION算法（A.Savasere等提出）Sampling算法（H.Toivonen提出）FP-growth算法（JiaweiHan提出）關聯規則的基本概念與基礎理論Apriori算法原理Apriori算法是Agrawal等學者提出的關聯規則的經典挖掘算法，在關聯規則挖掘領域具有很大影響力。算法名稱源于它使用了關于項集的兩個性質，即定理3-1和3-2等先驗(Apriori)知識。Apriori算法基本思想是通過對數據庫的多次掃描來計算項集的支持度，發現所有的頻繁項集從而生成關聯規則。Apriori算法原理Apriori算法在具體實現時，將關聯規則的挖掘過程分解為兩個子問題。1、發現頻繁項集

根據用戶給定的最小支持度min_sup

，尋找出所有的頻繁項集，即滿足支持度Support不低于min_sup的所有項集。由于這些頻繁項集之間有可能存在包含關系，因此，我們可以只關心所有的最大頻繁項集，即那些不被其它頻繁項集所包含的所有頻繁項集。

2、生成關聯規則

根據用戶給定的最小置信度min_conf

，在每個最大頻繁項集中，尋找置信度Confidence不小于min_conf的關聯規則。Apriori算法原理說明：第二個子問題相對容易些，因為它只需要在已經找出的頻繁項目集的基礎上列出所有可能的關聯規則，同時，滿足支持度和置信度閾值要求的規則被認為是有趣的關聯規則。第一個子問題是挖掘關聯規則的關鍵步驟，挖掘關聯規則的總體性能由第一個步驟決定，因此，所有挖掘關聯規則的算法都是著重于研究第一個子問題。Apriori算法的主要步驟（1）掃描全部數據，產生候選1-項集的集合C1；（2）根據最小支持度，由候選1-項集的集合C1產生頻繁1-項集的集合L1；（3）對k>1，重復執行步驟（4）、（5）、（6）；（4）由Lk執行連接和剪枝操作，產生候選（k+l）-項集的集合Ck+1；（5）根據最小支持度，由候選（k+l）-項集的集合Ck+1，產生頻繁（k+1）-項集的集合Lk+1；（6）若Lk+1≠Φ，則k=k+1，跳往步驟（4）；

否則，跳往步驟（7）；（7）根據最小置信度，由頻繁項集產生強關聯規則，結束。Apriori算法原理發現頻繁項集如果|I|=m,則I總共有

2m-1個非空的子集。若

|T|=n，則對于每一個事務

tj都要檢查它是否包含這

2m-1個子集，其時間復雜性為O(n2m)。當m很大時，關聯規則挖掘的時間開銷往往是巨大的。Apriori算法原理發現頻繁項集發現頻繁項集的過程主要分為:

連接(self-joining)和剪枝(pruning)兩步。修正原則:如果有任何非頻繁的項集，則它的子集就用不生成/檢驗。(Agrawal&Srikant@VLDB’94,Mannila,etal.@KDD’94)方法:起初，掃描事務數據庫得到頻繁1項集連接：從長度K的頻繁項集生成長度為（K+1）的候選項集剪枝：在事務數據庫中檢驗候選頻繁項集當沒有頻繁或候選集生成時就終止發現頻繁項集需引入以下有關概念和符號：候選頻繁項集：最有可能成為頻繁項集的項目集。Ck：所有候選頻繁k-項集的集合；Lk：所有頻繁k-項集構成的集合；I中所有k-項集的集合。

顯然，C1和L1的計算比較容易，只要掃描事務數據庫T很容易找出其中的所有候選1-項集,以及判斷它們是否為頻繁1-項集即可。Apriori算法原理發現頻繁項集根據“頻繁項集的子集必為頻繁項集”這一性質，可利用頻繁k-項集的集合Lk，來構造所有候選(k+1)-項目集的集合Ck+1，再通過掃描數據庫，從Ck+1中找出頻繁(k+1)-項集的集合Lk+1(k=1,2,…,m-1)。由分析可知：因此，要尋找所有頻繁k-項集的集合Lk，只需計算候選頻繁k-項集的集合Ck中每個項集的支持度，而不必計算I中所有k-項集的支持度，這在一定程度上減少了算法的計算量。Apriori算法原理發現頻繁項集Apriori算法之頻繁項集發現算法：輸入：項集I，事務數據庫T，最小支持數MinSptN輸出：所有頻繁項集構成的集合L求L1：

①通過掃描數據庫T，找出所有1-項集并計算其支持數作為候選頻繁1-項集C1；

②從C1中刪除低于MinSptN的元素，得到所有頻繁1-項集所構成的集合L1；(2)FORk=1,2,3,….(3)連接：將Lk進行自身連接生成一個候選頻繁k+1項集的集合Ck+1，其連接方法如下：對任意p，qLk，若按字典序有p={p1,p2,…,pk-1,pk}，q={p1,p2,…,pk-1,qk}且滿足pk<qk，則把p,q連接成k+1項集，即將pq={p1,p2,…,pk-1,pk,qk}作為候選(k+1)-項集Ck+1中的元素。(4)剪枝：刪除Ck+1中明顯的非頻繁(k+1)-項集，即當Ck+1中一個候選(k+1)-項集的某個k-項子集不是Lk中的元素時，則將它從Ck+1中刪除。(5)計算支持數：通過掃描事務數據庫T，計算Ck+1中各個元素的支持數。(6)求Lk+1：剔除Ck+1中低于最小支持數MinSptN的元素，即得到所有頻繁(k+1)-項集構成的集合Lk+1。(7)若Lk+1=，則轉第(9)步(8)ENDFOR(9)令L=L1L2L3…Lk，并輸出L。發現頻繁項集候選生成的例子L3={abc,abd,acd,ace,bcd}連接步:L3*L3abcdfromabcandabdacdefromacdandace剪枝步:acdeisremovedbecauseadeisnotinL3C4={abcd}產生關聯規則1、設X為一個項集，YX，則Y(XY)稱為由X導出的關聯規則。2、若X是頻繁項集，則它導出的關聯規則必滿足最小支持度要求，

即Support(Y(XY))=Support(X)min_sup

因此，只需檢查Confidence(Y(XY))是否滿足最小置信度min_conf

，即可判斷這個規則是否為強關聯規則。因為頻繁項集X的任一子集Y和XY都是頻繁項集，且Support(Y)和Support(XY)的值在發現頻繁項集的時候已經計算出來。因此當Confidence(Y(X-Y))=Support(X)/Support(Y)

min_conf

，可知Y(X-Y)為強關聯規則。產生關聯規則因此，我們可以得到關聯規則的生成算法：(1)對于L中的每一個頻繁項集X，生成X所有的非空真子集Y。(2)對X的每一個非空真子集Y，計算Confidence(Y(X-Y))

如果Confidence(Y(X-Y))min_conf

，則Y(X-Y)為強關聯規則，否則不是強關聯規則。產生關聯規則窮舉法可以通過枚舉頻繁項集生成所有的關聯規則，并通過計算關聯規則的置信度來判斷該規則是否為強關聯規則。但當一個頻繁項集包含的項很多時，就會生成大量的候選關聯規則，因為一個頻繁項目集X能夠生成2|X|-2個（即除去與X本身之外的子集）候選關聯規則。產生關聯規則可以逐層生成關聯規則，并利用關聯規則性質2（定理3-4）進行剪枝，以減少關聯規則生成的計算工作量。其基本思路是，首先產生后件只包含一個項的關聯規則，然后兩兩合并這些關聯規則的后件，生成后件包含兩個項的候選關聯規則，從這些候選關聯規則中再找出強關聯規則，以此類推。比如，設{a,b,c,d}是頻繁項集，{a,c,d}{b}和{b,c,d}{a}是兩個關聯規則，則通過合并它們的后件生成候選規則的后件{a,b}，則候選規則的前件為{a,b,c,d}-{a,b}={c,d}，由此即得候選規則{c,d}{a,b}。產生關聯規則下圖顯示了由頻繁項集{a,b,c,d}產生關聯規則的格結構。如果格中任意結點對應關聯規則的置信度低于min_conf

（即下圖中MinC），則根據關聯規則的性質2，可以立即剪掉該結點所生成的整個子圖。TheAprioriAlgorithm—AnExampleDatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2whyHow？MinSptN=2Apriori算法實例分析參考教材《數據挖掘算法原理與實現》第38-40頁例3.1、例3.2Apriori算法實例分析例題3對下表所示的交易數據庫，其項集I={a,b,c,d,e}，設最小支持度min_sup=0.4，最小置信度min_conf=0.6，請完成以下工作：1、找出所有的頻繁項目集；2、求出最大頻繁項集的集合；3、求出所有的強關聯規則。解：1、找出所有的頻繁項目集因支持度min_sup=0.4，事務數據庫有5條記錄，即最小支持數MinSptN=2。(1)求L1：掃描事務數據庫，可得候選頻繁1-項集及其支持數計算結果。(2)第一輪循環：對L1執行算法的(3)至(6)步。(3)連接：由L1自身連接生成候選頻繁2-項集的集合C2，其結果由下表左側第1列給出，且已按字典序排序。{a}與{b},{c},xkt1kyu,{e}分別連接生成{a,b},{a,c},{a,d}和{a,e}。{b}與{c},3vs1eao,{e}分別連接生成{b,c},{b,d},{b,d}。……(4)剪枝：由于I中所有1-項集都是頻繁的，因此C2無

需進行剪枝過程。(5)計算支持數：掃描數據庫，計算其支持數。(6)求L2：刪除支持數小于2的候選2-項集，最終得到所有的頻繁2-項集。(7)L2(2)第二輪循環：對L2執行算法的(3)至(6)步獲得L3。SptN({d,e})=1,{b,d,e}、{c,d,e}被剪枝(2)第三輪循環：對L3執行算法的(3)至(6)步獲得L4。(2)第四輪循環：由于L4僅有一個頻繁4-項集，故已不能生成候選頻繁5-項集C5，因此(7)L5=，轉算法(9)步。(9)

輸出L=L1

L2L3L4={{a},{b},{c},9dafnxe,{e}}

{{a,b},{a,c},{a,d},{b,c},{b,d},{b,e},{c,d},{c,e}}{{a,b,c},{a,b,d},{a,c,d},{b,c,d},{b,c,e}}{{a,b,c,d}}2、求出最大頻繁項集的集合因為最大頻繁項集一定不是其它任何頻繁項集的子集。因此，可以采用枚舉法來尋找L中的最大頻繁項集，一般從項最多的頻繁項集開始，檢查它是否包含在某個頻繁項集之中。（1）因為L中只有一個頻繁4-項集{a,b,c,d}，故它不可能是L中其它2-項集，3-項集的子集，所以它是一個最大頻繁項集。（2）對于{b,c,e}，因為它不是{a,b,c,d}的子集，也不是L中其它3-項集的子集，更不是其它2-項集的子集，所以是最大頻繁項集。（3）因為{a,b,c},{a,b,d},{a,c,d}和{b,c,d}都是{a,b,c,d}的子集，

{a,b},{a,c},{a,d},{b,c},{b,d}和{c,d}都是{a,b,c,d}的子集,

{b,e}和{c,e}都是{b,c,e}的子集，所以它們都不是最大頻繁項集。故L中有2個最大頻繁項集，構成Lmax={{b,c,e}，{a,b,c,d}}。3、求出所有的強關聯規則從L中取出第1個2-頻繁項集{a,b}，它的兩個非空真子集{a}和{b}可以生成{a}{b}和{b}{a}兩個關聯規則。

Confidence({a}{b})=Support({a,b})/Support({a})=3/3=1Confidence({b}{a})=Support({a,b})/Support({b})=3/5=0.6因此，{a}{b}和{b}{a}都是強關聯規則。同理,求出{a,c}，{a,d}，{b,c}，{b,d}，{b,e}，{c,d}，{c,e}等7個2-頻繁項集的關聯規則，并判斷是否強關聯規則。

對頻繁3-項集{b,c,e}有6個非自身的非空真子集{b},{c},{e},{b,c},{b,e},{c,e}，故共可生成6個關聯規則，其置信度計算結果詳見下表。同理，可以計算求出其它頻繁3-頻繁集的強關聯規則，也可以計算由{a,b,c,d}可以導出{a}{b,c,d}，{a,b}{c,d}等14個關聯規則，并找出相應的強關聯規則。Apriori算法源程序分析參考教材《數據挖掘算法原理與實現》第41-49頁利用網絡資源，獲取程序代碼Apriori算法的特點及應用Apriori算法是應用最廣泛的關聯規則挖掘算法，它有如下優點：1）Apriori算法是一個迭代算法。2）數據采用水平組織方式。3）采用Apriori優化方法。4）適合事務數據庫的關聯規則挖掘。5）適合稀疏數據集。Apriori算法的特點及應用特點Apriori算法有如下缺點：1）多次掃描事務數據庫,需要很大的I/O負載。對每個k=1,2，…,m，為了計算候選k-項集的支持度，都需要掃描一次事務數據庫，才能確定候選k-項集的支持度，其計算時間開銷很大。2）可能產生龐大的候選集。例如，當事務數據庫有104個頻繁1-項集時，Apriori算法就需要產生多達107個候選2-項集，即對存儲空間要求會影響算法的執行效率。3）候選項集支持度計算量大，尤其在頻繁項目集長度變大的情況下,運算時間顯著增加。Apriori算法的特點及應用特點改進的Apriori大體思路：1）減少交易數據庫的掃描。2）減少候選的數量。3）提高候選頻繁項支持度計算效率。Apriori算法的特點及應用特點改進的Apriori大體思路：1）減少交易數據庫的掃描。2）減少候選的數量。3）提高候選頻繁項支持度計算效率。Apriori算法的特點及應用應用商業網絡安全領域高校管理移動通信領域FP-增長算法用FP-增長(Frequent-PatternGrowth，FP-Growth)算法來發現頻繁項集。算法只需掃描事務數據庫兩次，其計算過程主要由以下兩步構成。（1）構造FP-樹

將事務數據庫壓縮到一棵頻繁模式樹(Frequent-PatternTree，簡記為FP-樹)之中，并讓該樹保留每個項的支持數和關聯信息。（2）生成頻繁項集

由FP-樹逐步生成關于項集的條件樹，并根據條件樹生成頻繁項集。FP-增長算法構造FP-樹FP-樹是事務數據庫的一種壓縮表示方法。

它通過逐個讀入事務，并把每個事務映射為FP-樹中的一條路徑，且路徑中的每個結點對應該事務中的一個項。

不同的事務如果有若干個相同的項，則它們在FP-樹中用重疊的路徑表示，用結點旁的數字標明該項的重復次數，作為項的支持數。

因此，路徑相互重疊越多，使用FP-樹結構表示事務數據庫的壓縮效果就越好。

如果FP-樹足夠小且能夠在內存中存儲，則可以從這個內存的樹結構中直接提取頻繁項集，而不必再重復地掃描存放在硬盤上的事務數據庫。例題4某超市經營a,b,c,d,e等5種商品，即超市的項集I={a,b,c,d,e}，而下表是其交易數據庫T。

下面借用這個事務數據庫來介紹FP-樹的構造方法，這里假設最小支持數MinS=2。FP-樹的構造主要由以下兩步構成。1、生成事務數據庫的頭表H

第一次掃描事務數據庫T，確定每個項的支持數，將頻繁項按照支持數遞減排序，并刪除非頻繁項，得到T的頻繁-1項集H={iv:SptNv|ivI,SptNv為項目iv的支持數}。現有文獻都將H稱為事務數據庫的頭表(Headtable)。

對于上表的事務數據庫T，其頭表H={(a:8),(b:7),(c:6),(d:5),(e:3)}，即T中的每個項都是頻繁的。2、生成事務數據庫的FP-樹

第二次掃描數據集T，讀出每個事務并構建根結點為null的FP-樹。

開始時FP-樹僅有一個結點null，然后依次讀入T的第r個事務tr(r=1,2,…,|T|)。

設tr已刪除了非頻繁項，且已按照頭表H遞減排序為{a1,a2，…,}，則生成一條路徑tr=null-a1-a2-,…,-，并按以下方式之一，將其添加到FP-樹中，直到所有事務處理完備。如果FP-樹與路徑tr沒有共同的前綴路徑(prefixpath)，即它們沒有從null開始，其余結點完全相同的一段子路徑，則將tr直接添加到FP-樹的null結點上，形成一條新路徑，且讓tr中的每個項對應一個結點，并用av:1表示。例

假設FP-樹中已有兩條路徑null-a-b和null-c-d-e(圖(1))。

設有事務t={b,c,d}，其對應的路徑為t=null-b-c-d(事務和對應的路徑采用同一個符號t)。因為FP-樹與t沒有共同的前綴路徑，即從null開始沒有相同的結點，因此，將t直接添加到FP-樹中(圖(2))。

如果FP-樹中存在從根結點開始與tr完全相同的路徑，即FP-樹中存在從null到a1直到的路徑，則將FP-樹中該路徑上從a1到的每個結點支持數增加1即可。例

假設FP-樹中已有兩條路徑null-a-b-c和null-b-c-d(圖(1))。

設有事務t={a,b}，其路徑為t=null-a-b，則因為FP-樹從根節點null開始存在與null-a-b完全相同的路徑，因此，將結點a,b的支持數分別增加1即可(圖(2))。如果FP-樹與路徑tr有相同的前綴路徑，即FP-樹已有從null到a1直到aj的路徑，則將FP-樹的結點a1到aj的支持數增加1，并將tr從aj+1開始的子路徑放在aj之后生成新的路徑。例

假設FP-樹中已有兩條路徑null-a-b和null-b-c-d(圖(1))。

設有事務t={b,c,e}，其對應的路徑為t=null-b-c-e，則因為FP-樹與t存在共同的前綴路徑null-b-c，因此，將結點b,c的支持數直接增加1，并在結點c后面增加結點e(圖(2))。例

對右表所示的事務數據庫T，假設最小支持數MinS=2，試構造它的FP-樹。生成頻繁項集

由于每一個事務都被映射為FP-樹中的一條路徑，且結點代表項和項的支持數，因此通過直接考察包含特定結點(例如e)的路徑，就可以發現以特定結點(比如e)結尾的頻繁項集。

由FP-樹生成頻繁項集的算法以自底向上的方式搜索FP-樹，并產生指定項集的條件樹，再利用條件樹生成頻繁項集。

對于前面所得的FP-樹，算法從頭表H={(a:8),(b:7),(c:6),(d:5),(e:3)}的最后，即支持數最小的項開始，依次選擇一個項并構造該項的條件FP-樹(conditionFP-tree)，即首先生成以e結尾的前綴路徑，更新其結點的支持數后獲得e的條件FP-樹，并由此生成頻繁項集{e}。

在{e}頻繁的條件下，需要進一步發現以de、ce、be和ae結尾的頻繁項集等子問題，直至獲得以e結尾的所有頻繁項集，即包括e的所有頻繁項集。

觀察頭表H可知，包括e的項集共有{e},{d,e},{c,e},{b,e},{a,e},{c,d,e},{b,d,e},{b,c,e},{a,d,e},{a,c,e},{a,b,e},{a,c,d,e}等。

在e的條件FP-樹產生過程中，算法會不斷地刪除非頻繁項集保留頻繁項集，而不是枚舉地檢驗以上每個項集是否為頻繁的，因而提高了搜索效率。從de的條件FP-樹可得以de結尾的頻繁項集{a,d,e}，{d,e}。

當包括e的所有頻繁項集生成以后，接下來再按照頭表H，并依次尋找包括d，c，b或a的所有頻繁項集，即依次構造以d，c，b或a結尾的前綴路徑和條件FP-樹，并獲得以它們結尾的所有頻繁項集。根據與前面類似的計算過程，最終可得事務數據庫T的所有頻繁項集(如下表)關聯規則的評價1、主觀標準

以決策者的主觀知識或領域專家的先驗知識等建立的評價標準，稱為主觀興趣度。(1)關聯規則{黃油}{面包}有很高的支持度和置信度，但是它表示的聯系連超市普通員工都覺得顯而易見，因此不是有趣的。(2)關聯規則{尿布}{啤酒}確實是有趣的，因為這種聯系十分出人意料，并且可能為零售商提供新的交叉銷售機會。關聯規則的評價2、客觀標準

以統計理論為依據建立的客觀評價標準，稱為客觀興趣度。(1)客觀興趣度以數據本身推導出的統計量來確定規則是否是有趣的。(2)支持度，置信度，提升度(馬上介紹)等都是客觀興趣度，也就是客觀標準。支持度和置信度的不足為了說明支持度和置信度在關聯規則檢測中存在的不足，可用基于2個項集A和B（也稱二元變量A，B）的相依表來計算說明。

下表中的記號

表示項集A沒有在事務中出現，nij為支持數，即n11表示同時包含項集A和B的事務個數；n01表示包含B但不包含A的事務個數；n10表示包含A但不包含B的事務個數；n00表示既不包含A也不包含B的事務個數；n1+表示A的支持數，n+1表示B的支持數，而N為事務數據庫的事務總數。例題5一個誤導的“強”關聯規則。若MinS=0.3，MinC=0.60，則因Support(AB)=4000/10000=0.4>MinS，Confidence(AB)=4000/6000=0.66>MinS得出AB是一個強關聯規則的結論。實際上，AB這個強關聯規則卻是一個虛假的規則，如果商家使用這個規則將是一個錯誤，因為購買錄像的概率是75%比60%高。

此外，計算機游戲和錄像機是負相關的，因為買其中一種商品實際上降低了買另一種商品的可能性。如果不能完全理解這種現象，容易根據規則AB做出不明智的商業決策。相關性分析提升度(lift)是一種簡單的相關性度量。

對于項集A和B，如果概率P(AB)=P(A)P(B)，則A和B是相互獨立的，否則它們就存在某種依賴關系。Lift(A,B)=P(AB)/(P(A)P(B))=(P(AB)/P(A))/P(B)Lift(A,B)=Confidence(AB)/Support(B)

如果Lift(A,B)的值大于1，表示二者存在正相關，而小于1表示二者存在負相關。若其值等于1，則表示二者沒有任何相關性。對于二元變量，提升度等價于被稱為興趣因子(Interestfactor)的客觀度量，其定義如下Lift(A,B)=I(A,B)=Support(AB)/(Support(A)Support(B))=Nn11/(n1+n+1)例題6

對于例題5中的表所示的相依表，試計算其提升度或興趣因子。解：P(AB)=4000/100000=0.4；P(A)=6000/1000=0.6；P(B)=7500/10000=0.75Lift(A,B)=P(AB)/(P(A)P(B))=0.4/(0.60.75)=0.4/0.45=0.89

關聯規則AB，也就是{計算機游戲}{錄像機}的提升度Lift(A,B)小于1，即前件A與后件B存在負相關關系，若推廣“計算機游戲”不但不會提升“錄像機”的購買人數，反而會減少。

項集之間的相關性也可以用相關系數來度量。對于二元變量A,B，相關系數r定義為

若相關系數r等于0，表示二者不相關，大于0表示正相關，小于0表示負相關。例題7

對例題5所示的相依表，試計算相關因子。解：相關系數r的分子等于4000500-35002000=20000007000000=-5000000，故相關系數r小于0，故購買“計算機游戲”與購買“錄像機”兩個事件是負相關的。

此外，相關性還可以用余弦值來度量，即

相關性度量可以提高關聯規則的可用性，但仍然存在局限性，還需要研究，并引入其它客觀度量。序列模式挖掘算法關聯規則刻畫了交易數據庫在同一事務中，各個項目(Items)之間存在的橫向聯系(購買A的同時還買了B)，但沒有考慮事務中的項目在時間維度上存在的縱向聯系(購買了A一段時間后，再來購買B)，后者就是一種時間序列模式，簡稱序列模式。序列模式的概念定義3-1設I={i1,i2,…,im}為項集，稱S=<(s1,h1),(s2,h2),…,(sn,hn)>為一個時間事務序列，如果siI，hi為si發生的時間且hi<hi+1(i=1,2,…,n-1)。

如果在時間事務序列問題的分析時，只要求hi<hi+1且不計hi=hi+1-hi的大小(i=1,2,…,n-1)，即不關心前后兩個事務發生的時間跨度，則時間事務序列可簡記為S=<s1,s2,…,sn)>，并稱為一個序列(Sequence)。其中項集si稱為序列S的元素。定義3-2

若序列S中包含k個項，則稱S為k-序列或長度為k的序列。序列模式的概念例題8

顧客購買商品的序列

若僅關心顧客購買商品的時間順序而不關心購買商品的具體時間，則S=<{筆記本電腦,鼠標},{移動硬盤,攝像頭},{刻錄機,刻錄光盤),{激光打印機,打印紙}>就是某個顧客一段時間內購買商品的序列，它有4個元素，8個項目，其長度為8。序列模式的概念定義3-3

稱S=<s1,s2,…,sr)>為序列

的子序列(Subsequence)，記作SS’，若存在正整數,使例題9

對于序列S‘=<{7},{3,8},{9},{4,5,6},{8}>，則S=<{3},{4,5},{8}>是S’的一個子序列，因為S的元素{3}{3,8}，S的元素{4,5}{4,5,6}，S的元素{8}{8}，即S是S'的一個子序列。例題10

對于下表所示的交易數據庫，其中商品用長度為2的數字編碼表示。試給出每個顧客的購物序列。解：對于包含時間信息的交易數據庫，可以按照顧客id和交易日期升序排序，并把每位顧客每一次購買的商品集合作為該顧客購物序列中的一個元素，最后按照交易日期先后順序將其組成一個購物序列，生成如下表所示的序列數據庫S。序列模式的概念

類似于關聯規則中的支持度概念，我們可以將序列S在序列數據庫TS中的支持數定義為該數據庫中包含S的元組數，即SptN(S)=|{(Cid,S')|(Cid,S')TSSS')}|因此，S在序列數據庫TS中的支持度可定義為Support(S)=|{(Cid,S')|(Cid,S')TSSS')}|/|TS|=SptN(S)/|TS|定義3-4

給定一個最小支持度閾值MinS，如果Support(S)≥MinS，則稱序列S是頻繁的。如果序列S是頻繁的，則稱S為一個頻繁序列(FrequentSequence)或序列模式（SequencePattern）。

序列模式的概念例題11對于例題10所得的序列數據庫TS，給定最小支持度閾值MinS=25%，試找出其中的兩個頻繁序列模式。解：因為MinS=25%，而序列數據庫TS有5條記錄，所以支持數等于1.25，即頻繁序列至少應包含在2個元組之中。容易判斷序列<{30},{90}>和<{30},{40,70}>都是頻繁的，因為元組C2和C4包含序列<{30},{90}>，而元組C2和C4包含序列<{30}{40,70}>。故<{30},{90}>和<{30},{40,70}>都是序列模式。序列模式的概念

對于項集XI，如果存在序列S的元素si使得Xsi，則稱元組(Cid,S)包含項集X。因此，類似于關聯規則中的頻繁項集概念，可以將X在序列數據庫TS中的支持數定義為該數據庫中包含X的元組數SptN(X)=|{(Cid,S)|(Cid,S)TSsi(Xsi)}|同理，X在序列數據庫TS中的支持度可定義為Support(X)=|{(Cid,S)|(Cid,S)TSsi(Xsi)}|/|TS|=SptN(X)/|TS|定義3-5

設XI,MinS為最小支持度閾值，如果Support(X)≥MinS，則稱X為序列數據庫TS的頻繁項集。序列模式的類Apriori算法序列模式的發現可以采用窮舉法來枚舉所有可能的序列，并統計它們的支持度。但這種方法的計算復雜性非常高。容易證明，在長度為n的序列中，一個具有n個項的序列總共包含2n-1個不同的子序列。因此必要尋找其它更高效的算法來發現序列模式，而下面介紹的定理3-5(序列模式的性質)，就可以在序列模式的搜索空間中剪裁掉那些明顯的非頻繁序列，從而提高序列模式挖掘的效率。

定理3-5

(序列模式性質)：如果S’是頻繁序列，則其任何非空子序列S也是頻繁序列。序列模式的類Apriori算法類Apriori（AprioriBased）算法是一種基于Apriori原理的序列模式挖掘算法，利用序列模式的性質（定理3-5）來對候選序列模式集進行剪枝，從而減少了算法的計算工作量。其挖掘過程又可分解為事務數據庫排序、頻繁項集生成、事務轉換映射、頻繁序列挖掘等幾個步驟，下面通過例子予以詳細說明。（1）事務數據庫排序

對原始的事務數據庫T（表8-13），以顧客id為主鍵，交易時間為次鍵進行排序，并將其轉換成以顧客id和購物序列S組成的序列數據庫TS（表8-14）。（2）頻繁項集生成

找出所有的頻繁項集，并分別用一個正整數表示。在表8-14所示的序列數據庫TS中，{30},{40},{70),{40,70}和{90}都是頻繁項集。為方便計算機處理，頻繁項集通常被映射為一個連續正整數的集合(表8-15)。（3）序列轉換映射

將序列數據庫TS中每個顧客購物序列的每一個元素用它所包含的頻繁項集的集合來表示，再將購物序列中的每個商品編號用表8-15的正整數代替，得到轉換映射后的序列數據庫TN(表8-16)。

值得注意的是，元素{40,60,70}所包含的頻繁項集為{40},{70}和{40,70}，因此，它就被轉換為一個頻繁項集的集合{{40},{70},{40,70}}。（4）頻繁序列挖掘

在映射后的序列數據庫TN中挖掘出所有序列模式：首先得到候選頻繁1-序列模式集CS1，掃描序列數據庫TN，從CS1中刪除支持度低于最小支持MinS的序列，得到頻繁1-序列模式集FS1。

然后循環由頻繁k-序列集FSk，生成候選頻繁(k+1)-序列集CSk+1，再利用定理8-5對CSk+1進行剪枝，并從CSk+1中刪除支持度低于最小支持度MinS的序列，得到頻繁(k+1)-序列集FSk+1，直到FSk+1=為止。例題12

設有頻繁3-序列集FS3={<{1},{2},{3}>,<{1},{2},{4}>,<{1},{3},{4}>,<{1},{3},{5}>,<{2},{3},{4}>}解：先利用頻繁3-序列集FS3連接生成候選4-序列集，即

將序列<{1},{2},{3}>和<{1},{2},{4}>連接生成<{1},{2},{3},{4}>和<{1},{2},{4},{3}>，

將序列<{1},{3},{4}>和<{1},{3},{5}>連接生成<{1},{3},{4},{5}>和<{1},{3},{5},{4}>因此，得到候選4-序列集CS4={<{1},{2},{3},{4}>，<{1},{2},{4},{3}>，<{1},{3},{4},{5}>，<{1},{3},{5},{4}>}根據頻繁序列的性質（定理3-5），對C4進行剪枝操作。首先將4-序列<{1},{2},{4},{3}>從C4中刪除，因為它存在一個3-序列<{2},{4},{3}>不在FS3之中，即它不會是頻繁4-序列。類似地可以將<{1},{3},{4},{5}>，<{1},{3},{5},{4}>從CS4中刪除。因此，得到最終的候選頻繁4-序列集CS4={<{1},{2},{3},{4}>}。例題13

設最小支持數為2，對于表8-16轉換映射后的序列數據庫TN挖掘出所有的序列模式。解：在序列數據庫的轉換和映射過程中已得到頻繁1-序列FS1={<{l}>，<{2}>，<{3}>，<{4}>，<{5}>}。利用頻繁1-序列集FS1生成候選頻繁2-序列集CS2={<{1},{2}>,<{2},{1}>,<{1},{3}>,<{3},{1}>,<{1},{4}>,<{4},{1}>,<{1},{5}>,<{5},{1}>,<{2},{3}>,<{3},{2}>,<{2},{4}>,<{4},{2}>,<{2},{5}>,<{5},{2}>,<{3},{4}>,<{4},{3}>,<{3},{5}>,<{5},{3}>,<{4},{5}>,<{5},{4}>}。

共有20個候選頻繁2-序列。

掃描序列數據庫TN并對候選頻繁2-序列計算支持數，如<{1},{2}>的支持數為2，<{2},{1}>的支持數為0，<{1},{5}>支持數為3等，取支持數不低于2的序列組成頻繁2-序列集FS2={<{1},{2}>，<{1},{3}>，<{1},{4}>，<{1},{5}>，<{2},{3}>，<{2},{4}>，<{2},{5}>，<{3},{4}>，<{3},{5}>，<{4},{5}>}

對頻繁2-序列集FS2進行自身連接并剪枝后得到候選3-序列集CS3={<{1},{2},{3}>，<{1},{2},{4}>，<{1},{2},{5}>，<{1},{3},{4}>，<{1},{3},{5}>，<{1},{4},{5}>，<{2},{3},{4}>，<{2},{3},{5}>，<{2},{4},{5}>，<{3},{4},{5}>}

說明：頻繁2-序列連接生成20個候選頻繁3-序列，其中10個候選頻繁3-序列被剪枝，如<{1},{3},{2}>被剪枝是因其子序列<{3},{2}>不是頻繁2-序列。

對候選頻繁3-序列集CS3中每個序列計算支持數，保留支持數不小于2的序列形成頻繁3-序列集FS3={<{1},{2},{5}>，<{1},{3},{5}>，<{1},{4},{5}>}。

由于FS3不能再產生候選頻繁4-序列，故最后得到頻繁序列模式集FS=FS2FS3={<{1},{2}>，<{1},{3}>