序列模式挖掘算法的研究

王曉雪

摘要：序列模式挖掘是數據挖掘領域中的重要技術之一，應用非常廣泛。利用序列模式挖掘算法能夠發現具有一定商業價值的模式規律，因此近年很多學者也對序列模式挖掘算法提出了改進。本文首先介紹了序列模式挖掘算法的相關背景及應用，然后對于各個算法進行介紹和對比，最后，對序列模式挖掘的未來發展進行了展望。

關鍵詞： 序列模式挖掘； Apriori； PrefixSpan； SPADE； MEMISP； SPIRIT

中圖分類號： TP311

文獻標志碼： A

文章編號： 2095-2163（2016）06-0132-03

0引言

隨著大數據時代的到來，數據中隱藏信息的重要性已不容忽視，因此，越來越多的學者致力于改進數據挖掘技術，各類研究開展均是期待該技術能夠具備強大性能，進而高效準確地獲取數據中的隱藏信息。序列模式挖掘技術就是數據挖掘領域中的一個重要研究內容，其應用范圍正日趨廣泛，如Web用戶訪問或購買模式發現、醫學診斷、自然災害預測，股票走勢預測等。

Agrawal和Srikant于1995年首次提出利用Apriori[1]算法，處理超市顧客購買記錄，發現其中的某些商品經常發生集中統一購買的銷售規律，用來指導超市經營者制定營銷策略、商品擺放、市場定位等。此后，則陸續推出了序列模式挖掘算法的系列成果。序列模式挖掘算法不僅僅可以發現商品間一同被購買的規律，還可以進一步發現記錄中呈現有先后順序的購買規律。

[BT4]1相關概念

本次研究以某超市購買記錄數據庫為例，探討定義如下概念。

項目：任一項目Ij（1≤j≤m），對應超市中一類商品，對應唯一一個條形碼。

項目集合：多個項目構成的集合，也稱為項集，通常用I表示所有項目的集合。

元素：每個元素Sj（1≤j≤n）均為任意多個項目構成的集合。一般來說，不同元素在數據庫中的時間戳不同，表示顧客一次購買的商品，多個元素的有序集合即為序列。

事務數據庫：事務數據庫T={T1，T2，…，Tn}中每個記錄Ti（1≤i≤n）都是一個事務，同時也是一個顧客的全部購買序列，一個事務包含多個元素。

支持度[WT5”HX]s[WT5”BX]：在事務數據庫中一個序列出現的概率，包含序列的事務數或者記錄數稱為該序列的支持數。支持度的計算公式表述如下：

s=支持數/數據庫事務數總數[JY]（1）

頻繁序列模式：minsup為預設閾值，當一個序列支持度s滿足s ≥minsup時，即為頻繁序列。

序列包含：[JP4]設有2個序列α，β，而且，α =〈a1 ，a2 ， …， an 〉，[JP2]β =〈b1 ，b2 ，…，bm〉，n ≤ m。如果存在整數1 ≤ j1

序列前綴：[JP2]設序列內元素中的項目按某種順序（如字典）排列。有如下2個序列模式α和β， 且α=， [JP]β= （m≤n），若β為α的前綴（Prefix），當且僅當同時滿足如下3個條件：

1）ei =ei，i≤（m-1）；

2）emem；

3）（em –em′）中的各項目均按順序排在em′中各項目的后面，并且序列α對應于β的后綴（Postfix）為序列。

投影：給定序列α， β（βα），α′α稱為α對應序列β的投影（Projection），當且僅當同時滿足如下2個條件：

1）β是α′的前綴；

2）α′是α的最大子序列。

[WT5”BZ]

[BT4]2算法實現研究

[BT5]2.1Apriori算法及改進

為發現超市顧客購物籃模式，Agrawal和Srikant于1995年設計提出了Apriori[1]算法對超市顧客購買記錄進行處理，發現商品啤酒和尿布之間的關聯規則，代表算法有AprioriSome、AprioriAll [1]、GSP（Generalized Sequential Patterns）[2]等。

Apriori算法的步驟為測試和剪枝，在其實現過程中需要多次掃描原始數據庫和產生大量候選集，因而對其的研究改進過程也從未停止。GSP算法則屬于類Apriori算法，其搜索策略與Apriori基本相同，均為寬度優先搜索，但在其基礎上卻添加了3項時間約束：最小間隔、最大間隔及滑動窗口，用來優質搜索用戶要求的時間段內頻繁序列，同時輔助修剪，并且在存儲由Lk-1自連接形成的候選集Ck時采用了哈希樹結構，達到了修剪Ck和有效縮減其構成的搜索空間的作用，然后根據Apriori性質找到Ck中的頻繁序列，若一個候選序列的全部子序列均為頻繁的，則該序列也為頻繁的。GSP只對其長度為k-1的子序列進行測試，若不滿足，則從Ck中去掉該候選序列。經過上述步驟后在測試階段，需要在哈希樹中搜索Ck中的每個候選序列，若在其中找到該候選序列，則將支持數增1。實驗證明，GSP在效率上與Apriori算法相比則高達20倍。

[BT5]2.2FreeSpan算法及改進

為避免產生與Apriori算法類似的問題，Han在2000年研究提出了FreeSpan[3]算法，其中創建性地構造了數據投影的概念，Pei 等人在2001年也就隨后提出了PrefixSpan[4]算法，即是基于FreeSpan的改進算法，通過采用分而治之的思想，處理過程中會不斷生成多個更小的投影數據庫，來代替原始數據庫，因此在各個投影數據庫上進行遞歸挖掘能夠縮小搜索空間，并且也不產生候選序列，對應設計可描述為：每次在數據庫中搜索頻繁1-序列，將其連接到之前發現的頻繁序列上，重新創建新序列的投影數據庫，遞歸查找頻繁1-序列，重復上述步驟，直到無法再找到頻繁1-序列為止，最后形成的頻繁序列即為結果。在實現過程中，該算法在整體上設計展現了3種投影技術：逐層投影、隔層投影以及偽投影，來提高算法性能，并且共掃描原始數據庫2次，對于大型數據庫、較長的序列模式均可達到滿意預期，同時也更容易加入約束，運行時間和空間上則要優于FreeSpan、GSP和SPADE[5]算法，缺點卻是支持度較低時效果欠佳，并且時間將重點消耗在投影數據庫的生成和建立上。

[BT5]2.3SPADE算法

在傳統的事務數據庫中可以執行以上類Apriori算法，傳統數據庫的結構為水平格式，原理組成可表示為（userID，Time，Items），其中每條記錄都是一個顧客的購買序列。而Zaki于2001年獨立研發的SPADE（Sequential Pattern Discovery using Equivalence classes）[6]算法，其搜索策略與Apriori相同，也為寬度優先搜索，但不同之處則在于，該算法在進行搜索前，需先將水平格式數據庫轉換為垂直格式數據庫，轉換后的結構可設置為（Items，SID，EID），具體如表1所示。其中，每個序列下對應多條記錄，如序列（Items）A對應的SID和EID分別為（1，10），在含義上則特指序列A的一次發生位置，其中序列號SID=1，元素編號EID=10。對于其中序列的支持數的取值即為對應序列下不同的SID總數。

在此，研究中分析得出SPADE算法的基本思想：首先掃描數據庫一次，找出所有的候選集C1，轉化成長度為1 的ID-表，計算支持度，產生頻繁1-序列L1。然后以2個序列的SID相同為連接前提條件，對L1中任意2個序列處理實現自連接，產生候選2-序列C2，再對C2中序列的SID總數展開統計運算，產生頻繁2-序列L2，依次執行，直到不產生候選序列為止。整個搜索過程僅需掃描3次數據庫，與序列長度無關，因而與Apriori算法形成了不同的技術設計，極大減少了掃描數據庫次數，這即是該算法的顯著獨特優勢，而且支持度的計算也可歸結為快捷簡單。實驗表明SPADE算法在效率上要超過GSP，尤其在計算頻繁集L3到Lk時，SPADE會比GSP高出3倍、以至一個數量級，即使受到支持度閾值較低時的影響，SPADE算法的效率仍可保持為GSP算法的2倍范圍。[JP2]但因為SPADE算法和Apriori算法一樣都會產生候選集，使得Apriori算法中的問題也將概莫能外地出現在SPADE中。[JP]

[BT5]2.4MEMISP算法

在接下來的2002年，Lin和Lee中又研創開發了MEMISP （memory indexing for sequential pattern mining） [7]算法，提出采用一種內存索引的方式來處理大型數據庫。MEMISP的基本思想為：首先掃描一次數據庫，對于能夠存儲在內存中的數據庫，將其以MDB （memory database）的形式存入內存中，同時通過測試支持度找出L1，然后再利用L1以及構造內存索引來生成C2，最后在MDB上利用索引技術根據支持度找到L2。遞歸執行直到再沒有其他頻繁模式產生為止。這個挖掘過程僅需遍歷1次數據庫。若經過掃描發現數據庫無法裝入內存，則將其分解為多個部分存入內存，對每個部分將各自應用MEMISP找出頻繁模式，集成后形成的序列集合為整個數據庫的候選集，最后根據支持度再次遍歷數據庫確定候選集中的頻繁序列，整個過程僅需遍歷數據庫2次。

MEMISP的優勢是挖掘過程中無需構造投影數據庫，也并未產生大量候選序列，并且掃描原始數據庫次數極少，最多2次。實驗結果表明，MEMISP在效率上要高于GSP和PrefixSpan算法，而且隨著數據庫容量和數據序列長度的增減，也同時伴有良好的線性可伸縮性。

[BT5]2.5SPIRIT算法

在傳統算法中，用戶只能通過最小支持度，以及提供經驗判斷的方式來參與挖掘，但仍會產生大量的無用結果。為了提高用戶參與度，Garofalakism有針對性地推出了SPIRIT （sequential pattern mining with regular expression constraints）[5]算法，也就是通過利用正則表達式來描述用戶特定要求，從而發現用戶感興趣的序列的方法。這種方法不必再運行處理用戶不感興趣和無用的潛在的模式，因此免去了在這些方面的算法開銷。

為了控制正則表達式，SPIRIT算法中拓展加入了一系列能夠讀取和中斷正則表達式限制的操作，并且綜合考慮同時滿足支持度與用戶約束條件的序列模式，在此基礎上文中又根據實際需要提出了4種約束強度不同的算法，按照約束程度依次增強的順序，分別是SPIRIT [N]、SPIRIT[L]、SPIRIT[V]、SPIRIT[R]。

綜上所述，除了文中研究探討的算法外，還有考慮不同維度屬性的多維序列模式挖掘，數據庫更新情況下的增量式序列模式挖掘，以及挖掘再生模式的周期模式挖掘等。

[BT4]3結束語

近年來，序列模式挖掘雖然已取得了長足進步與可觀成就，但卻仍處于完善發展的進程階段，有其必須面臨的問題，如效率并不理想，缺乏有效人工參與，評價標準未臻置統一等。因此后續研究方向還是將圍繞在提高算法效率、縮小搜索空間、以及現有挖掘算法的高效深入融合研究上。

參考文獻：

AGRAWAL R， SRIKANT R. Mining sequential patterns[C]//ICDE '95 Proceedings of the Eleventh International Conference on Data Engineering. Washington， DC， USA：IEEE Computer Society，1995：3-14.

[2] [JP3]SRIKANT R， AGRAWAL R. Mining sequential patterns： Generalizations and performance improvements[C]//[JP]Proc 5th Int Conf on Extending Database Technology（EDBT）.Avignon， France：Springer，2010， 31（6）：176-184.

[3] [JP3]HAN Jiawei，PEI Jian， MORTAZAVI-ASL B， et al. FreeSpan：[JP]Frequent patternprojected sequential pattern mining[C]//Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining. Boston， Massachusetts， USA：ACM，2000： 355-359.

[4] PEI Jian，HAN Jiawei， MORTAZAVIASL B， et al. Mining sequential patterns by pattergrowth：The PrefixSpan approach[J]. IEEE Transactions on Knowledge and Data Engineering，2004，16（11）：1424-1440.

[5] GAROFALAKISM N， RASTOGI R， SHIM K. Spirit： sequential pattern mining with regular expression constraints[C] //Proc of the 25th International Conference on Very Large Databases. San Francisco， CA， USA ： ACM， 1999： 223-234.

[6] ZAKI M J.SPADE： An efficient algorithm for mining frequent sequences[J]. Machine learn， 2001，42（1）：31-60.

[7] LIN Mingyen， LEE S Y. Fast discovery of sequential patterns by memory indexing [C]//Proc of the 4th International Conference on Data Warehousing and Knowledge Discovery. London， UK： ACM， 2002： 150-160.