利用數(shù)據(jù)變換與并行運(yùn)算的閉頻繁項(xiàng)集挖掘方法*

黨紅恩，　趙爾平，　劉　煒，　雒偉群

(西藏民族大學(xué) 信息工程學(xué)院，陜西 咸陽 712082)

海量信息的爆發(fā)式增長已成為當(dāng)今世界最主要的特點(diǎn).在這些形式各異、容量極大的數(shù)據(jù)中，如何準(zhǔn)確提取關(guān)鍵信息，幫助各類決策者了解、掌握瞬息變換的客觀世界，是非常重要的[1].信息技術(shù)和硬件技術(shù)的快速進(jìn)步，已經(jīng)使得用戶生產(chǎn)并處理海量的事務(wù)數(shù)據(jù)(即大數(shù)據(jù))成為可能，大數(shù)據(jù)處理的核心就是數(shù)據(jù)挖掘技術(shù)[2].然而，在物理世界中不斷涌現(xiàn)的閉頻繁項(xiàng)集(closed frequent itemset, CFI)加大了大數(shù)據(jù)挖掘的難度，降低了數(shù)據(jù)挖掘結(jié)果的實(shí)時性和可靠性.

閉頻繁項(xiàng)集的概念最早見于文獻(xiàn)[3]，此后出現(xiàn)了大量的閉頻繁項(xiàng)集挖掘算法[4-7].在處理小數(shù)據(jù)集或高支持閾值的CFI挖掘問題時，現(xiàn)有的方法表現(xiàn)出了良好的性能.這些算法通過將搜索空間限制在閉頻繁項(xiàng)集而不是整個集合的冪集，將尋找頻繁項(xiàng)集簡化為挖掘閉頻繁項(xiàng)集.但是，當(dāng)數(shù)據(jù)集范圍增大或支持度閾值變低時，內(nèi)存占用和通信成本的急劇增大使得現(xiàn)有方法的可行性和運(yùn)行速率變低.一些研究試圖通過并列運(yùn)行的方式加快CFI挖掘算法的速度，但卻產(chǎn)生了一些如數(shù)據(jù)劃分和通信成本最小化等問題，需要進(jìn)一步改進(jìn).然而，不可否認(rèn)的是，并行方案確實(shí)是一種解決CFI大規(guī)模挖掘的行之有效的方法.目前，針對閉頻繁項(xiàng)集并行挖掘算法的研究相對較少.[8]基于MapReduce平臺的CFI，提出一種基于貪婪策略的CFI并行平衡挖掘算法，并通過實(shí)驗(yàn)證明了所提算法在大規(guī)模CFI挖掘中的可靠性和快速性.[9]提出了一種充分利用頻繁模式增長算法固有并行特征的多處理器順序展開結(jié)構(gòu)，實(shí)驗(yàn)結(jié)果表明提出的結(jié)構(gòu)可以大幅度提高運(yùn)算速度.[10]提出一種運(yùn)行于多核處理器上的SAT并行算法，通過路徑指引來分解枚舉過程，大大提高了CFI挖掘的動態(tài)性能.

為充分利用并行框架Spark在計(jì)算和存儲等方面的優(yōu)勢，本文提出一種基于數(shù)據(jù)變換與并行運(yùn)算(data transformation and parallel computing, DTPC)的CFI挖掘方法：利用平方和開方運(yùn)算將數(shù)據(jù)集的項(xiàng)轉(zhuǎn)化為質(zhì)數(shù)，進(jìn)而成頻繁項(xiàng)集.利用3 000萬篇文章組成的大數(shù)據(jù)集進(jìn)行了相關(guān)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明本文算法在可靠性、準(zhǔn)確性和動態(tài)響應(yīng)速度等方面大大優(yōu)于現(xiàn)有的算法.

1　DTPC算法

本文提出的DTPC閉頻繁項(xiàng)集挖掘方法包括兩個步驟：第一步，進(jìn)行數(shù)據(jù)轉(zhuǎn)換，生成頻繁項(xiàng)列表，并在Spark中進(jìn)行降序排列；第二步，在Spark中挖掘閉頻繁項(xiàng)集.在介紹本文具體算法之前，先對閉頻繁項(xiàng)集的一些相關(guān)概念進(jìn)行簡單的介紹.

定義1提取上下文：指一個三元組κ=(O,I,R)，式中O表示對象的有限集合，I為項(xiàng)的有限集合，R為二元(關(guān)聯(lián))關(guān)系(即R?O×I)，每對(o,i)∈R表示對象o∈O包含項(xiàng)i∈I.

定義2閉項(xiàng)集：項(xiàng)i∈Ι是閉環(huán)的，當(dāng)且僅當(dāng)I″=I；S(I)代表i的支持，其值等于κ中包含i的項(xiàng)數(shù)；如果S(i)比S(I)的最小值大，則認(rèn)為i是頻繁的.

定義2中，(″)表示閉包算子，由ψ:P(i)→P(O)s.t.ψ(i)={o∈O|?i∈I,(o,i)∈R}和φ:P(O)→P(i)s.t.φ(O)={i∈I|?o∈O,(o,i)∈R}共同定義.閉包算子將項(xiàng)的冪集分割成了互不相連的子集.

我們提出一種數(shù)據(jù)轉(zhuǎn)換方法來生成頻繁項(xiàng)列表，同時使用Spark[11]依據(jù)項(xiàng)支持的降序分類該列表.

定義3質(zhì)數(shù)：一個整數(shù)Z>1是質(zhì)數(shù)，當(dāng)且僅當(dāng)其僅能被自身和1整除.

在定義3和定義4的基礎(chǔ)上，給出一種新型的數(shù)據(jù)變換方法(定義5)，用來將輸入數(shù)據(jù)變換為頻繁項(xiàng)集.

定義5事務(wù)轉(zhuǎn)換：假設(shè)T={ij,…,ik}為事務(wù)，項(xiàng)ir∈T，通過將質(zhì)數(shù)pr分配給每個項(xiàng)ir，并用方程

(1)

進(jìn)行計(jì)算，可以完成數(shù)據(jù)轉(zhuǎn)換過程，得到事務(wù)轉(zhuǎn)換后的新數(shù)值VT.

表1數(shù)據(jù)變換示例

Tab.1Exampleofdatatransformation

表1給出了數(shù)據(jù)轉(zhuǎn)換的示例，其中：表1(a)為提取上下文κ；表1(b)為κ中按照降序分類的項(xiàng)，以及這些項(xiàng)的質(zhì)數(shù)和支持；表1(c)為上下文κ經(jīng)數(shù)據(jù)轉(zhuǎn)換后得到的結(jié)果.完成數(shù)據(jù)轉(zhuǎn)換后，需要在Spark中提取閉頻繁項(xiàng)集的完整集合，從而建立完整的DTPC閉頻繁項(xiàng)集挖掘方法.

定義6條件上下文：給定提取上下文[12]κ，令i為κ中的頻繁項(xiàng)，當(dāng)省略了所有頻繁項(xiàng)、項(xiàng)i和跟隨i之后的項(xiàng)時，i的條件上下文定義為包含i的轉(zhuǎn)換子集.令j為頻繁項(xiàng)X的條件上下文中的一個頻繁項(xiàng)，當(dāng)省略了所有頻繁項(xiàng)、項(xiàng)j和跟隨j之后的項(xiàng)時，jX條件上下文定義為包含j的、X的條件上下文中的轉(zhuǎn)換子集.

將頻繁項(xiàng)按支持度的大小進(jìn)行降序分類，對于每個i，DTPC只包含i的數(shù)據(jù)轉(zhuǎn)換中的條件上下文.為了加快對這些子上下文的搜索，本文定義了與每個上下文關(guān)聯(lián)的指示表，該表列舉了按項(xiàng)支持度降序分裂的，包含在其相應(yīng)條件上下文中的項(xiàng).在本文算法中，提取閉頻繁項(xiàng)集不需要使用此表.本文研究的項(xiàng)集X具有以下特征：(1) 從上下文中提取的閉項(xiàng)集X，是通過連接與X同樣頻繁的項(xiàng)發(fā)現(xiàn)的.(2) 無需設(shè)計(jì)包含在閉頻繁項(xiàng)集的項(xiàng)集Y的條件上下文，來使S(X) =S(Y).

定理1(最大公約數(shù)閉包)令X條件上下文為包含X的轉(zhuǎn)換集，X條件上下文中的最大公約數(shù)所有事務(wù)的閉包.

將項(xiàng)及其事務(wù)轉(zhuǎn)換為質(zhì)數(shù)后，通過計(jì)算條件上下文的所有事務(wù)的最大公約數(shù)，可以很簡單地計(jì)算出閉包，而且這并不需要存儲條件上下文包含的項(xiàng)的支持度.通過將閉包與連接候選項(xiàng)進(jìn)行連接(即將該候選項(xiàng)的質(zhì)數(shù)與閉包的數(shù)值相乘)，即可得到閉頻繁項(xiàng)集.本文將該閉頻繁項(xiàng)集表示為一個數(shù)，并將該數(shù)添加到最終得到的集合中.

綜上，可得DTPC算法的具體步驟：(1) 對輸入數(shù)據(jù)進(jìn)行基于質(zhì)數(shù)平方/開方的數(shù)據(jù)轉(zhuǎn)化預(yù)處理；(2) 并行挖掘閉頻繁項(xiàng)集，即利用并行最大公約數(shù)方法挖掘局部閉頻繁項(xiàng)集；(3) 獲取輸出結(jié)果，即閉頻繁項(xiàng)集.基于以上三步，即可以正確、快速地挖掘出閉頻繁項(xiàng)集的完整集合.事實(shí)上，在預(yù)處理階段后，DTPC已經(jīng)開始基于Spark計(jì)算項(xiàng)的支持度，并將項(xiàng)按照支持度降序進(jìn)行，得到相應(yīng)的列表.在正式開始挖掘閉頻繁項(xiàng)集時，DTPC算法使用第二個Spark,通過將上下文分割為一個新的數(shù)據(jù)集，并將其作為輸入數(shù)據(jù)的條件上下文.此時，DTPC算法通過應(yīng)用新的閉包操作，計(jì)算條件上下文之間所有事務(wù)的最大公約數(shù)，進(jìn)而提取并獲取閉環(huán).

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

為了驗(yàn)證提出的DTPC算法的有效性，本文在兩個數(shù)據(jù)集上進(jìn)行測試.第一個數(shù)據(jù)集為“Google Article”，表示將Google轉(zhuǎn)換為事務(wù)數(shù)據(jù)集的轉(zhuǎn)換集合，每一行為一篇文章.Google Article包含5 352 741個事務(wù)，合計(jì)4 305 928個不同的項(xiàng)目.在這些事務(wù)中，事務(wù)的最大長度為102 394，整個數(shù)據(jù)集的尺寸為3.2 GB.第二個數(shù)據(jù)集為“Clue Web”，包含10種語言、約10億種網(wǎng)頁，收集于2017年1月，該數(shù)據(jù)集包含43 783 550個事務(wù)、9 802 501個項(xiàng)，這些事務(wù)的最大長度為403 521，整個“Clue Web”的尺寸為19.5 GB.

采用高性能消息傳遞庫OpenMPI[13]作為實(shí)驗(yàn)平臺，選取15個節(jié)點(diǎn)的聚類進(jìn)行實(shí)驗(yàn)：將一個節(jié)點(diǎn)選為主節(jié)點(diǎn)，負(fù)責(zé)在不同節(jié)點(diǎn)之間調(diào)度執(zhí)行任務(wù)；將其他節(jié)點(diǎn)設(shè)置為從節(jié)點(diǎn)，負(fù)責(zé)并行計(jì)算.

為驗(yàn)證該算法的優(yōu)越性，將DTPC算法與[14]和[15]中的算法進(jìn)行比較，結(jié)果如圖1所示.

圖1(a)為最小支持度值小于數(shù)據(jù)庫整體規(guī)模3%時，三種算法在“Google Article”上測試的實(shí)驗(yàn)結(jié)果.由實(shí)驗(yàn)結(jié)果可知，提出的DTPC算法明顯優(yōu)于其他算法.這是因?yàn)椤癎oogle Article”包含數(shù)量眾多的項(xiàng)，項(xiàng)數(shù)幾乎等于事物數(shù).當(dāng)最小支持度的值足夠低時，文獻(xiàn)[14]、[15]中的兩種算法都會生成許多的候選者和條件上下文.因此，在這兩種算法中所使用的方法非常復(fù)雜，進(jìn)而導(dǎo)致挖掘性能變差.DTPC算法基于質(zhì)數(shù)，通過簡單的平方/開方運(yùn)算即可生成條件上下文，因而計(jì)算起來非常簡便.此外，每個條件上下文中的最大公約數(shù)消除了候選者和其閉包之間的支持度檢驗(yàn)，從而省略了閉包頻率的計(jì)算.

圖1(b)為在“Clue Web”上的實(shí)驗(yàn)結(jié)果，通過減少最小支持度值，閉頻繁項(xiàng)數(shù)變化并不明顯；匹配候選者事務(wù)的數(shù)量卻快速增加，這樣會導(dǎo)致項(xiàng)集的候選者生成較大的條件上下文.然而，在這種情況下，本文提出的DTPC算法仍能獲得較好的計(jì)算性能，這是因?yàn)楸疚牡乃惴ū苊饬藦拿總€條件上下文中產(chǎn)生閉包的冗余計(jì)算，而文獻(xiàn)[14]、[15]中的兩種算法則不具備這種能力.

[1]趙海燕, 王向前, 馬藝. 量子密碼學(xué)結(jié)合Grover搜索的大數(shù)據(jù)安全認(rèn)證方案[J]. 湘潭大學(xué)自然科學(xué)學(xué)報, 2016, 38(4): 76-79.

[2]史玉珍, 呂瓊帥. 基于進(jìn)化模糊規(guī)則的Web新聞文本挖掘與分類方法[J]. 湘潭大學(xué)自然科學(xué)學(xué)報, 2016, 38(2): 99-103.

[3]PASQUIER N,BASTIDE Y,TAOUIL R, et al. Discovering frequent closed itemsets for association rules[J]. Lecture Notes in Computer Science, 1999, 1540: 398-416.

[4]SUTHA M J,DHANASEELAN F R. An efficient method for detection of breast cancer based onclosed frequent itemsets mining[J]. Journal of Medical Imaging & Health Informatics, 2015, 5(5): 45-56.

[5]TAN J. Efficient data streams based closed frequent itemsets mining algorithm[J]. Applied Mechanics & Materials, 2013, 256-259: 2910-2913.

[6]LUCCHESE C,ORLANDO S,PEREGO R. Fast and memory efficient mining of frequent closed itemsets[J]. IEEE Transactions on Knowledge & DataEngineering, 2006, 18(1): 21-36.

[7]王黎明, 張卓. 基于iceberg概念格并置集成的閉頻繁項(xiàng)集挖掘算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2007, 44(7): 1184-1190.

[8]CHEN G P,YANG Y B,ZHANG Y. MapReduce-based balanced mining for closed frequent itemset[C]//International Conference on Web Services, 2012: 652-653.

[9]IONESCU C M,COPOT D,COPOT C, et al.Parallel architecture for implementation of frequent itemset mining using FP-growth[C]//International Conference on Signals and Systems, 2017: 92-98.

[10]DLALA IO,JABBOUR S,SAIS L, et al. Parallel SAT based closed frequent itemsets enumeration[C]//IEEE/ACS 12th International Conference of Computer Systems and Applications, 2015: 1-8.

[11]陳潔, 褚龍現(xiàn), 夏棟梁. 一種支持并行處理的矢量數(shù)據(jù)存儲與查詢方法[J]. 電子設(shè)計(jì)工程, 2017, 25(10): 31-33.

[12]HAN J,PEI J,YIN Y, et al. Mining frequent patterns without candidate generation: a frequent-pattern tree approach[J]. Data Mining & Knowledge Discovery, 2004, 8(1): 53-87.

[13]PERKS O,BECKINGSALE D A,DAWES A S, et al. Analysing the influence of InfiniBand choice on OpenMPI memory consumption[C]//International Conference on High Performance Computing and Simulation, 2013: 186-193.

[14]唐穎峰, 陳世平. 一種基于后綴項(xiàng)表的并行閉頻繁項(xiàng)集挖掘算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2014, 31(2): 373-377.

[15]李海峰. 基于GPU的閉合頻繁項(xiàng)集挖掘方法[J]. 計(jì)算機(jī)工程, 2011, 37(14): 59-61.