大數據集序列模式挖掘算法研究.pdf

1、序列模式挖掘是數據挖掘中的一個重要研究課題，其最早在1995年被Agrawal和Srikant提出。與其他的數據挖掘算法相比，序列模式挖掘算法主要是基于有序的數據集來挖掘出現頻率高的序列模式，它具有實用性和易于理解的優(yōu)勢，因此受到了國內外專家學者的廣泛的關注和深入的研究，其應用范圍也從最初的購物籃分析擴展到自然災害的預測、DNA序列分析、疾病診斷等諸多領域。
　　序列模式挖掘從其被提出到現在，產生了很多經典的算法。其中應用最為廣泛

2、的是PrefixSpan算法。該算法采用前綴投影技術，能夠有效地避免候選項集的產生，在一定程度上提高了挖掘的效率。然而PrefixSpan算法也有一些缺點，它需要構造大量的投影數據庫，構造投影數據庫不僅需要消耗巨大的內存，而且增加了掃描時間，降低了挖掘效率。針對這個問題，本文對PrefixSpnan算法進行了改進，提出了一種基于隔層投影的BLSPM算法，該算法可以大大減少投影數據庫的構造數量，從而提高挖掘效率。此外該算法提出序列模式值的

3、概念，通過計算每個頻繁序列的序列模式值，然后按照序列模式值的大小對挖掘結果重新排序，使之能夠找到最重要的序列模式。最后采用實驗驗證，分別從不同支持度、不同類型的數據集、不同大小的數據集三個方面來驗證BLSPM算法的挖掘效率。此外，針對BLSPM算法在大數據集下的挖掘效率較低的問題，本文提出了基于Map-Reduce的BLSPM算法，并選取了超市的商品擺放作為應用實例來驗證基于Map-Reduce的BLSPM算法的實用性和有效性。

4、　　本文的主要工作及創(chuàng)新點如下：
　　(1)改進PrefixSpan算法，提出BLSPM算法。首先進行有效的剪枝，即在構建投影數據庫時，如果序列模式中支持度小于最小支持度時，對其剪枝，將它們從序列數據庫中刪除，這樣可以減少部分投影數據庫的掃描時間。其次，提出一種隔層投影的方法，即在挖掘長度為奇數的序列模式時，按照原來的方式構造投影數據庫；在挖掘長度為偶數的序列模式時，不用構造投影數據庫，取而代之構造一個下三角的M矩陣，這樣可以大大

5、的減少投影數據庫的構造數量，從而可以減少投影數據庫的掃描時間。最后引入“序列模式值”的概念，將該算法的挖掘結果按照“序列模式值”的大小進行重新排序，從而能夠找到最重要的序列模式。
　　(2)通過實驗驗證BLSPM算法效率。首先對比兩種算法的挖掘結果，得出BLSPM算法能夠找到最重要的序列模式，從而更符合實際需求。其次分別從不同支持度、不同類型的數據集、不同大小的數據集三個方面進行實驗，驗證BLSPM算法在效率和性能上優(yōu)于Prefi

6、xSpan算法。
　　(3)將BLSPM算法Map-Reduce化。在實際的應用中，當面對海量的數據集時，BLSPM算法挖掘效率也面臨瓶頸，因此提出了基于Map-Reduce的BLSPM算法。該算法采用分布式處理的方式，將大數據集均衡劃分為多個小數據集，并在每個節(jié)點上并行的進行序列模式挖掘。該算法可以分為五步：數據分片，并行計數，構建下三角矩陣，均衡分組，并行挖掘。最后通過實驗驗證基于Map-Reduce的BLSPM算法的效率。第

7、一組實驗驗證算法在單機和hadoop平臺上加速比，第二組實驗驗證算法在不同大小數據集下的挖掘效率。通過兩組實驗得出，基于Map-Reduce的BLSPM算法能夠提升在大數據集下的挖掘效率。
　　(4)將算法應用到超市商品擺放的案例中。為了驗證算法實用性，將基于Map-Reduce的BLSPM算法應用到實際的案例中，首先通過分析超市的歷史銷售數據，將其進行清理、采樣等操作，使之轉變?yōu)樾蛄袛祿欤缓蟛捎没贛ap-Reduce的BL