劉瑞雪，秦丹陽，賈　爽，楊松祥

(1.哈爾濱工業(yè)大學 深圳研究生院，廣東 深圳 518055；2.黑龍江大學 電子工程學院，哈爾濱 150080 )

?

基于極大頻繁關聯(lián)模式挖掘的復制算法研究

劉瑞雪1，2，秦丹陽2，*，賈爽2，楊松祥2

(1.哈爾濱工業(yè)大學 深圳研究生院，廣東 深圳 518055；2.黑龍江大學 電子工程學院，哈爾濱 150080 )

針對現(xiàn)有基于數(shù)據挖掘的文件關聯(lián)性復制算法無法有效提取文件關聯(lián)性的問題，提出了基于極大頻繁關聯(lián)模式挖掘的分散群復制算法(Decentralized Replication strategy based on Maximal Frequent Correlated Patterns, DRMFCP)。DRMFCP算法通過二進制歷史文件轉換、極大頻繁關聯(lián)模式挖掘和復制，以實現(xiàn)極大減少復制模式數(shù)量、消除冗余以及優(yōu)化復制的目的。數(shù)據分析與仿真結果表明，在不同存取模式下相較于無復制、DR2、PRA和PDDRA算法，DRMFCP算法提取文件關聯(lián)性的效率更高，并能同時降低作業(yè)執(zhí)行平均時間，為降低網格數(shù)據傳輸延遲提供新的解決方案。

數(shù)據挖掘；關聯(lián)模式；數(shù)據復制；分散群

數(shù)據網格是一種管理科學實驗和工程應用領域中產生的大量分布式數(shù)據的集成架構[1]。數(shù)據復制技術能夠改善數(shù)據網格的響應時間，減少帶寬消耗并維護系統(tǒng)可靠性。然而，目前多數(shù)復制算法在運行時只考慮了單一文件群，而忽略了各文件群間的關聯(lián)性。分析表明，許多實際的數(shù)據密集型應用與文件群的關聯(lián)性密切相關。因此，有效提取文件關聯(lián)性成為相關研究領域的熱點。數(shù)據挖掘技術可從大量數(shù)據集合中提取有價值信息，利用數(shù)據挖掘技術挖掘網格數(shù)據，能夠有效發(fā)現(xiàn)文件間隱藏的關聯(lián)性，從而實現(xiàn)優(yōu)化網格副本管理模塊的目的。

挖掘文件間關聯(lián)性可以采用頻繁序列挖掘和關聯(lián)模式挖掘兩種方法。典型的PRA[2]和PDDRA[3]算法主要是基于頻繁序列挖掘的復制算法，每次運行時，為了預測請求的文件，將不斷進行頻繁序列挖掘，這不僅會增加復制的文件數(shù)量，也會對網格響應時間及存儲占用百分比造成較大的影響。Apriori算法[4]是最典型的關聯(lián)模式挖掘算法之一，它能夠從大型數(shù)據集合中識別出頻繁項集合，從而生成強關聯(lián)模式。Apriori算法屬于比較成熟的數(shù)據挖掘算法，其優(yōu)化及衍生態(tài)挖掘方式可以應用于不同行業(yè)領域[5-7]。但是，常見的關聯(lián)模式挖掘算法提取模式中大多存在冗余，無法反映出文件真實的關聯(lián)情況[8,9]。為此，本文在已有研究的基礎上，提出一種基于關聯(lián)模式挖掘的分散群復制算法DRMFCP，通過優(yōu)化周期參數(shù)并利用極大頻繁關聯(lián)模式挖掘模塊，周期地在實際的網格環(huán)境中觸發(fā)數(shù)據挖掘，用以實現(xiàn)降低網絡延遲、快速訪問遠程有價值文件的目的。

1　極大頻繁關聯(lián)模式挖掘

1.1基本定義

定義1全置信度。全置信度是一種關聯(lián)性度量，用于判斷模式的關聯(lián)性程度。項集X?I的全置信度的計算公式為：

(1)

1)反單調性。對于任意項集I?I，I1?I，如果I滿足約束條件Q能推出I1也滿足條件Q，則約束Q是反單調的。

3)零不變性。零不變關聯(lián)性度量允許定量分析同一組中項的相互關聯(lián)程度，而不考慮不屬于提到的組的項[10]。對于模式I?I，稱不包含I的事務為零事務，那么零事務數(shù)一定不能決定I的零不變關聯(lián)性，從而避免了零事務對判斷關聯(lián)性的影響。

定義3極大頻繁關聯(lián)模式。若X是頻繁關聯(lián)模式，但是X的超集一定不是頻繁關聯(lián)模式，那么稱X為極大頻繁關聯(lián)模式。定義極大頻繁關聯(lián)模式能極大減少待復制的分散群數(shù)量，降低網格的存儲占用，優(yōu)化復制過程。

1.2極大頻繁關聯(lián)模式挖掘模塊

為了對網格的分散群進行挖掘，需要提取前文所述的極大頻繁關聯(lián)模式，本節(jié)設計了一種極大頻繁關聯(lián)模式挖掘模塊(Maximal Frequent Correlated Patterns Miner, MFCPM)，主要通過算法1實現(xiàn)，其中相關符號定義見表1。

對算法1的子程序GENERATE_NEXT_FCP說明如下：①以FCP為輸入，運行Apriori算法，生成候選k+1項集Ck+1；②確保每個Ck+1中的模式Xk+1滿足全置信度的交叉支持性，否則進行剪枝；③確保每個Xk+1滿足頻繁關聯(lián)模式的反單調性，否則進行剪枝；④若Xk+1能夠同時滿足上述兩種性質，計算Xk+1的支持度并與最小支持度閾值minsupp進行比較，判斷模式Xk+1是否頻繁；⑤若Xk+1是頻繁的，繼續(xù)計算其全置信度。若Xk+1的全置信度不小于最小全置信度閾值min-all-confidence，說明Xk+1是頻繁關聯(lián)模式，將其添加到頻繁關聯(lián)模式集中。算法最終輸出頻繁關聯(lián)模式k+1項集FCPk+1。

MFCPM模塊輸出的極大頻繁關聯(lián)模式將作為后續(xù)描述的DRMFCP算法的輸入，繼續(xù)進行后續(xù)的復制過程。

表1　MFCPM模塊中使用的符號

Algorithm1 算法1 極大頻繁關聯(lián)模式挖掘模塊算法(MFCPM)Input:二進制歷史文件,最小支持度閾值minsupp,最小全置信度閾值min-all-confidenceOutput:極大頻繁關聯(lián)模式1Begin2k:=1;3FCP1:={i∈I|Supp(i)≥minsupp};%確定頻繁項4MFCP:=FCP1;5WhileFCPk≠?do6FCPk+1:=GENERATE_NEXT_FCP(FCPk,min-supp,min-all-confidence);7Foreach(Xk+1∈FCPk+1)do8IF(?Xk?Xk+1|(Xk∈MFCP))then9removeXkfromMFCP10MFCP:=MFCP∪FCPk+1;%確保不存在冗余的模式11k:=k+1;12ReturnMFCP13End

圖1　DRMFCP算法的主要步驟Fig. 1　Main steps of the DRMFCP strategy

2　基于MFCP的分散群復制算法

2.1算法的步驟

本文基于前節(jié)提出的MFCPM算法，設計了一種面向P2P數(shù)據網格拓撲的分散群復制算法(Decentralized Replication strategy based on Maximal Frequent Correlated Patterns, DRMFCP)，通過協(xié)同定位分散群來改善網格性能，該算法包括4個執(zhí)行階段，見圖1。

1)提取文件存取歷史。針對本地文件和遠端文件的請求，當前站點作業(yè)需要在每個執(zhí)行周期內記錄文件存取歷史，作業(yè)存取順序由存取模式決定。

2)將文件存取歷史轉換為二進制歷史文件。二進制歷史文件實際上是由存取的目標文件和作業(yè)組成的包含邏輯值的列表。

3)生成極大頻繁關聯(lián)模式。利用MFCPM模塊挖掘分散群之間隱藏的關聯(lián)性，簡化后續(xù)的復制過程。

4)復制和置換。以MFCPM模塊的輸出作為本階段的輸入，主要根據待復制和待刪除文件的平均權重選擇保留或置換。

2.2二進制歷史文件轉換

在進行數(shù)據挖掘前，將文件存取歷史轉換為包含邏輯值0或1的二進制歷史文件。為了進行轉換，需要考慮文件的普遍性。如果站點Si執(zhí)行的作業(yè)頻繁的存取某一文件Fj，那么認為Fj在站點Si范圍內是普遍的。引入每個文件被請求的平均次數(shù)AvgAccess(Fj)，以便于評估站點Si中文件Fj的普遍性。AvgAccess(Fj)的定義式為：

(2)

其中，nj是存取文件Fj的總作業(yè)數(shù)。

2.3DRMFCP算法的復制過程

以MFCPM模塊輸出的極大頻繁關聯(lián)模式MFCP作為復制過程的輸入。設MFCP={α1,α2,…,αn}，任意元素αi∈MFCP都是作業(yè)頻繁同時存取文件的集合。

DRMFCP算法復制過程的具體步驟如下：

1)對于αi∈MFCP，按照αi包含模式數(shù)的遞減順序，對MFCP中的元素進行排序。

2)對于αi∈MFCP，如果站點的存儲空間足夠存儲αi中的所有文件，那么將復制αi中的所有文件到站點Si。

3)否則，將通過式(3)計算站點Si的文件Fj的權重，選擇要刪除的候選文件。

(3)

4)根據式(4)和(5)分別計算待復制的和待刪除的文件組的平均權重。

(4)

(5)

5)對兩種平均權重值進行比較。若AvgGroupRepWeight>AvgCandidateDelWeight，那么待刪除的候選文件將被待復制的文件所代替；否則放棄復制。

圖2　OptorSim的體系結構Fig. 2　OptorSim architecture

3 　性能分析與仿真評價

3.1仿真環(huán)境

本文使用OptorSim仿真器進行仿真。OptorSim是一種用Java語言編寫的仿真包，被用于仿真數(shù)據網格結構并測試作業(yè)調度和復制算法[11-12]。OptorSim由用戶、資源代理和許多站點組成。每個站點由計算元、副本管理器和存儲元組成。OptorSim的體系結構見圖2。本文的仿真環(huán)境為CMS實驗臺網格，網格拓撲見圖3，由模擬歐洲和美國的20個站點組成。CERN和FNAL站點都擁有100 Gb的存儲容量，其他站點均擁有一個計算元和50 Gb的存儲容量。最初，網格中文件大小為1 Gb，文件總數(shù)為97，作業(yè)總數(shù)為1 000，存儲在站點的SE中，采用順序存取方式，使用當前作業(yè)成本與隊列作業(yè)成本之和最小調度算法。

圖3　CMS實驗臺網格拓撲Fig. 3 　CMS testbed grid topology

圖4　不同執(zhí)行周期下DRMFCP算法的作業(yè)平均執(zhí)行時間Fig. 4　Mean job execution time of the DRMFCP strategy for different periods

3.2執(zhí)行周期對算法性能的影響

給定作業(yè)數(shù)為1 000，最小支持度和最小全置信度閾值固定，研究不同執(zhí)行周期對DRMFCP算法作業(yè)執(zhí)行平均時間的影響。這里定義所有作業(yè)獨立運行時間的總和除以運行作業(yè)的總數(shù)即為作業(yè)執(zhí)行平均時間。顯然作業(yè)執(zhí)行平均時間越短，算法性能越好。

仿真結果見圖4，這表明1 000個作業(yè)執(zhí)行時，每20個作業(yè)后(即2%)觸發(fā)DRMFCP可以得到最小的平均執(zhí)行時間。周期過短或過長時，都會頻繁存取遠端文件，導致作業(yè)執(zhí)行平均時間增加，復制效率下降。

3.3閾值對算法性能的影響

給定作業(yè)數(shù)為1 000，周期為2%，分別研究最小全置信度閾值和最小支持度閾值等于0.2、0.4和0.6時，對應的最小支持度閾值和最小全置信度閾值的變化對DRMFCP算法的作業(yè)執(zhí)行平均時間的影響，見圖5。

圖5　不同閾值下DRMFCP算法的作業(yè)平均執(zhí)行時間Fig. 5　Mean job execution time of the DRMFCP strategy for different thresholds

由圖5可見，閾值在0～0.5時，作業(yè)執(zhí)行平均時間開始緩慢衰減，閾值超過0.5后，作業(yè)執(zhí)行平均時間迅速增長，意味著算法性能惡化。仿真結果表明，閾值的增加可能會引起性能惡化，當最小支持度閾值和最小全置信度閾值均等于0.5時，算法的平均執(zhí)行作業(yè)時間達到最低，意味著此時DRMFCP算法的性能達到最佳。

3.4存取模式對算法性能的影響

給定作業(yè)數(shù)為1 000，周期為2%，最小支持度閾值和最小全置信度閾值均為0.5，對比提出的DRMFCP算法與其他4種復制算法在不同存取模式下的性能表現(xiàn)，4種算法分別是無復制算法、DR2[13]、PRA和PDDRA算法。每次對比過程至少重復10次，并計算其均值。

圖6　不同存取模式下的作業(yè)執(zhí)行平均時間Fig. 6　Mean job execution time for different access patterns

1)不同存取模式下5種算法的作業(yè)執(zhí)行平均時間見圖6。仿真結果表明，對于不同的存取模式，相比無復制、DR2、PRA和PDDRA算法，DRMFCP算法的作業(yè)執(zhí)行平均時間最多可分別降低80%，60%，20%和15%。

2)有效網絡利用率(Effective Network Usage, ENU)是轉移的文件與請求文件的比率，ENU的取值范圍在0至1之間，計算公式如(6)所示，其數(shù)值越小說明采用的復制算法性能越好。不同存取模式下5種算法的ENU見圖7。

(6)

其中，Nremotefileaccesses代表遠端文件存取數(shù)；Nfilereplications代表文件副本數(shù)；而Nlocalfileaccesses代表本地文件存取數(shù)。

仿真結果表示，相比DR2、PRA和PDDRA算法，DRMFCP算法的ENU值最多可分別降低80%，70%和65%。算法研究的主要目標之一是最小化帶寬消耗，減少網絡業(yè)務量，相比之下，DRMFCP算法實現(xiàn)效果更好。

3)復制總數(shù)即為復制執(zhí)行的總次數(shù)，復制總數(shù)大表明請求的文件大部分存儲在遠端。不同存取模式下5種算法的復制總數(shù)見圖8。

圖7 不同存取模式下的有效網絡利用率Fig.7 Effectivenetworkusagefordifferentaccesspatterns圖8 不同存取模式下的復制總數(shù)Fig.8 Totalnumberofreplicationsfordifferentaccesspatterns

仿真結果表明，對于所有的存取模式，相比DR2、PRA和PDDRA算法，DRMFCP算法的復制總數(shù)最多可分別減少40%，68%和70%，但仍然能確保數(shù)據網格中文件的可用性。復制總數(shù)越大意味著文件傳輸越多，其他的算法只是消耗了合理的網絡帶寬，而DRMFCP算法則成功地降低了復制總數(shù)且不會浪費更多的網絡帶寬。

4)命中率(Hit Ratio, HR)是存取本地文件總次數(shù)與存取所有文件總次數(shù)的比率，命中率的計算如式(7)所示。不同存取模式下各算法的命中率見圖9。

(7)

仿真結果表明，對于所有的存取模式，相比DR2、PRA和PDDRA算法，DRMFCP算法的命中率最多可分別提高65%，20%和15%。

5)存儲占用百分比是網格中各站點存儲元利用率的平均值。存儲元利用率是指文件使用的存儲資源與存儲元容量的比率。不同存取模式下5種算法的存儲占用百分比見圖10。

圖9　不同存取模式下的命中率Fig. 9　Hit ratio for different access patterns

圖10　不同存取模式下的存儲占用百分比Fig. 10　Percentage of storage filled for different access patterns

由仿真結果不難看出，由于無復制算法不執(zhí)行復制，因此存儲占用百分比最小。除無復制算法外，對于所有的存取模式，相比同類DR2、PRA和PDDRA算法，DRMFCP算法的存儲占用百分比最多可分別降低60%，65%和70%。

4　結　論

當今社會許多科學和工程領域產生的數(shù)據量與日俱增，因此各領域對計算和存儲的要求也越來越高，數(shù)據網格作為一種合理的解決方案應運而生。本文以網格中各站點分布的分散群為對象，在傳統(tǒng)的復制算法基礎上增加了極大頻繁關聯(lián)模式挖掘模塊，提出了基于極大頻繁關聯(lián)模式挖掘的分散群復制算法DRMFCP。與同類算法相比，DRMFCP算法的作業(yè)執(zhí)行平均時間和ENU最多可降低80%，而命中率最多可提高65%。仿真結果說明，DRMFCP算法以分散群為挖掘對象，能夠減少待復制的文件數(shù)量，從而改善網格性能，具有一定優(yōu)勢和良好的應用前景。未來的研究將對站點的文件存取歷史進行優(yōu)化，并采用多維動態(tài)的數(shù)據挖掘技術，以進一步改善復制過程，使算法更加適應實際網格環(huán)境的要求。

[1]王元卓, 賈巖濤, 劉大偉, 等. 基于開放網絡知識的信息檢索與數(shù)據挖掘[J]. 計算機研究與發(fā)展, 2015, 52(5): 456-474.

[2]Tian T, Luo J, Wu Z, et al. A pre-fetching-based replication algorithm in data grid[C]//Proceedings of the 3th International Conference on Pervasive Computing and Application. 2008: 526-531.

[3]Saadat N, Rahmani A M. PDDRA: a new pre-fetching based dynamic data replication algorithm in data grids[J]. Future Generation Computer System, 2012, 28(4): 666-681.

[4]Agrawal R, Imielinski T, Swami A. A mining association rules between sets of items in large databases[C]//Proceedings of the 1993 ACM SIGMOD Conference. 1993: 207-216.

[5]劉端陽, 馮建, 李曉. 一種基于邏輯的頻繁序列模式挖掘算法[J]. 計算機科學, 2015, 42(5): 260-264.

[6]王秀枝, 馮建, 李曉. 基于支持度和置信度智能優(yōu)化的關聯(lián)分類算法[J]. 計算機應用與軟件, 2013, 30(11): 184-186.

[7]趙佳璐, 楊俊, 韓晶, 等. 基于事務ID集合的帶約束的關聯(lián)規(guī)則挖掘算法[J]. 計算機工程與設計, 2013, 34(5): 1663-1667.

[8]Bouasker S,Hamrouni T, Yahia B S. Ecient mining of new concise representations of rare correlated patterns[J]. Intelligent Data Analysis, 2015, 19(2): 359-390.

[9]Kiran R U, Kitsuregawa M. Mining correlated patterns with multiple minimum all-confidence thresholds[C]//Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery and Data Mining. 2013: 295-306.

[10] Wu T, Chen Y, Han J. Re-examination of interestingness measures in pattern mining: a unified framework[J]. Data Mining and Knowledge Discovery, 2010, 21(3): 371-397.

[11] Grace R K, Manimegalai R. Dynamic replica placement and selection strategies in data grids-a comprehensive survey[J]. Journal of Parallel and Distributed Computing, 2014, 74(2): 2099-2108.

[12] Amjad T, Sher M, Dau M.A survey of dynamic replication strategies for improving data availability in data grids[J]. Future Generation Computer System, 2012, 28(2): 337-349.

[13] Suri P, Singh M. A two-stage dynamic replication strategy for data grid[J]. Recent Trends in Engineering and Technology, 2009, 2(4): 201-203.

Research on replication strategy based on maximalfrequent correlated patterns mining

LIU Rui-Xue1，2，QIN Dan-Yang2，*，JIA Shuang2，YANG Song-Xiang2

(1.ShenzhenGraduateSchool,HarbinInstituteofTechnology,Shenzhen518055,Guangdong,China;2.SchoolofElectronicEngineering,HeilongjiangUniversity,Harbin, 150080,China)

Aiming at the problem that most of the existing data mining based replication strategies cannot extract correlations between files effectively, an improved replication strategy based on maximal frequent correlated patterns mining, called DRMFCP, is proposed. By converting the file access history to a binary history file, applying maximal frequent correlated patterns mining and performing replication, DRMFCP can extremely reduce the number of patterns to replicate, eliminate redundancy and optimize the replication performance. Data analysis and simulation results show that comparing with other strategies, such as no replication, DR2, PRA and PDDRA, DRMFCP can extract correlations more effectively and gain lower mean job execution time with different access patterns, which will provide a new option to reduce transmission delay in data grid.

data mining; correlated patterns; data replication; distributed groups

10.13524/j.2095-008x.2016.03.045

2016-05-13

國家自然科學基金資助項目(61302074);教育部高等學校博士學科點專項科研基金資助項目(20122301120004);黑龍江省自然科學基金資助項目(QC2013C061)

劉瑞雪(1993-)，女，內蒙古赤峰人，碩士研究生，研究方向：數(shù)據挖掘，E-mail:ruixue_liu@foxmail.com;*通訊作者：秦丹陽(1984-)，女，江蘇蘇州人，副教授，碩士研究生導師，博士，研究方向：泛在通信與普適計算，E-mail：qindanyang@hlju.edu.cn。

TN915.5

A

2095-008X(2016)03-0074-08

網絡出版地址：http:www.cnki.net/kcms/detail/23.1566.T.20160719.1132.008.html