關(guān)聯(lián)規(guī)則挖掘算法的多核并行優(yōu)化*

吳華平，鄭曉薇，張建強

（遼寧師范大學(xué) 計算機與信息技術(shù)學(xué)院，遼寧 大連 116081）

關(guān)聯(lián)規(guī)則挖掘算法的多核并行優(yōu)化*

吳華平，鄭曉薇，張建強

（遼寧師范大學(xué) 計算機與信息技術(shù)學(xué)院，遼寧 大連 116081）

分析了并行關(guān)聯(lián)規(guī)則挖掘算法存在的不足，提出了一種改進的關(guān)聯(lián)規(guī)則挖掘的多核并行優(yōu)化算法。該算法對Apriori算法的壓縮矩陣進行了改造，并在多核平臺下利用OpenMP技術(shù)和TBB技術(shù)對串行程序進行循環(huán)并行化和任務(wù)分配的并行化設(shè)計，最大限度地實現(xiàn)并行關(guān)聯(lián)規(guī)則挖掘。

關(guān)聯(lián)規(guī)則；Apriori算法；頻繁項集矩陣；OpenMP；TBB；多核并行

海量數(shù)據(jù)中隱藏著大量的不為人知的模式和知識，尋找有價值的數(shù)據(jù)模式和知識是數(shù)據(jù)挖掘研究的主要內(nèi)容[1]。關(guān)聯(lián)規(guī)則的挖掘是數(shù)據(jù)挖掘中的一項重要的基礎(chǔ)技術(shù)。經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法主要有Agrawal等提出的基于Apriori算法的頻繁集方法，該算法以遞歸統(tǒng)計為基礎(chǔ)，以最小支持度為依據(jù)剪切生成頻繁集。隨著數(shù)據(jù)容量的增加，為了提高關(guān)聯(lián)規(guī)則的挖掘效率，研究人員提出了并行挖掘算法[2-3]。這些并行算法都是基于MPI和機群系統(tǒng)實現(xiàn)的，雖然具有速度快、容易實現(xiàn)、要求各節(jié)點間同步次數(shù)較少等優(yōu)點，但仍然存在著可擴展性差、網(wǎng)絡(luò)通信量大、負載不平衡、處理器空轉(zhuǎn)、規(guī)則合成難度高等缺點。

目前市場上多核處理器已成為主流，比較有代表性的支持多核處理器的并行計算平臺之一的線程構(gòu)建模塊TBB（Thread Building Blocking），可以在其他多核化工具支持下對串行程序中的可并行化部分進行線程的并行化重構(gòu)，提升多核處理器平臺的效能，簡化應(yīng)用程序的并行化過程。本文針對TBB的多核并行編程的優(yōu)勢，結(jié)合OpenMP并行編程，提出了一種改進的關(guān)聯(lián)規(guī)則挖掘多核并行優(yōu)化算法。該算法對Apriori算法的壓縮矩陣進行了改造，只需掃描一次數(shù)據(jù)庫，并利用TBB技術(shù)最大限度地壓縮矩陣，使矩陣的運算規(guī)模逐步減小。它不需要Apriori算法中的自聯(lián)接和剪枝，直接通過支持矩陣行向量的按位“與”運算并行地找出頻繁集，減少了數(shù)據(jù)移動帶來的額外開銷，提高關(guān)聯(lián)規(guī)則挖掘效率。與分布式系統(tǒng)的Apriori并行算法相比，該算法采用多核TBB并行技術(shù)，不存在節(jié)點間的通信與同步、負載平衡和規(guī)則合成難度高等問題。實驗證明該算法具有高效的并行挖掘效率和較高的多核CPU利用率。

1 挖掘關(guān)聯(lián)規(guī)則的串行算法

關(guān)聯(lián)規(guī)則的核心是基于兩階段頻繁項集思想的遞推算法。發(fā)現(xiàn)頻繁項集是關(guān)聯(lián)規(guī)則挖掘應(yīng)用中的技術(shù)和步驟。支持度和置信度是關(guān)聯(lián)規(guī)則挖掘中的兩個重要指標，為了計算支持度，需要訪問數(shù)據(jù)庫。而Agrawal等人提出的挖掘關(guān)聯(lián)規(guī)則串行算法Apriori是首先掃描數(shù)據(jù)庫，計算每個數(shù)據(jù)項的支持度，并根據(jù)支持度閾值產(chǎn)生頻繁 1-項集 L1；L1用于找頻繁 2-項集 L2，L2而用于找L3，如此逐層迭代的搜索，直到不能找到頻繁k-項集。Apriori算法存在一些難以克服的缺陷：（1）可能產(chǎn)生大量的候選項集，沒有排除不應(yīng)該參與組合的元素；（2）多次掃描數(shù)據(jù)庫，大大增加系統(tǒng)的 I／O開銷，并且數(shù)據(jù)庫有些可以刪除的項或事務(wù)被多次掃描；（3）連接程序中相同的項重復(fù)較多。針對Apriori算法的缺點，參考文獻[4]將事務(wù)數(shù)據(jù)庫轉(zhuǎn)換為基于內(nèi)存的矩陣，在矩陣上找出所需的頻繁項集，從而大大減少了數(shù)據(jù)庫的掃描次數(shù)，但沒有對矩陣進行壓縮。參考文獻[5-6]對矩陣進行了壓縮，但不徹底，而且矩陣數(shù)據(jù)結(jié)構(gòu)不合理，還額外增加了轉(zhuǎn)置矩陣。

本文介紹一種改進的基于Apriori算法的挖掘關(guān)聯(lián)規(guī)則的多核并行優(yōu)化算法。本文改進了參考文獻[4-5]中的矩陣的數(shù)據(jù)結(jié)構(gòu)：在一個單純的事務(wù)矩陣中，添加2個輔助行和1個輔助列，方便矩陣進行徹底的壓縮，使矩陣的規(guī)模逐步減小，運算量也大為減少；同時為了配合查找頻繁 k-項集（k＞=2）的運算，設(shè)置了一個簡單的輔助二維數(shù)組，用來記錄下標組合情況。

定義1支持矩陣R：設(shè)A為任一給定的事務(wù)數(shù)據(jù)庫，m為事務(wù)的個數(shù)，n為項目的個數(shù)，事務(wù)集Ti（i∈m），項目集 Ij（j∈n）。如果 Ij∈Ti（1≤i≤n，1≤j≤m），則支持矩陣rij=1，否則rij=0。為方便矩陣進行徹底地壓縮，再為矩陣添加1列sum_r，記錄每個事務(wù)的事務(wù)數(shù)，即累計每行的項數(shù)；為矩陣添加1行sum_c，記錄每個項的項支持度；為矩陣添加一項，記錄項的編碼，則構(gòu)造支持矩陣 R（m+2）×（n+1）。 支持矩陣 R如圖 1所示。

圖1 支持矩陣R

其中：第一行為記錄項的編碼；最后一行為每個項的支持度；第一列為每個事務(wù)的事務(wù)數(shù)；rij=1|0，（1≤i≤n，1≤j≤m）。

定義3 k-項集支持度：對支持矩陣R中的任意k列向量（除去第一列）進行對位（同行的元素）“與”運算，運算結(jié)果中“1”的個數(shù)稱為k列向量的k-項集支持度。

根據(jù) k-項集支持度的定義，結(jié)合 Apriori性質(zhì)，可以得到以下性質(zhì)。

性質(zhì) 1 Xk是 k-項集，如果頻繁（k-1）-項集 Lk-1中包含Xk的（k-1）-子項集的個數(shù)小于k，則Xk不可能是k維最大頻繁項集。證明見參考文獻[6]。

性質(zhì) 2 設(shè) k為 k-項頻繁項集，若 T?I，且支持矩陣 R（m+2）×（n+1）中 T的事務(wù)數(shù)等于 k，由于 k-項集對于生成頻繁（k+1）-項集沒有作用，則求（k+1）-項集支持度時，該行事務(wù)T可刪除。

性質(zhì) 3 對于頻繁 k-項集的集合 Lk，如果|Lk|＜k+1，則被挖掘的事務(wù)數(shù)據(jù)庫最大頻繁項集的次數(shù)為k。其中|Lk|是指 Lk的頻繁 k-項集的個數(shù)。

證明：對于頻繁（k+1）-項集 Ix={I1，I2，…，Ik+1}，一定有k+1個頻繁k-項子集，若頻繁k-項集的集合Lk元素個數(shù)小于k+1，則被挖掘的事務(wù)數(shù)據(jù)庫不存在頻繁（k+1）-項集。利用該性質(zhì)可以提前終止搜索頻繁集的循環(huán)。

2 多核并行編程技術(shù)

OpenMP是共享存儲系統(tǒng)編程的工業(yè)標準，它具有簡單、移植性好和可擴展等優(yōu)點。OpenMP規(guī)范了一系列的編譯制導(dǎo)、運行時庫函數(shù)和環(huán)境變量來說明共享存儲結(jié)構(gòu)的并行機制。OpenMP實現(xiàn)的是線程級的并行，線程間通過讀/寫共享變量實現(xiàn)，使用Fork-Join的并行執(zhí)行模式。

TBB是針對多核平臺開發(fā)的一組開源的C++的模板庫，基于GPLv2開源證書，支持可伸縮的并行編程[7-8]。TBB的編程模式通過使用模板來提供常見的并行迭代模式，使程序員即使在不具備很專業(yè)的同步、負載平衡、緩存優(yōu)化等專門知識的情況下，也能夠?qū)崿F(xiàn)自動調(diào)度的并行程序，使得CPU的多個核心處于高效運轉(zhuǎn)之中。TBB完全支持嵌套的并行，程序員可以很容易地創(chuàng)建自己的并行組件，進而構(gòu)建大型的并行程序。TBB并行編程指定的是任務(wù)，而不是線程[9]，并以高效的方式將任務(wù)自動映射到線程，程序容易實現(xiàn)，且具有更優(yōu)的可移植性和可擴展性。

3 關(guān)聯(lián)規(guī)則挖掘算法的多核并行優(yōu)化

本文在改進算法的同時，運用多核平臺并行編程的優(yōu)勢，配合采用OpenMP的工作分區(qū)sections和并行庫TBB的tbb_parallel_for，可以實現(xiàn)每個工作段都由多個執(zhí)行核并行執(zhí)行和負載均衡的并行執(zhí)行固定數(shù)目獨立循環(huán)迭代體，用于提高查找頻繁項集的效率。基本流程如圖2所示。

（1）并行掃描數(shù)據(jù)庫 D，建立支持矩陣 R（m+2）×（n+1）。 TBB先初始化對象，再對包含m個事務(wù)n個項目的事務(wù)數(shù)據(jù) 庫 D={T1，T2，… ，Tm}，項 目 集 I={I1，I2，… ，Im}，運 用OpenMP的工作分區(qū)sections并行優(yōu)化掃描事務(wù)數(shù)據(jù)庫D，建立支持 矩陣 R（m+2）×（n+1）。

圖2 并行優(yōu)化流程圖

（2）并行求頻繁1-項集。k=1，計算最小事務(wù)支持度min_supsh=ceiling（min_sup×m），壓縮矩陣的列，余下的項都是頻繁1-項集。重新計算矩陣的sum_r列和sum_c行。

（3）k=2。

（4）并行壓縮支持矩陣。按照性質(zhì)1，先統(tǒng)計每個項目I1在頻繁（k-1）-項集中出現(xiàn)的次數(shù) bi，若 bi小于（k-1），則刪除R中Ii對應(yīng)的矩陣列。重新計算矩陣的sum_r列和sum_c行，按照性質(zhì)2，刪除不合條件的列和行，直到不能再壓縮為止。

//R支持矩陣 Wp×k存放 P個 k維項組合對

4 實驗及分析

為了驗證基于多核并行技術(shù)的改進挖掘關(guān)聯(lián)規(guī)則算法的性能，本文在Intel（R）Pentium（R）D CPU 3.0 GHz、1.86 GHz、1 GB內(nèi)存的雙核處理器系統(tǒng)上測試了參考文獻[8]的BBM算法，改進的挖掘關(guān)聯(lián)規(guī)則串行算法（以下稱本文串行算法）及改進的挖掘關(guān)聯(lián)規(guī)則的多核并行優(yōu)化算法（以下簡稱多核并行算法）。從參考文獻[10]選擇數(shù)據(jù)集進行實驗，事務(wù)數(shù)據(jù)庫共100 000條事務(wù)，事務(wù)的平均長度為 12。實驗測試結(jié)果見表 1，其中，加速比=本文串行執(zhí)行時間/多核并行執(zhí)行時間，CPU運行效率=加速比/核數(shù)。

表1 三種算法執(zhí)行時間比較

表1表明，支持度較高時，這三種算法的執(zhí)行時間差別并不大；但當(dāng)支持度逐漸降低時，與BBM算法相比，本文串行算法的執(zhí)行時間要更短，而多核并行算法的執(zhí)行時間幾乎是本文串行算法的一半，具有高的并行挖掘效率。從加速比和CPU利用率分析，多核并行算法的多核CPU運行效率達到90%左右，充分調(diào)度了兩個處理核心的資源，體現(xiàn)了計算機雙核的優(yōu)勢。

關(guān)聯(lián)規(guī)則技術(shù)是數(shù)據(jù)挖掘中的一種重要的基礎(chǔ)算法，本文在深入研究Apriori算法的基礎(chǔ)上，提出了一種改進的關(guān)聯(lián)規(guī)則挖掘的多核并行優(yōu)化算法，綜合了布爾矩陣和多核并行編程的優(yōu)點，節(jié)約了存儲空間，減少了執(zhí)行時間，具有較高的并行挖掘效率和多核CPU的利用率。本算法的設(shè)計方法對于相關(guān)算法的研究有較好的借鑒作用。

[1]何軍，劉紅巖，杜小勇.挖掘多關(guān)系關(guān)聯(lián)規(guī)則[J].軟件學(xué)報，2007，18（11）.

[2]Boeyen SX.509（2000）：4thEdition Overview of PKI&PMI Frameworks.http：//www.entrust.com.

[3]何中勝.基于向量的并行關(guān)聯(lián)規(guī)則挖掘算法[J].計算機系統(tǒng)應(yīng)用，2009，18（3）：42-45.

[4]曾萬聘，周緒波，戴勃，等.關(guān)聯(lián)規(guī)則挖掘的矩陣算法[J].計算機工程，2006，32（2）：45-47.

[5]張月琴.基于0-1矩陣的頻繁項集挖掘算法研究[J].計算機工程與設(shè)計，2009，30（20）.

[6]張素蘭.一種基于事務(wù)壓縮的關(guān)聯(lián)規(guī)則優(yōu)化算法[J].計算機工程與設(shè)計，2006，27（18）：3450-3453.

[7]Reinders J.Intel threading building blocks[M].[s.l.]：O’REILLY 出版社，2007.

[8]胡斌，袁道華.TBB多核編程及其混合編程模型的研究[J].計算機技術(shù)與發(fā)展，2009，19（2）：89-101.

[9]Intel threading building blocks基于任務(wù)編程 [OL].http：//www.cppprog.com/2009/0401/96_2.html.

[10]ALMADEN I.Quest synthetic data generation code.http：//www.almaden.ibm.com/cs/quest/syndata.html.

Matrix compression based on multi-core TBB parallel algorithms for mining association rules

Wu Huaping，Zheng Xiaowei，Zhang Jianqiang

（College of Computer and Information Technology，Liaoning Normal University，Dalian 116081，China）

This paper analyzes the parallel algorithm for mining association rules exist，the paper proposes an improved multicore parallel association rule mining algorithm.The algorithm transforms the compression matrix of Apriori algorithm，and uses OpenMP and TBB technology under multi-core platform to complish cycle of serial procedures and task allocation in parallel of parallel design，to maximize the parallel association rule mining.

association rules；Apriori algorithm；frequent itemsets matrix；OpenMP；TBB；multi-core parallel

TP311

A

1674-7720（2011）01-0004-03

國家自然科學(xué)基金項目（No.60603047）

2010-09-05）

吳華平，男，1984年生，碩士研究生，主要研究方向：并行計算，多核計算機系統(tǒng)。

鄭曉薇，女，1957年生，教授，主要研究方向：并行計算，多核計算機系統(tǒng)。

張建強，男，1981年生，碩士研究生，主要研究方向：并行計算，多核計算機系統(tǒng)。