循序樣式探勘：以Python的PrefixSpan實作 / Implement Sequential Pattern Mining with PrefixSpan in Python

8月 23, 2017 Data Mining , Programming/Python 15 Comments Edit Copy Download

我之前用R的arulesSequences來做循序樣式探勘，但是在輸入的資料量過大的時候，arulesSequences沒辦法順利運作。這個問題就是循序樣式探勘AprioriAll需要產生候選項目的後遺症。所以我另外找尋了不需要產生候選項目的循序樣式探勘演算法，最後找到的就是以Python實作的PrefixSpan。我參考chuanconggao發佈在GitHub的PrefixSpan-py專案，調整它輸入資料跟輸出結果的方式，把它整理成更容易在Windows環境下使用。所有程式碼都公開在GitHub的保存庫「PrefixSpan-py」上，歡迎有需要做循序樣式探勘的朋友來使用。

PrefixSpan演算法 / PrefixSpan Algorithm

(圖片來源：PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth)

chuanconggao提供了PrefixSpan的原始論文連結：PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth

APA引用格式：

Han, J., Pei, J., Mortazavi-Asl, B., Pinto, H., Chen, Q., Dayal, U., & Hsu, M. C. (2001, April). Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth. In proceedings of the 17th international conference on data engineering (pp. 215-224).

我參考数据淘金者的4种序列模式挖掘算法的比较分析中對PrefixSpan的介紹，整理出以下對PrefixSpan的介紹：

PrefixSpan是一種序列模式探勘的演算法。通常含有循序樣式序列資料的資料庫可分成稠密資料集與稀疏資料集。稠密資料集有大量的較長模式和較高支持度(亦即較多人共同)的頻繁模式。在稠密資料集中有許多相似的事件，例如DNA分析或著股票序列分析。

稀疏資料集主要由短模式組成，其中長模式的支持度較小，例如超級市場的交易數據集(客戶買的東西都不一樣，而且一次購物的商品不多)，使用者在網站中的瀏覽頁面序列(每個人瀏覽的內容都不一樣，而且一次不會點選太多網頁)等。

PrefixSpan改進了FreeSpan演算法，即透過前綴投影發掘序列模式。PrefixSpan的中心思想是在投影時不考慮所有可能出現的頻繁子序列，只檢查前綴序列，然後把相應的後綴投影成投影資料集。每個投影資料集中只檢查局部頻繁樣式，因此在整個過程中不需要生成候選序列。

PrefixSpan適用於稠密資料集和稀疏資料集兩種，而且在稠密資料集中比傳統的Apriori類演算法更有效率，相對的缺點是PrefixSpan實作難度較高，目前仍較少人採用。

上面雖然寫說PrefixSpan很難實作，但是chuanconggao卻在prefixspan.py用不到80行就寫完了。感謝開放原始碼社群的蓬勃發展，感謝GitHub上雲集的高手，讓我們能夠站在巨人的肩膀上看得更遠。

環境配置 / Environment

(圖片來源：First Steps With Python)

接著要來說明如何使用PrefixSpan-py。以下我指的PrefixSpan-py都是在說我分支(fork)原始專案之後的改寫版PrefixSpan-py喔。

Python版本2.7.13 / Python version 2.7.13

PrefixSpan-py是以Python撰寫而成，不過因為裡面使用到的lambda語法是Python 2.7的版本，在Python 3底下運作會出錯，所以我建議大家安裝Python 2.7.13版本。

• Python 2.7.13 下載頁面：https://www.python.org/downloads/release/python-2713/

必須注意的是，Python不要安裝在有空格的路徑底下。建議採用預設建議的路徑，安裝在「C:\Python27」之中。我之前一直試著安裝在C:\Program Files\，結果一堆功能都不能用，原來是路徑不能有空格。

安裝模組docopt / Install module: docopt

PrefixSpan-py用到了docopt模組處理來自指令列的參數，請用pip指令來安裝模組。基本的指令是：

pip install docopt

或是

python -m pip install docopt

每臺電腦上使用pip安裝模組的方式通常都不會很順利。有問題的話請先Google看看吧。

使用PrefixSpan-py / PrefixSpan-py usage

環境配置好之後，接下來就可以來使用PrefixSpan-py了。

1. 準備行為序列資料集 / Preparing data set

• 範例資料：input.csv

雖然實際上PrefixSpan-py接受的是input.txt這樣的格式，但考慮到從資料庫取資料出來的程序，我會比較推薦大家使用input.csv試算表的格式。

在input.csv中包含了三個欄位：

• user_id：使用者的編號，可以用任何字元組成，除了逗號「,」。
• seq_id：序列編號，必須是以數字組成，數字越小表示越早發生、數字越大表示越晚發生。通常會推薦使用Unix時間戳記，比較容易跟資料庫的時間資料整合。要注意seq_id必須是數字，不可以包含空格或「-」字元。同一個使用者可以擁有不同筆但相同的seq_id，這時候程式會把相同seq_id的events合併。seq_id可以省略，程式會用行數前後作為seq_id。
• events：事件代號。可以用任何字元組成，除了逗號「,」。

接著把input.csv檔案放到input資料夾中，這樣就行了。

附帶一提，這邊使用的是逗號分割值CSV格式，不是Excel的xls或xlsx，也不是Open Document Format的ods喔。

2. 進行分析 / Start to analyze

接下來在PrefixSpan-py根目錄找到「prefixspan.bat」，執行它。

接下來就會看到命令提示字元跑出大量的資料。等它跑完就完成了。

3. 取得分析結果 / Get the result

接著到input的輸出資料夾「input-output」中，找到「input.csv」的分析結果「output-input.csv.csv」，用試算表軟體打開它吧。

這個表格非常地大，總共有五個欄位：

• score：itemset_length乘與frequency的數值，預設以此欄位遞減排序，表示儘可能找出越多人共有、越長的序列。
• itemset_length：探勘出來的序列長度，亦即這個序列中包含的事件數量。一般來說我們會想要找到較長的序列。
• frequency：有多少人共同擁有這個循序樣式。
• frequency_percent：多少比例的人共同擁有這個循序樣式，1表示所有人都有這個樣式。
• itemset：探勘出來的循序樣式。

我們以上面這個表格作為例子來說明：

PrefixSpan-py找到了一個序列，它的分數score是10，序列長度itemset_length是2個事件，有5個人的行為中都有這個序列，佔所有人的62.5%。序列本身所包含的兩個事件是「GL2_9&GL6_2」跟「GL2_6」，其中「GL2_9&GL6_2」是因為擁有相同的seq_id，所以兩個事件被合併為一個事件了。

這樣子就做完循序樣式探勘囉。

進階做法：指令列 / Advanced usage: Command Line

為了方便大多數使用者的操作，我把PrefixSpan-py操作過程簡化成上述三個步驟。不過實際上PrefixSpan-py是一個從指令列操作的工具。指令列的用法寫在prefixspan.bat中，內容如下：

python.exe prefixspan.py input 1000

第一個「python.exe」表示我們要執行一個python的程式，第二個「prefixspan.py」表示主要進行分析的程式碼prefixspan.py，PrefixSpan-py的所有關鍵動作都寫在這裡；第三個「input」跟第四個「1000」都是給prefixspan.py的參數，「input」表示要進行分析的資料夾名稱，「1000」表示要找出頻率最高的1000筆資料，也就是循序樣式探勘中的top-k做法。

你可以直接在其他程式中呼叫prefixspan.py，並且給與不同的參數，這樣子就能跟其他系統進行整合了。

小結 / In closing

雖然我使用了chuanconggao的PrefixSpan-py專案改編而成了PrefixSpan-py，但我花比較多時間在操作流程的簡化，並沒有很仔細的研究PrefixSpan的運作方式，也還沒有仔細驗證它是否符合邏輯，心裡總是覺得不太紮實。不過這就等下次要用PrefixSpan的時候再來驗證看看好了。

最後，在寫Python的時候真的是不得不稱讚這個程式語言。Python是我寫過最容易上手、閱讀起來最賞心悅目，任何想要的功能都可以稍微猜一下就順利寫出來，非常順手。特別是最近我也一併在寫R跟Perl，相較之下，Python真的很好用。難怪現在很多程式語言教學都直接以Python開始了，這的確是很好的起點啊。