一種關聯分析算法的並行化方法

2023-04-24 22:38:06

一種關聯分析算法的並行化方法
【專利摘要】一種關聯分析算法的並行化方法是針對一種經典的關聯規則分析算法Apriori不能很好適應並行化的缺陷，設計了一種新的並行化方案。通過主控節點將計算任務進行分塊，分配並分發給各個子計算節點。由各計算節點並行計算篩選頻繁集，最後合併節點並返回結果統計，生成頻繁集。再次分發頻繁集，由各節點生成規則。由於每個計算節點僅處理一部分計算任務，解決了海量數據無法由單機讀入內存進行處理和處理速度過慢的問題；且多個節點並行參與處理，有效提高了處理效率；並且對計算過程中的節點間的同步依賴、網絡通訊負擔過重、I/O操作過於頻繁做了相應的改進，提高了資料庫掃描和計算的速度。
【專利說明】一種關聯分析算法的並行化方法
【技術領域】
[0001]本發明是針對一種經典的關聯規則分析算法Apriori不能很好適應並行化的缺陷，設計了一種新的並行化方法，減少了節點間的同步依賴和網絡通訊負擔，提高了資料庫掃描和計算的速度。屬於分布式計算和雲計算領域。
【背景技術】
[0002]雲計算(Cloud Computing)是一種新興的商業計算模型,它將計算任務分布在大量計算機構成的資源池上，使各種應用系統能夠根據需要獲取計算力、存儲空間和各種軟體服務，它是數據管理技術不斷演進的結果。在上世紀末，分布式處理、並行處理和網格計算就已相當成熟，它們是雲計算發展的技術基礎，企業推動則是雲計算快速發展的主要動力。目前，IT巨頭正在相繼開發雲計算平臺、雲計算終端和伺服器。
[0003]關聯規則算法用來描述事物之間的聯繫和挖掘事物之間的相關性，其核心是通過統計數據項獲得頻繁項集，被廣泛應用於分類設計「捆綁式銷售」倉儲貨存配置等領域，關聯規則的挖掘已經成為數據挖掘中一個非常重要的研究方向。
[0004]Apriori算法首先由Agrawal教授於1993年提出，是一種最有影響的挖掘布爾關聯規則頻繁項集的算法，其核心是基於兩階段頻集思想的遞推算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則，所有支持度大於最小支持度的項集稱為頻繁項集，簡稱頻集。
[0005]該算法的基本思想是:首先找出所有的頻集，這些項集出現的頻繁性至少和預定義的最小支持度一樣。然後由頻集產生強關聯規則，這些規則必須滿足最小支持度和最小置信度。接著使用這些找到的頻集產生期望的規則，產生只包含集合的項的所有規則，其中每一條規則的右部只有一項，這裡採用的是中規則的定義。一旦這些規則被生成，那麼只有那些大於用戶給定的最小可信度的規則才被留下來。為了生成所有頻集，使用了遞推的方法，依次從k項集推出k+Ι項集。
[0006]可能產生大量的候選集，以及可能需要重複掃描資料庫，是Apriori算法的兩大缺點，然而隨著挖掘數據的增大，其運算能力很快出現了瓶頸。因此，利用雲計算將數據處理並行化來降低運算時間，提高處理能力成為了一個新的方向。本發明提出了一種新的並行化方案，使傳統的Apriori算法適用於雲計算環境中。

【發明內容】

[0007]技術問題:本發明的目的是針對一種經典的關聯規則分析算法Apriori不能很好適應並行化的缺陷，設計了一種關聯分析算法的並行化方法，減少了節點間的同步依賴和網絡通訊負擔，提高了資料庫掃描和計算的速度，利用雲計算解決了海量數據分析的困難和瓶頸。
[0008]技術方案:針對這些問題，本發明提出了一種關聯分析算法的並行化方法，將頻繁項的篩選和規則的生成分攤到了集群中並行完成。利用下一層的候選頻繁集生成並不需要完全依賴於上一層的頻繁集，取消了每層頻繁集生成中的同步過程，採用先到先計算的規貝U，減少了節點間的同步依賴和網絡通訊負擔。通過事務編號集來定位掃描的位置，減小了i/o的壓力，提高了資料庫掃描和計算的速度。
[0009]現有的並行化大致分為兩個思路:
[0010]一、將對事務資料庫掃描的過程並行，把資料庫分片，保存在各個節點上。每次循環開始時將候選頻繁k-項集發送到各個節點上分別統計每項在局部資料庫上的支持度，然後在循環結束時同步所有節點的計算結果，統計出每項的全局支持度並刪除不滿足閥值的項。
[0011]該方案減少了對資料庫掃描所需的時間，在一定程度上提升了處理能力，但是每次循環結束時同步會存在不同節點之間的相互等待的問題。並且剪枝是在合併後完成，單個節點僅有掃描和統計的功能而沒有判斷功能，隨著節點數的增多，通信量將迅速增大，給帶寬帶來了巨大壓力。
[0012]二、將整個挖掘過程並行，把資料庫分成η塊，發送到每個節點上，針對每一塊數據獨立地進行傳統Apriori算法的挖掘過程，閥值縮小為I/η。最後將每個節點輸出的1-到k_項局部頻繁集合併及掃描整個資料庫，刪除掉不滿足閥值的項，得到整個頻繁集。
[0013]該方案為節點增加了判斷的能力，使得各節點可以獨立完成剪枝，提高了並行程度，減輕了帶寬壓力。但是根據概率統計學，各節點每次生成的候選頻繁k_項集應該是近似的。這種近似的挖掘過程將在各個節點上重複η遍，浪費了相當大的計算資源。
[0014]可以看出，將資料庫分片雖然是一種簡單的並行方案，但是各節點之間的通信量和計算量的平衡問題並無法妥善解決。
[0015]因此本發明嘗試了一種新思路，算法的運行流程步驟如下:
[0016]該方法採用主從結構，由一臺伺服器作為主節點處理所有的調度和協調，其餘伺服器作為子節點完成計算任務，該並行化方法的步驟如下:
[0017]步驟1.啟動所有伺服器，將待分析的原始數據的資料庫分別下載到所有伺服器節點上；
[0018]步驟2.第一階段分析開始，主節點掃描自身資料庫，統計出整個1-項集以及事務總數，設定閥值，並將閥值發送到各個子節點上；
[0019]步驟3.將整個1-項集作為候選頻繁1-項集，由主節點將每一項的統計任務分派給一個空閒的子節點；
[0020]步驟4.收到任務的各個子節點掃描自身資料庫，統計該項的支持度，如果該項的支持度滿足閥值則向主節點返回該項以及該項的支持度和事務編號集，如果不滿足則刪除掉該項；
[0021]步驟5.主節點將收到的返回結果加入頻繁1-項集中，並連接這些項集生成按字典順序排列的候選頻繁2-項集，每生成一項，就連同其候選事務編號集一併分派給一個空閒的子節點；
[0022]步驟6.收到任務的各個子節點掃描所給的候選事務編號集，統計該項的支持度，如果該項的支持度滿足閥值則向主節點返回該項以及該項的支持度和事務編號集，如果不滿足則刪除掉該項及其相關數據；
[0023]步驟7.主節點將收到的返回結果加入頻繁2-項集中，並連接這些項集生成按字典順序排列的候選頻繁3-項集，每生成一項，就連同其候選事務編號集一併分派給空閒節
佔.[0024]步驟8.重複步驟6，步驟7的過程，將每次返回的結果保存入頻繁集，並連接生成更長的候選頻繁集，直到沒有新的項滿足閥值為止，保存所有的頻繁1-項、2-項、3-項……k_項集以及各自的支持度，將所有的頻繁集按照頻繁1-項集分組，第一階段分析結束；
[0025]步驟9.第二階段分析開始，按照分組將各組頻繁集及其支持度發送給各個子節
佔.[0026]步驟10.各子節點分別根據每組頻繁集生成規則並計算其置信度，如果滿足閥值則向主節點返回該規則，如果不滿足則忽略；
[0027]步驟11.主節點將所有收到的返回結果保存，排序後即為規則集，第二階段分析結束；
[0028]步驟12.輸出顯示規則集，結束。
[0029]有益效果:本發明提出了一種新的Apriori算法並行化方案，該方案的主要優勢在於:
[0030]一、將每一項的統計過程獨立並行，並且沒有產生重複的計算，提升了整個候選頻繁項集的生成速度； [0031]二、每個節點都具有判斷的功能，不會向網絡發送無用的數據，減輕了網絡壓力；
[0032]三、跨層統計的功能避免了各個節點之間相互等待的問題；
[0033]四、掃描上一層的事務編號集而不是整個資料庫大量減少了每次掃描所需的時間，這對於需要多次掃描統計的Apriori算法來說節省的時間是相當可觀的。
【專利附圖】

【附圖說明】
[0034]圖1關聯分析算法運行流程圖。
[0035]圖2分析集群架構圖。
【具體實施方式】
[0036]細節說明:
[0037]k-項集:關聯規則算法是為了從{A, B, C, D}, {A, B}......等集合中找出例如A — B
的規則。因此，例如{A}，{C}就稱之為1-項集，{Α,Β}就稱之為2-項集，{A，B，C……}就稱之為k-項集，其中k代表集合中有多少項。
[0038]頻繁k_項集:出現的頻率滿足閥值的1-項集稱之為頻繁1-項集，出現的頻率滿足閥值的2-項集稱之為頻繁2-項集，同理，出現的頻率滿足閥值的k-項集稱之為頻繁k_項集。
[0039]候選頻繁k_項集:通過集合連接得到的可能成為頻繁2-項集的2-項集稱之為候選頻繁2-項集。通過集合連接得到的可能成為頻繁k-項集的k-項集稱之為候選頻繁k_項集。
[0040]置信度:表示某條規則的可信程度。計算方法為下層頻繁集的支持度與上層頻繁集的支持度之商。例如，〈ABCE，3>，，則規則AB — CE的置信度為30%。
[0041]跨層統計:由η項自然連接所產生的集分別為Cj1,G.......Cir15C;;個，呈菱形分布。通過Apriori算法產生的候選頻繁k_項集的驗證過程可以拆解成每一項的簡單計數,是相互獨立的，因此將該過程並行化是可行的。並且即使在候選頻繁k-項集沒有完全驗證完畢的時候，將已經驗證過的部分頻繁k-項集進行連接，同樣可以產生一部分候選頻繁(k+l)_項集。也就是說不必等待同一層的所有頻繁集完全確定之後才能開始下一次頻繁集的生成和驗證。因此將每一項單獨驗證還可以一定程度上解決各節點間的相互等待的問題。
[0042]事務編號集:每個節點都存儲了整個事務資料庫，事務數據形如下表，Tid表示事務的編號。
[0043]
【權利要求】
1.一種關聯分析算法的並行化方法，其特徵在於該方法採用主從結構，由一臺伺服器作為主節點處理所有的調度和協調，其餘伺服器作為子節點完成計算任務，該並行化方法的步驟如下: 步驟1.啟動所有伺服器，將待分析的原始數據的資料庫分別下載到所有伺服器節點上； 步驟2.第一階段分析開始，主節點掃描自身資料庫，統計出整個1-項集以及事務總數，設定閥值，並將閥值發送到各個子節點上； 步驟3.將整個1-項集作為候選頻繁1-項集，由主節點將每一項的統計任務分派給一個空閒的子節點； 步驟4.收到任務的各個子節點掃描自身資料庫，統計該項的支持度，如果該項的支持度滿足閥值則向主節點返回該項以及該項的支持度和事務編號集，如果不滿足則刪除掉該項； 步驟5.主節點將收到的返回結果加入頻繁1-項集中，並連接這些項集生成按字典順序排列的候選頻繁2-項集，每生成一項，就連同其候選事務編號集一併分派給一個空閒的子節點； 步驟6.收到任務的各個子節點掃描所給的候選事務編號集，統計該項的支持度，如果該項的支持度滿足閥值則向主節點返回該項以及該項的支持度和事務編號集，如果不滿足則刪除掉該項及其相關數據；步驟7.主節點將收到的返回結果加入頻繁2-項集中，並連接這些項集生成按字典順序排列的候選頻繁3-項集，每生成一項，就連同其候選事務編號集一併分派給空閒節點；步驟8.重複步驟6，步驟7的過程，將每次返回的結果保存入頻繁集，並連接生成更長的候選頻繁集，直到沒有新的項滿足閥值為止，保存所有的頻繁1-項、2-項、3-項……k-項集以及各自的支持度，將所有的頻繁集按照頻繁1-項集分組，第一階段分析結束； 步驟9.第二階段分析開始，按照分組將各組頻繁集及其支持度發送給各個子節點；步驟10.各子節點分別根據每組頻繁集生成規則並計算其置信度，如果滿足閥值則向主節點返回該規則，如果不滿足則忽略； 步驟11.主節點將所有收到的返回結果保存，排序後即為規則集，第二階段分析結束； 步驟12.輸出顯示規則集，結束。
【文檔編號】G06F17/30GK103914528SQ201410124334
【公開日】2014年7月9日 申請日期:2014年3月28日 優先權日:2014年3月28日
【發明者】張琳, 邵天昊, 王汝傳, 韓志傑, 付雄, 季一木 申請人:南京郵電大學