E4關(guān)聯(lián)規(guī)則挖掘Apriori算法的研究

1、基于關(guān)聯(lián)規(guī)則挖掘Apriori算法的研究及改進呂 建 06379031（2006級 信息與計算科學(xué)（雙專業(yè)）摘 要 關(guān)聯(lián)規(guī)則挖掘能夠發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有意義的關(guān)聯(lián)或相關(guān)聯(lián)系，是數(shù)據(jù)挖掘研究的一項重要內(nèi)容。在分析研究關(guān)聯(lián)規(guī)則挖掘技術(shù)及其相關(guān)算法Apriori算法基礎(chǔ)上，針對該算法存在的兩個缺陷，即多次掃描事務(wù)數(shù)據(jù)庫和產(chǎn)生大量的候選數(shù)據(jù)集，分別從減少搜索事務(wù)個數(shù)、劃分、抽樣和散列的方法，舉出了幾種改進的Apriori算法。改進后的算法都在某一程度上減少了運行開銷，提高了挖掘速度，從而獲得更好的性能。關(guān)鍵詞 數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；Apriori算法；頻繁項集 Improved Algorithm

2、Based On Apriori Mining Association Rules AlgorithmLvjian 06379031（2006 Information and Computing Sciences（Double Majors）Abstract Abundant meaningful relations and relevance among the different itemsets can be located by means of the association rules mining which is a significant topic in the data

3、mining field. On the base of analyzing and reseaching the technique of association rules mining and the relevant Apriori algorithm which has two defects: scanning database too much and creating excessive candidate itemsets, the thesis presents several improved Apriori algorithms with decreasing amou

4、nt of searching transaction, Partition, Sampling and Hash methods. The improved algorithms reduce runtime expenses to some extent, and accelerate data mining, then achieve better performance.Key Words data mining; association rules; Apriori algorithm; frequent itemset目 錄1 引 言32 關(guān)聯(lián)規(guī)則32.1關(guān)聯(lián)規(guī)則的基本概念32.2

5、 關(guān)聯(lián)規(guī)則屬性32.2.1 支持度（Support）32.2.2 置信度（Confidence）及平均置信度（Average Confidence）42.2.3 期望置信度（Expected Confidence）42.2.4 作用度（Lift）43Apriori算法43.1算法概述43.2 主要步驟53.3 算法描述53.4 算法實例63.4.1 產(chǎn)生頻繁項集63.4.2 由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則83.5 性能分析93.5.1 Apriori算法的時間復(fù)雜度93.5.2 Apriori算法的空間復(fù)雜度94 Apriori算法改進94.1減少搜索事務(wù)個數(shù)的方法104.1.1 AprioriTID

6、算法104.1.2 矩陣算法104.2 基于劃分（Partition）的方法134.3 基于抽樣（Sampling）的方法154.4 基于散列（Hash）的方法165總結(jié)18參考文獻:19致謝201 引 言隨著計算機的廣泛應(yīng)用和數(shù)據(jù)的大量積累，如何有效地處理海量數(shù)據(jù)并從中提取有價值的信息和人們感興趣的知識逐漸受到廣泛的關(guān)注，數(shù)據(jù)挖掘（Data Mining）技術(shù)由此應(yīng)運而生。數(shù)據(jù)挖掘1，也稱為知識發(fā)現(xiàn)，是從大量的數(shù)據(jù)中挖掘出隱含的、未知的、用戶可能感興趣的和對決策有潛在價值的知識和規(guī)則。而數(shù)據(jù)挖掘中的一個非常重要的數(shù)據(jù)處理方法是關(guān)聯(lián)規(guī)則的挖掘。關(guān)聯(lián)規(guī)則反映一個事務(wù)與其他事務(wù)之間的相互依存性和關(guān)

7、聯(lián)性，從海量記錄中挖掘有用的關(guān)聯(lián)信息，可以幫助決策者制定決策。Apriori 算法是關(guān)聯(lián)規(guī)則中的經(jīng)典算法，由Rakesh Agrawal和Rnamakrishnan Srikant在1994年提出2，其基本思想3是逐層迭代尋找頻繁項集，從長度為Lk的頻繁集迭代地產(chǎn)生長度為Lk+1的候選集，再掃描數(shù)據(jù)庫以驗證其是否為頻繁集。使用Apriori算法能夠比較有效地產(chǎn)生頻繁項集，但其代價是巨大的，特別是應(yīng)用于處理海量數(shù)據(jù)時，求候選集的規(guī)模呈指數(shù)增長3，對時間和空間都是一種挑戰(zhàn)。針對Apriori算法在實際應(yīng)用中存在的問題，人們相繼提出了一些改進的算法。本文對基于關(guān)聯(lián)規(guī)則挖掘的Apriori算法進行研究

8、，介紹幾種優(yōu)化的Apriori算法，并分析其性能。2 關(guān)聯(lián)規(guī)則2.1關(guān)聯(lián)規(guī)則的基本概念關(guān)聯(lián)規(guī)則問題首先由Agrawal等提出，是數(shù)據(jù)挖掘領(lǐng)域的一個基本、重要的問題。其源于零售商的貨籃分析，通過分析顧客購物貨籃中的不同商品、不同項之間的聯(lián)系，了解顧客的購物習(xí)慣，從而得到顧客所購商品之間的關(guān)聯(lián)。這種關(guān)聯(lián)的發(fā)現(xiàn)可以幫助零售商制定營銷策略。關(guān)聯(lián)規(guī)則定義2：設(shè)I= I1，I2，Im 是所有項的集合，其中Ik（k=1，2，m）稱為項。項的集合稱為項集，包含k個項的項集稱為k-項集。一個事務(wù)T（Transaction）是一個項集，它是I的一個子集，每個事務(wù)均與一個唯一標(biāo)識符Tid相聯(lián)系。不同的事務(wù)一起組成了

9、事務(wù)集D，它構(gòu)成了關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的事務(wù)數(shù)據(jù)庫（Transaction Database）。如果項集XT，則稱事務(wù)T支持（Support）項集X，也稱事務(wù)T包含項集X。關(guān)聯(lián)規(guī)則是如下形式的一種蘊涵X Y，其中X I，Y I，且XY=Æ。2.2 關(guān)聯(lián)規(guī)則屬性 支持度（Support）關(guān)聯(lián)規(guī)則XY 對事務(wù)集合D的支持度（Support）定義為D中包含有事務(wù)X和Y的百分比。支持度描述了X和Y這兩個項集的并集XY在所有事務(wù)中出現(xiàn)的概率。數(shù)學(xué)表達式為support（XY）=support（XY）其中“| |”表示集合中的元素個數(shù)。 置信度（Confidence）及平均置信度（Average Con

10、fidence）稱規(guī)則XY的置信度為confidence（XY），如果confidence（XY）其中support（XY）表示規(guī)則XY的支持?jǐn)?shù)，即在事務(wù)集D中包含項集合XY的所有項的數(shù)目，support（X）表示項集合X的支持?jǐn)?shù)，即support(X)=|T|TD and XT|。項集Y的平均置信度（Average Confidence）4可以通過以下公式計算得出confidence(Y) =其中n是有效實例的數(shù)目，有效實例是指具有大于特定閥值的支持度和置信度的規(guī)則的實例。 期望置信度（Expected Confidence）設(shè)事務(wù)集D中有e%的事務(wù)支持項集Y，e%稱為關(guān)聯(lián)規(guī)則XY的期望置信

11、度。期望置信度描述了在沒有任何條件影響時，項集Y在所有事務(wù)中出現(xiàn)的概率。公式表示為expectedconfidence（XY） 作用度（Lift） 作用度是置信度與期望置信度的比值。作用度描述了項集X的出現(xiàn)對項集Y的出現(xiàn)影響程度。公式表示為 lift（XY）根據(jù)概率和條件概率的計算公式，可得下表2-12：名稱描述公式支持度項集X和Y同時出現(xiàn)的概率P(XY)置信度項集Y在X出現(xiàn)下出現(xiàn)的概率P(Y | X)期望置信度項集Y出現(xiàn)的概率P(Y)作用度置信度與期望置信度的比值P(Y|X)/P(Y)表2-1 關(guān)聯(lián)規(guī)則4個參數(shù)的計算公式關(guān)聯(lián)規(guī)則的挖掘問題就是在事務(wù)數(shù)據(jù)庫 D中找出具有用戶給定的閥值最小支持度

12、minsup和最小置信度minconf的關(guān)聯(lián)規(guī)則。3 Apriori 算法3.1 算法概述Apriori算法5是一種以概率為基礎(chǔ)的具有影響的挖掘布爾型關(guān)聯(lián)規(guī)則頻繁項集的算法。項集的出現(xiàn)頻率是包含項集的事務(wù)數(shù)，稱為項集的頻率。如果項集滿足最小支持度minsup，則稱它為頻繁項集（Freqent Itemset）。頻繁k-項集的集合通常記為Lk。Apriori算法的關(guān)鍵任務(wù)是求出事務(wù)集D中的所有頻繁項集，挖掘出所有頻繁項集是該算法的核心，占整個計算量的大部分。另一任務(wù)是利用頻繁項集生成滿足最小置信度minconf的所有關(guān)聯(lián)規(guī)則。該算法過程分為兩步： 一為連接（類矩陣運算），二為剪枝（去掉那些沒必要

13、的中間結(jié)果）。Apriori算法在生成候選項集時利用了兩個性質(zhì)：一個頻繁項集的任一非空子集必定也是頻繁項集；一個非頻繁項集的任一超集必定也是非頻繁項集。3.2 主要步驟Apriori算法主要包含以下3 個步驟6：一、連接步：連接（k-l）項頻繁項集Lk-l生成k項候選集Ck?？梢赃B接的條件是兩個（k-l）項的前k-2項相等并且第l個（k-l）項集的第（k-l）項比第2個（k-l）項集的第（k-l）項小。記li是Lk-1中的項集，lij表示li的第j項。設(shè)l1、l2是可連接的，即如果（l11=l21l12=l22(l1k-2=l2k-2)(l1k-1l2k-1)，則連接l1和l2產(chǎn)生的結(jié)果項集是

14、l11l12l1k-2l1k-1l2k-1。由Lk-1中科連接的項集中連接所產(chǎn)生的k-項集的集合便是Ck。二、剪枝步：利用Apriori算法性質(zhì)對k-項候選集Ck 進行剪枝。剪枝的規(guī)則是，若其中某個k-項候選集的任一（k-l）項子集不屬于（k-l）項頻繁集Lk-1，那么該候選k項集就不可能成為一個頻繁k-項集，可以將其從Ck中刪除。三、計數(shù)步：掃描事務(wù)數(shù)據(jù)庫，累計k項候選集在事務(wù)數(shù)據(jù)庫中出現(xiàn)的次數(shù)。對于一個候選項集，若某條事務(wù)記錄包含該候選項集，則該候選項集出現(xiàn)的次數(shù)加1。最后根據(jù)給定的最小支持度生成k-項頻繁項集Lk。3.3 算法描述算法：3-1 Apriori78輸入：事務(wù)數(shù)據(jù)庫D，最小支

15、持度閾值minsup輸出：D中的頻繁項集L1) L1=find_frequent_1-itemsets(D); /發(fā)現(xiàn)1-項集2) for(k=2; Lk-1Æ k+) do3) begin4) Ck=apriori-gen(Lk-1); /根據(jù)頻繁(k-1)-項集產(chǎn)生候選k-項集5) for all transactions tÎD do /掃描數(shù)據(jù)庫，以確定每個候選項集的支持頻度6) begin7) Ct=subset(Ck, t); /獲得t所包含的候選項集8) for all candidates cÎCt do9) c.count+;10) end11)

16、 Lk=cÎCk|c.count ³ minsup;12) end13) Answer L=kLk;Procedure find_frequent_1-itemsets(D)1) begin2) for all transactions tÎD do3) begin4) for each item ikÎt do5) ik.count+;6) end7) L1=iÎI|i.count ³ minsup8) return L1;9) endProcedure Apriori-gen(Lk)1) begin2) for each item

17、set l1ÎLk do3) for each itemset l2ÎLk do4) begin5) if(l11=l21)(l12=l22)(l1k-1=l2k-1)(l1k<l2k) then6) begin7) c=l1 l2; / 連接產(chǎn)生候選項集8) if Is_include_infrenquent_subset(c,Lk) then9) delete c; /除去不可能產(chǎn)生頻繁項集的候選10) else add c to Ck+1;11) end12) end13) return Ck+1;14) endProcedure Is_include_infr

18、enquent_subset(c,Lk)1) begin2) for each k-subset s of c3) if sÏLk then4) reture TRUE;5) return FALSE;6) end3.4 算法實例下面通過舉例闡述上述算法，考慮某超市包含9個事務(wù)的數(shù)據(jù)庫D（表3-1），即 |D|=9，并假定這些事務(wù)的項按順序存放。設(shè)定最小支持度minsup=2/9=22%，即最小支持計數(shù)為2。 產(chǎn)生頻繁項集TID項列表T1I1, I2, I5T2I2, I4T3I2, I3T4I1, I2, I4T5I1, I3T6I2, I3T7I1, I3T8I1, I2, I3

19、, I5T9I1, I2, I3表3-1某超市數(shù)據(jù)庫D下圖3-1是Apriori算法尋找D中頻繁項集的過程。 C1 C1 L1項集I1I2I3I4I5項集支持計數(shù)I1I2I3I4I567622項集支持計數(shù)I1I2I3I4I567622掃描D 與最小 計算支支持計持計數(shù)數(shù)相比 C2 C2 L2 項集I1, I2I1, I3I1, I4I1, I5I2, I3I2, I4I2, I5I3, I4I3, I5I4, I5項集支持計數(shù)I1, I2I1, I3I1, I4I1, I5I2, I3I2, I4I2, I5I3, I4I3, I5I4, I54412422010項集支持計數(shù)I1, I2I1,

20、 I3I1, I5I2, I3I2, I4I2, I5442422L1連接掃描D與最小 產(chǎn)生候計算支支持計選集C2持計數(shù)數(shù)相比 C3 C3項集I1, I2, I3I1, I2, I5I1, I3, I5I2, I3, I4I2, I3, I5I2, I4, I5項集I1, I2, I3I1, I2, I5L2連接刪除存在子產(chǎn)生候集 不 屬 于選集C3 L2 的 項 集項集支持計數(shù)I1, I2, I3I1, I2, I522 C3 L3項集支持計數(shù)I1, I2, I3I1, I2, I522掃描D與最小計算支支持計持計數(shù)數(shù)相比 C4 C4 項集I1, I2, I3，I5項集Æ L3連接

21、產(chǎn)生刪除存在子集不候選集C4屬于 L2 的項集圖3-1 頻繁集產(chǎn)生過程具體過程描述如下：(1) 尋找頻繁項集1-項集 數(shù)據(jù)庫中每個數(shù)據(jù)項均為候選1-項集的集合C1中的元素，對于C1中每個項集，掃描數(shù)據(jù)庫中的事務(wù)，統(tǒng)計其支持計數(shù)。然后與最小支持計數(shù)2相比，判斷是否頻繁，從而確定頻繁1-項集的集合L1。(2) 尋找頻繁2-項集連接L1產(chǎn)生候選2-項集的項集C2，即C2=L1L1= I1, I2,I1, I3,I1, I4,I1, I5,I2, I3,I2, I4,I2, I5,I3, I4,I3, I5,I4, I5。由于C2中每個2-項集的所有1-項集子集都包含在L1中，所以不需要剪枝。對于C2

22、中每個項集，掃描數(shù)據(jù)庫中的事務(wù)，統(tǒng)計其支持計數(shù)。然后與最小支持計數(shù)2相比，判斷是否頻繁，從而確定頻繁2-項集的集合L2。(3) 尋找頻繁3-項集連接L2產(chǎn)生候選3-項集的項集C3，即C3=L2L2= I1, I2, I3, I1, I2, I5, I1, I3, I5, I2, I3, I4, I2, I3, I5, I2, I4, I5。然后對C2進行剪枝，例如項集I1, I2, I3的2-項子集的為I1, I2, I1, I3, I2, I3。由于項集I1, I2, I3的全部2-項子集都是L2的子集，所以項集I1, I2, I3保留在C3中。又如對另一項集I2, I3, I5，其2-項子

23、集的為I2, I3,I2, I5,I3,I5。但I3,I5不是L2的子集，所以項集I2, I3, I5不是頻繁項集，應(yīng)當(dāng)將其從C3中刪除。對C3中其他的項集采用同樣方法進行剪枝，最后得C3=I1, I2, I3, I1, I2, I5。對于C3中每個項集，掃描數(shù)據(jù)庫中的事務(wù)，統(tǒng)計其支持計數(shù)。然后與最小支持計數(shù)2相比，判斷是否頻繁，從而確定頻繁3-項集的集合L3。(4) 尋找頻繁4-項集 連接L3產(chǎn)生候選4-項集的項集C4，C4= I1, I2, I3, I5，其子項集I2, I3, I5不屬于L3，因此將項集I1, I2, I3, I5從C4中刪除，此時C4=Æ，算法結(jié)束。 由頻繁項

24、集產(chǎn)生關(guān)聯(lián)規(guī)則找出頻繁項集后，就可按以下方法提取關(guān)聯(lián)規(guī)則：(1) 對于每個頻繁項集Li，求出其全部非空子集。(2) 對于頻繁項集Li的每個非空子集S，計算規(guī)則“S(Li-S)”的置信度，即confidence（S(Li-S)）如果confidence（S(Li-S)）³ minconf則此產(chǎn)生關(guān)聯(lián)規(guī)則S(Li-S)。由上例，得到數(shù)據(jù)庫D的頻繁項集L= I1,I2,I3,I4,I5,I1,I2,I1,I3,I1,I5, I2,I3,I2,I4,I2,I5,I1,I2,I3,I1,I2,I5。例如設(shè)定最小置信度minconf=70%，則對于集合I1,I2,I5，其非空子集為I1,I2,

25、I1,I5, I2,I5, I1, I2, I5。計算得confidence(I1 ÙI2I5) = scI1,I2,I5/scI1,I2=2/4 = 50%confidence(I1 ÙI5I2) = scI1,I2,I5/scI1,I5 = 2/2 = 100%confidence(I2 ÙI5I1) = scI1,I2,I5/scI2,I5 = 2/2 = 100%confidence(I1I2 ÙI5) = scI1,I2,I5/scI1 = 2/6 = 33%confidence(I2I1 ÙI5) = scI1,I2,I5/scI2

26、 = 2/7 = 29%confidence(I5I1 ÙI2) = scI1,I2,I5/scI5 = 2/2 = 100%與最小置信度70%相比，則得關(guān)聯(lián)規(guī)則I1 ÙI5I2、I2 ÙI5I1和I5I1 ÙI2。3.5 性能分析由上述實例可見，Apriori算法每次掃描都要徹底掃描整個原始數(shù)據(jù)庫D，這要耗費大量的時間；而且進行連接操作而生成完整的候選項集后才進行置信度的計算，將消耗大量的存儲空間。 Apriori算法的時間復(fù)雜度雖然Ap riori算法自身已經(jīng)做了一定的優(yōu)化，但仍然存在算法效率不高的問題。Ap riori算法主要的時間消耗是在以下四個

27、方面910：(1) 利用k-頻繁項集連接產(chǎn)生k+1候選項目集，判斷連接條件時比較次數(shù)太多。假設(shè)項集個數(shù)為m的頻繁項集集合Lk，判斷連接條件時比較的時間復(fù)雜度是O ( k*m2 )，并且其中m的值會很大。因為，假設(shè)1-項集合中項集個數(shù)為102 ，那將會產(chǎn)生5000個候選2-項集。最壞情況下即假設(shè)發(fā)現(xiàn)了一個長度為100的頻繁項集，則將產(chǎn)生約1030 個候選項集。(2) 對任意一個c Ck判斷c的k個( k-1) -子集是否都在Lk - 1中。在這個過程中，對于c在最好情況下只需掃描一次Lk 1，即第一個(k-1)-子集不在Lk - 1 中。在最壞情況下則需要一直掃描到第k次時才發(fā)現(xiàn)第k個(k 1)

28、 -子集不在Lk - 1 中或k個( k - 1) -子集都在Lk - 1中。于是，在平均情況下，對任意一個c Ck掃描Lk - 1次數(shù)為| Lk - 1|×k /2；那么對所有候選k-項集需要掃描次數(shù)為 | Ck |×| Lk - 1 | ×k /2。(4) Apriori算法的時間復(fù)雜度為O(|C|×|D|)，|C|為潛在頻繁項集的長度之和，|D|為事情務(wù)數(shù)據(jù)庫規(guī)模。用Hi 來表示第i次生成頻繁項的長度，則|C|Hi。(3) 為了得到所有Ck ( k = 1, 2, , n) 候選頻繁項集的支持度，需要掃描數(shù)據(jù)庫n次。 Apriori算法的空間復(fù)雜度

29、 在空間耗費上，設(shè)頻繁項的最大長度為項的總數(shù)量m，若不對min_up限制，Apriori算法的空間復(fù)雜度為：S(m)=2m-1。項集連接方法產(chǎn)生的潛在頻繁項集，往往隨著商品種類增長而成指數(shù)增長，當(dāng)數(shù)據(jù)事務(wù)大規(guī)模增加時，這種情況更加明顯。一個超市中，其產(chǎn)品達上千種，其空間需求在最壞情況下可達21000-1。4 Apriori算法改進鑒于Apriori算法存在上述問題，許多改進的算法已經(jīng)被提出來，這些算法主要為以下幾類：減少搜索事務(wù)個數(shù)的方法、基于劃分（Partition）的方法、基于散列（Hash）的方法和基于采樣（Sampling）的方法。這些方法都在一定程度（減少掃描數(shù)據(jù)庫次數(shù)、降低項集比較

30、次數(shù)、減少空間消耗等）上優(yōu)化了Apriori算法，但任何算法無論如何改進，總會存在優(yōu)點和缺點，只是不同的改進算法適用于某些領(lǐng)域相對會有更好的性能。4.1減少搜索事務(wù)個數(shù)的方法 該思想也是由Agrawal等人提出的，通過減少用于未來掃描的事務(wù)集的大小來改進Apriori算法?，F(xiàn)已有多種基于該方法的算法，如AprioriTID算法、矩陣算法。 AprioriTID算法AprioriTID算法是在Apriori算法基礎(chǔ)上改進的關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法。該算法的特點是在第一次對事務(wù)數(shù)據(jù)庫D掃描時計算候選項集的支持度，其他各次用其上一次掃描生成的候選事務(wù)數(shù)據(jù)庫Tk來計算候選頻繁項集的支持度。Tk中每個成員

31、的形式為<TID，Xk>，其中每個Xk是一個事務(wù)中潛在的k-項集。在標(biāo)示符為TID的事務(wù)中，對于k=1，Tk對應(yīng)于事務(wù)數(shù)據(jù)庫D。對于k>1，Tk由算法產(chǎn)生與事務(wù)t相對應(yīng)的Tk成員是<t.TID，TÎCk|t中包含的T>。如果一個事務(wù)不包含任何候選k-項集，那么Tk中就不會有該事務(wù)的項集。因此，當(dāng)k的值很大時，Tk中項的數(shù)目將比事務(wù)數(shù)據(jù)庫D中的事務(wù)數(shù)少很多。AprioriTID算法描述如下11：算法：4-1 AprioriTID輸入：事務(wù)數(shù)據(jù)庫D，最小支持度閾值minsup輸出：D中的頻繁項集L1) C1=candidate1-itemsets;2) L1

32、=cÎC1|c.count ³ minsup;3) T1=事務(wù)數(shù)據(jù)庫D;4) for(k=2;Lk-1¹Æk+) do bigin5) Ck=Apriori-gen(Lk-1);6) Tk=Æ7) 根據(jù)Tk-1和Ck生成Tk；8) 由Tk計算Ck中各項集的支持?jǐn)?shù);9) Lk=cÎCk|c.count ³ minsup; /生成頻繁k-項集Lk10) end11) L=kLk; 矩陣算法矩陣算法15（Matrix algorithm）通過一次掃描數(shù)據(jù)庫，得到一個由0和1組成的矩陣。采用矩陣形式，只掃描了一次數(shù)據(jù)庫，減少了I/O

33、 操作，并且突破常規(guī)的采用先假設(shè)頻繁項集項目數(shù)的辦法，從高階項集著手尋找頻繁項集，最大限度的減少了候選數(shù)據(jù)集的個數(shù)，大大提高了算法的效率。令項集I=i1，i2，in，集合D=t1，t2，tm，則矩陣G的元素gij定義如下：其中i=1，2，m；j=1，2，n。下面用表3-1的數(shù)據(jù)說明矩陣的生成過程。設(shè)I=I1，I2，I3，I4，I5，事務(wù)數(shù)據(jù)庫為t1= I1, I2, I5，t2= I2, I4，t3= I2, I3，t4= I1, I2, I4，t5= I1, I3，t6= I2, I3，t7= I1, I3，t8= I1, I2, I3, I5，t9= I1, I2, I3。則生成的矩陣如圖

34、4-1圖4-1 矩陣G算法思想如下3：對關(guān)聯(lián)矩陣G的每一行進行求和，計算出所有事務(wù)項目數(shù)；選取大于等于最小支持度的項目數(shù)為測試頻繁項集項目數(shù)；合并所有項目數(shù)為測試頻繁項集項目數(shù)的項目集；計算其支持?jǐn)?shù)，刪除小于最小支持度的項目集，剩余的為我們尋找的頻繁項目集；若剩余數(shù)為0，則測試頻繁項集項目數(shù)-1，繼續(xù)，直至找到頻繁項目集。算法描述如下：輸入：事務(wù)數(shù)據(jù)庫D，最小支持度閾值minsup輸出：D中的頻繁項集L1）Cn=0; /Cn，n為最大項目數(shù)2）for each tiÎT do3）i=|ti|； /i 為每個事務(wù)所含的項目數(shù)4）Ci=Ci+15）for i=n to 16）If (Ci

35、 ³ minsup) then7）k=I; /假定k = i為最大頻繁項目集項目數(shù)8 ) break;9） for i=k to 1 do10）Ck=select k-itemsets /挑選出含有k個事務(wù)數(shù)的候選數(shù)據(jù)集11）for each Ci Í Ck do12）Lk = Ci| count(Ci) ³ minsup ;13）If (Lk ¹ Æ) return Lk;算法實例：表4-1為事務(wù)數(shù)據(jù)庫D，其最小事務(wù)支持?jǐn)?shù)mincount=2，即minsup = 2 /8 = 25%。TID項列表T1I1, I2, I3, I4T2I2, I

36、3T3I1, I3, I5T4I3, I4T5I1, I2T6I1, I3T7I2, I3, I4T8I2表4-1事務(wù)數(shù)據(jù)庫D根據(jù)矩陣算法求頻繁項集過程如下： G C1 L1項集支持計數(shù)I1I2I3I4I545631項集支持計數(shù)TIDI1I2I3I44563T1,T3,T5,T6T1,T2,T5,T7,T8T1,T2,T3,T4,T6,T7T1,T4,T7 G1 C2 L2項集支持計數(shù)I1,I2I1,I3I1.I4I2,I3I2,I4I3,I4231323項集支持計數(shù)TIDI1,I2I1,I3I2,I3I2,I4I3,I423323T1,T5T1,T3,T6T1,T2,T7T1,T7T1,T4

37、,T7G2 C3 L3 項集支持計數(shù)I1,I2,I3I2,I3,I412項集支持計數(shù)TIDI2,I3,I42T1,T7從上述過程可以看出，矩陣在不斷地壓縮，從G到G1 刪除了第8列，也就是將事務(wù)8刪除了；從G1到G2 刪除了第2，3，4，5，6列，也就是將事務(wù)2，3，4，5，6刪除了。這樣每一次都盡可能地刪除對生成下一層候選項集不起作用的事務(wù)。在這個實例中，如果用Apriori算法就要完整地掃描3次事務(wù)數(shù)據(jù)庫，而改進后的算法只要在最初構(gòu)造矩陣時掃描一次事務(wù)數(shù)據(jù)庫就夠了，以后只需要通過掃描矩陣就可以得到頻繁項集；而且矩陣是不斷變小的，這樣可以大大提高算法的效率。4.2 基于劃分（Partitio

38、n）的方法Partition挖掘算法14采用“分而治之”的方法，將事務(wù)數(shù)據(jù)庫分為N個互不相交且能一次性裝入內(nèi)存的數(shù)據(jù)塊。每次處理一個數(shù)據(jù)塊，利用Apriori算法得到局部頻繁項集。然后將各數(shù)據(jù)塊局部頻繁項集合并，生成候選項集，掃描整個事務(wù)數(shù)據(jù)庫，計算這些項集的支持度，最終得到全局大項集。就整個數(shù)據(jù)庫D而言，一個局部頻繁項集不一定就是全局頻繁項集；但是任何全局頻繁項集一定會出現(xiàn)從所有劃分所獲得的這些局部頻繁項集中。這一點很容易反證獲得。因此可以將從N個劃分中所挖掘出的局部頻繁項集作為整個數(shù)據(jù)庫D中頻繁項集的候選項集；而在第二階段中再次掃描整個數(shù)據(jù)庫以獲得所有候選項集的支持頻度，以便最終確定全局頻

39、繁的項集。各劃分大小和數(shù)目可以以每個劃分大小能夠整個放入內(nèi)存為準(zhǔn)，因此每個階段只需讀入一次數(shù)據(jù)庫內(nèi)容，而整個挖掘就需要兩次掃描整個數(shù)據(jù)庫。由于局部頻繁項集的生成在內(nèi)存中進行，這樣就大大提高了算法的運行效率。Partition算法描述：定義一個劃分PÍD為事務(wù)數(shù)據(jù)庫D任意一個子集，并且任何兩個劃分都不相交，即PiPj=Æ，i¹j。為劃分P的局部候選k-項集的集合，為劃分P的局部頻繁k-項集的集合，Lp為劃分P的全部局部頻繁項集的集合，為全局k-項集的集合，CG為全部全局候選項集的集合，為全局頻繁k-項集的集合。算法：Partition算法輸入：項集I，事務(wù)數(shù)據(jù)庫D，

40、最小支持度閾值minsup輸出：頻繁項集L1) P = partition-database(D);2) n = Number of partitions;3) for i = 1 to n begin / Phase I4) read_in_partition(PiÎP);5) Li= gen_frequency_itemsets(Pi);6) end7) for (i = 2; ¹Æ, j = 1, 2, . . , n; i+) do8) =j=1,2,n ; / Merge Phase10) for i = 1 to n begin / Phase II1

41、1) readin_partition(PiÎP);12) for all candidates cÎCG gen_count(c, Pi);13) end14) LG = cÎCG|c.count ³ minsup;Procedure gen_frequency_itemsets(P: database partition)1) = frequency l-itemsets along with their tidlists;2) for ( k = 2; ¹Æ k+) do begin3) forall itemsets L1&#

42、206; do begin4) forall itemsets L2Î do begin5) if L11 = L21 ÙL12 = L22 ÙÙ L1k-2=L2k-2 ÙL1k-1<L2k-1 then6) c = L1l L12 L1 k-1 L2k-1;7) if c cannot be pruned then8) c.tidlist =L1.tidlistL2.tidlist;9) if |c.tidlist| / |P| ³ minsup then10) = c;11) end12) end13) end14) re

43、turn k算法實例：事務(wù)數(shù)據(jù)庫D，最小支持度minsup=50%，根據(jù)Partition算法，求頻繁項集過程如下：首先，將事務(wù)數(shù)據(jù)庫D劃分為兩個分區(qū)：D1=T1,T2,T3,D2=T4,T5。事務(wù)數(shù)據(jù)庫D D1 D2 TID項集T1T2T3T4T5I1,I3,I4I2,I3,I5I1,I2,I3,I5I2,I5I2,I3TID項集T1T2T3I1,I3,I4I2,I3,I5I1,I2,I3,I5TID項集T4T5I2,I5I2,I3劃分為兩個區(qū)其次，計算D1的頻繁項集，得到D1的局部頻繁項集=I1,I2,I3,I5,I2,I3,I2,I5,I3,I5,I1,I3,I2,I3,I5。L1 L2

44、 L3 項集支持計數(shù)I1I2I3I52232項集支持計數(shù)I2,I3I2,I5I3,I5I1,I32222項集支持計數(shù)I2,I3,I52然后，計算D2的頻繁項集，得到局部頻繁項集=I2,I3,I5,I2,I3,I2,I5。L1 L2 項集支持計數(shù)I2I3I5211項集支持計數(shù)I2,I3I2,I511最后，合并頻繁項集，得到全局頻繁項集=I2,I3,I5,I2,I3,I2,I5。L1 L2 項集支持計數(shù)I2I3I5443項集支持計數(shù)I2,I3I2,I533第二次掃描數(shù)據(jù)庫，最小支持?jǐn)?shù)mincount=5×50%=2.5，從而得全局頻繁項集=I2,I3,I5,I2,I3,I2,I5。通過分

45、區(qū)有效的提高了算法的挖掘效率。4.3 基于抽樣（Sampling）的方法Mannila等人首先認(rèn)為采樣是發(fā)現(xiàn)規(guī)則的一個有效途徑，而Toivonen進一步發(fā)展了這個思想：選取給定數(shù)據(jù)庫D的隨機樣本S，在S中搜索頻繁集，得到在S中成立的關(guān)聯(lián)規(guī)則，這些規(guī)則也可能在整個數(shù)據(jù)庫中成立，然后用數(shù)據(jù)庫的剩余部分驗證這個結(jié)果12。由于搜索空間的減小，可能會丟失一些全局頻繁項，為減少這種可能性，對樣本挖掘時可以使用較低的支持度閥值。使用抽樣方法，是以犧牲一些精度來獲得有效性的。目前有許多應(yīng)用抽樣方法的關(guān)聯(lián)規(guī)則挖掘算法，如D-Sampling算法，F(xiàn)AST算法和SMDM算法。文獻13給出了下面一種抽樣算法：算法：

46、 Sampling algorithm輸入： 項集I，事務(wù)數(shù)據(jù)庫D，最小支持度閾值minsup輸出： 頻繁項集L1) begin2) Ds=Sample drawn from D;3) PL=Apriori(I, Ds, smalls); /smalls可以是小于minnsup的任意值4) C=Æ5) for each IiÎC do6) Ci=0; /每個項集初始計數(shù)為07) for each tjÎD do /第一次掃描計數(shù)8) for each IiÎtj，then9) Ci=Ci+1;10) for each IiÎC do11) if

47、 Ci ³ (minsup´|D|) do12) L=LIi;13) ML=x|xÎBD-(PL)xÎL; /舍去頻繁項集14) if(ML¹Æ) then15) C=L; /設(shè)置候選集為大項集16) repeat17) C=CBD-(C); /使用負邊界擴展候選集18) until no new itemsets are added to C;19) for each IiÎC do20) Ci=0; /每個項集初始計數(shù)為021) for each tjÎD do /第二次掃描計數(shù)22) for each Ii&

48、#206;C do23) if(IiÎtj) then24) Ci=Ci+1;25) if Ci ³ (s´|D|) do26) L=LIi;4.4 基于散列（Hash）的方法 Park等人16于1995年提出了一種基于散列（Hash）計術(shù)產(chǎn)生頻繁項集的算法。這種方法把待掃描的項集放到不同的Hash桶中，每個項集最多只可能放在一個特定的桶中，這樣可以對每個桶中的項集進行測試，減少了候選項集生成的代價。利用Hash表技術(shù)可以幫助有效減少候選k-項集Ck(k>1)所占用的空間。例如：在掃描事務(wù)數(shù)據(jù)庫D以便從候選項集中產(chǎn)生頻1-項集時，就可以為每個事務(wù)記錄產(chǎn)生所有

49、的2-項集并將它們散列到相應(yīng)的桶中，且增加相應(yīng)桶的計數(shù)。對于表3-1的事務(wù)數(shù)據(jù)庫D，設(shè)定哈希函數(shù)h(x,y)=(order of x)´10+(order of y) mod 7，例如h(I2,I3)=(2´10+3)mod 7=2。如表4-117，Hash表中一個存放2-項集的桶計數(shù)若低于最小支持頻度（設(shè)minsup=0.3，最小支持計數(shù)為3），則0桶、1桶、3桶、4桶中項集總個數(shù)小于3，不能成為頻繁項集，2桶、5桶、6桶成為候選頻繁2-項集，即C2= I2, I3，I1, I2，I1, I3。利用這樣Hash表技術(shù)可以有效減少需要檢查的候選k-項集數(shù)目，尤其是當(dāng)k=2時

50、。桶地址0123456桶計數(shù)2242244桶內(nèi)容I1, I4I3, I5I1, I5I1, I5I2, I3I2, I3I2, I3I2, I3I2, I4I2, I4I2, I5I2, I5I1, I2I1, I2I1, I2I1, I2I1, I3I1, I3I1, I3I1, I3表4-1利用Hash表H2創(chuàng)建2-項集C2基于Hash方法的DHP算法描述如下：算法：DHP算法輸入：事務(wù)數(shù)據(jù)庫D，最小支持度閾值minsup輸出：D中的頻繁項集L/ Part 11) s=minsup;2) set all the buckets of H2 to zero; /Hash table3) forall transaction tÎD do begin4) insert and count 1-items occurrences in a hash tree;5) forall 2-subsets s of t do6) H2h2(x)+;7) end8) L1=c|c.count ³ s, c exists in th