畢玉萍，胡世昌，李勁華

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

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

1 Apriori算法

1.1 基本概念

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

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

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

3)使用數(shù)組的方式。數(shù)組的長度為頻繁1-項集的個數(shù)，每個位置代表頻繁1項集中的一個項，如果存在則為1，不存在則為0。可以確定每個孩子節(jié)點在數(shù)組中對應的項，如果該項存在，則可以進行下一步的搜索。利用孩子節(jié)點在頻繁1-項集按頻次排序后的索引，可以立刻計算出在事務記錄的中位置。時間復雜度為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)生的候選項集進行剪枝[15]。若對一個項集的所有子集都進行是否是頻繁項集的判斷，由于一個k-項集的所有子集數(shù)量為2k，則這個過程的時間復雜度為O(2k)，顯然是不符合實際的。由于一個頻繁項集的子集都是頻繁項集，所以假如一個候選(k＋1)-項集的k 個k-項子集，都是頻繁項集，那么此候選(k＋1)-項集的非空子集就都是頻繁項集，即該(k＋1)-項集就不會是非頻繁項集的超集，通過性質(zhì)1剪枝，復雜度由O(2k)減少到了O(k)。剪枝的依據(jù)可以是若(k＋1)個候選頻繁(k＋1)-項集的每個k-項子集是否都是頻繁k-項集來判斷，即有一個或者多個k-項子集不是頻繁k-項集，那么該候選(k＋1)-項集不可能為頻繁(k＋1)-項集[16]。通過這種方式可以有效剔除一定不是頻繁項集的候選項集；

3)通過遍歷數(shù)據(jù)庫，對候選頻繁(k＋1)-項集的支持度進行統(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ù)庫時需要對候選項集和事務進行模式匹配，這個過程需要消耗大量的時間[19]。

1.4 FIMIST算法

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

2 Node-Apriori算法

2.1 基本概念

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

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

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

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

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

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

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

性質(zhì)2對于排序樹中第k 層的結點A 和B，結點A 表示的頻繁項集為{A[1]，A[2]，…，A[k]}，結點B 表示的頻繁項集為{B[1]，B[2]，…，B[k]}，若結點B 是結點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只有在事務記錄包含A 代表的項集的情況下，才可能包含B 代表的項集。

2.2 實例介紹

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

表1 實例的事務記錄

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

表3 編碼后的項

表4 編碼后的事務記錄

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

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

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

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

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

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

2.3 算法描述

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

2)對事務記錄進行二進制編碼；

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

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

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

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

2.4 算法的性能分析

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

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

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

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

4)根據(jù)性質(zhì)3，利用父節(jié)點代表的頻繁項集是子節(jié)點代表的候選項集的子集的條件，可以減少統(tǒng)計子節(jié)點代表的候選項集支持度需要遍歷的事務記錄數(shù)量。給節(jié)點添加一個屬性，表示包含該節(jié)點的所有事務記錄。這樣由于父節(jié)點是子節(jié)點的子集，那么只有在包含父節(jié)點的基礎上，才可能包含子節(jié)點，這樣可以遍歷父節(jié)點的事務記錄屬性，獲得子節(jié)點的所有事務記錄屬性。相當于在統(tǒng)計候選項集節(jié)點支持度時利用了統(tǒng)計父節(jié)點支持度的事務記錄的結果，避免了每次統(tǒng)計候選項集支持度時，需要遍歷所有事務記錄。對于從根節(jié)點到任意一個葉子節(jié)點，每個節(jié)點包含的事務記錄是非增的，這樣隨著候選項集節(jié)點深度越大，其需要遍歷的事務記錄數(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 語言擴展自導的groceries數(shù)據(jù)集，這三個數(shù)據(jù)集經(jīng)常被使用在關聯(lián)規(guī)則算法實驗中。實驗目的是對比三種算法在mushroom 數(shù)據(jù)集、chess數(shù)據(jù)集以及groceries數(shù)據(jù)集上的表現(xiàn)。mushroom 數(shù)據(jù)集中的事務數(shù)為8124，事務的長度均為23，總共包含120個項。chess數(shù)據(jù)集中包括的事務記錄數(shù)為3196，事務的長度均為36，雖然該數(shù)據(jù)集中的事務數(shù)較少，但是頻繁規(guī)則較多，所以選擇比較的支持度較大。groceries數(shù)據(jù)集是R 語言arules包自帶的數(shù)據(jù)集，是某個雜貨店一個月的真實交易記錄，包含有9 835條消費記錄和139個商品，該數(shù)據(jù)集中事務記錄和事務項都較多，在支持度較小的時候?qū)θN算法的運行時間才具有區(qū)分度。

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

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

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

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

4 結論

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