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

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

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

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

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

1　DTPC算法

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

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

定義2閉項集：項i∈Ι是閉環(huán)的，當且僅當I″=I；S(I)代表i的支持，其值等于κ中包含i的項數(shù)；如果S(i)比S(I)的最小值大，則認為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}共同定義.閉包算子將項的冪集分割成了互不相連的子集.

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

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

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

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

(1)

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

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

Tab.1Exampleofdatatransformation

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

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

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

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

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

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

2　實驗分析

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

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

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

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

圖1(b)為在“Clue Web”上的實驗結(jié)果，通過減少最小支持度值，閉頻繁項數(shù)變化并不明顯；匹配候選者事務的數(shù)量卻快速增加，這樣會導致項集的候選者生成較大的條件上下文.然而，在這種情況下，本文提出的DTPC算法仍能獲得較好的計算性能，這是因為本文的算法避免了從每個條件上下文中產(chǎn)生閉包的冗余計算，而文獻[14]、[15]中的兩種算法則不具備這種能力.

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

[2]史玉珍, 呂瓊帥. 基于進化模糊規(guī)則的Web新聞文本挖掘與分類方法[J]. 湘潭大學自然科學學報, 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概念格并置集成的閉頻繁項集挖掘算法[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è)計工程, 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]唐穎峰, 陳世平. 一種基于后綴項表的并行閉頻繁項集挖掘算法[J]. 計算機應用研究, 2014, 31(2): 373-377.

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