基于哈希樹的并行關聯(lián)規(guī)則挖掘算法研究?

吉 祥 黃樹成

（江蘇科技大學計算機學院 鎮(zhèn)江 212003）

1 引言

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

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

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

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

1）掃描事務數據集，產生候選1-項集的集合C1；

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

3）設定初始值n=1；

4）對Ln作Ln∞Ln的連接運算，再剪掉運算結果不必要的項集，生成候選n+1項集Cn+1；

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

6）若Ln+1≠?，對n 作增1 操作，返回4）；否則，轉7）；

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

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

3 基于Hash 樹的并行計數的改進算法-Apriori_ParallelCount

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

性質1：k 項集lk是頻繁項集的必要條件是它所有的k-1子項集lk-1也是頻繁項集［6］。

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

性質2：如果k-項集lk的任意一個k-1 子項集lk-1不是頻繁項集，則k-項集lk不是頻繁k-項集［6］。

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

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

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

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

本文應用以上性質對Apriori算法進行改進，主要體現(xiàn)在兩個方面。

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

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

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

1）掃描事務數據集，產生候選1-項集的集合C1；

2）將候選1-項集C1組織成Hash 樹結構，對C1中的候選集并行計數，具體過程如步驟5）所示，刪除小于給定支持度的項生成頻繁1-項集L1；

3）設定初始值i=1；

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

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

6）若Li+1≠?，對i作增1操作，返回4）；否則，轉7）；

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

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

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

圖1 改進算法挖掘頻繁項集過程

圖2 在Hash樹根節(jié)點散列事務

支持度計數過程中，算法首先根據C2構建Hash 樹，Hash 函數為h（p）=p mod 3，然后枚舉事務T2 形成2-項集，最后將事務T2 所包含的2-項集散列到Hash 樹中進行匹配。由于事務中的項集只與同一桶內的候選項集比較，因而有效降低了計算支持度所花費的時間開銷。

4 實驗與分析

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

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

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

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

將實驗結果以點線圖的形式表示出來，如圖3所示。

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

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

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

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

將表格轉換為曲線圖，如圖4所示。

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

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

實驗3：本實驗比較不同線程版本Apriori_ParallelCount 算法的運行效率。設給定的支持度值為10%，從數據集文件retail中選取前50000條記錄來測試不同線程數的改進算法的運行時間。實驗結果（單位：ms）如表3所示。

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

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

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

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

5 結語

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