摘  要： 分析了并行關聯規則挖掘算法存在的不足，提出了一種改進的關聯規則挖掘的多核并行優化算法。該算法對Apriori算法的壓縮矩陣進行了改造，并在多核平臺下利用OpenMP技術和TBB技術對串行程序進行循環并行化和任務分配的并行化設計，最大限度地實現并行關聯規則挖掘。
關鍵詞： 關聯規則；Apriori算法；頻繁項集矩陣；OpenMP；TBB；多核并行

    海量數據中隱藏著大量的不為人知的模式和知識，尋找有價值的數據模式和知識是數據挖掘研究的主要內容[1]。關聯規則的挖掘是數據挖掘中的一項重要的基礎技術。經典的關聯規則挖掘算法主要有Agrawal等提出的基于Apriori算法的頻繁集方法，該算法以遞歸統計為基礎，以最小支持度為依據剪切生成頻繁集。隨著數據容量的增加，為了提高關聯規則的挖掘效率，研究人員提出了并行挖掘算法[2-3]。這些并行算法都是基于MPI和機群系統實現的，雖然具有速度快、容易實現、要求各節點間同步次數較少等優點，但仍然存在著可擴展性差、網絡通信量大、負載不平衡、處理器空轉、規則合成難度高等缺點。
    目前市場上多核處理器已成為主流，比較有代表性的支持多核處理器的并行計算平臺之一的線程構建模塊TBB(Thread Building Blocking)，可以在其他多核化工具支持下對串行程序中的可并行化部分進行線程的并行化重構，提升多核處理器平臺的效能，簡化應用程序的并行化過程。本文針對TBB的多核并行編程的優勢，結合OpenMP并行編程，提出了一種改進的關聯規則挖掘多核并行優化算法。該算法對Apriori算法的壓縮矩陣進行了改造，只需掃描一次數據庫，并利用TBB技術最大限度地壓縮矩陣，使矩陣的運算規模逐步減小。它不需要Apriori算法中的自聯接和剪枝，直接通過支持矩陣行向量的按位“與”運算并行地找出頻繁集，減少了數據移動帶來的額外開銷，提高關聯規則挖掘效率。與分布式系統的Apriori并行算法相比，該算法采用多核TBB并行技術，不存在節點間的通信與同步、負載平衡和規則合成難度高等問題。實驗證明該算法具有高效的并行挖掘效率和較高的多核CPU利用率。
1 挖掘關聯規則的串行算法
    關聯規則的核心是基于兩階段頻繁項集思想的遞推算法。發現頻繁項集是關聯規則挖掘應用中的技術和步驟。支持度和置信度是關聯規則挖掘中的兩個重要指標，為了計算支持度，需要訪問數據庫。而Agrawal等人提出的挖掘關聯規則串行算法Apriori是首先掃描數據庫，計算每個數據項的支持度，并根據支持度閾值產生頻繁1-項集L1；L1用于找頻繁2-項集L2，L2而用于找L3，如此逐層迭代的搜索，直到不能找到頻繁k-項集。Apriori算法存在一些難以克服的缺陷：(1)可能產生大量的候選項集，沒有排除不應該參與組合的元素；(2)多次掃描數據庫，大大增加系統的I／O開銷，并且數據庫有些可以刪除的項或事務被多次掃描；(3)連接程序中相同的項重復較多。針對Apriori算法的缺點，參考文獻[4]將事務數據庫轉換為基于內存的矩陣，在矩陣上找出所需的頻繁項集，從而大大減少了數據庫的掃描次數，但沒有對矩陣進行壓縮。參考文獻[5-6]對矩陣進行了壓縮，但不徹底，而且矩陣數據結構不合理，還額外增加了轉置矩陣。
    本文介紹一種改進的基于Apriori算法的挖掘關聯規則的多核并行優化算法。本文改進了參考文獻[4-5]中的矩陣的數據結構：在一個單純的事務矩陣中，添加2個輔助行和1個輔助列，方便矩陣進行徹底的壓縮，使矩陣的規模逐步減小，運算量也大為減少；同時為了配合查找頻繁k-項集(k>=2)的運算，設置了一個簡單的輔助二維數組，用來記錄下標組合情況。

2 多核并行編程技術
    OpenMP是共享存儲系統編程的工業標準，它具有簡單、移植性好和可擴展等優點。OpenMP規范了一系列的編譯制導、運行時庫函數和環境變量來說明共享存儲結構的并行機制。OpenMP實現的是線程級的并行，線程間通過讀/寫共享變量實現，使用Fork-Join的并行執行模式。
    TBB是針對多核平臺開發的一組開源的C++的模板庫，基于GPLv2開源證書，支持可伸縮的并行編程[7-8]。TBB的編程模式通過使用模板來提供常見的并行迭代模式，使程序員即使在不具備很專業的同步、負載平衡、緩存優化等專門知識的情況下，也能夠實現自動調度的并行程序，使得CPU的多個核心處于高效運轉之中。TBB完全支持嵌套的并行，程序員可以很容易地創建自己的并行組件，進而構建大型的并行程序。TBB并行編程指定的是任務，而不是線程[9]，并以高效的方式將任務自動映射到線程，程序容易實現，且具有更優的可移植性和可擴展性。
3 關聯規則挖掘算法的多核并行優化
    本文在改進算法的同時，運用多核平臺并行編程的優勢，配合采用OpenMP的工作分區sections和并行庫TBB的tbb_parallel_for，可以實現每個工作段都由多個執行核并行執行和負載均衡的并行執行固定數目獨立循環迭代體，用于提高查找頻繁項集的效率?；玖鞒倘鐖D2所示。

  


4 實驗及分析
    為了驗證基于多核并行技術的改進挖掘關聯規則算法的性能，本文在Intel(R)Pentium(R)D CPU 3.0 GHz、 1.86 GHz、1 GB內存的雙核處理器系統上測試了參考文獻[8]的BBM算法，改進的挖掘關聯規則串行算法(以下稱本文串行算法)及改進的挖掘關聯規則的多核并行優化算法(以下簡稱多核并行算法)。從參考文獻[10]選擇數據集進行實驗，事務數據庫共100 000條事務，事務的平均長度為12。實驗測試結果見表1，其中，加速比=本文串行執行時間/多核并行執行時間，CPU運行效率=加速比/核數。
    表1表明，支持度較高時，這三種算法的執行時間差別并不大；但當支持度逐漸降低時，與BBM算法相比，本文串行算法的執行時間要更短，而多核并行算法的執行時間幾乎是本文串行算法的一半，具有高的并行挖掘效率。從加速比和CPU利用率分析，多核并行算法的多核CPU運行效率達到90%左右，充分調度了兩個處理核心的資源，體現了計算機雙核的優勢。

    關聯規則技術是數據挖掘中的一種重要的基礎算法，本文在深入研究Apriori算法的基礎上，提出了一種改進的關聯規則挖掘的多核并行優化算法，綜合了布爾矩陣和多核并行編程的優點，節約了存儲空間，減少了執行時間，具有較高的并行挖掘效率和多核CPU的利用率。本算法的設計方法對于相關算法的研究有較好的借鑒作用。
參考文獻
[1] 何軍，劉紅巖，杜小勇．挖掘多關系關聯規則[J].軟件學報，2007，18(11)．
[2] Boeyen SX.509(2000)： 4th Edition Overview of PKI&PMI Frameworks. http： //www. entrust. com.
[3] 何中勝．基于向量的并行關聯規則挖掘算法[J].計算機系統應用，2009，18(3)：42-45．
[4] 曾萬聘，周緒波，戴勃，等．關聯規則挖掘的矩陣算法[J].計算機工程，2006，32(2)：45-47．
[5] 張月琴．基于0-1矩陣的頻繁項集挖掘算法研究[J].計算機工程與設計，2009，30(20)．
[6] 張素蘭．一種基于事務壓縮的關聯規則優化算法[J].計算機工程與設計，2006，27(18)：3450-3453．
[7] Reinders J. Intel threading building blocks[M]. [s.l.]：O’REILLY出版社，2007.
[8]胡斌，袁道華．TBB多核編程及其混合編程模型的研究[J].計算機技術與發展，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.