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

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

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

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

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

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

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

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