[發明專利]一種并行化的數據流頻繁項集挖掘方法

有效

• 申請號: 201710696637.2
• 申請日: 2017-08-15
• 公開（公告）號: CN107451290B
• 公開（公告）日: 2020-03-10
• 發明（設計）人: 段貴多;羅光春;田玲;韓宏
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F16/2455
• 分類號: G06F16/2455;G06F16/2458
• 代理公司: 成都弘毅天承知識產權代理有限公司 51230
• 代理人: 徐金瓊;劉東

本發明公開了一種并行化的數據流頻繁項集挖掘方法，旨在解決現有技術數據挖掘吞吐量小的問題；本申請包括初始化，預挖掘，FP?Stream結構維護，頻繁項集生成四部分,算法收集一小段時間內到達的事務，構成一個事務集，第一個事務集被特殊處理，它被用于初始化，以建立f_list和FP?Stream結構,每個事務集觸發一輪微批處理。每輪微批處理先進行預挖掘，再進行FP?Stream結構維護，當計算請求到達時，算法利用FP?Growth算法在指定的時間窗口內挖掘FP?Stream結構得到頻繁項集；本申請采用的算法增加了系統的整體吞吐量，極大程度提高了數據挖掘的處理速度；本申請適用于數據挖掘相關方面。

技術領域

本發明涉及數據挖掘領域，尤其涉及一種并行化的數據流頻繁項集挖掘方法。

背景技術

頻繁項集挖掘也叫關聯規則挖掘，目標是從大量事務中找出有價值項目間隱含的關系。所謂頻繁項是指在事務集合中，出現頻率較高的項目；頻繁項集是指在事務集合中，多次同時出現的項目所組成的集合。極大頻繁項集被定義為元素個數最多的頻繁項集，它的所有超集都是非頻繁項集。頻繁項集挖掘的經典應用案例是利用頻繁項集挖掘技術發現了啤酒銷售和尿布銷售之間的隱含關系。

傳統數據流上的頻繁項集挖掘算法是基于單機環境，其吞吐量受單機環境的限制。然而，不斷增長的海量數據已經遠遠超過了單機的處理能力，單機頻繁項集挖掘技術僅適用于少量數據的環境。

大數據時代，分布式計算是解決海量數據難題的重要手段。并行化的算法能夠有效提升系統的整體吞吐量，所以在分布式環境下并行化地挖掘數據流中的頻繁項集是極其重要的。鑒于對并行化的數據流頻繁項集挖掘算法的需求，本發明提出一種基于微批處理思想的并行化數據流頻繁項集挖掘方法。

發明內容

本發明的目的在于：針對現有技術數據挖掘吞吐量小的問題，本發明提供一種并行化吞吐量大的數據流頻繁項集挖掘方法。

本發明采用的技術方案如下：

本申請提供了一種并行化的數據流頻繁項集挖掘方法,包括以下步驟：

步驟1：初始化，首個事務集到達時，進行算法初始化工作。

步驟1.1：收集單位時間的所有事務，形成事務集，依次記為{B₁…B_i},并分散存儲至各個節點上，第一個事務集為B₁，統計所有項目在B₁中的頻率，然后根據頻率降序排列得到f_list；

步驟1.2：用FP-growth算法，支持度閾值設為∈，挖掘事務集B₁，并用挖掘事務集B₁得到的項目集建立FP-Stream結構并儲存至所述Zookeeper集群；

步驟2：單輪微批處理

當除了B₁事務集的其他一個事務集到達時，進行一輪微批處理，每輪微批處理包含預挖掘部分與FP-Stream結構維護兩部分，兩部分依次分布式執行；

步驟2.1：并行執行預挖掘，當一個事務集(首個事務集除外)到達時，進行一輪微批處理。每輪微批處理包含預挖掘與FP-Stream結構維護維護兩部分，這兩部分依次分布式執行；

步驟2.1.1：統計分散在各個節點的B_i(i>1)中事務出現的對應頻率，得到集合T，集合T中記錄的形式為<事務，頻率>；

步驟2.1.2：以f_list為依據，對T中事務的項目進行排序，得到新的集合W；

步驟2.1.3：再次統計集合T中事務對應的頻率，得到新的集合R，求R中每條事務的元素個數大于1的項目集以及項目集對應的頻率，組成集合S，集合S的記錄形式為<項目集，頻率>；