:::

循序樣式探勘工具 Sequential Pattern Mining Tool

觀察樣本
  • 每一個字都表示一個編碼記錄,請用空格、斷行來切割不同使用者的序列,用括弧表示同時發生的不同編碼。
  • 舉例1 「ABDC CBBD」:表示有兩個使用者的序列,他們所做的行為依時間排序為「ABDC」、「CBBD」。
  • 舉例2 「A(BD)C(CB)BD」:表示有一個使用者的序列,而他的序列中(BD)表示同時發生B跟D這兩個事件、(CB)表示同時發生了C跟B這兩個事件。
  • 使用者的序列越多,越容易找出循序樣式。
  • (Google Chrome不到1分鐘即可計算完畢)
  • (Google Chrome大約要跑10分鐘)
最小支持度

說明

AprioriAll循序樣式探勘演算法的目的是探勘出多位使用者的共通循序行為樣式。循序的意思是有考慮到順序先後,但並不一定會是相鄰的動作。

在輸入觀察樣本資料,使用者每一個動作都是一個「編碼」,請利用單一文字來表示使用者的行為,例如0表示登入、1表示閱讀、2表示撰寫資料。並以空格或換行來區隔不同的使用者。

接著請設定最小支持度,值為0到1之間,表示你想要探勘的樣式至少佔總人數的多少比例。舉例來說,0.6表示至少要有六成的使用者都有共同的循序樣式。最小支持度越低,運算時間越長、能找出來的樣式越多,但這些樣式不一定是很多人共通的;最小支持度越大,運算速度越快,而且能篩選出大部分的人都有的共通循序行為樣式。當你的觀察樣本中,每位使用者的行為都完全不相同時,最小支持度要設較低才能看出共同的循序行為樣式;當大部分使用者的行為都相同時,最小支持度可以設高一點,以加快運算的速度、篩選出最頻繁的循序行為樣式。

開始計算之後請稍待,此工具會幫你找出觀察樣本中出現次數高於最小支持度的樣式。此工具會盡量地探勘到最長的序列,而越長的序列也越有參考價值。

總歸來說,使用者人數越多,探勘出來的結果越有代表性,表示大部分的人都有這樣的行為。


感想

此方法是使用AprioriAll演算法實作而成,方便大家計算。但實際上這隻程式運算速度並不快,測試好玩用即可,不建議進行大量資料分析。

用來實作的程式語言是JavaScript,一如所料的,效率並不高。即使是用Google Chrome這種處理JavaScript很快速的瀏覽器,處理資料的速度依然很慢。除了JavaScript本來就不是講求高運算效率的程式語言之外,也這可能是我的演算法複雜度太高所致。

先不論演算法好壞什麼的,至少完成這隻程式能夠訓練邏輯。資料探勘果然是需要好的演算法跟資料結構的高度複雜方法,當運算結果能正確地探勘出來之後,就讓人感到非常興奮。雖然距離一個真正好用的工具還有很大的一段距離,不過至少實作出來還蠻自我感覺良好的吧。

這次考量到大量資料的處理,我用了非常多setTimeout()的延遲迴圈,避免程式在執行中造成視窗結凍,然而這樣的缺點是速度稍微會慢一點,但總比看起來就像是當機的視窗結凍來得好得多。此外也加入了「記錄」的功能,所以大家可以看得到處理的過程。後來覺得陣列搜尋速度太慢,所以應用倒置索引檔的資料結構概念,利用索引加快搜尋的速度。

作為小工具來說,這是一個對我來說是個完成度頗高的JavaScript程式。不僅僅只是實作一個資料探勘的方法,而是使用到多種JavaScript技巧、應用到資料結構與演算法的理論、挑戰基礎邏輯問題等等,都讓人感到身心舒暢,就像是做運動做得滿身大汗一樣的爽快感。

範例觀察樣本1是曾憲雄老師書中的例子,範例觀察樣本2則是手邊再處理的資料,預先丟進來跑跑看。至於各個編碼代表什麼意思,就請各位自行想像並應用了。

最後要說的是,計算過程如有任何問題或錯誤,請務必在下面留言告知,感謝。

參考文獻

  • 曾憲雄, 蔡秀滿, 蘇東興, 曾秋蓉, & 王慶堯. (2005). 資料探勘. 臺北市: 旗標.

修改記事

  • 2011/1/8: 撰寫完成。
  • 2011/1/5: 開始撰寫。