顧軍華，蘇 鳴，張亞娟，張丹紅

1.河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院，天津300401

2.河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，天津300401

1 引言

頻繁項(xiàng)集挖掘是數(shù)據(jù)挖掘領(lǐng)域中重要的研究方向之一，其最初的用途是分析超市購(gòu)物籃[1]，通過(guò)交易數(shù)據(jù)，來(lái)獲得顧客對(duì)不同商品的購(gòu)買(mǎi)習(xí)慣，幫助商家制定銷(xiāo)售策略。在過(guò)去20 年中，頻繁項(xiàng)集挖掘一直是數(shù)據(jù)挖掘領(lǐng)域的熱門(mén)研究課題，且廣泛應(yīng)用于氣象關(guān)聯(lián)分析、銀行金融客戶交叉銷(xiāo)售分析[2]和電子商務(wù)搭配營(yíng)銷(xiāo)等[3]領(lǐng)域。

頻繁項(xiàng)集挖掘的經(jīng)典算法Apriori算法是由Agrawal等人[4]于1994年提出的。該算法基于先驗(yàn)原理，簡(jiǎn)單易懂，但效率低下，面對(duì)數(shù)據(jù)庫(kù)中的巨量數(shù)據(jù)，由于其算法存在產(chǎn)生大量候選項(xiàng)集，以及需要重復(fù)多次掃描數(shù)據(jù)庫(kù)的問(wèn)題，會(huì)對(duì)內(nèi)存產(chǎn)生巨大的負(fù)載。對(duì)此，提出了一系列的改進(jìn)算法。2000年，Han等人[5]提出基于FP-tree的FP-growth算法，該算法以FP-tree作為數(shù)據(jù)結(jié)構(gòu)，在挖掘過(guò)程中只需要掃描兩次數(shù)據(jù)庫(kù)，并且不生成候選項(xiàng)集，相比于Apriori 算法的挖掘效率有很大的提升。基于FP-growth 算法思想，近年來(lái)提出了很多改進(jìn)算法。2012年，Deng等人[6]提出了PrePost算法，該算法通過(guò)對(duì)FP-tree進(jìn)行前序和后序的兩次遍歷，得到每個(gè)節(jié)點(diǎn)的前序序列pre-order 和后序序列post-order，并據(jù)此構(gòu)建前序后序編碼樹(shù)（Pre-order and Post-order Code tree，PPC-tree），得到1-項(xiàng)集的節(jié)點(diǎn)列表（N-list）。通過(guò)迭代連接兩個(gè)頻繁的（k-1）-項(xiàng)集的N-list，可以得到所有的頻繁k-項(xiàng)集。2014年，Deng等人[7]提出一種基于Nodeset[8]數(shù)據(jù)結(jié)構(gòu)的FIN 算法，該算法與PrePost 算法的不同之處在于，構(gòu)建Nodeset中的節(jié)點(diǎn)僅需要FP-tree的前序遍歷順序，并且在挖掘過(guò)程中還使用了對(duì)搜索樹(shù)進(jìn)行優(yōu)化的超集等價(jià)剪枝策略，進(jìn)一步精簡(jiǎn)了挖掘空間，增加了挖掘效率。與Nodeset 相比，2016 年，Deng 等人[9]提出的DFIN 算法構(gòu)建的DiffNodeset 中，每個(gè)k-項(xiàng)集(k≥3)的DiffNodeset由兩個(gè)（k-1）-項(xiàng)集的DiffNodeset之間的差異性生成。由于DiffNodeset 的規(guī)模要小于Nodeset，所以DFIN 算法的挖掘效率要優(yōu)于FIN 算法。2018 年，Biu等人[10]提出了NFWI算法，該算法采用基于N-list改進(jìn)的WN-list 作為數(shù)據(jù)結(jié)構(gòu)，用于挖掘加權(quán)頻繁項(xiàng)集，挖掘效率要高于PrePost 算法；但由于仍需要根據(jù)前序和后序編碼進(jìn)行大量交集運(yùn)算，僅適用于大型稀疏數(shù)據(jù)集。

FIN 算法的缺點(diǎn)是在對(duì)兩個(gè)Nodesets 進(jìn)行連接時(shí)，需要對(duì)編碼樹(shù)（POC-tree）進(jìn)行多次遍歷，并且需要判斷兩個(gè)不同的Nodeset 能否滿足連接條件，這會(huì)消耗大量時(shí)間。而盡管DiffNodeset 相比于Nodeset 具有優(yōu)勢(shì)，但對(duì)于稠密數(shù)據(jù)集，計(jì)算兩個(gè)DiffNodeset 之間的差異仍需要較長(zhǎng)時(shí)間；并且由于使用了差集策略[11]，也會(huì)占用較大的內(nèi)存空間。針對(duì)這些問(wèn)題，提出基于新的數(shù)據(jù)結(jié)構(gòu)位編碼鏈表（Bitmap-code List，BC-List）的頻繁項(xiàng)集挖掘算法（BC-List Frequent Itemsets Mining，BCLFIM），BC-List中的每個(gè)節(jié)點(diǎn)均采用編碼模型—基于集合的位圖來(lái)表示。通過(guò)這種數(shù)據(jù)結(jié)構(gòu)，在連接頻繁（k-1）-項(xiàng)集以得到頻繁k-項(xiàng)集的過(guò)程中，可以按位運(yùn)算，避免了大量交集運(yùn)算。此外，該算法還使用集合枚舉樹(shù)來(lái)代表搜索空間，并且使用超集等價(jià)和支持度計(jì)數(shù)剪枝策略來(lái)對(duì)集合枚舉樹(shù)進(jìn)行剪枝處理，減少了空間占用，提高了頻繁項(xiàng)集的挖掘效率。

2 問(wèn)題定義

2.1 基本概念

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

定義2（頻繁項(xiàng)集）若項(xiàng)集A的支持度大于最小支持度minSup(∈[0，1]），即support(A)≥minSup，則稱A是頻繁項(xiàng)集；如果A的長(zhǎng)度為k，則稱A為頻繁k-項(xiàng)集。

根據(jù)定義1 可以計(jì)算表1 所示的事務(wù)數(shù)據(jù)庫(kù)DB 中的1-項(xiàng)集的支持度計(jì)數(shù)，如表2 所示。設(shè)minSup為0.4，則由定義2 可得頻繁1-項(xiàng)集為{a},,{c},syggg00,{e}。將每個(gè)事務(wù)中非頻繁項(xiàng)刪除，然后按支持度計(jì)數(shù)將事務(wù)按非升序排列，如表1所示。

表2 1-項(xiàng)集及其支持度計(jì)數(shù)

2.2 構(gòu)建BC-tree

圖1 表2中頻繁項(xiàng)的索引

定義6（Bitmap-Code（BC）項(xiàng)集位圖代碼）設(shè)存在任意一個(gè)項(xiàng)集P，項(xiàng)集P可以用大小為nf的位圖代碼BC(P)=bnf-1…b1b0來(lái)表示。項(xiàng)索引L1中的第j個(gè)項(xiàng)與位圖中的bj相對(duì)應(yīng)；若項(xiàng)i(i∈L1)是P中的成員，那么位圖中根據(jù)定義5的項(xiàng)索引，相對(duì)應(yīng)的位置為1，否則置為0。例如，根據(jù)表2得到的位圖如圖2所示。

圖2 表2中每個(gè)頻繁項(xiàng)所分配的位

對(duì)于表2 中的1-頻繁項(xiàng)集，其位圖為BC()=01000，如圖3所示。

圖3 頻繁1-項(xiàng)集的位圖

輸入：事務(wù)數(shù)據(jù)庫(kù)DB，最小支持度minSup。

輸出：BC-tree，頻繁1-項(xiàng)集L1。

1.掃描事務(wù)數(shù)據(jù)庫(kù)DB，找到頻繁1-項(xiàng)集F1；

2.根據(jù)定義3 將F1中的項(xiàng)根據(jù)各項(xiàng)支持度按非降序排序；

3.創(chuàng)建BC-tree的根節(jié)點(diǎn)Tr，并執(zhí)行以下初始化任務(wù)：

圖4 根據(jù)表1的事務(wù)數(shù)據(jù)庫(kù)構(gòu)建的BC-tree

2.3 構(gòu)建BC-List

根據(jù)BC-tree，可以得到頻繁1-項(xiàng)集。在定義BCList之前，首先給出BC-List中節(jié)點(diǎn)信息BC-N-info的定義。

定義8（BC-N-info）設(shè)N是BC-tree中的一個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)N的BC-N-info，由節(jié)點(diǎn)的bitmap-code 和count 組成，即（N.bitmap-code，N.count）。

定義9（BC-List（頻繁1-項(xiàng)集））給定一個(gè)BC-tree，頻繁1-項(xiàng)集的BC-List是在BC-tree中所有節(jié)點(diǎn)的BC-N-info的集合，按BC-N-info.bitmap升序排序。項(xiàng)集{a}的BC-List，BCL（{a}）={（10 000，4）}。得到的頻繁1-項(xiàng)集的BC-List如圖5所示。

圖5 根據(jù)圖4生成的頻繁1-項(xiàng)集的BC-List

圖6 頻繁1-項(xiàng)集的BC-List連接

3 基于BC-List的BCLFIM算法

BCLFIM算法在挖掘頻繁項(xiàng)集的過(guò)程中，通過(guò)掃描BC-List，連接兩個(gè)滿足最小支持度條件的頻繁（k-1）-項(xiàng)集來(lái)發(fā)現(xiàn)頻繁k-項(xiàng)集，以生成新的BC-List，并得到頻繁k-項(xiàng)集的支持度。為了避免重復(fù)連接的問(wèn)題，BCLFIM算法使用了集合枚舉樹(shù)來(lái)代表搜索空間。在搜索過(guò)程中，使用了超集等價(jià)策略和提前停止交集策略來(lái)對(duì)搜索空間進(jìn)行剪枝操作，進(jìn)一步縮小了算法的時(shí)間復(fù)雜度，提高了挖掘頻繁項(xiàng)集的速度。

3.1 剪枝策略

BCLFIM 算法使用集合枚舉樹(shù)[12]來(lái)代表搜索空間，利用集合枚舉樹(shù)的特性來(lái)避免在挖掘頻繁k-項(xiàng)集時(shí)出現(xiàn)重復(fù)連接的問(wèn)題。在根據(jù)集合枚舉樹(shù)構(gòu)建BC-List的過(guò)程中，為了提高挖掘頻繁項(xiàng)集的速度，還對(duì)搜索空間使用了超集等價(jià)策略[13]和支持度計(jì)數(shù)剪枝策略[14]來(lái)進(jìn)行剪枝操作。

3.1.1 集合枚舉樹(shù)

輸入：節(jié)點(diǎn)N，N的父節(jié)點(diǎn)生成的頻繁項(xiàng)集BCLparent。

輸出：頻繁k-項(xiàng)集BCLN。

圖8 根據(jù)表2構(gòu)建的集合枚舉樹(shù)

3.2 BCLFIM算法描述

BCLFIM 算法可分為以下幾個(gè)步驟：（1）掃描事務(wù)數(shù)據(jù)庫(kù)DB，將每個(gè)事務(wù)的項(xiàng)集按支持度以非升序排序，得到頻繁1-項(xiàng)集F1，構(gòu)建頻繁1-項(xiàng)集F1對(duì)應(yīng)的BC-tree。（2）通過(guò)掃描BC-tree，得到頻繁1-項(xiàng)集F1對(duì)應(yīng)的BC-List。（3）根據(jù)算法2，在集合枚舉樹(shù)所代表的搜索

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

為了避免其他客觀因素帶來(lái)的性能差異，將3 種用Java 語(yǔ)言編寫(xiě)的算法[17]在同一臺(tái)內(nèi)存為8 GB，CPU為Intel?Core ?i5-2430M@2.40 GHz，操 作 系 統(tǒng) 為Windows 10專業(yè)版的PC上運(yùn)行，以保證實(shí)驗(yàn)結(jié)果是公平有效的，如表3所示。

表3 實(shí)驗(yàn)使用數(shù)據(jù)集及其特征

給定相同的最小支持度與相同的數(shù)據(jù)集，發(fā)現(xiàn)通過(guò)BCLFIM 算法挖掘得到的頻繁項(xiàng)集與FIN 算法和DFIN算法挖掘得到的頻繁項(xiàng)集相同，證明了BCLFIM算法所挖掘的頻繁項(xiàng)集的正確性，如表4所示。

表4 mushroom數(shù)據(jù)集下頻繁項(xiàng)集數(shù)量

4.2 實(shí)驗(yàn)分析

3 種算法在如表3 所示的3 個(gè)不同數(shù)據(jù)集下運(yùn)行時(shí)間對(duì)比，如圖9 所示。在稠密數(shù)據(jù)集pumsb 和accidents中，BCLFIM 算法相比于FIN 算法有明顯的效率提升，相比于DFIN算法運(yùn)行時(shí)間也相對(duì)縮短。在稀疏數(shù)據(jù)集mushroom 中，由于數(shù)據(jù)集規(guī)模較小，結(jié)果區(qū)分并不明顯。但也可看出BCLFIM 算法比其他兩種算法的運(yùn)行速度也相對(duì)更快，表明BCLFIM算法在不同的數(shù)據(jù)集上均具有較高的時(shí)間效率。

圖9 不同數(shù)據(jù)集上3種算法運(yùn)行時(shí)間對(duì)比

圖10 是3 種算法在3 個(gè)不同數(shù)據(jù)集下的內(nèi)存占用對(duì)比。由圖10（a）和（b）可以看出，雖然在數(shù)據(jù)集較大時(shí)，BCLFIM 算法的內(nèi)存占用要大于FIN 算法，但是始終小于DFIN 算法。圖10（c）表現(xiàn)在mushrooms 數(shù)據(jù)集上的3 種算法內(nèi)存占用情況，由于數(shù)據(jù)集稀疏，挖掘過(guò)程中消耗內(nèi)存較少，所以3種算法的內(nèi)存占用變化不明顯，但可以看出BCLFIM算法的內(nèi)存占用相對(duì)較小。綜合來(lái)看，BCLFIM算法也有較高的空間效率。

圖10 不同數(shù)據(jù)集上3種算法內(nèi)存占用對(duì)比

實(shí)驗(yàn)表明，本文提出的BCLFIM算法對(duì)稠密數(shù)據(jù)集和稀疏數(shù)據(jù)集同樣適用。相比于FIN算法，由于使用了新的數(shù)據(jù)結(jié)構(gòu)BC-tree，無(wú)需對(duì)樹(shù)進(jìn)行多次遍歷，就可以得到節(jié)點(diǎn)信息列表BC-List，通過(guò)BC-List就可以得到兩個(gè)節(jié)點(diǎn)之間的祖先-后代關(guān)系，大大減少了生成頻繁k-項(xiàng)集的時(shí)間。相比于DFIN 算法，BCLFIM 算法的連接過(guò)程更加簡(jiǎn)單，項(xiàng)集支持度的計(jì)算也更加便捷。除此以外，BCLFIM算法還使用了超集等價(jià)和支持度計(jì)數(shù)剪枝策略來(lái)對(duì)頻繁k-項(xiàng)集的生成進(jìn)行優(yōu)化，在內(nèi)存占用較小的情況下，加快了挖掘頻繁項(xiàng)集的速度，提升了挖掘效率。

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

本文提出的BCLFIM算法，使用基于位圖編碼表示的節(jié)點(diǎn)編碼模型生成位圖樹(shù)（BC-tree），以BC-tree 的節(jié)點(diǎn)信息作為數(shù)據(jù)結(jié)構(gòu)，通過(guò)按位運(yùn)算來(lái)快速獲取BCList的節(jié)點(diǎn)集合，并通過(guò)兩種剪枝策略來(lái)縮小挖掘頻繁模式的搜索空間，解決了FIN算法由于存在建樹(shù)過(guò)程復(fù)雜及支持度計(jì)算繁瑣而導(dǎo)致的挖掘效率較低的問(wèn)題。通過(guò)實(shí)驗(yàn)對(duì)比FIN 算法與DFIN 算法，證明了本文提出的算法在內(nèi)存占用與運(yùn)行時(shí)間上表現(xiàn)更好，具有較高的挖掘效率。

在接下來(lái)的研究中，將結(jié)合分布式計(jì)算理論，對(duì)該算法進(jìn)行進(jìn)一步優(yōu)化，以應(yīng)對(duì)當(dāng)前大數(shù)據(jù)時(shí)代背景下的海量數(shù)據(jù)。除此以外，擬將該算法應(yīng)用于氣象領(lǐng)域，嘗試挖掘空氣質(zhì)量要素與氣象要素之間的關(guān)聯(lián)性，充分發(fā)揮算法的應(yīng)用價(jià)值。