大數(shù)據(jù)集序列模式挖掘算法研究.pdf

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

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

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

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

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

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

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