摘  要： 分析了并行關(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)用程序的并行化過程。本文針對(duì)TBB的多核并行編程的優(yōu)勢(shì),，結(jié)合OpenMP并行編程,，提出了一種改進(jìn)的關(guān)聯(lián)規(guī)則挖掘多核并行優(yōu)化算法。該算法對(duì)Apriori算法的壓縮矩陣進(jìn)行了改造,，只需掃描一次數(shù)據(jù)庫,，并利用TBB技術(shù)最大限度地壓縮矩陣，使矩陣的運(yùn)算規(guī)模逐步減小,。它不需要Apriori算法中的自聯(lián)接和剪枝,，直接通過支持矩陣行向量的按位“與”運(yùn)算并行地找出頻繁集，減少了數(shù)據(jù)移動(dòng)帶來的額外開銷,，提高關(guān)聯(lián)規(guī)則挖掘效率,。與分布式系統(tǒng)的Apriori并行算法相比，該算法采用多核TBB并行技術(shù),，不存在節(jié)點(diǎn)間的通信與同步,、負(fù)載平衡和規(guī)則合成難度高等問題。實(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ì)算支持度,，需要訪問數(shù)據(jù)庫,。而Agrawal等人提出的挖掘關(guān)聯(lián)規(guī)則串行算法Apriori是首先掃描數(shù)據(jù)庫，計(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)集,，沒有排除不應(yīng)該參與組合的元素,；(2)多次掃描數(shù)據(jù)庫，大大增加系統(tǒng)的I／O開銷,，并且數(shù)據(jù)庫有些可以刪除的項(xiàng)或事務(wù)被多次掃描,；(3)連接程序中相同的項(xiàng)重復(fù)較多。針對(duì)Apriori算法的缺點(diǎn),，參考文獻(xiàn)[4]將事務(wù)數(shù)據(jù)庫轉(zhuǎn)換為基于內(nèi)存的矩陣,，在矩陣上找出所需的頻繁項(xiàng)集，從而大大減少了數(shù)據(jù)庫的掃描次數(shù),，但沒有對(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ù)組，用來記錄下標(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í)庫函數(shù)和環(huán)境變量來說明共享存儲(chǔ)結(jié)構(gòu)的并行機(jī)制,。OpenMP實(shí)現(xiàn)的是線程級(jí)的并行，線程間通過讀/寫共享變量實(shí)現(xiàn),，使用Fork-Join的并行執(zhí)行模式,。
    TBB是針對(duì)多核平臺(tái)開發(fā)的一組開源的C++的模板庫，基于GPLv2開源證書,，支持可伸縮的并行編程[7-8],。TBB的編程模式通過使用模板來提供常見的并行迭代模式，使程序員即使在不具備很專業(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和并行庫TBB的tbb_parallel_for,，可以實(shí)現(xiàn)每個(gè)工作段都由多個(gè)執(zhí)行核并行執(zhí)行和負(fù)載均衡的并行執(zhí)行固定數(shù)目獨(dú)立循環(huán)迭代體,，用于提高查找頻繁項(xiàng)集的效率?；玖鞒倘鐖D2所示,。

  


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ù)庫共100 000條事務(wù)，事務(wù)的平均長(zhǎng)度為12,。實(shí)驗(yàn)測(cè)試結(jié)果見表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] 曾萬聘,，周緒波,，戴勃，等．關(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.