一種改進的時間序列特征模式提取方法研究

史震

摘 要：傳統(tǒng)的時間序列特征模式提取算法，在基于前綴檢索的基礎(chǔ)上引入了項集間隔約束的思想，優(yōu)化了特征模式提取的質(zhì)量。本文在此基礎(chǔ)上引入了跨度閾值，對模式候選集進行了深度的剪紙及優(yōu)化，有效提高了特征模式的挖掘質(zhì)量。通過實驗結(jié)果證明，特征模式質(zhì)量改善明顯。

關(guān)鍵詞：時間序列；特征模式；跨度閾值

中圖分類號：TP311 文獻標(biāo)識碼：A 文章編號：1671-2064（2017）08-0254-01

隨著大數(shù)據(jù)時代的到來，時間序列方面的研究也逐步被重視并占據(jù)著重要的的地位。賈艷芳等人提出的基于改進的PrefixSpan算法[1]對序列化數(shù)據(jù)進行特征模式提取，其融入了MPP算法的思想，使其可以對單序列數(shù)據(jù)進行模式挖掘。該方法充分利用了序列的原始特性，但提取的模式候選集中序列之間的部分屬性存在較大的偏差，因此可信度較低，模式的特征性不強。

在單序列特征模式提取問題中，為了提高模式的可信度，謝飛等人提出了MAIL算法，該算法引入了項集間隔約束思想，從而避免了候選集中序列項集間隔的較大差異，在模式質(zhì)量方面有所改善和提高。但在滿足序列自身項集間隔約束的同時并未對序列之間跨度差異進行限定，因此在部分特征模式候選集中序列與序列之間的跨度差異較大，抗干擾性較弱，影響特征模式質(zhì)量。

本文在前人算法的基礎(chǔ)上引入了跨度閾值約束機制，通過模式候選集的模式過濾，優(yōu)化了特征模式的提取。經(jīng)驗證，提取的特征模式質(zhì)量得以顯著改善。

1 序列特征模式提取

1.1 跨度閾值

定義：跨度閾值。目標(biāo)序列S中，模式P匹配到的所有序列位置組成模式候選集M。在候選集M中，每一個序列都對應(yīng)一個跨度值L，在候選集總的跨度值中選取該集合中位數(shù)，記為MI，與MI差值的絕對值滿足自給定約束范圍的序列記為可用序列。其中，自給定約束范圍即為跨度閾值。

不同的跨度閾值對特征模式提取的影響不同，因此可以靈活的按需提取不同精度的特征模式，從而發(fā)現(xiàn)模式的潛在特性，細(xì)粒度化的提高特征模式質(zhì)量。

1.2 特征性判定

序列中滿足設(shè)定支持度的模式即為特征模式，由于序列本身周期性特點以及其中較多孤立干擾點的存在，其挖掘出的特征模式候選集中的序列之間存在互相重疊的特性，若重疊率較高，在一定程度上會影響特征模式的質(zhì)量，致使特征模式的特征性不明顯。

為了定性的表征特征模式的該特性，可以通過如下公式來計算得出，計算公式為：

其中，分母為特征模式候選集中所有序列的總跨度之和，分子為候選集中所有子序列段的跨度乘以其權(quán)重之和，其中權(quán)重為該重疊子序列個數(shù)的倒數(shù)，η的取值范圍在[0，1]之間。該值作為特征模式質(zhì)量參考值可以在一定程度上有效的判定出特征模式獨特性的強弱。

2 模式候選集結(jié)構(gòu)的改進

模式候選集用以模式的擴展，記錄匹配序列在目標(biāo)序列中出現(xiàn)的位置信息，并以首字符位置作為該模式匹配序列的索引標(biāo)記。為了保證模式的完備性和一致性，模式候選集采用如下數(shù)據(jù)結(jié)構(gòu)（模式候選集結(jié)構(gòu)（部分）見表1）。

由以前基于前綴式的檢索方式改為基于首字符位置的內(nèi)外混合式搜索方式。外部搜索加快了對模式位置的定位，內(nèi)部搜索實現(xiàn)了對特征模式的跨度閾值檢測。

3 實驗結(jié)果分析

3.1 實驗環(huán)境

所有算法運行在Pentium Dual CPU 3.0GHz，內(nèi)存為2GB的計算機上，使用JDK1.7開發(fā)環(huán)境實現(xiàn)。

3.2 數(shù)據(jù)來源及預(yù)處理

數(shù)據(jù)源采用提供的來自不同領(lǐng)域的3條時間序列的實際數(shù)據(jù)集：Ocean、Burstin和Advertisement，序列長度均為12000。

3.3 實驗對比分析

跨度閾值的引入對特征模式的提取質(zhì)量產(chǎn)生很大的影響，從提取的特征模式數(shù)量、特征η值這兩個方面進行對比。實驗參數(shù)：跨度閾值約束等級分為5和10，項集間隔約束采用g=[0，4]，支持度support=20。

經(jīng)實驗驗證，隨著跨度閾值約束逐漸增強，序列中提取出的特征模式數(shù)量較以往算法有明顯減少，但特征模式的特征η值均值有顯著提高，這表明特征模式候選集中序列之間的重疊率下降，特征模式的特征性和可信度得到明顯加強和提高。例如Ocean序列數(shù)據(jù)集，以往算法所提取的特征模式的特征η值均值僅為18.4%和42.1%，可見其中特征模式候選集中序列之間的重疊率較高，而改進算法的特征性均值提升至77.1%，在一定程度上剪去了重疊率較高的特征模式，突出了特征模式的特征性。

4 結(jié)語

跨度閾值的引入，一方面限定特征模式候選集中序列間跨度的差異，降低了特征模式候選集中序列之間的重疊率，提高了特征模式質(zhì)量；另一方面提供了一種將特征模式的特征性進行細(xì)粒度劃分的方式，為更深入的理解序列特征模式提供了依據(jù)。

參考文獻

[1]Pei J， Han J， Mortazavi-Asl B， et al. Prefixspan： Mining sequential patterns efficiently by prefix-projected pattern growth[C]//icccn. IEEE，2001：0215.