基于試驗任務相關的并行化關聯挖掘研究

何國良 雷 震 孫 巖

基于試驗任務相關的并行化關聯挖掘研究

何國良 雷 震 孫 巖

通過分析關聯挖掘和傳統Apriori算法的特征，設計并實現一種基于任務相關和布爾矩陣的并行化Apriori關聯挖掘算法。該算法通過分而治之的分布式并行計算承載平臺MapReduce進行計算，只需掃描一次數據庫，將事務數據庫轉化為布爾矩陣，僅對任務相關的項集進行連接合并與向量內積運算，提升了Apriori算法的關聯挖掘效率。

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

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

關聯規則相關定義及Apriori算法簡介

關聯規則相關定義

關聯規則相關定義如下:

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

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

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

給定一個數據庫，當一條規則滿足最小支持度和最小置信度時，稱該規則為強關聯規則，也就是需要分析的關聯規則。

Apriori算法簡介

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

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

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

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

任務相關

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

事務項目的布爾化及向量內積

事務項目的布爾化

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

表1 數據庫片段

表2 片段對應布爾向量矩陣

向量內積

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

改進算法

可描述為（假設任務相關項個數為1）

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

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

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

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

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

步驟6:在Map階段，對該k項集的所有任務相關項目進行內積運算；在Reduce階段，統計所有Map階段的輸出結果，符合支持度閥值要求的k項集被判斷為頻繁k項集。

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

算法性能分析

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

表3 Hadoop集群配置信息

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

運行結果如圖2所示。

相比傳統Apriori算法，本文提出的基于試驗任務相關的并行化改進Apriori算法效率提升明顯。

圖1 mushroom數據庫（片段）

圖2 算法性能對比

結語

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

何國良1雷 震2孫 巖2

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

10.3969/j.issn.1001-8972.2015.07.001