基于布爾矩陣Apriori算法的改進研究

汪 浩， 吳 靜

(西南科技大學(xué) 信息工程學(xué)院，四川 綿陽 621010)

0 引言

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘中的一個重要問題。Agrawal與 Srikant[1]于 1994年提出的 Apriori算法是數(shù)據(jù)挖掘中提取頻繁項集之間關(guān)聯(lián)規(guī)則的一種經(jīng)典算法。該算法采用頻繁項集的反單調(diào)性壓縮搜索空間，實現(xiàn)了頻繁項集的快速提取。但存在一些難以克服的性能瓶頸：①多次掃描數(shù)據(jù)庫，需要很大的 I/O負(fù)載；②可能產(chǎn)生龐大的候選集。基于布爾矩陣的 Apriori算法是將事務(wù)數(shù)據(jù)庫映射到布爾矩陣中，整個挖掘過程只掃描一次事務(wù)數(shù)據(jù)庫，大大降低了 I/O負(fù)載，但仍需要產(chǎn)生大量候選集。本算法在研究基于布爾矩陣的 Apriori算法的基礎(chǔ)上提出了一種改進的算法 PMApriori，先將事務(wù)數(shù)據(jù)庫映射到布爾矩陣上，然后根據(jù)相關(guān)性質(zhì)對布爾矩陣的行列進行修剪，最后直接生成頻繁項集。不需要進行連接和減枝步驟，不需要生成候選項集，提高了算法效率。

1 關(guān)聯(lián)規(guī)則基本概念

現(xiàn)介紹關(guān)聯(lián)規(guī)則挖掘中的一些基本概念與知識[2]：

關(guān)聯(lián)規(guī)則挖掘問題一般可以分為兩個子問題[4]：①找出事務(wù)數(shù)據(jù)庫中所有大于等于指定的最小支持度(minSup)的頻繁項集；②根據(jù)頻繁項集與用戶設(shè)定的最小置信度得到關(guān)聯(lián)規(guī)則。

對于第二個子問題的實現(xiàn)相對較為容易，因此，目前大量的研究工作都集中在第一個子問題上，它是關(guān)聯(lián)規(guī)則挖掘算法中的核心問題。

2 基于布爾矩陣的Apriori算法

算法思想[5-6]：只掃描數(shù)據(jù)庫一次，此算法將事務(wù)數(shù)據(jù)庫映射成一個布爾矩陣，矩陣中行代表事務(wù)，列代表數(shù)據(jù)項，通過逐行掃描相應(yīng)的列就能得到項的頻度。詳細(xì)描述如下：

首先將事務(wù)數(shù)據(jù)庫初始化為布爾矩陣。掃描事務(wù)數(shù)據(jù)庫D，假設(shè)數(shù)據(jù)庫D中有m個事務(wù)，n個數(shù)據(jù)項。令:fDM→即事務(wù)數(shù)據(jù)庫D映射成的布爾矩陣M為其中

圖1表示一個事務(wù)數(shù)據(jù)庫D及經(jīng)過初始化之后映射成的布爾矩陣M。然后依次計算矩陣M各列的列向量之和即可

圖1 事務(wù)數(shù)據(jù)庫D及初始化后的布爾矩陣M

得1-項集{Ii}的頻度，對于其值小于最小支持度的項集予以刪除，生成頻繁1-項集1L。再通過1L自連接產(chǎn)生候選2-項集C2，若要得到2-項集{Ii,Ij}的頻度，只需對矩陣M的第i列和第j列進行按位“與操作”，結(jié)果中1的個數(shù)即為所求項集頻度。同理，要得到k-項集的頻度，只需對矩陣的第1,2,…,k列進行按位“與操作”。最后生成頻繁k-項集Lk，直到候選k-項集kC=?則算法終止。假設(shè)最小支持度minSup=2，算法執(zhí)行過程如圖2所示。

圖2 基于矩陣的Apriori算法流程示例

由圖2可知，算法在求得頻繁項集kL時，仍需要頻繁項集1kL-進行自連接，將產(chǎn)生大量的候選項集Ck。故針對此算法的不足，提出優(yōu)化算法PMApriori。

3 PMApriori算法

3.1 主要性質(zhì)

性質(zhì)1：若布爾矩陣中，列向量中1的個數(shù)小于最小支持度，則可刪除此列。

證明：根據(jù)頻繁項集的反單調(diào)性[7]，即頻繁項集的所有非空子集必然也是頻繁的。列向量中1的個數(shù)表示此項的出現(xiàn)次數(shù)，若此列向量中1的個數(shù)小于最小支持度，則說明此列表示的項為非頻繁項集，與產(chǎn)生頻繁項集無關(guān)，故可刪除。

性質(zhì)2：若布爾矩陣中，行向量中1的個數(shù)小于k，則可刪除此行。

證明：行向量中1的個數(shù)表示此次事務(wù)中包含的項數(shù)，在求頻繁k-項集時，當(dāng)行向量中1的個數(shù)小于k時，說明此事務(wù)項中包含的項小于k，與產(chǎn)生頻繁k-項集無關(guān)[8]，故可刪除。

3.2 基本步驟

基本步驟如下：

1) 掃描事務(wù)數(shù)據(jù)庫D，將事務(wù)數(shù)據(jù)庫映射成布爾矩陣，并對布爾矩陣中的行向量和列向量中1的個數(shù)分別計數(shù)。

2) 由性質(zhì)1可知，當(dāng)列向量中1的個數(shù)小于最小支持度 minSup時，該項目列為非頻繁項集，與產(chǎn)生頻繁 2-項集無關(guān)，可刪除該項目列，若大于等于最小支持度，則保留。

3) 由性質(zhì)2可知，當(dāng)行向量中1的個數(shù)小于k時，此行事務(wù)項與產(chǎn)生頻繁 k-項集無關(guān)，也可刪除，故刪除行向量計數(shù)小于k的事務(wù)項，保留1的個數(shù)大于等于k的事務(wù)項。

4) 在求k(k≥2)維項集的頻度時，掃描布爾矩陣對應(yīng)的列，求 k-項集{I1,I2,…,Ik}的頻度，只需對矩陣的第1,2,…,k列向量進行按位“與操作”，然后對向量運算后的結(jié)果中的 1計數(shù)，如果大于等于最小支持度minSup，則為頻繁k-項集的子集。掃描完布爾矩陣，保留下來得子集則為所求頻繁k-項集。

5) 重復(fù)步驟 2～3，不停的壓縮矩陣，一方面可以降低矩陣的大小，另一方面可以提高算法的運行效率。然后再執(zhí)行步驟4, 直到kL為空, 算法終止。

3.3 示例說明

假設(shè)最小支持度 minSup=2，使用圖 1中所示的事務(wù)數(shù)據(jù)庫及映射后的布爾矩陣，對矩陣的行列向量進行計數(shù)先得到頻繁項集1L，然后對矩陣進行修剪壓縮，接著掃描修剪后的矩陣，挖掘出頻繁項集Lk，算法執(zhí)行過程如圖3所示。

圖3 PMApriori算法流程示例

3.4 性能分析

為了驗證 PMApriori算法的效率，將基于布爾矩陣的 Apriori算法與 PMApriori算法在相同的實驗環(huán)境下經(jīng)行比較測試，驗證算法所用的實驗硬件環(huán)境為：處理器為 Intel(R)Core(TM)2 Duo CPU T550，主頻1.83 GHz, 內(nèi)存2 G，硬盤容量160 G，操作系統(tǒng) Windows 7 旗艦版，系統(tǒng)類型 32位。兩種算法均采用 Visual C++語言實現(xiàn)，測試數(shù)據(jù)庫為SQL Server 2005所自有的 foodmart.mdb數(shù)據(jù)庫，挖掘樣本為對 dbo.sales_fact_1997表中數(shù)據(jù)預(yù)處理過的事務(wù)數(shù)據(jù)表，所含事務(wù)數(shù)據(jù)分別選取 1 000條、2 000條、3 000條、4 000條、5 000條。設(shè)定最小支持度為20%，實驗結(jié)果如圖4所示。

圖4 記錄數(shù)不同時算法性能對比

由圖 4可知，在相同數(shù)據(jù)集的前提下，PMApriori算法運行效率始終優(yōu)于基于布爾矩陣的Apriori算法。PMApriori算法與基于布爾矩陣的Apriori算法相比，運行時間增長趨勢更加平緩，說明在針對大型數(shù)據(jù)庫進行數(shù)據(jù)挖掘時，算法運行效率更加顯著。算法的運行時間與算法執(zhí)行過程有著緊密的關(guān)系，PMApriori算法在時間特性和空間特性上有顯著優(yōu)勢，原因在于產(chǎn)生頻繁項集前對存儲數(shù)據(jù)的矩陣進行有效的修剪壓縮，而且不用產(chǎn)生候選集，降低了內(nèi)存開銷；不需要經(jīng)行自連接、測試等操作，然后直接生成頻繁項集，有效地提高了算法的運行效率。

4 結(jié)語

關(guān)聯(lián)規(guī)則挖掘作為數(shù)據(jù)挖掘領(lǐng)域中的重點研究內(nèi)容，其受重視程度也將日益彰顯。為了提高關(guān)聯(lián)規(guī)則挖掘算法中頻繁項集的生成效率，在基于布爾矩陣的Apriori算法的基礎(chǔ)上提出了一種新的改進算法 PMApriori算法，并且與基于布爾矩陣的 Apriori算法做了性能對比分析，PMApriori算法性能更加優(yōu)越，此算法只需掃描一次數(shù)據(jù)庫，降低了 I/O開銷；能對矩陣的進行有效的修剪壓縮，且不需要生成大量候選集，減小內(nèi)存空間的消耗；對項集計數(shù)只需掃描矩陣中的部分?jǐn)?shù)據(jù)，提高了算法執(zhí)行效率。通過實驗結(jié)果可知，PMApriori算法能有效而又快速地從事務(wù)數(shù)據(jù)庫中提取頻繁項集，表現(xiàn)出了良好的性能。由于實驗數(shù)據(jù)的局限性，算法在海量數(shù)據(jù)挖掘的效率還沒有驗證，需要進一步深入研究。

[1] AGRAWAL R, SRIKANT R. Fast Algorithms for Mining Association Rules[C].Santiago: Proceedings of the VLDB International Conference,1994:487-499.

[2] 朱明.數(shù)據(jù)挖掘[M].第 2版.合肥:中國科學(xué)技術(shù)大學(xué)出版社,2008:160-163.

[3] 肖冬榮,楊磊.基于遺傳算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘[J].通信技術(shù),2010,43(01):205-207.

[4] 張圣.一種基于云計算的關(guān)聯(lián)規(guī)則 Apriori算法[J].通信技術(shù),2011,44(06):141-143.

[5] 周文秀.關(guān)聯(lián)規(guī)則挖掘算法的研究與改進[D].武漢:武漢理工大學(xué),2008.

[6] 裴古英.一種基于布爾矩陣的關(guān)聯(lián)規(guī)則快速挖掘算法[J].自動化與儀器儀表,2009,5(145):16-18.

[7] 鄭巖. 數(shù)據(jù)倉庫與數(shù)據(jù)挖掘原理及應(yīng)用[M].北京:清華大學(xué)出版社,2011:168.

[8] 朱嘉杰,蔡偉.一種安全事件模糊關(guān)聯(lián)規(guī)則挖掘算法[J].信息安全與通信保密,2010(04):63.