何國(guó)良 雷 震 孫 巖

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

何國(guó)良 雷 震 孫 巖

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

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

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

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

關(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ù)庫(kù)中事務(wù)項(xiàng)之間的關(guān)聯(lián)關(guān)系。設(shè)I是項(xiàng)目的集合，X和Y都是I的子集，并且X∩Y=Ф，關(guān)聯(lián)規(guī)則是像X=＞Y這種形式的表達(dá)式。

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

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

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

Apriori算法簡(jiǎn)介

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

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

定理1:頻繁項(xiàng)集的任何非空子集都是頻繁項(xiàng)集；

定理2:非頻繁項(xiàng)集的任何超集都是非頻繁項(xiàng)集。

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

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

事務(wù)項(xiàng)目的布爾化及向量?jī)?nèi)積

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

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

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

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

向量?jī)?nèi)積

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

改進(jìn)算法

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

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

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

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

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

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

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

按照上述過程求出全部頻繁項(xiàng)集。

算法性能分析

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

表3 Hadoop集群配置信息

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

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

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

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

圖2 算法性能對(duì)比

結(jié)語(yǔ)

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

何國(guó)良1雷 震2孫 巖2

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

10.3969/j.issn.1001-8972.2015.07.001