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

汪 浩， 吳 靜

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

0 引言

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

1 關聯規則基本概念

現介紹關聯規則挖掘中的一些基本概念與知識[2]：

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

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

2 基于布爾矩陣的Apriori算法

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

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

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

圖1 事務數據庫D及初始化后的布爾矩陣M

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

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

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

3 PMApriori算法

3.1 主要性質

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

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

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

證明：行向量中1的個數表示此次事務中包含的項數，在求頻繁k-項集時，當行向量中1的個數小于k時，說明此事務項中包含的項小于k，與產生頻繁k-項集無關[8]，故可刪除。

3.2 基本步驟

基本步驟如下：

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

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

3) 由性質2可知，當行向量中1的個數小于k時，此行事務項與產生頻繁 k-項集無關，也可刪除，故刪除行向量計數小于k的事務項，保留1的個數大于等于k的事務項。

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

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

3.3 示例說明

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

圖3 PMApriori算法流程示例

3.4 性能分析

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

圖4 記錄數不同時算法性能對比

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

4 結語

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

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

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

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

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

[5] 周文秀.關聯規則挖掘算法的研究與改進[D].武漢:武漢理工大學,2008.

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

[7] 鄭巖. 數據倉庫與數據挖掘原理及應用[M].北京:清華大學出版社,2011:168.

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