盧海濤

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

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

中圖分類號：TP311 文獻標識碼：A 文章編號：1672-3791（2014）06（b）-0204-01

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

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

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

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

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

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

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

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

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

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

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

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

3 時間序列分段線性表示研究

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

參考文獻

[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