吉 祥 黃樹(shù)成

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘研究中的一個(gè)熱門(mén)話題，它的主要作用是發(fā)現(xiàn)海量數(shù)據(jù)中隱藏著的有趣的關(guān)聯(lián)和有意義的聯(lián)系。Apriori 算法是經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法，其本質(zhì)是在項(xiàng)集的冪集中利用統(tǒng)計(jì)學(xué)的基本原理，通過(guò)多次掃描數(shù)據(jù)庫(kù)找出頻繁項(xiàng)集，再根據(jù)已找到的頻繁項(xiàng)集生成關(guān)聯(lián)規(guī)則［6］。近年來(lái)，國(guó)內(nèi)外許多學(xué)者對(duì)關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行了大量的研究，其主要工作是提高挖掘算法的效率。如Savasere 等提出的基于數(shù)據(jù)分割的Partition 算法，Park 等提出的基于散列的哈希算法以及國(guó)內(nèi)學(xué)者于守健等提出利用前綴項(xiàng)集的存儲(chǔ)方式，通過(guò)哈希表快速查找來(lái)提高查找效率［1］。這些算法都在一定程度或不同側(cè)重點(diǎn)上對(duì)Apriori算法進(jìn)行了優(yōu)化，但這些算法并沒(méi)有充分發(fā)揮多核CPU的優(yōu)勢(shì)，因而在實(shí)際應(yīng)用中仍不夠理想。本文首先對(duì)Apriori 算法的挖掘過(guò)程進(jìn)行詳細(xì)概述與論證，研究候選項(xiàng)集的剪枝和支持度計(jì)數(shù)過(guò)程，針對(duì)支持度計(jì)數(shù)過(guò)程，提出一種基于Hash 樹(shù)的并行計(jì)數(shù)算法，改進(jìn)算法可以有效提高支持度計(jì)數(shù)的速度，從而提高關(guān)聯(lián)規(guī)則的挖掘效率。

2 經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法Apriori算法

Apriori 算法是由Agrawal等在1993年提出的非常有影響力的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法［7］。Apriori 算法是一種廣度優(yōu)先的搜索算法，它通過(guò)迭代查找來(lái)挖掘頻繁項(xiàng)集，比如用頻繁k-項(xiàng)集探索候選k+1 項(xiàng)集。首先，算法掃描一次數(shù)據(jù)集生成候選1-項(xiàng)集C1，對(duì)C1做篩選，刪除C1中支持度小于給定下限值minsup 的候選項(xiàng)得到頻繁1-項(xiàng)集L1。對(duì)L1做連接運(yùn)算并去除不必要的項(xiàng)集產(chǎn)生候選2-項(xiàng)集C2，將C2中支持度不滿足的項(xiàng)刪除得到頻繁2-項(xiàng)集L2。對(duì)以上敘述的過(guò)程進(jìn)行有限步的循環(huán)，若沒(méi)有新的頻繁項(xiàng)集出現(xiàn)，算法終止。

現(xiàn)具體闡述Apriori算法的主要步驟：

1）掃描事務(wù)數(shù)據(jù)集，產(chǎn)生候選1-項(xiàng)集的集合C1；

2）統(tǒng)計(jì)C1中每個(gè)候選集的計(jì)數(shù)值，剔除不符合下限值的項(xiàng)，生成頻繁1-項(xiàng)集的集合L1；

3）設(shè)定初始值n=1；

4）對(duì)Ln作Ln∞Ln的連接運(yùn)算，再剪掉運(yùn)算結(jié)果不必要的項(xiàng)集，生成候選n+1項(xiàng)集Cn+1；

5）統(tǒng)計(jì)Cn+1中每個(gè)候選集的計(jì)數(shù)值，剔除不符合下限值的項(xiàng)，生成頻繁n+1項(xiàng)集的集合Ln+1；

6）若Ln+1≠?，對(duì)n 作增1 操作，返回4）；否則，轉(zhuǎn)7）；

7）從頻繁集中尋找規(guī)則，刪除小于給定置信度的規(guī)則，算法結(jié)束。

從上述步驟來(lái)看，Apriori 算法存在三個(gè)缺點(diǎn)：1）候選項(xiàng)集的規(guī)模較大，盡管采用了剪枝技術(shù)，但仍存在不必要的候選項(xiàng)集；2）計(jì)算候選集支持度時(shí)，效率太低，算法每次將數(shù)據(jù)記錄與所有候選集對(duì)比了一次；3）計(jì)算支持度時(shí)，算法每次讀取了事務(wù)數(shù)據(jù)集，系統(tǒng)時(shí)間開(kāi)銷(xiāo)較大。針對(duì)上述缺點(diǎn)，本文提出了基于Hash 樹(shù)并行計(jì)算支持度的優(yōu)化算法。該算法對(duì)前兩個(gè)缺點(diǎn)進(jìn)行改進(jìn)，對(duì)于第三個(gè)缺點(diǎn)，國(guó)內(nèi)外已有很多文獻(xiàn)做了進(jìn)一步的研究，本文不做研究。

3 基于Hash 樹(shù)的并行計(jì)數(shù)的改進(jìn)算法-Apriori_ParallelCount

為了優(yōu)化Apriori算法，以下性質(zhì)將作為優(yōu)化依據(jù)。

性質(zhì)1：k 項(xiàng)集lk是頻繁項(xiàng)集的必要條件是它所有的k-1子項(xiàng)集lk-1也是頻繁項(xiàng)集［6］。

證明：設(shè)有一k 頻繁集lk，則Support(lk)不小于支持度下限。對(duì)于lk的任意一個(gè)k-1 項(xiàng)子集lk-1，Support(lk-1)≥Support(lk)，那么Support(lk-1)也必然不小于支持度下限。又因lk-1可以是lk的任何k-1子項(xiàng)集。故而命題得證。

性質(zhì)2：如果k-項(xiàng)集lk的任意一個(gè)k-1 子項(xiàng)集lk-1不是頻繁項(xiàng)集，則k-項(xiàng)集lk不是頻繁k-項(xiàng)集［6］。

證明：現(xiàn)有一k-項(xiàng)集lk，它存在一個(gè)k-1 項(xiàng)子集lk-1不是頻繁項(xiàng)集，那么Support(lk-1)一定比支持度下限值小，而Support(lk-1)≥Support(lk)，所以Support(lk)也小于支持度下限值。也就是說(shuō)，lk是非頻繁集。命題得證。

性質(zhì)3：如果k-項(xiàng)集lk是頻繁k-項(xiàng)集，則其每一個(gè)項(xiàng)在頻繁k-1 項(xiàng)集Lk-1中出現(xiàn)的次數(shù)一定不小于k-1次［7］。

證明：設(shè)有一k頻繁集lk。由性質(zhì)1知，它的全部k-1 項(xiàng)子集都是頻繁的，又lk共有k 個(gè)k-1 子項(xiàng)集，所以，這k 個(gè)k-1 子項(xiàng)集都在頻繁k-1 項(xiàng)集Lk-1中出現(xiàn)。那么，對(duì)于項(xiàng)集lk來(lái)說(shuō)，它的每一個(gè)項(xiàng)在Lk-1中都至少出現(xiàn)了k-1次。命題得證。

性質(zhì)3 為改進(jìn)算法縮減候選項(xiàng)集規(guī)模提供了有力的依據(jù)。在改進(jìn)算法中應(yīng)用該性質(zhì)可以進(jìn)一步對(duì)頻繁k-1項(xiàng)集Lk-1進(jìn)行篩選，使參與連接的頻繁項(xiàng)集數(shù)量大大縮減，從而降低了候選項(xiàng)集的數(shù)目，提升了算法的挖掘性能。

本文應(yīng)用以上性質(zhì)對(duì)Apriori算法進(jìn)行改進(jìn)，主要體現(xiàn)在兩個(gè)方面。

1）降低候選項(xiàng)集規(guī)模。由頻繁k-項(xiàng)集Lk求候選k+1 項(xiàng)集Ck時(shí)先統(tǒng)計(jì)Lk中每個(gè)元素的頻數(shù)，由性質(zhì)3知元素頻數(shù)少于k的項(xiàng)集是不可能自連接得到頻繁k+1 項(xiàng)集，所以可以在連接前將其刪除，減少頻繁k-項(xiàng)集的數(shù)量，進(jìn)而縮小連接產(chǎn)生的候選k+1項(xiàng)集的規(guī)模。

2）組織候選集成Hash 樹(shù)結(jié)構(gòu)，并行計(jì)算支持度。在對(duì)候選項(xiàng)集Ck進(jìn)行支持度計(jì)數(shù)時(shí)，為了減少比較次數(shù)，可以利用Hash 樹(shù)達(dá)到此目的。將Ck組織成Hash 樹(shù)，存放在不同的桶中，計(jì)數(shù)時(shí)，將事務(wù)中的所有項(xiàng)集也散列到對(duì)應(yīng)的桶中。這種方法不是將事務(wù)中的每個(gè)項(xiàng)集與所有候選項(xiàng)集比較，而是將它們與同一桶內(nèi)候選項(xiàng)集進(jìn)行匹配［5］。另外，考慮到現(xiàn)在的CPU幾乎都是多核的，這就使多線程并行成為可能。對(duì)于事務(wù)數(shù)據(jù)集D，可以將其均勻的劃分為若干塊子數(shù)據(jù)集S，為每個(gè)子數(shù)據(jù)集S 創(chuàng)建線程，線程在該子數(shù)據(jù)集S 上對(duì)候選項(xiàng)集進(jìn)行支持度計(jì)數(shù)，其結(jié)果存放在當(dāng)前線程內(nèi)部數(shù)組中。待得所有線程執(zhí)行完畢，取出各線程內(nèi)部數(shù)組數(shù)據(jù)相加得到候選項(xiàng)集Ck在整個(gè)事務(wù)數(shù)據(jù)集D 上的支持度計(jì)數(shù)。

改進(jìn)的Apriori_ParallelCount 算法的執(zhí)行步驟如下：

1）掃描事務(wù)數(shù)據(jù)集，產(chǎn)生候選1-項(xiàng)集的集合C1；

2）將候選1-項(xiàng)集C1組織成Hash 樹(shù)結(jié)構(gòu)，對(duì)C1中的候選集并行計(jì)數(shù)，具體過(guò)程如步驟5）所示，刪除小于給定支持度的項(xiàng)生成頻繁1-項(xiàng)集L1；

3）設(shè)定初始值i=1；

4）對(duì)頻繁項(xiàng)集Li中每個(gè)項(xiàng)出現(xiàn)的次數(shù)進(jìn)行統(tǒng)計(jì)，根據(jù)性質(zhì)3，若某一項(xiàng)出現(xiàn)的次數(shù)小于i，則刪除包含該項(xiàng)的項(xiàng)集得到，然后由經(jīng)過(guò)連接步和剪枝步生成候選i+1項(xiàng)集Ci+1；

5）將候選項(xiàng)集Ci+1組織成Hash 樹(shù)結(jié)構(gòu)。掃描事務(wù)數(shù)據(jù)集D，將數(shù)據(jù)集D 均勻劃分為若干塊，利用多線程技術(shù)并行計(jì)算候選項(xiàng)集Ci+1在各個(gè)塊上的支持度，最后，歸并各個(gè)塊上的支持度獲得Ci+1在數(shù)據(jù)集D上的支持度。刪除不符合閾值的項(xiàng)，生成頻繁i+1項(xiàng)集的集合Li+1；

6）若Li+1≠?，對(duì)i作增1操作，返回4）；否則，轉(zhuǎn)7）；

7）從頻繁集中尋找規(guī)則，刪除小于給定置信度的規(guī)則，算法結(jié)束。

舉例來(lái)闡述改進(jìn)算法。設(shè)有一零食售貨商店，假設(shè)5 位客戶購(gòu)買(mǎi)了5 種商品。5 位客戶記為T(mén)1～T5。5 種商品為巧克力、果凍、餅干、面包、牛奶，為方便，5種商品記為1～5。給定的支持度為3，算法將數(shù)據(jù)集D 均勻分割為2 塊，創(chuàng)建兩個(gè)線程并行計(jì)算候選項(xiàng)集的支持度。則優(yōu)化后的算法執(zhí)行過(guò)程如圖1所示。

具體解釋如下：算法掃描數(shù)據(jù)集D 產(chǎn)生候選1-項(xiàng)集C1，將數(shù)據(jù)集D 劃分為D1和D2，創(chuàng)建兩個(gè)線程對(duì)候選1-項(xiàng)集并行計(jì)數(shù)，合并候選1-項(xiàng)集在D1和D2上的計(jì)數(shù)結(jié)果得到候選1-項(xiàng)集在數(shù)據(jù)集D 上的計(jì)數(shù)結(jié)果。對(duì)C1進(jìn)行篩選，將計(jì)數(shù)結(jié)果小于3 的候選集剔除掉得到頻繁集L1，對(duì)L1作連接和剪枝運(yùn)算產(chǎn)生候選2-項(xiàng)集L2。對(duì)以上敘述的過(guò)程進(jìn)行有限步的循環(huán)，若沒(méi)有新的頻繁項(xiàng)集出現(xiàn)，算法終止。注意L2中由于項(xiàng)2和3的個(gè)數(shù)均小于2，故由性質(zhì)3 知包含2 或3 的候選項(xiàng)全部剔除。對(duì)于支持度計(jì)數(shù)，將候選項(xiàng)集組織成特殊的樹(shù)狀結(jié)構(gòu)Hash 樹(shù)，然后散列數(shù)據(jù)記錄到Hash 樹(shù)中進(jìn)行比對(duì)。以上圖C2為例，構(gòu)建Hash樹(shù)并散列事務(wù)T2，如圖2所示。

圖1 改進(jìn)算法挖掘頻繁項(xiàng)集過(guò)程

圖2 在Hash樹(shù)根節(jié)點(diǎn)散列事務(wù)

支持度計(jì)數(shù)過(guò)程中，算法首先根據(jù)C2構(gòu)建Hash 樹(shù)，Hash 函數(shù)為h（p）=p mod 3，然后枚舉事務(wù)T2 形成2-項(xiàng)集，最后將事務(wù)T2 所包含的2-項(xiàng)集散列到Hash 樹(shù)中進(jìn)行匹配。由于事務(wù)中的項(xiàng)集只與同一桶內(nèi)的候選項(xiàng)集比較，因而有效降低了計(jì)算支持度所花費(fèi)的時(shí)間開(kāi)銷(xiāo)。

4 實(shí)驗(yàn)與分析

為了比較改進(jìn)算法Apriori_ParallelCount 和經(jīng)典算法Apriori的效率，本節(jié)以實(shí)驗(yàn)為基礎(chǔ)對(duì)兩個(gè)算法進(jìn)行詳細(xì)闡述。本實(shí)驗(yàn)的測(cè)試環(huán)境如下：采用Inter Core i3-2350M 2.30GHz 的CPU，4GB內(nèi)存，Windows 8.1 專(zhuān)業(yè)版操作系統(tǒng)，使用Java 編程語(yǔ)言，編程工具為Eclipse Photon 2018。

實(shí)驗(yàn)所采用的數(shù)據(jù)集是從GitHub 社區(qū)上下載的retail文本文件，該文件共有88162條事務(wù)記錄。

實(shí)驗(yàn)1：本次實(shí)驗(yàn)比較Apriori 算法和創(chuàng)建一個(gè)線程的Apriori_ParallelCount 算法的時(shí)間效率。給定支持度值為2%，4%，6%，8%，10%。從數(shù)據(jù)集文件retail 中選取前10000 條記錄來(lái)測(cè)試兩個(gè)算法的運(yùn)行時(shí)間。其執(zhí)行時(shí)間（單位：ms）的結(jié)果見(jiàn)表1。

表1 不同支持度兩個(gè)算法執(zhí)行時(shí)間比較

將實(shí)驗(yàn)結(jié)果以點(diǎn)線圖的形式表示出來(lái)，如圖3所示。

圖3 不同支持度兩算法執(zhí)行時(shí)間比較

從上圖可以看出，改進(jìn)算法Apriori_Parallel-Count相較于經(jīng)典算法Apriori時(shí)間性能有較明顯的提升，Apriori 算法執(zhí)行時(shí)間集中在12000ms 左右，改進(jìn)算法多集中在3000ms 左右。另外，兩個(gè)算法運(yùn)行所花費(fèi)的時(shí)間整體上都是伴隨著支持度的增大而降低。這是因?yàn)?，支持度的增大?huì)使頻繁項(xiàng)集數(shù)目出現(xiàn)一定程度的縮減，從而提高算法的效率。從曲線的前半部分可以看出，支持度從2%增大到4%時(shí)，兩個(gè)算法的執(zhí)行時(shí)間都出現(xiàn)大幅度的下降，尤其是改進(jìn)算法Aproiri_ParallelCount。出現(xiàn)這個(gè)現(xiàn)象的原因可能與數(shù)據(jù)集本身有關(guān)，本實(shí)驗(yàn)采用的數(shù)據(jù)集在支持度設(shè)定為2%到4%時(shí)，頻繁項(xiàng)集的規(guī)模會(huì)大大的減少。再看曲線后半部分，當(dāng)支持度為10%時(shí)，改進(jìn)算法的執(zhí)行時(shí)間有所增加。這個(gè)情況主要考慮是存在誤差，由于支持度設(shè)定為8%和10%時(shí)，算法執(zhí)行時(shí)間差距不大，因而可能會(huì)產(chǎn)生細(xì)微的誤差。整體來(lái)看，改進(jìn)算法的挖掘效率較經(jīng)典算法具備顯著優(yōu)勢(shì)。

實(shí)驗(yàn)2：本實(shí)驗(yàn)繼續(xù)比較Apriori 算法和創(chuàng)建一個(gè)線程的Apriori_ParallelCount_算法的執(zhí)行時(shí)間。設(shè)給定的支持度值為10%，從數(shù)據(jù)集文件retail中分別取1000條、5000條、10000條、50000條和80000條事務(wù)記錄來(lái)測(cè)試兩個(gè)算法的運(yùn)行時(shí)間。測(cè)試結(jié)果（單位：ms）如表2所示。

表2 不同記錄數(shù)兩個(gè)算法執(zhí)行時(shí)間比較

將表格轉(zhuǎn)換為曲線圖，如圖4所示。

圖4 不同記錄數(shù)兩個(gè)算法執(zhí)行時(shí)間比較

從圖4 可以看出，改進(jìn)算法的執(zhí)行時(shí)間普遍比Apriori 算法少，尤其是當(dāng)數(shù)據(jù)量很大時(shí)，改進(jìn)算法的性能更顯著。隨著記錄數(shù)的增加，我們可以看到經(jīng)典算法的執(zhí)行時(shí)間增長(zhǎng)幅度很快，幾乎呈指數(shù)級(jí)增長(zhǎng)，而改進(jìn)算法的增長(zhǎng)幅度較慢，有放緩的趨勢(shì)。這說(shuō)明改進(jìn)算法相較于經(jīng)典Apriori 算法更適合處理十萬(wàn)級(jí)甚至更大的數(shù)據(jù)量，有一定的實(shí)用價(jià)值。另外，在記錄數(shù)只有1000條時(shí)，我們發(fā)現(xiàn)Apriori 算法的執(zhí)行時(shí)間比改進(jìn)算法更短。這是因?yàn)?，改進(jìn)算法讀取事務(wù)數(shù)據(jù)集形成候選1-項(xiàng)集時(shí)，需要按字典序?qū)蜻x項(xiàng)集排序，這個(gè)過(guò)程會(huì)花費(fèi)一些時(shí)間?？偟膩?lái)說(shuō)，盡管改進(jìn)算法花費(fèi)了一些時(shí)間排序，但在面對(duì)急劇增長(zhǎng)的數(shù)據(jù)量情況下，改進(jìn)算法的時(shí)間效能是優(yōu)越于經(jīng)典算法Apriori的。

實(shí)驗(yàn)3：本實(shí)驗(yàn)比較不同線程版本Apriori_ParallelCount 算法的運(yùn)行效率。設(shè)給定的支持度值為10%，從數(shù)據(jù)集文件retail中選取前50000條記錄來(lái)測(cè)試不同線程數(shù)的改進(jìn)算法的運(yùn)行時(shí)間。實(shí)驗(yàn)結(jié)果（單位：ms）如表3所示。

表3 不同線程數(shù)改進(jìn)算法執(zhí)行時(shí)間比較

將此表以曲線圖表示，如圖5所示。

從圖5 可以看出，隨著線程數(shù)的增多，改進(jìn)算法的執(zhí)行時(shí)間整體在降低。這是因?yàn)?，?shí)驗(yàn)所采用的CPU 是雙核四線程且操作系統(tǒng)是基于線程調(diào)度的，所以多個(gè)線程會(huì)被調(diào)度到多個(gè)核心上運(yùn)行，使線程并行執(zhí)行，從而降低算法的執(zhí)行時(shí)間。尤其是當(dāng)創(chuàng)建的線程數(shù)從1 變?yōu)樗膬杀? 時(shí)，算法執(zhí)行時(shí)間大幅下降。當(dāng)線程數(shù)從4 增加到5 時(shí)，算法執(zhí)行時(shí)間有所上升。這是因?yàn)椋€程數(shù)多于核心數(shù)，線程上下文切換需要花費(fèi)時(shí)間?？傮w來(lái)說(shuō)，改進(jìn)算法充分利用了多核CPU的優(yōu)勢(shì)，其效率較經(jīng)典算法也有明顯提高。

圖5 不同線程數(shù)改進(jìn)算法執(zhí)行時(shí)間比較

5 結(jié)語(yǔ)

本文提出了一種基于Hash 樹(shù)的并行計(jì)數(shù)的關(guān)聯(lián)規(guī)則優(yōu)化算法，通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證改進(jìn)算法與經(jīng)典算法之間的性能差異。改進(jìn)算法對(duì)候選項(xiàng)集的數(shù)目進(jìn)一步做了裁剪，同時(shí)利用多線程技術(shù)并行計(jì)算各個(gè)候選項(xiàng)集的支持度，進(jìn)而提高算法挖掘頻繁模式的速度。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法相對(duì)于Aprori算法是十分高效的，尤其對(duì)在海量數(shù)據(jù)中挖掘關(guān)聯(lián)規(guī)則具備優(yōu)勢(shì)。