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

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

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

?

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

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

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

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

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

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

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

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

1.1基本定義

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

(1)

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

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

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

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

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

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

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

表1　MFCPM模塊中使用的符號

Algorithm1 算法1 極大頻繁關(guān)聯(lián)模式挖掘模塊算法(MFCPM)Input:二進(jìn)制歷史文件,最小支持度閾值minsupp,最小全置信度閾值min-all-confidenceOutput:極大頻繁關(guān)聯(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的分散群復(fù)制算法

2.1算法的步驟

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

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

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

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

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

2.2二進(jìn)制歷史文件轉(zhuǎn)換

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

(2)

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

2.3DRMFCP算法的復(fù)制過程

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

DRMFCP算法復(fù)制過程的具體步驟如下：

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

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

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

(3)

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

(4)

(5)

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

圖2　OptorSim的體系結(jié)構(gòu)Fig. 2　OptorSim architecture

3 　性能分析與仿真評價

3.1仿真環(huán)境

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

圖3　CMS實驗臺網(wǎng)格拓?fù)銯ig. 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í)行平均時間越短，算法性能越好。

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

3.3閾值對算法性能的影響

給定作業(yè)數(shù)為1 000，周期為2%，分別研究最小全置信度閾值和最小支持度閾值等于0.2、0.4和0.6時，對應(yīng)的最小支持度閾值和最小全置信度閾值的變化對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í)行平均時間迅速增長，意味著算法性能惡化。仿真結(jié)果表明，閾值的增加可能會引起性能惡化，當(dāng)最小支持度閾值和最小全置信度閾值均等于0.5時，算法的平均執(zhí)行作業(yè)時間達(dá)到最低，意味著此時DRMFCP算法的性能達(dá)到最佳。

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

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

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

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

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

(6)

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

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

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

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

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

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

(7)

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

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

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

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

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

4　結(jié)　論

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

[1]王元卓, 賈巖濤, 劉大偉, 等. 基于開放網(wǎng)絡(luò)知識的信息檢索與數(shù)據(jù)挖掘[J]. 計算機(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]. 計算機(jī)科學(xué), 2015, 42(5): 260-264.

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

[7]趙佳璐, 楊俊, 韓晶, 等. 基于事務(wù)ID集合的帶約束的關(guān)聯(lián)規(guī)則挖掘算法[J]. 計算機(jī)工程與設(shè)計, 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

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

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

TN915.5

A

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

網(wǎng)絡(luò)出版地址：http:www.cnki.net/kcms/detail/23.1566.T.20160719.1132.008.html