改進的基于兩個矩陣的關聯規則挖掘算法

曹風華

(內蒙古財經學院計算機信息管理學院，內蒙古 呼和浩特 010070)

關聯規則挖掘作為數據挖掘的一個重要研究分支，主要研究從大型數據集中發現隱藏的、有趣的、屬性間存在的規律。由于關聯規則挖掘的對象通常是包含有海量原始數據和大量項目的事務數據庫，因此如何提高從大型數據庫中挖掘關聯規則的效率和伸縮性，以便有效降低計算的復雜性、提高算法的運行速度，仍是關聯規則挖掘研究領域的核心問題。

R.Agrawal等人首先提出了挖掘關聯規則的Apriori算法［1－2］，該算法是挖掘布爾關聯規則最有影響的數據挖掘算法之一，其基本思想是重復掃描數據庫，根據一個頻繁集的任意子集都是頻繁集的原理，可以從長度為k的頻繁項集迭代地產生長度為k+1的候選項集，再掃描數據庫以驗證其是否為頻繁項集。該算法因多次掃描規模不變的事務數據庫，耗費大量時間，隨后出現了很多類Apriori算法，其中有些算法將事務數據庫以二進制形式映射到內存中然后進行相關挖掘操作，這類算法由于減少了直接掃描數據庫的次數，避免了在I/O操作上浪費大量時間，在一定程度上提高了挖掘效率。

文獻［3］中提出了一種高效的 ABM(Algorithm Based on Matrix)算法，該算法具有前文所述類Apriori算法的優點，但每次操作的對象都是規模不變的向量，而事實上，當項集維數很高時，參與運算向量的規模將在一定程度上影響算法的執行效率，因此，在ABM算法的基礎上，文中提出了改進的 ABTM(Algorithm Based on Two Matrix)算法，在算法中引入了兩個矩陣，一個用來映射數據庫，另一個用來存儲頻繁2－項集相關信息。通過對兩個矩陣的操作，有效避免了Apriori算法中需要多次重復掃描規模不變的數據庫和產生大量候選集并進行剪枝的缺點，并解決了ABM算法中影響算法執行效率的瓶頸問題，實驗表明，本算法具有較好的性能。

1 相關概念和性質

設 I={i1，i2，…，im}是全體數據項的集合，數據項集是指由不同數據項構成的非空集合。設D為全體事務集，每條事務T有惟一標識TID，且T?I。對于項集X?I，當且僅當X?T時稱項集X在事物T中出現。項集X在事務集合D中出現的次數稱為X的支持數，記做sup(X)。對于用戶給定的最小支持數閥值min_sup，若sup(X)≥min_sup，則項集X是頻繁項集，否則X是非頻繁項集。若頻繁項集X有k個數據項組成，則稱X是頻繁k－項集，所有頻繁k－項集的集合記做Lk。

性質1 頻繁k－項集的所有m，0＜m＜k，維子集都是頻繁項集。

性質2 m維非頻繁項集的任一k，k＞m，維超集是非頻繁項集。

性質1和性質2的詳細證明可參見文獻［3］。

推論:項集{i1，i2，…，ik，iu}，k≥2，i1＜ i2＜ … ＜ik＜iu)為頻繁k+1項集的必要條件是:(1){ij，iu}，j=1，2，…，k必須都為頻繁2－項集。(2)能與iu組成頻繁2－項集且小于iu的項的個數至少要有k個。

證明:{i1，i2，…，ik，iu}為頻繁 k +1 項集，對于 j =1，2，…，k，2 項集{ij，iu}共有 k 個且都是項集{i1，i2，…，ik，iu}的子集，由性質1知，這k個2項集都是頻繁項集，同時可能存在 k ＜j＜u，ij＜ iu且{ij，iu}是頻繁 2項集，所以能與iu組成頻繁2－項集且＜iu的項的個數至少有k個。

性質3 ?i∈I，如果i在頻繁k－1項集的集合Lk－1中的出現次數＜k－1，則 i 不會出現在任何頻繁k－項集中。

證明:假設項目i出現在某頻繁k－項集中，由于該頻繁k－項集有k個k－1維子集，且k個子集都在Lk－1中，因此對于i，在這k個k－1維子集中共出現k－1 次，故≥k－1，與條件矛盾，因此i不會出現在任何頻繁k－項集中。

根據頻繁k－項集的支持數的定義很容易得出結論，證明略。

2 ABTM算法描述

(1)構造事務矩陣TM(Transaction Matrix)，并產生頻繁1－項集。對于有m條事務，n個項的事務數據庫，建立一個 m × (n+1)的事務矩陣［8］TMm×p，p=n+1，并將矩陣每位元素初始化為0。掃描事務數據庫，統計每個項目出現的次數，同時如果項目i在第j條事務中出現，則將Mji置1，否則置0。矩陣的第n+1列為hcount列，該列記錄每行中1的個數，每行的hcount值表示該條事物中項目的個數，也即該事務的長度。矩陣前n列分別是與項目i對應的位向量BVi，某列中1的個數即是該列對應的項目的支持數，如果該值大于最小支持數，則該項目是頻繁1－項集。

(2)構造二項支持矩陣SM(Support Matrix)，產生頻繁2－項集。建立一個n×(n－1)的矩陣SMn×q，n為項目數，q=n－1，并將矩陣每位元素初始化為0。將頻繁1－項集中的項目進行排序后(本文使用字典序)，對所有項目i，取比i大的項目j，對它們對應的向量做內積運算［5－6］，即如果 B Vi·BVj不小于最小支持數，則項集{i，j}是頻繁2－項集，將 S Mij置1，否則置0。矩陣的第n行為vcount行，該行記錄每列中1的個數，每列的vcount值表示能與該列對應的項組成頻繁2－項集且編號小于該項的項的個數。

(3)裁剪事務矩陣TM［3］。在求頻繁k－項集前，計算各單項在Lk－1中的出現次數，根據性質3，若＜k－1，則刪除i在矩陣中對應的列。重新計算矩陣的hcount列的值后，根據性質4，如果某行的hcount值＜k，則刪除該行。

(4)求頻繁k－項集。K－項集的產生是通過對頻繁k－1項集的擴展來求解的，對于頻繁k－1項集{i1，i2，…，ik－1}，i1＜i2＜ … ＜ ik－1，如果在二項支持矩陣中有 SM［ik－1，iu］=1，iu＞ ik－1，iu列的 vcount值不小于k －1，且 SM［i1，iu］=SM［i2，iu］= … =SM［ik－2，iu］=1，那么擴展該頻繁k－1－項集為 k－項集{i1，i2，…，ik－1，iu}，對這k個項目對應的映射矩陣中的列向量做內積運算，即如果 BVi1·BVi2·…·BVik－1·BViu的結果不小于最小支持數，則項集{i1，i2，…，ik－1，iu}是頻繁k－項集。

(5)重復執行算法的第(3)～(4)步，直至不能產生更高階的頻繁項集。

3 算法執行實例

以表1所示的事務數據集為例，介紹ABTM算法的執行過程，設最小支持數min_sup=2，具體過程如下:

表1 事務數據集

表2 事務矩陣TM

表3 支持矩陣SM

表4 裁剪后的TM矩陣

第一步 掃描事務數據集構造映射矩陣，如表2所示。得到 L1={a，b，c，d，e}。

第二步 構造二項支持矩陣，如表3所示。得到L2={{a，b}，{a，c}，{a，d}，{a，e}，{b，c}，{b，e}，{c，e}}。

第三步 對于L2中的各單項，由于=1＜2，因此刪除矩陣的d列，對hcount重新計算，由于1，5，6行的hcount都＜3，刪除這3行，得到裁剪后的矩陣，如表4所示。

第四步 根據頻繁2－項集中的項和二項支持矩陣記錄的相關信息，可以得到擴展3－項集{a，b，c}，{a，c，e}和{b，c，e}，由映射矩陣可得到 BVa·BVb·BVc=2，BVa·BVc·BVe=1，BVb·BVc·BVe=2，因min_sup=2，得到 L3={{a，b，c}，{b，c，e}}。由于 L3中項的個數＜3，故L3是最大頻繁集。

4 算法比較和實驗結果

4.1 算法性能比較

Apriori算法是挖掘關聯規則的經典算法，與該算法相比，ABTM算法僅需要掃描數據庫一遍，減少了讀取數據庫的時間，而且頻繁k－項集的產生是通過擴展項集和向量內積運算求解，不需要連接和剪枝等操作。Apriori算法操作的對象直接是事物數據庫，而且每次掃描數據庫的規模不變，ABTM算法通過轉換將數據庫映射到矩陣中以二進制形式存儲，通過合理設計稀疏矩陣的數據結構，使最終占用空間相對較小。

ABM算法［3］是一種高效的關聯規則挖掘算法，與該算法相比，ABTM算法的不同之處在于兩個方面:(1)采用矩陣映射事務數據庫，而不是建立單個項目的位向量，盡管兩種算法將數據庫映射到內存中占用的空間相同，但矩陣存儲能夠實現對規模的有效裁剪，隨著項集維數的增長，ABTM算法將矩陣中無用的行和列刪除，使得內存空間逐步得到釋放，同時參與運算向量的長度越短，計算量也越小。(2)ABM算法中的支持矩陣是(n－1)×n的，但考慮到最小項目不可能與更小的項目構成頻繁2－項集，因此無需為最小項目建立對應的列，所以ABTM算法采用的是(n－1)×(n －1)矩陣，節省了存儲空間［8］。

4.2 實驗結果與分析

算法采用Java實現，數據庫為SQL Server2000，實驗機器CPU為Intel Pentium42.8 GHz，內存為512 MB，測試數據集有10000條事務，由IBM數據生成器生成，該數據生成器可以在IBM網站下載。

為比較提出的ABTM算法和經典算法在不同支持度下的所用時間，設置了不同的支持度分別運行各算法，描點繪圖如下，得到的實驗結果如圖1所示。

圖1 不同支持度下個算法運行時間

由于提出的算法和ABM算法性能的差異取決于候選項集的產生速度以及產生數量的大小，而屬性數量的多少直接影響了候選項集的生成。設置支持度固定為0.15，針對不同的屬性個數，分別統計各算法的所用時間，繪圖如2所示。

圖2 屬性數量對算法的影響

從圖2可以看出，ABTM算法運行所需時間顯著少于Apriori算法和ABM算法。圖1中，隨著所設定的支持度越來越小，Apriori算法和ABM算法總運算量與支持度呈非線性增長，所需時間也大大增加，而由于ABTM算法僅需要掃描數據庫一遍，減少了讀取數據庫的時間，而且頻繁k－項集的產生是通過擴展項集和向量內積運算求解，不需要連接和剪枝等操作，隨支持度減小，算法所需時間并未顯著增加。圖2中，隨著屬性數量的增加，Apriori算法和ABM算法運行時間迅速上升，而ABTM的擴展項集和向量內積運算并不會因為屬性數量增加而收到較大影響。

5 結束語

文中算法引入兩個矩陣，分別從時間和空間上進行優化，使得算法效率顯著提高，是一種易理解且可行性較好的算法。算法還可以在以下兩方面做進一步的優化:(1)由于在構造事務矩陣后就完成了頻繁1－項集的產生，所以可以在構造二項支持矩陣前進行一次映射矩陣的裁剪。(2)由于可能存在一些項并非頻繁1－項集，那么這些項不可能再出現在更高階的頻繁項集中，因此在構造二項支持矩陣時也沒有必要考慮這些項。

［1］戴新喜，白似雪.一種高效的基于模式矩陣的Apriori改進算法［J］.廣西師范大學學報，2007，25(4):176 －179.

［2］HAN Jiawei，MICELINE K.數據挖掘概念與技術［M］.范明，孟小峰，譯.北京:機械工業出版社，2001.

［3］牛小飛，石冰，盧軍，等.挖掘關聯規則的高效ABM算法［J］.計算機工程，2004，30(11):118 －120.

［4］王柏盛，劉寒冰，靳書和，等.基于矩陣的關聯規則挖掘算法［J］.微計算機信息，2007，54(53):144 －146.

［5］劉曉玲，李玉忱.一種利用邏輯“與”運算挖掘頻繁項集的算法［J］.科技論壇，2005(15A):122－123.

［6］劉以安，劉強，鄒曉華.基于向量內積的關聯規則挖掘算法研究［J］.計算機工程與應用，2006，21(3):172 －174.

［7］曾萬聃，周緒波，戴勃，等.關聯規則挖掘的矩陣算法［J］.計算機工程，2006，32(2):45 －47.

［8］徐章艷，劉美玲，張師超，等.Apriori算法的三種優化方法［J］.計算機工程與應用，2004，40(36):190 －192.