前后部項(xiàng)約束關(guān)聯(lián)規(guī)則并行化算法

孟月昊 馮文 林榮霞 陳銘師

摘? 要： 為了解決大規(guī)模數(shù)據(jù)環(huán)境下挖掘出的關(guān)聯(lián)規(guī)則過(guò)多，用戶需要耗費(fèi)大量時(shí)間在這些關(guān)聯(lián)規(guī)則中尋找自己感興趣規(guī)則的問(wèn)題，提出了一種基于Map/Reduce并行化編程模型的前后部項(xiàng)約束關(guān)聯(lián)規(guī)則挖掘算法FRPFP。通過(guò)對(duì)用戶感興趣的規(guī)則前后部項(xiàng)進(jìn)行標(biāo)記和分組挖掘，并在各分組挖掘過(guò)程中根據(jù)標(biāo)記的規(guī)則前后部約束項(xiàng)，對(duì)事務(wù)集進(jìn)行壓縮，從而篩選出有效的頻繁項(xiàng)集，最終得到含有用戶感興趣項(xiàng)的關(guān)聯(lián)規(guī)則。該算法在Spark框架中實(shí)現(xiàn)，實(shí)驗(yàn)結(jié)果表明，該算法能夠有效地減少冗余規(guī)則的產(chǎn)生，計(jì)算開(kāi)銷較少，具有較好的規(guī)模增長(zhǎng)性。

關(guān)鍵詞： 項(xiàng)約束; 關(guān)聯(lián)規(guī)則; 數(shù)據(jù)挖掘; FRPFP算法

中圖分類號(hào)：TP311.11????????? 文獻(xiàn)標(biāo)識(shí)碼：A???? 文章編號(hào)：1006-8228（2021）08-01-07

Parallel algorithm for fore-part and rear-part item-constrained association rules

Meng Yuehao， Feng Wen， Lin Rongxia， Chen Mingshi

（32753Army， Wuhan， Hubei 430010， China）

Abstract： To solve the problem that too many association rules are mined in large-scale data environments， users need to spend a lot of time to find the rules they interested in， a fore-part and rear-part item-constrained association rule mining algorithm FRPFP based on Map/Reduce parallel programming model is proposed. By marking and grouping the fore-part and rear-part items of the rules of interest to the user， and compressing the transaction set according to the fore-part and rear-part constraint items of the tagged rules during the group mining process， a valid set of frequent items is filtered out， and the association rules containing the items of interest to the user are finally obtained. The algorithm is implemented in Spark framework， and the experimental results show that the algorithm can effectively reduce the generation of redundant rules， which has less computational overhead and has better scale growth.

Key words： item-constrained; association rule; data mining; FRPFP algorithm

0 引言

目前，關(guān)聯(lián)規(guī)則廣泛應(yīng)用于互聯(lián)網(wǎng)領(lǐng)域的推薦系統(tǒng)[1]和點(diǎn)擊流分析[2]等場(chǎng)景。在這些實(shí)際應(yīng)用場(chǎng)景中，商家往往希望通過(guò)關(guān)聯(lián)規(guī)則挖掘出用戶感興趣的、有明顯規(guī)則前后部約束的邏輯關(guān)系。例如，購(gòu)物籃分析可以研究“氣候/時(shí)間→貨物”的關(guān)系，從而指導(dǎo)電子商務(wù)巨頭，如亞馬遜、eBay等提高其銷售策略。在這里，“氣候/時(shí)間”是用戶感興趣的規(guī)則前部，“貨物”是用戶感興趣的規(guī)則后部。但是傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法在面向大規(guī)模數(shù)據(jù)挖掘時(shí)存在一些不足之處，如挖掘出的冗余規(guī)則過(guò)多，用戶需耗費(fèi)大量時(shí)間對(duì)挖掘出的關(guān)聯(lián)規(guī)則進(jìn)行二次篩選來(lái)尋找自己感興趣的部分。因此，迫切需要一種有效的并行化關(guān)聯(lián)規(guī)則算法來(lái)提高挖掘用戶感興趣規(guī)則的效率。

關(guān)聯(lián)規(guī)則的并行化研究主要聚焦于對(duì)經(jīng)典的Apriori算法和FP-growth算法的并行化改造[3-6]。早期主要針對(duì)Apriori算法的并行化改造[7]。近年來(lái)，F(xiàn)P-growth算法的并行化改造研究相對(duì)多起來(lái)。文獻(xiàn)[6]提出的PFP算法是目前應(yīng)用較為廣泛的FP-growth并行化的算法，其算法思想已在Spark MLlib工具包中實(shí)現(xiàn)。文獻(xiàn)[8]提出的FPPM算法優(yōu)化了FP-tree的構(gòu)建方法，減少了冗余枝的生成，提高了并行化挖掘效率。由于未考慮項(xiàng)約束，這些算法在應(yīng)對(duì)上述應(yīng)用需求方面會(huì)生成大量冗余無(wú)關(guān)的關(guān)聯(lián)規(guī)則。

當(dāng)前，項(xiàng)約束關(guān)聯(lián)規(guī)則[9-11]的研究成果在一定程度上可以應(yīng)用于上述用戶關(guān)心的邏輯需求。其中，文獻(xiàn)[12-13]對(duì)前后部約束關(guān)聯(lián)規(guī)則進(jìn)行了形式化定義，描述了有明確的規(guī)則前后部約束的邏輯關(guān)系，并給出了基于Apriori和FP-growth算法的前后部約束關(guān)聯(lián)規(guī)則挖掘算法。算法能夠挖掘出用戶感興趣的、有明顯的規(guī)則前后部約束的邏輯關(guān)系。但算法僅僅是基于單機(jī)環(huán)境進(jìn)行優(yōu)化挖掘的，在面對(duì)大規(guī)模數(shù)據(jù)集挖掘時(shí)，存在計(jì)算開(kāi)銷過(guò)大等問(wèn)題。文獻(xiàn)[14]提出的CPFP算法雖然是基于項(xiàng)約束條件的并行化關(guān)聯(lián)規(guī)則挖掘，但只側(cè)重于事物集的壓縮和FP-tree的剪枝，在后續(xù)挖掘頻繁項(xiàng)集過(guò)程中缺乏對(duì)用戶需求的針對(duì)性，從而仍會(huì)產(chǎn)生較多的冗余頻繁項(xiàng)集和無(wú)關(guān)規(guī)則。

針對(duì)項(xiàng)約束關(guān)聯(lián)規(guī)則并行化研究這一現(xiàn)狀，本文提出了一種基于Map/reduce并行編程模型的前后部項(xiàng)約束關(guān)聯(lián)規(guī)則并行化算法 FRPFP（Fore-part and Rear-part Parallel FP-Growth，簡(jiǎn)稱FRPFP）。該算法能夠基于規(guī)則前部和規(guī)則后部項(xiàng)約束，壓縮候選項(xiàng)集空間，并進(jìn)行分組篩選頻繁項(xiàng)集，從而有效減少冗余規(guī)則的產(chǎn)生。

1 前后部項(xiàng)約束關(guān)聯(lián)規(guī)則相關(guān)理論

由confidence （X→Y）=sup_count （X ∪Y）/sup_count（X）可知，若要求取前后部項(xiàng)約束關(guān)聯(lián)規(guī)則X→Y，則必需知道（X ∪Y）和X這兩種頻繁項(xiàng)集的支持度，而X為規(guī)則前部，Y為規(guī)則后部，則（X ∪Y）表示同時(shí)具有規(guī)則前部和后部項(xiàng)的頻繁項(xiàng)集，故定義前后部項(xiàng)集IFRt及對(duì)應(yīng)的前后部頻繁項(xiàng)集LFRt。而（X）表示只具有前部項(xiàng)的頻繁項(xiàng)集，故定義前部項(xiàng)集FSj及對(duì)應(yīng)的前部頻繁項(xiàng)集LFj。因此，F(xiàn)RPFP算法的思想在于：通過(guò)挖掘出所有的前后部頻繁項(xiàng)集LFRt和前部頻繁項(xiàng)集LFj，來(lái)達(dá)到求取符合項(xiàng)約束條件的關(guān)聯(lián)規(guī)則以及減少冗余規(guī)則數(shù)量的目的。整個(gè)算法核心是圍繞如何挖掘出所有的LFRt和LFj來(lái)進(jìn)行求解的。

2 FRPFP算法思想

2.1 算法流程

FRPFP算法流程分為四個(gè)步驟，通過(guò)二個(gè)Map/Reduce操作來(lái)完成，如圖1所示。為更直觀形象地理解本算法，本文以包含8個(gè)事務(wù)的事務(wù)集D作為案例，如圖2（a）所示，假定用戶感興趣的規(guī)則前部集合F={I2，I5}，規(guī)則后部集合R={I1，I3}，minsup=0.25。

步驟1 計(jì)算頻繁1-項(xiàng)集。通過(guò)一次Map/Reduce來(lái)完成。計(jì)算頻繁1-項(xiàng)集采用Map/Reduce里的詞頻統(tǒng)計(jì)思想，頻繁1-項(xiàng)集的結(jié)果采用表MFR-list來(lái)描述。MFR-list四個(gè)要素：項(xiàng)名、支持度計(jì)數(shù)、標(biāo)簽和指針。首先統(tǒng)計(jì)各項(xiàng)sup_count，篩選掉小于minsup值的項(xiàng)，將剩余項(xiàng)按照sup_count從大到小排序;接著根據(jù)用戶興趣對(duì)項(xiàng)加上標(biāo)簽，如果該項(xiàng)屬于前部項(xiàng)集合，則標(biāo)記為f，如果該項(xiàng)屬于后部項(xiàng)集合，則標(biāo)記為r;最后為各項(xiàng)加入指針，使得MFR-list具有項(xiàng)頭表的功能，用于鏈接后續(xù)構(gòu)建的FP-tree上的節(jié)點(diǎn)。

對(duì)事務(wù)集D完成步驟1后，生成的MFR-list如圖2（b）所示。MFR-list的第一列的項(xiàng)按照sup_count由大到小排序，第二列為項(xiàng)的sup_count值，第三列為存放前后部項(xiàng)的標(biāo)簽信息，第四列的值暫為空指針。

步驟2 分組建立FP-tree。此操作通過(guò)一次Map/Reduce來(lái)完成。在Map階段，首先對(duì)事務(wù)集D中的每條事務(wù)T按照項(xiàng)的sup_count降序重新排列。其次，構(gòu)建分組列表G-list，并按照G-list對(duì)每條事務(wù)進(jìn)行分組和篩選，壓縮分組事務(wù)集的空間，具體方法見(jiàn)2.2.1節(jié)。在Reduce階段，對(duì)壓縮后的分組事務(wù)集構(gòu)建分組FP-tree。

步驟3 挖掘LFR和LF。在步驟2建立的各分組FP-tree上，挖掘出所有前后部頻繁項(xiàng)集和前部頻繁項(xiàng)集，并分別放入集合LFR和LF中。具體方法見(jiàn)2.2.2節(jié)。

步驟4 輸出關(guān)聯(lián)規(guī)則。將各組挖掘結(jié)果歸并至同一計(jì)算節(jié)點(diǎn)，遍歷LFR，針對(duì)每個(gè)LFRt若存在對(duì)應(yīng)的前部頻繁項(xiàng)集LFj，則計(jì)算每個(gè)前后部頻繁項(xiàng)集的置信度，若其置信度大于等于minconf，則輸出強(qiáng)關(guān)聯(lián)規(guī)則。若不存在對(duì)應(yīng)的前部頻繁項(xiàng)集LFj，則不考慮。

2.2 算法具體描述

2.2.1 分組建立FP-tree

分組建立FP-tree通過(guò)一次Map/Reduce來(lái)完成。本節(jié)重點(diǎn)闡述Map階段對(duì)事務(wù)集D進(jìn)行分組并壓縮分組事務(wù)空間的方法。

⑴ 事務(wù)排序

根據(jù)MFR-list，對(duì)有標(biāo)簽的項(xiàng)構(gòu)建分組列表G-list，對(duì)每條事務(wù)T按照MFR-list中項(xiàng)的sup_count值降序排列，并根據(jù)結(jié)論1刪除未作標(biāo)簽項(xiàng)，如圖3（a）中的項(xiàng)I4。對(duì)事務(wù)集D按照MFR-list （圖3（a）），得到降序排列后的事務(wù)集合，如圖3（b）第三列。

⑵ 篩選分組

按照分組列表G-list對(duì)事務(wù)集合進(jìn)行分組，并根據(jù)結(jié)論2，去掉只標(biāo)記有r項(xiàng)的分組事務(wù)。而只標(biāo)記有f項(xiàng)的分組事務(wù)，由于會(huì)生成前部頻繁項(xiàng)集，故保留。以事務(wù)集D為例，按照?qǐng)D3（a）的分組列表G-list對(duì)事務(wù)集合進(jìn)行分組，如圖3（b）第四列。對(duì)已分組的事務(wù)1→{I1，I3}和3→{I1}，由于只包含后部項(xiàng)，故刪除此兩條事務(wù)。

具體偽代碼如下：

Mapper階段：

1.Sort-D （D， MFR-list） { //刪除事務(wù)中冗余項(xiàng)，并對(duì)事務(wù)排序

2. ?foreach T in D do

3. ? ?foreach item in T do

4. ? ? ?if （item.support

5. ? ? then 從T中刪除item

6. ? ? ? ?Sortby（item.sup_count）.descend按照sup_count

對(duì)T中的項(xiàng)降序排列

7. ?Output Dsorted //輸出排序后的事務(wù)集合Dsorted

}

8.Partition-D（Dsorted，G-list） {//按照G-list分組，并刪除冗余事務(wù)

9. D_P←partition（Dsorted，G-list） //按照G-list分組

10. ?foreach Di in D_P do

11. ? ? foreach T in Di do

12. ? ? ? ?if item∈T， 且item標(biāo)記為r

13. ? ? ? ?then 刪除T

}

在Reduce階段，將篩選后的分組事務(wù)按照相同的Group-id歸并至同一個(gè)Reducer中，并建立分組FP-tree。以事務(wù)集D為例，1號(hào)、2號(hào)和3號(hào)分組的事務(wù)集合如圖3（b）第五列所示?；贕roup1的事務(wù)集合構(gòu)建的分組FP-tree如圖4所示。需要指出的是，為了便于搜索分組FP-tree，以MFR-list作為項(xiàng)頭表，使分組中的前部項(xiàng)和后部項(xiàng)通過(guò)指針指向它在分組FP-tree中的位置。如圖4所示，I5，I3是Group1中的項(xiàng)，且I5為前部項(xiàng)（標(biāo)記為f），I3為后部項(xiàng)（標(biāo)記為r），故分別通過(guò)指針指向I5和I3在1號(hào)分組FP-tree中的位置。

2.2.2 挖掘LFR和LF

在Reducer中，通過(guò)掃描分組FP-tree進(jìn)行挖掘，得到包含前后部頻繁項(xiàng)集的集合LFR和前部頻繁項(xiàng)集集合LF。具體挖掘方法分為二步：①發(fā)現(xiàn)分枝;②在分枝上挖掘LFR和LF。

⑴ 發(fā)現(xiàn)分枝

針對(duì)每個(gè)分組建立的FP-tree，挖掘標(biāo)記為f或r的本分組項(xiàng)。如圖4所示，以事務(wù)集合D的Group1建立的FP-tree為例，I5和I3屬于Group1，且標(biāo)記分別為f和r。I5在Group1的FP-tree上有兩個(gè)分支：null→I2：1→I5：1和null→I2：2→I1：2→I3：2→I5：2。I3在Group1的FP-tree上有兩個(gè)分支：null→I2：4→I1：4→I3：4，和null→I2：1→I3：1。

⑵ 在分枝上挖掘LFR和LF

根據(jù)經(jīng)典FP-growth算法挖掘頻繁項(xiàng)集的思想：以待挖掘項(xiàng)為后綴挖掘FP-tree，構(gòu)造條件模式樹(shù)，從而生成包含后綴的頻繁項(xiàng)集。因此利用生成的頻繁項(xiàng)集必定包含后綴項(xiàng)這一特性，在挖掘分組FP-tree分枝時(shí)，以本分組包含的項(xiàng)作為后綴，確保生成的IFRt和FSj必定包含本分組項(xiàng)，這樣的LFRt和LFj既是局部頻繁項(xiàng)集也是全局頻繁項(xiàng)集。

遍歷每個(gè)分枝，根據(jù)MFR-list的label中標(biāo)記的信息，將分枝上的節(jié)點(diǎn)項(xiàng)分別放入規(guī)則前部項(xiàng)集合F和規(guī)則后部項(xiàng)集合R，并分別求出前部項(xiàng)集集合FS和后部項(xiàng)集集合RS。具體分三種情況，若挖掘的是標(biāo)記為f的本分組項(xiàng)的分枝，則分為以下兩種情況。

⑴ 分枝上既有標(biāo)記為f的節(jié)點(diǎn)也有標(biāo)記為r的節(jié)點(diǎn)，則只保留FS中包含本分組項(xiàng)的前部項(xiàng)集FSj，然后與RS中的后部項(xiàng)集RSn兩兩組合連接，生成前后部項(xiàng)集IFRt并輸出，即IFRt=FSj?RSn，同時(shí)輸出保留的前部項(xiàng)集FSj。

⑵ 分枝上的節(jié)點(diǎn)均標(biāo)記為f，即規(guī)則后部集合R為空集，則直接輸出FS中包含本分組項(xiàng)的前部項(xiàng)集FSj。

以Group1的FP-tree為例，圖5是挖掘標(biāo)記為f的本分組項(xiàng)I5的分枝。

由圖5可知，I5屬于Group1的本分組項(xiàng)且被標(biāo)記為f。選取I5一條分枝null→I2：2→I1：2→I3：2→I5：2，將標(biāo)記為f的I5，I2放入規(guī)則前部集合F，標(biāo)記為r的I3，I1放入規(guī)則后部集合R，并求出前部項(xiàng)集集合FS與后部項(xiàng)集集合RS。由于I5屬于Group1的本分組項(xiàng)，故只保留FS中包含I5的前部項(xiàng)集FSj，將篩選后的FSj與RSn兩兩進(jìn)行組合連接，輸出前后部項(xiàng)集IFRt，同時(shí)輸出前部項(xiàng)集FSj，輸出結(jié)果如圖中所示。

而I5的另一條枝null→I2：1→I5：1，由于I2，I5均標(biāo)記為f，則生成的規(guī)則后部集合R為空集。同理，由于I5屬于Group1的本分組項(xiàng)，故只保留FS中包含I5的前部項(xiàng)集FSj，輸出前部項(xiàng)集<{I5}，1>，<{I2，I5}，1>。

若挖掘的是標(biāo)記為r的本分組項(xiàng)的分枝，只存在一種情況：只保留RS中包含本分組項(xiàng)的后部項(xiàng)集RSn，然后與FS中的前部項(xiàng)集FSj兩兩組合連接，生成前后部項(xiàng)集IFRt并輸出，但不輸出前部項(xiàng)集FSj。如圖6所示是挖掘標(biāo)記為r的本分組項(xiàng)I3的分枝。

由圖6可知，I3屬于1號(hào)組的本分組項(xiàng)且被標(biāo)記為r。選取I3一條分枝null→I2：4→I1：4→I3：4，由于I3出現(xiàn)在規(guī)則后部項(xiàng)集合R中，故只保留RS中包含I3的后部項(xiàng)集RSn，然后與前部項(xiàng)集FSj兩兩組合連接，輸出前后部項(xiàng)集IFRt。

最后將本組挖掘出的IFRt、FSj進(jìn)行合并，如I5的兩條枝均有生成{I5}，{I2，I5}，故將其合并。得到候選項(xiàng)集CFRt和CFsj，并根據(jù)最小支持度minsup求出前后部頻繁項(xiàng)集LFRt和前部頻繁項(xiàng)集LFj，并分別放入前后部頻繁項(xiàng)集集合LFR和前部頻繁項(xiàng)集集合LF中。如圖7是Group1所挖掘出的本分組項(xiàng)I5的前后部頻繁項(xiàng)集集合LFR和前部頻繁項(xiàng)集集合LF。

具體偽代碼如下所示。

In Reducer：

1. gen-LFR（FP-tree，MFR-list，G-list[i]，minsup） {

//發(fā)現(xiàn)分枝

2. foreach item in G-list[i] { //對(duì)每組的分組項(xiàng)

3. if item.link ≠ null then

4. ? Branchset←find branch（item.link，F(xiàn)P-tree）;

5. ? foreach branch in Branchset ?do

6. ? ? F←findFore-part（branch， MFR-list）;

7. ? ? R←findRear-part（branch， MFR-list）;

8. ? ? FS←non-empty-powerset（F）;

9. ? ? RS←non-empty-powerset（R）;

//挖掘本分組項(xiàng)標(biāo)記為f的情況：

10. if item.label= ‘f

11. then保留FS中包含本分組項(xiàng)的前部項(xiàng)集FSj

12. if R≠Φ then //挖掘標(biāo)記有f和r節(jié)點(diǎn)的分枝

13. ? foreach （FSj∈FS ，RSn∈RS） do

14. ? ? IFRt←FSj?RSn//生成前后部項(xiàng)集IFRt

15. ? else 重復(fù)步驟（11） // R≠Φ即挖掘只標(biāo)記有f

節(jié)點(diǎn)的分枝

//挖掘本分組項(xiàng)標(biāo)記為r的情況

16. ? if item.label=‘r then//若本分組項(xiàng)被標(biāo)記為r

17. ? ? ?保留RS中包含本分組項(xiàng)的后部項(xiàng)集RSn

18. ? ? ?重復(fù)步驟（13）、（14）生成IFRt。

//合并項(xiàng)集生成LFR，LF

19. CFRt，CFj←aggregate（IFRt，F(xiàn)Sj）//將相同的IFRt，F(xiàn)Sj進(jìn)行合并

生成候選項(xiàng)集CFRt，CFj

20. foreach CFRt，CFj do //合并同時(shí)判斷頻繁項(xiàng)集

21. ? if CFRt，CFj ≥ minsup×D then

22. ? ? LFRt，LFj←CFRt，CFj //生成頻繁項(xiàng)集LFRt，LFj

23. ? ? LFR，LF←add LFRt，LFj //將LFRt，LFj添加進(jìn)LFR，LF

}

24. ? i++

}

3 實(shí)驗(yàn)結(jié)果與分析

3.1 算法性能測(cè)試及分析

本文提出的FRPFP算法采用Scala編程并在Spark框架下實(shí)現(xiàn)。實(shí)驗(yàn)環(huán)境為：3臺(tái)CPU主頻為3.6GHz，內(nèi)存為16G的臺(tái)式機(jī)，Ubuntu16.04，Hadoop2.7.2，Spark1.6.1，scala2.10.4，JDK1.7.0_51。實(shí)驗(yàn)從不同數(shù)據(jù)量的運(yùn)行時(shí)間以及生成的關(guān)聯(lián)規(guī)則數(shù)量?jī)蓚€(gè)方面比較FRPFP算法與其他算法的優(yōu)劣;并從規(guī)模增長(zhǎng)性方面分析了FRPFP算法本身的性能。采用http：//fimi.ua.ac.be/data/的T40I10D100k數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集。

3.1.1 FRPFP算法與其他算法對(duì)比分析

⑴ 不同數(shù)據(jù)量運(yùn)行時(shí)間對(duì)比

對(duì)FRPFP、PFP[6]、FPPM[8]以及CPFP[14]算法進(jìn)行對(duì)比。把數(shù)據(jù)集分成10組，設(shè)置最小支持度minsup為10%，最小置信度minconf為50%。由于FRPFP算法對(duì)挖掘的項(xiàng)有約束，因此為減小因項(xiàng)的數(shù)目和種類不同導(dǎo)致挖掘的復(fù)雜程度不同的影響，每組數(shù)據(jù)集將所有頻繁1-項(xiàng)集隨機(jī)均分成兩組并標(biāo)記為f或r，構(gòu)建MFR-list。共進(jìn)行10次實(shí)驗(yàn)，取10次實(shí)驗(yàn)結(jié)果的平均值作為本組實(shí)驗(yàn)的運(yùn)行時(shí)間，結(jié)果如圖8所示。

從圖8中可以看出，F(xiàn)RPFP算法和同屬于項(xiàng)約束算法的CPFP相比，計(jì)算時(shí)間更少，但和側(cè)重于性能提高的FPPM算法相比，所用時(shí)間較多。

⑵ 生成關(guān)聯(lián)規(guī)則數(shù)目結(jié)果對(duì)比

為了測(cè)試FRPFP算法挖掘關(guān)聯(lián)規(guī)則的效果，利用實(shí)驗(yàn)⑴中的10組測(cè)試集得出的關(guān)聯(lián)規(guī)則的結(jié)果進(jìn)行對(duì)比。由于PFP和FPPM算法均未對(duì)挖掘的項(xiàng)有約束條件，故挖掘的是所有關(guān)聯(lián)規(guī)則。而CPFP和FRPFP算法均對(duì)挖掘的關(guān)聯(lián)規(guī)則有約束，故生成的關(guān)聯(lián)規(guī)則數(shù)量不同。具體結(jié)果如表1所示。

結(jié)合表1中的實(shí)驗(yàn)結(jié)果，F(xiàn)RPFP算法生成的關(guān)聯(lián)規(guī)則數(shù)與PFP、FPPM算法相比，大大減少了冗余規(guī)則的產(chǎn)生，與CPFP算法相比，生成的規(guī)則數(shù)也較少。

3.1.2 FRPFP算法本身的性能

數(shù)據(jù)量規(guī)模增長(zhǎng)性測(cè)試。規(guī)模增長(zhǎng)性是指處理節(jié)點(diǎn)不變的條件下，擴(kuò)大數(shù)據(jù)規(guī)模時(shí)，并行算法的性能。計(jì)算公式為sizeup （D，m）=tm×D /tD，式tm×D中表示對(duì)規(guī)模為m×D的數(shù)據(jù)集運(yùn)行算法所用的時(shí)間，tD表示對(duì)規(guī)模為D的數(shù)據(jù)集運(yùn)行算法所用的時(shí)間。根據(jù)圖8中的實(shí)驗(yàn)數(shù)據(jù)，可得FRPFP算法數(shù)據(jù)量規(guī)模增長(zhǎng)性曲線如圖9所示。

從圖9的實(shí)驗(yàn)效果可以看出，F(xiàn)RPFP算法具有良好的數(shù)據(jù)規(guī)模增長(zhǎng)性。

4 結(jié)束語(yǔ)

本文提出的FRPFP算法屬于項(xiàng)約束關(guān)聯(lián)規(guī)則算法的一種，在挖掘關(guān)聯(lián)規(guī)則方面，能夠減少大量冗余規(guī)則的產(chǎn)生，不僅提高了用戶篩選自己感興趣的關(guān)聯(lián)規(guī)則的效率，降低了時(shí)間成本，而且算法也具有較好的規(guī)模增長(zhǎng)性，在計(jì)算開(kāi)銷的時(shí)間花費(fèi)上與傳統(tǒng)的算法相比也較少，能夠較好的適用于大規(guī)模數(shù)據(jù)集的挖掘。

參考文獻(xiàn)（References）：

[1] W. Lin， S. A. Alvarez， and C. Ruiz.Efficient Adaptive Support Association Rule Mining for Recommender Systems[J].DataMining and Knowledge Discovery，2002.6（1）：83-105

[2] B. Mobasher， H. Dai， T. Luo， and M. Nakagawa.Effictive

Personalization Based on AssociationRule Discovery from Web Usage Data[C]//ACM CIKM 2001 10th International Conference on Information andKnowledge Management，2001：9-15

[3] 米允龍，姜 麟，米春橋.MapReduce環(huán)境下的否定粗糙關(guān)聯(lián)規(guī)則算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2014.20（11）：2894-2903

[4] HE B.The algorithm of mining frequent itemsets based on

MapReduce[C]//Proceedings of InternationalConference on Soft Computing Techniques and Engineering Application.Ber-lin， Ger-many：Springer Verlag，2014.15：1827-1831

[5] QIU H，GU R，YUAN C， et al. YAFIM：A parallel frequent

itemset mining algorithm with Spark[C]//2014 IEEE InternationalParallel&Distributed Processing Symposium Workshops.[S.l.]：IEEE，2014：1664-1671

[6] Haoyuan Li，Yi Wang，Dong Zhang，Ming Zhang，Edward Y.

Chang. PFP：Parallel FP-Growth forQuery Recommendation[J].ACM Conference on Recommender Systems，2008.39（5）：107-114

[7] A. Savasere， E. Omiecinski， and S.B. Navathe.An

EfficientAlgorithm for Mining Association Rules in Large Databases[J].Vldb Journal，1995：432-444

[8] 章志剛，吉根林.一種基于FP-growth的頻繁項(xiàng)目集并行挖掘算法[J].計(jì)算機(jī)工程與應(yīng)用，2014.50（2）：103-106

[9] 陳平，王利剛，李博涵.基于項(xiàng)約束的關(guān)聯(lián)規(guī)則挖掘研究綜述[J].制造業(yè)制動(dòng)化，2014.36（8）：10-15

[10] 陶再平.基于約束的關(guān)聯(lián)規(guī)則挖掘[M].浙江工商大學(xué)出版社，2012.

[11] AGRAWAL R，SHAFERJ C. Parallel Mining of?Association rules[J].IEEE Transactions on Konwledge and Data Engineering，1996.8（6）：962-969

[12] 孟月昊，王朝霞，郭宇棟.基于規(guī)則前后部約束的關(guān)聯(lián)規(guī)則挖掘算法[J].后勤工程學(xué)院學(xué)報(bào)，2017.33（1）：79-84

[13] 李贊，王朝霞，孟月昊，隋昊.基于FP-growth的前后部項(xiàng)約束關(guān)聯(lián)規(guī)則改進(jìn)算法[J].艦船電子工程，2018.38（9）：21-26

[14] 楊向榮，王希武.基于規(guī)則約束的并行FP-growth算法研究[J].計(jì)算機(jī)與數(shù)字工程，2015.11（43）：1933-1936

[15] 范明，孟小峰.數(shù)據(jù)挖掘：概念與技術(shù)[M].機(jī)械工業(yè)出版社，2001：149-175

收稿日期：2021-03-29

基金項(xiàng)目：貴州大學(xué)文科研究青年項(xiàng)目資助“邊緣計(jì)算驅(qū)動(dòng)的高校智慧圖書(shū)館數(shù)據(jù)智能流通模式研究”（GDQN2020028）

作者簡(jiǎn)介：周杰（1992-），男，安徽六安人，貴州大學(xué)圖書(shū)館助理館員，主要研究方向：新技術(shù)應(yīng)用。