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

在審

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

1.一種基于Spark框架的增量式頻繁項集挖掘方法，其特征在于，包括以下幾個步驟：

步驟1：獲取原始數據集AprioriDB的初始一元頻繁項集；

依據設定的頻繁項集最小支持度，計算原始數據集AprioriDB中每個項的支持度，將大于或等于設定的頻繁項集最小支持度的項作為初始一元頻繁項集；

步驟2：利用k-1元頻繁項集L_k-1迭代生成k元頻繁項集L_k；

步驟3：按照步驟1-2所述方法，提取新增數據集Aprioridb的頻繁項集和對應的支持度，Aprioridb的頻繁項集及其支持度結果記為f；

步驟4：運行任務taskFRead讀取原始數據集AprioriDB的頻繁項集及對應的支持度，AprioriDB的頻繁項集及其支持度結果記為F；

步驟5：運行任務taskClassify讀取并合并f和F，依據支持度的合并結果，將所有的頻繁項集進行分類，得到三種不同類型的項集，分別是：項集F∩f、項集f-F、F-f；同時運行任務taskdbRead和taskDBRead讀取原始數據集AprioriDB和新增數據集Aprioridb；

其中，項集F∩f中的每個項集在AprioriDB和Aprioridb中都是頻繁項集；

項集f-F是指從f中去除F中存在的項集，需要掃描AprioriDB，并計算f-F中每一個項集在AprioriDB中的支持度；

項集F-f是指從F中去除f中存在的項集，需要掃描Aprioridb，計算F-f中每一個項集在Aprioridb中的支持度；

步驟6：同時運行三個不同的任務，分別讀取并更新項集F∩f、項集f-F、項集F-f中的每個項集的支持度；

其中，項集F∩f中的所有頻繁項集記為DirectF；

項集f-F中的每個項集通過掃描AprioriDB計算各項集在整個數據集中的最終支持度；再篩選出支持度小于MIN_SUP×(D×d)的項集，獲得所有頻繁項集scan_DBF；

項集F-f中的每個項集掃描Aprioridb計算各項集在整個數據集中的最終支持度；再過濾出支持度少于MIN_SUP×(D×d)的項集，獲得所有頻繁項集果scan_dbF；

步驟7：運行任務taskUnion合并頻繁項集結果DirectF，scan_DBF和scan_dbF以得到最終的頻繁項集結果F′。

2.根據權利要求1所述的方法，其特征在于，在步驟2中依據數據處理的時間復雜度，為每次迭代選擇不同的計算方法；

其中，m為頻繁項集的數量；b為每個事務中的平均項目數；P為map任務的數量；Y為事務的數量；I：迭代的次數；表示第I次迭代中得到m個頻繁項集；表示第I次迭代中得到每個事務的b個平均項目數；

若上式成立，則選擇方法1，否則，選擇方法2；

方法1：輸入文件為存儲在HDFS上的數據集AprioriDB和存儲在Bloom過濾器中的上一次迭代后得到的k元頻繁項集L_k；

首先，map任務接收事務并修剪事務，使它只包含存在Bloom過濾器的項；然后，map任務為被修剪的事務生成相應的<key，value>對；隨后，reduce任務利用reduceByKey()組合所有<key，value>對；

方法2：輸入文件為存儲在HDFS上的數據集AprioriDB和存儲在HashTree中的通過L_k-1生成的候選項集C_k；

首先，map任務接收事務，并且找到每個事務的k項集并生成相應的<key，value>對；隨后，reduce任務利用reduceByKey()組合所有<key，value>對。