汪 浩， 吳 靜

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

0 引言

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

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

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

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

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

2 基于布爾矩陣的Apriori算法

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

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

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

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

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

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

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

3 PMApriori算法

3.1 主要性質(zhì)

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

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

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

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

3.2 基本步驟

基本步驟如下：

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

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

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

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

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

3.3 示例說(shuō)明

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

圖3 PMApriori算法流程示例

3.4 性能分析

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

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

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

4 結(jié)語(yǔ)

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

[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版.合肥:中國(guó)科學(xué)技術(shù)大學(xué)出版社,2008:160-163.

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

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

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

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

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

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