摘  要： 分析了并行關(guān)聯(lián)規(guī)則挖掘算法存在的不足，提出了一種改進的關(guān)聯(lián)規(guī)則挖掘的多核并行優(yōu)化算法。該算法對Apriori算法的壓縮矩陣進行了改造，并在多核平臺下利用OpenMP技術(shù)和TBB技術(shù)對串行程序進行循環(huán)并行化和任務分配的并行化設(shè)計，最大限度地實現(xiàn)并行關(guān)聯(lián)規(guī)則挖掘。
關(guān)鍵詞： 關(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)，提升多核處理器平臺的效能，簡化應用程序的并行化過程。本文針對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ī)則挖掘應用中的技術(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)生大量的候選項集，沒有排除不應該參與組合的元素；(2)多次掃描數(shù)據(jù)庫，大大增加系統(tǒng)的I／O開銷，并且數(shù)據(jù)庫有些可以刪除的項或事務被多次掃描；(3)連接程序中相同的項重復較多。針對Apriori算法的缺點，參考文獻[4]將事務數(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)：在一個單純的事務矩陣中，添加2個輔助行和1個輔助列，方便矩陣進行徹底的壓縮，使矩陣的規(guī)模逐步減小，運算量也大為減少；同時為了配合查找頻繁k-項集(k>=2)的運算，設(shè)置了一個簡單的輔助二維數(shù)組，用來記錄下標組合情況。

2 多核并行編程技術(shù)
    OpenMP是共享存儲系統(tǒng)編程的工業(yè)標準，它具有簡單、移植性好和可擴展等優(yōu)點。OpenMP規(guī)范了一系列的編譯制導、運行時庫函數(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并行編程指定的是任務，而不是線程[9]，并以高效的方式將任務自動映射到線程，程序容易實現(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)迭代體，用于提高查找頻繁項集的效率?；玖鞒倘鐖D2所示。

  


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ù)集進行實驗，事務數(shù)據(jù)庫共100 000條事務，事務的平均長度為12。實驗測試結(jié)果見表1，其中，加速比=本文串行執(zhí)行時間/多核并行執(zhí)行時間，CPU運行效率=加速比/核數(shù)。
    表1表明，支持度較高時，這三種算法的執(zhí)行時間差別并不大；但當支持度逐漸降低時，與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].軟件學報，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].計算機系統(tǒ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] 張素蘭．一種基于事務壓縮的關(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 基于任務編程[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.