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

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

海量信息的爆發(fā)式增長(zhǎng)已成為當(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í)時(shí)性和可靠性.

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

為充分利用并行框架Spark在計(jì)算和存儲(chǔ)等方面的優(yōu)勢(shì)，本文提出一種基于數(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)確性和動(dòng)態(tài)響應(yīng)速度等方面大大優(yōu)于現(xiàn)有的算法.

1　DTPC算法

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

定義1提取上下文：指一個(gè)三元組κ=(O,I,R)，式中O表示對(duì)象的有限集合，I為項(xiàng)的有限集合，R為二元(關(guān)聯(lián))關(guān)系(即R?O×I)，每對(duì)(o,i)∈R表示對(duì)象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)列表，同時(shí)使用Spark[11]依據(jù)項(xiàng)支持的降序分類該列表.

定義3質(zhì)數(shù)：一個(gè)整數(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分配給每個(gè)項(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)時(shí)，i的條件上下文定義為包含i的轉(zhuǎn)換子集.令j為頻繁項(xiàng)X的條件上下文中的一個(gè)頻繁項(xiàng)，當(dāng)省略了所有頻繁項(xiàng)、項(xiàng)j和跟隨j之后的項(xiàng)時(shí)，jX條件上下文定義為包含j的、X的條件上下文中的轉(zhuǎn)換子集.

將頻繁項(xiàng)按支持度的大小進(jìn)行降序分類，對(duì)于每個(gè)i，DTPC只包含i的數(shù)據(jù)轉(zhuǎn)換中的條件上下文.為了加快對(duì)這些子上下文的搜索，本文定義了與每個(gè)上下文關(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ù)，可以很簡(jiǎn)單地計(jì)算出閉包，而且這并不需要存儲(chǔ)條件上下文包含的項(xiàng)的支持度.通過將閉包與連接候選項(xiàng)進(jìn)行連接(即將該候選項(xiàng)的質(zhì)數(shù)與閉包的數(shù)值相乘)，即可得到閉頻繁項(xiàng)集.本文將該閉頻繁項(xiàng)集表示為一個(gè)數(shù)，并將該數(shù)添加到最終得到的集合中.

綜上，可得DTPC算法的具體步驟：(1) 對(duì)輸入數(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)集時(shí)，DTPC算法使用第二個(gè)Spark,通過將上下文分割為一個(gè)新的數(shù)據(jù)集，并將其作為輸入數(shù)據(jù)的條件上下文.此時(shí)，DTPC算法通過應(yīng)用新的閉包操作，計(jì)算條件上下文之間所有事務(wù)的最大公約數(shù)，進(jìn)而提取并獲取閉環(huán).

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

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

采用高性能消息傳遞庫OpenMPI[13]作為實(shí)驗(yàn)平臺(tái)，選取15個(gè)節(jié)點(diǎn)的聚類進(jìn)行實(shí)驗(yàn)：將一個(gè)節(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%時(shí)，三種算法在“Google Article”上測(cè)試的實(shí)驗(yàn)結(jié)果.由實(shí)驗(yàn)結(jié)果可知，提出的DTPC算法明顯優(yōu)于其他算法.這是因?yàn)椤癎oogle Article”包含數(shù)量眾多的項(xiàng)，項(xiàng)數(shù)幾乎等于事物數(shù).當(dāng)最小支持度的值足夠低時(shí)，文獻(xiàn)[14]、[15]中的兩種算法都會(huì)生成許多的候選者和條件上下文.因此，在這兩種算法中所使用的方法非常復(fù)雜，進(jìn)而導(dǎo)致挖掘性能變差.DTPC算法基于質(zhì)數(shù)，通過簡(jiǎn)單的平方/開方運(yùn)算即可生成條件上下文，因而計(jì)算起來非常簡(jiǎn)便.此外，每個(gè)條件上下文中的最大公約數(shù)消除了候選者和其閉包之間的支持度檢驗(yàn)，從而省略了閉包頻率的計(jì)算.

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

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

[2]史玉珍, 呂瓊帥. 基于進(jìn)化模糊規(guī)則的Web新聞文本挖掘與分類方法[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào), 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ù)存儲(chǔ)與查詢方法[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.