趙欣燦，朱 云，毛伊敏

（1.江西理工大學(xué) 理學(xué)院，江西 贛州 341000；2.江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000）

0 概述

關(guān)聯(lián)規(guī)則挖掘技術(shù)［1］是數(shù)據(jù)挖掘領(lǐng)域的重要分支之一，其旨在找出各數(shù)據(jù)項之間的相互關(guān)系，被廣泛應(yīng)用于社交網(wǎng)絡(luò)、精準營銷等領(lǐng)域。然而，隨著動態(tài)大數(shù)據(jù)的發(fā)展，數(shù)據(jù)維數(shù)逐漸升高。醫(yī)療數(shù)據(jù)、全球氣候數(shù)據(jù)以及多媒體數(shù)據(jù)等均屬于高維數(shù)據(jù)，且此類數(shù)據(jù)具有數(shù)據(jù)量大、數(shù)據(jù)特征豐富以及數(shù)據(jù)稀疏等特性［2］。因此，大部分數(shù)據(jù)挖掘技術(shù)已經(jīng)從單目標分析擴展為多目標融合分析［3］。采用高效的方式準確捕捉高維復(fù)雜數(shù)據(jù)的特征屬性，以及解決節(jié)點分布的負載均衡化問題，并有效提高頻繁項集的緊湊程度［4］成為研究熱點。

本文提出基于MapReduce 的高維數(shù)據(jù)頻繁項集挖掘算法PARDG-MR。通過設(shè)計基于高維數(shù)據(jù)維度?；约肮?jié)點負載均衡的數(shù)據(jù)預(yù)處理策略，并對復(fù)雜的高維數(shù)據(jù)進行特征屬性捕捉，構(gòu)建基于本地PJPFP-Tree 樹存儲結(jié)構(gòu)的算法步驟并行化方法。在此基礎(chǔ)上，提出基于剪枝前綴推論（Pruning Prefix Lemma，PPL）的整合節(jié)點算法，從而提高算法整體運行速率，且減少算法執(zhí)行時間和內(nèi)存。

1 相關(guān)工作

高維數(shù)據(jù)預(yù)處理過程包括以特征提取和特征選擇［5］兩種方式，在有效消除無關(guān)、冗余特征的同時也減小了特征挖掘空間，但是該方法忽略了數(shù)據(jù)的敏感性以及數(shù)據(jù)特征之間的關(guān)聯(lián)性。為獲得更優(yōu)的數(shù)據(jù)特征屬性挖掘結(jié)果，研究人員對高維數(shù)據(jù)進行維數(shù)約簡。文獻［6］提出基于圖的大數(shù)據(jù)實體識別算法，并將高維數(shù)據(jù)關(guān)系映射在圖中，其中邊代表某些數(shù)據(jù)項間的關(guān)系，每條邊的權(quán)值代表項間關(guān)聯(lián)的程度。該方法避免了重復(fù)計算數(shù)據(jù)項維度屬性間的關(guān)聯(lián)程度，并在高維數(shù)據(jù)的約簡［7］方面取得了相應(yīng)進展。但是此類方法在數(shù)據(jù)集中仍存在噪聲數(shù)據(jù)，其是影響數(shù)據(jù)特征捕捉精確度的關(guān)鍵因素，并且高維數(shù)據(jù)分布在對應(yīng)的低維空間中，也會縮短噪聲數(shù)據(jù)與可用特征數(shù)據(jù)之間的距離，從而降低挖掘數(shù)據(jù)的價值。因此，在研究高維數(shù)據(jù)特征約簡過程中，粒計算理論［8］應(yīng)運而生，其將輸入的原始高維數(shù)據(jù)集分割成包含多個信息粒的小數(shù)據(jù)集，同時通過粒計算理論對大規(guī)模高維數(shù)據(jù)進行預(yù)處理。粒計算理論能夠保證數(shù)據(jù)價值，且精準捕捉數(shù)據(jù)特征，從而降低數(shù)據(jù)復(fù)雜度。文獻［9］提出鄰域知識粒度概念用于評估高維數(shù)據(jù)特征的?；芰?，并將鄰域知識粒度與鄰域依賴度相結(jié)合作為啟發(fā)式函數(shù)，用于數(shù)據(jù)屬性約簡。此外，文獻［10］針對高維數(shù)據(jù)系統(tǒng)特征屬性的粒度選擇問題，分析了信息粒與粒度劃分概念，準確地反映決策系統(tǒng)中數(shù)據(jù)維度粗糙化程度，從而彌補了在大數(shù)據(jù)環(huán)境中高維數(shù)據(jù)?；瘯r僅基于論域?qū)傩赃M行約簡的不足。文獻［11］提出通過對解析式模擬與信息粒進行替換，以定義鄰域互補熵、鄰域互補條件熵，進而得到非單調(diào)性高維數(shù)據(jù)屬性?；头菃握{(diào)性高維數(shù)據(jù)屬性約簡。因此，通過粒計算理論對高維數(shù)據(jù)進行預(yù)處理，準確捕捉其數(shù)據(jù)特征成為挖掘高維數(shù)據(jù)的研究熱點。

高維數(shù)據(jù)通過?；稻S能在一定程度上提高捕捉數(shù)據(jù)特征的精確度，但是在大數(shù)據(jù)環(huán)境中數(shù)據(jù)節(jié)點的負載均衡化也一直是研究人員關(guān)注的課題。文獻［12］提出采用根據(jù)節(jié)點頻繁度不同劃分數(shù)據(jù)的負載均衡策略，通過估計節(jié)點的任務(wù)數(shù)對其進行平均分組，以解決數(shù)據(jù)傾斜、負載過重的問題。文獻［13］提出TBLB 算法，該算法結(jié)合節(jié)點能量和節(jié)點度，以形成根據(jù)路徑性能評價因子進行路徑選擇的負載平衡樹，該平衡樹能夠有效地均衡節(jié)點負載，降低節(jié)點能量消耗。目前，大部分負載均衡方法［14］在分組過程中采用貪心策略，利用計算量模型公式來預(yù)估頻繁項產(chǎn)生的負載量，將負載量大的項放在負載量總和最小的組以實現(xiàn)負載均衡，然而，計算量模型易造成節(jié)點在分布過程中所消耗的時間差異，使得算法的整體效率降低。因此，?；蟮母呔S數(shù)據(jù)特征集可以實現(xiàn)分組結(jié)果的負載均衡化，成為并行化計算思想發(fā)展過程中的主要研究方向。

大數(shù)據(jù)環(huán)境中的FP-growth 算法［15］在并行頻繁項集的挖掘執(zhí)行過程中，數(shù)據(jù)的頻繁交互需要消耗大量資源，使得內(nèi)存負載壓力較大。為此，研究人員嘗試將MapReduce 數(shù)據(jù)處理模型與FP-growth 挖掘算法相融合，提出了PFP-growth［16］算法。該算法在執(zhí)行針對頻繁項集的挖掘行為時，每個計算節(jié)點無需互相等待或進行節(jié)點間的數(shù)據(jù)交換，均為相互獨立的計算節(jié)點，從而提高頻繁項集在并行挖掘過程中的效率。文獻［17］提出MRPrePost 算法，在第一次MapReduce 任務(wù)執(zhí)行結(jié)束后得到頻繁1-項集的F-list，并生成PPC-Tree 樹，對分布在其上的多個計算節(jié)點進行頻繁項集挖掘，且該過程不需要將PPCTree 樹保存在內(nèi)存中，既提高了項集支持度的計算效率，又減少了算法在時間與空間方面的消耗。文獻［18］提出僅包含單向頻繁模式的UFP-Tree 樹，并引入被約束子樹，分別通過遞歸和非遞歸方法對指向相同端點和不同端點的路徑進行頻繁項集挖掘。以上研究旨在減少數(shù)據(jù)間交互次數(shù)且避免消耗過多資源。因此，如何減少因數(shù)據(jù)頻繁交互帶來的影響逐漸成為研究熱點。

在大數(shù)據(jù)環(huán)境下，數(shù)據(jù)挖掘效率的影響因素不僅包括數(shù)據(jù)維度及數(shù)據(jù)結(jié)構(gòu)，還包括頻繁項集緊湊化過程中的算法步驟。近年來，為簡化頻繁項集的緊湊化步驟，文獻［19］提出深度路徑優(yōu)先搜索和長度超集優(yōu)先檢驗的改進方法。該方法通過深度優(yōu)先的路徑遞歸搜索，連續(xù)完成最大頻繁候選項集的挖掘，并根據(jù)路徑長度對挖掘結(jié)果進行排序，并檢驗所挖掘的頻繁項集超集，以減少候選項集的數(shù)量和挖掘次數(shù)，從而解決在數(shù)據(jù)量大、維度高時挖掘效率低的問題。文獻［20］提出2FP-Forest 算法，該算法通過第一次完全掃描數(shù)據(jù)集得到全部1-項集和2-項集的支持度，同時充分利用2-項集的剪枝作用，使得所構(gòu)建樹的深度、寬度均比FP-Tree 樹少。此類算法通過生成最大頻繁候選項集以及縮短頻繁模式樹的構(gòu)建時間，提高頻繁項集的緊湊化程度，從而提升整體的挖掘效率，但是仍無法避免頻繁項集在剪枝過程中的冗余搜索和無效計算。因此，如何在?；蟮母呔S數(shù)據(jù)特征集中最大程度提高頻繁項集緊湊化程度仍是重要問題。

2 相關(guān)概念

定義1（N-list［21-22］）給出任意2 個（k-1）-項集XA和XB，使其均為具有相同前綴的頻繁項集，故對應(yīng)的N-list 結(jié)構(gòu)分別表示為：

k-項集XAB的N-list 定義如下：

對于任 意(x1p，y1p，z1p) ∈N-list(XA)，1 ≤p≤m，(x2q，y2q，z2q) ∈N-list(XB)，1 ≤q≤n，若滿足條件x1py2p，則將(x1p，y1p，z2q)加入到XAB的N-list 中，得到初始N-list。

定義2（JPFP-Tree 樹［23］）一種樹形數(shù)據(jù)結(jié)構(gòu)，樹中節(jié)點由節(jié)點名稱（Item-name）、節(jié)點計數(shù)（Count）、子節(jié)點列表（Children-list）組成。

定義3（空間數(shù)據(jù)庫［24-25］）由空間關(guān)系數(shù)據(jù)與對象關(guān)系數(shù)據(jù)集構(gòu)成，實現(xiàn)空間數(shù)據(jù)的數(shù)據(jù)庫化。空間數(shù)據(jù)庫的設(shè)計過程包括數(shù)據(jù)庫的邏輯結(jié)構(gòu)設(shè)計以及空間數(shù)據(jù)的集成存儲。其中，數(shù)據(jù)庫的邏輯結(jié)構(gòu)設(shè)計采用經(jīng)典的實體-聯(lián)系（Entity-Relation）圖描述現(xiàn)實地理世界，各圖層間的路徑數(shù)與數(shù)據(jù)屬性特征數(shù)成正比，具體設(shè)計如圖1 所示。

圖1 圖層間實體-聯(lián)系模型Fig.1 Entity-relation model among layers

定義4（剪枝性質(zhì)［26］）如果項集X=｛x1，x2，…，xk｝是頻繁的，?α∈X∩β∈X∩α≠β，則2-項集{α，β}一定頻繁。相反，?α∈X∩β∈X∩α≠β，如果2-項集{α，β}不是頻繁項集，則項集X也一定非頻繁。

3 PARDG-MR 算法

本文提出的PARDG-MR 算法的基本原理如下：

1）提出DGPL 策略對數(shù)據(jù)進行預(yù)處理，使得復(fù)雜的高維數(shù)據(jù)完成特征屬性的穩(wěn)定捕捉，該方法首先提出基于屬性精確度計算（Attribute Accuracy Calculation，AAC）方法和維度粒大?。―imensional Grain Size，DGS）計算的維度粒化算法（Dimensional Granulation Algorithm，DGA），其次根據(jù)各特征屬性的前綴長度，提出在?；蟮臄?shù)據(jù)集中基于負載估計（Load Estimation，LE）策略的負載均衡算法（GPL），提高數(shù)據(jù)的特征屬性捕捉精確度，從而解決劃分中節(jié)點負載不均衡的問題。

2）在數(shù)據(jù)劃分完成的基礎(chǔ)上，設(shè)計了本地PJPFP-Tree 樹存儲結(jié)構(gòu)，并構(gòu)建算法步驟并行化策略（PARM）來減少數(shù)據(jù)交互頻度，降低磁盤I/O 次數(shù)，減緩負載壓力。

3）針對候選剪枝策略，提出基于剪枝前綴推論（Pruning Prefix Lemma，PPL）的整合節(jié)點剪枝算法（PJPFP），該策略將本地生成的PJPFP-Tree 樹中的頻繁2-項集挖掘結(jié)果作為完全剪枝的剪枝條件，使得PJPFP-Tree 中不存在非潛在候選3-項集，從而增強頻繁項集緊湊化程度，實現(xiàn)算法整體速率的提高。

3.1 DGPL 策略

大數(shù)據(jù)環(huán)境下的高維數(shù)據(jù)挖掘算法在進行數(shù)據(jù)預(yù)處理時，存在以下3 個問題：

1）在數(shù)據(jù)屬性特征捕獲過程中屬性劃分通常僅基于部分相容的數(shù)據(jù)屬性，而忽略其他數(shù)據(jù)造成數(shù)據(jù)的捕獲結(jié)果不具備全局性。

2）在數(shù)據(jù)劃分過程中，無法消除噪聲數(shù)據(jù)，不能提取單個維度的屬性，使得研究不具有針對性。

3）分類后的數(shù)據(jù)集無法將數(shù)據(jù)均勻分組至各數(shù)據(jù)節(jié)點，造成數(shù)據(jù)傾斜、負載不均衡，使得算法執(zhí)行效率低。針對以上問題，本文先對數(shù)據(jù)集進行特征維度屬性粒化處理，提出DGA。針對DGA 算法處理后的數(shù)據(jù)集，提出基于LE 的GPL 算法，以實現(xiàn)在數(shù)據(jù)劃分過程中的負載均衡化。

3.1.1 DGA 算法

DGA 算法主要是進行高維數(shù)據(jù)的預(yù)處理，通過將數(shù)據(jù)特征屬性維度?；?，以準確地捕捉此類高維數(shù)據(jù)的特征，其主要分為2 個階段：

1）在高維復(fù)雜數(shù)據(jù)集中，將屬性精確度計算方法AAC 作為設(shè)置維度粒大小的參數(shù)，充分挖掘數(shù)據(jù)的質(zhì)量，以避免產(chǎn)生過多噪音數(shù)據(jù)。

定義5（AAC 方法）若數(shù)據(jù)空間中第i維度的數(shù)據(jù)點個數(shù)為N，均方差為Si，均值為μ，屬性精確度為di，則AAC 的計算如式（1）所示：

2）基于AAC 方法根據(jù)維度相關(guān)性以及總體方差定義的原理，提出維度粒大小計算方法DGS。該策略定義如下。

定義6（DGS 方法）若數(shù)據(jù)空間中的總維度數(shù)為D，各維度的屬性精度值為di，本文選取di的均值γ作為維度粒大小的選取參數(shù)，故維度粒大小的計算如式（2）所示：

證明因為，其中0

以上2 個階段實現(xiàn)了用最低的成本完成大量規(guī)模數(shù)據(jù)集?；哪繕耍蚁啾葐我坏臋?quán)重選擇算法［27］能較好地捕獲特征維度間的相關(guān)性。DGA 策略在一定程度上提高了算法的粒化效率，同時減少了數(shù)據(jù)集的維度數(shù)量，從而確保后續(xù)挖掘算法的可行性。因此，式（1）和式（2）作為維度粒大小的推理計算公式是合理的。

DGA 算法實例：設(shè)論域U={x1，x2，…，x6}表示待處理的原始數(shù)據(jù)集，其中，A={a1，a2，a3，a4}為論域U上的數(shù)據(jù)屬性，將屬性評價分為1、2、3、4、5 類，分別表示優(yōu)、良、中、合格、差，如表1 所示。

表1 原始數(shù)據(jù)集信息Table 1 Information of original dataset

對于?ai∈A，屬性a1包含的維度粒為：A1={(a1，1)，(x1，x4，x6)}，{(a1，2)，(x2，x5)}，{(a1，3)，(x3)}。屬性a2包含的維度粒為：A2={(a2，1)，(x1，x3，x5，x6)}，。屬性a3包含的維度粒為A3={(a3，1)，(x1，x2，x3，x4，x5，x6)}。屬性a4包含的維度粒為A4={（a4，2），（x2，x3，x5）}，{(a4，3)，(x4)}，{(a4，4)，(x1，x6)}。因此，可得數(shù)據(jù)集中的數(shù)據(jù)點個數(shù)N=6，屬性a1、a2、a3、a4包含的維度粒均值分別為n1=2，n2=3，n3=6，n4=2，μ=3.25，其均方 差Si分別為1.25、0.25、1.66、1.25，可得屬性精確度di分別為0.38、0.08、0.51、0.38。由定義5 可知，屬性精度均值γ=0.337 5，總維度數(shù)D=5，維度粒大小P≈2。因此，經(jīng)計算后得到的屬性{1}、{2}為數(shù)據(jù)特征屬性維度?；Y(jié)果。

3.1.2 GPL 算法

通過DGA 算法完成特征屬性維度的精確捕捉后，能夠進一步提高分組效率。GPL 算法在?；蟮臄?shù)據(jù)集中執(zhí)行一次MapReduce 任務(wù)。基于DGA算法所得的粒大小，本文根據(jù)屬性的前綴長度設(shè)計了負載估計策略LE，用于估算該粒所對應(yīng)的結(jié)構(gòu)路徑長度，并進行負載均衡化分組，以確保每組分配到相同的負載量，從而實現(xiàn)整體的負載均衡，負載估計策略LE 定義如下。

定義7（負載估計策略LE）已知k為節(jié)點在Nlist 中的位置，i為維度粒大小的取整結(jié)果，則該節(jié)點路徑長度的計算如式（3）所示：

證明對于頻繁項item 而言，假設(shè)其在N-list 中的位置為k，其中最差的結(jié)果是item 前任意k-1 項的組合在該PJPFP-Tree 樹中均有相應(yīng)的路徑，該路徑中含有item 項，且此時的路徑最多有2k-1條，空間數(shù)據(jù)庫中路徑數(shù)與維度數(shù)成正比，因此，式（3）作為路徑長度估計函數(shù)是合理的。

DGPL 策略的原理是根據(jù)DGA 算法實現(xiàn)高維特征數(shù)據(jù)的維度?；?，得到屬性精確度及數(shù)據(jù)可分析性均較高的特征屬性捕捉結(jié)果，從而克服高維數(shù)據(jù)挖掘算法的局限性。針對?；蟮目臻g數(shù)據(jù)集，DGPL 策略通過GPL 算法對頻繁1-項集進行均勻分組，生成P-list 列表，實現(xiàn)了節(jié)點的均勻分布。

算法1DGPL 策略

3.2 PARM 策略

為進一步減少數(shù)據(jù)庫的掃描次數(shù)和不必要的計算消耗，本文提出PARM 策略以生成本地模式基表樹，從而緩解因數(shù)據(jù)交互次數(shù)增多帶來的負載壓力。雖然PWARM 算法［28］省去了FP-Tree 樹和Head 表的構(gòu)建過程，但在Reduce 階段仍需統(tǒng)計Map 階段輸出的項集加權(quán)支持度。該算法因磁盤I/O 次數(shù)的增加導(dǎo)致計算速度緩慢，從而大幅降低挖掘效率。此外，基于給定項目屬性權(quán)重的方法，在項目集不斷更新過程中無法衡量項目權(quán)值，因此，在數(shù)據(jù)集研究過程中降低挖掘精度且增加了數(shù)據(jù)集的維護代價。PARM 策略在構(gòu)造完成P-list 列表后，映射存儲該列表中的頻繁1-項集至本地，再正常調(diào)用MapReduce過程。

根 據(jù)FP-growth 原 理，PARM 策略對F-list 列表中的每個項集進行映射，映射規(guī)則為：設(shè)頻繁1-項集x1={a}，x2=0sycsya，x3=，x4={e}，x5={c}，其支持度分別為7、8、5、5、4。由于列表會重復(fù)存儲大量的不頻繁項，并且讀取一個完整事務(wù)時需遍歷整個列表才能得到目標項集，這樣會占用大量的存儲空間且消耗大量的時間。因此，根據(jù)FP-growth 原理，本文設(shè)計類似FP-Tree 的樹形數(shù)據(jù)結(jié)構(gòu)PJPFP-Tree 樹。該樹在Reduce 階段通過與P-list 列表映射構(gòu)造得出，此步驟避免統(tǒng)計Map 階段輸出集合的過程，并相對提高算法的性能。

定義8（PJPFP-Tree 樹）是具有N(N≥0)個節(jié)點的有限集合，當(dāng)N=0 時，稱為空樹。在任意一棵非空樹中應(yīng)滿足以下2 個條件：1）有且僅有一個名為null的節(jié)點作為根；2）當(dāng)N>1 時，其余每1 個節(jié)點均由頻繁1-項集節(jié)點名稱（Frequent 1-Itemset）和該節(jié)點支持度兩部分組成。

該樹作為一種邏輯結(jié)構(gòu)，同時也是一種M(M=2)層的分層結(jié)構(gòu)，具有以下2 個特點：1）該樹的根節(jié)點沒有前驅(qū)節(jié)點；2）樹中除根節(jié)點外的其他所有節(jié)點僅以根節(jié)點為其前驅(qū)節(jié)點，且此類節(jié)點均沒有后繼節(jié)點。

生成PJPFP-Tree 樹的目的是在本地磁盤中加快頻繁1-項集的合并速度，使其作為挖掘局部2-項集的本地模式基，同時大規(guī)模減少數(shù)據(jù)交互頻度，從而緩解負載壓力。相比PWARM 算法的挖掘過程，PARDG-MR 算法中的并行化實現(xiàn)僅基于頻繁項集挖掘過程中的Reduce 階段，根據(jù)分組完成后的Plist 列表及在頻繁項集生成過程中，該階段構(gòu)造得到本地頻繁模式基PJPFP-Tree 樹，并有效利用分組完成后的數(shù)據(jù)，避免內(nèi)存溢出。該過程不存在冗余步驟，為大數(shù)據(jù)環(huán)境下高維數(shù)據(jù)的挖掘應(yīng)用提供了優(yōu)勢。

3.3 PJPFP 策略

在大數(shù)據(jù)背景下生成的FP-Tree 樹規(guī)模較大，導(dǎo)致大部分算法忽略了在FP-Tree 樹中進行項集剪枝時帶來的內(nèi)存耗費，從而造成不完全剪枝，且頻繁項集緊湊化程度低。因此，在利用PARM 策略構(gòu)造完成本地PJPFP-Tree 樹后，本節(jié)提出PJPFP 策略，將PJPFP-Tree 樹中的頻繁2-項集結(jié)果作為挖掘局部2-項集的本地模式基，該策略既考慮了減少再次掃描數(shù)據(jù)集的時間成本，又使得后續(xù)生成的項集中不存在非潛在候選3-項集。

PJPFP 策略主要分為2 個步驟：1）提出剪枝前綴推論PPL，同時利用PPL 刪除可能產(chǎn)生頻繁2-項集的頻繁1-項集，并在后續(xù)剪枝過程中將該推論作為(k-1)項集階段的剪枝標準，進而達到后續(xù)被整合的節(jié)點中不包含非潛在候選k-項集的目的；2）基于上述挖掘結(jié)果，根據(jù)頻繁模式的支持度對其進行降序排列。

定義9（剪枝前綴推論PPL）如果項集{α，β，γ}為非頻繁項集，則以其為前綴的所有項集均為非頻繁項集。

證明根據(jù)剪枝定理可知，?α∈X∩β∈X∩α≠β，如果2-項集{α，β}不是頻繁項集，則項集X也一定是非頻繁項集，即若{α，β，γ}為非頻繁項集，則以項集{α，β，γ}為前綴的子集或超集，均是非頻繁項集。

為更清晰地描述該推論，本節(jié)給出數(shù)據(jù)集I，1-項集和2-項集的支持度如表2 所示。

表2 1-項集和2-項集的支持度Table 2 Support degree of 1-item set and 2-item set

根據(jù)表1 的數(shù)據(jù)集統(tǒng)計結(jié)果，令數(shù)據(jù)集I 的支持度min_sup=3。根據(jù)本節(jié)提出的剪枝推論PPL 可推論得出應(yīng)同時刪除項目F，其他項目按降序排列，可得結(jié)果I′={D，A，B，E，C}。執(zhí)行過程代碼如下：

3.4 PARDG-MR 算法

PARDG-MR 算法主要分為以下4 個步驟。

步驟1輸入原始數(shù)據(jù)，通過式（1）和式（2）確定維度粒的大小，完成數(shù)據(jù)特征屬性的精確捕捉。

步驟2執(zhí)行MapReduce 任務(wù)，根據(jù)式（3）計算屬性前綴長度，實現(xiàn)負載均衡分組，生成包含頻繁1-項集的P-list 列表。

步驟3通過PARM 方法將P-list 列表中的頻繁1-項集作為PJPFP-Tree 樹的頻繁2-項集模式基。

步驟4利用PJPFP 策略實現(xiàn)后續(xù)頻繁項集的緊湊化，從而完成全局頻繁項集的挖掘。

3.5 算法的復(fù)雜度分析

3.5.1 時間復(fù)雜度分析

PARDG-MR 算法由頻繁1-項集的均勻分組、生成本地頻繁模式基PJPFP-Tree 樹和頻繁項集的并行挖掘過程3 個部分組成，因此將本文算法3 個階段的時間復(fù)雜度分別記為和。

在對高維數(shù)據(jù)進行特征屬性捕捉及獲得頻繁1-項集P-list 的過程中，本文算法需要獲得各個記錄的數(shù)據(jù)項中每個維度的屬性值，例如每條項集包含的維度數(shù)是N，記錄數(shù)是M，即在每條項集維度屬性值獲取過程中的時間復(fù)雜度為：

在對頻繁1-項集進行均勻分組，生成本地頻繁模式基PJPFP-Tree 樹時，該步驟僅需在本地完成即可。因此，假設(shè)P-list 的長度為P，目標分組產(chǎn)生的數(shù)量為N，則該階段的時間復(fù)雜度為：

在頻繁項集的并行挖掘過程中，時間復(fù)雜度的計算主要包含同一前綴的頻繁（k-1）-項集合并成頻繁k-項集的過程。假設(shè)頻繁1-項集P-list={I1，I2，…，In}，以項Ii作為結(jié)尾的頻繁（k-1）-項集的結(jié)構(gòu)長度為Li，則其時間復(fù)雜度為：

因此，PARDG-MR 算法的時間復(fù)雜度為：

在PWARM 算法中，第一階段的時間復(fù)雜度基本一致，但在后續(xù)分組過程中需要多次掃描數(shù)據(jù)庫，依次比較列表間的元素，可得其時間復(fù)雜度為：

3.5.2 空間復(fù)雜度分析

PARDG-MR 算法的空間復(fù)雜度是通過計算頻繁項集、P-list 列表和頻繁模式基樹存儲所需空間的總和。其中，采用模糊屬性維度?；椒ㄊ沟酶鱾€節(jié)點的任務(wù)量基本相同，使得頻繁項集列表結(jié)構(gòu)規(guī)模大致相似。假設(shè)每個分組結(jié)果中平均有g(shù)k個頻繁k-項集，其中每個頻繁k-項集均占b1Byte，故頻繁k-項集P-list的長度均值為Lk。頻繁k-項集的每個P-list結(jié)構(gòu)占b2Byte，因此P-list 結(jié)構(gòu)的空間復(fù)雜度為，然而模式基樹存儲所需要的空間只由頻繁1-項集決定，其空間復(fù)雜度為O(b1×Lk！)，則PARDG-MR 算法的空間復(fù)雜度為：

PWARM 算法在構(gòu)建加權(quán)FP-Tree 樹時，通常會導(dǎo)致每組節(jié)點間存在不均衡負載的問題，且在算法的復(fù)雜度評估過程中一般選取最差的結(jié)果作為衡量算法復(fù)雜度的指標。因此假設(shè)分組結(jié)果中節(jié)點最多有g(shù)max個頻繁k-項集，則PWARM 算法的空間復(fù)雜度為：

在大數(shù)據(jù)背景中，加權(quán)FP-Tree 樹的構(gòu)建遠大于P-list 列表和模式基樹所占的存儲空間，因此，PARDG-MR 算法的空間復(fù)雜度小于PWARM 算法。

4 實驗與結(jié)果分析

4.1 實驗環(huán)境

本文實驗硬件方面包含4 個節(jié)點，其中1 個主節(jié)點，3 個輔助節(jié)點。4 個節(jié)點的CPU 來自AMD Ryzen 7，其中CPU 包含8 個處理單元，內(nèi)存均是16 GB。實驗采用的4 個計算節(jié)點都屬于同一局域網(wǎng)，均由200 Mb/s 的以太網(wǎng)互相連接。在軟件方面，計算節(jié)點安裝的均是2.7.4 版本的Hadoop 以及1.8.0版本的JDK，其所用的操作系統(tǒng)是Ubuntu 16.04 版本。各節(jié)點的配置如表3 所示。

表3 實驗中各節(jié)點的基礎(chǔ)配置Table 3 Basis configuration of each node in the experiment

4.2 實驗數(shù)據(jù)集

PARDG-MR 算法使用的3 個實驗數(shù)據(jù)集均來自標準數(shù)據(jù)庫，分別為Gisette 數(shù)據(jù)集、NDC 數(shù)據(jù)集和Webdocs 數(shù)據(jù)集，數(shù)據(jù)集信息如表4 所示。其中Gisette 數(shù)據(jù)集中包含手寫數(shù)字識別問題的數(shù)據(jù)，該數(shù)據(jù)集樣本數(shù)量為6 000，其特征數(shù)為5 000，具有數(shù)據(jù)量小、特征維度大的特點；NDC 數(shù)據(jù)集中均為正態(tài)分布集群數(shù)據(jù)，該數(shù)據(jù)集樣本容量為100 000，維度為32，具有數(shù)據(jù)量大、特征維度適中的特點，具有較強的代表性；Webdocs數(shù)據(jù)集中包含1 692 082 條Web 文檔數(shù)據(jù)，每條數(shù)據(jù)包含5 267 656 條不同屬性，是一組數(shù)據(jù)量大、特征維度較大的數(shù)據(jù)集合。

表4 實驗數(shù)據(jù)集信息Table 4 Information of experimental datasets

4.3 評價指標

為評估PARDG-MR 算法的運算效率，本文采用加速比作為算法性能的衡量指標。加速比［29］是指在相同任務(wù)量的情況下，使用單一處理器進行運算與使用多個處理器運算所消耗時間的比值。加速比較大，則說明算法在并行計算過程中所消耗的時間越少，挖掘效率越高。

4.4 PARDG-MR 算法可行性分析

本節(jié)通過對比算法的加速比，驗證PARDG-MR 算法挖掘執(zhí)行的可行性。本文分別選取最小支持度閾值為1 000、3 000 和5 000，在不同的支持度閾值下將PARDG-MR算法分別應(yīng)用在數(shù)據(jù)集上，并單獨執(zhí)行15次，獲得15次結(jié)果的平均值。在不同數(shù)據(jù)集上PARDG-MR算法的加速比對比如圖2 所示。

圖2 在不同數(shù)據(jù)集上PARDG-MR 算法的加速比對比Fig.2 Acceleration rate comparison of PARDG-MR algorithm on different datasets

從圖2 可以看出，在支持度不小于3 000 的情況中，PARDG-MR 算法在數(shù)據(jù)量大、維度數(shù)高的數(shù)據(jù)集環(huán)境上執(zhí)行時，會產(chǎn)生較高的加速比；相反，在類似NDC 的小數(shù)據(jù)集中執(zhí)行時，其加速比增量趨于平穩(wěn)，而在Webdocs 的大規(guī)模數(shù)據(jù)集上執(zhí)行時，隨著節(jié)點數(shù)量的增加，加速比呈上升趨勢。當(dāng)支持度值為5 000 時，PARDG-MR 算法在同一數(shù)據(jù)集各節(jié)點的加速比相較于該數(shù)據(jù)集中前一節(jié)點的加速比分別提升了0.91 和0.99，其原因是在數(shù)據(jù)量較小、數(shù)據(jù)維度較低時，現(xiàn)有的數(shù)據(jù)量不能將集群處理的數(shù)據(jù)量最大化，此時將數(shù)據(jù)劃分至各節(jié)點反而會增大時間開銷。然而在大數(shù)據(jù)環(huán)境下，算法優(yōu)化的關(guān)鍵在于能夠完成數(shù)據(jù)集有效降維以及頻繁項集準確合并，在一定程度上能夠減少算法在數(shù)據(jù)集中的掃描次數(shù)，并提高算法整體的挖掘性能。在大規(guī)模高維度數(shù)據(jù)集上，PARDG-MR算法的挖掘加速比差距接近最大值1，說明該算法具有較強的全局挖掘潛力。實驗結(jié)果表明，PARDG-MR 算法能夠適用于大數(shù)據(jù)背景中高維數(shù)據(jù)頻繁項集的挖掘。

4.5 挖掘性能對比

本文分別在3 個實驗數(shù)據(jù)集上進行多次對比實驗，在算法挖掘過程中將其與PWARM、PFP-growth、MRPrePost 算法的運行時間分別進行對比。

為驗證PARDG-MR 算法的有效性，本文分別在Webdocs、Gisette、NDC 這3 個數(shù)據(jù)集上將PARDGMR、PWARM、PFP-growth、MRPrePost 算法的運行時間進行對比，如圖3 所示。在獨立運行15 次后對其平均值進行分析，通過對比運行時間，評估PARDG-MR 算法的性能。

從圖3 可以看出，相比PFP-growth 和PWARM算法，PARDG-MR 算法在3 個數(shù)據(jù)集上的整體執(zhí)行時間均有不同程度的減少，其性能表現(xiàn)最佳。在NDC 數(shù)據(jù)集上PARDG-MR 算法的運行時間下降幅度最大，相比Webdocs 數(shù)據(jù)集和Gisette 數(shù)據(jù)集，其運行時間分別下降了20%和64%。在Gisette 數(shù)據(jù)集上PARDG-MR 算法的運行時間下降幅度持續(xù)穩(wěn)定，保持為6%。相比PWARM 算法在NDC 數(shù)據(jù)集中3 種支持度下的執(zhí)行時間，PARDG-MR 算法分別減少了28%、24%和38%。相比PFP-growth 算法在Gisette 數(shù)據(jù)集中3 種支持度下的執(zhí)行時間，PARDG-MR 算法分別減少了28%、17%、15%。執(zhí)行時間減少的原因在于PARDG-MR 算法在進行頻繁項集挖掘的分組過程中先進行了負載均衡化，并且在構(gòu)建頻繁模式基樹時，將冗長的項集結(jié)構(gòu)通過合并方法轉(zhuǎn)化為辨識度較高的樹結(jié)構(gòu)，從而大幅縮短了運算時間。PWARM 算法在獲得頻繁項集的過程中首先生成了加權(quán)FP-tree 樹，同時生成加權(quán)節(jié)點，該過程消耗了大部分時間；而PFP-growth 算法在生成頻繁項集的過程中需要多次掃描數(shù)據(jù)集，通過遞歸的形式構(gòu)建頻繁模式樹，從而產(chǎn)生大量的計算開銷。由于PARDG-MR 算法的運行時間在NDC 數(shù)據(jù)集上的下降幅度最大，該算法對于數(shù)據(jù)量大、維度高的數(shù)據(jù)適應(yīng)能力最強，其在降低數(shù)據(jù)維度規(guī)模的同時利用頻繁模式基結(jié)構(gòu)加速節(jié)點的合并，避免了無效計算，在一定程度上提高了算法的挖掘執(zhí)行效率，且降低了算法的運行時間。

圖3 不同算法的執(zhí)行時間對比Fig.3 Running time comparison among different algorithms

5 結(jié)束語

本文提出基于維度粒化的并行挖掘算法。通過設(shè)計DGPL 策略對高維數(shù)據(jù)進行預(yù)處理，以解決高維數(shù)據(jù)特征屬性捕捉困難以及節(jié)點負載不均勻的問題。為進一步提升運行效率，提出PARM 策略，在本地映射頻繁1-項集列表上構(gòu)建生成本地PJPFP-Tree樹，以加快節(jié)點合并速度、減少數(shù)據(jù)交互頻度并降低負載壓力。在此基礎(chǔ)上，將頻繁2-項集作為完全剪枝的剪枝條件，構(gòu)建PJPFP 策略，從而增強頻繁項集緊湊化程度，同時降低內(nèi)存消耗。在Webdocs、NDC、Gisette 3 個數(shù)據(jù)集上的實驗結(jié)果驗證了PARDG-MR 算法的有效性，相比PFP-growth、PWARM 等算法，PARDG-MR 算法的挖掘效果更佳，能夠提高挖掘效率。后續(xù)將利用維度間的相關(guān)性保留用戶更感興趣的關(guān)聯(lián)規(guī)則信息，以提高數(shù)據(jù)挖掘結(jié)果的實用性。