改進(jìn)的基于兩個矩陣的關(guān)聯(lián)規(guī)則挖掘算法

曹風(fēng)華

(內(nèi)蒙古財經(jīng)學(xué)院計算機(jī)信息管理學(xué)院，內(nèi)蒙古 呼和浩特 010070)

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

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

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

1 相關(guān)概念和性質(zhì)

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

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

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

性質(zhì)1和性質(zhì)2的詳細(xì)證明可參見文獻(xiàn)［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的項的個數(shù)至少要有k個。

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

性質(zhì)3 ?i∈I，如果i在頻繁k－1項集的集合Lk－1中的出現(xiàn)次數(shù)＜k－1，則 i 不會出現(xiàn)在任何頻繁k－項集中。

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

根據(jù)頻繁k－項集的支持?jǐn)?shù)的定義很容易得出結(jié)論，證明略。

2 ABTM算法描述

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

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

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

(4)求頻繁k－項集。K－項集的產(chǎn)生是通過對頻繁k－1項集的擴(kuò)展來求解的，對于頻繁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，那么擴(kuò)展該頻繁k－1－項集為 k－項集{i1，i2，…，ik－1，iu}，對這k個項目對應(yīng)的映射矩陣中的列向量做內(nèi)積運算，即如果 BVi1·BVi2·…·BVik－1·BViu的結(jié)果不小于最小支持?jǐn)?shù)，則項集{i1，i2，…，ik－1，iu}是頻繁k－項集。

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

3 算法執(zhí)行實例

以表1所示的事務(wù)數(shù)據(jù)集為例，介紹ABTM算法的執(zhí)行過程，設(shè)最小支持?jǐn)?shù)min_sup=2，具體過程如下:

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

表2 事務(wù)矩陣TM

表3 支持矩陣SM

表4 裁剪后的TM矩陣

第一步 掃描事務(wù)數(shù)據(jù)集構(gòu)造映射矩陣，如表2所示。得到 L1={a，b，c，d，e}。

第二步 構(gòu)造二項支持矩陣，如表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所示。

第四步 根據(jù)頻繁2－項集中的項和二項支持矩陣記錄的相關(guān)信息，可以得到擴(kuò)展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中項的個數(shù)＜3，故L3是最大頻繁集。

4 算法比較和實驗結(jié)果

4.1 算法性能比較

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

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

4.2 實驗結(jié)果與分析

算法采用Java實現(xiàn)，數(shù)據(jù)庫為SQL Server2000，實驗機(jī)器CPU為Intel Pentium42.8 GHz，內(nèi)存為512 MB，測試數(shù)據(jù)集有10000條事務(wù)，由IBM數(shù)據(jù)生成器生成，該數(shù)據(jù)生成器可以在IBM網(wǎng)站下載。

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

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

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

圖2 屬性數(shù)量對算法的影響

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

5 結(jié)束語

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

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

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

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

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

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

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

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

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