葉得學(xué)

（蘭州工商學(xué)院 信息工程學(xué)院，甘肅 蘭州 730101）

目前關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘已憑借自身的優(yōu)勢(shì)廣泛應(yīng)用于零售、醫(yī)療、工業(yè)等多種領(lǐng)域，這在推動(dòng)互聯(lián)網(wǎng)數(shù)據(jù)分析有著極其重要的價(jià)值［1-3］。數(shù)據(jù)挖掘技術(shù)在信息化時(shí)代背景下具有不可忽視的作用，而關(guān)聯(lián)規(guī)則挖掘則是數(shù)據(jù)領(lǐng)域中極其重要的環(huán)節(jié)。常見的數(shù)據(jù)挖掘算法為深度優(yōu)先算法（Equivalence Class Transformation；Eclat）、Apriori、K-Means 等算法，但每種數(shù)據(jù)挖掘算法均具有各自的缺陷和優(yōu)點(diǎn)。BEcla（tBitSetEclat）算法是在Eclat 算法的基礎(chǔ)上通過位存儲(chǔ)機(jī)制優(yōu)化數(shù)據(jù)組，DEcla（tDeep Eclat）算法采用深度剪枝壓縮候選項(xiàng)集規(guī)模，結(jié)合兩種優(yōu)化策略的BDEclat 算法能夠明顯提升算法的運(yùn)行效率［4］。同時(shí)，分布式并行計(jì)算系統(tǒng)因其較好的開源性和可移植性在關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘中有著一定的成果。鑒于此，研究構(gòu)建一個(gè)融合BDEclat 的并行關(guān)聯(lián)規(guī)則算 法（Balance Parallel Eclat，BPEclat）和 改 進(jìn) 的K-Means 算法（K-Means++）的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘模型，旨在為數(shù)據(jù)挖掘理論的創(chuàng)新和發(fā)展注入活力。

1 面向BPEclat 和K-Means++算法的數(shù)據(jù)挖掘

1.1 BDEclat 關(guān)聯(lián)規(guī)則算法設(shè)計(jì)

BPEclat 并行關(guān)聯(lián)規(guī)則優(yōu)化算法是在Spark分布式計(jì)算機(jī)框架下進(jìn)行對(duì)BDEclat 算法并行化處理得到的。BDEclat 改進(jìn)算法是在Eclat 算法的基礎(chǔ)上，通過位存儲(chǔ)機(jī)制策略和深度剪枝策略進(jìn)行優(yōu)化。對(duì)于存儲(chǔ)機(jī)制，研究通過二進(jìn)制儲(chǔ)存儲(chǔ)機(jī)制完成垂直列表存儲(chǔ)事務(wù)記錄的優(yōu)化，每條記錄存儲(chǔ)方式為一個(gè)BitSet 二進(jìn)制矢量對(duì)象，出現(xiàn)和未出現(xiàn)的事務(wù)分別標(biāo)記為True 和False。傳統(tǒng)Eclat 算法存儲(chǔ)事務(wù)記錄位置的形式為矩陣或數(shù)據(jù)集合，記錄類型為Int 整型數(shù)據(jù)類型。BDEclat 算法則在對(duì)應(yīng)事務(wù)出現(xiàn)的地方以True 或False 表示，且每一個(gè)True 或False 存儲(chǔ)數(shù)據(jù)為1 位。改進(jìn)后BDEclat 算法對(duì)單個(gè)事務(wù)記錄的存儲(chǔ)需求為1Bit，這極大降低算法運(yùn)行過程中內(nèi)存的占用。值得一提的是，隨著事務(wù)記錄存儲(chǔ)方式的變化，兩個(gè)項(xiàng)集連接的交集操作也轉(zhuǎn)變?yōu)槎M(jìn)制對(duì)象的“與”操作。除此之外，項(xiàng)目支持度計(jì)算可利用Cardinality函數(shù)直接獲得True 的位數(shù)。圖1 表示改進(jìn)關(guān)聯(lián)規(guī)則算法前后存儲(chǔ)結(jié)構(gòu)的情況。

圖1 改進(jìn)關(guān)聯(lián)規(guī)則算法前后存儲(chǔ)結(jié)構(gòu)的情況

對(duì)深度剪枝策略，研究分為預(yù)剪枝、約束剪枝、后剪枝三個(gè)階段。當(dāng)兩個(gè)項(xiàng)集k-1生成k項(xiàng)集，當(dāng)兩個(gè)項(xiàng)集的前k-2項(xiàng)存在差異時(shí)，則新產(chǎn)生的項(xiàng)集為從前產(chǎn)生的非頻繁或重復(fù)的項(xiàng)集。對(duì)于約束剪枝，在Ck超集中某個(gè)k-項(xiàng)集x，則任意(k+1)-項(xiàng)集均為非頻繁項(xiàng)集。對(duì)后剪枝，假如Lk-1項(xiàng)集中存在事務(wù)i，要使i在全部頻繁項(xiàng)集Lk-1中的出現(xiàn)次數(shù)低于k-1次，則涵蓋i的項(xiàng)集構(gòu)成的Ck都是非頻繁的。

BDEclat 算法的基本流程如圖2 所示。BDEclat算法可分為數(shù)據(jù)預(yù)處理階段和頻繁項(xiàng)集生成階段。數(shù)據(jù)預(yù)處理階段可將事務(wù)庫(kù)中結(jié)構(gòu)轉(zhuǎn)變?yōu)榇怪睌?shù)據(jù)結(jié)構(gòu)，進(jìn)而產(chǎn)生候選1-項(xiàng)集C1。頻繁項(xiàng)集生成階段是將C1通過雙層循環(huán)完成所有項(xiàng)目頻繁項(xiàng)集的迭代。

圖2 BDEclat 算法的基本流程

1.2 BPEclat 并行關(guān)聯(lián)規(guī)則優(yōu)化算法

盡管BDEclat 算法能夠顯著提升算法的運(yùn)行效率，但這種串行關(guān)聯(lián)規(guī)則算法無法完成多維、冗雜、異構(gòu)的數(shù)據(jù)挖掘［5-7］。研究在Spark 分布式計(jì)算框架的基礎(chǔ)上實(shí)現(xiàn)并行化處理，主要通過算法的執(zhí)行順序和合理的數(shù)據(jù)分區(qū)策略。相較于串行計(jì)算，并行計(jì)算可借助多個(gè)計(jì)算資源在相同時(shí)間完成計(jì)算任務(wù)，在時(shí)間運(yùn)行方面具有突出的優(yōu)勢(shì)［8-9］。但并非所有的任務(wù)均能實(shí)現(xiàn)并行化處理，并行計(jì)算需具備以下特點(diǎn)。對(duì)于并行資源來說，并行計(jì)算需具備相似的軟件和硬件資源配置的處理機(jī)，如多計(jì)算機(jī)集群和多核CPU。除此之外，還需并行編程和具備并行能力的任務(wù)。在數(shù)據(jù)分區(qū)策略中，BPEclat 算法能解決因前綴項(xiàng)數(shù)據(jù)差異造成的數(shù)據(jù)傾斜，研究從兩個(gè)階段實(shí)現(xiàn)數(shù)據(jù)均衡分區(qū)。在水平數(shù)據(jù)集生成頻繁項(xiàng)集階段時(shí)，該算法會(huì)依據(jù)每條事務(wù)數(shù)據(jù)產(chǎn)生頻繁項(xiàng)集的計(jì)算量來完成數(shù)據(jù)分配。每條事務(wù)的計(jì)算量用式（1）表示。

式（1）中，γ1是指每條事物數(shù)據(jù)的計(jì)算量，ti是指第i條事務(wù)中的項(xiàng)目數(shù)。在完成計(jì)算量統(tǒng)計(jì)之后，依據(jù)大小完成降序排序。接著計(jì)算節(jié)點(diǎn)個(gè)數(shù)和步長(zhǎng)，并依據(jù)步長(zhǎng)劃分?jǐn)?shù)據(jù)。

在完成數(shù)據(jù)的前綴劃分后，需根據(jù)隨機(jī)抽樣結(jié)果確定前綴權(quán)重，并各個(gè)前綴平均發(fā)放給不同的計(jì)算節(jié)點(diǎn)。具體步驟如下：首先確定分區(qū)采樣順利完成。設(shè)置樣本數(shù)據(jù)容量為G，依據(jù)key對(duì)父分區(qū)數(shù)據(jù)抽樣，通過比較分區(qū)采樣量g和平均采樣率e判斷數(shù)據(jù)是否出現(xiàn)傾斜。當(dāng)數(shù)據(jù)出現(xiàn)傾斜，則重新進(jìn)行采樣；否則，可視為采樣順利完成。

式（2）中，M表示節(jié)點(diǎn)數(shù)量，擴(kuò)容系數(shù)用k指代，分區(qū)用l指代，分區(qū)l記錄的總數(shù)量用Pl指代，g是指分區(qū)采樣量，g l是指分區(qū)l的采樣量。其次，計(jì)算樣本各key值的權(quán)重Wil，接著對(duì)采樣數(shù)據(jù)依據(jù)權(quán)重完成排序，得到總權(quán)重和分區(qū)步長(zhǎng)step，再對(duì)數(shù)據(jù)完成循環(huán)采樣，當(dāng)累計(jì)權(quán)重超過步長(zhǎng)的上限，則將累加前的數(shù)據(jù)都劃分到該分區(qū)，同時(shí)分配相應(yīng)的標(biāo)號(hào)。最后，依據(jù)采樣劃分結(jié)果完成對(duì)父分區(qū)結(jié)果進(jìn)行劃分，需確保節(jié)點(diǎn)間數(shù)據(jù)分布均衡，也保證相似數(shù)據(jù)在相同節(jié)點(diǎn)。

式（3）中，分區(qū)l采樣key集合用指代，k il是指l分區(qū)key值為i的個(gè)數(shù)，分區(qū)的個(gè)數(shù)為V。研究所使用的分布式集群為Hadoop 集群和Spark 集群。Hadoop 集群需修改mapred-site.xml 文件、hdfs-site.xml 文件、core-site.xml 文件、slave 文件。Spark 集群使用的版本為2.1.3，需修改spark-env.sh 文件和slaves。

1.3 面向BPEclat 和K-Means++算法的數(shù)據(jù)挖掘

鑒于BPEclat 關(guān)聯(lián)規(guī)則算法處理的數(shù)據(jù)類型為同源同結(jié)構(gòu)的離散數(shù)據(jù)，研究構(gòu)建一種結(jié)合BPEclat 和K-Means++算法的數(shù)據(jù)挖掘方法，K-Means++算法對(duì)單個(gè)或多個(gè)指標(biāo)狀態(tài)變量和操作變量進(jìn)行數(shù)據(jù)聚類處理，BPEclat 能完成關(guān)聯(lián)規(guī)則挖掘，進(jìn)而獲取聚類結(jié)果包含的潛在知識(shí)。圖3表示結(jié)合BPEclat 和K-Means++算法的數(shù)據(jù)挖掘。

圖3 面向BPEclat 和K-Means++算法的數(shù)據(jù)挖掘

K-Means 聚類算法是在開始聚類處理前在所有樣本點(diǎn)挑選K個(gè)樣本點(diǎn)作為第一階段聚類的中心，然后將其余數(shù)據(jù)放到離簇中心距離最短的簇中，最終利用不斷移動(dòng)中心的迭代方法來劃分簇。但K-Means 聚類算法的準(zhǔn)確性和快速性達(dá)不到要求、初始化均值具有隨機(jī)性、算法容易陷于局部最優(yōu)解、對(duì)初始條件具有很強(qiáng)的依賴性。對(duì)于狀態(tài)變量的操作，研究所使用的K-Means++算法通過初始化聚類中心的選擇方式減少計(jì)算量，具體的過程如下。其一，隨機(jī)選取一個(gè)初始聚類中心，計(jì)算每個(gè)點(diǎn)到聚類中心的距離B(x)。其二，依據(jù)概率重新選擇聚類中心，重復(fù)以上步驟找到初始聚類中心K個(gè)。其三，計(jì)算每個(gè)樣本與每個(gè)質(zhì)心間的距離B，并將所有樣本劃分到相似度最高的Ci中。其四，再次計(jì)算每類Ci的質(zhì)心和樣本到新聚類中心的距離，并劃分到新的類中，當(dāng)達(dá)到最大迭代次數(shù)或質(zhì)心不變時(shí)，則判斷準(zhǔn)則函數(shù)收斂。其五，最終獲得樣本數(shù)據(jù)的類別和K個(gè)聚類中心。準(zhǔn)則函數(shù)的計(jì)算公式為式（4）所示。

式（4）中，數(shù)據(jù)庫(kù)中所有對(duì)象空間中的一點(diǎn)用A指代，聚類Ci的均值用mi指代，每個(gè)對(duì)象和對(duì)應(yīng)聚類中心的平方誤差總和用E指代。樣本被選定為聚類中心的概率的計(jì)算公式為式（5）。

式（5）中，B(x)是指數(shù)據(jù)之間的相似性，通過多種距離公式計(jì)算得到，研究采用歐幾里得距離計(jì)算公式。

在數(shù)據(jù)挖掘之前，研究還需對(duì)操作變量進(jìn)行歸一化和離散化處理。數(shù)據(jù)正態(tài)分布情況如圖4（a）所示，相應(yīng)區(qū)間內(nèi)數(shù)值分布的概率不同，但該圖不能體現(xiàn)數(shù)據(jù)信息的多樣性。研究使用方差準(zhǔn)則對(duì)數(shù)據(jù)進(jìn)行離散，示意圖如圖4（b）所示。數(shù)據(jù)被分為三個(gè)部分，分割點(diǎn)為均數(shù)-方差和均數(shù)+方差。

圖4 數(shù)據(jù)正態(tài)分布情況和1σ 準(zhǔn)則示意圖

2 關(guān)聯(lián)規(guī)則算法性能測(cè)試和數(shù)據(jù)挖掘應(yīng)用效果分析

2.1 BPEclat 關(guān)聯(lián)算法性能測(cè)試

研究利用常見的關(guān)聯(lián)規(guī)則算法測(cè)試數(shù)據(jù)集分析BPEclat 關(guān)聯(lián)算法的性能，數(shù)據(jù)集包括Mushroom 和Chess 兩種數(shù)據(jù)集，對(duì)比算法為基于Spark 的Eclat 算法，即SPEclat 算法，設(shè)置最小支持度為0.05。Mushroom 數(shù)據(jù)集的項(xiàng)目個(gè)數(shù)、事務(wù)個(gè)數(shù)分別為119 個(gè)、8124 個(gè)，Chess 數(shù)據(jù)集相應(yīng)的特征分別為75 個(gè)和3196 個(gè)。Mushroom 和Chess兩種數(shù)據(jù)集的平均事務(wù)長(zhǎng)度分別為23 和37。圖5（a）和5（b）分別表示Mushroom 數(shù)據(jù)集 和Chess 數(shù)據(jù)集下兩種并行關(guān)聯(lián)規(guī)則優(yōu)化算法在6個(gè)節(jié)點(diǎn)下運(yùn)行時(shí)間。從圖5 中可知，Mushroom 和Chess 兩種數(shù)據(jù)集下SPEclat 算法節(jié)點(diǎn)間的運(yùn)行時(shí)間差值范圍分別為0.8-8.1 s、2.3-7.8 s，相應(yīng)數(shù)據(jù)集下BPEclat 算法的相應(yīng)取值范圍分別為0.1-2.6 s、0.2-2.2 s。這是因?yàn)镾PEclat 算法沒有考慮負(fù)載均衡，各個(gè)節(jié)點(diǎn)間的任務(wù)分配出現(xiàn)差異較大的情況；而BPEclat 算法通過均衡策略能較好地分配數(shù)據(jù)的計(jì)算量，各個(gè)節(jié)點(diǎn)的完成時(shí)間相差很小。

圖5 不同數(shù)據(jù)集下兩種并行關(guān)聯(lián)規(guī)則優(yōu)化算法的運(yùn)行時(shí)間對(duì)比

研究接著設(shè)置數(shù)據(jù)規(guī)模分別為20 G 和30 G，節(jié)點(diǎn)數(shù)分別為2、4、6，通過加速比驗(yàn)證兩種并行關(guān)聯(lián)規(guī)則優(yōu)化算法的并行化性能。圖6（a）和圖6（b）分別表示Mushroom 數(shù)據(jù)集兩種并行關(guān)聯(lián)規(guī)則優(yōu)化算法在30 G 和20 G 下的加速比。當(dāng)節(jié)點(diǎn)數(shù)為6個(gè)時(shí)，Mushroom 數(shù)據(jù)集中BPEclat 算法和SPEclat算法在30 G 的加速比分別為5.18 和4.67，在20 G的加速比分別為5.78 和5.13。圖6（c）和圖6（d）分別表示Chess 數(shù)據(jù)集兩種并行關(guān)聯(lián)規(guī)則優(yōu)化算法在30 G 和20 G 下的加速比。當(dāng)節(jié)點(diǎn)數(shù)為6 個(gè)時(shí)，Chess 數(shù)據(jù)集中BPEclat 算法和SPEclat 算法在30 G 的加速比分別為4.78 和4.12，在20 G 的加速比分別為5.31 和5.14。整體來看，隨著節(jié)點(diǎn)數(shù)量的增加，不同數(shù)據(jù)集下兩種關(guān)聯(lián)規(guī)則算法的加速比呈現(xiàn)逐漸增大的趨勢(shì)，但增加的幅度逐漸變慢。這是因?yàn)楣?jié)點(diǎn)數(shù)量的增加后，數(shù)據(jù)交換和傳輸?shù)臅r(shí)間相對(duì)增加。

圖6 兩種并行關(guān)聯(lián)規(guī)則優(yōu)化算法的并行化性能

2.2 關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘應(yīng)用效果

研究通過TE（Tennessee Eastman）過程驗(yàn)證所提出的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘模型效果，選取的體現(xiàn)系統(tǒng)運(yùn)行狀態(tài)的指標(biāo)分別為反應(yīng)器的內(nèi)部溫度參數(shù)（A）、內(nèi)部液化參數(shù)（B）、內(nèi)部壓力參數(shù)（C）。A、B、C 狀態(tài)變量的聚類中心1 分別為2723.3、74.2、120.6，聚類中心2 分別為2691.3、75.6、120.3，聚類中心3 分別為2756.3、74.5、120.4。狀態(tài)變量的影響因素為冷凝器冷卻水流量（D1）、反應(yīng)器冷卻水流量（D2）、排水閥（D3）、A 進(jìn)料量（D4）、E 進(jìn)料量（D5）、D 進(jìn)料量（D6）。通過1 方差準(zhǔn)則離散化處理六個(gè)操作變量，分割區(qū)間如表1 所示。以D1 為例，第一部分、第二部分、第三部分分別為［12.33，18.62）、［18.62，15.65）、［15.65，20.95）。

表1 六個(gè)操作變量的分割區(qū)間

設(shè)置最小支持度和最小置信度分別為0.1和0.6，研究所提出的數(shù)據(jù)挖掘模型得出，A 在臨界、正常溫度范圍內(nèi)的規(guī)則3 條規(guī)則和4 條規(guī)則；C 在正常和臨界壓力內(nèi)規(guī)則有1 條規(guī)則和57 條規(guī)則。依據(jù)得到的規(guī)則可知，反應(yīng)器溫度升高時(shí)，操作人員可適當(dāng)調(diào)整反應(yīng)器冷凝水流量。依據(jù)排氣閥的規(guī)則，反應(yīng)器的壓力較低的情況下，排放閥的開關(guān)比例較高。研究分析A 和D2 的定性關(guān)系，結(jié)果如圖7（a）所示。冷凝器冷卻水流量能降低反應(yīng)器的溫度，進(jìn)而導(dǎo)致反應(yīng)器出現(xiàn)散熱的情況，反應(yīng)器冷卻水流量和反應(yīng)器的溫度正向相關(guān)。圖7（b）表示C 和D3 的定性關(guān)系。排放閥開關(guān)比例能控制反應(yīng)器的氣體含量，進(jìn)而能夠調(diào)節(jié)反應(yīng)器的壓力。排水閥開關(guān)比例和反應(yīng)器壓力呈現(xiàn)正向相關(guān)性。

圖7 操作變量和狀態(tài)變量的定性分析

3 結(jié)論

對(duì)目前關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘技術(shù)存在的計(jì)算復(fù)雜度高、運(yùn)行效率低等問題，研究構(gòu)建了一種融合BPEclat 與K-Means++算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘模型。研究結(jié)果顯示，Mushroom 和Chess 兩種數(shù)據(jù)集下SPEclat 算法節(jié)點(diǎn)間的運(yùn)行時(shí)間差值范圍分別為0.8～8.1s、2.3～7.8 s，相應(yīng)數(shù)據(jù)集下BPEclat算法的相應(yīng)取值范圍分別為0.1～2.6 s、0.2～2.2 s。Mushroom 數(shù)據(jù)集中BPEclat 算法和SPEclat 算法的加速比最大分別為5.78 和5.13，Chess 數(shù)據(jù)集中的加速比最大分別為5.31 和5.14。關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘得到，反應(yīng)器內(nèi)部溫度在臨界、正常溫度范圍內(nèi)分別有3 條規(guī)則和4 條規(guī)則；內(nèi)部壓力參數(shù)在正常和臨界壓力內(nèi)分別有1 條規(guī)則和57 條規(guī)則。TE 應(yīng)用效果分析得出，反應(yīng)器冷卻水流量和反應(yīng)器的溫度正向相關(guān)。排水閥開關(guān)比例和反應(yīng)器壓力呈現(xiàn)正向相關(guān)性。該模型在數(shù)據(jù)挖掘領(lǐng)域具有較高的性能和擴(kuò)展性。后續(xù)研究可擴(kuò)大樣本規(guī)模驗(yàn)證研究的結(jié)論，以提高模型的適用性。