基于排序樹的Node-Apriori改進(jìn)算法

畢玉萍，胡世昌，李勁華

(青島大學(xué)數(shù)據(jù)科學(xué)與軟件工程學(xué)院，青島266071)

隨著互聯(lián)網(wǎng)的運(yùn)用和普及，信息的產(chǎn)生和傳播日益迅速與便捷，數(shù)據(jù)信息在爆炸式地增長。信息存儲單位從之前以G 為單位，到現(xiàn)在以PB甚至EB為單位。網(wǎng)上瀏覽的信息，各種社交App中發(fā)表的語言動態(tài)，各種購物平臺購買的商品以及其他網(wǎng)上行為，都會被視為數(shù)據(jù)信息加以記錄和儲存?；ヂ?lián)網(wǎng)數(shù)據(jù)信息的增長，讓許多行業(yè)看到了機(jī)遇，在這些數(shù)據(jù)信息中篩選有效的用戶信息，給予精準(zhǔn)的推薦與利用，是可以產(chǎn)生巨大的商業(yè)利益的[1]。但隨著數(shù)據(jù)的不斷增加和累積，無效信息也會越來越多，信息過量的問題也隨之產(chǎn)生，這對許多行業(yè)提出了挑戰(zhàn)。面對海量的數(shù)據(jù)信息，如何在海量含有噪聲的信息中篩選出隱藏的有效信息成為一個急需攻克的難題[2]。從大量信息中挖掘有效信息的技術(shù)越來越重要，數(shù)據(jù)挖掘技術(shù)和算法應(yīng)運(yùn)而生[3]。數(shù)據(jù)挖掘是指從大數(shù)據(jù)中通過算法提取隱藏信息的過程，在1989年的人工智能專題研討會上首次提出[4]。關(guān)聯(lián)規(guī)則挖掘是其中的一個重要研究方向，有著廣泛的應(yīng)用。例如分析之前招生的學(xué)生成績以及地域從而找到合適的關(guān)聯(lián)規(guī)則進(jìn)行更為有效的招生[5]，或者根據(jù)調(diào)查問卷挖掘有效的關(guān)聯(lián)規(guī)則為奧賽選拔學(xué)生提供了有效信息[6]，利用藥房和藥店等醫(yī)療保健系統(tǒng)產(chǎn)生大量的交易數(shù)據(jù)挖掘藥房處方藥物規(guī)則[7]，挖掘事物營養(yǎng)成分之間的關(guān)聯(lián)規(guī)則從而提高人類營養(yǎng)的吸收[8]，利用關(guān)聯(lián)規(guī)則分析海事事故[9]等。針對關(guān)聯(lián)分析領(lǐng)域傳統(tǒng)的Apriori算法效率低的問題，文獻(xiàn)[10]提出了BE-Apriori(Binay Encoded Apriori)算法，其利用二進(jìn)制數(shù)在內(nèi)存及運(yùn)算速度上的優(yōu)勢，對事務(wù)記錄進(jìn)行二進(jìn)制編碼后加載到內(nèi)存，然后利用等效的二進(jìn)制數(shù)之間運(yùn)算代替集合之間的運(yùn)算，改進(jìn)了Apriori算法的效率。文獻(xiàn)[11]提出了Tree-Apriori(Tree based Apriori)算法，指出Apriori算法同級節(jié)點中每個節(jié)點包含的事務(wù)記錄是可能重復(fù)的，利用FP-Tree(Frequent Pattern-growth)的方式組織事務(wù)記錄，每個節(jié)點都代表一棵子樹，通過對樹中節(jié)點進(jìn)行合并和更新的操作完成頻繁項集的挖掘。本文在文獻(xiàn)[10]和文獻(xiàn)[11]的基礎(chǔ)上進(jìn)行了改進(jìn)，通過二進(jìn)制編碼的方式，提出了一種改進(jìn)的Node-Apriori算法。

1 Apriori算法

1.1 基本概念

Apriori算法[12]有兩種方式統(tǒng)計候選項集的支持度:對于每個候選項集遍歷事務(wù)記錄統(tǒng)計；對于每個事務(wù)記錄統(tǒng)計對該事務(wù)記錄包含的候選項集的支持事務(wù)數(shù)加1[13]。假如匹配到trie樹中的某個節(jié)點，該節(jié)點有n 個孩子節(jié)點，還需要匹配的事務(wù)記錄為t′，下一步需要做的就是如何在這n 個孩子節(jié)點中找到和t′匹配的項。通常有三種方式[14]:

1)孩子節(jié)點和事務(wù)記錄同時遍歷。利用兩個指針，第一個指針指向事務(wù)記錄t′的第一項，第二個指針指向第一個孩子節(jié)點。比較兩者按照頻繁1-項集頻次中的順序，小者進(jìn)行移動，如果指向事務(wù)記錄的第x項則指針指向第(x＋1)項，如果指向第k 個孩子節(jié)點，則指針指向第(k＋1)個孩子節(jié)點。如果兩者相同，則同時移動。這些操作的時間復(fù)雜度為O(n ＋|t′|)；

2)二分搜索。有兩種基本的方式，或者兩者的結(jié)合。對于事務(wù)記錄t＇，找到對應(yīng)的孩子節(jié)點，由于事務(wù)記錄中的項是排序過的，所以可以使用二分搜索搜索在孩子節(jié)點中搜索t′中第一項所在的孩子節(jié)點；或者對于的孩子節(jié)點，使用二分法搜索該孩子節(jié)點在t′的位置。兩者的時間復(fù)雜度分別為O(|t′|log n)和O(n log|t′|)，可以兩者相結(jié)合的使用，選擇其中較小的一個作為二分搜索的維度；

3)使用數(shù)組的方式。數(shù)組的長度為頻繁1-項集的個數(shù)，每個位置代表頻繁1項集中的一個項，如果存在則為1，不存在則為0?？梢源_定每個孩子節(jié)點在數(shù)組中對應(yīng)的項，如果該項存在，則可以進(jìn)行下一步的搜索。利用孩子節(jié)點在頻繁1-項集按頻次排序后的索引，可以立刻計算出在事務(wù)記錄的中位置。時間復(fù)雜度為O(n)。

1.2 算法描述

Apriori算法中挖掘頻繁項集的步驟如下:掃描數(shù)據(jù)庫，獲取所有項的支持度，獲取頻繁1-項集。

1)連接:若兩個頻繁k-項集A 和B 其中有(k-1)項相同，則這兩個頻繁k-項集可以連接產(chǎn)生候選(k＋1)-項集；

2)剪枝:根據(jù)Apriori算法的性質(zhì)非頻繁項集的超集也是非頻繁項集，可以對產(chǎn)生的候選項集進(jìn)行剪枝[15]。若對一個項集的所有子集都進(jìn)行是否是頻繁項集的判斷，由于一個k-項集的所有子集數(shù)量為2k，則這個過程的時間復(fù)雜度為O(2k)，顯然是不符合實際的。由于一個頻繁項集的子集都是頻繁項集，所以假如一個候選(k＋1)-項集的k 個k-項子集，都是頻繁項集，那么此候選(k＋1)-項集的非空子集就都是頻繁項集，即該(k＋1)-項集就不會是非頻繁項集的超集，通過性質(zhì)1剪枝，復(fù)雜度由O(2k)減少到了O(k)。剪枝的依據(jù)可以是若(k＋1)個候選頻繁(k＋1)-項集的每個k-項子集是否都是頻繁k-項集來判斷，即有一個或者多個k-項子集不是頻繁k-項集，那么該候選(k＋1)-項集不可能為頻繁(k＋1)-項集[16]。通過這種方式可以有效剔除一定不是頻繁項集的候選項集；

3)通過遍歷數(shù)據(jù)庫，對候選頻繁(k＋1)-項集的支持度進(jìn)行統(tǒng)計，若低于最小支持度，則濾除；

4)循環(huán)執(zhí)行2)～4)步，直到不能通過連接產(chǎn)生候選頻繁項集為止。

1.3 Apriori算法的缺陷

Apriori算法的缺點主要如下[17](通過頻繁k-項集產(chǎn)生頻繁(k＋1)-項集來舉例):

1)連接的步驟計算效率低下。要判斷任意兩個頻繁k-項集是否有(k-1)項相同；

2)每個候選(k＋1)-項集是否是頻繁k-項集還需要遍歷(k＋1)次數(shù)據(jù)庫，但是I/O 存取的消耗相對于內(nèi)存存取要高幾個數(shù)量級[18]；

3)在掃描數(shù)據(jù)庫時需要對候選項集和事務(wù)進(jìn)行模式匹配，這個過程需要消耗大量的時間[19]。

1.4 FIMIST算法

FIMST 算法[20]采用了前綴樹的方式組織項集，兄弟節(jié)點具有相同的前綴，這樣FIMST 算法在連接的過程中只需要連接兄弟節(jié)點即可。并且采用了末項剪枝的概念，若兩個兄弟節(jié)點不是頻繁項集，那么兩個兄弟節(jié)點連接成的候選項集必定不是頻繁項集，來進(jìn)行剪枝。然后遍歷事務(wù)記錄，統(tǒng)計同一級候選項集節(jié)點的支持事務(wù)數(shù)，對于一條事務(wù)記錄，如果不包含前綴樹的一個節(jié)點，那么這個事務(wù)記錄必定不包含此節(jié)點樹中所有節(jié)點代表的候選項集，以此來提高通知候選項集支持度的效率。利用頻繁k-項集對事務(wù)記錄做了一次篩選，避免了每條事務(wù)記錄都需要掃描所有候選項集來統(tǒng)計支持度。該算法在連接、剪枝以及統(tǒng)計候選項集支持度的過程中都提高了算法的執(zhí)行效率。

2 Node-Apriori算法

2.1 基本概念

節(jié)點按照一個規(guī)則排序后，候選項集的產(chǎn)生是有跡可循的。例如統(tǒng)計所有的事務(wù)記錄之后頻繁-1 項集排序結(jié)果為a、b、c、d，那么排序后的所有事務(wù)記錄不可能包含順序為c、b 子序列的事務(wù)記錄，而排序后的事務(wù)記錄中不可能包含子序列c、b。如果一個事務(wù)記錄包含的I為{a，b，c，d}，那么可能產(chǎn)生的候選項集如圖1表示。

首先按照規(guī)則排序的頻繁1-項集，然后對于每個節(jié)點只能與節(jié)點在排序中的位置之后的元素才可能生成候選項集，這些節(jié)點組成的樹稱為排序樹，樹中節(jié)點的深度代表的時候頻繁項集或者候選項集的長度，每個節(jié)點都代表一個頻繁項集或者候選項集。

這樣不需要像Apriori算法那樣進(jìn)行連接產(chǎn)生候選項集。Apriori算法連接的時間復(fù)雜度為O(n2)，n 為頻繁k-項集的個數(shù)。而通過這種方式組織節(jié)點之后，由于每個節(jié)點子節(jié)點的前綴都是相同的，所以連接的過程僅需要對有大于1個孩子節(jié)點的節(jié)點進(jìn)行連接，其時間復(fù)雜度為O(k2)，k 為該節(jié)點含有子節(jié)點的個數(shù)。與原方法相比，并不需要對每兩個頻繁－k 項集的前(k－1)項相同進(jìn)行判斷，僅需要對子節(jié)點之間順序連接即可，大大提高了算法連接過程的效率。

事務(wù)記錄的存儲是可以嵌入到節(jié)點中。每個頻繁項集節(jié)點包含的事務(wù)記錄都是包含此項集的事務(wù)記錄。在統(tǒng)計候選項集支持度的時候，無需遍歷所有事務(wù)記錄，對于頻繁項集包含的事務(wù)記錄可以采用方式2對該節(jié)點的子節(jié)點統(tǒng)計支持度。因為父節(jié)點表示項集的是子節(jié)點表示的項集的子集，而包含子節(jié)點的事務(wù)記錄，必定包含父節(jié)點表示的項集，父節(jié)點的事務(wù)記錄是全部事務(wù)記錄的子集，減少了統(tǒng)計候選項集需要遍歷的事務(wù)記錄的數(shù)量。由于Apriori算法中統(tǒng)計候選項集支持度是最消耗時間的步驟[21]，所以增加的屬性事務(wù)記錄可以極大的提高算法挖掘頻繁項集的效率。

由于事務(wù)記錄繁多時，不可能全部加載進(jìn)入內(nèi)存，即不可能直接給每個節(jié)點添加未加處理的事務(wù)記錄。通過二進(jìn)制編碼的方式可以有效的減少事務(wù)記錄內(nèi)存的占用[21]，使用二進(jìn)制之間的運(yùn)算還可以替換集合之間的運(yùn)算。這樣就可以有效解決事務(wù)記錄占用內(nèi)存較大的問題，并有效的提高算法的執(zhí)行效率。

二進(jìn)制編碼:若頻繁1-項集的個數(shù)為n，則可以把所有項集編碼為長度小于或等于n 位的二進(jìn)制數(shù)。長度為n 的二進(jìn)制數(shù)中的每個位置分別代表每個項。若某項在此項集中存在，則在該位置為1；若該項在此項集中不存在，則該位置為0。編碼后的二進(jìn)制數(shù)可能小于n，這是由于二進(jìn)制數(shù)前面部分位置代表的項均不存在。據(jù)此可以對所有事務(wù)，頻繁項集和候選項集進(jìn)行編碼。然后，通過長度小于或等于n 的二進(jìn)制數(shù)代表頻繁項集和候選項集以及事務(wù)記錄。

性質(zhì)1編碼后的項集a 和項集b。a&b 的結(jié)果為項集a 和項集b 共同含有的項集；例如若頻繁1-項集為{A，B，C}，項集a－{A，B}二進(jìn)制編碼的結(jié)果為110，項集b－{A，B，C}二進(jìn)制編碼的結(jié)果為111，項集c－{A，C}二進(jìn)制編碼的結(jié)果為101。a&b＝a，表明{A，B}為{A，B，C}的子集，a&c! ＝a，表明{A，B}并非{A，C}的子集。

性質(zhì)2對于排序樹中第k 層的結(jié)點A 和B，結(jié)點A 表示的頻繁項集為{A[1]，A[2]，…，A[k]}，結(jié)點B 表示的頻繁項集為{B[1]，B[2]，…，B[k]}，若結(jié)點B 是結(jié)點A 兄弟節(jié)點，則有A[1]＝B[1]，A[2]＝B[2]，…，A[k－1]＝B[k－1]，A[k]! ＝B[k][14]。

性質(zhì)3對于排序樹中第k 層節(jié)點A 和其子節(jié)點B，那么B 代表的項集是A 代表的項集的超集，即，A屬于?B只有在事務(wù)記錄包含A 代表的項集的情況下，才可能包含B 代表的項集。

2.2 實例介紹

現(xiàn)舉例說明本文算法，事務(wù)記錄如表1所示，設(shè)定挖掘頻繁項集的最小支持度為0.4。候選1-項集的支持事務(wù)數(shù)如表2所示。去掉支持度小于0.4的候選1-項集“4”之后，按照支持度從大到小排序的頻繁1-項集的結(jié)果為:“3”，“2”，“1”，“5”。編碼后的頻繁1-項集如表3所示。對每個事務(wù)記錄進(jìn)行二進(jìn)制編碼，編碼后的事務(wù)記錄如表4所示。

表1 實例的事務(wù)記錄

表2 候選1-項集的持事務(wù)數(shù)

表3 編碼后的項

表4 編碼后的事務(wù)記錄

初始化頻繁1-項集的節(jié)點之后，節(jié)點“3”二進(jìn)制編碼的結(jié)果對每個編碼后的事務(wù)記錄進(jìn)行與運(yùn)算。由性質(zhì)3，如果dataset&1000＝1000，則節(jié)點“3”表示的項集是該事務(wù)記錄的子集，從而可以將該事務(wù)記錄添加到節(jié)點“3”包含的事務(wù)記錄之中?？梢缘玫焦?jié)點“3”包含的事務(wù)記錄有T1，T2，T3，T5。同理可得，節(jié)點“2”包含的事務(wù)記錄有T2，T3，T4，T5。節(jié)點“1”包含的事務(wù)記錄有T1，T3，T5。節(jié)點“5”包含的事務(wù)記錄有T2，T3，T4。由于根節(jié)點含有“3”，“2”，“1”，“5”四個子節(jié)點，根據(jù)性質(zhì)4 知道可以產(chǎn)生的候選2-項集為“32”，“31”，“35”，“21”，“25”，“15”。

統(tǒng)計候選項集‘32’的支持度需要遍歷的事務(wù)記錄為節(jié)點“3”包含的事務(wù)記錄而不是所有的事務(wù)記錄。由性質(zhì)3可以知道，遍歷事務(wù)記錄的時候，與事務(wù)記錄進(jìn)行“與”運(yùn)算即可。如果dataset&100＝100相等，說明該事務(wù)包含“32”，所以可以將該事務(wù)分配給節(jié)點“3”的子節(jié)點“32”。可以得到“3”的子節(jié)點“32”包含的事務(wù)記錄為T2，T3，T5。同理可得“31”包含的事務(wù)記錄為T1，T3，T5?！?5”包含的事務(wù)記錄為T2，T3?！?1”包含的事務(wù)記錄為T3，T5?！?5”包含的事務(wù)記錄為T2，T3，T4?！?5”包含的事務(wù)記錄為T3。由于節(jié)點“15”的支持度為0.2，小于最小支持度，去掉該節(jié)點。在統(tǒng)計候選項集的支持度的時候，節(jié)點“3”的子節(jié)點需要遍歷的事務(wù)記錄數(shù)量為4，節(jié)點“2”的子節(jié)點需要遍歷的事務(wù)記錄的數(shù)量也為4，節(jié)點“1”的子節(jié)點需要遍歷的事務(wù)記錄數(shù)量為3。

經(jīng)過上述步驟的操作，節(jié)點“3”有三個子節(jié)“32”，“31”，“35”。所以由性質(zhì)4，產(chǎn)生的候選3-項集為“321”，“325”，“315”。通過Apriori算法的性質(zhì)2可知，“315”一定不是頻繁項集，因為子集“15”為非頻繁項集。判斷“321”是否是頻繁項集需要遍歷的事務(wù)記錄為節(jié)點“31”包含的事務(wù)記錄T2，T3，T5。對每個事務(wù)記錄的操作為dataset&10＝10。如果相等，則說明dataset包含“321”，可以獲得的事務(wù)記錄為T3，T5。同理可得“325”的事務(wù)記錄為T2，T3。節(jié)點“2”有兩個子節(jié)點“21”、“25”。所以產(chǎn)生的候選3-項集為“215”。由于該項集的子集“15”是非頻繁項集，所以去掉該項集。在統(tǒng)計候選項集支持度的時候，節(jié)點“32”子節(jié)點需要遍歷的事務(wù)記錄數(shù)量為3。

通過節(jié)點“32”可以得到頻繁3項集為“321”，“325”。由于節(jié)點“32”含有兩個子節(jié)點，所以可以產(chǎn)生的候選4項集為“3215”，因為該候選項集包含有3-項集“315”，而“315”是非頻繁項集，所以“3215”是非頻繁項集。算法到此結(jié)束。

在挖掘頻繁項集的過程中，需要統(tǒng)計支持度的候選項集為“3”，“2”，“1”，“4”，“5”，“32”，“31”，“35”，“21”，“25”，“15”，“321”，“325”。在使用Apriori或者FIMST 算法統(tǒng)計候選項集的支持度的時候，這些項集需要遍歷的事務(wù)記錄數(shù)量為13×5＝75，而使用本文算法的時候，需要遍歷的事務(wù)記錄數(shù)量為5×5＋4×3＋4×2＋3×1＋3×2＝54。所以本文算法減少統(tǒng)計候選項集需要遍歷事務(wù)記錄的比例為28%。因此通過給節(jié)點添加事務(wù)記錄這個屬性，可以有效的減少統(tǒng)計候選項集需要遍歷的事務(wù)記錄的數(shù)量，提高算法的執(zhí)行效率。

頻繁項集節(jié)點組成的排序樹如圖2所示，灰色填充的節(jié)點為非頻繁項集節(jié)點。

2.3 算法描述

1)掃描事務(wù)記錄，獲取所有單個項集的支持度。剔除非頻繁1-項集，并將頻繁-1項集根據(jù)支持事務(wù)數(shù)按照從大到小的順序排列；

2)對事務(wù)記錄進(jìn)行二進(jìn)制編碼；

3)初始化根節(jié)點，并為根節(jié)點分配孩子。根節(jié)點的孩子為所有的頻繁1-項集。對根節(jié)點的每個孩子節(jié)點與事務(wù)記錄進(jìn)行“與”運(yùn)算的方式分配事務(wù)記錄；

4)根據(jù)每個頻繁-1項集的兄弟節(jié)點為其分配候選2-項集的孩子節(jié)點。由于候選2-項集的所有子集都是頻繁1-項集，所以不需要剪枝。對每個候選2-項集遍歷其父節(jié)點包含事務(wù)記錄，并與事務(wù)記錄進(jìn)行“與”運(yùn)算的方式為候選項集節(jié)點分配事務(wù)記錄，去掉含有的事務(wù)記錄比例小于預(yù)先設(shè)定的支持度的候選項集節(jié)點；

5)根據(jù)每個頻繁k-項集的兄弟節(jié)點為其分配候選(k＋1)-項集的子節(jié)點。利用Apriori算法性質(zhì)2對子節(jié)點進(jìn)行剪枝。對每個候選(k＋1)-項集遍歷其父節(jié)點包含事務(wù)記錄，并與事務(wù)記錄進(jìn)行“與”運(yùn)算的方式為候選項集節(jié)點分配事務(wù)記錄，去掉含有的事務(wù)記錄比例小于預(yù)先設(shè)定的支持度的候選項集節(jié)點；

6)不斷重復(fù)第5步，直到不能產(chǎn)生候選項集節(jié)點為止。

2.4 算法的性能分析

通過對頻繁項集和候選項集以節(jié)點的方式進(jìn)行組織，利用節(jié)點之間的關(guān)系，進(jìn)行候選項集的產(chǎn)生和支持事務(wù)數(shù)的統(tǒng)計，從而提高算法的執(zhí)行效率[21]。

1)避免了多次掃描數(shù)據(jù)庫，僅僅掃描兩遍數(shù)據(jù)庫，就可以通過編碼后的事務(wù)集代替數(shù)據(jù)庫中的事務(wù)記錄。之后僅僅通過在內(nèi)存中的運(yùn)算，就可以得到全部頻繁項集。

2)根據(jù)性質(zhì)1，可以利用二進(jìn)制的運(yùn)算代替此Apriori算法執(zhí)行過程中的集合之間的運(yùn)算。集合在編程語言中需要轉(zhuǎn)化為特定的數(shù)據(jù)結(jié)構(gòu)，再進(jìn)行集合之間的運(yùn)算。而二進(jìn)制編碼后的項集可以省略中間步驟，從而提高算法的執(zhí)行效率。

3)根據(jù)性質(zhì)2可以知道兄弟節(jié)點具有共同的前綴，不需要對所有頻繁k-項集兩兩之間判斷是否有相同(k-1)項來進(jìn)行連接步驟了。在頻繁k-項集的個數(shù)為n 時，連接步驟因為需要兩兩頻繁k-項集的判斷，所以時間復(fù)雜度為O(n2)，而在本文算法中省去了判斷的步驟，因為兄弟節(jié)點的前綴都是相同的，兄弟節(jié)點直接連接就可以產(chǎn)生候選項集。

4)根據(jù)性質(zhì)3，利用父節(jié)點代表的頻繁項集是子節(jié)點代表的候選項集的子集的條件，可以減少統(tǒng)計子節(jié)點代表的候選項集支持度需要遍歷的事務(wù)記錄數(shù)量。給節(jié)點添加一個屬性，表示包含該節(jié)點的所有事務(wù)記錄。這樣由于父節(jié)點是子節(jié)點的子集，那么只有在包含父節(jié)點的基礎(chǔ)上，才可能包含子節(jié)點，這樣可以遍歷父節(jié)點的事務(wù)記錄屬性，獲得子節(jié)點的所有事務(wù)記錄屬性。相當(dāng)于在統(tǒng)計候選項集節(jié)點支持度時利用了統(tǒng)計父節(jié)點支持度的事務(wù)記錄的結(jié)果，避免了每次統(tǒng)計候選項集支持度時，需要遍歷所有事務(wù)記錄。對于從根節(jié)點到任意一個葉子節(jié)點，每個節(jié)點包含的事務(wù)記錄是非增的，這樣隨著候選項集節(jié)點深度越大，其需要遍歷的事務(wù)記錄數(shù)量越少。

3 實驗驗證

實驗環(huán)境:處理器2.7 GHz Intel Core i5，內(nèi)存8 GB 1867 MHz DDR3，操作系統(tǒng)mac OS 10.13.5，采用Python3.6作為開發(fā)語言，分別實現(xiàn)了基本的Apriori算法，F(xiàn)IMST 算法和Node-Apriori算法。實驗數(shù)據(jù)采用的數(shù)據(jù)集為UCI Machine Learning Repository中的mushroom 數(shù)據(jù)集、chess數(shù)據(jù)集以及R 語言擴(kuò)展自導(dǎo)的groceries數(shù)據(jù)集，這三個數(shù)據(jù)集經(jīng)常被使用在關(guān)聯(lián)規(guī)則算法實驗中。實驗?zāi)康氖菍Ρ热N算法在mushroom 數(shù)據(jù)集、chess數(shù)據(jù)集以及groceries數(shù)據(jù)集上的表現(xiàn)。mushroom 數(shù)據(jù)集中的事務(wù)數(shù)為8124，事務(wù)的長度均為23，總共包含120個項。chess數(shù)據(jù)集中包括的事務(wù)記錄數(shù)為3196，事務(wù)的長度均為36，雖然該數(shù)據(jù)集中的事務(wù)數(shù)較少，但是頻繁規(guī)則較多，所以選擇比較的支持度較大。groceries數(shù)據(jù)集是R 語言arules包自帶的數(shù)據(jù)集，是某個雜貨店一個月的真實交易記錄，包含有9 835條消費(fèi)記錄和139個商品，該數(shù)據(jù)集中事務(wù)記錄和事務(wù)項都較多，在支持度較小的時候?qū)θN算法的運(yùn)行時間才具有區(qū)分度。

圖3、圖4和圖5分別表示三種算法在mushroom 數(shù)據(jù)集、chess數(shù)據(jù)集以及groceries數(shù)據(jù)集中的運(yùn)行時間的折線圖。

在支持度較小的時候，頻繁1-項集會較多，由于算法是層層迭代的，所以造成之后的計算量增多，也就是算法的運(yùn)行時間會隨著支持度的增大而減少。從圖3、圖4和圖5可知，Node-Apriori算法在支持度較小時，其運(yùn)行時間均遠(yuǎn)小于另外兩種算法；在支持度較大時，耗費(fèi)時間也小于另外兩種算法。隨著支持度的減少，挖掘的關(guān)聯(lián)規(guī)則越多，其他兩種算法與Node-Apriori算法的差距就越大。而FIMST 算法雖說較Apriori算法有一定的提升，但是僅僅是在連接產(chǎn)生候選項集的過程中進(jìn)行了優(yōu)化，而算法在時間上消耗最多的過程當(dāng)屬于遍歷事務(wù)記錄統(tǒng)計候選項集的支持度[16]。算法Node-Apriori在FIMST 算法改進(jìn)的基礎(chǔ)上，給節(jié)點增加了事務(wù)記錄這個屬性，有效的減少了統(tǒng)計候選項集支持度需要遍歷的事務(wù)記錄數(shù)量，極大的提高了算法的執(zhí)行效率。

對于mushroom 數(shù)據(jù)集在支持度為0.2的時候，統(tǒng)計得到三種算法在挖掘頻繁項集的過程中產(chǎn)生的候選項集個數(shù)為54 522，對于候選項集Node-Apriori算法遍歷的事務(wù)記錄數(shù)量為124 558 694，而總的事務(wù)記錄數(shù)量為8 214?？梢缘玫较噍^于Apriori算法，Node-Apriori算法減少了遍歷事務(wù)記錄數(shù)量的比例為72%。這個比例對于3.2實例介紹的少了許多，是因為隨著候選項集節(jié)點的深度的增加，統(tǒng)計其支持度的時候需要遍歷的事務(wù)記錄數(shù)越少。

注意，節(jié)點中可能包含重復(fù)數(shù)據(jù)。例如節(jié)點“3”包含的數(shù)據(jù)集為T1，T2，T3，T5。節(jié)點“2”包含的事務(wù)記錄有T2，T3，T4，T5。兩個節(jié)點都包含T2，T3，T5。這是因為事務(wù)記錄中包含項2，也是可能包含項3的。并且，算法采用的是廣度優(yōu)先的搜索方式，生成候選項集，統(tǒng)計支持度，剔除非頻繁項集。在數(shù)據(jù)量比較多的時候，由于每個節(jié)點包含的數(shù)據(jù)量包含重復(fù)的部分，對內(nèi)存的消耗上還是比較大的。

4 結(jié)論

本文在FIMST 算法的基礎(chǔ)上，利用頻繁項集和候選項集以節(jié)點關(guān)系組織的形式，進(jìn)行候選項集的產(chǎn)生，從而改進(jìn)了Apriori算法的執(zhí)行效率。Node-Apriori算法通過對事務(wù)記錄進(jìn)行二進(jìn)制編碼的方式編碼事務(wù)記錄，給頻繁項集節(jié)點添加事務(wù)記錄的屬性，統(tǒng)計候選項集節(jié)點的支持度的時候，僅僅需要掃描候選項集父節(jié)點的所有事務(wù)記錄即可。然后利用二進(jìn)制編碼的數(shù)據(jù)進(jìn)行集合間的運(yùn)算。有效的提高了算法的執(zhí)行效率。但是同級節(jié)點之間包含可能相同的事務(wù)記錄，在事務(wù)記錄較多的時候，對內(nèi)存的需求比較大。之后的工作可以就組織候選項集的方式上進(jìn)行展開。