[發明專利]一種基于Spark云計算平臺的并行序列模式挖掘方法

有效

• 申請號: 201710482965.2
• 申請日: 2017-06-22
• 公開（公告）號: CN107346331B
• 公開（公告）日: 2019-08-20
• 發明（設計）人: 余嘯;劉進;吳思堯;崔曉暉;張建升;井溢洋
• 申請（專利權）人: 武漢大學
• 主分類號: G06F16/20
• 分類號: G06F16/20;G06F16/23
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 魏波

本發明公開了一種基于Spark云計算平臺的并行序列模式挖掘方法，針對現有的串行化序列模式挖掘算法在處理海量數據時計算能力低效的問題和現有的基于Hadoop的并行序列模式挖掘算法具有高IO開銷和負載不平衡的問題，設計了合理的投影序列數據庫切分策略，最大限度的解決了負載不平衡的問題。在此基礎上根據MapReduce編程框架的特性，對原始PrefixSpan算法進行了并行化，利用Spark云計算平臺的大規模并行計算能力提高了海量數據序列模式挖掘效率。本發明的技術方案具有簡單、快速的特點，能夠較好地提高序列模式挖掘的效率。

技術領域

本發明屬于序列模式挖掘技術領域，特別涉及一種基于Spark云計算平臺的并行序列模式挖掘方法。

背景技術

(1)序列模式挖掘技術

[文獻1]最早提出序列模式挖掘的概念。序列模式挖掘就是挖掘序列數據庫中頻繁出現的有序事件或子序列。序列模式挖掘作為數據挖掘研究領域中重要的研究內容之一，有著很廣泛的應用需求，比如用戶購買行為分析、生物序列分析、出租車頻繁軌跡模式發現、人類移動行為模式分析。以下是序列模式挖掘中的一些術語的定義。

定義1:對于一個集合I＝{i_k，k＝1，2，…，m}是一個包含m個不同項的集合，稱一個子集為一個項集。

定義2：序列是由多個項集組成的集合，記為S＝<s₁，s₂，…，s_n>，其中某個具體的序列的長度等于序列包含項的數目。假定某個序列的長度為l，則稱此序列是l-序列。

定義3：序列數據庫由<Sid，S>組成，其中第一列Sid表示序列號，第二列S表示序列的具體組成項集，每行表示一條序列記錄。

定義4：對于序列S支持度定義為序列S在全局序列數據庫中出現的次數。已知最小支持度，如果序列S的支持度不低于最小支持度，那么序列S就是序列模式。長度為l的序列模式稱為l-序列模式。

定義5：給定兩個序列α＝<a₁，a₂，..a_n>，β＝<b₁，b₂，…b_m>(m≤n)，β被稱為α的前綴當且僅當或a_m-b_m＝Φ.序列γ＝<a_m-b_m，a_m+1，…，a_n>被稱為α相對于β的后綴。

定義6：α是序列數據庫D中的一個序列模式，α的投影數據庫是以α為前綴的所有后綴的集合，記為S|_α。

[文獻2]提出了采用冗余候選模式的剪除策略和哈希樹來實現候選模式快速訪存的GSP算法。[文獻3]提出了基于垂直數據表示的SPADE算法。[文獻4]提出了基于投影數據庫的PrefixSpan算法。這些傳統的串行化算法雖然隨著數據結構的優化和挖掘機制的改變，在性能上有一定提高，但在面對大規模數據集時算法的處理速度往往達不到人們的要求。直到20世紀初，計算機硬件的急速發展極大的推動了并行序列模式挖掘算法的研究。國內外學者相繼提出了各種分布式序列模式挖掘算法。

[文獻5]提出了基于樹投影技術的兩種不同的并行化算法來解決分布內存并行計算機的序列模式發現問題。[文獻6]提出了通過語法序列樹減少數據傳輸量的DMGSP算法。[文獻7]提出了快速挖掘全局最大頻繁項目集的FMGSP算法。但是由于分布式內存系統或網格計算系統這些并行平臺并未提供容錯機制，所以在這些并行平臺上面實現的并行序列模式挖掘算法不具備容錯性。此外，在這些平臺上開發并行算法需要程序員具備大量的并行算法開發經驗。