盧海濤

摘 要：論文闡述了基于時(shí)間序列的模式挖掘的基本概念，對(duì)基于時(shí)間序列的模式挖掘經(jīng)典算法和增量挖掘、時(shí)間序列分段線性表示及相似性算法進(jìn)行了相對(duì)全面的介紹，對(duì)算法的特征做了詳細(xì)的論述。

關(guān)鍵詞：時(shí)間序列 序列模式 增量挖掘 數(shù)據(jù)挖掘

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2014）06（b）-0204-01

1993年，Agrawal提出關(guān)聯(lián)規(guī)則挖掘算法，但是關(guān)聯(lián)規(guī)則挖掘只針對(duì)單次事務(wù)內(nèi)部模式，不能挖掘出與時(shí)間關(guān)聯(lián)的事務(wù)間的聯(lián)系和趨勢(shì)。針對(duì)這個(gè)問(wèn)題，在1995年，Agrawal和Srikant再次提出序列模式挖掘算法，這是序列模式挖掘算法的第一次提出，算法概要為：給定一個(gè)序列集合，由項(xiàng)集構(gòu)成單一序列，然后給定由用戶指定的最小支持度閾值，序列模式挖掘算法發(fā)現(xiàn)所有出現(xiàn)頻率大于或等于指定的最小支持度閾值的頻繁子序列。序列模式挖掘在關(guān)聯(lián)挖掘中加入了時(shí)間屬性，用以挖掘事務(wù)之間在時(shí)間上的順序聯(lián)系，其作用是能夠從數(shù)據(jù)集中發(fā)現(xiàn)可以反映事務(wù)間聯(lián)系和規(guī)律的一些模式，進(jìn)而能夠預(yù)測(cè)事務(wù)將來(lái)的發(fā)展趨勢(shì)。

序列模式挖掘算法一般可將其大致分為一般算法、增量式序列模式挖掘算法和時(shí)間序列分段線性表示及相似性算法等。

1 一般序列模式挖掘算法研究

早期的序列模式挖掘算法大多是基于Apriori算法進(jìn)行的改進(jìn)，一般都基于在Agrawal提出的關(guān)聯(lián)規(guī)則挖掘中提及的所謂Apriori特性：任一個(gè)頻繁模式的子模式必須是頻繁的。Apriori All[1]、Apriori Some、Dynamic Some、GSP[2]等算法都是基于這個(gè)特性而構(gòu)造出來(lái)的。

最早提出的序列模式挖掘算法是Apriori All算法。之后提出的GSP算法改進(jìn)了Apriori All算法的執(zhí)行效率，加入了對(duì)時(shí)間的限制、擴(kuò)展了交易的定義、考慮了分類的概念，廣義化了序列模式挖掘應(yīng)用領(lǐng)域。之后提出的基于GSP的算法MFS，采用直接連接所有已知頻繁序列的方式生成不同長(zhǎng)度的候選序列，以期改進(jìn)算法執(zhí)行效率。更之后提出的PSP算法，主要是針對(duì)存儲(chǔ)頻繁序列和候選序列的存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)作了改進(jìn)，將GSP算法中的Hash-tree結(jié)構(gòu)改成了Prefix-tree，這進(jìn)一步減少了存儲(chǔ)序列所需的空間，并且對(duì)非序列模式的剪枝過(guò)程也更容易進(jìn)行。

基于所謂Apriori特性的這一類序列挖掘算法是采用分級(jí)式方式、通過(guò)產(chǎn)生候選序列進(jìn)行比對(duì)的方式進(jìn)行，其有如下一些局限性：（1）會(huì)有大量的候選序列集被產(chǎn)生出來(lái)。（2）需要對(duì)序列所在數(shù)據(jù)庫(kù)進(jìn)行多次掃描，運(yùn)行開(kāi)銷過(guò)于龐大。（3）對(duì)于長(zhǎng)序列模式的查找，通過(guò)掃描序列數(shù)據(jù)庫(kù)的方式也面臨諸多困難。

之后有人提出基于數(shù)據(jù)投影的序列模式挖掘算法，算法采用分而治之，逐步求精的思想，在序列模式挖掘過(guò)程中無(wú)需生成候選序列，這就減小了搜索空間，提高了算法執(zhí)行效率。經(jīng)典的算法包括FreeSpan和PrefixSpan算法等。

而基于垂直格式的SPADE算法，定義了格序列搜索模式，并采用簡(jiǎn)單連接方式來(lái)遍歷頻繁序列，僅需最多三次序列數(shù)據(jù)庫(kù)掃描過(guò)程就可以找到所有目標(biāo)序列。

之后又提出基于內(nèi)存索引的MEMISP算法，其思想是通過(guò)掃描外存數(shù)據(jù)庫(kù)將它轉(zhuǎn)換為MDB（內(nèi)存數(shù)據(jù)庫(kù)），跟PrefixSpan算法相比，算法執(zhí)行過(guò)程中不再掃描數(shù)據(jù)庫(kù)，也不需要生成候選序列和中間投影數(shù)據(jù)庫(kù)，比PrefixSpan得執(zhí)行效率更高，MEMISP算法的性能與數(shù)據(jù)庫(kù)的大小和數(shù)據(jù)序列的數(shù)量呈現(xiàn)線性相關(guān)性。

2 增量式序列模式挖掘研究

時(shí)間序列是時(shí)間相關(guān)的，期望挖掘出的目標(biāo)序列數(shù)據(jù)也在隨時(shí)間改變，所以增量式序列模式挖掘在時(shí)間序列模式挖掘上更為適合。在這一方面，有如下算法被提出。

GSP+算法基于GSP，其算法的主要改進(jìn)在于剪枝策略的變化，在對(duì)Hash-tree進(jìn)行剪枝時(shí)僅掃描更新部分的數(shù)據(jù)庫(kù)以檢測(cè)候選序列支持度。而基于MFS算法的MFS+也采用了同樣的剪枝策略。ISM算法[3]是基于SPADE算法進(jìn)行改進(jìn)的，其執(zhí)行效率有了極大提升，比起大多數(shù)序列模式挖掘算法來(lái)說(shuō)，效率提升了幾個(gè)數(shù)量級(jí)。ISE算法[4]對(duì)ISM算法作了改進(jìn)，在新序列的插入策略上做了調(diào)整。ISE是擴(kuò)展頻繁序列后綴，而IUS算法則是對(duì)前綴和后綴都進(jìn)行了擴(kuò)展。并且IUS使用了ISM定義的負(fù)邊界，并新定義了一個(gè)最小負(fù)邊界序列支持?jǐn)?shù)，IUS算法對(duì)于內(nèi)存空間的占用更少。

3 時(shí)間序列分段線性表示研究

分段線性表示法主要用來(lái)對(duì)時(shí)間序列進(jìn)行近似表示，具體方法是對(duì)時(shí)間序列中進(jìn)行特征點(diǎn)抽取，將抽取的特征點(diǎn)依次連接，構(gòu)成的線段序列就稱為時(shí)間序列的分段線性表示。時(shí)間序列分段線性表示研究中最重要的問(wèn)題就是如何進(jìn)行特征點(diǎn)抽取，目前主要的方法有PCA（Piecewise Const Approximation）方法、Landmark模型、重要點(diǎn)分段法和PLA（Piecewise Linear Approximation）方法等。

參考文獻(xiàn)

[1] AgrawalR，SrikantR.Mining Sequential Patterns，Proceedings of the 1th International Conference on Data Engineering.TaiPei：IEEE Computer Society Press，1995：3-14.

[2] AgrawalR，SrikantR. Mining sequential Pattems：Generalizations and Performance imProvements.In：APers PMG Mokrane B，etal，eds.Proc.of the 5th Int.1Conf.on Extending Database Technology.Heidelberg：Springer-Verlag，1996：3-17.

[3] parthasarathys，Zak1MJ，OgiharaM，etal. Incremental and interactive sequenee mining[C] //Proc.of the 5th International Conference on Information and Knowledge Management.KansasCity，NewYork：ACMPress，1999：251-258.

[4] MassegliaF，PoneeletP，TeisseireM. Incremental mining of sequential Patterns in large databases[J].Data and Knowledge Engineering，2003，46（1）：97-121.endprint