王曉雪

摘要：序列模式挖掘是數(shù)據(jù)挖掘領(lǐng)域中的重要技術(shù)之一，應(yīng)用非常廣泛。利用序列模式挖掘算法能夠發(fā)現(xiàn)具有一定商業(yè)價(jià)值的模式規(guī)律，因此近年很多學(xué)者也對序列模式挖掘算法提出了改進(jìn)。本文首先介紹了序列模式挖掘算法的相關(guān)背景及應(yīng)用，然后對于各個(gè)算法進(jìn)行介紹和對比，最后，對序列模式挖掘的未來發(fā)展進(jìn)行了展望。

關(guān)鍵詞： 序列模式挖掘； Apriori； PrefixSpan； SPADE； MEMISP； SPIRIT

中圖分類號： TP311

文獻(xiàn)標(biāo)志碼： A

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

0引言

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

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

[BT4]1相關(guān)概念

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

項(xiàng)目：任一項(xiàng)目Ij（1≤j≤m），對應(yīng)超市中一類商品，對應(yīng)唯一一個(gè)條形碼。

項(xiàng)目集合：多個(gè)項(xiàng)目構(gòu)成的集合，也稱為項(xiàng)集，通常用I表示所有項(xiàng)目的集合。

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

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

支持度[WT5”HX]s[WT5”BX]：在事務(wù)數(shù)據(jù)庫中一個(gè)序列出現(xiàn)的概率，包含序列的事務(wù)數(shù)或者記錄數(shù)稱為該序列的支持?jǐn)?shù)。支持度的計(jì)算公式表述如下：

s=支持?jǐn)?shù)/數(shù)據(jù)庫事務(wù)數(shù)總數(shù)[JY]（1）

頻繁序列模式：minsup為預(yù)設(shè)閾值，當(dāng)一個(gè)序列支持度s滿足s ≥minsup時(shí)，即為頻繁序列。

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

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

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

2）emem；

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

投影：給定序列α， β（βα），α′α稱為α對應(yīng)序列β的投影（Projection），當(dāng)且僅當(dāng)同時(shí)滿足如下2個(gè)條件：

1）β是α′的前綴；

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

[WT5”BZ]

[BT4]2算法實(shí)現(xiàn)研究

[BT5]2.1Apriori算法及改進(jìn)

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

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

[BT5]2.2FreeSpan算法及改進(jìn)

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

[BT5]2.3SPADE算法

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

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

[BT5]2.4MEMISP算法

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

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

[BT5]2.5SPIRIT算法

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

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

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

[BT4]3結(jié)束語

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

參考文獻(xiàn)：

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.