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

在審

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

本發明公開了一種海量數據的頻繁序列挖掘方法，首先用戶輸入時間序列數據，計算每一個項的頻率，并構造頻繁項集合，其次對于所有頻繁項，在Map構造ω?等價的劃分，然后對于構造的劃分在Reduce進行獨立的挖掘得到頻繁序列，最后將所有的頻繁序列集合并在一起，并過濾掉將重復的序列輸出。本發明提供了對輸入數據庫的一種劃分方法，能夠有效的提升算法效率；本發明在挖掘階段，可以采用任意一種現在已經成型的挖掘算法來進行挖掘，容易實現。

技術領域

本發明涉及一種海量數據的頻繁序列挖掘方法，屬于數據處理技術領域。

背景技術

最早出現序列模式挖掘概念的時候就提出了基于Apriori的改進算法，比如：AprioriSome，AprioriAll，Dynamic-some。之后，隨著算法的改進，基于Apriori思想，又有人提出了GSP算法，該算法規定了序列的時間限制、滑動時間窗口以及使用者規定的分類，這樣挖掘出來的頻繁序列更符合現實意義。后來又相繼有人提出MFS算法以及PSP算法，都對GSP算法的執行效率進行了改進。這些改進的算法都來源于Apriori算法的思想。但Apriori有自身的缺點，那就是都需要多次掃描數據庫，這對于海量數據來說需要巨大的時間效率，并且會產生大量的候選集，如果支持度閾值取得較小，或者頻繁模式較長，這個問題就會變得非常棘手。

由M.zaki等人提出了一種基于垂直存儲格式的序列模式挖掘方法SPADE算法，基本思想就是：首先將輸入序列數據庫通過某種手段轉換成垂直數據庫的格式，然后利用簡單的連接方法，采用格理論的思想來挖掘頻繁序列模式。其優點是：相比于Apriori系列算法，掃描數據庫的次數大大減少，挖掘過程從頭到尾只需3次掃描數據庫。但是SPADE算法也存在一些弊端，那就是其在講水平格式的數據庫變成垂直格式的時候需要額外的存儲空間和計算時間，并且這一算法當中用到的遍歷方法還是廣度優先遍歷方法，這就需要巨大的候選碼產生的代價。

最近幾年J.Han,J.Pei等人又提出了一種基于投影的頻繁模式增長的算法——FreesPan算法，這個算法后來經過改進演變成了PrefixsPan算法，性能進一步大幅度提高。FreeSpan算法的優勢是它能夠大大減少候選序列的產生，也減少了產生候選序列的開銷，并且能夠完全的發現全部的頻繁序列模式。但是，該算法也存在一些弊端，就是會產生大量投影數據庫，考慮到一種特殊情況，即如果有某一種模式出現在輸入數據庫當中的每一個序列當中，那么這個模式對應的投影數據庫相比于原來的數據庫就不會有所縮減；除此之外，如果長度為K的子序列可能在任意一個位置增長，那么搜索長度為(K+1)的候選序列就要考慮到每一個可能的組合，就會增加相當大的時間花銷。

多維序列模式挖掘的特點就是挖掘出多維信息當中用戶感興趣，有意義的信息，其在普通的挖掘序列模式方式的基礎上，同時考慮其他的維度信息。例如，對于消費者消費習慣這一數據中，消費者的性別，年齡，職業等信息就構成了多維的序列模式。這種模式含有更多有價值的信息，具有更高的應用價值。目前已出現多種多維序列模式挖掘算法，如：UniSeq，Seq-Dim和Dim-Seq其中UniSeq算法的主要思想就是通過把數據庫當中的多維信息分別嵌入到每個序列中，從而形成新的擴展序列數據庫，然后可以利用PrefixSpan算法對這個新的擴展的序列數據庫進行頻繁序列模式挖掘從而得到多維頻繁序列模式。

頻繁序列挖掘是一系列重要數據挖掘任務的基礎，例如在文本挖掘中，頻繁序列被用于構造機器翻譯的統計語言模型、資料恢復、信息提取以及垃圾郵件檢測，詞義聯想還可以被用于關系提取。在網頁使用挖掘和對話分析中，頻繁序列可以表示用戶某種共同的或通用的行為(如網頁訪問日志中的頻繁序列)。以上幾種情況以及一些簡單的應用程序中，頻繁序列挖掘的挖掘對象是巨大的，并且包含了以億為數量級條序列。例如微軟提供的一個基于數千億網頁的n維數據的使用權，谷歌出版的一個超過十億維度的預料庫。在這種情況下，一種可以處理海量數據的頻繁序列挖掘算法就顯得格外重要。對于現有的方法來說，一單數據集的大小是巨大的，那么運算開銷和內存使用仍然是非常巨大的。

發明內容