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

有效

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

1.一種基于Spark云計算平臺的并行序列模式挖掘方法，其特征在于：包括數據庫切分、支持度計數和投影數據庫生成三步驟，且三步迭代執行，直到沒有新的序列模式產生為止；

所述數據庫切分，具體實現包括以下子步驟：

步驟1.1：在第一次執行時，將原始數據庫切分成相同大小的數據庫分片，使每個數據庫分片中的包含的序列個數近似相等；將數據庫分片從HDFS中導入RDD中，接下來的所有MapReduce任務從RDD中讀取數據庫分片或生成的序列模式，并將該任務生成的投影數據庫或序列模式存入RDD中；

步驟1.2：在后續迭代執行時，將投影數據庫切分成相同大小的數據庫分片，使每個數據庫分片中的包含的序列個數近似相等；將投影數據庫分片存入RDD中，接下來的所有MapReduce任務從RDD中讀取投影數據庫分片或生成的序列模式，并將該任務生成的投影數據庫或序列模式存入RDD中；

所述支持度計數，利用一個MapReduce任務發現序列模式；其具體實現包括以下子步驟：

步驟2.1：在第一次執行時，調用第一個flatMap函數從序列數據庫片段中讀取每條序列，其中序列以<LongWritable偏移量， Text 序列>鍵值對的形式存儲；調用另一個flatMap函數將序列切分為項，產生<項，1>鍵值對；擁有相同鍵的鍵值對被合并傳遞給Reduce節點，Reduce節點調用ReducebyKey()函數計算<項，1>鍵值對的支持度，輸出支持度大于等于設定的最小支持度的鍵值對；這些鍵值對的鍵即為1-序列模式，值即為該1-序列模式的支持度計數；刪除原始序列數據庫中的非1-序列模式，形成新的序列數據庫，后續的MapReduce任務都基于此新的序列數據庫進行操作；

步驟2.2：在后續迭代執行時，每一個Map節點首先調用flatMap函數從投影數據庫片段S_i|_α中讀取每一行后綴序列，然后再調用另一個flatMap函數將后綴序列中的第一項切分出來，將這一項b加入到前綴α后產生<α+b, 1>鍵值對；擁有相同鍵的鍵值對被合并傳遞給Reduce節點；最后每一個Reduce節點調用ReducebyKey()函數計算<α+b, 1>鍵值對的支持度，輸出支持度大于等于設定的最小支持度的鍵值對；

所述投影數據庫生成，利用一個MapReduce任務為每個在支持度計數步中產生的序列模式生成相應的投影數據庫；其具體實現包括以下子步驟：

步驟3.1：每個Map節點調用flatMap() 函數讀取在之前的以α為前綴的投影數據庫中的后綴序列；

步驟3.2：每個map函數計算前綴α￠的后綴，以α為前綴的投影數據庫中的后綴序列中第一次出現前綴α￠的后綴即為α￠的后綴；其中α￠是以α為前綴的序列模式；

步驟3.3：將Map節點產生的鍵值對傳遞給Reduce節點，Reduce節點對這些鍵值對不做任何的處理，生成最終的投影數據庫。

2.根據權利要求1所述的基于Spark云計算平臺的并行序列模式挖掘方法，其特征在于：步驟1.1中，數據庫分片的數量與集群中Map節點數相同。