[發明專利]一種基于垂直分解的并行頻繁閉序列挖掘方法

有效

• 申請號: 201611091669.1
• 申請日: 2016-12-01
• 公開（公告）號: CN106599122B
• 公開（公告）日: 2019-12-31
• 發明（設計）人: 趙宇海;印瑩;王國仁;李晨光;畢天馳
• 申請（專利權）人: 東北大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458
• 代理公司: 21109 沈陽東大知識產權代理有限公司
• 代理人: 梁焱

本發明提出一種基于垂直分解的并行頻繁閉序列挖掘方法，屬于數據挖掘領域，該方法采用序列求交的方式，縮短序列的長度，這相當于在豎直方向將原始序列分割成較短的序列；再從求交結果中選出K條差異度最大的序列，這又使得序列之間列數差異較大，兩步均可縮短挖掘時間；本發明提出壓縮頻繁模式的觀點，壓縮模式的好處在于減小了頻繁閉模式枚舉范圍，縮短挖掘時間，減小算法的時間復雜度；本發明采用現階段最流行的并行框架Hadoop實現頻繁閉序列挖掘算法；充分利用Hadoop的并行特點，將海量數據分散存儲到集群中的各個節點上，按照map函數、reduce函數的特點編寫算法，因為枚舉出的模式獨立的分發到不同節點進行檢測封閉性，因此本方法獲得較高的加速比。

技術領域

本發明屬于數據挖掘領域，具體涉及一種基于垂直分解的并行頻繁閉序列挖掘方法。

背景技術

現代社會，信息技術的發展日新月異，大量的數據存在于社會發展中的各個領域，其中最大的需求就是將這些數據轉變有效的規則或知識，這使得數據挖掘備受社會各方面的關注。從應用方向來講，數據挖掘可用于市場分析、客戶保全、欺詐檢測、產品控制和科學探索等多方面，而且隨著數據挖掘技術的發展，數據挖掘將會應用于越來愈多的領域，并將發揮重大的作用。數據挖掘是一門交叉學科，其融合了多種理論和技術，包括有人工智能、數據庫技術、模式識別、機器學習、數理統計、信息檢索以及數據可視化等眾多學科，這些學科的快速發展對數據挖掘技術的發展起到了重要的推動作用。數據挖掘是通過一系列統計分析和處理，從海量的信息中找出對我們有意義的信息，這些信息影響著我們的決策。

數據挖掘是在一些限制條件下，借助于某些特定領域的知識發現算法，從大規模數據中挖掘有用信息。在整個數據挖掘領域中，頻繁序列模式挖掘是其中的一個有重大研究意義的分支，它一般意義上是指發現某一時間段內出現頻率較高的子序列。Agrawal和Srikant1995年在文獻^[7]中提出了序列模式的概念。挖掘序列模式時為了分析消費者的交易序列。序列模式挖掘是數據挖掘中的一個重要組成部分，它與傳統的關聯規則不同，序列模式挖掘帶有時間信息，比如說城市交通數據序列、信用卡消費序列、大型超市客戶的購物序列等。這些數據中包含了大量的商業價值。

現有的挖掘算法，都是在單一計算機上進行操作的，而且這些算法并沒有減少算法的時間復雜度。現有的一種序列挖掘算法，是PrefixSpan算法，通過產生投影數據庫來進行序列挖掘，這種算法不需要產生任何的候選模式。

現有的挖掘算法按照序列模式的研究過程這個標準可劃分為四類；基本的挖掘算法、增量式更新算法、多維度多層次挖掘和周期模式挖掘算法。基本挖掘算法大部分都是基于Apriori性質的，如AprioriAll、AprioriSome、DynamicSome到后來的GSP和SPADE算法等，2000年韓家煒等提出了數據投影算法FreeSpan和PrefixSpan提高了挖掘效率。這些方法都是在單一計算機上進行操作的，這些方法無法對大數據進行處理，序列挖掘算法時間復雜度都是由數據的列數決定，但是原來的算法并沒有考慮如何所見列數，這種計算消耗大量內存，而且耗費時間。

發明內容

針對現有技術的不足，本發明提出一種基于垂直分解的并行頻繁閉序列挖掘方法，以達到通過減少數據的列數來減少算法的時間復雜度的目的。

一種基于垂直分解的并行頻繁閉序列挖掘方法，包括以下步驟：

步驟1、對原始數據庫掃描，將數據按行進行水平分片處理，并分別發送至不同的處理器中；

步驟2、對每個處理器中的數據進行垂直分解；具體為：

在每個處理器上，并行執行以下操作：

執行一條數據與數據集中的所有數據進行兩兩相交，獲得任意兩條數據之間的公共子序列，即候選模式集；

步驟3、將獲得的所有公共子序列進行合并和去重操作，得到挖掘前的候選模式集；