基于試驗任務(wù)相關(guān)的并行化關(guān)聯(lián)挖掘研究

何國良 雷 震 孫 巖

基于試驗任務(wù)相關(guān)的并行化關(guān)聯(lián)挖掘研究

何國良 雷 震 孫 巖

通過分析關(guān)聯(lián)挖掘和傳統(tǒng)Apriori算法的特征，設(shè)計并實現(xiàn)一種基于任務(wù)相關(guān)和布爾矩陣的并行化Apriori關(guān)聯(lián)挖掘算法。該算法通過分而治之的分布式并行計算承載平臺MapReduce進行計算，只需掃描一次數(shù)據(jù)庫，將事務(wù)數(shù)據(jù)庫轉(zhuǎn)化為布爾矩陣，僅對任務(wù)相關(guān)的項集進行連接合并與向量內(nèi)積運算，提升了Apriori算法的關(guān)聯(lián)挖掘效率。

關(guān)聯(lián)規(guī)則挖掘也稱為頻繁項集挖掘，旨在發(fā)現(xiàn)海量數(shù)據(jù)項集之間的相互關(guān)聯(lián)關(guān)系。在諸多的關(guān)聯(lián)挖掘算法中，Apriori算法是比較經(jīng)典的算法之一。該算法結(jié)合一定的先驗知識，采用逐層迭代的方法搜索頻繁項集。傳統(tǒng)的Apriori算法中，若要生成頻繁項集，就要執(zhí)行連接和剪枝，而這些連接和剪枝操作帶有一定的機械性和盲目性，會有大量冗余的候選項集生成，需要進行多次掃描數(shù)據(jù)庫操作，導(dǎo)致算法運行效率不高。

鑒于傳統(tǒng)Apriori算法的以上不足，本文提出一種基于任務(wù)相關(guān)的并行化Apriori關(guān)聯(lián)規(guī)則挖掘算法。該算法僅僅需要對數(shù)據(jù)庫進行一次掃描操作，把原始事務(wù)數(shù)據(jù)集劃分為多個數(shù)據(jù)分片，基于MapReduce并行計算平臺對各個數(shù)據(jù)分片進行計算與整合，同時將項目映射為布爾矩陣，棄除與任務(wù)無關(guān)的項集，通過連接合并與向量內(nèi)積計算，減少候選項集，以相應(yīng)并行邏輯運算代替頻繁的數(shù)據(jù)庫掃描，最終完成高效的關(guān)聯(lián)挖掘任務(wù)。

關(guān)聯(lián)規(guī)則相關(guān)定義及Apriori算法簡介

關(guān)聯(lián)規(guī)則相關(guān)定義

關(guān)聯(lián)規(guī)則相關(guān)定義如下:

（1） 關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則分析最初是用來確定事務(wù)數(shù)據(jù)庫中事務(wù)項之間的關(guān)聯(lián)關(guān)系。設(shè)I是項目的集合，X和Y都是I的子集，并且X∩Y=Ф，關(guān)聯(lián)規(guī)則是像X=＞Y這種形式的表達式。

（2）支持度（support）。是指同時包含X和Y的事務(wù)在總事務(wù)數(shù)據(jù)庫中所占的百分比，即sup（X=＞Y）=P（X∪Y）；最小支持度表示項集在統(tǒng)計意義上的最低重要性，是由用戶定義的衡量支持度的一個閾值；

（3）置信度（confidence）。是數(shù)據(jù)庫中包含項目集X的事務(wù)中出現(xiàn)項目集Y的概率，即同時包含項目集X和項目集Y的事務(wù)與只包含X的事務(wù)數(shù)的比值，是一種條件概率，即conf（X=＞Y）=P（X∪Y）/P（X）= P（Y|X）；最小置信度表示項集在統(tǒng)計意義上的最低可靠性，是由用戶定義的衡量置信度的一個閾值。

給定一個數(shù)據(jù)庫，當一條規(guī)則滿足最小支持度和最小置信度時，稱該規(guī)則為強關(guān)聯(lián)規(guī)則，也就是需要分析的關(guān)聯(lián)規(guī)則。

Apriori算法簡介

Apriori算法是一種寬度優(yōu)先算法，采用逐層搜索的迭代方法挖掘頻繁項集。在首輪迭代過程中，通過計算事務(wù)數(shù)據(jù)庫中每一個項的支持度從而找出頻繁項集。繼而在前一輪生成的頻繁k-項集的基礎(chǔ)之上，將其作為本輪的種子項集，迭代產(chǎn)生候選（k+1）-項集，計算每個候選（k+1）-項集在事務(wù)數(shù)據(jù)庫中的支持度，從而計算出所有頻繁（k+1）-項集，再將其作為下輪的種子項集，按照上述方法迭代計算候選項及頻繁項集，直到不再滿足新的頻繁項集產(chǎn)生條件時結(jié)束整個頻繁項集挖掘過程。

根據(jù)頻繁項集的定義，為了找出所有的頻繁項集，需要窮舉出一條事務(wù)中的所有項的各種組合和每種組合的支持度，找出頻繁項集。為提高項集組合的搜索效率，Apriori算法遵循了以下兩條定理:

定理1:頻繁項集的任何非空子集都是頻繁項集；

定理2:非頻繁項集的任何超集都是非頻繁項集。

任務(wù)相關(guān)

考慮到作戰(zhàn)試驗數(shù)據(jù)具有豐富的屬性類別，數(shù)據(jù)量大，維數(shù)眾多，這樣在進行上述頻繁項集提取時會有大量候選項集產(chǎn)生，其中很多候選項集對于挖掘目標而言是不相關(guān)的，且只會影響挖掘分析效率。如果初始階段就能夠瞄準挖掘目標，挖掘過程中緊密結(jié)合挖掘任務(wù)，允許用戶交互其中，通過消減掉大量與任務(wù)無關(guān)的候選項集，只產(chǎn)生與任務(wù)相關(guān)的某個子集，使得挖掘過程更加具有針對性，節(jié)省支持度計算時間和存儲項集的空間，以此來提高關(guān)聯(lián)挖掘效率。

事務(wù)項目的布爾化及向量內(nèi)積

事務(wù)項目的布爾化

事務(wù)數(shù)據(jù)庫經(jīng)過一次掃描之后，被映射為布爾向量矩陣。以下表為例，表1是數(shù)據(jù)庫片段，表2是該片段對應(yīng)的布爾向量矩陣。布爾向量中的“1”的出現(xiàn)的次數(shù)與該項目在數(shù)據(jù)庫中出現(xiàn)的次數(shù)一致。

表1 數(shù)據(jù)庫片段

表2 片段對應(yīng)布爾向量矩陣

向量內(nèi)積

關(guān)于向量空間內(nèi)積，我們并不陌生。對于任意兩個n維向量α=（x1，x2，…，x n）和β=（y1，y2，…，yn），其內(nèi)積定義為:

改進算法

可描述為（假設(shè)任務(wù)相關(guān)項個數(shù)為1）

步驟1:原始事務(wù)數(shù)據(jù)集被劃分為多個數(shù)據(jù)分片，對各個數(shù)據(jù)分片進行掃描，將其映射為一個布爾向量矩陣。

步驟2:頻繁1項集推導(dǎo)。在Map階段，對各分片中各項目中“1”的個數(shù)進行統(tǒng)計；在Reduce階段，對所有Map階段輸出的結(jié)果進行合并，獲取全局候選1-項集，并且和MinSup進行比較，輸出符合要求的頻繁1-項集。

步驟3:頻繁2項集推導(dǎo)。在Map階段，對頻繁1項集中任務(wù)相關(guān)的任意2個向量進行內(nèi)積運算，得到候選2-項集；在Reduce階段，對所有Map階段輸出的結(jié)果進行統(tǒng)計，判斷結(jié)果中“1”的個數(shù)是否滿足支持度閥值條件，如果滿足則將此2個向量組合判斷為頻繁2項集。

步驟4:頻繁k（k≥3）項集推導(dǎo)。在Map階段對前述已存在的頻繁k-1（k≥3）項集中任意兩個符合條件的任務(wù)相關(guān)項集進行連接操作，從而生成k項集，在生成結(jié)果中判斷不同的兩個項的內(nèi)積；在Reduce階段對所有Map階段輸出的結(jié)果進行合并，結(jié)果符合支持度閥值的則可繼續(xù)進行下一步，否則該k-項集不屬于頻繁k項集的考慮范疇。

步驟5:如果上述在Reduce階段符合支持度閥值的k項集的所有k-1項子集都存在于頻繁Lk-1中，那么進入下一步；如果有一項子集不存在于頻繁Lk-1中，根據(jù)性質(zhì)“非頻繁項集的任何超集都是非頻繁的”，則該k-項集也不屬于頻繁項集。

步驟6:在Map階段，對該k項集的所有任務(wù)相關(guān)項目進行內(nèi)積運算；在Reduce階段，統(tǒng)計所有Map階段的輸出結(jié)果，符合支持度閥值要求的k項集被判斷為頻繁k項集。

按照上述過程求出全部頻繁項集。

算法性能分析

本實驗采用3臺虛擬機組成集群環(huán)境，虛擬機運行在高性能刀片服務(wù)器上，該服務(wù)器支持多核英特爾?至強TM處理器5600系列。其中一臺虛擬機作為主服務(wù)器（Master），其余2臺作為從服務(wù)器（Slave）。設(shè)定每臺虛擬機的IP地址并使用48口千兆交換機互聯(lián)。

表3 Hadoop集群配置信息

首 先 在 客 戶 端Windows平 臺 下 安 裝Citrix XenCenter軟件，在該環(huán)境下創(chuàng)建虛擬機并在虛擬機上安裝CentOS操作系統(tǒng)和JDK，創(chuàng)建Hadoop用戶，配置SSH和Hadoop環(huán)境，安裝Navicat for MySQL數(shù)據(jù)庫（版本號是8.2.20）。使用Eclipse進行程序設(shè)計與調(diào)試。采用UC Irvine 機器學(xué)習(xí)數(shù)據(jù)倉庫中的mushroom數(shù)據(jù)庫作為實驗對象，該數(shù)據(jù)庫共有8124條記錄，部分記錄如圖1所示。

運行結(jié)果如圖2所示。

相比傳統(tǒng)Apriori算法，本文提出的基于試驗任務(wù)相關(guān)的并行化改進Apriori算法效率提升明顯。

圖1 mushroom數(shù)據(jù)庫（片段）

圖2 算法性能對比

結(jié)語

本文提出的基于試驗任務(wù)相關(guān)的并行化關(guān)聯(lián)挖掘算法是在傳統(tǒng)Apriori算法的基礎(chǔ)之上改進的，原始事務(wù)數(shù)據(jù)集被劃分為多個數(shù)據(jù)分片，將其映射為布爾向量矩陣，對各個數(shù)據(jù)分片分別進行掃描和并行化處理，僅需掃描一次數(shù)據(jù)庫，且通過消減掉大量與任務(wù)無關(guān)的候選項集，只產(chǎn)生與任務(wù)相關(guān)的某個子集，顯著提升了傳統(tǒng)Apriori算法的關(guān)聯(lián)挖掘效率。

何國良1雷 震2孫 巖2

1.裝甲兵工程學(xué)院裝備指揮與管理系；2.裝甲兵工程學(xué)院科研部

10.3969/j.issn.1001-8972.2015.07.001