前面講到頻繁項集挖掘的關聯(lián)算法Apriori（機器學習(22)之Apriori算法原理總結(jié)）和FP Tree（機器學習(31)之頻繁集挖掘FP Tree詳解），這兩個算法都是挖掘頻繁項集的。而今天要介紹的PrefixSpan（PrefixSpan算法的全稱是Prefix-Projected Pattern Growth，即前綴投影的模式挖掘）算法也是關聯(lián)算法，但是它是挖掘頻繁序列模式的，因此要解決的問題目標稍有不同。

首先看看項集數(shù)據(jù)和序列數(shù)據(jù)有什么不同，如下圖所示。

左邊的數(shù)據(jù)集就是項集數(shù)據(jù)，在Apriori和FP Tree算法中已經(jīng)看到過，每個項集數(shù)據(jù)由若干項組成，這些項沒有時間上的先后關系。而右邊的序列數(shù)據(jù)則不一樣，它是由若干數(shù)據(jù)項集組成的序列。比如第一個序列,它由a,abc,ac,d,cf共5個項集數(shù)據(jù)組成，并且這些項有時間上的先后關系。對于多于一個項的項集要加上括號，以便和其他的項集分開。同時由于項集內(nèi)部是不區(qū)分先后順序的，為了方便數(shù)據(jù)處理，一般將序列數(shù)據(jù)內(nèi)所有的項集內(nèi)部按字母順序排序。

子序列和數(shù)學上的子集的概念很類似，也就是說，如果某個序列A所有的項集在序列B中的項集都可以找到，則A就是B的子序列。當然，如果用嚴格的數(shù)學描述，子序列是這樣的：

而頻繁序列則與頻繁項集很類似，也就是頻繁出現(xiàn)的子序列。比如對于下圖，支持度閾值定義為50%，也就是需要出現(xiàn)兩次的子序列才是頻繁序列。而子序列<(ab)c>是頻繁序列，因為它是圖中的第一條數(shù)據(jù)和第三條序列數(shù)據(jù)的子序列，對應的位置用藍色標示。

PrefixSpan算法的全稱是Prefix-Projected Pattern Growth，即前綴投影的模式挖掘，里面有前綴和投影兩個詞。那么首先看看什么是PrefixSpan算法中的前綴prefix。

在PrefixSpan中的前綴prefix通俗意義講就是序列數(shù)據(jù)前面部分的子序列。如果用嚴格的數(shù)學描述，前綴是這樣的：對于序列A={a1,a2,...an}和序列B={b1,b2,...bm},n≤m，滿足a1=b1,a2=b2...an?1=bn?1,而an?bn，則稱A是B的前綴。比如對于序列數(shù)據(jù)B=，而A=,則A是B的前綴。當然B的前綴不止一個，比如, , 也都是B的前綴。

接下來再看看前綴投影，其實前綴投影就是這兒的后綴，前綴加上后綴就可以構(gòu)成一個我們的序列。下面給出前綴和后綴的例子。對于某一個前綴，序列里前綴后面剩下的子序列即為我們的后綴。如果前綴最后的項是項集的一部分，則用一個“_”來占位表示。

下面這個例子展示了序列的一些前綴和后綴，還是比較直觀的。要注意的是，如果前綴的末尾不是一個完全的項集，則需要加一個占位符。在PrefixSpan算法中，相同前綴對應的所有后綴的結(jié)合稱為前綴對應的投影數(shù)據(jù)庫。

PrefixSpan算法的目標是挖掘出滿足最小支持度的頻繁序列。那么怎么去挖掘出所有滿足要求的頻繁序列呢？回憶Aprior算法（機器學習(22)之Apriori算法原理總結(jié)），它是從頻繁1項集出發(fā)，一步步的挖掘2項集，直到最大的K項集。PrefixSpan算法也類似，它從長度為1的前綴開始挖掘序列模式，搜索對應的投影數(shù)據(jù)庫得到長度為1的前綴對應的頻繁序列，然后遞歸的挖掘長度為2的前綴所對應的頻繁序列，。。。以此類推，一直遞歸到不能挖掘到更長的前綴挖掘為止。

下面對PrefixSpan算法的流程做一個歸納總結(jié)。

輸入：序列數(shù)據(jù)集S和支持度閾值α

輸出：所有滿足支持度要求的頻繁序列集

1）找出所有長度為1的前綴和對應的投影數(shù)據(jù)庫

2）對長度為1的前綴進行計數(shù)，將支持度低于閾值α的前綴對應的項從數(shù)據(jù)集S刪除，同時得到所有的頻繁1項序列，i=1.

3）對于每個長度為i滿足支持度要求的前綴進行遞歸挖掘：

        a) 找出前綴所對應的投影數(shù)據(jù)庫。如果投影數(shù)據(jù)庫為空，則遞歸返回。

        b) 統(tǒng)計對應投影數(shù)據(jù)庫中各項的支持度計數(shù)。如果所有項的支持度計數(shù)都低于閾值α，則遞歸返回。

        c)將滿足支持度計數(shù)的各個單項和當前的前綴進行合并，得到若干新的前綴。

        d) 令i=i+1，前綴為合并單項后的各個前綴，分別遞歸執(zhí)行第3步。

PrefixSpan算法由于不用產(chǎn)生候選序列，且投影數(shù)據(jù)庫縮小的很快，內(nèi)存消耗比較穩(wěn)定，作頻繁序列模式挖掘的時候效果很高。比起其他的序列挖掘算法比如GSP,FreeSpan有較大優(yōu)勢，因此是在生產(chǎn)環(huán)境常用的算法。

PrefixSpan運行時最大的消耗在遞歸的構(gòu)造投影數(shù)據(jù)庫。如果序列數(shù)據(jù)集較大，項數(shù)種類較多時，算法運行速度會有明顯下降。因此有一些PrefixSpan的改進版算法都是在優(yōu)化構(gòu)造投影數(shù)據(jù)庫這一塊。比如使用偽投影計數(shù)。當然使用大數(shù)據(jù)平臺的分布式計算能力也是加快PrefixSpan運行速度一個好辦法。比如Spark的MLlib就內(nèi)置了PrefixSpan算法。

不過scikit-learn始終不太重視關聯(lián)算法，一直都不包括這一塊的算法集成，這就有點落伍了。

參考：

1. 周志華《機器學習》

2. 博客園

   http://www.cnblogs.com/pinard/p/6323182.html

3. 李航《統(tǒng)計學習方法》