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

周 凱, 顧洪博, 李愛(ài)國(guó)

(1.東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院, 黑龍江 大慶 163318; 2.大慶油田工程有限公司, 黑龍江 大慶 163712)

數(shù)據(jù)挖掘是指從大量的數(shù)據(jù)中篩出有效的、可信的以及隱含信息的高級(jí)處理過(guò)程。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的一個(gè)重要研究方向，側(cè)重于確定數(shù)據(jù)庫(kù)中不同領(lǐng)域間的聯(lián)系，找出滿足給定支持度和可信度的多個(gè)域之間的依賴關(guān)系[1-2]。由Agrawal等人提出的基于布爾關(guān)聯(lián)規(guī)則挖掘頻繁項(xiàng)集的Apriori算法，用由下到上逐層搜索的迭代方法查找頻繁項(xiàng)集[3-5]。由于數(shù)據(jù)庫(kù)本身的數(shù)據(jù)量較大，會(huì)存在多次掃描數(shù)據(jù)庫(kù)以及多次迭代后產(chǎn)生大量候選集兩個(gè)主要問(wèn)題，最終導(dǎo)致算法效率不高。

國(guó)內(nèi)外學(xué)者對(duì)挖掘頻繁項(xiàng)集算法進(jìn)行了大量的研究：于守鍵等[6]利用前綴項(xiàng)集的存儲(chǔ)方式，通過(guò)哈希表快速查找來(lái)提高查找的效率。趙龍等[7]提出Apriori算法中會(huì)出現(xiàn)同一屬性的不同屬性值進(jìn)行連接的情況，通過(guò)比較能提前判斷是否有這種情況發(fā)生，這樣避免重復(fù)連接的同時(shí)，也不需要再和數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行驗(yàn)證對(duì)比，節(jié)約了資源，提高了挖掘效率。屈鑫乙等[8]利用任何一個(gè)頻繁k+1項(xiàng)集均可以表示一個(gè)頻繁k項(xiàng)集與一個(gè)頻繁1項(xiàng)集的交集這一性質(zhì)，產(chǎn)生頻繁項(xiàng)集。該改進(jìn)算法減少了掃描數(shù)據(jù)庫(kù)的次數(shù)并提高了算法的效率。邊根慶等[9]通過(guò)富裕項(xiàng)和事務(wù)權(quán)重，計(jì)算項(xiàng)的權(quán)重支持度，從而得到頻繁項(xiàng)集。

本文提出一種快速挖掘頻繁項(xiàng)集的改進(jìn)Apriori算法。該算法只需對(duì)事物數(shù)據(jù)庫(kù)掃描一次，即可獲得與該數(shù)據(jù)庫(kù)對(duì)應(yīng)的一個(gè)布爾矩陣，從而大量復(fù)雜數(shù)據(jù)的處理變?yōu)閷?duì)0或1的處理，減少系統(tǒng)資源的占用[10]。通過(guò)布爾矩陣的行向量計(jì)算或者列向量計(jì)算兩種方式，實(shí)現(xiàn)快速查找頻繁項(xiàng)集的目的。不管采用行向量計(jì)算還是列向量計(jì)算，在挖掘過(guò)程中都采用盡可能壓縮候選項(xiàng)集，刪除其中的非頻繁K-1項(xiàng)集元素，再產(chǎn)生頻繁k項(xiàng)集的方式，其目的為節(jié)省運(yùn)行時(shí)間，提高產(chǎn)生有效頻繁項(xiàng)集的效率。

1 Apriori算法

設(shè)I={i1,i2,i3,…}是一個(gè)項(xiàng)目集合，事務(wù)數(shù)據(jù)庫(kù)D={t1，t2，t3,…}是一系列事物，由唯一標(biāo)識(shí)TID進(jìn)行區(qū)分。每個(gè)事務(wù)ti(i=1,2,3,…)對(duì)應(yīng)I上的一個(gè)子集。引用文獻(xiàn)[5]中的事物數(shù)據(jù)庫(kù)D，如表1所示。Apriori算法是利用逐層搜索的迭代方法，用k-1項(xiàng)集搜索k項(xiàng)集。搜索前要設(shè)定最小支持度，基本操作為：

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

(1)每個(gè)項(xiàng)都是候選1項(xiàng)集的集合C1，掃描數(shù)據(jù)庫(kù)D，統(tǒng)計(jì)每一個(gè)項(xiàng)發(fā)生的數(shù)目，找出滿足最小支持度的項(xiàng)，生成頻繁1項(xiàng)集，計(jì)作L1；

(2)用L1與自己連接(L1∞L1)來(lái)生成候選2項(xiàng)集的集合C2，掃描數(shù)據(jù)庫(kù)D，統(tǒng)計(jì)每一個(gè)項(xiàng)發(fā)生的數(shù)目，找出滿足最小支持度的項(xiàng)，生成頻繁2項(xiàng)集，計(jì)作L2；

(3)如此下去，直到不能找到頻繁k項(xiàng)集Lk。

Apriori算法中滿足關(guān)聯(lián)規(guī)則挖掘的理論：頻繁項(xiàng)目集的子集仍是頻繁項(xiàng)目集；非頻繁項(xiàng)目集的超集是非頻繁項(xiàng)目集[5]。算法中的Ck是Lk的超集，也就是說(shuō)Ck的成員可以不是頻繁的，但所有的頻繁項(xiàng)集都包含在Ck中，并且任何非頻繁的(k-1)項(xiàng)集都不是頻繁項(xiàng)集的子集。但是Apriori算法存在兩個(gè)主要的缺陷：一方面在剪枝過(guò)程中，需要多次掃描數(shù)據(jù)庫(kù)，需要很大的I/O負(fù)載，候選集Ck中的每個(gè)元素都必須通過(guò)掃描一次數(shù)據(jù)庫(kù)來(lái)驗(yàn)證是否加入Lk；另一方面可能產(chǎn)生龐大的候選集，由Lk-1產(chǎn)生k候選集Ck是呈指數(shù)增長(zhǎng)[6]。

2 Apriori算法的改進(jìn)

2.1 生成數(shù)據(jù)庫(kù)的布爾矩陣

表2 數(shù)據(jù)庫(kù)D對(duì)應(yīng)的布爾向量矩陣

掃描事務(wù)數(shù)據(jù)庫(kù)D，用事務(wù)表示行向量，項(xiàng)集表示列向量，若第i個(gè)事務(wù)中存在第j個(gè)項(xiàng)集，則第i行，第j列所對(duì)應(yīng)的值就為1，否則為0，按照這種方式只需掃描一次數(shù)據(jù)庫(kù)D，就可構(gòu)造出與數(shù)據(jù)庫(kù)相對(duì)應(yīng)的布爾矩陣。根據(jù)表1所示內(nèi)容，構(gòu)造出如表2所示的布爾矩陣。

2.2 改進(jìn)算法的描述

2.2.1 布爾矩陣的行向量算法

設(shè)項(xiàng)目集合中包含的項(xiàng)目數(shù)為m，通過(guò)表2計(jì)算事務(wù)數(shù)據(jù)庫(kù)D中每項(xiàng)事務(wù)包含的項(xiàng)目的個(gè)數(shù)k(k≤m)，統(tǒng)計(jì)所有k值相同項(xiàng)的個(gè)數(shù)N，若N大于等于給定的最小支持?jǐn)?shù)，則k為最大頻繁項(xiàng)目的項(xiàng)目數(shù)，找出所有包含k項(xiàng)的候選項(xiàng)目集。接著分別判斷這些項(xiàng)目集是否為頻繁k項(xiàng)集，若某個(gè)頻繁k項(xiàng)目集是頻繁項(xiàng)目集，那么它的所有非空子集都是頻繁項(xiàng)目集，即可找到所有的頻繁項(xiàng)集。行向量算法流程如圖1所示。

以表1中事務(wù)數(shù)據(jù)庫(kù)D為例，用此方法計(jì)算出事務(wù)數(shù)據(jù)庫(kù)的全部頻繁項(xiàng)集。設(shè)最小支持?jǐn)?shù)為2。由表2可得到每個(gè)事務(wù)中包含的項(xiàng)集的個(gè)數(shù)，如表3所示，最后一列為每項(xiàng)事務(wù)包含的項(xiàng)目的個(gè)數(shù)。

k=2時(shí)，包含的有5項(xiàng)事務(wù)(N=5)大于等于最小支持?jǐn)?shù)，分別是{i2,i3}、{i2,i4}、{i1,i3}，由表4可得{i2,i3}、{i2,i4}、{i1,i3}的支持?jǐn)?shù)大于等于最小支持?jǐn)?shù)。所以頻繁2項(xiàng)集為{i2,i3}、{i2,i4}、{i1,i3}。

k=3時(shí)，包含的有3項(xiàng)事務(wù)(N=3)大于等于最小支持?jǐn)?shù)，分別是{i1,i2,i5}、{i1,i2,i4}、{i1,i2,i3}，同上方法，得{i1,i2,i5}、{i1,i2,i3}兩項(xiàng)的支持?jǐn)?shù)都大于等于最小支持?jǐn)?shù)。所以頻繁3項(xiàng)集為{i1,i2,i5}、{i1,i2,i3}。

等效電容C由開(kāi)口間隙的距離、開(kāi)口的橫截面積以及金屬環(huán)的介電常數(shù)決定，等效電感L則主要與金屬環(huán)的周長(zhǎng)與寬度有關(guān)。隨著開(kāi)口距離d的增大，等效電容隨之減小，同時(shí)金屬環(huán)的長(zhǎng)度減小導(dǎo)致等效電感的減小，最終諧振頻率隨之增加，從而發(fā)生藍(lán)移。圖6（b）為高頻諧振的Q值變化。隨著開(kāi)口距離d的增大，超材料的非輻射損耗隨之減小，高頻處諧振的Q值也進(jìn)一步增大，由8.23增加到8.46再增加到10.32。環(huán)偶極子超材料的低損耗及高Q值有助于制備高效的超材料功能器件。

k=4時(shí)，包含的有1項(xiàng)事務(wù)(N=1)小于給定的最小支持?jǐn)?shù)，所以事務(wù)數(shù)據(jù)庫(kù)D中不包含項(xiàng)目數(shù)為4的項(xiàng)。

根據(jù)項(xiàng)目集是頻繁項(xiàng)集，則它的所有非空子集都是頻繁項(xiàng)目集的性質(zhì)。所有頻繁3項(xiàng)集、頻繁2項(xiàng)集及它們的子集都是頻繁項(xiàng)集。所以事務(wù)數(shù)據(jù)庫(kù)D的頻繁項(xiàng)集為{{i1}，{i2}，{i3}，{i4}，{i5}，{i1,i2}，{i1,i3}，{i1,i5}，{i2,i3}，{i2,i4}，{i2,i5}，{i1,i2,i3}，{i1,i2,i5}}。

表3 每項(xiàng)事務(wù)包含項(xiàng)集的個(gè)數(shù)

表4 候選項(xiàng)集的支持?jǐn)?shù)

2.2.2 布爾矩陣的列向量算法

通過(guò)表2可以計(jì)算出項(xiàng)目集合I中的每個(gè)項(xiàng)出現(xiàn)的次數(shù)(即“1”的個(gè)數(shù))，若大于等于給定最小支持度，則該項(xiàng)就屬于頻繁1項(xiàng)集。將頻繁1項(xiàng)集中的任意兩項(xiàng)進(jìn)行“與”運(yùn)算，所得的結(jié)果中若“1”的個(gè)數(shù)大于等于給定最小支持度，則這兩項(xiàng)的組合就屬于頻繁2項(xiàng)集。以此類推，要求頻繁k項(xiàng)集時(shí)，從已知的頻繁k-1項(xiàng)集中任取2個(gè)符合條件的項(xiàng)進(jìn)行連接，將連接后的項(xiàng)集中的各項(xiàng)進(jìn)行“與”運(yùn)算，其結(jié)果如果大于等于最小支持度，則該項(xiàng)即屬于頻繁k項(xiàng)集。列向量算法流程如圖2所示。

圖1 行向量算法流程圖 圖2 列向量算法流程圖

以表1中事務(wù)數(shù)據(jù)庫(kù)D為例，用此方法計(jì)算出事務(wù)數(shù)據(jù)庫(kù)的全部頻繁項(xiàng)集。設(shè)定最小支持度為2。

由表2可得：i1=(100110111)，i2=(111101011)，i3=(001011111)，i4=(010100000)，i5=(100000010)，i1，i2，i3，i4，i5中“1”的個(gè)數(shù)分別為6,7,6,2,2，大于等于最小支持度，所以頻繁1項(xiàng)集L1={{i1}，{i2}，{i3}，{i4}，{i5}}。

從頻繁2項(xiàng)集L2中選擇開(kāi)始項(xiàng)相同的兩個(gè)項(xiàng)集，如{i1,i2}、{i1,i3}，首先判斷{i1,i2,i3}是否可能是頻繁3項(xiàng)集，根據(jù)關(guān)聯(lián)規(guī)則挖掘的理論：頻繁項(xiàng)集的子集仍是頻繁項(xiàng)集，即{i1,i2}、{i1,i3}、{i2,i3}都應(yīng)存在于頻繁2項(xiàng)集中。若滿足該條件，則將i1∧i2∧i3運(yùn)算所得的結(jié)果(000000011)與最小支持度進(jìn)行比較，由于結(jié)果滿足最小支持度的要求，{i1,i2,i3}屬于頻繁3項(xiàng)集L3。同理，{i1,i2,i5}滿足要求，所以L3={{i1,i2,i3}，{i1,i2,i5}}。

從頻繁3項(xiàng)集L3中選擇開(kāi)始項(xiàng)相同的兩個(gè)項(xiàng)集為{i1,i2,i3,i5}，根據(jù)Apriori算法的性質(zhì)，若{i1,i2,i3,i5}為頻繁項(xiàng)集，則它的任意子集也應(yīng)該是頻繁子集，但是子集{i3,i5}不是頻繁子集，所以{i1,i2,i3,i5}不是頻繁4項(xiàng)集，也就是說(shuō)頻繁4項(xiàng)集L4為空集。

綜上所示，該數(shù)據(jù)庫(kù)事務(wù)D的頻繁項(xiàng)集為{{i1}，{i2}，{i3}，{i4}，{i5}，{i1,i2}，{i1,i3}，{i1,i5}，{i2,i3}，{i2,i4}，{i2，i5}，{i1,i2,i3}，{i1,i2,i5}}。

2.2.3 算法性能分析

為了測(cè)試Apriori改進(jìn)算法的性能，選取測(cè)試數(shù)據(jù)集Mushroom(事務(wù)數(shù)8124，每個(gè)事務(wù)有23項(xiàng))作為實(shí)驗(yàn)數(shù)據(jù)，通過(guò)MATLAB平臺(tái)進(jìn)行算法性能測(cè)試。運(yùn)行結(jié)果如圖3、圖4所示。圖3所示中設(shè)定相同的事務(wù)數(shù)，在最小支持度不同的情況下，挖掘頻繁項(xiàng)集所花費(fèi)的時(shí)間的比較；圖4中采用相同的支持度，在事務(wù)數(shù)不同的情況下，挖掘頻繁項(xiàng)集所用的時(shí)間比較。通過(guò)實(shí)驗(yàn)證明，由于改進(jìn)后的算法只需對(duì)數(shù)據(jù)庫(kù)進(jìn)行一次掃描，并且采用行向量或列向量挖掘過(guò)程中通過(guò)盡量壓縮頻繁k-1項(xiàng)集，提高頻繁k項(xiàng)集的挖掘效率，提高運(yùn)行速度。同時(shí)數(shù)據(jù)集Mushroom中的數(shù)據(jù)相關(guān)性較強(qiáng)，改進(jìn)的Apriori算法也能較好地進(jìn)行頻繁項(xiàng)集的挖掘，完全優(yōu)于原有的Apriori算法。

圖3 不同支持度下Apriori算法與改進(jìn)算法性能比較 圖4 不同事務(wù)數(shù)下Apriori算法與改進(jìn)算法性能比較

3 結(jié)束語(yǔ)

本文提出了基于布爾矩陣的行向量和列向量?jī)煞N方式的改進(jìn)Apriori算法，該算法掃描一次數(shù)據(jù)庫(kù)后，將數(shù)據(jù)庫(kù)轉(zhuǎn)化為布爾矩陣，不但節(jié)省了大量?jī)?nèi)存，而且避免了傳統(tǒng)算法總多次掃描數(shù)據(jù)庫(kù)的缺陷；同時(shí)在通過(guò)行向量和列向量方式生產(chǎn)頻繁k項(xiàng)集前，對(duì)頻繁k-1項(xiàng)集進(jìn)行壓縮，盡可能刪除非頻繁k-1項(xiàng)集。改進(jìn)算法意在解決原Apriori算法中的兩個(gè)主要問(wèn)題，大大節(jié)省挖掘頻繁項(xiàng)集的時(shí)間，提高了算法的效率。數(shù)據(jù)挖掘面向的是大量的數(shù)據(jù)，本文只是以測(cè)試數(shù)據(jù)為例，提出了詳細(xì)的頻繁項(xiàng)集的生成過(guò)程。在實(shí)際應(yīng)用的過(guò)程中，可以參考此方法完成對(duì)大量數(shù)據(jù)的挖掘，這也是下一步的工作之一。