基于MapReduce 的高維數(shù)據(jù)頻繁項(xiàng)集挖掘

趙欣燦，朱 云，毛伊敏

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

0 概述

關(guān)聯(lián)規(guī)則挖掘技術(shù)［1］是數(shù)據(jù)挖掘領(lǐng)域的重要分支之一，其旨在找出各數(shù)據(jù)項(xiàng)之間的相互關(guān)系，被廣泛應(yīng)用于社交網(wǎng)絡(luò)、精準(zhǔn)營銷等領(lǐng)域。然而，隨著動(dò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］。因此，大部分?jǐn)?shù)據(jù)挖掘技術(shù)已經(jīng)從單目標(biāo)分析擴(kuò)展為多目標(biāo)融合分析［3］。采用高效的方式準(zhǔn)確捕捉高維復(fù)雜數(shù)據(jù)的特征屬性，以及解決節(jié)點(diǎn)分布的負(fù)載均衡化問題，并有效提高頻繁項(xiàng)集的緊湊程度［4］成為研究熱點(diǎn)。

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

1 相關(guān)工作

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

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

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

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

2 相關(guān)概念

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

k-項(xiàng)集XAB的N-list 定義如下：

對(duì)于任 意(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é)點(diǎn)由節(jié)點(diǎn)名稱（Item-name）、節(jié)點(diǎn)計(jì)數(shù)（Count）、子節(jié)點(diǎn)列表（Children-list）組成。

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

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

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

3 PARDG-MR 算法

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

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

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

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

3.1 DGPL 策略

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

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

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

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

3.1.1 DGA 算法

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

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

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

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

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

證明因?yàn)椋渲?

以上2 個(gè)階段實(shí)現(xiàn)了用最低的成本完成大量規(guī)模數(shù)據(jù)集?；哪繕?biāo)，且相比單一的權(quán)重選擇算法［27］能較好地捕獲特征維度間的相關(guān)性。DGA 策略在一定程度上提高了算法的?；剩瑫r(shí)減少了數(shù)據(jù)集的維度數(shù)量，從而確保后續(xù)挖掘算法的可行性。因此，式（1）和式（2）作為維度粒大小的推理計(jì)算公式是合理的。

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

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

對(duì)于?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ù)點(diǎn)個(gè)數(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)計(jì)算后得到的屬性{1}、{2}為數(shù)據(jù)特征屬性維度?；Y(jié)果。

3.1.2 GPL 算法

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

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

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

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

算法1DGPL 策略

3.2 PARM 策略

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

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

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

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

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

3.3 PJPFP 策略

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

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

定義9（剪枝前綴推論P(yáng)PL）如果項(xiàng)集{α，β，γ}為非頻繁項(xiàng)集，則以其為前綴的所有項(xiàng)集均為非頻繁項(xiàng)集。

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

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

表2 1-項(xiàng)集和2-項(xiàng)集的支持度Table 2 Support degree of 1-item set and 2-item set

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

3.4 PARDG-MR 算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 實(shí)驗(yàn)環(huán)境

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

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

4.2 實(shí)驗(yàn)數(shù)據(jù)集

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

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

4.3 評(píng)價(jià)指標(biāo)

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

4.4 PARDG-MR 算法可行性分析

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

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

4.5 挖掘性能對(duì)比

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

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

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

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

5 結(jié)束語

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