Apriori算法的壓縮二進制編碼改進

谷 鵬，肖建于，徐成振

（淮北師范大學(xué)計算機科學(xué)與技術(shù)院，安徽淮北235000）

隨著大數(shù)據(jù)時代的到來，各領(lǐng)域產(chǎn)生的數(shù)據(jù)呈“井噴式”增長，數(shù)量多而雜，從以前的GB 級別，飛速發(fā)展到現(xiàn)在PB 甚至EB 級別的數(shù)據(jù). 雖然數(shù)據(jù)增長很快，但是真實價值的數(shù)據(jù)是分散在這些海量數(shù)據(jù)中的. 因此數(shù)據(jù)挖掘技術(shù)應(yīng)運而生，而關(guān)聯(lián)規(guī)則是其中一個重要的分支，在數(shù)據(jù)挖掘中有著廣泛的運用. Agrawal 等[1]在1993 年首次提出的Apriori 算法是關(guān)聯(lián)規(guī)則挖掘算法中最有影響力的一種，但Apriori也存在缺陷：一是生成候選項集和頻繁項集的效率低；二是要多次掃描數(shù)據(jù)庫，I/O 負(fù)載大；三是候選項集與未處理的事務(wù)集對比占用大量時間和空間.

不少學(xué)者對此從各個方面進行研究改進.Bhandari 等[2]采用并行算法和聚類算法的思想對算法進行改進. Vasoya 等[3]提出將數(shù)據(jù)庫劃分為各個簇，再用基于矩陣的Apriori 算法對每個簇進行處理. 張巖慶[4]、陳興蜀等[5]針對大數(shù)據(jù)集使用分布式的方法對算法進行改進. 徐哲煒等[6]通過增加約束條件減少候選集的想法改進Apriori算法.Liu 等[7]利用先驗的思想對數(shù)據(jù)進行處理，結(jié)合信息的特性產(chǎn)生關(guān)聯(lián)規(guī)則.

這些算法對Apriori 進行了改進，提高了算法效率，但也存在著不足. 一是忽視了數(shù)據(jù)庫中的事務(wù)可能存在的重復(fù)信息，使得算法的對比次數(shù)增多；二是沒有對處理的事務(wù)進行壓縮整理，消耗了大量存儲空間. 對此，本文提出基于壓縮二進制編碼的Apriori 改進算法CBE-Apriori (Compressed Binary Encoded)，只需要對數(shù)據(jù)庫掃描兩次，利用二進制數(shù)間的運算更為高效的思想，將集合轉(zhuǎn)化成二進制編碼，并對事務(wù)的二進制編碼壓縮，減少空間占用和比較次數(shù)提升算法效率.

1 相關(guān)知識

1.1 性質(zhì)與定義

定義1[8]設(shè)I={i1,i2,...,im}是所有項的集合，T={t1,t2,...,tn}是所有事務(wù)的集合. 事務(wù)集合T的每個項集都是I的子集.

性質(zhì)1[9]頻繁項集的所有非空子集必是頻繁項集，任意非頻繁項的超集必是非頻繁項集.

性質(zhì)2頻繁k項集A和B連接得到的候選(k+1)項集C，若其子集{A[k],B[k]}不是頻繁項集，則候選集C必不是頻繁項集.

證明：由性質(zhì)1得，因為C的子集{A[k],B[k]}不是頻繁項，所以C不是頻繁項集.

性質(zhì)3將A和B兩個數(shù)據(jù)集轉(zhuǎn)化為二進制編碼，若AB=A，則A為B的子集.

性質(zhì)4將A和B兩個數(shù)據(jù)集轉(zhuǎn)化為二進制編碼，則A∧B的結(jié)果為A和B不同時含有的項集.

1.2 基本算法

Apriori算法是數(shù)據(jù)挖掘算法中最為常用的算法之一，應(yīng)用在各種領(lǐng)域，例如鐵路風(fēng)險的預(yù)控[10]、森林蟲害預(yù)測[11]、城市交通流預(yù)測[12]等.Apriori算法的核心基于性質(zhì)1，通過尋找候選項集并利用迭代的方法由頻繁k項集生成候選(k+1)項集，其主要流程由以下兩步組成：

（1）連接，若兩個k項集的前k-1 項相等但第k項不同，則連接兩個頻繁項集生成候選(k+1)項集.

（2）剪枝，通過掃描數(shù)據(jù)庫，計算候選項集中每個項集的支持度，將其與最小支持度進行比較，若小于最小支持度，則不是頻繁項集，刪去此項來縮減候選項選項集，最后遍歷完生成頻繁項集.

2 CBE-Apriori 算法

由以上描述可知，Apriori 算法每次生成頻繁項集時需要對數(shù)據(jù)庫進行掃描，影響算法的運行效率；連接時，需判斷項集前(k-1)項元素是否相等；計算支持度時需對每個事務(wù)進行對比，沒有對事務(wù)進行壓縮.

2.1 算法改進思想

（1）通過掃描數(shù)據(jù)庫得到的頻繁1-項集，對事務(wù)進行二進制編碼，利用頻繁1-項集對事務(wù)編碼可以減小編碼的長度，且二進制運算的效率更高，以可以提高算法的性能.

（2）事務(wù)編碼后會出現(xiàn)重復(fù)項，對其統(tǒng)計并將重復(fù)項只保留一個，這樣可以減少之后頻繁項集編碼與事務(wù)編碼對比的次數(shù).

（3）根據(jù)性質(zhì)2、3、4，將候選項集和事務(wù)進行邏輯“與”的操作來計算支持度；將兩個候選項集邏輯“異或”操作，判斷其是否為頻繁項集，減少了算法的時間復(fù)雜度.

2.2 算法流程

CBE-Apriori算法流程如下：

輸入：事務(wù)數(shù)據(jù)庫D，最小支持度min-support

輸出：頻繁項集L

（1）掃描輸入的事務(wù)數(shù)據(jù)庫D，獲取頻繁1-項集

（2）掃描事務(wù)數(shù)據(jù)庫D，通過獲取的頻繁1-項集將事務(wù)轉(zhuǎn)化為二進制編碼.

（3）掃描事務(wù)的二進制編碼，將相同的二進制編碼壓縮成一個并計數(shù)出現(xiàn)次數(shù)到n中，得到事務(wù)二進制編碼集Dc.

（4）通過頻繁k項集生成候選(k+1)項集，利用性質(zhì)3將候選k項集和Dc進行與的位運算操作，計算支持度，對比min-support生成頻繁(k+1)項集.

（5）利用性質(zhì)2 和4 將頻繁項集兩兩異或，判斷結(jié)果是否為頻繁2-項集. 若是將頻繁項集與異或的結(jié)果利用或位運算將其連接生成候選k項集，重復(fù)步驟（4）的操作生成頻繁(k+1)項集.

（6）最終將步驟(4)生成的結(jié)果合并為L.

3 算法分析與實驗對比

3.1 實例分析

舉例說明CBE-Apriori算法，事務(wù)數(shù)據(jù)庫如表1所示，設(shè)最小支持度為0.4.

表1 事務(wù)數(shù)據(jù)庫

（1）掃描事務(wù)數(shù)據(jù)庫，獲取頻繁1-項集，對得到的頻繁1-項集轉(zhuǎn)化為二進制編碼，頻繁1-項集與編碼結(jié)果如表2所示.

表2 頻繁1-項集與編碼結(jié)果

（2）通過頻繁1-項集的編碼結(jié)果對事務(wù)集進行二進制編碼.每個事務(wù)中含有的單個頻繁1-項子集根據(jù)其對應(yīng)的二進制編碼，將它們利用邏輯“或”位運算操作進行連接，得到的事務(wù)與編碼結(jié)果如表3所示.

表3 事務(wù)與編碼結(jié)果

（3）掃描事務(wù)的二進制編碼結(jié)果，統(tǒng)計每個編碼出現(xiàn)的次數(shù)并刪除重復(fù)項，得到的事務(wù)編碼與重復(fù)數(shù)結(jié)果如表4所示.

表4 事務(wù)編碼與重復(fù)數(shù)結(jié)果

（4）掃描頻繁1-項集，將其兩兩組合生成候選2-項集，共生成C24=6 個候選2-項集，此步驟不能進行刪減操作，所以生成的候選2-項集規(guī)模較大.生成的候選2-項集與編碼結(jié)果如表5所示.

表5 候選2-項集與編碼結(jié)果

（5）根據(jù)性質(zhì)3，將候選2-項集編碼的結(jié)果與每個事務(wù)的二進制編碼邏輯“與”運算，若得到結(jié)果等于其候選2-項集編碼，則將其事務(wù)編碼對應(yīng)的重復(fù)數(shù)提取出進行累加，累加最終的結(jié)果除以事務(wù)總數(shù)可以得到其候選項集對應(yīng)的支持度.候選2-項集與支持度的結(jié)果如表6所示.

表6 候選2-項集與支持度結(jié)果

（6）根據(jù)最小支持度閾值去除不符合條件的候選2-項集生成頻繁2-項集，根據(jù)性質(zhì)2和性質(zhì)4，將得到的頻繁2-項集相互進行邏輯“異或”，將其結(jié)果是否存在與頻繁2-項集中，若存在則將兩個頻繁2-項集進行連接得到候選3-項集編碼. 例如候選2-項集編碼1100 與1010，1100∧1010=110 其結(jié)果存在于頻繁2-項集編碼中，則1101100=1110. 其結(jié)果為候選3-項集的編碼.

隨著職業(yè)教育的發(fā)展，中職學(xué)校英語學(xué)科成為一門必修學(xué)科，英語口語表達成為一項必備的語言技能。然而，英語又是中職學(xué)生學(xué)習(xí)最為吃力的學(xué)科之一，大多數(shù)學(xué)生為此備受打擊，已不再奢望能學(xué)好英語，處在進退維谷的尷尬境地。由此，要重點樹立學(xué)生學(xué)習(xí)英語的信心和勇氣，培養(yǎng)學(xué)生學(xué)習(xí)英語的興趣，在教學(xué)中注入情感，用發(fā)展的眼光看待學(xué)生。同時借鑒專業(yè)教學(xué)的理念，任務(wù)引領(lǐng)、驅(qū)動，明確學(xué)習(xí)目標(biāo)，搭建師生互動學(xué)習(xí)的平臺和學(xué)生展示的舞臺。再者，要尊重學(xué)生、愛護學(xué)生，建立和諧的師生關(guān)系，采用靈活的教學(xué)方法，定制學(xué)生的學(xué)習(xí)任務(wù)，讓每個學(xué)生學(xué)有所獲。

遍歷完頻繁2-項集編碼的最終結(jié)果只有一個1110，所以候選3-項集只存在一個，將其與事務(wù)編碼進行邏輯“與”，統(tǒng)計并計算得到其支持度0.6. 因為其頻繁3-項集有且只有一個，所以不能生成候選4-項集，程序到此結(jié)束，最終輸出所有頻繁項集.

3.2 性能分析

與Apriori 相比較，可以發(fā)現(xiàn)CBE-Apriori 有以下幾點改進：

（1）CBE-Apriori 算法只需對數(shù)據(jù)庫掃描兩次，避免Apriori 算法運行時多次對數(shù)據(jù)庫掃描的問題，使算法效率有著顯著的改善.

（2）利用位運算“與”“異或”“異或”代替Apriori算法生成候選項集和頻繁項集的步驟，因采用的是位運算，所以在數(shù)據(jù)集的連接和裁剪時的時間復(fù)雜度為O(1)，而Apriori 算法在連接兩個頻繁k項集時要判斷前k-1 項是否相同，因為要按照特點順序?qū)ζ溥M行排列，而在較好情況下，k項集排序的時間復(fù)雜度也有O(klogk)，而且裁剪操作時，要判斷候選(k+1)項集的子集，因為數(shù)目為k，所以時間復(fù)雜度為O(k). Apriori 算法的連接和裁剪的時間復(fù)雜度其結(jié)果為將兩者相乘得到O(k2logk). 所以相比較CBE-Apriori 算法在連接和裁剪上比Apriori 效率要更好.

（3）在對事務(wù)編碼時由于將重復(fù)項壓縮為一個，節(jié)約了數(shù)據(jù)占用的內(nèi)存空間. 在之后的實驗對比中，事務(wù)集經(jīng)過壓縮后相比于原事務(wù)個數(shù)有著明顯的減少，可在后續(xù)的對比步驟中可以減少時間復(fù)雜度.

3.3 實驗對比

實驗平臺為：Intel Core i5-8400 CPU，內(nèi)存16 GB @2667 MHz DDR4，操作系統(tǒng)為Windows 10，采用Python 3.7.3 作為編程語言，分別實現(xiàn)Apriori算法和CBE-Apriori 算法. 實驗數(shù)據(jù)選用UCI 數(shù)據(jù)庫中的蘑菇（Mushroom）數(shù)據(jù)集，該數(shù)據(jù)集中共有8 124 條事務(wù)，總計119 個屬性，事務(wù)含有屬性的最大個數(shù)為23 個. 在圖1 中按照30%、35%、40%、45%的支持度給出了Apriori 算法、BE-Apriori 算法[13]和CBE-Apriori 算法處理蘑菇數(shù)據(jù)集的各自運行時間.表7表示各支持度下，壓縮后事務(wù)集的個數(shù).

圖1 蘑菇數(shù)據(jù)集運行時間

表7 支持度與事務(wù)集個數(shù)結(jié)果

當(dāng)設(shè)定有支持度時，生成的頻繁1-項集對事務(wù)進行編碼，因濾去無意義的屬性，生成的事務(wù)編碼會生成大量重復(fù)項，對其進行過濾壓縮，由表7 可以看出事務(wù)集個數(shù)有明顯減少. 但是當(dāng)最小支持度達到45%時，事務(wù)集個數(shù)沒有變化，說明在最小支持度為45%的情況下，事務(wù)集的編碼沒有重復(fù)項.

圖1 顯示，最小支持度分別為30%、35%、40%、45%時，Apriori 算法運行時間分別為6.03 秒、2.43秒、1.33 秒、1.01 秒；BE-Apriori 算法運行時間分布為8.07 秒、3.91 秒、2.1 秒、1.36 秒；CBE-Apriori 算法運行時間分別為2.35 秒、1.11 秒、0.73 秒、0.66 秒. 分析實驗結(jié)果分析可知，BE-Apriori 算法雖然同樣用的二進制編碼，但是沒有對事物集壓縮，當(dāng)賦予的最小支持稍大時，運算效率不如初始的Apriori算法.

當(dāng)支持度較小時，生成的頻繁1-項集較多，會導(dǎo)致后續(xù)生成的候選項集和頻繁項集中的元素數(shù)量更大，使得運行時間更長.因為CBE-Apriori算法采用位運算代替集合運算，并將將要對比的事務(wù)數(shù)量進行壓縮，從而減少算法的運行時間.從圖1可以看出，當(dāng)支持度較小時，算法消耗的時間遠小于Apriori；當(dāng)支持度增加時算法的運行時間逐漸接近，但CBE-Apriori 算法的運行時間還是小于Apriori算法.

以上數(shù)據(jù)的對比結(jié)果顯示，CBE-Apriori 算法在空間存儲上和運行時間上對比Apriori 有著明顯的提升，運行時間最大提升達到61%.

4 結(jié)語

本文針對經(jīng)典Apriori 算法的缺點，提出通過生成的頻繁1-項集將事務(wù)轉(zhuǎn)化為二進制編碼，且對二進制編碼進行壓縮，使之后的運算都在內(nèi)存中完成. 并利用邏輯運算代替Apriori算法中集合直接的運算提高算法效率. 通過對算法時間復(fù)雜度的分析和實驗證明，相對于Apriori 算法，改進的算法可以更快速的得到頻繁項集和減少內(nèi)存空間的占用，并且因為對數(shù)據(jù)集的壓縮，也改進了當(dāng)最小支持度稍大時，只用二進制編碼運用于Apriori 算法時性能不如原算法的效率快的問題.