摘  要： 分析了并行關(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)鍵詞： 關(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)的額外開(kāi)銷(xiāo)，提高關(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開(kāi)銷(xiā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)組合情況。

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ò)讀/寫(xiě)共享變量實(shí)現(xiàn)，使用Fork-Join的并行執(zhí)行模式。
    TBB是針對(duì)多核平臺(tái)開(kāi)發(fā)的一組開(kāi)源的C++的模板庫(kù)，基于GPLv2開(kāi)源證書(shū)，支持可伸縮的并行編程[7-8]。TBB的編程模式通過(guò)使用模板來(lái)提供常見(jiàn)的并行迭代模式，使程序員即使在不具備很專(zhuān)業(yè)的同步、負(fù)載平衡、緩存優(yōu)化等專(zhuān)門(mén)知識(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)集的效率。基本流程如圖2所示。

  


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表明，支持度較高時(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)算法的研究有較好的借鑒作用。
參考文獻(xiàn)
[1] 何軍，劉紅巖，杜小勇．挖掘多關(guān)系關(guān)聯(lián)規(guī)則[J].軟件學(xué)報(bào)，2007，18(11)．
[2] Boeyen SX.509(2000)： 4th Edition 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)虑伲?-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.