:::

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

image

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


PrefixSpan演算法 / PrefixSpan Algorithm

image

(圖片來源: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

pythonlogo

(圖片來源:First Steps With Python)

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

Python版本2.7.13 / Python version 2.7.13

image

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

必須注意的是,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

image

雖然實際上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:事件代號。可以用任何字元組成,除了逗號「,」。

image

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

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

2. 進行分析 / Start to analyze

image

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

image

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

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

image

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

image

這個表格非常地大,總共有五個欄位:

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

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

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

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

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

總共15 則留言 ( 我要發問 , 隱藏留言 顯示留言 )

  1. 我參考了pip的用法,在腳本裡面加入了安裝套件的程式

    寫法參考自這篇:
    https://stackoverflow.com/a/24773951/6645399

    然後還加入了GUI互動功能Tkinter
    選擇分析的檔案:
    https://stackoverflow.com/questions/3579568/choosing-a-file-in-python-with-simple-dialog
    用對話視窗輸入數字:
    http://interactivepython.org/runestone/static/thinkcspy/GUIandEventDrivenProgramming/02_standard_dialog_boxes.html

    也加入了判斷Python 2的Tkinter或Python 3的tkinter的寫法
    參考自這篇:
    https://stackoverflow.com/questions/25905540/importerror-no-module-named-tkinter

    大概是這樣

    回覆刪除
  2. 回覆 收信件 的問題
    http://blog.pulipuli.info/2005/12/blogger_113544406852218769.html#comment-3970071194

    1.不知道freq是否代表樣式出現的次數?

    http://blog.pulipuli.info/2017/08/pythonprefixspan-implement-sequential.html#postcatapythonprefixspan-implement-sequential.html0_anchor7
    最後輸出CSV檔案中其中一格欄位frequency就是次數


    2.程式內的minsup我好像調0.001~1000 都不會影響到輸出的結果.... ,不知道那參數實際上的用途是作為何者的門檻值呢?

    https://github.com/pulipulichen/PrefixSpan-py/blob/master/prefixspan.py#L92
    程式碼中的minsup是指minimun support最小支持度
    也就是最後出來探勘出來的循序樣式的頻率至少要高於這個門檻值

    但我不確定這個門檻值有沒有正常運作,看程式邏輯應該是有啦

    回覆刪除
  3. 很謝謝您的回覆,因為看到您的內容是打"frequency:有多少人共同擁有這個循序樣式。"
    所以我的想法是若有多位使用者,其多位使用者分別擁有多次相同樣式的事件,是否會僅計算一次呢?
    例如有三位使用者,分別都購買了蘋果、香蕉,其中一位使用者購買了七次蘋果、香蕉這樣的組合,其餘二位都僅購買一次此組合
    那是否此frequency僅會計算3次呢?還是說會計算為7+2次呢?

    哈哈,我了解其代表的意思,只是設定後發現100000和0.000001好像都一樣....

    非常謝謝您的回覆!很感激
    還是會出現7+2次

    回覆刪除
    回覆
    1. 好吧,我沒仔細確認它的程式定義
      感謝你的說明!

      刪除
  4. 不好意思,想請問一下,這是直接寫好的python的PrefixSpan實作嗎?
    還是需要做一些修改?

    回覆刪除
    回覆
    1. 您好,

      試跑看看,然後遇到什麼問題再來問問?

      刪除
  5. 今天有人在問,如果論文中使用了這篇的PrefixSpan演算法來探勘循序樣式的話,要如何引用呢?

    請引用PrefixSpan原始論文即可:
    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).

    因為我寫的程式只是簡化了原本chuanconggao的PrefixSpan-py專案的作法,沒有什麼創新之處,所以引用一手資料即可。

    回覆刪除
  6. http://www.cnblogs.com/pinard/p/6323182.html
    你好,我參考上面網址裡面的資料,丟進去你的程式跑,結果不太一樣欸

    回覆刪除
    回覆
    1. 作者已經移除這則留言。

      刪除
    2. To 汪皖翔,

      我檢查了一下,發現這個程式碼本身有問題。

      第一個問題出自於python程式碼原始演算法本身。這個演算法並不支援同一時間發生多個事件的情況。

      我試著調整,將序列資料<(ad)c(bc)(ae)>是被當成a&d, c, b&c, a&e這四個事件來分析
      但這並不符合原本PrefixSpan的作法

      第二個問題出自於我取得csv轉換成輸入資料格式之間的轉換法有問題

      這個問題會導致原本python演算法無法如期運作
      至於要如何修理,我得花些時間來研究
      我還是覺得Python很難寫啊

      刪除
  7. 同時我用R裡面的循序樣式探勘(arulesSequences)做驗證,結果跟網址裡面的一樣

    回覆刪除
    回覆
    1. 好的,我會再找時間測試看看,謝謝您的回饋。

      刪除
  8. 從不同方式試了看看,這些問題似乎無法輕易克服。
    以Python撰寫的PrefixSpan-py暫時不再維護。

    如果那天我會再需要用到循序樣式探勘,我應該會選擇其他程式語言來撰寫吧。
    那這個專案就到此為止了。

    回覆刪除
  9. 請問: 是否 有哪個軟體可幫助我們做比較快的影片中行為的編碼?您請助理先將學習者每個動作的時間點都先寫出來列在EXCEL上嗎?
    或者您是用某個平台去自動記錄學習者的每個動作發生的時間點與結束點?因為我之前的一個研究-是請了八個兼任助理-每個人平均花了至少六個小時以上 反覆看錄影帶 去做每個學習小組(兩個孩童一組)的各個動作(例如:閱讀字卡;兩人互相討論;聽老師講述等等)來寫下時間點記錄。 這個方式我覺得比較沒有安全感-因為要檢查兼任助理是否有記錯時間也是件重大工程

    回覆刪除
    回覆
    1. 您好,

      對於這個問題,我們可能會期待會有什麼可以自動識別聲音、畫面出現物品的工具,能幫我們自動在時間軸上標註事件。也許會有吧,多少會看到一些資訊工程的論文會提出能夠分類影片的演算法,但論文離實作通常有段不小的距離,我實際並沒有研究過影片分類的工具。

      另一個問題是,像是行為編碼這種質性研究,一般來說還要做信度評估,以確保編碼具有一定品質。所以您提到助理看完後老師也要看,在我看來這似乎是很正常的流程。可是您的問題似乎又像是想要擺脫信度評估這個環節,這讓我不太懂您的研究到底是何種定位?

      寶傑,你怎麼看?

      刪除