[發明專利]一種基于Spark框架的增量式頻繁項集挖掘方法

在審

• 申請號: 201811551301.8
• 申請日: 2018-12-18
• 公開（公告）號: CN109739897A
• 公開（公告）日: 2019-05-10
• 發明（設計）人: 何夢思;唐卓;李肯立;李克勤;付仲明;肖偉
• 申請（專利權）人: 湖南大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458
• 代理公司: 長沙市融智專利事務所(普通合伙) 43114
• 代理人: 龔燕妮

本發明公開了一種基于Spark框架的增量式頻繁項集挖掘方法，首先實現一種基于Spark的自適應并行Apriori算法，使用自適應算法來尋找具有更高精度和效率的頻繁模式，可以有效解決傳統Apriori算法在面對大規模數據時處理能力不足的問題。接著，在并行Apriori算法的基礎上實現增量式Apriori算法，能夠增量處理動態數據集，大幅減少參與計算的數據量，有效解決Apriori頻繁項集挖掘方法的時效性問題。

技術領域

本發明涉及一種基于Spark框架的增量式頻繁項集挖掘方法。

背景技術

在大數據時代，數據不再是社會產生的“副產物”，而是可以被二次乃至多次加工的原材料，從中可以探索更大的價值，將其變成生產資料。挖掘大數據的價值類似沙里淘金，從海量數據中挖掘稀有但珍貴的信息是大數據的一個典型特征。目前，各行各業都在利用數據產生的商業價值改變著我們的生活。因此，如何快速準確地從海量數據中獲取所需要的信息成為新的研究問題。

數據挖掘即是一種專門研究如何快速高效的從海量數據中發現知識的新興技術，而頻繁項集挖掘是數據挖掘最受關注的領域之一。隨著數據集的大小增加，頻繁項級算法的效率大大小下降。因此，處理大型數據集，需要引入并行算法來提高算法的處理效率。另外頻繁項集挖掘的時效性在處理動態變化的數據集時也尤為重要。隨著應用的不斷豐富，數據利用的目的更加多元化，頻繁項集挖掘Apriori算法需要處理的數據不再是靜態不變的，而是動態的、不斷更新的數據集，如天貓超市的購物記錄，銀行的交易記錄等。每當數據發生改變時，若仍然采用傳統的Apriori算法反復地處理全量數據集，則每次處理都將會導致大量的運算資源浪費和性能損失。因此，在面對大規模動態數據集時，如何提高Apriori算法的性能成為本課題的重點研究問題。

大數據處理涉及的關鍵技術有海量數據存儲與實時處理。在Hadoop的體系結構中，Mapreduce作為并行編程模型已經成為用于海量數據處理的強大工具。但Hadoop的中間數據不能緩存在內存中，使得對于重復使用的數據集需要頻繁I/O，因此對于高迭代計算效率較低。很多機器學習算法比如K-means聚類算法和邏輯回歸算法都需要對數據進行迭代計算，針對Mapreduce中出現的各種不足，伯克利大學推出了全新的統一大數據處理框架ApacheSpark，它創新性的提出了RDD概念(一種新的抽象的彈性數據集)。Spark允許將數據緩存在內存中，并應用于多次迭代計算，因此，Spark更適合迭代運算較多的機器學習或數據挖掘算法。

發明內容

本發明提出了一種基于Spark框架的增量式頻繁項集挖掘方法，首先實現一種基于Spark的自適應并行Apriori算法，使用自適應算法來尋找具有更高精度和效率的頻繁模式，在每次迭代之前制定執行計劃，采用最合適的計劃來最小化時間和空間復雜性。接著，在并行Apriori算法的基礎上，提出一種增量式Apriori算法，利用已有的計算結果，根據新增加的數據對頻繁項集進行修改，避免了反復地處理全量數據集。

相關定義：

(1)項目集(項集)

一個項集由多個互不相同的項目(項)組成。項集用t表示，可記作t＝{i₁，i₂….，i_k}，其中i_x(x為[1,k]之間的整數])為出現在項集t中的一個項。在t＝{i₁，i₂….，i_k}中，共有k個項，即|t|＝k，因此又稱這個t為k元項集。

(2)事務(交易記錄)

一個與項集相似的概念，交易記錄是一個項集，因此可表示為t＝{i₁，i₂….，i_k}。交易記錄又區別于項集，交易記錄是輸入數據中實際出現的數據，而項集是多個項目之間任意的數學組合，與是否出現在輸入數據中無關。

(3)輸入數據集