吳華平，鄭曉薇，張建強(qiáng)

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

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

吳華平，鄭曉薇，張建強(qiáng)

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

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

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

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

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

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

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

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

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

圖1 支持矩陣R

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

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

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

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

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

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

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

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

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

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

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

本文在改進(jìn)算法的同時(shí)，運(yùn)用多核平臺(tái)并行編程的優(yōu)勢(shì)，配合采用OpenMP的工作分區(qū)sections和并行庫(kù)TBB的tbb_parallel_for，可以實(shí)現(xiàn)每個(gè)工作段都由多個(gè)執(zhí)行核并行執(zhí)行和負(fù)載均衡的并行執(zhí)行固定數(shù)目獨(dú)立循環(huán)迭代體，用于提高查找頻繁項(xiàng)集的效率?；玖鞒倘鐖D2所示。

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

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

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

（3）k=2。

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

//R支持矩陣 Wp×k存放 P個(gè) k維項(xiàng)組合對(duì)

4 實(shí)驗(yàn)及分析

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

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

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

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

[1]何軍，劉紅巖，杜小勇.挖掘多關(guān)系關(guān)聯(lián)規(guī)則[J].軟件學(xué)報(bào)，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].計(jì)算機(jī)系統(tǒng)應(yīng)用，2009，18（3）：42-45.

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

[5]張?jiān)虑?基于0-1矩陣的頻繁項(xiàng)集挖掘算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（20）.

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

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

[8]胡斌，袁道華.TBB多核編程及其混合編程模型的研究[J].計(jì)算機(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

國(guó)家自然科學(xué)基金項(xiàng)目（No.60603047）

2010-09-05）

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

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

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