[發明專利]一種海量數據的頻繁序列挖掘方法

在審

• 申請號: 201711457785.5
• 申請日: 2017-12-28
• 公開（公告）號: CN108170799A
• 公開（公告）日: 2018-06-15
• 發明（設計）人: 王宏志;秦謙
• 申請（專利權）人: 江蘇名通信息科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 董建林;張賞

1.一種海量數據的頻繁序列挖掘方法，其特征在于，包括以下步驟：

1)用戶輸入時間序列數據，獲得數據的基本統計信息，計算每一個項ω∈Σ的頻率，并且對于頻繁項要構造集合F_σ,0,1(D)，其中，ω表示輸入的子序列，Σ為全集，表示輸入所有時間序列集合，D表示輸入時間序列數據庫，下標σ表示支持度閾值，0是間隔閾值，1是長度閾值；所述頻繁項是指，對于σ>0，如果滿足f_γ(S,D)≥σ，則序列S是(σ,γ)–頻繁的，其中，f_γ(S,D)表示序列S的頻率；

2)對于Σ中所有頻繁項，在Map構造ω-等價的劃分P_ω；

3)對步驟2)構造的劃分P_ω在Reduce進行獨立的挖掘，得到F_σ,γ,λ(P_ω)，其中，P_ω是以ω為中心項的劃分，F_σ,γ,λ(P_ω)是P_ω當中所有長度不超過λ且滿足(σ，γ)-頻繁的序列；

4)將步驟3)得到的每個頻繁項的F_σ,γ,λ(P_ω)集合并在一起，將重復的序列過濾掉即得到最后的輸出。

2.根據權利要求1所述的一種海量數據的頻繁序列挖掘方法，其特征在于，所述步驟1)中，數據的基本統計信息包括時間序列數據的平均長度、長度最大值、序列總數、項總數、不同的項數、總字節數。

3.根據權利要求1所述的一種海量數據的頻繁序列挖掘方法，其特征在于，所述步驟1)通過單次MapReduce作業完成。

4.根據權利要求1所述的一種海量數據的頻繁序列挖掘方法，其特征在于，所述步驟1)中，為每一個項聲明了一個整數標識符，并且完全用整數標識符的數組來表示序列，首先，按照項的頻率降序對整數標識符進行排序，然后采用字節變化編碼方式把項壓縮成為整數。

5.根據權利要求1所述的一種海量數據的頻繁序列挖掘方法，其特征在于，所述步驟2)中，構造ω-等價的劃分的步驟如下：

2-1)用極小性檢驗輸入時間序列是否與中心項相關；如果不相關，令如果相關，則執行一個對輸入時間序列的反向掃描以得到所有下標的右距離；

2-2)然后執行一個正向掃描，需要同時執行以下幾點：

(a)計算左距離；

(b)進行不可到達化簡；

(c)用空格替換不相關項；

(d)執行前綴/后綴化簡和空格化簡；

(e)使用γ+1個空格將輸入序列拆分成若干個子序列，這些子序列會被用于空格拆分方法，從而形成最后的輸出P_ω。

6.根據權利要求5所述的一種海量數據的頻繁序列挖掘方法，其特征在于，在進行劃分之前，首先，通過掃描集合F_σ,0,1(D)，其中集合中的項是按照頻率降序排列好的，將相鄰的項分為一組直到它們的頻率和大于設定值m，遍歷每一個項，完成分組；然后，針對每個分組，構造一個單獨的劃分。

7.根據權利要求5所述的一種海量數據的頻繁序列挖掘方法，其特征在于，采用PrefixSpan算法對劃分P_ω進行挖掘。