[發明專利]基于Spark的并行化關聯挖掘優化方法

在審

• 申請號: 201710413035.1
• 申請日: 2017-06-05
• 公開（公告）號: CN107291848A
• 公開（公告）日: 2017-10-24
• 發明（設計）人: 肖甫;許平;沙樂天;王少輝;韓崇;王汝傳
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京知識律師事務所32207
• 代理人: 張芳

技術領域

本發明涉及大數據關聯挖掘算法領域，特別是基于Spark的并行化關聯挖掘優化方法。

背景技術

大數據通常用來形容大量半結構化和非結構化數據，有明顯的自身特征：體量大、種類多、產生速度快、實時性要求高、價值密度低，這意味著傳統的數據關聯挖掘算法已不能滿足大數據的處理需求，面向多機、并行、分布式的大數據處理方式變得越來越重要，因此研究并提出新的能夠適應大數據環境的關聯挖掘算法已經顯得十分迫切而重要。

Apriori算法是最為經典的關聯規則挖掘算法，該算法的核心是生成最大項目集，通過迭代方式逐層搜索頻繁項集，直至沒有更大項目集生成。目前Apriori算法存在的性能瓶頸主要體現在兩個方面：(1)每次搜索都需要完整地掃描一次數據庫，(2)需要通過自連接和剪枝產生龐大的候選項集。與此同時，在當前大數據背景下，面對海量數據，這種傳統串行方式效率特別低，對算法進行并行化改造成為了研究的熱點。

發明內容

針對Apriori算法的不足，本發明提供一種基于Spark的并行化關聯挖掘優化方法，Spark是一種快速、通用、可擴展的大數據分析引擎，利用改進的基于Spark平臺的關聯挖掘算法Apriori對網站點擊流日志進行用戶訪問路徑分析，通過對經典關聯規則算法Apriori的分析并結合Spark計算模型的特點，提供基于用戶訪問路徑關聯的算法，最終能夠快速準確為用戶提供頁面訪問推薦策略。

基于Spark的并行化關聯挖掘優化方法，先對事務數據庫進行預處理，根據業務需求進行數據清洗，提取簡要有效信息，將事務項數據編碼化后，全部讀取到內存，轉換成RDD模型；在生成頻繁1項集的過程中，構造新的數據結構存放1項集的事務序列號；在頻繁項集連接、剪枝生成候選集的過程中，舍去候選項集的產生過程，篩選出連接后事務序列號數滿足最小支持度的項集；重復以上過程，直到沒有滿足最小支持度條件的更大的項集產生。

所述生成頻繁項集的過程為：

a1、對事務中包含的所有項發射該項及對應事務編號的鍵值對，reducer將每項對應的事務編號合并起來，構造成(item,BitSet)的存儲形式；

a2、對事務編號進行統計，根據支持度過濾得到只包含頻繁1項集的轉換后的數據集F；

a3、將存儲于數據集F₁中的頻繁1項集進行兩兩自連接，然后判斷其支持度，將滿足最小支持度條件的(item,BitSet)存入F₂中,其中item表示事務項，BitSet表示事務編號；

a4、將存儲于F_K-1中的頻繁k-1項集兩兩自連接，連接規則為：k-1項集中的前k-2項相同，第k-1項不同，則可連接成f_i[1],f_i[2]…f_i[k-2],f_i[k-1],f_j[k-1],將滿足支持度的項集和事務編號集存入F_k。

本發明的顯著優點為：求項集的出現次數從遍歷整個數據集簡化到將對應項的BitSet求與，減少了系統I/O；舍去了候選項集的產生過程，提高了算法的運行效率。本發明可以對網站用戶訪問路徑數據進行基于關聯規則的數據挖掘分析，可以幫助技術人員合理修改網站結構及適度分配資源，構建后臺服務器群組；可以幫助企業改善市場營銷決策，獲取更高投資回報率。

附圖說明

圖1為本發明實施例中網站用戶訪問源數據庫圖；

圖2為本發明實施例數據預處理流程圖；

圖3是本發明實施例由關聯規則產生的非循環圖；

圖4是本發明實施例基于Spark的關聯挖掘優化方法流程圖。

具體實施方式

為了使本發明的目的、技術方案及優點更加清楚明白，以下結合附圖及實施例，對本發明進行進一步詳細說明。應當理解，此處所描述的具體實施例僅僅用以解釋本發明，并不用于限定本發明。

基于Spark的并行化關聯挖掘優化方法步驟如下：

(1)掃描事務數據庫D，對源數據進行數據清洗，將數據記錄簡化，提取有效信息，并將所有的數據項替換為其所對應的編號生成新的事務數據庫D，存入HDFS中。新的編碼化后的數據如表1所示。

表1